Paxos と Raft ― 分散合意を理解するために必要なこと
0章：イントロダクション — お金を動かす“合意” こんにちは。久しぶりの投稿になります。 アドベントカレンダーの時期は、ふだん記事化できていないテーマに取り組む良いきっかけになりますね。 今年のテーマは 「Raft と Paxos」 です。 分散システムにおける合意（Consensus）アルゴリズムといえばまず Paxos が挙がります。しかしその説明は、歴史的背景も構造も含めて、とにかく難解です。一方の Raft は、あえて「理解しやすさ」を設計思想に据えて作られたアルゴリズムです。 本記事では、この2つのアルゴリズムを “歴史の Paxos” と “実装の Raft” という対比の軸で読み解いていきます。 ただし、いきなりアルゴリズムそのものに飛び込んでしまうと唐突なので、まずは「そもそも分散システムに“合意”はなぜ必要なのか？」という直感的なところから話を始めていきます。 0.1 分散システムで銀行口座を扱うという仮想世界（改訂案） まずは、直感的に理解しやすい“仮想の銀行システム”で考えてみましょう。 これは実際の銀行の仕組みとは異なりますが、**「なぜ合意が必要か」**を説明するには最適な例えです。 一般的に銀行システムは RDB などを中心とした堅牢なアーキテクチャを持ちますが、ここでは一旦それを横に置き、次のような少し極端な世界を想定します。 RDB を中央集約せず、 各サーバが独立したコピーの残高データを持っている 3〜5 台のサーバに残高を複製し、どのサーバも同じ残高に到達する必要がある サーバは落ちたり復帰したりする ネットワークは遅延するし、順序も入れ替わり、メッセージがロスすることもある （補足） 実際の金融システムや生命に関わるシステムでは、この記事で説明する合意アルゴリズムよりもさらに高い保証が必要です。そのため、ここで紹介するメカニズムが“どこにでも”使われているわけではありません。ただし 「どうやって複数台の状態を揃えるのか」 を理解するうえでは十分役に立ちます。 この前提のもとで扱う世界は、常に 不確実 です。 だからこそ、すべてのサーバが同じ状態に到達するためには 「操作が同じ順序で実行されること」 が絶対条件になります。 “合意”とは、この順序を全サー...
