ざっくり理解するPaxos

ゴールデンウィーク中、Appleがオープンソースとしてリリースした分散データベース FoundationDB のドキュメントを読んでいました。なかなか面白いデータベースだと思うのでこれについては別途書きたいですが、それはそれとしてFoundationDBでは、分散環境下でACIDトランザクションを実現するために、分散合意プロトコルとして有名なPaxosを採用しているようでした。

PaxosはGoogleのChubbyやCassandraのLight Weight Transactionなどで使われていますが、僕はいまだにPaxosがどのように動作するのかあまりよく分かっていませんでした。良い機会だと思い、FoundationDBの技術を理解するためにも連休の後半でLeslie LamportによるPaxosの論文の一つ Paxos Made Simple を読み、何となくわかった気持ちになったので備忘録としてここに書き残しておきます。（間違いがあったらマサカリ頂きたいです）

Paxosが達成したいこと

Paxos を使って達成できるのは、簡単にいうと以下のようなセマンティックです。

• ネットワーク上の複数ノードが、「提案」された値の中からひとつの値だけを 「選択」したい。
• 一度値が「選択」されたら、その値はあとから未選択状態に戻ったり、値が変わったりしない。
• 多少の参加ノードが途中で故障したり復帰したりしても、残ったメンバーで破綻なくプロトコルが続行され、選択に至ることができる。

一度選択された決定が、後からなかったことにされたり、ひっくり返されたりしない、というのは日常生活からも有用性さが納得できる話です。ここでは、例として「今日のお昼ご飯」を決定する例に挙げます。ここでは複数のメンバーが「ラーメン」「カレー」「ピザ」などの値を「提案」し、そのなかからひとつのメニューを「選択」し、そのメニューのお店にメンバー全員で一緒にご飯を食べに行きたいとします。（例題設定は @nobu_k さんのスライドからお借りしました）

メンバーからの提案を受けてメニューを決定するリーダーが一人だけいれば、「ラーメンにしよう」などとすぐに「選択」できて話は簡単です。しかし、このワンマンリーダーはプロジェクトの単一障害点なので、プロトコル中に突然の交通事故で病院に搬送されてしまうと、残されたメンバーは昼飯のメニューを選択できなくなります。そのような場合、他のメンバーをリーダーに昇格させ、新リーダーに「カレーにしよう」などと選択してもらうことができます。しかし、旧リーダーの傷が浅く、すぐに病院から戻ってきて、「ピザにしよう」などと選択を続行する可能性があります（Crash-Recovery故障モデル）。これは一度決まった決定がひっくり返り、値が一つより多く選択されてしまった状態と言えます。こうなると、メンバーのうち一部は新リーダーとカレーを食べに、一部は旧リーダーとピザを食べに行ってしまうなどの分裂状態に陥る可能性があり、全員で一緒にご飯を食べるという目的は達成されません（Split-Brain障害）。

Crash-RecoveryによるSplit-Brainを避ける手法として一般的なのは、リーダーに心拍計を取り付け、確実にリーダーが死亡してから新リーダーを昇格させるというものです。しかし、この死亡確認までの所要時間は、長すぎるとメンバーはいつまでも昼飯に出発できない（可用性の低下）し、かといって短すぎるとやはりSplit-Brainを起こします。（SRE本では他にもSTONITH(Shoot The Other Node in the Head = リーダーの頭を撃ち抜く)コマンドというより積極的な手法も紹介されていますが、こちらもネットワーク障害などでリーダーの機能を確実に停止できない可能性あり完全ではありません）

このように、従来一般的な単一の「マスター」ノードに値の「選択」をさせるアーキテクチャは、Crash-Recovery故障モデルでの耐障害性がありません。そこで、単一のリーダーノードによる独裁的な決定ではなく、分散された複数のノードによる「合意」に基づいた選択をすることによって、ノードが多少故障したりNWが一時的に分断しても値を選択し続けられるような耐障害性を獲得したいという動機があり、そのための分散合意アルゴリズムのひとつがPaxosです。

