2015年5月15日金曜日

Paxos の解説の解説(その 1)

Google の distributed 系の論文を読んでるとほぼ必ずでてくる Paxos。複数のプロセス間で合意を取るためのプロトコル (consensus protocol) で、リーダー選出などに使われる。
元論文はこちらだが、これが一般人には分かり難かったらしく、同じ著者 Leslie Lamport が解説を書いているので、こっちを読んでみた。

まず基本的な概念から。なお以下で、「値 x が選択される」とは「値 x で合意が取れる」と同じ意味である。
3 種類のエージェントを考える。proposer は値を提案する人。acceptor は提案された値を受理する(もしくは受理しない)人。learner は選択された値を受け取る人である。(実際には一つのインスタンスが複数のエージェントとして振舞うことがある)
ただし、learner については難しいことはないので、特に説明しない。複数の proposer が提案する値の中から、どうやって一つの値 x で合意するか、というのが目的となる。

シンプルだが正しく動かない例を挙げてみる。
2 つの acceptor a1, a2 が存在し、それぞれ最初に受け取った値を accept する(= 選択する = 合意する)ものとする。2 つの proposer p1, p2 が、同時点でそれぞれ値 v1, v2 を提案したが、p1 -> a2 と p2 -> a1 の通信が失敗したとする。すると、a1 は v1 を、a2 は v2 を「選択」してしまい、合意が取れないことになる。これは明らかに良くない。

consensus protocol が満たすべき要求は以下の 3 つだ。

  1. 選択された値は、必ず提案された値である。
    === 誰も提案していない値が選択されることはない。
  2. 選択される値は一つである。
    === みんなが同じ値に合意する。
    === 複数の値が選択されることはない。
  3. 値 x が選択されたときに限って、「値 x が選択された」という情報を受け取る
    === 偽の情報を受け取ることはない。
上記のシンプルな例は 2 を満たしていない。

答えを先に書くと、正しいプロトコルは以下の通りである。まず前提として、

  • "prepare" request と "accept" request との 2 種類がある。全てのリクエストは、提案・合意される「値」とは別に "proposal number" と呼ばれる整数を持っている。
  • proposer は整数カウンタを 持つ。これは proposal number を生成するために使われる。
  • acceptor はいかの 2 つの値を記憶している。
    • これまでに受け取った "prepare" request のうち最大の proposal number。これを Mp と呼ぶ。
    • これまでに受理した「値」とその proposal number。これを Pa と呼ぶ。ただし、まだ何も受理していない場合は Pa = null となる。
このプロトコルは 2 つのフェーズから成る。

Phase 1: prepare phase
  • proposer は proposal number N の "prepare" request を(少なくとも)過半数の acceptor に送る。
  • acceptor は、N <= Mp であれば、この "prepare" request を無視する。N > Mp の場合は、Pa をレスポンスとして送り返す。
Phase 2: accept phase
  • proposer は、"prepare" request に対するレスポンスを過半数の acceptor から受け取った場合は、proposal number N と提案する値 V の "accept" request をその acceptor に送る。V は以下の条件で決まる。(なおレスポンスが過半数に満たない場合は、この「提案」は失敗なので、カウンタを increment して Phase 1 からやり直す。)
    • 一つ以上の acceptor が Pa != null を返した場合は、複数の Pa のうち、最大の proposal number を持つ Pa の値とする。
    • 全ての acceptor が Pa == null を返した場合は、proposer は任意の値を V とする。
  • acceptor は、proposal number N の "accept" request を受け取ったら、N >=(現時点での)Mp なら、値 V を受理する。N < Mp なら無視する。

このようにプロトコル自体はとてもシンプルである。問題は「このプロトコルでなぜ正しく合意が取れるのか」であり、この解説もそこにページ数を割いている。「正しさ」については次のエントリで書きたい。


0 件のコメント:

コメントを投稿