Paxos と Raft ― 分散合意を理解するために必要なこと

0章：イントロダクション — お金を動かす“合意”

こんにちは。久しぶりの投稿になります。
アドベントカレンダーの時期は、ふだん記事化できていないテーマに取り組む良いきっかけになりますね。
今年のテーマは 「Raft と Paxos」 です。
分散システムにおける合意（Consensus）アルゴリズムといえばまず Paxos が挙がります。しかしその説明は、歴史的背景も構造も含めて、とにかく難解です。一方の Raft は、あえて「理解しやすさ」を設計思想に据えて作られたアルゴリズムです。
本記事では、この2つのアルゴリズムを“歴史の Paxos” と “実装の Raft”という対比の軸で読み解いていきます。
ただし、いきなりアルゴリズムそのものに飛び込んでしまうと唐突なので、まずは「そもそも分散システムに“合意”はなぜ必要なのか？」という直感的なところから話を始めていきます。

---

0.1 分散システムで銀行口座を扱うという仮想世界（改訂案）

まずは、直感的に理解しやすい“仮想の銀行システム”で考えてみましょう。
これは実際の銀行の仕組みとは異なりますが、**「なぜ合意が必要か」**を説明するには最適な例えです。

一般的に銀行システムは RDB などを中心とした堅牢なアーキテクチャを持ちますが、ここでは一旦それを横に置き、次のような少し極端な世界を想定します。

• RDB を中央集約せず、各サーバが独立したコピーの残高データを持っている

• 3〜5 台のサーバに残高を複製し、どのサーバも同じ残高に到達する必要がある

• サーバは落ちたり復帰したりする

• ネットワークは遅延するし、順序も入れ替わり、メッセージがロスすることもある

（補足）
実際の金融システムや生命に関わるシステムでは、この記事で説明する合意アルゴリズムよりもさらに高い保証が必要です。そのため、ここで紹介するメカニズムが“どこにでも”使われているわけではありません。ただし 「どうやって複数台の状態を揃えるのか」 を理解するうえでは十分役に立ちます。

---

この前提のもとで扱う世界は、常に 不確実 です。

だからこそ、すべてのサーバが同じ状態に到達するためには
「操作が同じ順序で実行されること」
が絶対条件になります。

“合意”とは、この順序を全サーバで揃えるための仕組みなのです。

---

0.2 なぜ順序が重要なのか？

では次に、なぜ順序を全サーバで揃えないといけないのか を見ていきます。
これは直感的に理解できる部分なので、銀行の例で考えてみましょう。

---

例：2つの振込操作

1. A → あなた：＋500 円

2. あなた → B：−700 円

この 2 つの取引が同じ時刻に起きたとしましょう。

もしサーバ X が次の順で処理したら：

• A からあなたへ +500

• あなたから B へ -700
  → 最終残高： −200

しかしサーバ Y がこの順で処理したら：

• あなたから B へ -700

• A からあなたへ +500
  → 最終残高： −200 ……ではなく、
  “途中で残高不足扱いになり操作が拒否される” といった別の結果になる可能性があります。

---

つまり、順序が変わると結果が変わってしまう のです。
そして、複製している各サーバがバラバラの順序で操作を適用してしまうと、

• あるサーバでは取引が成立しているのに

• 別のサーバでは残高不足で拒否されている

といった 矛盾した状態 が発生します。

---

だからこそ、
「どの順序で操作を適用したか？」を全サーバで一致させる
必要があるのです。

ここからようやく「順序を揃える＝合意が必要」という話につながります。

---

0.3 State Machine Replication（SMR）という枠組み

先ほどの銀行の例で、
「すべてのサーバが同じ順序で操作を適用しないとズレる」
という話をしました。

この発想をより一般化した枠組みが State Machine Replication（SMR） です。
SMR は分散データベース、キーバリューストア、そして後述する合意アルゴリズムなど、幅広い分野の基礎になっています。

---

SMR の基本アイデア

SMR はとてもシンプルな考え方に基づいています：

１．全サーバが同じ「状態遷移のルール」（State Machine）を持つ
例：残高 + 入金額 のように、状態と入力から新しい状態を計算する関数。

２．全サーバが同じ「操作メッセージ」を受け取る

例：

「A → あなた：+500 円」
「あなた → B：−700 円」

3．それらの操作を同じ“順番”で適用する

これさえ守れば、各サーバは完全に同じ計算を行うため、
最終状態も必ず一致します。

---

合意アルゴリズムの役割は「順序を決めること」

そして、ここで登場するのが Paxos や Raft といった 合意アルゴリズム（Consensus） です。

彼らが解くべき問題は、実はとても限定されています：

次に実行すべき操作の“順序”を決めること。

それだけで SMR は正しく動き、複製されたサーバ群は最終的に同じ状態へたどり着きます。

---

0.4 なぜ Paxos と Raft を扱うのか？

ここまでで「なぜ順序が必要なのか」「なぜ SMR が必要なのか」を説明してきました。
では、順序を決める“合意”のためのアルゴリズムとして、なぜ Paxos と Raft の2つを取り上げるのでしょうか？

ここには大きく 3 つの理由があります。

0.4.1 理由1：Paxos は分散合意の歴史的基礎だから

Paxos は、
「故障が起きても、ネットワークが遅延しても、ノード間で正しい合意は可能である」
ことを世界で初めて理論的に示したアルゴリズムです。
現在の多くの方式（Multi-Paxos、VRR、Raft など）は、Paxos が確立した“正しさの条件”を土台にして構築されています。
また、Google Spanner の内部プロトコルや、Microsoft Azure の一部コンポーネントなど、
現代の大規模システムにも Paxos 由来の思想が多く使われています。
（もちろん “完全な原論文 Paxos” がそのまま使われているわけではありませんが。）
つまり Paxos は 歴史と理論の基礎 なのです。

---

0.4.2 理由2：Raft は“理解しやすさ”を最初から設計した合意アルゴリズムだから

Paxos が強力なのは確かですが、「分かりにくい」 という点が大きな課題でした。

そこで 2014 年、USENIX で Raft が登場します。
Raft のサブタイトルは “Understandable Consensus”。

Paxos が複雑になりがちな部分を

• リーダー選出

• ログ複製

• コミットの定義
  などに明確に分解し、「理解しやすさ」を第一に設計されています。

実際、多くの教育・実装ガイドでは、Paxos よりも Raft が標準的な教材 として扱われるようになっています。

---

0.4.3 理由3：Paxos（理論）と Raft（実装）を並べると両方分かりやすくなる

Paxos が難しいと言われる理由にはいくつかあります：

• 抽象すぎる