…というのが前提についての自分のおおざっぱな理解です。

Paxos

ここからPaxosの解説を始めます。

Paxos では、参加ノードを、値を提案する Proposer, 提案を受け入れる Acceptor, 提案の合意状態を観測して「選択」を判定する Learner の3種類のロールに分けます(Fig.1)。それぞれ何台いても良いし、同じサーバーが複数のロールを兼務してもよいです。 Proposerにより提案された値が過半数のAcceptorに受理(accept)されたとき、Learnerはその値を「選択」することができます（そのため、Acceptorノードは3つや5つなど、奇数が好ましい）。そのため、Paxosは、Acceptorの過半数が生き残っている限り、合意に至るプロトコルのどの段階でProposerが全滅したり復活したりしても破綻しません。

Fig.1:

通常、Acceptorが値をAcceptするとLearnerに通知されるのでLearnerは素早く合意を検知できますが、パケットロスなどのため、Learnerが常に形成された合意を知りえるとは限らないので、そういう場合はLearnerからAcceptorにaccept状況を確認しにいく必要があります。

Paxosプロトコル

さて、この各々のAcceptorノードに、どのようなプロトコルで値をAcceptさせるかが肝心な点です。ナイーヴなプロトコルではPaxosが求める正しさや耐障害性は得られません。たとえば、単純な「各Acceptorは最初に自分に提案された値をAcceptする」プロトコルでは、同時に3つ以上の提案がなされたり(Fig.2)、合意形成前にAcceptorがFailしたりすると(Fig.3)、いずれの提案も過半数を獲得できずにプロトコルが終了しません。反対に、「最後に提案された値をAcceptする」プロトコルの場合は、いちど値が選択されたあとも、選択値が変化してしまい、目的を達成できません。

Fig.2 単純なFirst-Write-Winでは3つ以上のproposeで誰も過半数を握れなくなる

Fig.3 単純なFirst-Write-Winではacceptorのfailで誰も過半数を握れなくなる

Paxos では、Proposerが提案するそれぞれの提案に各提案にユニークな番号（便宜上、ここでは提案番号と呼ぶ）を付与し、フェーズ1 (prepare) / フェーズ2 (accept) のふたつのフェーズからなるプロトコルで提案をやりとりします。提案番号は、提案どうしで重複してはいけないので、時刻とノードIDの組み合わせなどで生成します。

フェーズ1: Prepare / Promise

Paxosのフェーズ1は、Proposerが値を提案するところから始まります。フェーズ1のルールは以下の通りです。

• Phase 1. (a): Proposerは過半数のAcceptorに、生成した提案番号nとともにprepare(n)要求を送信する。
• Phase 1. (b): Acceptorが既に応答したどのprepare要求の提案番号よりも大きな提案番号nとともにprepare要求を受信したら、nより小さな番号の提案は今後acceptしないという約束(promise)と、もしあれば現在までにacceptした最大の番号の提案とともに要求に応答する。そうでなければ、Acceptorはこのprepare要求を無視する。
  • 無視とあるが、これはタイムアウトと無視エラーレスポンスを同一視してよく、レスポンスを返さなくてもプロトコルは破綻しないという意味で、パフォーマンス最適化のために即時に無視レスポンスを返してもよい。

Proposerが過半数のAcceptorからpromiseレスポンスを受け取れたらフェーズ2に進みます。できなければ、もっと大きな提案番号を用いて最初からやり直します。少し複雑なので、以下に図解します。(Fig.4, Fig.5, Fig.6)

Prepare要求した提案番号がAcceptorの最大のpromise済み提案番号よりも大きかった場合

この場合、AcceptorはProposerにpromise応答を返します(Fig.4)。Acceptorがすでに何らかの提案をacceptしていた場合、その最大の提案をpromise応答に付与します(Fig.5)。

Fig.4 Fig.5

Prepare要求した提案番号がAcceptorの最大のpromise済み提案番号よりも小さかった場合

