分散はなぜ難しいか

ここまでは 1 台のマシンの中の話だった。ここからは複数台で協調する世界に入る。まずコードを書かず、「なぜ分散は難しいのか」を押さえる。難しさは部分故障から来る。一部だけが壊れる・遅れる・連絡が取れなくなり、しかも落ちたのか遅いだけなのか区別できない。この曖昧さが split brain(指揮官が 2 人になる)を生む。次章の Raft は、この難しさに過半数という道具で答える。

なぜ1台では足りないか

これまで作ってきた DB もキャッシュも、1台のマシンの中で完結していた。1台には2つの限界がある。

壊れると全部止まる: ディスクが飛ぶ、電源が落ちる、プロセスが死ぬ。その瞬間サービスが止まる
1台の性能で頭打ち: CPU・メモリ・ディスク・帯域には上限がある。載せきれない負荷は載せきれない

答えは「複数台で持つ」。壊れても他の台が引き継げば止まらない(可用性)。負荷を分ければ1台の上限を超えられる(スケール)。ところが、複数台にした途端、1台では起きなかった難しさが噴き出す。

分散特有の難しさ: 部分故障

1台のプログラムでは、関数を呼べば「返る」か「(クラッシュして)全部止まる」かのどちらかだった。分散では第3の状態が生まれる。相手だけが落ちる。しかも自分からは、落ちたのか・ただ遅いのか・ネットワークが切れただけなのか、区別がつかない。

    A ──「これやって」──▶ B
    A ◀───  ？？？  ────  B

 A から見える「無音」の正体は3通り、しかも見分けられない:
   (1) B は死んだ            → 別の台に頼み直すべき
   (2) B は生きていて処理中   → 待つべき(二重に頼むと二重実行)
   (3) 返事だけが途中で消えた → B はやり終えている(頼み直すと二重実行)

部分故障。A が B に返事を待っている。B が死んだのか、B は生きていて処理中なのか、返事が途中で消えたのか。A には同じ『無音』にしか見えない。この曖昧さが分散の難しさの根っこ

1台の世界に「呼んだ相手が、生きてるか死んでるか分からない」という状況は無い。この部分故障(partial failure) こそが、分散システムを難しくしている当のもの。タイムアウトで見切りをつけるしかないが、タイムアウトは「遅いだけの相手」を「死んだ」と誤診する。

ネットワーク分断と split brain

部分故障が最悪の形で出るのがネットワーク分断(network partition)。ノード同士は生きているのに、ネットワークが真っ二つに割れて互いに連絡が取れなくなる状態。

このとき、素朴に「リーダー(指揮を執る1台)から連絡が来なくなったら新しいリーダーを立てる」と決めていると、両側がそれぞれ「相手が死んだ」と誤診して各自リーダーを立ててしまう。指揮官が2人になる。これが split brain。

        分断前(リーダーは1人)              分断後(誤ってリーダーが2人に)

         ┌───────────────┐              ┌ 島1 ┐   ✂   ┌───── 島2 ─────┐
         │  L   F   F   F │              │ L  F │       │ L'  F   F     │
         │  ↑指揮官は1人  │              │ 各自「相手が死んだ」と誤診  │
         └───────────────┘              └──────┘       └──────────────┘
                                         「x=1」を受付     「x=2」を受付
                                          ↓ 復旧すると x はどっち? 決められない

split brain。分断で連絡が切れ、両側が『相手が落ちた』と誤診して別々のリーダーを立てる。2人のリーダーが別々の書き込みを受け付けると、復旧したときにどちらが正か決められず、データが食い違う

split brain が怖いのは、両方のリーダーが別々の書き込みを受け付けてしまうこと。分断が復旧したとき「同じデータが2つの値を持つ」状態になり、どちらが正しいか決めようがない。銀行残高でこれが起きたら事故になる。

答えの骨格: 過半数(quorum)

split brain を防ぐ鍵が過半数(quorum)。「何かを決めてよいのは、全体の過半数が同意したときだけ」というルールにする。すると分断で割れても、過半数を含む島は高々1つしか存在できない(半分より多い集合は2つ作れない)。

   5台を分断:   ┌ 2台 ┐  ✂  ┌ 3台 ┐
                │ 過半数 3 に  │ 3 ≥ 3 → 過半数 ○
                │ 届かない ✕   │ ここだけが決定できる
                └──────┘      └──────┘

   「過半数の同意」を全ての決定の条件にすると:
     ・多数派(3台)  → リーダーを立てられる。書き込みを確定できる
     ・少数派(2台)  → リーダーになれない。書き込みは宙に浮いたまま確定しない
   ⇒ 決定できる島は常に1つ以下。split brain が起きない

過半数が2つ同時に存在することはない。5台を2:3に割ると、3台の側だけが過半数(3以上)を満たす。だから『過半数の同意がなければ何も決めない』とすれば、リーダーは分断されても1島にしか立てず、split brain が原理的に防げる

過半数の効き目は、2つの過半数が必ず1台以上を共有することにもある。「前にこれを決めた過半数」と「今これを決めようとする過半数」は必ず重なるので、その重なった1台が過去の決定を覚えていて、決定が消えない。これが次章 Raft の安全性の土台になる。