• 実用するための前提（Timeout、再送、ログ永続化など）がほとんど書かれていない

• 複数回の合意を行うには Multi-Paxos などの追加知識が必要

一方 Raft は、
「どう実装すればいいか」の詳細まで丁寧に提示されています。

端的にまとめると：

アルゴリズム	役割
Paxos	合意の本質を最小限に抽象化した“理論の基礎”
Raft	実際に実装するために整理された“設計指針つき合意アルゴリズム”

この2つを併せて学ぶことで、「Paxos の本質 → Raft の実装」という流れが非常に理解しやすくなります。

---

0.5 本記事の構成

本記事は、分散合意の「本質 → 理論 → 実装」という流れで理解できるよう、次の構成で進めていきます。

1. 分散環境で“順序”を揃える難しさ（直感）
   — 銀行口座の例を使いながら、「合意が必要になる理由」をまず直感をもって理解します。

2. Paxos の基本と、なぜ難しいのか
   — 抽象的な正しさを持つ一方で、なぜ読みにくく、なぜ実装しづらいのかを解説します。

3. Raft の設計思想と、なぜ理解しやすいのか
   — “Understandable Consensus” を掲げた Raft が、Paxos の複雑さをどう分解し整理したのかを見ていきます。

4. Paxos と Raft の比較（軽め）
   — この2つを並べることで、“理論 → 実装” のつながりがより明確になります。

---

それでは次章から、
「順序の合意がなぜ難しいのか？」
を直感的に解きほぐしていきます。

1章：分散環境で順序を揃える難しさ（直感編）

まずは、「なぜ順序に合意することがこんなにも難しいのか？」を、直感的な視点から整理します。

---

1.1 サーバは落ちるし、遅延するし、復帰する

分散環境で前提すべき世界は、次のように容赦がありません。

• サーバは突然落ちる（Crash）

• 落ちていたサーバが予告なく復帰する（Crash recovery）

• メッセージは遅延する

• メッセージの順序が入れ替わる

• メッセージがロスしたり、重複して届いたりもする

現実のクラスタでは、これらは「起こりうる」ではなく 日常的に起きるもの です。

Paxos（特にオリジナルの Single-Decree Paxos）は、これらの“クラッシュ故障”や“通信の不確実性”を前提に設計されています。
ただし昨年の記事でも書いたように、Byzantine（悪意ある故障） は対象外です。

---

1.2 順序が食い違うと、すぐに整合性が壊れる

前述の例を改めて考えてみましょう。

例：同じ振込2件でも順序が変わると結果が変わる

• Node A：先に +500 → 後で −700

• Node B：先に −700 → 後で +500

この2台の結果は一致しません。
片方で成功、片方でエラー。
順序がズレるだけで整合性は瞬時に壊れます。

だから、全サーバで「同じ操作を同じ順序で」適用する必要があります。

---

1.3 “順序合意”を邪魔するもの

順序を揃えたいだけなのに、分散環境では様々な要因がそれを阻みます。 

1.3.1 遅延したメッセージ（過去のゴースト）が後から届く問題

• すでに意味を失った古い提案番号のメッセージが

• 復帰したノードやネットワーク経路の遅延によって

• 唐突に、後から届く

これが順序を混乱させます。

（※分散環境では「過去のゴースト」が届くことは珍しくありません。）

---

1.3.2 リーダー不在または多数のリーダーが出現する問題

多くの合意アルゴリズムでは リーダー（代表者） が操作の順序を決めます。
しかしそのリーダー自身が落ちたり遅延したらどうなるか？

さらに悪いケース：

ネットワークが分断（Partition）すると、A側とB側で別々のリーダーが選ばれる

• A クラスタ：「こっちがリーダーだ！」

• B クラスタ：「いや、こっちがリーダーだ！」

結果：順序が分裂し、整合性は破壊されます。

Paxos ではクラスタの概念が曖昧ですが、Raft ではクラスタ構成が明確に存在します。
どちらにせよリーダーを1つに保つのは簡単ではありません。

---

1.3.3 復帰したノードが古い状態のまま合流する問題

Crash recovery の代表的な問題です。

復帰直後のノードはログが古く、
最新のノードと衝突する可能性があります。

• 復帰ノード：「これが正しい残高です！」

• 他ノード：「いや、それ古いよ……」

これを解決する仕組みが必要になります。

---

1.4 「順序に合意する」だけなのに、なぜこんなに難しいのか？

理由はとてもシンプルです。

分散環境には“共通の時間”が存在しない

NTP はありますが、分散アルゴリズムで使う時間とは「論理時間（イベントの順序）」であり、現実の「物理時計の時間」ではありません。

ネットワーク遅延があれば、“A のあとに B” が簡単に破壊されます。

だからこそ、「順序を揃えるための仕組み」が必要になります。
これが合意アルゴリズムです。

---

1.5 Paxos と Raft が登場する文脈

ここまでを整理すると、分散環境は次の条件を満たします：

• ノードは信頼できない（落ちる・遅れる）

• ネットワークも信頼できない（遅延・ロス）

• 時間も揃わない（時計の同期は前提にできない）

ただしここでの「信頼できない」は悪意（Byzantine）を含まない“クラッシュ故障のみ” です。

この厳しい環境であっても、

最終的にたった1つの順序に収束する仕組みが必要だった

これが Paxos が誕生した背景であり、その理解の難しさを整理して「実装しやすく」したのが Raft です。

---

この章では直感的な難しさを扱いました。
次章では、いよいよ Paxos の仕組みと、その難しさ に踏み込みます。

2章：Paxos ― 正しさは強力だが“理解しにくい”理由

Paxos は、分散合意アルゴリズムの古典として長く扱われてきた仕組みです。

「正しさが証明されたプロトコル」として評価される一方で、その理解や実装には非常に高い壁があります。

• 論文が読みづらい

• 登場人物とその役割が分かりにくい

• 状態遷移をきちんと追うのが難しい

• 実装しようとすると細かい落とし穴が多い

といった理由から、Paxos は“正しいけど難しいプロトコル”として知られてきました。

本章では、Paxos の全貌をすべて説明するのではなく、
「なぜ Paxos は理解しにくいのか？」を自然に感じられる最小限のポイントに絞って紹介します。

---

2.0 Paxos が扱う“状態”の基本

Paxos を理解するうえでまず重要なのは、各ノードが内部でどんな 状態（state） を持っているかを押さえることです。

最小構成（正常系・故障なし）では、実はごく少ない状態だけで Paxos は動きます。

その前提として、Paxos には 3 種類の論理的な役割があります。

---

Proposer / Acceptor / Learner の役割（前提）

