Alibaba Cloud 第2回インタビュー: Zookeeper 一貫性アルゴリズム

[[424686]]

前回、私は後輩たちとSpringに関するいくつかの知識ポイントについて話しました。彼らはとても喜んでいました。しかし、前回、ある後輩が私にメッセージを残し、面接に行ったときに面接官から混乱して不安になるような質問をされたと伝えてきました。

Zookeeper を使用したことがありますか? 登録センターとして CP をどのように確保しますか?

後輩たちの信頼に応えるべく、Zookeeper における一貫性選出アルゴリズム Paxos アルゴリズムについて詳しくお話しします。

CAPとは何ですか?

CAP 理論は、分散システムでは、一貫性、可用性、パーティション耐性という 3 つの基本要件を同時に満たすことは不可能であり、最大でもそのうちの 2 つしか満たすことができないということを意味します。

一貫性: データは異なるコピー間で一貫性があり、データが更新された後もコピーは一貫した状態のままです。
可用性: システムによって提供されるサービスは常に利用可能である必要があり、システムへの各要求は設定された時間内に通常の結果を返す必要があります。
パーティション耐性: 分散システムでネットワークパーティション障害が発生した場合でも、ネットワーク環境全体が完全に麻痺しない限り、一貫性と可用性を満たすサービスを外部に提供できる必要があります。

3つの2の原則とは何ですか?

分散システムの場合、CAP 原則では、P を保証する必要があります。パーティション耐性がなければ、システムは脆弱になります。ただし、一貫性や可用性を同時に保証することはできません。現在の分散システムでは、一貫性が満たされると可用性が必然的に失われ、可用性が満たされると一貫性が必然的に失われます。したがって、分散システムの CAP 原則は、3 対 2 原則である AP または CP のいずれかを満たす必要があります。

Zookeeper と Eureka の違いは何ですか?

Zookeeper は CP 原則に従います。これにより、一貫性は確保されますが、可用性は失われます。これは、リーダーがダウンすると、zk クラスターがすぐに新しいリーダーを選出しますが、選出プロセスが麻痺するという事実に反映されています。したがって、可用性を満たしていません。
Eureka は、高可用性を保証し、1 回の実行で失われる AP 原則に従います。各サーバー間にはハートビート検出メカニズムがあり、各サーバーはハートビートメカニズムを介して読み取りと書き込みを行い、データ共有同期を完了することができます。そのため、マシンがダウンしても他のマシンは正常に動作しますが、ダウンしたマシンはこの時点でデータ共有同期を実行していない可能性があるため、一貫性が満たされません。

話を元に戻しましょう。ここまでは基本的な部分についてお話しました。それでは早速本文に移りましょう!!!

Paxosアルゴリズム

Paxos アルゴリズムは、1990 年に Leslie Lamport によって提案されたメッセージパッシングに基づく、耐障害性に優れたコンセンサスアルゴリズムです。 Google Chubby の作者 Mike Burrows 氏はかつて、世界には一貫性アルゴリズムが 1 つしか存在せず、それが Paxos であると述べました。他のすべての一貫性アルゴリズムは、Paxos アルゴリズムの不完全なバージョンです。
Paxos アルゴリズムはよく知られているあまり知られていないアルゴリズムであり、エンジニアリングで実装するのも非常に困難です。
したがって、Paxos アルゴリズムは主に、分散システムで投票に基づいて合意に達する方法を解決するために使用されます。

アルゴリズムの事前理解

まず理解する必要があるのは、アルゴリズムの3つの役割です

提案者
アクセプター
学習者

提案に対して複数の意思決定者 (Acceptor) が存在する場合がありますが、クラスター内に複数の提案者 (Proposer) が存在する場合もあり、異なる提案者 (Proposer) が異なる提案を提出します。

Paxos アルゴリズムの特徴:

提案がない場合、提案は選択されません。
提案を行う際、各提案者はまず、グローバルに一意で増加する提案番号 N、つまりクラスター全体で一意の番号 N を取得し、次に行う提案にその番号を割り当てます。 (Zookeeper では、epoch と xid で構成される zxid です)
提案を承認した後、各投票者は提案番号 N をローカルに記録します。このように、各投票者が保存した承認済み提案の中で、最大の番号を持つ提案が存在し、それが maxN であると想定されます。各投票者は、ローカル maxN より大きい数値の提案のみを受け入れます。
多数の提案の中から選択できるのは 1 つの提案のみです。
提案が選択されると、他のサーバーは提案をローカルサーバーに積極的に同期 (学習) します。

Paxos アルゴリズムの選出プロセス全体は、2 つの段階で理解できます。

フェーズ1

この段階は主に提案書を送るための準備段階である

プロポーザーは番号 N の提案を送信する準備をしているため、最初にすべてのアクセプターに prepare(N) 要求を送信して、クラスターが番号 N の提案をサポートしているかどうかをテストします。
各意思決定者 (Acceptor) は、これまでに受け入れた提案の最大数 maxN を保存します。投票者は別のホストから prepare(N) 要求を受信すると、N の値と maxN の値を比較します。
N が maxN より小さい場合、提案は古く、現在の投票者は応答しないことで準備要求を拒否することを意味します。
N が maxN より大きい場合、提案は受け入れられることを意味します。現在の投票者はまず N を記録し、これまでに受け入れた最大の数値である提案 (Proposal (myid, maxN, value)) を提案者にフィードバックして、提案者に提案を支持する意思を示します。最初のパラメータ myid は投票者 Acceptor の識別 ID を表し、2 番目のパラメータはこれまでに承認された提案の最大数 maxN を表し、3 番目のパラメータは提案の実際のコンテンツ値を表します。
現在の投票者が（最初の初期化時に）提案を承認していない場合、Proposal(myid,null,null) が提案者にフィードバックされます。
現段階では、N は maxN と等しくなることはできません。これはNの生成メカニズムによって決まります。 N の値を取得するには、同期ロック方式を使用して元の値を 1 増やす必要があります。

フェーズ2

現在の段階は、実際の送受信段階であり、Accept 段階とも呼ばれます。

提案者が prepare(N) を送信したときに、決定者 (Accepters) の半数以上からフィードバックを受け取った場合、提案者は実際の提案 Proposal(N, value) をすべての投票者に送信します。
決定者（アクセプター）は、提案者から送信された提案（N、値）を受信すると、受け入れた提案の最大数maxNと記録した準備の最大数を取り出し、Nとそれらを比較します。Nがこれら2つの数以上であれば、現在の投票者は提案を受け入れ、提案者にフィードバックします。 N がこれら 2 つの数値より小さい場合、意思決定者は応答せずに提案を拒否します。
提案者が投票者の半数以上から承認フィードバックを受け取らなかった場合は、準備フェーズに戻り、提案番号を増やして、準備リクエストを再送信します。提案者がフィードバックの半分以上を受け取った場合、次の 2 種類の情報をブロードキャストします。
提案を受け入れた有権者に「実行可能なデータ同期信号」を送信し、受け取った提案を実行させる。

承認フィードバックを送信していない投票者には「提案 + 実行可能データ同期信号」を送信します。つまり、提案を受け取ったらすぐに実行できるようにします。

これを見ると、多くの後輩は困惑するかもしれません。一体何なのでしょう? 理解を深め、プロセス全体をより明確にするために、例を挙げてみましょう!!!

リーダーを選択するためのホストサーバーが 3 つあると仮定します (さらに多くのサーバーを選択することもできますが、便宜上および理解しやすいように、ここでは少数を選択します)。したがって、これら 3 つのホストは、それぞれ提案者 (Proposer)、意思決定者 (Acceptor)、学習者 (大衆) の役割を果たします。