AcceptorはPrepare要求を無視します。(Fig.6)

Fig.6

フェーズ2: Accept

• Phase 2(a): proposerがprepare(n)要求に過半数のacceptorからレスポンスを受信したら、それらのAcceptorに、提案番号n、値Vのaccept要求を送信する。Vはレスポンスされた中で最大番号の提案の値か、もし何の提案も受け取っていなければ任意の値。
• Phase 2 (b): accept(n,V)要求を受け取ったAcceptorは、もしnが今までpromiseした最大の提案番号よりも大きければ、その提案をacceptする。そうでなければ無視する。
  • Phase 1 (b) と同様、無視ではなくIgnoreレスポンスを返すことで素早くリトライできる。

過半数のAcceptorが同じ値をacceptすると、合意が成立したとみなされ、Learnerはその値を「選択」することができます。Phase 2(a) での値Vの選択がやや複雑ですが、ここがPaxosのキモです。

accept要求の提案番号が、Acceptorがpromiseした最大の提案番号以上だった場合

問題なくacceptされる。

Fig.7

accept要求の提案番号が、Acceptorがpromiseした最大の提案番号より小さかった場合

accept要求は無視される。

Fig.8

Paxosプロトコル例

Paxos Made Smple で定義されているプロトコルはこれだけです。本当にこれだけのプロトコルで、「値がただ一つだけ選択される」が実現できるのか、実際に試してみよう。ここではProposer2ノード、Acceptor5ノード、Learner1ノードの集合を想定します。本当はラーメン・カレー・ピザの例を続けたかったですが、作図上の都合により、値V1,V2,V3と記して説明します。

一番かんたんなパターン

まずはすんなり選択に至るパターンを試してみましょう。Proposer P1が提案番号n1, 値V1 の提案(n1,V1)を提案したいとします。

フェーズ1

Fig.9: P1が過半数のAcceptor（ここではA1,A2,A3の3ノード）に提案番号n1をprepare要求する。全てのAcceptorがn1をpromiseしてくれたのでフェーズ2に進む。

フェーズ2

Fig.10: P1がpromise応答したAcceptorにaccept(n1,V1)要求をする。いずれのAcceptorもこれをacceptする。

過半数のAcceptorが同一の値をacceptしたので、Learner L1は値V1を「選択」できるようになりました。よかったですね。

選択後に他の値が提案されるパターン

ところで、Paxosの合意においては、いちど値が選択されたら、それ以外の値が選択されてはいけません。たとえば、この状態からProposer P2が、大きな提案番号n2で値V2を提案した場合、はたして値V2が選択されずにいられるでしょうか。ためしてみましょう。（n1より小さな提案番号を使った場合については、フェーズ1を満たせず棄却されることが自明なので省略する）

フェーズ1

Fig.11: P2が過半数のAcceptor A3,A4,A5に提案番号n2をprepare要求する。全てのAcceptorはpromise応答するが、(n1,V1)提案をaccept済みのA3はこの提案(n1,V1)をpromise応答に付与する。

提案(n1,V1)はすでに過半数のAcceptorによりacceptされているので、このとき、P2がどの過半数のノードの組み合わせにprepare要求しようとも、少なくともひとつのノードからは提案(n1,V1)つきのpromiseが応答されることになります。

フェーズ2

Fig.12: ルールPhase2(a)により、P2は、元々の提案(n2, V2)を、acceptorから受け取った値V1で書き換えた提案(n2,V1)をノードA3,A4,A5にaccept要求する。このaccept要求は、すべてacceptされるが、結局すでに選択済みの値と同じ値がacceptされるに過ぎず、Learnerが選択する値はV1のまま変わらない。

このように、各ProposerがPaxosプロトコルを守る限りにおいて、いちど過半数にAcceptされた値（V1）はくつがえされることはありません。

これで、Paxosがどういう挙動をするものなのかなんとなくイメージできたと思います。

衝突するパターン

