コンテンツにスキップ

Paxosアルゴリズム

出典: フリー百科事典『ウィキペディア（Wikipedia）』

Paxosとは信頼性が低いプロセッサのネットワークにおいて合意の問題を解決するためのプロトコルの集合である。 合意とは参加者のグループにおいて単一の結果について合意を得るプロセスである。参加者や通信手法に障害が起きる可能性がある場合、この問題は困難なものとなる[1]。

合意プロトコルは分散コンピューティングにおける状態機械アプローチの基礎であり、これはレスリー・ランポート[2]により提案され、Fred Schneiderによってサーベイがなされている[3]。

Paxosプロトコルは1990年に登場し命名されたが、論文として出版されたのは1998年であった[4]。 これ以前に、ナンシー・リンチ、Cynthia Dwork、Larry Stockmeyerは"部分同期"システムの広い範囲における合意形成方法を例証している。Paxosは分散トランザクションの文脈において、1988年にOkiとBarbara Liskovが発表したViewstampedレプリケーションにおける合意形成に使用されるプロトコルと非常に似ている[5]。

状態機械アプローチとはアルゴリズムをフォールトトレラントな、分散した実装に変換する技法である。アドホックな技術では重要な障害ケースが未解決 のままになる可能性がある。Lamport等によって定式化された手法では全てのケースが安全に処理されることを保証している。

Paxosプロトコル集合には次のものについてトレードオフを持っているような数種のものがある。

  • プロセッサ数
  • 合意された値を知るまでのメッセージ遅延
  • 各ノードのアクティビティレベル
  • 送信されたメッセージ数
  • 障害の種類

Paxosプロトコル集合の共通の特徴は、不整合な状態に陥らないということがある[4][6][7][8][9]。

安全性と活性に関する特性

[編集]

安全性を保証するため、Paxosは3つの安全性の特性を定義し、障害パターンによらず、これらが必ず守られていることを保証する。

非自明性
提案された値のみが習得される。[7]
完全性
最大一つの値が習得可能である。(つまり、2つの習得ノードがことなる値を習得することはない)[7][8]
活性(C;L)
もし、値Cが提案されたならば、習得ノードLは何らかの値を習得する。(ただし十分数のプロセッサが障害を起こしていない場合)[8]

前提

[編集]

Paxosの説明を単純化するため、次の前提や定義が明確化されなければならない。応用範囲を広げるための技術は文献に提示されており、当記事では触れない。詳細は外部リンクを参照のこと。

プロセッサ