そこで、選挙のシミュレーションを開始し、3 つのサーバーが N (グローバルに一意で増加する提案番号 N) の値を取得し始めるとします。この時点で、serverOne (ホスト 1) は ProposerOne (提案者 1) に対応し、serverTwo (ホスト 2) は ProposerTwo (提案者 2) に対応し、serverThree (ホスト 3) は ProposerThree (提案者 3) に対応します。

プロセス全体をよりシンプルかつ明確にし、プロセス中に理解しやすくします。初期N値はServerOne(2)、ServerTwo(1)、ServerThree(3)に具体的に設定されており、それらはすべて意思決定者(Acceptor)に提案を送信して投票します。

名詞分析
提案: 提案者から意思決定者に送信される中間データのパッケージは、提案と呼ばれます。

同時に、各提案者は 2 人の意思決定者 (受け入れ者) に提案メッセージを送信します。つまり、次のようになります:

ProposerOne (提案者 1) は、AcceptorOne (意思決定者 1) と AcceptorTwo (意思決定者 2) にリクエストを送信します。

ProposerTwo (提案者 2) から AcceptorTwo (意思決定者 2) および AcceptorThree (意思決定者 3) へ、

ProposerThree（提案者3）からAcceptorTwo（意思決定者2）とAcceptorThree（意思決定者3）へ、

提案メッセージを送信します。プロセス構造を簡素化するために、提案は 2 つに送信されますが、これですでに投票数の半分を超えています。もちろん、より多くのホストを選択して、より多くの提案を送信することもできますが、プロセスはより複雑になり、理解するのが少し難しくなります。重要なのは、投票数の半数を超えなければならないということです。

グラフ全体は次のようになります。

上の図によると、最初の段階が始まります

上記で想定したプロセスに従って実行プロセスを開始します

ProposerOne (提案者 1) から AcceptorOne (意思決定者 1) および AcceptorTwo (意思決定者 2)

AcceptorOne（意思決定者1）とAcceptorTwo（意思決定者2）は、ProposerOne（提案者1）からの提案を初めて受け取ります。提案を受け取るのは初めてなので、最大N値はローカルに保存されていないため、両方ともProposerOne（提案者1）からの提案を受け入れます。
したがって、AcceptorOne (意思決定者 1) と AcceptorTwo (意思決定者 2) は、ProposerOne (提案者 1) に戻って、提案に同意することを私に通知することを提案します。
同時に、AcceptorOne（意思決定者 1）と AcceptorTwo（意思決定者 2）は、現在受信した最大提案数 N が 2 であり、ローカルに保存されているため、2 未満の他の N 値を受信する場合は提案に応答しません。
ProposerOne は半数以上の回答を受け取ったため、提案は承認されました。
現時点では：
AcceptorOne（意思決定者1）のローカルN値は2
AcceptorTwo（意思決定者2）のローカルN値は2です
AcceptorThree（意思決定者3）のローカルN値はnullです

ProposerTwo (提案者 2) から AcceptorTwo (意思決定者 2) および AcceptorThree (意思決定者 3)

AcceptorTwo (意思決定者 2) と AcceptorThree (意思決定者 3) が ProposerTwo (提案者 2) からの提案を受信したとき。 AcceptorTwo（意思決定者2）は以前にProposerOneの提案を受け入れているため、ローカルN値にはすでに2が格納されている。
ProposerTwo の N 値が 1 の場合、ローカルに保存されている最大 N 値より小さいため、承認されず、ProposerTwo は返信されません。
AcceptorThree が提案を受信するのは今回が初めてであり、最大 N 値がないため、提案に同意し、現在の提案を返し、ローカル N 値を更新します。
最終的に、ProposerTwo (提案者 2) は AcceptorThree (意思決定者 3) から承認フィードバックのみを受け取りましたが、選択肢の半分を超えなかったため、承認されませんでした。
現時点では：
AcceptorOne（意思決定者1）のローカルN値は2
AcceptorTwo（意思決定者2）のローカルN値は2です
AcceptorThree（意思決定者3）のローカルN値は1です

