Paxosという分散システムでconsensusを取得するアルゴリズムがある。複数台のマシンから構成されるシステムで、単一のproposalが共有されることを保証するものである。ネットワークが不安定だったりシステムを構成するマシンが落ちたりするので、複数台のマシンが情報を共有するというのは難しいものなのだ。
Leslie Lamport*1の『Paxos Made Simple』を読んで勉強中です。
証明は非常に難しいらしいが、アルゴリズム自体は単純です*2。以下に、記事からPaxosアルゴリズムの流れを引用します。
Phase 1.
A proposer selects a proposal number n and sends a prepare request with number n to a majority of acceptors.
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 2.
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.
If an acceptor receives an accept request for a proposal numbered n it accepts the proposal unless it has already responded a prepare request having a number greater than n.
ミソはprepare requestとaccept requestの２回に分けてproposeを行う点である。データベースでのtwo-phase commitによく似ている。詳しくないので分からないが、本質的には同じものなのかな？
練習で実装してみた。
A simple Paxos implementation for study.
特に結論とかはない。
- 作者: ジョンマコーミック
- 出版社/メーカー: 日経BP社
- 発売日: 2013/10/10
- メディア: Kindle版
- この商品を含むブログ (6件) を見る
