Raftコンセンサスアルゴリズム (2015)
(raft.github.io)- 分散システムで複数のサーバーが同じ決定を下せるようにする コンセンサス問題 を、より理解しやすく解きほぐすために Raft は設計されており、Paxos と同等の耐障害性・性能を目標としている
- Raft はリーダー選出、ログ複製、安全性といった下位問題に構造を分けることで、レプリケートされた状態機械 の実装に必要な判断ポイントを明確にしている
- サーバーの過半数が生存していれば処理を進められ、過半数が失われた場合は停止しても誤った結果を出さない方式で 安全性 を維持する
- サイトにはブラウザベースの RaftScope と The Secret Lives of Data の可視化、Raft 論文、TLA+ 仕様、検証・分析論文や講演資料がまとまっている
- Rust、Go、Java、C++、C#、Python などさまざまな言語の実装が整理されており、実装ごとにリーダー選出・ログ複製、永続化、メンバーシップ変更、ログ圧縮の対応範囲が異なる
Raftが対象とするコンセンサス問題
- Raft はコンセンサスアルゴリズムをより幅広い読者層が理解できるようにするために設計された
- 耐障害性と性能は Paxos と同等の水準を目標としている
- 核心的な違いは構造にある
- 問題を比較的独立した下位問題に分割する
- 実際のシステム実装に必要な構成要素を切り分けて扱う
- 目標は、コンセンサスベースのシステムをより理解しやすくし、より高品質に実装できるようにすることにある
コンセンサスとレプリケートされた状態機械
- コンセンサス(consensus) は耐障害分散システムの基本問題である
- 複数のサーバーが 1 つの値に合意し、いったん決定された値は最終状態となる
- 一般的なコンセンサスアルゴリズムは、サーバーの 過半数 が利用可能なときに処理を進める
- 5 台のサーバーからなるクラスターは、2 台のサーバーが障害を起こしても動作を継続できる
- それより多くのサーバーが失敗すると進行は停止する
- その場合でも誤った結果を返さないことが重要である
- コンセンサスは通常 レプリケートされた状態機械 を作るために使われる
- 各サーバーは状態機械とログを持つ
- 状態機械は、ハッシュテーブルのような耐障害性を持たせたいコンポーネントになり得る
- クライアントは、一部のサーバーが故障しても 1 つの信頼できる状態機械とやり取りしているかのように扱える
- 各状態機械は自分のログからコマンドを入力として受け取る
- ハッシュテーブルの例では
set x to 3のようなコマンドがログに入る - コンセンサスアルゴリズムは、どのコマンドをどの順序でサーバーログに入れるかを決める
- ある状態機械が
set x to 3を n 番目のコマンドとして適用したなら、他の状態機械が同じ位置に別のコマンドを適用しないことを保証しなければならない
- ハッシュテーブルの例では
- 結果として、すべての状態機械は同じコマンド列を処理し、同じ結果列と状態列に到達する
Raftを理解するための可視化
- ブラウザで動作する Raft クラスター の可視化を直接操作できる
- 左側には 5 台のサーバーが表示される
- 右側には各サーバーのログが表示される
- ユーザーは対話しながら Raft の動作を見ることができる
- RaftScope はまだ磨き込みの余地があり、Pull Request を歓迎している
- The Secret Lives of Data は Raft を別の形で見せる可視化である
- よりガイド型で、対話性は少ない
- 初めて触れる読者にとって、より穏やかな出発点になり得る
論文、仕様、検証資料
- In Search of an Understandable Consensus Algorithm (Extended Version) は Raft を詳しく扱う「Raft 論文」である
- Diego Ongaro と John Ousterhout が執筆した
- やや短い版は 2014 USENIX Annual Technical Conference で Best Paper Award を受賞した
- Diego Ongaro の Ph.D. dissertation は論文内容をさらに深く拡張している
- より単純なクラスターのメンバーシップ変更アルゴリズムを含む
- Raft の TLA+ 形式仕様 も含まれている
- やや更新された仕様は raft.tla で見ることができる
- 関連論文は、Raft の形式検証、分散システムの実装・検証フレームワーク、形式モデルに基づくコード生成、プロトコル分析を扱っている
- Planning for Change in a Formal Verification of the Raft Consensus Protocol, CPP 2016
- Verdi: A Framework for Implementing and Verifying Distributed Systems, PLDI 2015
- Automatic Distributed Code Generation from Formal Models of Asynchronous Concurrent Processes, PDP 2015
- Raft Refloated: Do We Have Consensus?, SIGOPS Operating Systems Review 2015
- ARC: Analysis of Raft Consensus, University of Cambridge Technical Report 2014
講演と教育資料
- Raft 入門向けの講演一覧もまとめられている
- John Ousterhout の CS@Illinois Distinguished Lecture Series 講演、2016年8月
- Jin Li の Dr. TLA+ Series 内の Raft と TLA+ 仕様に関する講演、2016年7月
- Diego Ongaro の Build Stuff 2015、CoreOS Fest 2015、Sourcegraph meetup、LinkedIn、USENIX ATC 2014、CraftConf 2014、RICON West 2013 の講演
- Ben Johnson の Strange Loop 2013 講演
- John Ousterhout の Raft User Study 講義、2013年3月
- 大学・教育課程でも Raft は講義やプログラミング課題に使われている
- University of Copenhagen、Czech Technical University in Prague、The University of Hong Kong、University of Virginia、UC San Diego、Technical University of Munich、UIUC など複数のコースが含まれる
- 一部のコースでは Go、Java、Erlang などによる Raft プログラミング課題 を提供している
- MIT 6.824 は Raft 講義ノートを含み、Jon Gjengset の教員向け・学生向けの Raft 解説記事も案内している
- 追加のコースは、サイトのリポジトリに Pull Request や issue を送って更新できる
質問チャネルと実装一覧
- Raft と実装に関する質問には raft-dev Google group が適した場として案内されている
- 一部の実装には独自のメーリングリストがあるため、各 README の確認が必要である
- 公開ソースコードのある Raft 実装 の一覧も提供されている
- 人気がある、または最近更新された実装が表の上部に配置されている
- 情報は時間の経過で古くなる可能性があるため、Pull Request や issue で更新できる
- 表では実装ごとの Stars、名前、主な作者、言語、ライセンス、機能対応状況を比較している
- 機能項目はリーダー選出とログ複製、永続化、メンバーシップ変更、ログ圧縮である
- 上位の実装例は次のとおり
- TiKV: Rust, Apache-2.0, 16,751★, リーダー選出・ログ複製/永続化/メンバーシップ変更/ログ圧縮をすべてサポート
- RethinkDB: C++, Apache-2.0, 27,000★, 主要機能をすべてサポート
- Seastar Raft: C++20, AGPL, 15,624★, 主要機能をすべてサポート
- hashicorp/raft: Go, MPL-2.0, 9,048★, 主要機能をすべてサポート
- hazelcast-raft: Java, Apache-2.0, 6,579★, 主要機能をすべてサポート
- 一覧には Rust、Go、Java、C++、C、Erlang、Python、Scala、C#、JavaScript、Haskell、OCaml、Kotlin、Zig、TypeScript、Elixir、F#、Shell など多様な言語実装が含まれる
1件のコメント
Hacker News の意見
Jepsen 作者による分散システム学習用ワークベンチ Maelstrom には、Raft のシンプルなモデル検査実装と実装チュートリアルがよくまとまっている: https://github.com/jepsen-io/maelstrom/
Raft はシンプルなアルゴリズムだが、原論文にはおもちゃ実装ではよく省略される正しさに関する細部が多く含まれている
実際のハードウェアにおけるメモリ/ディスク破損やグレー障害、厳しいレイテンシ SLA、柔軟なクォーラムと動的クラスタメンバーシップまで考慮すると、プロダクション実装は長く重い作業になる
etcd と hashicorp/raft のコミット履歴を見るだけでも、最も検証されているオープンソースの Raft 実装でさえ、正しさのバグが定期的に明らかになっていることが分かる
TigerBeetle チームは、不完全なハードウェアと抽象化されていないシステムモデルにおける分散システムの現実を詳しく扱っており、Paxos より古いが Raft により近く見える Viewstamped Replication を選んだ理由も説明している: https://github.com/tigerbeetle/tigerbeetle/blob/main/docs/DE...
実装上の悩みにどのような結果をもたらすのかはよく分からないが、論文自体が優れているので勧めたい
発表もあるが、前後を参照しながら見るには文章の方がよいと思う: https://www.youtube.com/watch?v=0K6kt39wyH0
コンセンサスアルゴリズムをまったく見たことがなかったのに、何度か読んだらある程度ついていけるようになった: https://dspace.mit.edu/bitstream/handle/1721.1/71763/MIT-CSA...
最近、Raft の リーダー選出 とログ複製を実装してみた。スナップショット/チェックポイントまでは行けなかったが、これまで取り組んだプロジェクトの中でも最も難しい部類だった
Raft 論文は読みやすく、直感をうまく与えてくれる
自分で実装していなくても、etcd、Consul、CockroachDB、TiDB のような Raft ベースのソフトウェアをすでに使っている可能性は高い
実装中に役立った資料はここにまとめてある: https://github.com/eatonphil/goraft#references
Diego Ongaro の博士論文と TLA+ 仕様も含まれている
「Raft 論文の Figure 2 だけで十分だ」と言う人もいるが、TLA+ 仕様と比べるとはるかに曖昧なので、そうではないと思う
MIT の分散システム講義の Raft テスト とつなげてみることをおすすめする: https://pdos.csail.mit.edu/6.824/labs/lab-raft.html
少なくともリーダー選出とログ複製の部分は、少しリファクタリングするだけで可能そうに見える
特に分散アルゴリズムに初めて触れる人には本当に勧められる
実装品質は大したものではないだろうが、興味のある人向けに置いてある: https://github.com/skowalak/fastapi-raft/
実装時に必要な具体的な細部が、論文の中にさらにいくつかある
コンセンサスアルゴリズムに興味があるなら、分散システム理論の授業で使っていた Reasoning about Knowledge という本も見る価値がある: https://mitpress.mit.edu/9780262562003/reasoning-about-knowl...
様相論理を学ぶのに少し投資が必要だが、そこを越えると Raft や Paxos がなぜ動作するのかについての証明が非常に直感的で簡単になる
証明の複雑さを、証明に使う論理構造の中へ押し込むやり方で、コンセンサスを見る観点を変えてくれた
「Raft Consensus Algorithm Failure」、Théodore Géricault、1819: https://classicprogrammerpaintings.com/post/6141087496359280...
可視化が何を示しているのか分からないなら、ノードを1つクリックして障害を起こせる点を見ればよい
特に現在のリーダーで、すべてのパケットを送受信しているノードで試すとよい
1つ目のスライダー横の小さな一時停止アイコンを押して再び時計に戻すと、シミュレーションが再開される
右側のスプレッドシートが何なのかはまだ分からず、常に空なので壊れているように見える
これまでに見つけたクリック可能な要素は、2つのスライダー、時計/一時停止アイコン、個別のサーバー
リーダーをクリックして
requestを選ぶと、コマンド送信をシミュレートできるレプリカを1つオフラインにすると遅れを取り、戻ってきたときに追いつく様子を見られる
数年前は、深刻な負荷の下でも堅牢なChubby風システムが常に重要な環境にいて、その頃は失敗が許されないなら ZooKeeper を使っていた
しかし今では、etcd や Consul のような Raft ベースの選択肢に、人々が何年も非常に重いワークロードを載せてきたと理解している
このうちどれかが今ではデフォルトの選択肢になったのか気になる
Raft の概念的な明快さと優雅さは、性能と信頼性につながりそうだが、この分野の感覚は古くなっている
2023年に Google や GCP に縛られていない人たちが、重要度の高いシステムで標準的なベストプラクティスとして何を使っているのか気になる
TiKV 側で作られたプロダクション品質の Rust 製 Raft 実装があった気がするし、堅牢で高性能なロックサーバーは Rust にかなり向いている領域に見えるが、実際に使われているのかも気になる
「Raftとは何か？」への答えがこれなら、読んでもまだ分からない
「Raftは理解しやすいように設計された合意アルゴリズムである。障害耐性と性能の面では Paxos と同等である。違いは、比較的独立したサブ問題に分解されており、実用システムに必要な主要部分をきれいに扱っている点である。私たちは、Raft が合意をより幅広い読者層に届け、その読者層が今よりも多様で高品質な合意ベースのシステムを作れるようになることを願っている」
こういうことは彼らだけの問題ではないが、自分たちの仕事をきちんと説明するのにもっと時間をかけないのは残念だと思う
意味が分からない読者を自動的にふるい落とすからだ
分散システムを作りながら複数の合意アルゴリズムを比較している人には単純で明確な説明であり、そうでないなら、そもそも関係のあるアルゴリズムではない可能性が高い
一般に合意アルゴリズムは、複数の物理デバイスにまたがるデータストアのレプリカがあり、デバイスや接続の一部が何らかの形で失敗したときに何をするかを決める問題を解こうとするものだ
「合意」と呼ぶのは、障害時にデータ片についてどんな決定を下すかをマシン同士が合意しなければならないからだ
例えば3台のサーバーが同じ SQL データベースを複製していて
(A) - (B) - (C)という形のとき、C と残り2台の間のネットワーク接続が切れれば、A と B はそれを把握して B をプライマリノードに昇格できるしかし C は何が起きたのか分からず、一部の書き込みを受け続ける可能性がある
接続が復旧すると、A、B、C はこれから何をするかを決めなければならない
B と C が互いに異なる書き込み集合を独立に受け取っていたため、サーバー群はデータの扱い方について合意しなければならない
Raft や Paxos などが一貫性があり性能のよい方法で解決しようとしている問題は、まさにこれだ
ある概念は、背景知識がまったくない人に1段落で紹介するには大きすぎる
それでもリンク先の記事は、読み進めれば優れた入門資料だと思う
合意プロトコル研究者として、過去10年のブロックチェーン研究のおかげで合意ははるかに理解しやすくなったと思う
Raft は、特に微妙な部分まで含めると、それに比べてギリシャ語のように読め、実装される
今から合意プロトコルを初めて学ぶ人なら、Bitcoin から始めて Paxos、Tendermint、Simplex に進ませ、Raft は完全に飛ばさせると思う
Simplex は私が書いた論文で、PBFT の単純化版だ
Raft は相対的に単純に見える
「リーダーを選び、ログを複製する」よりも保守しやすく間違えにくい点として、ブロックチェーンは何を提供するのか気になる
このサイトが好きだ
分散システムの授業で Raft を学び実装したとき、このページは本当に役に立った
論文自体もかなり読みやすい
Raft をこれほど明確にしてくれてありがとう
変更が必ずしもリーダーを経由しなくてもよい合意アルゴリズムがあるのか気になる
多くの分散システムでは、入力処理も分散したい
その一つが Chord: https://en.m.wikipedia.org/wiki/Chord_(peer-to-peer)
Chord は、ノードが値をコンシステントハッシュで分担する P2P リングである
ネットワークは “finger table” と呼ばれるものを活用するが、本質的にはレプリケーション情報を表形式で保存するもの
この表の情報が誤っていたり古かったりする場合があり、アクセスしたピアが別のピア、たいていは次のノードや後続ノードへ行くよう教えてくれるので、値が見つかるか見つからないと分かるまで進められる
このアルゴリズムが「リーダー」なしでも使える理由は、単に 1 つのノードへ行って全ノードを線形に走査する方法でも動作するため
クエリを高速化するための finger table は必須ではない
こうしたシステムでは通常、トランザクションごとに「リーダー」がいるが、正常動作ではその役割が競合しない
トランザクション調整役が自ら宣言する方式なので、調整役が何らかの理由で失敗したときだけ選挙が起きる
特定のデータやキーに対して複数のリーダーが同時に存在することもある
Cassandra は現在、この系統のリーダーレスプロトコルである Accord を開発中
実のところ Cassandra はすでに LWT でリーダーレスプロトコルを使っている
古典的な単一合意 Paxos の最適化版だが、同じキーに対して競合するトランザクションが同時に宣言されると、オーバーヘッドはかなり大きい
トランザクションが独立したトピックにまたがっているなら、リーダーをシャーディングして負荷を分散できる
キー空間の範囲を異なるリーダーに割り当て、各ノードが適切なリーダーシップの取り分を持つよう選挙を調整する方式
リーダーなしで進めるなら、各書き込みを事実上 1 つの選挙のように構成できる
暫定トランザクション、またはトランザクションが大きい場合は、トランザクション要求を全ノードにブロードキャストし、受諾クォーラムを得られれば勝利してコミットする、という形
しかし複数のノードがほぼ同時にトランザクションを試みると、合意に時間がかかることがある
ノードが多く、すべて同じトピックに対する待機中のトランザクションを持っているなら、リーダーを選んですべてのトランザクションをリーダー経由で送る方が、トランザクションごとに個別の合意を組むよりはるかに速い
ただしスループットのために分散したいという目的なら、Paxos が要求するクォーラムより、リーダー 1 つだけを必要とする方式の方が効率的かもしれない
推測ではある
Paxos も呼び出しが毎回同じ場所へ行くなら、より効率的
競合や再投票などを避けられるため
本質的には、各シャードがそれぞれ自前の Paxos 合意を持つ