ProposerThree (提案者 3) から AcceptorTwo (意思決定者 2) および AcceptorThree (意思決定者 3)

AcceptorTwo (意思決定者 2) と AcceptorThree (意思決定者 3) が ProposerThree (提案者 3) からの提案を受信したとき。なぜなら
AcceptorTwo と AcceptorThree は両方とも提案を受け取りました。そのため、AcceptorTwo が ProposerThree の提案を受け取ると、そのローカル N 値 2 は ProposerThree の N 値 3 より小さいため、提案は承認されます。
AcceptorThree（意思決定者3）は、以前にローカルで受信した最大値が1であるため提案を受け入れ、N値を3に更新します。
最終的に、ProposerThree は承認フィードバックの半分以上を受け取ったため、承認されました。
現時点では：
AcceptorOne（意思決定者1）のローカルN値は2
AcceptorTwo（意思決定者2）のローカルN値は3です
AcceptorThree（意思決定者3）のローカルN値は3です

なぜなら、ProposerTwo (提案者 2) が AcceptorTwo (意思決定者 2) と AcceptorThree (意思決定者 3) に提案を行ったときに、半数以上の票を獲得できなかったからです。したがって、最大の N 値 (グローバルに一意で、増加する提案番号 N) が再度取得されます。この時点で、ProposerTwo (提案者 2) によってローカルに取得された N 値は 4 であるため、別の投票ラウンドが開始されます。

AcceptorTwo (意思決定者 2) と AcceptorThree (意思決定者 3) が ProposerTwo (提案者 2) からの提案を再度受信します。 AcceptorTwo と AcceptorThree によってローカルに保存される最大 N 値は、ProposerTwo の現在の N 値 4 よりも小さいため、すべての提案が返され、ローカル N 値が更新されます。
ProposerTwo の N 値が 1 の場合、ローカルに保存されている最大 N 値より小さいため、承認されず、ProposerTwo は返信されません。
最終的に、ProposerTwo は承認フィードバックの半分以上を受け取ったため、承認されました。
現時点では：
AcceptorOne（意思決定者1）のローカルN値は2
AcceptorTwo（意思決定者2）のローカルN値は4です
AcceptorThree（意思決定者3）のローカルN値は4です

この時点で、作業の最初の段階は完了です。プロセス全体はテキスト中心であり、複数回読み取る必要があります。同時に、次のようなフローチャートも作成しました。

第一段階は完了したので、次のステップは間違いなく第二段階のプロセスです。

同時に、第 2 段階全体は 2 つの部分として理解できます。最初の部分は提案の正式な提出であり、2 番目の部分は投票段階です。

第一段階終了後に得られた結果は次のとおりです。

提案者

ProposerOne（提案者1）のローカルN値は2です
ProposerTwo (提案者2) のローカルN値は4です
ProposerThree（提案者3）のローカルN値は3です

アクセプター

AcceptorOne（意思決定者1）のローカルN値は2
AcceptorTwo（意思決定者2）のローカルN値は4です
AcceptorThree（意思決定者3）のローカルN値は4です

最初のブロック:

ProposerOne (提案者 1) は、AcceptorOne (意思決定者 1) と AcceptorTwo (意思決定者 2) に正式に提案を送信します。第 1 段階の結果から、AcceptorOne (意思決定者 1) のみが賛成票を投じ、AcceptorTwo (意思決定者 2) はローカル N 値未満であったため承認されなかったことがわかります。
ProposerTwo (提案者 2) は、提案を AcceptorTwo (意思決定者 2) と AcceptorThree (意思決定者 3) に正式に送信します。同様に、第 1 段階の結果によると、両方の意思決定者が承認したため、投票の半分以上が投じられました。
ProposerThree（提案者3）は、AcceptorTwo（意思決定者2）とAcceptorThree（意思決定者3）に正式に提案を送信します。同様に、第1段階の結果から、両方の意思決定者が承認されなかったことがわかります。

