Clever Geek Handbook

分散システムにおけるコンセンサス。 パクソス

最近、科学出版物では、Paxosと呼ばれる分散システムのコンセンサスアルゴリズムに言及することが多くなっています。 そのような出版物の中で、Googleの従業員（ チャビー 、 メガストア 、 スパナー ）の多くの作品は、ハブ 、 WANdiscoのアーキテクチャ、 Cephシステムなどで以前は部分的に取り上げられていました 。



この記事では、アルゴリズムの作成者であるレスリーランポートがかつてそれを作ろうとしたときに 、この状況を修正し、このアルゴリズムについて明確な言語で話そうとします 。



まず、このアルゴリズムが解決する問題を理解する必要があります。 これを行うには、x86サーバーのクラスターである分散情報処理システムを想像してください。 1台のサーバーの障害の確率が小さく、単純なシステムを実装する場合はしばしば無視できる場合、サーバーのクラスターでは、1台のサーバーの障害の確率は数倍大きくなります。N台のサーバーの1台のMTBFは、1台のサーバーのMTBFのN倍です。 これに、ネットワーク機器の故障やパケット損失、ハードドライブの故障、OSおよびアプリケーションレベルでのサーバーソフトウェアの故障などのネットワークの信頼性の欠如を追加します。 Googleによると 、1800台のマシンのクラスターでは、クラスターの運用開始から1年で1000台のサーバー障害、つまり1日あたり3回の障害について話します。これには、ハードドライブ障害、ネットワークおよび電源の問題などが含まれません その結果、分散システムのソフトウェアにフォールトトレランスを設定しない場合、上記の各問題がシステム障害につながるシステムが得られます。



したがって、コンセンサスに達するタスクは、個々の参加者が失敗し、誤った情報を提供し、データ送信媒体による送信値を歪める可能性がある状況で、参加者グループによって合意値を取得するタスクです。 一般に、分散システムのコンポーネントの異常な機能のシナリオは、2つのクラスに分類できます。



  1. 完全なコンポーネント障害。 このクラスの問題の特徴は、このような障害が分散システムのコンポーネントの1つにアクセスできないこと（または、スイッチ障害の場合はネットワークのセグメンテーション）につながることです。 このクラスの問題には、サーバー障害、ストレージシステム障害、スイッチ障害、オペレーティングシステム障害、アプリケーション障害が含まれます。
  2. ビザンチンの間違い。 システムノードは機能し続けますが、同時に誤った情報を返す可能性があるという特徴があります。 ECCを使用せずにRAMを使用すると、メモリから誤ったデータを読み取ったり、ネットワーク機器のエラーがパケットの破損などにつながる可能性があるとします。


セカンドクラスのエラーは、検出と修正がはるかに困難です。 一般に、レスリーランポートは 、 Nノードのビザンチン問題を修正するには、分散システムが少なくとも3N + 1ノードで構成され、特別なコンセンサスアルゴリズムを実装する必要があることを証明しました。 このレベルのフォールトトレランスは、重大度が非常に高いシステムの大部分（たとえば、宇宙産業のタスク）に必要です。



クラスターコンピューティングでは、フォールトトレランスは通常、完全なコンポーネント障害に対するシステムの抵抗として理解されます。 そのようなシステムでコンセンサスを達成するために、Paxosアルゴリズムが使用されます。 このアルゴリズムは 、前世紀の90年代にレスリーランポートによって提案され 、議会の仕事を組織する架空のシステムを持つギリシャのパクソス島にちなんで命名されました。 コンセンサスを得るために、このアルゴリズムでは、 2N + 1ノードのシステムで少なくともN + 1ノードが機能する必要があります。これらのN + 1ノードは「クォーラム」と呼ばれます



エージェントと以下の役割の相互作用におけるアルゴリズムの本質：



基本的なPaxosアルゴリズムは、次の手順で構成されています。



1a。 準備 （「提供」）。 このフェーズでは、提案者はシーケンス番号Nの 「文章」を生成し、それをすべての承認者に送信します。 次の「提案」のそれぞれについて、数値Nは以前に選択した値よりも大きくなければなりません



1b。 約束 （「約束」）。 各アクセプターは、シーケンス番号Nと値Vの 「オファー」を受け取ります。 「オファー」の数がこのアクセプターによって以前に受け入れられたすべてよりも多い場合、彼はこのメッセージに「約束」を付けて返信し、 N未満のシリアル番号の「オファー」を受け入れないようにしなければなりません。 指定されたアクセプターが何らかの「オファー」をすでに受け入れている場合、この「オファー」の数N iと受け入れられた値V iを返さなければなりません。そうでなければ、空の値を返します



2a。 受け入れる！ （「同意する」）。 提案者は、承認者定足数から「約束」を受け取った場合、要求をさらに処理する準備ができていると見なします。 アクセプターからの「約束」で値N iおよびV iも来る場合、提案者は、最大N iの 「約束」の値V iに等しいVを選択します。 次に、提案者は、 NおよびVの値を含む「承認」要求をすべての承認者に送信します。



2b。 受け入れられました 。 アクセプターが値NおよびVの 「accept」メッセージを受信すると、 Nより厳密に大きい数のオファーを受け入れることを「約束」していない場合にのみ、彼はそれを受け入れます。 それ以外の場合、値を想定し、すべての学習者に「受け入れられた」メッセージで応答します



学習者のタスクは単純です-Vの値で「accepted」メッセージを取得し、それを覚えておいてください



アルゴリズムの機能の例： 