代償もある。過半数が必要ということは、半数以上が落ちる/分断されると、生きている少数派は何も決められず止まる。5台なら2台の故障までは耐えるが、3台落ちたら残り2台は動けない。可用性より一貫性(食い違わないこと)を優先する設計だ。

何に合意するのか: ログのレプリケーション

では複数台は具体的に「何に」合意するのか。答えは操作の並び(ログ)。

各ノードは同じ「コマンドの列」をまったく同じ順序で持ち、それを頭から順に適用する。同じ初期状態に同じ操作を同じ順で当てれば、結果は必ず同じ状態になる。これを状態機械レプリケーション(state machine replication) という。だから複数台の合意問題は、「全員が同じログを、同じ順序で持つ」ことに還元される。

  合意すべきもの = ログ(操作の並び)。全ノードで同一・同順:

     位置:   1        2        3        4
     ログ:  set x=1  set y=5  set x=9  del y     ← 全ノードでこの並びが一致

  各ノードは頭から適用 → どのノードも {x=9} という同じ状態に到達
  (db 編の WAL と同じ発想。あれを「1台のクラッシュ安全」から「複数台の冗長化」へ広げる)

状態機械レプリケーション。全ノードが同じ操作列(ログ)を同じ順序で保持し、順に適用する。ログさえ揃えば、各ノードの状態は勝手に一致する。Raft が合意するのは『ログの中身と順序』そのもの

これは db 編の WAL と地続き。WAL は「操作をログに追記し、順に適用すれば1台がクラッシュしても復旧できる」仕組みだった。分散合意はそれを複数台に広げ、ログ自体を全ノードで一致させる。次章の Raft はまさに「1本のログを、故障があっても全ノードで一致させ続ける」アルゴリズム。

この分野の道具は何に使われているか

分散合意は縁の下の力持ちで、名前の知られたシステムの土台に必ずいる。

etcd(Raft): Kubernetes の全状態(どのPodがどのNodeか等)を保存する台帳。k8s の心臓部
ZooKeeper(Zab という Raft 類似): Kafka の旧コントローラ選出、HBase 等の協調に長年使われた
Consul(Raft): サービスディスカバリと設定共有
CockroachDB / TiKV / YugabyteDB(Raft): 分散SQLのデータ範囲ごとの複製
Spanner(Paxos): Google の地理分散DB

いずれも「一部が落ちても、決めたことが食い違わない」を過半数で担保している。次章では、この中でいちばん読みやすい設計とされる Raft を、選挙からログ複製まで手を動かして作る。

設計の観点

見分けられないことを前提に置く: 落ちたのか、遅いのか、返事だけ失われたのか。区別できないなら、区別しなくても正しく動く形にするしかない
分断は防げないので、結果を縛る: ネットワークが割れること自体は止められない。止められるのは、割れた両側が別々に決めてしまうことのほうになる
決める対象を、状態でなく操作の並びにする: 状態を直接そろえようとすると差分の計算が要る。ログを一致させれば、状態は各自が同じ順に再生するだけで勝手にそろう
答えないことを選べるようにする: 少数側は止まる。間違った答えより、答えないほうがましだと決めたことが、この分野の設計の出発点になる
台数は奇数にする: 4台は3台と同じ耐性しかない。過半数の条件が変わらないまま、壊れうる部品だけが増える
合意を使わない選択も持つ: 常に応答するほうが大事な用途では、食い違いを許して後で寄せる設計を選ぶ。何を捨てるかを先に決めるのが、この分野の設計そのものになる

裏どり:

タイムアウトは検出ではなく諦め: 非同期のネットワークでは「遅い」と「落ちた」を原理的に区別できない。実用系がタイムアウトで打ち切るのは、故障を検出したからではなく、待つのをやめると決めたからになる
偶数台は損をする: 4台の過半数は3、3台の過半数は2。どちらも1台の故障までしか耐えられないのに、4台のほうが壊れうる部品が多い。実運用が3台か5台に落ち着くのはこのため
Kafka は外部依存を外した: 長らく ZooKeeper に協調を任せていたが、自前の Raft 実装(KRaft)へ移行した。合意の仕組みを外部に置くか、中に持つかという設計判断の実例になる
Paxos が難しいと言われる理由: 原論文が単一の値の合意を扱い、実用に必要な連続したログへの拡張を詳しく書いていない。Raft が最初からログを対象にしたのは、この隙間を埋めるためになる
同じ誤解が繰り返される: 「ネットワークは信頼できる」「遅延はゼロ」といった8つの誤解は1990年代に整理されたが、同じ前提を置いた事故は今も起きる。知識としては古いのに、実装では新しい

次は Raft で、ここまでの話を実際に動くコードにする。

参考資料

Fallacies of Distributed Computing — 「ネットワークは信頼できる」等の典型的な誤解8つ
In Search of an Understandable Consensus Algorithm (Raft) — Raft 原論文。冒頭に分散合意の動機がある
Designing Data-Intensive Applications, 8〜9章 — 部分故障・分断・合意の定番解説

分散はなぜ難しいか ​

なぜ1台では足りないか ​

分散特有の難しさ: 部分故障 ​

ネットワーク分断と split brain ​

答えの骨格: 過半数(quorum) ​

何に合意するのか: ログのレプリケーション ​

この分野の道具は何に使われているか ​

設計の観点 ​

参考資料 ​