[編集]
  • プロセッサは任意の速度で動作してもよい。
  • プロセッサは障害が発生する可能性がある。
  • 安定したストレージを持つプロセッサは障害の後、再参加可能である。
  • プロセッサは共謀したり、誤った情報を返すなど、プロトコルの手続きを変えるようなことはしない。(任意の障害を容認する手法として、#ビザンチンPaxosを参照のこと)

ネットワーク

[編集]
  • プロセッサは他の全てのプロセッサにメッセージを送信することが可能である。
  • メッセージは非同期的に送信され、到達までに任意の時間がかかることがある。
  • メッセージは失われたり、順序を変更されたり、複製されることがある。
  • メッセージは破損なしに配信される。(任意の障害を許容する手法として#ビザンチンPaxosを参照のこと)

プロセッサ数

[編集]

一般に、分散合意アルゴリズムは個のプロセッサが存在すれば個のプロセッサが同時に障害を起こした場合でも動作することができる。しかし、同時障害が以下なら、再構成を行うことによって、合計の障害数がいくら増えてもよいようにプロトコルを作ることができる。

役割

[編集]

Paxosはプロトコルにおけるプロセッサの動作を、クライアント(Client)，アクセプタ(Acceptor)，プロポーザ(Proposer)，ラーナ(Learner), リーダ(Leader)のいずれかの役割として表現する。 典型的な実装では、1つのプロセッサは同時に2つ以上の役割を演じることもできる。 これによってプロトコルの正当性に影響を受けることはない。 実際、プロトコルが必要とする遅延やメッセージ数を改善するために、複数の役割をまとめることはよく行われる。

クライアント

クライアントは分散システムに対してリクエストを送信し、返信を待つ。 分散ファイルサーバー上のファイルに対する書き込みリクエストはその1例である．

アクセプタ

アクセプタはフォールトトレラントな「メモリ」として働く。 アクセプタはクォーラム(Quorum = 定足数)と呼ばれるグループにまとめられる。 アクセプタへのメッセージは必ず定足数のアクセプタに送られなければならない。 アクセプタが受信したメッセージは、グループの各アクセプタから同じコピーが送られてこない限り無視される。

プロポーザ

プロポーザはクライアントのリクエストを支持して、アクセプタの同意を取ろうと試み、プロトコルを前に進めるための調停を行う。

ラーナ

ラーナはプロトコルの複製要素として働く。 一旦クライアントのリクエストがアクセプタによって同意されると、ラーナはアクションを取る(すなわち、クライアントのリクエストを実行しその結果をクライアントに返信する)ことができる。 可用性を高めるために、複数のラーナが存在しても良い。

リーダ

Paxosはリーダと呼ばれる特別なプロポーザが必要である。 複数のプロセッサが、自身がリーダであると信じることがあり得るが、そのどれかが最終的に選ばれる場合に限り、プロトコルは前進することが保証される。 もし2つのプロセッサがリーダーであると信じている場合、競合するアップデートを繰り返し提案することにより、プロトコルを停止させてしまうことがありえる。しかし、その場合でも安全性は保たれている。

クォーラム

[編集]

クォーラムは、少なくとも一定以上のプロセッサが結果に関する知識を保持している事を保証することによって、Paxosの安全性を担保する。 クォーラムはアクセプタの集合の部分集合であって、どの二つの部分集合(つまりクォーラム)も1つ以上のメンバを共有しているものと定義される。 典型的には、クォーラムは過半数のアクセプタである。 例えば、4つのアクセプタが与えられた場合、過半数のクォーラムは任意の3つのアクセプタの集合({A, B, C}, {A, B, D}, {A, C, D}, {B, C, D})である。 一般の場合、アクセプタに任意の正の重みを割り当てて、メンバの重みの和が全体の重みの過半となるような集合がクォーラムである。

提案番号と合意値

[編集]

合意結果（合意値）を v と定義する試みは、アクセプタに対する提案として行われる。 各提案はプロセッサによってユニークな番号が振られる。 番号が振られた提案に対する合意値は Paxos プロトコルを実行する過程で計算されても良いし，そうでなくてもかまわない。

基本Paxos

[編集]

ビザンチンPaxos

[編集]

脚注

[編集]
  1. ^ Pease, Marshall; Robert Shostak, Leslie Lamport (April 1980). “Reaching Agreement in the Presence of Faults”. Journal of the Association for Computing Machinery 27 (2). http://research.microsoft.com/users/lamport/pubs/pubs.html#reaching 2007年2月2日閲覧。. 
  2. ^ Lamport, Leslie (July 1978). “Time, Clocks and the Ordering of Events in a Distributed System”. Communications of the ACM 21 (7): 558--565. doi:10.1145/359545.359563. http://research.microsoft.com/users/lamport/pubs/pubs.html#time-clocks 2007年2月2日閲覧。. 
  3. ^ Schneider, Fred (1990). “Implementing Fault-Tolerant Services Using the State Machine Approach: A Tutorial”. ACM Computing Surveys 22: 299. doi:10.1145/98163.98167. https://web.archive.org/web/20060508040935/http://www.eecs.harvard.edu/cs262/DSbook.c7.pdf. 
  4. ^ a b Lamport, Leslie (May 1998). “The Part-Time Parliament”. ACM Transactions on Computer Systems 16 (2): 133--169. doi:10.1145/279227.279229. http://research.microsoft.com/users/lamport/pubs/pubs.html#lamport-paxos 2007年2月2日閲覧。. 
  5. ^ Oki, Brian; Liskov, Barbara (1988). "Viewstamped Replication: A New Primary Copy Method to Support Highly-Available Distributed Systems". PODC '88: Proceedings of the seventh annual ACM Symposium on Principles of Distributed Computing. pp. 8--17. doi:10.1145/62546.62549。
  6. ^ Lamport, Leslie; Massa, Mike (2004). "Cheap Paxos". Proceedings of the International Conference on Dependable Systems and Networks (DSN 2004).
  7. ^ a b c Lamport, Leslie (2005年). “Fast Paxos”. 2007年2月2日閲覧。
  8. ^ a b c Lamport, Leslie (2005). Generalized Consensus and Paxos. http://research.microsoft.com/users/lamport/pubs/pubs.html#generalized 2007年2月2日閲覧。. 
  9. ^ Castro, Miguel (2001年). “Practical Byzantine Fault Tolerance”. 2007年2月2日閲覧。

関連項目

[編集]

外部リンク

[編集]
「https://ja.wikipedia.org/w/index.php?title=Paxosアルゴリズム&oldid=101071394」から取得