Client Proposer Acceptor Learner | | | | | | | X-------->| | | | | | Request | X--------->|->|->| | | Prepare(1) | |<---------X--X--X | | Promise(1,{Va,Vb,Vc}) | X--------->|->|->| | | Accept!(1,Vn=last(Va,Vb,Vc)) | |<---------X--X--X------>|->| Accepted(1,Vn) |<---------------------------------X--X Response | | | | | | |


分散システムのコンポーネントのいずれかに障害が発生するとどうなりますか？



失敗アクセプター： 

 Client Proposer Acceptor Learner | | | | | | | X-------->| | | | | | Request | X--------->|->|->| | | Prepare(1) | | | | ! | | !! FAIL !! | |<---------X--X | | Promise(1,{null,null, null}) | X--------->|->| | | Accept!(1,V) | |<---------X--X--------->|->| Accepted(1,V) |<---------------------------------X--X Response | | | | | |
システムには3つのアクセプターノードがあるため、この場合のクォーラムは2つなので、そのうちの1つが失敗する可能性があります



学習者の失敗： 

 Client Proposer Acceptor Learner | | | | | | | X-------->| | | | | | Request | X--------->|->|->| | | Prepare(1) | |<---------X--X--X | | Promise(1,{null,null,null}) | X--------->|->|->| | | Accept!(1,V) | |<---------X--X--X------>|->| Accepted(1,V) | | | | | | ! !! FAIL !! |<---------------------------------X Response | | | | | |


失敗の提案者： 

 Client Proposer Acceptor Learner | | | | | | | X----->| | | | | | Request | X------------>|->|->| | | Prepare(1) | |<------------X--X--X | | Promise(1,{null, null, null}) | | | | | | | | | | | | | | !! Leader fails during broadcast !! | X------------>| | | | | Accept!(1,Va) | ! | | | | | | | | | | | | !! NEW LEADER !! | X--------->|->|->| | | Prepare(2) | |<---------X--X--X | | Promise(2,{null, null, null}) | X--------->|->|->| | | Accept!(2,V) | |<---------X--X--X------>|->| Accepted(2,V) |<---------------------------------X--X Response | | | | | | |


提案者に障害が発生した場合、システムは新しい提案者を選択する必要があります。通常は、タイムアウトが経過してから古い提案者が戻るのを待って投票することによって行われます。 新しい提案者を選択した後、古い提案者が生き返った場合、リーダー間で競合が発生し、システムのループにつながる可能性があります。 

 Client Leader Acceptor Learner | | | | | | | X----->| | | | | | Request | X------------>|->|->| | | Prepare(1) | |<------------X--X--X | | Promise(1,{null,null,null}) | ! | | | | | !! LEADER FAILS | | | | | | | !! NEW LEADER (knows last number was 1) | X--------->|->|->| | | Prepare(2) | |<---------X--X--X | | Promise(2,{null,null,null}) | | | | | | | | !! OLD LEADER recovers | | | | | | | | !! OLD LEADER tries 2, denied | X------------>|->|->| | | Prepare(2) | |<------------X--X--X | | Nack(2) | | | | | | | | !! OLD LEADER tries 3 | X------------>|->|->| | | Prepare(3) | |<------------X--X--X | | Promise(3,{null,null,null}) | | | | | | | | !! NEW LEADER proposes, denied | | X--------->|->|->| | | Accept!(2,Va) | | |<---------X--X--X | | Nack(3) | | | | | | | | !! NEW LEADER tries 4 | | X--------->|->|->| | | Prepare(4) | | |<---------X--X--X | | Promise(4,{null,null,null}) | | | | | | | | !! OLD LEADER proposes, denied | X------------>|->|->| | | Accept!(3,Vb) | |<------------X--X--X | | Nack(4) | | | | | | | | ... and so on ...
これを防ぐために、アルゴリズムの実際の実装では、各提案者にシリアル番号があり、新しい提案者が選択されると、この番号が1つ増えます。 アクセプターはいずれも、古いプロポーザルからのメッセージを受け入れません。



実装の例として、 githubリポジトリの 1つを少し変更したpythonコードを提供します 。 

 class Proposer (object): # 1a.    proposal_id (     "N") #   ""  acceptor def prepare(self): self.promises_rcvd = 0 self.proposal_id = self.next_proposal_number self.next_proposal_number += 1 self.messenger.send_prepare(self.proposal_id) # 2a.  "".      - .   "" #    acceptor  -      . #    ""  ,   "" def recv_promise(self, proposal_id, prev_accepted_id, prev_accepted_value): if proposal_id != self.proposal_id: return if prev_accepted_id > self.last_accepted_id: self.last_accepted_id = prev_accepted_id if prev_accepted_value is not None: self.proposed_value = prev_accepted_value self.promises_rcvd += 1 if self.promises_rcvd == self.quorum_size: if self.proposed_value is not None: self.messenger.send_accept(self.proposal_id, self.proposed_value) class Acceptor (object): # 1b. Acceptor  ""  proposer.  ,       , #     .        ,  #        (  )  "" def recv_prepare(self, proposal_id): if proposal_id == self.promised_id: self.messenger.send_promise(proposal_id, self.accepted_id, self.accepted_value) elif proposal_id > self.promised_id: self.promised_id = proposal_id self.messenger.send_promise(proposal_id, self.accepted_id, self.accepted_value) # 2b.   "".          ,  #         "" def recv_accept_request(self, from_uid, proposal_id, value): if proposal_id >= self.promised_id: self.promised_id = proposal_id self.accepted_id = proposal_id self.accepted_value = value self.messenger.send_accepted(proposal_id, self.accepted_value) class Learner (object): # 3. Learner   "",        def recv_accepted(self, from_uid, proposal_id, accepted_value): self.final_value = accepted_value self.messenger.on_resolution( proposal_id, accepted_value )


参照：



More articles:


All Articles