Multi PaxosをJavaで実装してみた

Javaの練習と分散システムの理解のために、Multi Paxosの実装をしてみてた。16ファイルで970行程度で一応正常系は動くものはできたと思う。そろそろ疲れたので切り上げ。コードはださないけど、やったことをまとめ。

実装方針

この記事を何度も読んで、この通りに実装した。それに尽きる。

もちろんPaxos Made Simpleも読んだけど、実装するにあたっては上の記事がきれいにまとまってて必要十分だったので助かった。特にMulti Paxosについて丁寧に説明があるのでありがたかった。

まずはPaxosを実装

Paxosは単一の値の合意をとるためのプロトコルで、まずはここを実装した。上の記事通りに、Proposer/Voter/Arbiterの3 Roleをclassで実装。一応分けたけど、Peerとしてはどれも同じ役割にする前提を置いたので、それを束ねるPaxosクラスを作って使う感じ。

また、先にMessageを全て実装しておいたことで、それをどう扱っていくか?という観点で実装が進められたので楽だった。Messageは受け取ったらVisitor patternで処理を分岐させ、Thread poolに突っ込んでから処理させることで並列化したけど、Role毎にはsynchronizedつけて実質serialize処理にした。ちなみに最初は各所にBlockingQueueを挟みまくってたけど、その方針でも良かったのかもしれない。

最後にresolve処理として、Permission requestして合意が確認できるまでlock.wait()して待ち、Arbiter側で合意が取れたらlock.notifyAll()するようにして、pollingではなくresolveできるようにした。まぁ実際はひよってそれを更に適当にloopさせたけど。。。

ここまで多くの部分を机上でclassの実装を進めていて、実際実行してみることはなかった。型とIDEのおかげで、それだけでもちゃんと実装できた。ある程度目処がたったところで、簡単に動かしてみて、意外とあっさり合意形成できたのは感動的だった。Peerの数を増やしてもちゃんと動く。

Multi Paxosの実装

超難しかった。Paxosだけなら簡単だけど、こっちは本当に難しい。Stateの遷移が古い場合に過去を調整して更新する機能、Masterを選定し更新する機能、そしてアプリケーションが実際に更新する機能という複数の処理を不整合無く動かさないといけないのが、僕にはかなり大変だった。新しいPaxosに進む処理を可能な限り集約して、そこを注意して触るようにしたことでなんとかなったかなと思うが、多分バグは山ほどある。

過去を調整する機能は、もしPermission Request等がきて既に自分の歴史では合意が取れている場合には、その旨と合意した値を返してあげることでキャッチアップできるようにした。それを最新に追いつくまで繰り返すことで一応後追いでも参加できるようにした。

Master選定は別Threadにして、定期的にリース切れをチェックしながら、自分がMasterなら更新を打つ感じ。上の過去がない人がいる場合にどの場所で合意を取るのかといった部分の実装がレースコンディションで大変だった。

最終的には、一応Masterの選定・更新が走りながらも、アプリケーションの更新も含めて状態遷移が正しく複製されるところまではきた。とはいえ、考慮すべきケースは山ほどあって、全然カバーはしきれてない。でも一応動いた。

結果

  • 得られたもの
    • Paxos単体のアルゴリズムをそらで言える
    • Multi Paxosの難しさが語れる
    • 分散システムの想像力
    • java.util.(concurrent | function | stream)がちょっと使える
    • Multi thread楽しいけど辛い、monitorを正確に理解しきれてない
    • Visitor pattern分かったけど、やっぱpattern match欲しい
    • Inner classの使い勝手 (そんなに便利じゃない)
    • InterfaceとAbstruct classの使い勝手 (Java 9でInterfaceのprivateが入ったら便利そう)
  • もうちょっとやりたかったこと
    • アプリケーションとしての実装 (分散KVS)
    • packageの取り回し (今回は全部フラットなdefault package)
    • Loggerの扱い (System.out.printlnしか使わなかった。。。)
    • SerDe (インメモリ実装のみで、通信部分は省略したので)
    • 状態遷移の保存、復元、畳込み

今の仕事には役に立たないけど、寝る時間削って仕上げた甲斐はあった。Javaをちゃんと書いたのは初めてだったけど楽しい言語だし、自分が今まで触ってたスクリプト系の言語では正直ここまで実装するのは無理だったと思う。検索すればたくさん情報みつかるし、IDEでサクサク書けるしリファクタできるし、快適だった。

さて、次の課題を探しに行こう。