|
Paxosアルゴリズム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つの安全性の特性を定義し、障害パターンによらず、これらが必ず守られていることを保証する。
前提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脚注
関連項目外部リンク
|
