Paxos made simple (PDF)
Leslie Lamport
01 Nov 2001
簡単にしたPaxos
レスリー・ランポート
2001年11月1日
注：誤訳、誤字、その他ご指摘歓迎。翻訳者は誤訳に関して一切の責任を取りません:-)
Abstract
The Paxos algorithm, when presented in plain English, is very simple.
要約
Paxosアルゴリズムは、普通の言葉で語ればとても簡単だ。
1 Introduction
The Paxos algorithm for implementing a fault-tolerant distributed system
has been regarded as difficult to understand, perhaps because the original
presentation was Greek to many readers [5]. In fact, it is among the simplest
and most obvious of distributed algorithms. At its heart is a consensus
algorithm the “synod” algorithm of [5]. The next section shows that this
consensus algorithm follows almost unavoidably from the properties we want
it to satisfy. The last section explains the complete Paxos algorithm, which
is obtained by the straightforward application of consensus to the state machine
approach for building a distributed system an approach that should
be well-known, since it is the subject of what is probably the most often-cited
article on the theory of distributed systems [4].
1 はじめに
Paxosアルゴリズムはフォルトトレラントな分散システムを実装するために用いられるが、理解するのが難しいと考えられている。恐らくオリジナルの論文[5]が多くの読者にとって全く意味不明だったからだろう。
実際には最も単純で自明な分散アルゴリズムの1つだ。本質的には合意アルゴリズムで、[5]では議会のアルゴリズムになっている。
次の節ではこの合意アルゴリズムは私達が満たして欲しいと願う性質をほとんど回避不能に満すことを示す。
最後の節は分散システムを構築するための状態機械のアプローチを用いた簡単な合意アプリケーションにより得られた完全なPaxosアルゴリズムを説明する。そのアプローチはとてもよく知られている。なぜなら恐らく最もよく参照された論文[4]の主題だからだ。
2 The Consensus Algorithm
2.1 The Problem
Assume a collection of processes that can propose values. A consensus algorithm
ensures that a single one among the proposed values is chosen. If
no value is proposed, then no value should be chosen. If a value has been
chosen, then processes should be able to learn the chosen value. The safety
requirements for consensus are:
2 合意アルゴリズム
2.1 問題
値を提案することができるプロセスの集合を考える。合意アルゴリズムは提案された値の中から単一の値が選択されることを保障する。
もし値が1つも提案されない場合には1つの値も選択されない。
もし値が選択されたなら、プロセスは選択された値を記憶できなければならない。
合意のための安全な要件は
- 提案された値のみが選択され得る
- たった1つの値のみが選択される
- プロセスは実際に値が選択されるまでは、値を記憶しない。
We won’t try to specify precise liveness requirements. However, the goal is
to ensure that some proposed value is eventually chosen and, if a value has
been chosen, then a process can eventually learn the value.
We let the three roles in the consensus algorithm be performed by three
classes of agents: proposers, acceptors, and learners. In an implementation,
a single process may act as more than one agent, but the mapping from
agents to processes does not concern us here.
Assume that agents can communicate with one another by sending messages.
We use the customary asynchronous, non-Byzantine model, in which:
- Agents operate at arbitrary speed, may fail by stopping, and may restart. Since all agents may fail after a value is chosen and then restart, a solution is impossible unless some information can be remembered by an agent that has failed and restarted.
- Messages can take arbitrarily long to be delivered, can be duplicated, and can be lost, but they are not corrupted.
活性に対する明確な要件は定義しない。しかしゴールはある提案された値は結果的に選択され、もし値が選択されたならばプロセスは結果的にその値を記憶できることを確認することだ。
合意アルゴリズムにおいて、3つの役割を3つのクラスのエージェントに演じてもらおう。
proposer、acceptor、そしてlearnerだ。
実装においては単一のプロセスが1つ以上のエージェントを演じてもかまわない。しかしエージェントからプロセスへのマッピングはここでは気にしない。
エージェントはメッセージを送ることによってお互いに通信できるとしよう。慣習として非同期で、Byzantineモデル(*)ではないと定義する。つまり、
- エージェントは任意のスピードで動作し、停止により失敗しても良いし、再起動しても良い。全てのエージェントは値が選択された後に停止し、その後再起動しても良いので、解決策はエージェントがある程度の情報を停止と再起動に渡って記憶できない限り不可能である。
- メッセージは任意の長さの時間で配達されても良いし、複製されても良く、失われてもかまわない。しかしメッセージは壊れないものとする。
(*)Byzantineモデル： エージェントが裏切り物で嘘を付く可能性のあるモデル
2.2 Choosing a Value
The easiest way to choose a value is to have a single acceptor agent. A proposer
sends a proposal to the acceptor, who chooses the first proposed value
that it receives. Although simple, this solution is unsatisfactory because the
failure of the acceptor makes any further progress impossible.
2.2. 値を選択する
値を選択するのに最も簡単な方法は単一のacceptorエージェントを持つことだ。
proposerが提案をacceptorに送ったら、acceptorは最初に届いた提案値を選択すれば良い。
シンプルだが、このソリューションでは条件を満たさない。なぜならacceptorの障害がそれ以降の進捗を不可能にするからだ。
So, let’s try another way of choosing a value. Instead of a single acceptor,
let’s use multiple acceptor agents. A proposer sends a proposed value to a
set of acceptors. An acceptor may accept the proposed value. The value is
chosen when a large enough set of acceptors have accepted it. How large is
large enough? To ensure that only a single value is chosen, we can let a large
enough set consist of any majority of the agents. Because any two majorities
have at least one acceptor in common, this works if an acceptor can accept
at most one value. (There is an obvious generalization of a majority that
has been observed in numerous papers, apparently starting with [3].)
そこで他の値の選択方法を試そう。単一のacceptorの代わりに、複数のacceptorエージェントを使用しよう。
proposerが提案する値をacceptorの集団に送る。acceptorは提案された値を受け取ることができる。
その値は十分に大きなacceptorの集合がその提案に同意したときに選択される。
十分に大きな集団とはどれくらい大きな集団だろう？
単一の値のみが選択されるのを確約するために、十分に大きな集合とは任意の過半数のエージェントにより成り立つとしよう。任意の2つの過半数は少くとも1つのacceptorを共通に持つので、これはもしacceptorが最大でも1つの値のみを受け入れるときうまくいく。
(たぶん[3]で始まる多くの論文で過半数の明確な一般化が認められる)
In the absence of failure or message loss, we want a value to be chosen
even if only one value is proposed by a single proposer. This suggests the
requirement:
P1. An acceptor must accept the first proposal that it receives.
障害やメッセージを失うことが無い場合、単一のproposerによりたった1つの値が提案された場合でも値が選択されて欲しい。
このことが次の要件を示す
P1. acceptorは最初に受け取った提案を承認しなければならない
But this requirement raises a problem. Several values could be proposed by
different proposers at about the same time, leading to a situation in which
every acceptor has accepted a value, but no single value is accepted by a
majority of them. Even with just two proposed values, if each is accepted by
about half the acceptors, failure of a single acceptor could make it impossible
to learn which of the values was chosen.
しかしこの要件は1つの問題を引き起こす。ほとんど同時に異なるproposerにより提案された複数の値は、個々のacceptorが1つの値を承認するが、どの値も過半数のacceptorにより承認されないシチュエーションが導かれる。例えたった2つの値が提案されたとしてもそれぞれの値がだいたい半分のacceptorに承認され、たった1つのacceptorの障害が承認されたどの値も記憶することを不可能にしてしまうことが可能だ。
P1 and the requirement that a value is chosen only when it is accepted
by a majority of acceptors imply that an acceptor must be allowed to accept
more than one proposal. We keep track of the different proposals that an
acceptor may accept by assigning a (natural) number to each proposal, so a
proposal consists of a proposal number and a value. To prevent confusion,
we require that different proposals have different numbers. How this is
achieved depends on the implementation, so for now we just assume it. A
value is chosen when a single proposal with that value has been accepted by
a majority of the acceptors. In that case, we say that the proposal (as well
as its value) has been chosen.
P1とacceptorの過半数により承認された値のみが選択されるという要件はacceptorは1つ以上の提案を承認することが可能でなければならないことを暗示する。
我々は同じacceptorが承認するかもしれない異なる提案を、個々の提案に自然数を付けることによりトラッキングする。よって提案は提案番号と値により構成される。
混乱を防ぐために異なる提案は異なる番号を持つ必要がある。これがどうやって達成されるかは実装依存なので今はそう仮定するだけにしよう。
値はその値を持つ単一の提案が過半数のacceptorに承認された場合に選択される。
その場合、その提案(と共にその値)が選択されたと呼ぶ。
We can allow multiple proposals to be chosen, but we must guarantee
that all chosen proposals have the same value. By induction on the proposal
number, it suffices to guarantee:
P2. If a proposal with value v is chosen, then every higher-numbered proposal
that is chosen has value v.
複数の提案が選択されることを許可できるが、その場合全ての選択された提案は同じ値を持っていることを保障する必要がある。
提案番号より帰納的に、次を満たす必要がある。
P2. 値vを持つ提案が選択された場合、より大きな番号を持つ選択された提案は全て同じvを持つ
Since numbers are totally ordered, condition P2 guarantees the crucial safety
property that only a single value is chosen.
To be chosen, a proposal must be accepted by at least one acceptor. So,
we can satisfy P2 by satisfying:
P2a . If a proposal with value v is chosen, then every higher-numbered proposal
accepted by any acceptor has value v.
番号は完全に順序付けられているので条件P2はたった1つの値が選択されるという重大な安全性の属性を保障する。
選択されるためには、提案は最低でも1つのacceptorに承認される必要がある。従ってP2は以下が満たされる場合満たすことができる
P2a. もし値vを持つ提案が選択されたならば、任意のacceptorに承認されたより大きな番号の提案全ては値vを持つ
We still maintain P1 to ensure that some proposal is chosen. Because communication
is asynchronous, a proposal could be chosen with some particular
acceptor c never having received any proposal. Suppose a new proposer
“wakes up” and issues a higher-numbered proposal with a different value.
P1 requires c to accept this proposal, violating P2a . Maintaining both P1
and P2a requires strengthening P2a to:
P2b . If a proposal with value v is chosen, then every higher-numbered proposal
issued by any proposer has value v.
いくつかの提案が選択されることを確約するためまだP1を堅持している。
通信は非同期で行なわれるため、ある特定のacceptor、cが1つも提案を受け取らずにある提案が選択される場合がある。
新しいproposerが"起きて"より大きな番号の提案を異なる値で提出したと考える。
P1はcがこの提案を承認することを要求するが、P2aに違反する。
P1とP2aの両方を堅持するにはP2aを強化する必要がある
P2b. 値vを持つ提案が選択されたならば、任意のproposerにより提出された全てのより大きな番号の提案は値vを持つ
Since a proposal must be issued by a proposer before it can be accepted by
an acceptor, P2b implies P2a , which in turn implies P2.
提案はacceptorに承認され得る前にproposerから提出されてないといけないので、P2bはP2aを意味し、それは順にP2を意味する。
To discover how to satisfy P2b , let’s consider how we would prove that
it holds. We would assume that some proposal with number m and value
v is chosen and show that any proposal issued with number n > m also
has value v. We would make the proof easier by using induction on n,
so we can prove that proposal number n has value v under the additional
assumption that every proposal issued with a number in m..(n - 1) has
value v, where i..j denotes the set of numbers from i through j . For the
proposal numbered m to be chosen, there must be some set C consisting of a
majority of acceptors such that every acceptor in C accepted it. Combining
this with the induction assumption, the hypothesis that m is chosen implies:
Every acceptor in C has accepted a proposal with number in
m..(n - 1), and every proposal with number in m..(n - 1)
accepted by any acceptor has value v.
P2bを満たす方法を探すために、それが有効であることをどう証明できるかを考えよう。
番号mと値vを持つある提案が選択されたと仮定し、任意の番号n>mの提案が同じく値vを持っていると示そう。
より証明を簡単にするためにnについて帰納法を用いて、番号nの提案が値vを持つことを次の追加の仮定の下、証明できるだろう
番号m..n-1の全ての提案も値vを持つ、ここでi .. j はiからjまでの数を示す。
番号mの提案が選択されるなら、過半数のacceptorにより構成されるある集合Cが存在し、Cに属するacceptorは全て番号mの提案を承認していなければならない。
これを帰納法の仮定と結合すると、mが選択されたという仮説は次を示す。
Cに属する全てのacceptorは番号m..n-1の提案を承認し、任意のacceptorに承認された番号m..n-1の提案は値vを持っている
Since any set S consisting of a majority of acceptors contains at least one
member of C, we can conclude that a proposal numbered n has value v by
ensuring that the following invariant is maintained:
P2c. For any v and n, if a proposal with value v and number n is issued,
then there is a set S consisting of a majority of acceptors such that
either (a) no acceptor in S has accepted any proposal numbered less
than n, or (b) v is the value of the highest-numbered proposal among
all proposals numbered less than n accepted by the acceptors in S.
過半数のacceptorにより構成される任意の集合Sは最低でも1つのCのメンバーを含むため番号nの提案が値vを持つことを次の不変条件が堅持されることを確認することで結論づけることができる。
P2c. 任意のvとnにおいて、番号nと値vを持つ提案が発行されたとき、次のどちらかの条件に従う過半数のacceptorにより構成される集合Sが存在する
(a) Sに属する全てのacceptorはn未満の番号の提案を承認していない
(b) vはSに属するacceptorに承認された、番号がn未満の全ての提案の間で、最も大きな番号の提案の値
We can therefore satisfy P2b by maintaining the invariance of P2c.
従ってP2cの不変性を堅持することでP2bを満たすことができる
To maintain the invariance of P2c, a proposer that wants to issue a proposal
numbered n must learn the highest-numbered proposal with number
less than n, if any, that has been or will be accepted by each acceptor in
some majority of acceptors. Learning about proposals already accepted is
easy enough; predicting future acceptances is hard. Instead of trying to predict
the future, the proposer controls it by extracting a promise that there
won’t be any such acceptances. In other words, the proposer requests that
the acceptors not accept any more proposals numbered less than n. This
leads to the following algorithm for issuing proposals.
P2cの不変性を堅持するために、番号nの提案を発行したいproposerはn未満の最大の番号の提案を記憶しなければならない。もし存在するのならばそれはある過半数のacceptorの個々のacceptorにより承認されているか、承認される。
既に承認された提案を記憶することは十分に簡単だ。しかし、未来の承認を予見するのは難しい。
未来を予見する代わりに、proposerはそのような承認は存在し得ないという保障を展開することでコントロールする。
言い換えれば、proposerはacceptorに対しnより小さな番号の提案を一切承認しないよう要求する。
これが次の提案発行アルゴリズムに導く
1. A proposer chooses a new proposal number n and sends a request to
each member of some set of acceptors, asking it to respond with:
(a) A promise never again to accept a proposal numbered less than
n, and
(b) The proposal with the highest number less than n that it has
accepted, if any.
I will call such a request a prepare request with number n.
1. proposerは新しい提案番号nを選択し、あるacceptorの集合の各メンバーにリクエストを送り、次の返答を要求する
(a) nよりも小さな番号の提案を絶対に承認しない約束
(b) もし存在するのなら、番号がnより小さくて最も大きな承認済みの提案
このようなリクエストを番号nのprepareリクエストと呼ぶ。
2. If the proposer receives the requested responses from a majority of
the acceptors, then it can issue a proposal with number n and value
v, where v is the value of the highest-numbered proposal among the
responses, or is any value selected by the proposer if the responders
reported no proposals.
2. もしproposerが要求した返信をacceptorの過半数から受け取れば、番号nと値vの提案を発行できる。
この時vは返信の中で最も大きな番号の提案の値。もし返信に1つも提案が無い場合にはproposerが選んだ任意の値。
A proposer issues a proposal by sending, to some set of acceptors, a request
that the proposal be accepted. (This need not be the same set of acceptors
that responded to the initial requests.) Let’s call this an accept request.
proposerは任意のacceptorの集合に提案を承認して欲しいとリクエストとして送ることで、提案を発行する。
(最初のリクエストに対して返答したacceptorの集合と同じである必要はない)
これをacceptリクエストと呼ぼう。
This describes a proposer’s algorithm. What about an acceptor? It can
receive two kinds of requests from proposers: prepare requests and accept
requests. An acceptor can ignore any request without compromising safety.
So, we need to say only when it is allowed to respond to a request. It can
always respond to a prepare request. It can respond to an accept request,
accepting the proposal, iff it has not promised not to. In other words:
P1a . An acceptor can accept a proposal numbered n iff it has not responded
to a prepare request having a number greater than n.
これがproposerのアルゴリズムだ。
acceptorに関してはどうなるだろう？
acceptorはproposerから二種類のリクエストを受け取る。prepareリクエストとacceptリクエストだ。
acceptorはどのリクエストも安全性に歩み寄ることなく無視してかまわない。
重要なのはリクエストに返信してかまわないのはいつかだ。
prepareリクエストにはいつでも返信してかまわない。
acceptリクエストに対しては、返信しないと約束していない時、その時に限って提案を承認し、返信しても構わない。
言い換えれば
P1a. acceptorは番号nの提案を、nより大きな番号のprepareリクエストに返信していない時、その時に限って承認しても構わない。
Observe that P1a subsumes P1.
P1aがP1を含むことを確認せよ。
We now have a complete algorithm for choosing a value that satisfies the
required safety properties -- assuming unique proposal numbers. The final
algorithm is obtained by making one small optimization.
固有の提案番号を仮定することで、安全性の要件を充足する値の選択方法の完全なアルゴリズムができた。
最終的なアルゴリズムは小さな最適化を行うことで得られる。
Suppose an acceptor receives a prepare request numbered n, but it has
already responded to a prepare request numbered greater than n, thereby
promising not to accept any new proposal numbered n. There is then no
reason for the acceptor to respond to the new prepare request, since it will
not accept the proposal numbered n that the proposer wants to issue. So
we have the acceptor ignore such a prepare request. We also have it ignore
a prepare request for a proposal it has already accepted.
acceptorがprepareリクエストを番号nにて受けとったとする。しかしそのacceptorは既にnより大きな番号のprepareリクエストに返信していた。従って番号nの新しい提案を承認しないと約束してしまっている。それならばacceptorが新しいprepareリクエストに対し返信する理由は無い。acceptorはproposerが発行したい番号nの提案を承認することは無いからだ。だからacceptorにはそんなprepare要求は無視させる。同様に既に承認した提案に対するprepareリクエストも無視させる
With this optimization, an acceptor needs to remember only the highestnumbered
proposal that it has ever accepted and the number of the highestnumbered
prepare request to which it has responded. Because P2c must
be kept invariant regardless of failures, an acceptor must remember this
information even if it fails and then restarts. Note that the proposer can
always abandon a proposal and forget all about it as long as it never tries
to issue another proposal with the same number.
この最適化によりacceptorは、過去に承認した中で最も大きな番号のproposalと、過去に返信した最も大きな番号のprepareリクエストを記憶する必要がある。
なぜならP2cは失敗の存在に拘らず不変でなければならず、acceptorは例え停止し、後再起動してもこの情報を思い出さなければならない。
proposerはいつでも提案を中止し、そのことについて忘れてしまっても良いことに注意せよ。ただし同じ番号で新しい提案を試行してはならない。
Putting the actions of the proposer and acceptor together, we see that
the algorithm operates in the following two phases.
proposerとacceptorの行動を一緒にすることで、このアルゴリズムは次の2つのフェーズにて動作することがわかる。
Phase 1. (a) A proposer selects a proposal number n and sends a prepare
request with number n to a majority of acceptors.
(b) If an acceptor receives a prepare request with number n greater
than that of any prepare request to which it has already responded,
then it responds to the request with a promise not to accept any more
proposals numbered less than n and with the highest-numbered proposal
(if any) that it has accepted.
Phase 1.
(a) proposerは提案番号nを選択し、prepareリクエストを番号nと共にacceptorの過半数に送信する
(b) もしacceptorが既に返信した任意のprepareリクエストよりも大きな番号nを持つprepareリクエストを受信したならば、n未満の番号の提案は承認しないという約束と共に、(もし存在するなら)既に承認した中でも最も大きな番号のproposalをprepareリクエストに対し返信する。
Phase 2. (a) If the proposer receives a response to its prepare requests
(numbered n) from a majority of acceptors, then it sends an accept
request to each of those acceptors for a proposal numbered n with a
value v, where v is the value of the highest-numbered proposal among
the responses, or is any value if the responses reported no proposals.
(b) If an acceptor receives an accept request for a proposal numbered
n, it accepts the proposal unless it has already responded to a prepare
request having a number greater than n.
Phase 2.
(a) もしproposerが自分のprepareリクエスト(番号n)に対し過半数のacceptorから返信を受け取ったなら、番号nで値vの提案を個々のacceptorに送信する。この時vは返信の中で最も大きな番号の提案の値か、返信が1つも提案を提示しなかった場合は任意の値となる。
(b) もしacceptorが番号nの提案のacceptリクエストを受け取った時、nより大きな番号のprepareリクエストに返信してしまった場合以外はその提案を承認する。
A proposer can make multiple proposals, so long as it follows the algorithm
for each one. It can abandon a proposal in the middle of the protocol at any
time. (Correctness is maintained, even though requests and/or responses
for the proposal may arrive at their destinations long after the proposal
was abandoned.) It is probably a good idea to abandon a proposal if some
proposer has begun trying to issue a higher-numbered one. Therefore, if an
acceptor ignores a prepare or accept request because it has already received
a prepare request with a higher number, then it should probably inform
the proposer, who should then abandon its proposal. This is a performance
optimization that does not affect correctness.
proposerは複数の提案を個々がアルゴリズムに従う限り作ることができる。
proposerはプロトコル途中のいつでも提案を中止できる。
(その提案のリクエストや返信が提案が中止されたずっと後に目的地に着いても正確性は保持される。)
他のproposerがより大きな番号の提案を開始したら提案を中止するのは恐らく良い考えだ。
従ってacceptorがより大きな番号のprepareリクエストを受信したために、prepareやacceptリクエストを無視する場合、恐らくそのproposerに通知するべきだろう。そうしたらそのproposerは提案を中止するべきだ。
これはパフォーマンスの最適化であり、正確性には影響を与えない。
2.3 Learning a Chosen Value
To learn that a value has been chosen, a learner must find out that a proposal
has been accepted by a majority of acceptors. The obvious algorithm
is to have each acceptor, whenever it accepts a proposal, respond to all
learners, sending them the proposal. This allows learners to find out about
a chosen value as soon as possible, but it requires each acceptor to respond
to each learner a number of responses equal to the product of the number
of acceptors and the number of learners.
2.3 選択された値を記憶する
選択された値を記憶するために、learnerは提案が過半数のacceptorにより承認されたことを見付けなければならない。
明示的なアルゴリズムは個々のacceptorに、それが提案を承認した時常に全てのlearnerに返信し、その提案を送る。
これはlearnerに可能な限り早く選択された値を見つけさせられる。しかし個々のacceptorに個別のlearnerに返信させる必要があり、返信の数はacceptorとlearnerの数の積となる。
The assumption of non-Byzantine failures makes it easy for one learner
to find out from another learner that a value has been accepted. We can
have the acceptors respond with their acceptances to a distinguished learner,
which in turn informs the other learners when a value has been chosen. This
approach requires an extra round for all the learners to discover the chosen
value. It is also less reliable, since the distinguished learner could fail. But
it requires a number of responses equal only to the sum of the number of
acceptors and the number of learners.
Bizantine障害のない前提において、1つのlearnerが他のlearnerから値が承認されたことを知るのは簡単である。
acceptorに対し、その承認をlearnerの代表に返信させ、代表が順に他のlearnerにいつ値が選択されたのか報告するようにすることができる。
このアプローチは全てのlearnerが選択された値を知るのに余分なラウンドを必要とする。
またこの方法の信頼性は低い。learner代表が落ちる可能性があるからだ。
しかしこの方法はacceptorとlearnerの数の和の数しか返信を必要としない。
More generally, the acceptors could respond with their acceptances to
some set of distinguished learners, each of which can then inform all the
learners when a value has been chosen. Using a larger set of distinguished
learners provides greater reliability at the cost of greater communication
complexity.
より一般的に、acceptorはそれらの承認を複数のlearner代表に送ることができるだろう。
それらの1つ1つがlearner全員に対していつ値が選択されたのか通知することができる。
より大きなlearner代表の集合を使うと、より大きな信頼性をより大きな通信の複雑性のコストにて与えられる。
Because of message loss, a value could be chosen with no learner ever
finding out. The learner could ask the acceptors what proposals they have
accepted, but failure of an acceptor could make it impossible to know whether
or not a majority had accepted a particular proposal. In that case, learners
will find out what value is chosen only when a new proposal is chosen. If
a learner needs to know whether a value has been chosen, it can have a
proposer issue a proposal, using the algorithm described above.
メッセージが失われるために、選択された値がどのlearnerにも見つけられない可能性がある。
learnerはacceptorに対しどの提案を承認したのか確認できるが、acceptorの障害により過半数が特定のproposalを承認したのかどうかを知ることを不可能にしてしまうこともありえる。
そのようなケースでは、learnerは新しい提案が選択された時のみ、選択された値を知ることが可能である。
もしlearnerが値が選択されたのかどうか知る必要がある場合、learnerはproposerに対し上記のアルゴリズムを用いて提案を発行させることが可能だ。
2.4 Progress
It’s easy to construct a scenario in which two proposers each keep issuing
a sequence of proposals with increasing numbers, none of which are ever
chosen. Proposer p completes phase 1 for a proposal number n1. Another
proposer q then completes phase 1 for a proposal number n2 > n1. Proposer
p’s phase 2 accept requests for a proposal numbered n1 are ignored because
the acceptors have all promised not to accept any new proposal numbered
less than n2. So, proposer p then begins and completes phase 1 for a new
proposal number n3 > n2, causing the second phase 2 accept requests of
proposer q to be ignored. And so on.
2.4 進捗
2つのproposerがお互いに提案を連続する番号を増やしながら提出し、どちらも絶対に選択されないというシナリオを描くのは容易い。
proposer pが番号n1の提案のphase 1を終了したとする。
次にもう1つのproposer qが番号 n2 > n1の提案にてphase 1を完了する。
proposer pのphase 2にて番号n1の提案のacceptリクエストは無視される。なぜなら全てのacceptorは番号n2より小さな新しい提案を承認しないことを約束してしまっている。
従ってproposer pは次に番号n3 > n2の新しい提案のphase 1を開始して、完了し、それによりproposer qのphase 2が無視されることになる。以下、同様。
To guarantee progress, a distinguished proposer must be selected as the
only one to try issuing proposals. If the distinguished proposer can communicate
successfully with a majority of acceptors, and if it uses a proposal
with number greater than any already used, then it will succeed in issuing a
proposal that is accepted. By abandoning a proposal and trying again if it
learns about some request with a higher proposal number, the distinguished
proposer will eventually choose a high enough proposal number.
進捗を保障するにはproposerの代表を選択し、ただそれのみが提案を発行するようにしなければならない。
もしproposerの代表が過半数のacceptorとの通信に成功し、それが以前に使用されたどの番号よりも大きな番号の提案を用いれば、承認される提案を発行することに成功するだろう。
提案を中止し、再試行することでより大きな番号のリクエストを学習すれば、proposerの代表は結果的には十分に大きな提案番号を選択することが可能になるだろう。
If enough of the system (proposer, acceptors, and communication network)
is working properly, liveness can therefore be achieved by electing a
single distinguished proposer. The famous result of Fischer, Lynch, and Patterson
[1] implies that a reliable algorithm for electing a proposer must use
either randomness or real time for example, by using timeouts. However,
safety is ensured regardless of the success or failure of the election.
もしシステム(proposer、acceptor、そして通信のネットワーク)の十分な要素が正しく動作すれば、活性は単一のproposer代表を選択することで得られる。
Fischer, Lynch, and Patterson [1]による有名な結果は、proposerを選出する信頼できるアルゴリズムは乱数か、例えばタイムアウトを使用するようなリアルタイム性を用いる必要がある。
しかし安全性は選出の成功や失敗に関わらず守られている。
2.5 The Implementation
The Paxos algorithm [5] assumes a network of processes. In its consensus
algorithm, each process plays the role of proposer, acceptor, and learner.
The algorithm chooses a leader, which plays the roles of the distinguished
proposer and the distinguished learner. The Paxos consensus algorithm is
precisely the one described above, where requests and responses are sent as
ordinary messages. (Response messages are tagged with the corresponding
proposal number to prevent confusion.) Stable storage, preserved during
failures, is used to maintain the information that the acceptor must remember.
An acceptor records its intended response in stable storage before
actually sending the response.
2.5 実装
Paxosアルゴリズム[5]はプロセスのネットワークを前提とする。
その合意アルゴリズムにおいて、各プロセスはproposer、acceptor、そしてlearnerの役割を演じる。
アルゴリズムはproposer代表とlearner代表を演じるleaderを選出する。
Paxos合意アルゴリズムは正確に上述されたもので、リクエストと返信は通常のメッセージとして送られる。
(返信のメッセージは対応する提案の番号でタグ付けられ混乱を防ぐ。)
障害の間も維持される安定したストレージがacceptorが記憶しなければならない情報を保持するのに用いられる。
acceptorは意図する返信を安定したストレージに対し実際に送信する前に記録する。
All that remains is to describe the mechanism for guaranteeing that no
two proposals are ever issued with the same number. Different proposers
choose their numbers from disjoint sets of numbers, so two different proposers
never issue a proposal with the same number. Each proposer remembers
(in stable storage) the highest-numbered proposal it has tried to issue,
and begins phase 1 with a higher proposal number than any it has already
used.
あと必要なものは、どの2つの提案の組も同じ番号を絶対に発行しないことを保障するメカニズムの記述だ。
異なるporoposerはそれぞれの番号を互いに素な番号の集合から選択する。そうすることで2つの異なるproposerが同じ番号の提案を発行することは絶対に起らない。
それぞれのproposerは安定したストレージにそれが過去に発行しようとした最も大きな番号の提案を記録する。
そして以前に使用したどの番号よりも大きな番号の提案にてphase 1を開始する。
3 Implementing a State Machine
A simple way to implement a distributed system is as a collection of clients
that issue commands to a central server. The server can be described as
a deterministic state machine that performs client commands in some sequence.
The state machine has a current state; it performs a step by taking
as input a command and producing an output and a new state. For example,
the clients of a distributed banking system might be tellers, and
the state-machine state might consist of the account balances of all users.
A withdrawal would be performed by executing a state machine command
that decreases an account’s balance if and only if the balance is greater than
the amount withdrawn, producing as output the old and new balances.
3. 状態機械の実装
分散システムを実装するシンプルな方法は、中央サーバに命令を発行するクライアントの集合とすることだ。
サーバは決定性を持つ状態機械として記述可能で、クライアントの命令を任意の順序で実行する。
状態機械は現在の状態を持つ。コマンドを入力すると1ステップを実行し、出力と新しい状態を生産する。
例として、分散銀行システムのクライアントが窓口係とし、状態機械の状態は全ユーザの口座の残高により構成されるとする。
預金の引き出しは状態機械により、口座の残高が引き出す金額よりも大きい場合のみ、残高を減らすコマンドとして実行されるだろう。
出力として引き出し前と後の残額を生成する。
An implementation that uses a single central server fails if that server
fails. We therefore instead use a collection of servers, each one independently
implementing the state machine. Because the state machine is deterministic,
all the servers will produce the same sequences of states and outputs if they
all execute the same sequence of commands. A client issuing a command
can then use the output generated for it by any server.
単一の中央サーバを利用する実装はそのサーバが落ちると障害を発生する。
従ってその代わりとして、サーバの集合を用いて、個々に独立した状態機械を実装する。
状態機械は決定性を持つので全てのサーバが同じコマンドの列を実行すれば、同じ状態と出力の列を生成する。
コマンドを発行したクライアントは任意のサーバが生成した出力を利用することができる。
To guarantee that all servers execute the same sequence of state machine
commands, we implement a sequence of separate instances of the Paxos
consensus algorithm, the value chosen by the ith instance being the i th state
machine command in the sequence. Each server plays all the roles (proposer,
acceptor, and learner) in each instance of the algorithm. For now, I assume
that the set of servers is fixed, so all instances of the consensus algorithm
use the same sets of agents.
全てのサーバが同じ状態機械命令の列を実行することを保障するために、Paxos合意アルゴリズムの別々のインスタンスの列を実装し、i番目のインスタンスにより選択された値をi番目の状態機械命令にする。
各サーバは全ての役(proposer、acceptor、learner)を個々のアルゴリズムのインスタンスにて演ずる。
差し当たり、サーバの集合は固定だとしよう。つまり全ての合意アルゴリズムのインスタンスは同じエージェントの集合を用いる。
In normal operation, a single server is elected to be the leader, which
acts as the distinguished proposer (the only one that tries to issue proposals)
in all instances of the consensus algorithm. Clients send commands to the
leader, who decides where in the sequence each command should appear.
If the leader decides that a certain client command should be the 135th
command, it tries to have that command chosen as the value of the 135th
instance of the consensus algorithm. It will usually succeed. It might fail
because of failures, or because another server also believes itself to be the
leader and has a different idea of what the 135th command should be. But
the consensus algorithm ensures that at most one command can be chosen
as the 135th one.
通常の運用では1つのサーバがリーダーとして選ばれる。リーダーは全ての合意アルゴリズムのインスタンスにおいて、proposerの代表(提案を発行する唯一の者)として振る舞う。
クライアントはリーダーに命令を送り、リーダーは個々の命令が列においてどの位置にあるかを決定する。
もしリーダーが特定のクライアント命令は135番目の命令だと決めたならば、そのコマンドが135番目の合意アルゴリズムのインスタンスにより選択された値となるよう試行する。
それは通常成功するだろう。
障害や他のサーバが自身をリーダーだと思い135番目のコマンドにするべく異なる考えを持つ時にそれは失敗する。
しかし合意アルゴリズムはたかだか1つのコマンドが135番目のコマンドとして選択され得ることは保障する。
Key to the efficiency of this approach is that, in the Paxos consensus
algorithm, the value to be proposed is not chosen until phase 2. Recall that,
after completing phase 1 of the proposer’s algorithm, either the value to be
proposed is determined or else the proposer is free to propose any value.
このアプローチの効率性に対する鍵は、Paxos合意アルゴリズムにおいては、提案されるべき値はphase 2までは選択されないことだ。
proposerのアルゴリズムのphase 1が終了した後に、どの値が提案されるべきかが決定されるか、またはproposerが任意の値を自由に提案できることを思い出せ。
I will now describe how the Paxos state machine implementation works
during normal operation. Later, I will discuss what can go wrong. I consider
what happens when the previous leader has just failed and a new leader has
been selected. (System startup is a special case in which no commands have
yet been proposed.)
筆者はここからPaxos状態機械の実装が、通常動作の間、どのように働くかを記述する。
その後、どのような誤りが起こり得るか記述する。
筆者は前のリーダーが障害を起こし、新しいリーダーが選択された丁度その時に何が起こるかを考えている。
(システムスタートアップは1つも命令が提案されていない特別なケースである。)
The new leader, being a learner in all instances of the consensus algorithm,
should know most of the commands that have already been chosen.
Suppose it knows commands 1-134, 138, and 139 -- that is, the values chosen
in instances 1-134, 138, and 139 of the consensus algorithm. (We will
see later how such a gap in the command sequence could arise.) It then
executes phase 1 of instances 135-137 and of all instances greater than 139.
(I describe below how this is done.) Suppose that the outcome of these executions
determine the value to be proposed in instances 135 and 140, but
leaves the proposed value unconstrained in all other instances. The leader
then executes phase 2 for instances 135 and 140, thereby choosing commands
135 and 140.
新しいリーダーは、全ての合意アルゴリズムのインスタンスにおいてlearnerとなることにより、既に選択された命令のほとんどについて知らねばならない。
新しいリーダーが1-134,138,139の命令を知っているとしよう。つまり合意アルゴリズムの1-134, 138, 139番目のインスタンスにより選択された値だ。
(我々は後程、命令列の中にそのようなギャップがどのようにして起こり得るかを知ることになる。)
リーダーは次に135から137のインスタンスそして139以上の全てのインスタンスのphase 1を実行する。
(これがどのように行われるかは下に記述する。)
これらの実行結果がインスタンス135と140の提案されるべき値を決定したとしよう。しかし他のインスタンス全ての提案された値が束縛されない状態のままであるとする。
リーダーは次にインスタンス135と140に対しphase 2を実行する。それにより135と140の命令を選択する。
The leader, as well as any other server that learns all the commands
the leader knows, can now execute commands 1-135. However, it can’t
execute commands 138-140, which it also knows, because commands 136
and 137 have yet to be chosen. The leader could take the next two commands
requested by clients to be commands 136 and 137. Instead, we let it fill the
gap immediately by proposing, as commands 136 and 137, a special “no-op”
command that leaves the state unchanged. (It does this by executing
phase 2 of instances 136 and 137 of the consensus algorithm.) Once these
no-op commands have been chosen, commands 138-140 can be executed.
リーダーと、リーダーが知っている全ての命令を学ぶ他のサーバは同じく、1-135の命令を実行することが可能だ。
しかし、リーダーは138-140についても知っているのに実行することができない。
命令136と137がまだ選択されていないためだ。
リーダーはクライアントからリクエストされる次の2つの命令を命令136と137にすることも可能だろう。
しかしここではそのギャップを至急リーダーに命令136と137として、状態を変更しない特別な"no-op"命令を提案させることにより埋めさせよう。
(これは合意アルゴリズムのインスタンス136と137のphase 2を実行することにより行われる。)
これらのno-op命令が選択されれば直ぐに、命令138と140は実行されることができる。
注： "no-op"は"no operation"の略であり、何もしない命令。
Commands 1-140 have now been chosen. The leader has also completed
phase 1 for all instances greater than 140 of the consensus algorithm, and it
is free to propose any value in phase 2 of those instances. It assigns command
number 141 to the next command requested by a client, proposing it as the
value in phase 2 of instance 141 of the consensus algorithm. It proposes the
next client command it receives as command 142, and so on.
今、命令1-140が選択された。リーダーはまた合意アルゴリズムの140より大きなインスタンス全てのphase 1を終了した。
そしてリーダーはそれらのインスタンスのphase 2として、任意の値を自由に提案できる。
リーダーはクライアントによりリクエストされた次の命令に命令番号141をアサインする。
リーダーは受け取った次のクライアントの命令を命令142として提案する。以下、同文。
The leader can propose command 142 before it learns that its proposed
command 141 has been chosen. It’s possible for all the messages it sent
in proposing command 141 to be lost, and for command 142 to be chosen
before any other server has learned what the leader proposed as command
141. When the leader fails to receive the expected response to its phase 2
messages in instance 141, it will retransmit those messages. If all goes well,
its proposed command will be chosen. However, it could fail first, leaving a
gap in the sequence of chosen commands. In general, suppose a leader can
get α commands ahead -- that is, it can propose commands i + 1 through
i+α after commands 1 through i are chosen. A gap of up to α-1 commands
could then arise.
リーダーは命令142を命令141が選択されたと知る前に提案することが可能だ。
命令141の提案中に送った全てのメッセージが失われ、任意の他のサーバがリーダーが命令141として何を提案したかを知る前に命令142が選択されることが起こり得る。
リーダーが141のインスタンスにおいて、phase 2のメッセージに対し期待されるレスポンスを受信するのに失敗したとき、リーダーはそれらのメッセージを再送信する。
もし全てがうまくいけば、提案した値が選択される。
しかし最初に失敗する可能性があり、選択されたコマンドの列の中にギャップを残す。
一般に、リーダーがα個の命令を前持って得られるとする。それはつまりリーダーは命令1からiが選択された後に、命令i+1からi+αまで提案可能ということになる。
するとα-1個までの命令のギャップが起こり得る。
A newly chosen leader executes phase 1 for infinitely many instances
of the consensus algorithm -- in the scenario above, for instances 135-137
and all instances greater than 139. Using the same proposal number for
all instances, it can do this by sending a single reasonably short message
to the other servers. In phase 1, an acceptor responds with more than a
simple OK only if it has already received a phase 2 message from some
proposer. (In the scenario, this was the case only for instances 135 and
140.) Thus, a server (acting as acceptor) can respond for all instances with
a single reasonably short message. Executing these infinitely many instances
of phase 1 therefore poses no problem.
新しく選択されたリーダーは合意アルゴリズムの無限に多くのインスタンスに対しphase 1を実行する。
上のシナリオではインスタンス135-137と139より大きな全てのインスタンスに対して実行する。
同じ提案番号を全てのインスタンスに対して用いることで、新リーダーは単一の合理的に短いメッセージを他のサーバに送ることでこれを実行することができる。
phase1において、acceptorは既に他のproposerからphase 2のメッセージを受け取っている場合に限り単純なOK以上の返信を行う。
(このシナリオでは、これはインスタンス135と140のみだ。)
従ってacceptorを演じるサーバは全てのインスタンスに対し単一の合理的に短いメッセージを返信する。
これらの無限に多いインスタンスのphase 1を実行することは、従って何の問題も持たらさない。
Since failure of the leader and election of a new one should be rare
events, the effective cost of executing a state machine command -- that is, of
achieving consensus on the command/value -- is the cost of executing only
phase 2 of the consensus algorithm. It can be shown that phase 2 of the
Paxos consensus algorithm has the minimum possible cost of any algorithm
for reaching agreement in the presence of faults [2]. Hence, the Paxos algorithm
is essentially optimal.
リーダーの障害と新リーダーの選出は稀なイベントであるべきなので、状態機械の命令を実行する効率的なコストは、つまり命令=値について同意を得るための効率的なコストは、合意アルゴリズムのphase 2のみを実行するコストだ。
Paxos合意アルゴリズムのPhase2は障害出現下で同意に逹っする任意のアルゴリズムの最小の起こりうるコストであることがわかっている[2]。
従ってPaxosアルゴリズムは本質的に最適解だ。
This discussion of the normal operation of the system assumes that there
is always a single leader, except for a brief period between the failure of the
current leader and the election of a new one. In abnormal circumstances,
the leader election might fail. If no server is acting as leader, then no new
commands will be proposed. If multiple servers think they are leaders, then
they can all propose values in the same instance of the consensus algorithm,
which could prevent any value from being chosen. However, safety is
preserved -- two different servers will never disagree on the value chosen as
the ith state machine command. Election of a single leader is needed only
to ensure progress.
システムの通常運用でのこの議論は常に単一のleaderが存在することを想定している。例外として現在のleaderの障害と新リーダーの選出の短い間が存在する。
異常な状況において、リーダーの選出が失敗するかもしれない。leaderを演じるサーバが無い時、新しい命令が提案されることはない。
もし複数のサーバが自らがリーダーであると考えたなら、全員が合意アルゴリズムの同じインスタンスにおいて値を提案するだろう。その場合どの値も選択されないだろう。しかし安全性は維持されている。2つの異なるサーバがi番目の状態機械の命令として選択された値において一致しないことは絶対に無い。
If the set of servers can change, then there must be some way of determining
what servers implement what instances of the consensus algorithm.
The easiest way to do this is through the state machine itself. The current
set of servers can be made part of the state and can be changed with ordinary
state-machine commands. We can allow a leader to get α commands
ahead by letting the set of servers that execute instance i + α of the consensus
algorithm be specified by the state after execution of the i th state
machine command. This permits a simple implementation of an arbitrarily
sophisticated reconfiguration algorithm.
もしサーバの集合が変化し得るなら、どのサーバが合意アルゴリズムのどのインスタンスを実施しているのかを判断する方法が必須である。
これを行う最も簡単な方法は状態機械自身を通すことだ。現在のサーバの集合を状態の一部とすることが可能であり、通常の状態機械の命令で変更することが可能だ。
i番目の状態機械命令の実行後の状態により合意アルゴリズムのインスタンスi+αを実行するサーバの集合が特定されることにより、leaderに対し予めα個の命令を取得することを許可する。
これが任意に精緻な再構成を行うアルゴリズムの実装を可能にする。
References
参照
[1] Michael J. Fischer, Nancy Lynch, and Michael S. Paterson. Impossibility
of distributed consensus with one faulty process. Journal of the ACM,
32(2):374 382, April 1985.
[2] Idit Keidar and Sergio Rajsbaum. On the cost of fault-tolerant consensus
when there are no faults -- a tutorial. TechnicalReport MIT-LCS-TR-821,
Laboratory for Computer Science, Massachusetts Institute Technology,
Cambridge, MA, 02139, May 2001. also published in SIGACT News
32(2) (June 2001).
[3] Leslie Lamport. The implementation of reliable distributed multiprocess
systems. Computer Networks, 2:95 114, 1978.
[4] Leslie Lamport. Time, clocks, and the ordering of events in a distributed
system. Communications of the ACM, 21(7):558 565, July 1978.
[5] Leslie Lamport. The part-time parliament. ACM Transactions on Computer
Systems, 16(2):133 169, May 1998.