Paxos では各ノードが次の 3 つの論理役割を持ち得ます。
※ これらは物理マシンとして分離してもいいし、1台がすべて担っても構いません。

🔵 Proposer（提案者）

• クライアントから値を受け取り、「この値で合意したい！」 と提案を開始する役割。
• 複数 Proposer が同時に動く可能性があるため、衝突しないための提案番号（プロポーザル番号） の生成が重要。
• Prepare / Accept リクエストを Acceptor に送る。

🟡 Acceptor（承認者）

• Proposer から送られてくる提案を受け取り、承認するかどうか判断する役割。
• Paxos の“安全性”を守る中心的存在。
• Acceptors の多数派が同じ値を受け入れれば、それが合意した値となる。

🟢 Learner（学習者）

• Acceptors で合意された値を受け取り、「最終結果」を知る役割。
  
• 実装では Leader や複数ノードがまとめて兼務することも多い。

以下で、各役割がどのような状態を持つかを見ていきます。

---

2.0.1 Proposer が持つ状態

Proposer が保持する状態は最小構成だと次の 2 つです。

■ n（プロポーザル番号）

• 単調増加し、他ノードと衝突しないように生成される番号。

• 「より新しい提案ほど優先される」ための指標。

役割：

• Proposer 同士の衝突を防ぐ

• Acceptor が「古い提案を受け入れない」ための制御に使う

---

■ value（提案値）

• クライアントから受け取った値
  　　　　または Prepare の応答で返ってきた “すでに選ばれかけている値”。

Paxos の基本ルール：

Acceptors が過去に受け入れかけた値があるなら、Proposer は その値を優先して再提案 しなければならない。

---

2.0.2 Acceptor が持つ状態

Acceptor の状態は次の 3 つ。

■ promised_n

「これより小さい番号の Prepare には応答しません」という“約束”。

• これによって、過去の提案で状態が巻き戻るのを防ぐ。

■ accepted_n

直近で受け入れた提案番号。（まだ何も受け入れていなければ空）

■ accepted_value

accepted_n に対応する実際の値。（こちらも初期は空）

---

2.0.3 Learner が受け取る情報

Learner が知るべき情報はただ1つ：

■ 合意された最終的な値

• Acceptors の多数派が一致した時点で「この値が合意された」と判断できる。

• 実装では Leader が Learn メッセージを集約し、
  各ノードへブロードキャストするなどの工夫がある。

---

状態の数は少ないが、時系列が難しい

こうやって状態だけ羅列すると、「意外とシンプルじゃない？」と思うかもしれません。

しかし Paxos の本質的な難しさはここからです：

　これらの状態が、Prepare / Accept のやり取りの中でどのタイミングで、どの順序で変化するのかが非常に複雑。

Paxos を理解する鍵は、「状態遷移の時系列を整理すること」ここを意識すると、理解が一気に進みます。

---

2.1 Paxos の「ふるまい」を最小構成で理解する

Paxos の本質は、Proposer / Acceptor / Learner が

決められたルールに従って状態を更新し合い、最終的に 1つの値 に合意することです。

ここでは 故障なし・正常系のみ に限定し、
Paxos がどう動くのかを「仕様としてのふるまい」で整理します。

---

1）Proposer のふるまい

Proposer の目的はただ1つ：

ある値 value をクラスタ全体で合意させること

そのために行う操作は大きく 2つ のフェーズからなります。

① Prepare（準備）フェーズの開始

1. 新しい提案番号 n を選ぶ
   （単調増加で、他の Proposer と衝突しない仕組みを用いる）

2. Acceptor 全員に
   Prepare(n) をブロードキャストする

目的：
「番号 n の提案を進めてもよいか？」を Acceptors に確認すること。

② Accept（提案）フェーズの開始

過半数の Acceptor から Promise（準備OK） を受け取れたら：

1. Promise の中に“過去に accept されかけた値” があれば、その中で最大番号の値を採用する

2. なければ自分が合意させたい value を使う

3. その値を Acceptor にAccept(n, value) として送信する

---

（2）Acceptor のふるまい

Acceptor は、Paxos の安全性（Safety）を守る中心的役割です。

守るべきルールは 2つ しかありません。

ルール① Prepare(n) を受け取ったとき（Promise のルール）

Acceptor は内部に promised_n を持つ：

「この番号より小さい Prepare には応答しない」

という保証。

受信した n が promised_n より大きい場合：

• promised_n = n に更新

• これまで自分が受け入れていた
  accepted_n と accepted_value を返信（＝ Promise）

これが Paxos の安全性の基礎です。

ルール② Accept(n, value) を受け取ったとき

もし n が promised_n 以上なら：

• accepted_n = n

• accepted_value = value

に更新し、Accepted(n, value) を返す。

過半数の Acceptor がこの応答を返した時点で、
その値が 合意された（chosen） とみなせる。

---

（3）Learner のふるまい

Learner は「記録係」です。

• 過半数の Acceptor から
  Accepted(n, value) が届いた値を
  chosen（合意された値） として確定する。

ふるまい自体は非常にシンプルです。

---

（4）Decide フェーズ（Learners への伝達）

値が chosen になったら、その結果を Learners へ伝える。

この通知に Total Order Broadcast のような強い保証は不要 ですが、

• 遅延してもよい

• 重複して届いてもよい

• 最終的には届くこと が望ましい

といった性質は満たす必要があります。

実装形態はさまざま：

• Acceptor が直接 Learner に通知する

• Leader（Coordinator）がまとめて通知する

• マルチキャストを使う

など。

---

