Raftアルゴリズムの探求: 輪読会からの洞察
London Teck TalkのDDIA読了後最初の輪読会では、In Search of an Understandable Consensus Algorithm (Extended Version)を扱い、Raftコンセンサスアルゴリズムとその分散システムにおける適用について掘り下げた。この記事では、その議論から得られた洞察とRaftの実用的な側面について考察したい。
参加者
Raftのわかりやすさ
Raft以前のConsensus Algorithmの覇者だったPaxosは、現在でもGoogle Spannerなどの幅広い実装に使われているものの、わかりにくいことが最大の難点である。
一方でRaftはUnderstandability - 理解のしやすさに重点を置いていると論文の冒頭で述べられている。論文でありながらも比較的読みやすかったことは輪読会参加者のほとんどが触れており、最初の論文輪読会としてもいい選択肢だったと言える。
リーダー選出のプロセス
Raftの最大の特徴はLeader Election - Leaderの選出過程にある。
以下の図だけ見るとややこしいが、論文内では３つのNodeの役割 - Leader, Follower, Candidateについて順を追って説明されるので読んでみるとしっくりくる。
論文より、選出プロセスの説明
Kenさんがアナロジーとして出した実際の選挙の仕組みもわかりやすかった。
またシステムの可用性についての議論も盛り上がり、新しいリーダーが選ばれるまでの遅延がシステムにどのような影響を与えるか、どのようなメトリクスを用意したらいいかといった点も話題に上がった。
Clientとのインタラクション
Clientからのリクエストルーティングは議論が大きく盛り上がるポイントだった。
Strong LeaderもRaftの特徴の一つとして挙げられているように、選出によって選ばれたLeaderのみがFollowerに対してレプリケーションできる。
Leaderが短期間で何度も切り替わる場合、どのようにClientからのリクエストをLeaderに正しく振り分けるのかという点は議論のポイントとなった。
TomohisaさんはChatGPTに論文を読み込ませ、以下のメモを事前に残してくれていた。
クライアントの最初の選択がリーダーでない場合、そのサーバーはクライアントのリクエストを拒否し、最近聞いたリーダーについての情報を提供します
論文でも、LeaderからのリクエストにLeaderIdを含めることでFollowerがリダイレクトできる旨が記載されている
一方でTeppeiさんはetcdのドキュメントにも同様の記載があることもを見つけてくれた。
However, the client does not need to know which node is the leader. Any request that requires consensus sent to a follower is automatically forwarded to the leader.
マルチリージョン対応
また議論していく中で、マルチリージョン対応はできるのか、という疑問が上がった。論文では触れられておらず、輪読会の中でも答えはでなかったものの、VoteやReplicationに際して遅延が発生するだろうという結論になった。
この点について、Tomohisaさんが輪読会後に調べて共有してくれた。
調べたところ、Raftはマルチリージョンも考えられているが、基本的には遅いとのこと。ただ、この記事で説明されていましたが、優先リージョンというのを設定して、一箇所がメインの場所としておいて、２リージョン集まればOKという設定をすれば、一番遠いところの返事を待たずに確定していくことが可能とのことです。
Raftの実装と応用
Raftの実装については多くは述べらていませんが、Kenさんは、Apache KafkaがKRaft を実装して ZooKeeper 依存を無くそうとしている試みについて言及したり、その他多くの実装を各参加者が見つけてきてくれた。
話題に上がったDB実装としては以下が挙げられる
- Cockroach DB
- TiDB
- Yugabyte DB
- etcd
また、Raftの公式ページから他にも多くのOSS実装を見つけることができた。
過去の経験と照らし合わせる
Shuheiさんは過去の職場でコンセンサスアルゴリズムの独自実装を運用していた経験について話してくれた。当時Raftを知っていればよりよい実装ができたかもしれない、と経験談を共有してくれたのが興味深かった。この知識が実践で生きる時が来たら嬉しい。
また、当日参加できなかったKenさんもRaftの実装を運用していて起きた問題について事前にノート上でシェアしててくれた。こうした本では得られない実践をもとにした知識が得られるのも輪読会の醍醐味だ。
わからなかったこと
個人的には以下のポイントがわからず気になった。知っている人がいれば教えてほしい。
- Raftアルゴリズムを実装した上でPartitioningに対応するためにはどうしたらいいか
まとめ
私自身も全てを読み通したわけではなく、興味があるところをピックアップしているので、すべてを網羅できたわけではない。
しかし他の参加者のTakeawayや議論を通して読めなかった箇所の穴埋めをすることができ、Collective Intelligenceの醍醐味を今回も味わうことができた。
改めて輪読会の参加者の皆さんには感謝したい。
また、一つの論文を読み通したことについてTeppeiさんは
論文からアルゴリズムを理解するという初めての体験だったが、意外と理解できたことが自信に繋がった
と述べ、Tomohisaさんも以下のようにコメントしてくれた。
あまり学生の時や仕事でも論文を読むという機会がなかったので、ちょっと苦手意識があったのですが、読んでみたらこれに関しては読みやすくて、面白かった
引き続き輪読会の習慣を継続して、知識をブラッシュアップしていきたい。
Discussion