私は、Raftコンセンサスアルゴリズム（分散アルゴリズムの代表格）をPythonで実装しました。 かなりひどい実装です！ でも、（ある程度は）正しい実装でもあります。
同じような挑戦に興味がある人に向けて、伝えておきたいことをまとめました。
振り返ってみると、Raftを学び、正しく実装するうえで最も役に立ったのは、次の資料でした。
- Raftの論文（第5節まで読み、図2を何度も参照する）
- 学生のためのRaftガイド
- 最も広く使われているRaft実装の一つ
- リポジトリをクローンし、
raft.goにざっと目を通して、LLMとやり取りしながらコードベースと設計上の判断を理解する
- リポジトリをクローンし、
- Eli Benderskyのブログ連載
まず1時間ほど論文を読み、それから受信したバイト列を読み取って配列に追加するUDPまたはTCPサーバーのコードのひな形を書くのがおすすめです。 その後、私はEliの実装を追いながら、自分のRaft実装に同じ順序で機能を追加していきました。
リーダー選出らしきものが動くようになってから、バグや、アルゴリズムに対する自分の理解の誤りを探し始めました。 学生向けガイド、Raft論文の図2、自分の実装を行き来しながら、自分の実装がどこで一致しているか（あるいは異なっているか）を慎重に考えました。 このコードのレビューにもLLMを大いに活用し、その際は上記の資料をコンテキストに加えました。
ログ複製や永続化などについても、上の手順を繰り返します。
実装について
実装を簡単にするために、設計上いくつかの選択をしました。 順不同で挙げると、次のとおりです。
- 各ノードはシングルスレッドで動作し、メッセージを処理する
- システム内のローカルな「時刻」を管理するために「論理時計」を使う（たとえば、システム時刻を使う代わりに
tick()を呼び出し、各ノードのローカルなカウンターを増やす） - ネットワークデータの解析、ストレージ／永続化、Raftアルゴリズムの中核部分、ノード自体を制御するユーティリティやコマンドなど、すべてを1つのファイルに詰め込み、実装を「ごちゃ混ぜ」にする
2は堅実で正しい設計上の選択に思えます（etcdの実装でも論理時計が使われています）。 3は、学習や教育のためにはむしろよい、とも言えます。 すべてが1つのファイルにまとまっていると、一度に全体を見渡せて便利です。その実装をばらして、どんな抽象化がアルゴリズムに最もよく合うかを試すにも、ちょうどよい形になっています。
1は、個人的には少々問題の大きい選択だと思います。 確かに実装ははるかに簡単になります（デッドロックや、ノードの内部状態をアトミックに更新することをあまり気にせずに済みます）が、その結果、厳密にはRaftとは言い切れないものができあがります。 初めての実装なら、これでよいと思います。 アルゴリズムだけでも十分に複雑なので、ミューテックスをあれこれ調整するよりも、Raftアルゴリズムの中核部分にある論理的な誤りのデバッグに時間を使うほうがよいと思います。
この方法でRaftを実装するのは、30時間ほどのプロジェクトだと考えています。 最初にRaftの論文を読み、関連資料に目を通すのに数時間かかるはずです。 コーディングの大部分は、休暇中の約3日間、1日6〜8時間ほど手を動かして行いました。 今の実装には、まだ仕上げたり改善したりしたい点（たとえば微妙なバグの修正）が残っていて、これにはさらに半日ほどかかるかもしれません。
総じて、支える対象がこれほど多くのインフラに及ぶ中核的なアルゴリズムの一つを理解するための取り組みとしては、悪くないと思います。