2番目のブロック:

上記の最初の結果から、ProposerTwo だけが投票の半分を獲得したことがわかります。そのため、ProposerTwo はすぐにリーダーになることができます。この時点で、選挙状態は終了し、つまり、ProposerTwo (提案者 2) がすべての学習者にブロードキャストして、データを同期するように通知します。データが同期されると、サーバークラスター全体が正常に動作します。

要約する

Paxos アルゴリズムのプロセス全体を理解するのは、まだ比較的難しいです。プロセスを明確に説明するために、最も簡単な例を使用します。より多くのマシンがより多くの提案を行うこともできます。しかし、プロセス全体を理解するのはより困難です。

Paxos アルゴリズムを理解するには、上記の 2 つの段階で理解する必要があります。第一段階で何が行われ、どのような結果が得られたか。第一段階の結果に基づいて第二段階でどのような選挙プロセスが実施されるかは、誰もが考えなければならない重要なポイントです。

ここで皆さんにお伝えしたいのは、主に Paxos アルゴリズムの選択プロセスです。Fast Paxos、EPaxos など、他にも最適化されたバージョンが多数あります。

動物園の飼育員

Zookeeper の選択アルゴリズムでは Fast Paxos アルゴリズムを使用します。Fast Paxos を使用する理由は何ですか?

Fast Paxos アルゴリズムは Paxos の最適化バージョンであり、Paxos アルゴリズムのライブロック問題を解決し、各スレッドが一意の N 値を取得することを保証します。

ZAB (Zookeeper Atomic Broadcast) アトミックブロードキャストプロトコル

ZAB は実際には上記のアルゴリズムの実装であるため、Zookeeper は分散データの一貫性を実現するために ZAB に依存しています。

ZooKeeperではリーダーマシンとしてサーバーマシンが1台だけなので、クライアントがマシン上のノードに接続すると

クライアントがデータの読み取り要求を送信すると、現在接続されているマシンノードは保存したデータを返します。
クライアントがデータ書き込み要求を送信すると、まず現在接続されているノードがリーダーノードであるかどうかを確認します。リーダーノードでない場合は、リーダーマシンのノードに転送され、リーダーマシンによって書き込まれ、その後、他のノードにデータを同期するように通知するためにブロードキャストされます。

ZAB の 3 つの役割

リーダー: ZK クラスターのボスであり、データを書き込むことができる唯一のマシンです。
フォロワー: ZK クラスター内で活動し、一定の役職を持つ人。データの読み取りのみが可能で、リーダーマシンに障害が発生した場合に選挙に参加できます。
オブザーバー: 最年少の労働者。データの読み取りのみ可能です。リーダーのマシンがクラッシュしても、彼には関係ありません。選挙や投票に参加することはできません。

ZABの3つの重要なデータ

Zxid: ZooKeeper 内のトランザクション ID で、合計 64 ビットの長さを持つ Long 型データです。 2 つの部分があります。最初の 32 ビットはエポックで、次の 32 ビットは xid です。
エポック: 各リーダーにはこの値があり、現在のリーダーが獲得した最大のN値を示します。これは「時代」として理解できます。
Xid: トランザクション ID。ZooKeeper クラスター (監視メカニズム) によって現在送信されているトランザクション ID を示します。これにより、選出プロセス後にトランザクションが繰り返し実行されたり、省略されたりするなどの特別な状況が発生しなくなります。

Zookeeper にはセッション、Znode、ウォッチャーメカニズム、ACL、3 つの状態モード、Zookeeper が分散トランザクションロックを実装する方法など、多くの要素が含まれているため、ここでは Zookeeper に関するいくつかの知識ポイントを共有します。一度に全員と話すことはできません。

今回は、主に、Zookeeper の一貫性アルゴリズムがどのように保証されているかを、後輩たちに明確に理解してもらいたいと思います。