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 でサクサク書けるしリファクタできるし、快適だった。
さて、次の課題を探しに行こう。
