Paxos, Raftなど分散合意プロトコルを概観する(1)
tl;dr
- 2PC
- 3PC
- Paxos
- Raft(次回)
- Proof of Work(次回)
- Proof of Stake(次回)
分散システムについては素人の筆者が書いたため誤りが多いと思うので、できれば確認のため元論文を参照してもらいたいです。
introduction
基本的な定理, 用語
- CAP定理: 分散システムは、一貫性 (Consistency)、可用性 (Availability)、分断耐性 (Partition-tolerance)のうち最大でもいずれか2つしか満たすことはできない。
- レプリケーション: 一貫性を保ちながら、リソース間で情報を共有すること。
- RPC: プログラムであるノードから別のノード上の関数を呼び出すこと。ここでは、ノードから別のノードにメッセージを送ることという理解でもたぶん大丈夫だと思う。
- 冪等性: ある操作を何度行っても結果が同一になることが保障されていること。
- トランザクション: 一連の情報処理の単位。例えば口座A=>口座Bに1万円を移すとき、「口座Aから1万円引く」と「口座Bへ1万円足す」という処理は不可分に実施されなければならない。
FLP impossible
非同期システムでは、メッセージの損失がなかろうと1プロセスでも停止しうる限り、100%合意できるプロトコルはない。
ただしこのステートメントには様々な留保がついているが、以上の不可能性が根底にある中で*1、分散システムの合意に関する諸問題について緩和的なプロトコルが与えられている。
なぜ分散合意が必要となるか
通例あるサーバーに負荷が増大した場合、サーバーじたいの性能を上げる（スケールアップ）ことはもちろんであるが、サーバー自体の台数を増やす（スケールアウト）ことで対応するパターンが考えられる。 そのときデータはサーバーを構成するノード間でデータがレプリケーションされる必要があるが、一般にその通信には時間がかかると想定されるためデータが更新されてレプリケーションをしている途中では、クライアントが呼ぶサーバーによって入っているデータが異なる可能性がある。その可能性を許容し、時間が立てばいつかはどのサーバーに問い合わせても同じになるだろうと期待するのが結果整合性(eventually consistency)である。
では、ここでそれより制約の厳しい問題について取り組むことにする。すなわち、どのタイミングでもサーバーが常に一貫した値を返すようになっている仕組みをどうやって提供するかである。これは例えば銀行口座などを想起すればわかりやすいが、銀行口座でお金を全額引き出すという命令をサーバーに投げたとき、その伝達が遅延しておりあるサーバーのノードではその命令が実行されていないときに、問い合わせクエリを投げるとあたかも預金がまだ入っているかのように偽装できてしまう。問い合わせクエリだけならよいが、再びお金を全額引き出すというクエリが罷り通ってしまえば、二重引き落としが可能になってしまう。そのため、何らかの防御策が必要となる。
抽象化すると、あるデータベースに書き込まれたデータAをBに書き換えるクエリを発行したとき、それをそのデータベースを構成する複数のノードでいかに正しく共有できるか、という問題となる。そこで、以下の思考実験を与える。
Two general's Problem
2人の将軍A,Bが都市をはさんで反対側に陣取っているとして、一斉攻撃を仕掛ければ都市は陥落するが、片方で攻めると各個撃破されてしまう状況を想定する。このとき将軍間で連絡を取り、一斉攻撃する時刻を定めておけばよいが、ここでその連絡は途絶する可能性があるとしよう。
このとき、合意に至ることは不可能であることが言える。なぜならば、「翌朝7時に攻撃する」という通信がA=>Bへ送られたとして、B=>Aに通信が戻らなかった場合、AはそれがA=>Bで途絶えたかB=>Aで途絶えたか分からないので、通信が正しく伝わっているかを知るすべはないからだ。*2
分散合意再考
したがってデータベースのデータAを全ノードで一気にBに書き換えようとしても、その間の通信が途絶する可能性がある限り、その安全性は担保されない。
実際にデータベースではマスター/スレーブ型のサーバー構成を取り、書き込みクエリはマスターが一括して対応し、読み取りクエリはスレーブがそれぞれ対応することで対処することは多い。書き込みより読み取りが十分に多く、水平分割/垂直分割によってマスターの負荷が1台のサーバーでさばける量であればうまく動くだろう。
ところがマスターで処理したクエリをスレーブにただ流すだけのような単純な例を想定すると、マスターが落ちた際に誰も対処できないし、通信が途絶する可能性もあるのでスレーブとの一貫性も保てない。実際にはもっと複雑な通信が行われてはいるのだが、データのconsistencyを保つためには、何らかのルール/プロトコルによってサーバーの各ノードの動きが制限されていなければならないということがいえる。 ここでは以下のように、必要となる制限の強さに応じてプロトコルを提示し、その動作の概略を説明したい。
各々のプロトコルの説明
2 Phase Commit
分散システムで、あるトランザクションがあるときに、それを全ノードがコミットするか、それとも全ノードがコミットしないかのどちらかの状態になることを保障するプロトコルである。 調整者（Coordinator）と呼ばれるノードと残りの参加者(Cohort)ノードに分かれて以下の2フェーズで行われるため、2PCと呼ばれる。
- コミット要求フェーズ: 調整者（Coordinator）が参加者にトランザクションを伝え、コミットの準備ができているかを問い合わせる。参加者はトランザクションが成功するならば成功、失敗すれば失敗を連絡する。
- コミットフェーズ: すべての参加者が成功した場合、コミットを実施するように通告し、失敗した参加者が少なくとも1つあった場合はロールバックを指示する。参加者は指示を実行し、完了応答を行う。
完了応答が調停者にすべて到達した時点で、トランザクションは終了したとみなされる。
この仕組みは少し考えればわかるが、通信路故障やノード故障に対して頑健でない。調整者はすべてのノードからの応答があって次のフェーズに移行することができるため、1つのノードから応答がこなかっただけでブロックされてしまい、以後何も進まなくなるからだ。これはまた調整者のFailにも頑健でない。そこで次にノンブロッキングな仕組みについて考える。
3 Phase Commit
ここでは時間制限を設け、タイムアウトによって時間切れを起こした場合、強制的に別のステップに移行するようにすることで、ブロックを防ぐような仕組みがとられている。
上の状態機械の図を参考にすると良い。
- CoordはCommit_Requestメッセージを全Cohortにわたし、wait状態となる。CohortはCommit_Requestが成立するならば、AgreedメッセージをCoordに返し、wait状態となる。CohortがCommit_Requestにトランザクションの不整合などで失敗したならば、AbortメッセージをCoordに返しabort状態となる。CoordはAbortメッセージを受け取るか、Agreedメッセージを全Cohortから受け取る前にタイムアウトした場合はAbortし、CohortにAbortメッセージを送る。
- CoordがAgreedメッセージを全Cohortから受け取った場合、Prepareメッセージを全Cohortに送る。待機していた全Cohortは、Abortメッセージを受け取ったならばAbortし、Prepairメッセージを受け取ったらAckメッセージをCoordに返す。
- CoordはすべてのCohortからAckメッセージを受け取ったら、CommitメッセージをすべてのCohortに送り、Cohortはコミットする。一方でCoordがCommitメッセージを送る前にFailしてしまっていたならば、Cohortはタイムアウトしてトランザクションをロールバックする。CoordがすべてのCohortからAckメッセージを受け取る前にタイムアウトしたら、トランザクションをAbortし、Abortメッセージを全Cohort送る。
3PCの3相は、コミットリクエスト、コミット準備、コミットの3段階でメッセージをやり取りすることに依っている。今回の場合、故障したノードが存在してもタイムアウトによって最終的にAbort段階にたどり着くため終了することは保障されている。果たしてこれで分散合意は十分なのだろうか？
いや、決してそうではない。3PCではノードのクラッシュを許容するFail-Stop障害モデルに対応できることを示した。では仮にクラッシュしたノードが何食わぬ顔をして復帰してしまうような、Fail-Recover障害モデルではどうか？ そしてそれは現実のコンピューターでは極めてよくある現象である。なぜならば非同期通信において遅延した通信路によって、あたかも死んでいるかのように見えるノードがあったとして、それが突然速度を取り戻すこともあるし、ノードが単に再起動する可能性だってある。そのとき、3PCでは生き返ったノードを他のノードと同期させることができないのだ。
問題は他にもある。Coordinatorが落ち、別のノードがCoordinatorを代行したとしよう。その後再びCoordinatorが復活したとして、どちらもCoordinatorとしての職務を全うしようとしてしまうとき、Cohortにとってそれは不幸以外の何物でもない！
結局、単なるタイムアウトをとっただけでは、そのノードが死んでいるかそうでないかを判断することは不可能である。仮にFailから復活したノードがあったとして、そのノードにも適切に現状を伝え、そして役割を割り振ることのできるプロトコルが必要不可欠である。それが、以下で説明するPaxos、及び次回説明するRaftである。
Paxos
さてここで仮に多数決で物事を決めるとすると、過半数の参加者が正しい情報を持っていればよいと考えられる。この基本的な考えを敷衍して、メッセージは届かなかったり遅延はあってもよいが壊れないことを前提に置いた、非同期ネットワークのFail-Recover障害に対して回復力を持つプロトコルがPaxosである。
その中で全ての提案に順序番号を定め(Serialize)、どのプロセスにも同様の順序で到達することを約束している。これによってログのレプリケーションや命令の実行順序をシーケンシャルに定めることができる。ただし必ずしもその命令の発行された時間的順序とは一致しないが、このアルゴリズムは複数の提案を受理した際に単一の結果を得ることを保障する。 それぞれプロセスにはProposer, Acceptor, Learnerという役割を与えられており、2回のmessageのやり取りで合意を得る。
カジュアルなそれぞれのプロセスの役割は以下である。
- Proposer: 次に来る提案をAcceptorに問い合わせ(propose)、過半数の承認を得た場合にCommitメッセージを及び提案の承認とともに戻ってきた提案値のうち最大のものをAcceptorに伝える。
- Acceptor: Proposerの提案が自分の持っているログの中にある最大値の提案より小さければ提案を承認する(premise)。承認する場合は、ログ内の最大の提案値と共に返す。
- Commitメッセージと共に受け取った提案値が、さきAcceptした提案値と一致すれば、そのCommitを承認する。
- Learner: Accpetorの過半数Commitした提案を記憶する。
"Paxos made simple"によれば、ProposerとAcceptorが1つずつの場合、Acceptorが複数の場合、Proposerが複数の場合、というように増やしていくことが各プロセスのルールを理解する助けになるという。
http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf
この場合であっても発生しうる障害は、Proposerが複数存在した場合に一方のProposerによる提案のProposeとCommitの間に他方のProposeが入ることで、Commitが棄却されてしまうことだ。これによってこのアルゴリズムは停止保証がないが、安全性は保障されている。 これを防ぐにはProposerのLeaderを定める必要がある。Paxosでは乱数を使うなりタイムアウトを使うなりすればよいと書いてあるだけで、リーダー選出の問題はRaftにより詳しく書かれている。またLearnerは複数ある場合、Acceptorとの多対多通信が発生するので、AcceptorとLearnerを媒介するLeader的な(Distributed) Learnerがあると望ましい*3。このLeader Proposer, Learnerを1つのマスターとする実装は1つ考えられる。
Paxos made live
一方でGoogleの実装は"Paxos made live"という論文にあるが、そこで平等なノード間で単一のCoordinator=Proposerを選出し、残りのノードがAcceptorsになるようにしている。さきの説明ではProposer=>Acceptor=>Learnerがシーケンシャルにつながっているように記述したが、この実装ではその役割は可変的である。この仕組みを基礎としているjavascriptでの実装が以下にあり、わかりやすい。
Neat Algorithms - Paxos - Will You Harry Me
またこの論文ではMulti-paxosやmaster leasesといった仕組みを新たに導入している。
Multi-Paxosでは一旦選出されたProposer(=Coordinatior)をある程度の期間変えないことで、2回目以降のpropose/promiseの手続きをしなくてもすむため、処理速度の向上が図れる。*4 Multi-PaxosでのCoordinatorはMaster相当のもので、master leasesとよばれる仕組みは、そのMasterが定期的に単調増加なsequence numberを更新していくことで、古いマスターが一時的に切れて新しいマスターが誕生し、その後古いマスターが戻ってきたときにsequence numberが小さい方を無視することで競合を防いでいる。*5
次回に続く。Referenceについても最後にまとめて記す。