もう少し複雑な、同時に提案が走ったり、途中でProposerが落ちたりするパターンを試してみましょう。

P1がA1,A2,A3に(n1,V1)をprepare要求します。

P2がA3,A4,A5に(n2,V2)をprepare要求します。

P1がA1,A2,A3に(n1,V1)をaccept要求しますが、A3が受理しなかったのでやり直しになります。

P2がA4,A5に(n2,V2)をaccept要求しますが、A3に要求する前にプロセスが停止し、離脱してしまったとします。

そこに新たなP3が登場し、(n3,V3)を提案しようと、A2,A3,A4にprepare要求します。すでにP1,P2による提案をacceptしているノードからは、それらの提案がpromise応答されます。

P3は、提案(n3,V3)の値をpromise応答中最大の値に書き換えた提案(n3,V2)をA2,A3,A4にaccept要求(n3,V2)します。これで過半数のノードが同じ値V2をacceptしたので、選択値はV2に確定します。よかったですね。

ざっくりと雰囲気でいうと、Paxosは

• Acceptorは、promiseした番号以上の提案番号だけをacceptする
• Proposerは、Acceptorがacceptしている最大番号の提案で自分の提案を上書きする

のルールの組み合わせによって、後から提案するProposerほど、すでに場に出ている提案を追認せざるを得ない仕組みで選択値の変動を防いでいるようです。

Multi-Paxosと複製ステートマシン

ここまでで、Paxosがいかにお昼ご飯を選択するのに便利なプロトコルか理解してもらえたと思いますが、実際のところ、Paxosそのものでは大したものは作れません。Paxosのうまみは、単一の値についての合意というよりも、これを順序つきのコマンド列についての合意に拡張し、複製ステートマシン（RSM）の保持に応用できる点にあります。（Paxos Made Simpleの最後の章はこの複製ステートマシンの実装についての記述になっています。この論文にはMulti-Paxosという名前は一度も出てきませんが、他の論文や資料ではこの手法をMulti-Paxosと呼んでいるので、たぶんこれがMulti Paxosなんだと思います）

ステートマシンとは、ある状態にコマンドを入力して出力と新しい状態を生成する概念上の機械です。例えば、銀行システムは口座の全ての集合を一つのステートマシンと考えることできて、預金の引き出しは、口座に引き出し金額以上の預金がある場合に引き出し金額を出力し、金額を差し引いた新しい状態に遷移するコマンドと表現できます。複製ステートマシンでは、初期状態から全く同じ操作を、同じ順番で適用することで、複数のレプリカの状態を同一に保つことができます。RDBのbin-logみたいですね。

こういったシステムでは、一般的に単一のマスターサーバー（マスターDB）が全ての更新順序を決定する役割を担いますが、冒頭で議論したように、単一マスターのシステムは可用性とSplit-Brainの問題に悩まされることになるので、やはり分散合意による高い耐障害性を獲得したいわけです。そのためにMulti-Paxosを使います。

Multi-Paxos の仕組み

Multi-Paxosは、「連続したコマンド入力を受け取り、コマンドが同じ順序で適用されるように合意していく」ことで複製ステートマシンを構築します。複製ステートマシンは、順番つけられた、個別のPaxosインスタンスの列を持ちます。i番目のPaxosインスタンスで選択された値は、i番目のステートマシンコマンドになります。クライアントがProposerにコマンドを要求すると、そのProposerはそのコマンドが何番目に実行されるべきコマンドかを決定し、その番号の値についてAcceptorに提案を行います。

ところで、Paxosである値を選択するには、Prepare/Acceptの2フェーズが必要で、アクセプターが5台の場合は最低6ラウンドトリップ、さらに他の提案と衝突した場合はリトライのため追加のラウンドトリップが必要です。これではステートマシンとして使うにはあまりにスループットが低いです。