(5）このフェーズ構造が理解を難しくする理由

ここまで見ると、

• 役割も少ない

• 状態も少ない

• ルールもシンプル

に見えます。

しかし Paxos が「理解しづらい」「実装しづらい」理由は：

これらのルールが“時系列”で複雑に絡み合うため

例えば：

• 複数 Proposer が同時に Prepare を送る

• 古いメッセージが遅延して後から届く

• 過半数が揃うタイミングがズレる

• Accept フェーズに入った後に別 Proposer の Prepare が割り込む

など、実際の挙動は「動的に変化する状態」を追いかける必要があります。

抽象的ルールだけだと直感的には理解しづらく、
これこそが「Paxos が難しい」と言われる理由です。

2.2 なぜ、この最小シナリオでも難しいのか？

Paxos が高く評価される理由の一つは、分散環境で起こりうる典型的な障害に対しても安全に動作する ことです。

ここでは、Paxos が想定している障害モデルを整理し、
「最小シナリオでも難しい」と言われる理由を説明します。

（1）Paxos が想定する障害モデル

Paxos は「実際の分散システムで普通に発生する問題」を前提に設計されています。

具体的には、次のような状況でも 安全性（Safety） を壊しません。

① サーバ（ノード）が突然落ちる（クラッシュ故障）

• 停電

• プロセスの異常終了

• カーネル panic

など、「止まる」タイプの故障は当然発生すると考える。
※ 任意の嘘をつく ビザンチン障害 は扱わない。

② メッセージ遅延・ロスト・重複

- ネットワークの遅延
- パケットロス
- 同じメッセージが重複して届く

Paxos 自体はこれを許容し、その上で安全性を保証する。
再送や重複排除は実装レイヤで行う。

③ 複数の proposer が同時に動く

複数の Proposer が同時に Prepare を投げることで、

プロトコルが競合する状況を想定。

④ 古いメッセージが後から届く

Example：

• Prepare(n=1) の後に送った Prepare(n=2) が先に届く

• Accept が遅延して “選ばれたように見える値” の時系列が乱れる

Paxos はこのような “メッセージ到着順の乱れ” を受け入れつつ、
安全に動作するように設計されている。

---

（2）時系列で整理すると見える Paxos の“動的な複雑さ”

Paxos が難しい最大の理由は：

静的ルールだけ理解しても足りず、時系列での相互作用を追わないと挙動が理解できないから

シンプルな正常ケースでも、時系列で次のように進む。

---

▼ 正常系の典型的な流れ（シンプル版）

• 時刻 0：Proposer A が Prepare(n=1) を送る

• 時刻 1：Acceptor 1,2 が Promise（OK）を返す

• 時刻 2：A が Accept(n=1, value=X) を送る

• 時刻 3：Acceptor 2 の Accept 応答が遅延

ここまではよくある正常ケース。

▼ 別 proposer の割込みと競合（やや複雑な版）

• 時刻 3：別マシンで Proposer B が起動し、Prepare(n=2) を送る

• 時刻 4：Acceptor 1,2 が Promise を返す

• 時刻 5：B が Accept(n=2, value=Y) を送る

このように、数ミリ秒の遅延やプロセス再起動があるだけで、
どの値が選ばれるかの条件が一気に変わる。

Paxos のルールはこれを安全に扱うために、どうしても複雑になります。

（3）ここで重要なのは「安全性と進捗性は別」ということ

Paxos を理解するうえで特に大事なのが、この区別です。

• Safety（安全性） … 2つの異なる値が選ばれることは”絶対に起きない”

• Liveness（進捗性） … いつかは値が選ばれる（ただし保証は弱い）

Paxos は Safety は常に強く保証する 一方で、
Liveness（進むこと）は Leader やネットワークの状況に依存 して変わる。

「正しいけど進まない状況があり得る」という点は、
実装者にとって非常に難しいポイント。

---

2.3 まとめ：Paxos の“難しさ”の正体

Paxos が難しい理由を整理すると：

• 状態は少ないように見えて、時系列で変化すると一気に難しくなる

• フェーズは 2つだけでも、複数のラウンドが並行実行して絡み合う

• Safety を満たすための条件が多く、割り込み・遅延・再送が頻発する

• 実装ではさらに

• leader 選出

• reliable broadcast

• ログ永続化
  などを決める必要があり、抽象仕様よりさらに重い

つまり、

Paxos は「理論的に正しい」。
しかし「理解しづらい」「実装しづらい」。

だからこそ、理解しやすさを最初から設計に組み込んだ Raft が
大きな意味を持ちます。

3章：Paxos を理解しても実装できない理由（抽象度統一版）

Paxos は「正しさ」を数学的に保証した、分散合意アルゴリズムの古典です。

しかし、論文を読んで理解しただけでは実装できないというギャップがよく指摘されます。

ここでは、Paxos を実際のシステムに落とし込む際に必要になる追加要素を整理し、
なぜ“理解したのに実装できない”という状況が発生するのかを明確にします。

（1）Leader（eventual leader）の扱いは抽象的

Paxos は「最終的に proposer の誰か一人が優位に立つ（eventual leader）」という前提を置きます。

しかし論文では、この leader に関する重要な点がほぼ説明されません：

• leader をどう選ぶのか？

• leader がクラッシュしたらどう検出するのか？

• 再選挙はどう設計するのか？

• 競合する leader が複数存在したら？

理論としての Paxos は「そのうち落ち着く」としか言わず、具体的な方法は実装者に丸投げです。
結果として、多くの Paxos 実装は独自のリーダー選挙を持っています。

（2）ブロードキャストの性質も実は実装側の責務

Paxos の各フェーズで必要なブロードキャストは、本当は種類が異なります。

論文では「Prepare を送る」「Accept を送る」と書いてあるだけですが、
実際のシステムでは メッセージの性質（信頼性・順序・重複排除） を実装側が担わないと Paxos は正しく動きません。

実際に必要な性質を整理するとこうなります：

フェーズ	送信される内容	実装で必要な性質
Prepare	Prepare(n)	best-effort broadcast（遅延・ロスト対応、再送必要）
Accept	Accept(n, v)	reliable broadcast（重複排除・再送・順序保持）
Decide	chosen の通知	total-order broadcast（Multi-Paxos では特に重要）

論文の「送る」の裏には、実装者が考慮すべき通信要件が大量に隠れています。

（3）永続化のタイミングも自前設計が必要

Acceptor は以下を永続化する必要があります：

• promised_n

• accepted_n

• accepted_value

しかし、論文は説明を省略しています：

• いつディスクに書くべきか？

• 書き込みの fsync はどのタイミングで必要か？

• クラッシュ後に何を読み戻すべきか？

• ログの破損や不整合をどう扱うか？

実際のシステムではここが性能・正しさの両方を左右するのに、Paxos は“抽象仕様”に留まり、方針を示しません。

---

（4）Multi-Paxos になると、さらに最適化が前提になる

標準 Paxos の理解だけでは Multi-Paxos は実装できません。

実際には：
- leader の安定化
- accept フェーズの最適化（1ラウンド化）
- バッチング・パイプライン化
- ログの GC

など、多数の実装技術が必要になります。

---

（5）結論：Paxos は正しいけれど、実装のガイドとしては不親切

まとめると：

• 論文の Paxos：安全性の抽象モデルとしては完璧

• 実装としての Paxos：現実システムの複雑性をほとんど吸収してくれない

つまり、Paxos は：

• 理論として正しい

• しかし理解しただけでは実装に繋がらない

• 現実の分散システムでは追加設計が大量に必要

という“構造的に難しい”アルゴリズムなのです。

4章：Raft ― “理解しやすさ”を最優先に設計された合意アルゴリズム

Paxos が「正しいが理解しづらい」という課題を抱えていたことを背景に、
それを“意図的に”改善する形で 2014 年に登場したのが Raft です。

Raft の最大の特徴は：

• 人間が理解しやすい構造

• 実装者が迷わないように丁寧に書かれた仕様

• 学習・実装の両面で扱いやすい設計

という点にあります。

この章では、まず Raft の設計思想を明確にし、続いて基本動作を紹介し、
最終的に Paxos と比べて何が「優しい」のか を整理していきます。

4.1 Raft の設計思想：「正しさ」より先に「理解しやすさ」

Raft の論文タイトルは In Search of an Understandable Consensus Algorithm（理解しやすい合意アルゴリズムを求めて）。
つまり 「理解しやすさ」そのものが最初から明確な設計目標 でした。

Raft が解決しようとした課題ははっきりしています：

• Paxos は理論的には正しいが、実装には深い知識が必要になる

• 実装者ごとに理解や解釈がブレる

• “eventual leader” など抽象度が高く実装指針になりにくい部分が多い

• 学習コスト・実装コストが高すぎる

Raft はこの状況に対して、「合意アルゴリズムを分解し、役割を整理し、名前を与える」というアプローチを取りました。
その結果、アルゴリズムの構造が視覚的・概念的に理解しやすくなり、実装者が迷うポイントを大幅に減らしています。

4.2 Raft は動作を3つの部分に分割する

Raft のもう一つの特徴は、 Paxos のように複数のフェーズが絡み合うのではなく、
合意プロトコル全体を 3 つの明確な部分に分割した ことです。

• Leader 選出（Leader Election）

• ログ複製（Log Replication）

• 安全性の維持（Safety）

Paxos では Prepare / Accept が様々な意味を兼ねており、役割やタイミングを頭の中で整理する必要がありました。
一方、Raft では「どの時点で何が起きるか」が構造的に分かれているため、図やタイムラインを追うだけで挙動を把握できるようになっています。

4.3 ノードの役割は3つだが、状態遷移が明瞭

Raft のノードは次の 3 つの役割のどれかに属します。

• Leader
  　クライアント操作を受け付け、ログ複製を主導する中心的役割。

• Follower
  　Leader の指示に従い、受け取ったログをローカルに反映する役。

• Candidate
  　Leader 選出中に一時的に移行する状態。

Paxos の Proposer / Acceptor / Learner と比べても、役割の意味が直感的で、役割間の責任範囲が明確です。

さらに Raft では、状態遷移図そのものが論文に明示されており、次のように非常にシンプルです：

Follower → Candidate → Leader  
Leader → Follower（タイムアウト / 選挙敗北）

この単純な「三段階の遷移モデル」が、Raft の理解しやすさを大きく支えています。

4.4 Raft の中核：Leader 選出

Raft はまず Leader を 1 人に収束させることを徹底的に重視しています。

これにより、Paxos で問題となる「複数の proposer が競合する」状況を避けます。

---

▼ Leader 選出の基本フロー

1. Follower がタイムアウトすると Candidate になる

2. Candidate が全ノードに RequestVote（投票依頼）を送る

3. 過半数の票を獲得すれば Leader に昇格

4. 選挙は “term（任期）” ごとに実施される

この term（任期） は Raft の整理原理の核となる概念で、
すべてのログ操作が term によって秩序付けられ、曖昧さが排除されます。

Paxos の “いつか誰かがリーダーぽくなる” という抽象性に比べ、
Raft は 「明確な手順・明確な条件・明確な状態」 の 3 拍子で設計されています。

---

4.5 ログ複製（AppendEntries）が Paxos よりずっと読みやすい理由

Leader が確定すると、合意の中心は AppendEntries RPC に移ります。

この仕組みが Raft の「分かりやすさ」を象徴しています。

Leader は次のように動きます：

1. 新しいログエントリを Follower 全員に送信

2. 過半数の Follower が永続化すれば “コミット” と判定

3. コミット結果を全員に通知して反映させる

---

Raft の大きなポイント：Leader が常に“正”のログを持つ

Paxos の場合：

• どの proposer の値が選ばれるかは動的に変わる

• Prepare / Accept のタイミングで勝者が変化

• 並行 proposer による競合が常に起こりうる

一方 Raft では：

• Leader が 1 人に決まる → 一本のログが明示される

• Follower はそのログに追従するだけ

• 競合は Leader の切り替え時に限定される

つまり Raft のログ複製は、

「Leader のタイムラインに全ノードが追従する」
というシンプルな構造になっています。

---

4.6 Raft の安全性は「ログの整合チェック」で担保される

Raft が特に評価された理由の一つが、ログの競合処理を“分かりやすく”定式化した点にあります。

Raft では、Leader と Follower のログ整合性を次のルールで保証します。

---

▼ ログ整合性の基本ルール（Leader Completeness & Log Matching）

• Leader は常に最新のログを持つように選出される

• Follower に古いログや不整合があれば、Leader が正しい内容で上書きする

• term と index の組で整合性を検証し、不一致があれば巻き戻す

---

この仕組みにより、Paxos だと複雑だった以下の問題が自然に解決されます：

• 過去 Leader が残した“不完全なログ”

• リーダー切り替え時の“書きかけの値”

• 遅延メッセージによる“古いログ”の紛れ込み

Raft の整合チェックは、ややこしいケースを単純なルールに押し込めることに成功しています。

4.7 Paxos と Raft の本質的な違い

ここまでを踏まえると、Raft が Paxos と比べて「理解しやすい」理由は次の 5 点に集約できます。

---

① まず Leader を安定させる

    → Proposer が競合しないので、動作が大幅に単純化される。

② 動作を「選挙・複製・安全性」に分割

    → フェーズごとに役割や責任が整理され、読みやすい。

③ term による時間軸の導入

    → Paxos の Prepare 番号より直感的に理解できる。

④ ログ複製が AppendEntries に一本化

    → 「Leader の流れに全体が従う」だけで説明できる。

⑤ ログ整合性のルールが明文化

    → Paxos のように状態遷移と時系列が複雑に絡まない。

---

要するに Raft は、“Paxos を実装しやすいように再構成した” と見なすのがもっとも正確です。

---

4.8 実装のしやすさも Raft の強み

Raft は論文として理解しやすいだけでなく、実際のプロダクト実装でも圧倒的に採用されているという強みがあります。
（例：Etcd、Consul、TiKV など）

Raft が好まれる理由：

• RPC が少ない（RequestVote / AppendEntries の 2 種類）

• Leader がいることでロジックが整理される

• メッセージ競合や乱れを深く考えなくてもよい

• 学習コストが低い

これらはすべて、「実装者にとって扱いやすい」という Raft の哲学そのものです。

---

4.9 まとめ：Raft は“実装者のために設計された”合意アルゴリズム

• Paxos：数理的に美しく正しい。しかし複雑で、実装難易度が高い。

• Raft：理解しやすさと実装しやすさを第一に設計された、現場寄りのアプローチ。

Raft を Paxos の“代替”と考えるよりも、

「Paxos の正しさを保ちながら、実用へ向けて整理した構造化バージョン」

と捉えると本質がつかみやすいでしょう。

第5章：Raft の核 ― ログ複製・RPC・安全性のすべて

Raft が「わかりやすい合意アルゴリズム」と評価される最大の理由は、アルゴリズムの中心に “ログ複製（Log Replication）” という、直感的で一本筋の通った概念を据えた点にあります。

Paxos では「値をどう選ぶか」「どの提案が生き残るか」が時系列の中で動的に決まっていきましたが、Raft では 合意の対象は常に「ログエントリ」 であり、

「Leader が書いたログを、全員が同じ順序でコピーする」

という非常にシンプルなモデルに帰着します。

この章では、Raft の“本体”とも言える以下の要素を、実装視点で順に見ていきます。

---

本章で扱う内容

• ログ構造
  Raft における合意対象は「値」ではなく「ログエントリ」である、という前提

• AppendEntries RPC
  Leader がログを複製し、同時に心拍（heartbeat）としても機能する中核 RPC

• コミットのルール
  「いつログが確定（commit）したと見なせるのか」という安全性の要

• Follower の整合性維持
  ログが食い違った場合に、どのように巻き戻し・修復されるか

• Snapshot とログ圧縮
  無限に増えるログをどう現実的に扱うか

• Paxos と Raft の構造比較（概念対応）
  ここまで学んだ内容を、Paxos の構造と対応づけて整理

ここを理解できれば、
Raft はもはや「論文の中のアルゴリズム」ではなく、

「自分で実装できそうな現実のプロトコル」

として見えてくるはずです。

次節ではまず、Raft のログがどのような構造を持ち、なぜ「ログこそが合意そのもの」なのかを確認していきます。

---

5.1 Raft が合意するのは「単発の値」ではなく「ログ」

Raft が扱う合意の対象は、Paxos のような “単発の値” ではありません。

Raft では、合意の単位は 時系列に沿って追加されていくログ（Log Entries） です。

このログは、分散システム全体で共有される「操作の履歴」であり、Raft の合意アルゴリズムは このログを全ノードで同じ形に揃えることを目的としています。

ログエントリの構造

Raft の各ログエントリは、最低限次の情報を持ちます。

• index
  ログ内での位置（1, 2, 3, … と単調に増える）

• term
  そのログが作成されたときの Leader の任期番号

• command
  状態機械（State Machine）に適用する操作
  （例：deposit +500、withdraw -700 など）

この構造は非常に重要です。
なぜなら、Raft の安全性はこの index と term の組によって支えられているからです。

---

Raft の根本思想

Raft の考え方は驚くほどシンプルです。

「同じ index には、常に同じ command が入るべき」

この条件さえ全ノードで守られれば、

• 各ノードが同じログを

• 同じ順序で

• 同じ状態機械に適用する

ことになり、結果として 全ノードが同じ状態に到達します。

これは、0章で紹介した State Machine Replication（SMR） を、
そのまま実装に落とし込んだ形だと考えると分かりやすいでしょう。

---

Paxos との対比（直感的な違い）

ここで、Paxos との違いを一度整理しておきます。

• Paxos
  「この 値 を合意できるか？」にフォーカスする

• Raft
  「この ログの位置 に、何を書くか？」を合意する

Raft では、
合意すべき対象・順序・適用方法がすべて ログという一本の軸に統合されています。

この設計が、
Raft を「理解しやすく」「実装しやすい」アルゴリズムにしている最大の理由です。

Raft の基本的な振る舞い（election → Leader 確定 → ログ複製）

---

5.2 AppendEntries RPC ― Raft の“心臓”となるメッセージ

Raft における通信の中心は、実は ほぼこれ一種類だけです。

AppendEntries RPC（Leader → Followers）

Raft のログ複製も、リーダーの生存確認も、
すべてこの RPC を通して行われます。

AppendEntries RPC の2つの役割

AppendEntries には、明確に分かれた2つの用途があります。

1. ログ複製（Log Replication）
   Leader が新しいログエントリを Followers に送信する

2. ハートビート（Heartbeat）
   エントリを送らなくても、定期的に送信して
   「Leader は生きている」ことを伝える
   （entries が空の場合）

この設計により、
Raft では 追加の heartbeat 専用メッセージが不要になっています。

AppendEntries RPC の内容

AppendEntries RPC には、次の情報が含まれます。

• term
  Leader の現在の任期番号

• prevLogIndex / prevLogTerm
  今から追加しようとしているログの「直前」のログ情報
  Followers とログの整合性を確認するための前提条件

• entries[]
  追加すべきログエントリ群
  （空の場合は heartbeat）

• leaderCommit
  Leader がすでに「コミット済み」と判断している最大の index

この中で、特に重要なのが
prevLogIndex / prevLogTerm です。

なぜ prevLogIndex / prevLogTerm が重要なのか

Raft では、Follower は次の条件を満たした場合にのみログを受け入れます。

「自分のログに、prevLogIndex の位置に prevLogTerm のログが存在する」

もしこの条件が満たされなければ、Follower は AppendEntries を 拒否します。

この単純なチェックによって、

• 古い Leader からの誤った書き込み

• 分断中に作られた不整合なログ

• 中途半端に書きかけだったログ

といった 厄介なケースが、自然に排除されます。

Paxos のように「どの値が最終的に選ばれるか」を状況ごとに考える必要はありません。

“わかりやすい安全性”の正体

Raft の安全性は、

• index（位置）

• term（時間軸）

という、人間が直感的に理解できる2つの軸で表現されています。

AppendEntries は、
この2軸が一致しているかを 毎回、明示的に確認するための仕組みです。

その結果、Raft は「なぜ安全なのか」を図と文章だけで追えるアルゴリズムになっています。

5.3 整合性の維持：Follower がログを巻き戻せるという発明

Raft が「実装しやすい」と言われる最大の理由の一つが、
この Follower によるログの巻き戻し という仕組みです。

Follower は、Leader から受信した AppendEntries RPC に対して、
まず次のチェックを行います。

prevLogIndex の位置にあるログの term が一致しているか？

 ログが食い違っていた場合の動作

もし、

• prevLogIndex にログが存在しない

• prevLogIndex にあるが term が違う

いずれかに該当した場合、Follower は次の行動を取ります。

その index 以降のログをすべて削除する

そして、Leader から送られてくる正しいログで上書きされるのを待ちます。

つまり Raft では、

• Leader が常に正しいログの「正本」

• Follower は Leader に揃う存在

という関係が、明確に定義されています。

---

なぜこれが画期的なのか

この仕組みが優れているのは、ログの不整合を「特別扱いしない」点にあります。

• ネットワーク分断中に書かれたログ

• 旧 Leader が書きかけだったログ

• 競合する Leader が存在した履歴

これらすべてが、

「term が合わなければ削る」

という一つのルールで処理されます。

Paxos のように
「どの proposer の値が選ばれたのか」
「どこまでが確定なのか」
を状態ごとに追跡する必要はありません。

---

実装者視点での圧倒的な分かりやすさ

実装の観点では、Raft の整合性維持は極めて単純です。

• ログは配列（またはベクタ）として持つ

• index と term を比較する

• 合わなければ truncate（後ろを切る）

• Leader から再送してもらう

この「巻き戻せる」という前提があるからこそ、Raft は複雑な競合ケースを 自然に吸収できる のです。

---

Paxos との決定的な違い

• Paxos：
  状態・時系列・選択された値が絡み合い、理解も実装も難しい

• Raft：
  「Leader が正」「Follower は合わせる」という一本のルール

この設計思想の差が、Raft を「実際に書ける合意アルゴリズム」にしています。

 

---

5.4 コミットのルール：なぜ Raft の安全性はわかりやすいのか

Raft において コミット（commit） とは、

そのログが 将来どんな状況でも消えないことが保証された状態

を意味します。

基本ルール：過半数への保存

Leader は次の条件を満たしたとき、ログをコミットできます。

そのログが、過半数のノードに保存されたことを確認できたとき

これは Paxos の「多数決による選択」と同じ考え方です。

Raft 特有の追加ルール

Raft には、Paxos には明示されていなかった 重要な制約 があります。

Leader は「自分の任期（term）で作られたログ」だけを、
過半数に反映されたことを確認した時点でコミットしてよい

逆に言うと：

• 過去の Leader が作ったログ

• 自分が引き継いだだけのログ

については、それ単体ではコミットしない のです。

なぜこの制約が必要なのか

このルールにより、Raft は次の性質を自然に満たします。

Leader Completeness Property

ある term でコミットされたログは、
それ以降に選ばれるすべての Leader に必ず含まれる

これによって：

• 古い Leader が書いたログが、
  新しい Leader のもとで「勝手に」コミットされることはない

• 新 Leader は、前任者がコミットしたログを必ず引き継ぐ

という、非常に分かりやすい安全性保証が得られます。

結果として何が単純になるか

Raft では、

• 「このログはコミット済みか？」

• 「このログは消えてよいのか？」

という判断が、

term と過半数の確認

だけで決まります。

Paxos のように、
「どの proposer がどのラウンドで選ばれたのか」
を追い続ける必要はありません。

Raft の安全性が“説明しやすい”理由

• コミット条件が明示的

• Leader の責任範囲がはっきりしている

• 過去と現在が term で切り分けられる

その結果、Raft の安全性は「図と時系列だけで説明できる」 ものになっています。

---

5.5 Snapshot：ログが増え続ける問題への実装的な解決策

Raft では、合意対象が「ログ」である以上、
そのまま実装すると ログが無限に増え続ける という現実的な問題に直面します。

• メモリの圧迫

• ディスク使用量の増大

• 新規ノード追加時の同期コスト増大

これは理論では無視できても、実運用では致命的です。

Raft の解決策：Snapshot

Raft はこの問題を 新しい合意概念を導入せず に解決します。

それが Snapshot（スナップショット） です。

Snapshot とは：

• ある index までのログをすべて状態機械に適用し

• その結果得られた 「状態そのもの」 を永続化すること

です。

一度 Snapshot を取ったら：

• その index 以前のログは 安全に削除可能

• 合意の正しさは一切失われません

なぜ安全なのか

Raft の基本原則は変わっていません：

「同じ index には同じ command が入る」

Snapshot は、

• その index までのログを
  　　　　すでに適用済みの事実として固定化する

だけです。

つまり Snapshot は「ログの短縮」であって、「合意の省略」ではありません。

InstallSnapshot RPC

Follower が遅れている場合や、必要なログがすでに削除されている場合、Leader は：

InstallSnapshot RPC

を使って Snapshot を直接送信します。

これにより：

• 長大なログを再送する必要がない

• 新規参加ノードや復旧ノードが即座に追いつける

という実装上の大きなメリットがあります。

Snapshot がもたらす実装上の利点

• 初期同期が高速

• ログの肥大化を防止

• GC やストレージ管理が容易

• アルゴリズムの構造はそのまま

Raft はここでも「理解しやすさを壊さずに、実用性を追加する」という設計思想を貫いています。

まとめ

Snapshot は：

• Raft の安全性モデルを一切壊さず

• 実運用で不可避な問題を解決する

• 実装者にとって自然な拡張

です。

Raft は「教科書用アルゴリズム」ではなく、最初から“動くシステム”として設計されていることが、ここでもはっきり分かります。

---

Paxos と Raft の構造的な違い：図で見ると圧倒的に理解しやすい

5.6 Paxos と Raft の構造的な違い

ここまでで、Paxos と Raft の両方を個別に見てきました。
この節では、ブログ内の図に対応する形で、両者の構造的な違いを整理します。

Paxos の特徴（図：Prepare / Accept が交差する構造）

Paxos の図を見ると、次の特徴がはっきり現れています。

• Prepare / Accept の2フェーズ

  • 合意は常にこの2段階で行われる

• 役割が分離

  • Proposer / Acceptor / Learner が独立

• 単発値の合意モデル

  • 1つの値ごとに Paxos を実行

  • 実用には Multi-Paxos による最適化が必須

• 番号（proposal number）管理が核心

  • 「既存の合意を壊さない」ための比較ルールが複雑

• 並行性と遅延が難易度を押し上げる

  • 複数 proposer

  • 古いメッセージの遅延到着

  • フェーズの割り込み

図を追うだけでも分かる通り、状態と時系列が絡み合い、直感的な流れを掴みにくい 構造になっています。

---

Raft の特徴（図：Leader を中心とした一本の流れ）

一方で Raft の図は、構造が驚くほど単純です。

• Leader を前提にログを一本化

  • クライアント操作は必ず Leader 経由

• Follower との整合性チェックは最小限

  • prevLogIndex / prevLogTerm だけで判断

• 過半数でシンプルにコミット

  • 条件を満たせば即コミット可能

• ログモデルが最初から統一

  • 単発値ではなく、時系列ログが基本

• Snapshot まで含めて一貫した設計

  • 実運用の要素が自然に組み込まれている

図を見た瞬間に、

「あ、これならコードが書けそうだ」

と感じられる点が、Raft の最大の強みです。

---

構造比較の要点

両者の本質的な保証は同じです。

• 過半数による合意

• 安全性（異なる値が同時に確定しない）

• クラッシュ故障モデル

しかし違うのは “人間が理解しやすいかどうか”。

観点	Paxos	Raft
合意単位	単発の値	ログエントリ
主導者	抽象的（eventual leader）	明示的（Leader）
時系列	番号で間接的	term で直感的
実装イメージ	浮かびにくい	最初から浮かぶ
実運用要素	後付け	最初から含む

---

まとめ

Paxos と Raft は、

数学的には同じ強さの保証

を持っています。

しかし Raft は、

実装者がつまずくポイントを徹底的に排除した

という点で決定的に異なります。

• 図を見ただけで流れが分かる

• 仕様を読めばコードが書ける

• 実運用まで見据えた設計

これが、
「なぜ今、Paxos より Raft が選ばれるのか」
という問いへの最も素直な答えです。

---

5.7 まとめ：Raft の本体は“ログ＋Leader＋AppendEntries”だけ

本章では Raft の実用面の中心を整理しました：
- Raft が扱う対象は 順序付きログ
- AppendEntries RPC が 複製・整合性・heartbeat を兼ねる
- Follower のログ巻き戻しで 常に Leader が正本となる
- 過半数の反映でコミット、term に基づくシンプルな安全性
- Snapshot によるログ圧縮

この構造が「理解しやすく」「実装しやすい」を両立しています。

第6章：まとめ ― 合意アルゴリズムを「理解した」と言える状態とは

Leader Election

Raft

• Leader が明示的に存在する

• term によって Leader が一意に決まる

• 合意の入口が常に Leader に集約される

Paxos

• 理論上は Leader 不要

• 実装では事実上 Leader（Proposer）が必要

• Eventual Leader Election という前提に依存する

---

合意対象

Raft

• Log Entry（index, term）

• 順序はアルゴリズムの前提

• 「ログを揃える」こと自体が合意

Paxos

• 単一の Value（n, v）

• 順序はアルゴリズムの外側で管理

• 1回の合意は 1つの値のみ

---

通信モデル

Raft

• RPC ベース

• RequestVote

• AppendEntries

• 通信の形が明確に定義されている

Paxos

• Broadcast 前提（論文）

• Prepare / Accept を BCast

• 通信の信頼性は未規定

---

Broadcast の責務

Raft

• AppendEntries は RPC

• 過半数 Ack によって Commit

• BCast の抽象は不要

Paxos

• Accept：reliable Broadcast が必要

• Decide：atomic Broadcast が必要

• フェーズごとに異なる保証を要求

---

実装者の責務

Raft

• RPC の再送制御

• ログ管理・スナップショット

• Leader 交代時の整合性維持

Paxos

• 信頼性のある Broadcast の実装

• Multi-Paxos への構成

• 状態とフェーズの厳密な管理

---

思想の違い

Raft

• 「理解できる形で正しい」

• 人間が追える構造を優先

• 実装可能性を重視

Paxos

• 「正しさを証明する」

• 抽象モデルを重視

• 理論的安全性を最優先

本稿では、分散合意という一見シンプルだが本質的に難しい問題について、Paxos と Raft という 2つの代表的アルゴリズムを通して見てきました。

ここでは最後に、

• 何が難しかったのか

• Paxos と Raft は何が違うのか

• 読者が「どこまで理解できたと言えるのか」

を整理して締めくくります。

---

6.1 分散合意の本当の難しさは「順序」と「時間」にある

最初に見た通り、分散環境では次の前提が成り立ちません：

• ノードは必ず生きている

• メッセージはすぐ届く

• 時間は共有されている

この世界では、

「同じ操作を、同じ順序で適用する」

というだけの要求が、驚くほど難しくなります。

Paxos も Raft も、この現実を真正面から受け入れた上で、「それでも 1つの順序に収束させる」ための仕組みです。

---

6.2 Paxos：正しさを極限まで突き詰めた抽象モデル

Paxos の最大の価値は、

• 非同期ネットワーク

• クラッシュ故障

• メッセージ遅延・重複

という現実的な前提のもとで、2つの異なる値が選ばれない（Safety）ことを、数学的に保証した点にあります。

一方で、

• Eventual Leader という曖昧な前提

• フェーズごとに異なる通信保証

• 状態と時系列が強く絡み合う構造

により、「理解できるが、実装は別問題」 というギャップが生まれました。

Paxos は、

理論としては完成しているが、実装ガイドとしては不親切

なアルゴリズムだと言えるでしょう。

---

6.3 Raft：Paxos の正しさを保ったまま、実装へ近づけた設計

Raft は Paxos の代替ではありません。

Raft が行ったのは、

• Leader を明示する

• 合意対象を「単発の値」から「ログ」にする

• 時間軸を term で整理する

• RPC を最小限に絞る

という 構造の再設計 です。

その結果、

• 動作が図で追える

• 実装の形が最初から想像できる

• 実際に動くシステムが書ける

という、「実装者のための合意アルゴリズム」になりました。

---

6.4 「理解した」と言えるラインはどこか？

本稿を通じて、読者が次の状態に到達していれば十分です。

• なぜ分散合意が難しいのか説明できる

• Paxos の基本ルールと難しさを説明できる

• Raft がどこを単純化したのか説明できる

• Leader・ログ・過半数が果たす役割を理解している

• 図を見て「今、何が起きているか」を追える

論文を暗記する必要はありません。

重要なのは、

「なぜこの形でないといけないのか」を説明できること

です。

---

6.5 次の一歩：実装・論文・現実のシステムへ

この先に進む道はいくつかあります。

• Raft の論文を読む（今回はかなり読みやすくなっているはず）

• etcd / Consul / TiKV の実装を覗く

• 簡易 Raft を自作してみる

• Multi-Paxos と Raft の対応関係を整理する

どれを選んでも、
「分散システムの見え方」が確実に変わる はずです。

---

6.6 おわりに

分散合意は「難しいからこそ」長く研究されてきました。

Paxos はその難しさを正面から証明し、
Raft はその難しさを人間が扱える形に落とし込みました。

両者を知ることで初めて、

なぜ分散システムはこう設計されているのか

が、腹落ちするようになります。

ここまで読み進めてくださった方は、
もう「分散合意は黒魔術」という段階を抜けています。

ぜひ、次は 動くコード の世界へ進んでみてください。