そこで、Multi-Paxosでは特定のProposerをLeader Proposerに選出し、そのノードにコマンド順序の決定を行わせる最適化を行います。さらにPaxosプロトコルを拡張し、Proposerは「n番目以降の全てのPaxosインスタンスに対して、同じ提案番号でAcceptorにPrepare要求」ができるようになります。これらの拡張により、リーダープロポーザは、リーダー選出直後などのレアなイベント時をのぞいてフェーズ1を省略でき、さらに提案同士の衝突による性能低下も回避できます。　

リーダーを選出と聞いて、Sprit-Brainが起きないか心配してしまうかもしれませんが、あくまで性能最適化のためのリーダーに過ぎず、もしリーダー以外のノードがコマンドを提案したとしても（性能は低下しますが）、個々のPaxosにより正しさは守られているので、選択値が壊れたりはしません。

Multi-Paxos リーダー交代時の挙動

リーダープロポーザの故障などで他のプロポーザにリーダーシップを切り替える場合を考えてましょう。まず、新任リーダーは、コマンドを受け入れる仕事を始める前に、決定済みの全てのコマンドの決定を知る必要があります。Multi-Paxosでは基本的にProposerはLearnerも兼ねるので、リーダーを任された時点でほとんどの選択はLearnしているはずですが、単一Paxosの項で少し触れたように、Acceptor側の全ての合意が即座に全てのLearnerに通知されるわけではないので、認識に欠けがある可能性があります。

では、この新Leader Proposerがどうやって完全な決定を知るかというと、旧リーダーのものより大きな提案番号で「n番目以降の全てのPaxosインスタンスに同じ番号でPromise要求」コマンドを使います。このコマンドを受けたAcceptorは、promiseとともに「n番目以降の全てのAccept値」をレスポンスするので、これで新Leader Proposerは全ての未認知コマンドの選択値を入手できます。ちなみに、この方法でも選択値が確定できなかった虫食いコマンドのインデックスに対しては、なんと「No-opコマンドを提案」してスキップします。歴史改変じゃないかと心配になりますが、上記プロトコルで選択値が得られなかったインデックスのコマンドは、過去においても一度も選択されていなかったコマンドという保証があるので大丈夫ということのようです（つまり、プロトコルが正しく動いている限り虫食いは現れないはず）。

Multi-Paxos その他

そのほか、Multi-Paxosについてはメンバーシップ変更時は、メンバーシップの変更そのものをひとつのコマンドとして記録すればいいよとか、Leader Proposerは、提案が成功すれば、Learnを待たずに次の提案に移って良いけど、未Learnのコマンドの個数はα個までに制限すると良いとか、細かい議論がいくつかあります。

PaxosとRaft

ここまでPaxosとMulti-Paxosの動作を見てきました。しかし、Paxosは現在は以前ほど流行っていないようです。機能と性能がほぼ同じだがシンプルで理解しやすいとする新しい分散合意アルゴリズムのRaftが2013年に発表されました。また、Paxos Made Liveでは、Paxosは現実の分散システムに実装するためには論文に書かれていないことが多く、最終的なプロダクトは「未証明のプロトコル」になってしまうと指摘されています。実際、定評のあるオープンソース製品でPaxosを実装したものはあまり聞きません。それこそCassandraのLWTやFoundationDBくらいでしょうか。

一方、Raftは（まだ読んでいないのですが）、リーダーエレクションなど、実装に必要な詳細が論文化されているため多様なオープンソース実装が存在し、特にGo言語向けの github.com/coreos/etcd/raft は、etcdだけではなくCockroachDB、TiDBにも採用されるなど、新時代の分散DBの興隆を支えている感があります。そういうわけで、次はRaftを勉強したいと思います。

Raft Consensus Algorithm

参考文献

• Paxos Made Simple
• Paxos
• 今度こそ絶対あなたに理解させるPaxos - Qiita
• Henry Robinsonによる優しいPaxosの解説 - minghaiの日記

SRE サイトリライアビリティエンジニアリング ―Googleの信頼性を支えるエンジニアリングチーム

Googleを支える技術 ?巨大システムの内側の世界 (WEB+DB PRESSプラスシリーズ)