Zookeeper を簡単に説明する (パート 2) Zookeeper に基づく分散ロックとリーダー選出

1. Zookeeperの機能

1. Zookeeperノードタイプ

上記の「Zookeeper アーキテクチャと FastLeaderElection メカニズム」で説明したように、Zookeeper は Linux ファイルシステムに似たツリー構造を提供します。ツリー構造内の各ノードは znode と呼ばれ、次の 2 つの次元に分類できます。

（１）持続か短命か

Persist ノードが作成されると、誤って失われることはなく、すべてのサーバーが再起動されても存在し続けます。各 Persist ノードには、データノードと子ノードの両方を含めることができます。
エフェメラルノードは、それを作成したクライアントとサーバー間のセッションが終了すると自動的に削除されます。サーバーの再起動によりセッションが終了するため、Ephemeralタイプのznodeもこの時点で自動的に削除されます。

（２）シーケンスと非シーケンス

非シーケンスノード: 複数のクライアントが同時に同じ非シーケンスノードを作成すると、正常に作成できるのは 1 つだけであり、その他は失敗します。作成されたノードの名前は、作成時に指定されたノード名とまったく同じです。
シーケンスノード: 作成されたノード名には、指定された名前の後に 10 桁の 10 進シーケンス番号が付きます。複数のクライアントが同じ名前のノードを作成する場合、それらはすべて正常に作成されますが、シーケンス番号は異なります。

2. Zookeeper のセマンティック保証

Zookeeper はシンプルで効率的であり、次のセマンティック保証を提供するため、これらの機能を使用して複雑なサービスを提供することができます。

順次クライアントによって開始された更新は、送信された順序で Zookeeper に適用されます。
アトミック更新操作は、中間状態なしで成功するか失敗するかのいずれかになります。
単一のシステムイメージクライアントは、どのサーバーに接続しても、まったく同じシステムイメージ (つまり、まったく同じツリー構造) を表示できます。注: 上記の「Zookeeper アーキテクチャと FastLeaderElection メカニズム」で紹介されている ZAB プロトコルによれば、書き込み操作では、更新がすべてのフォロワーによって即座に確認されることは保証されません。したがって、一部のフォロワーを通じてデータを読み取っても、最新のデータを読み取ることができるとは限らず、一部のフォロワーとリーダーは最新のデータを読み取ることができます。単一のシステムイメージを確保する必要がある場合は、読み取り操作の前に同期メソッドを使用します。
信頼性: 更新が受け入れられると、他の更新によって上書きされない限り、誤って失われることはありません。
最終的に一貫性のある書き込みは、最終的に（すぐにではなく）クライアントに表示されます。

3. 動物園の飼育係の監視機構

Zookeeper のすべての読み取り操作にはウォッチを併用できます。対応するデータが変更されると、ウォッチがトリガーされます。時計には以下の機能があります

アクティブプッシュウォッチがトリガーされると、Zookeeper サーバーはクライアントのポーリングを必要とせずに更新をクライアントにアクティブにプッシュします。
ワンタイムデータが変更された場合、ウォッチは 1 回だけトリガーされます。クライアントが後続の更新について通知を受け取りたい場合は、ウォッチがトリガーされた後にウォッチを再登録する必要があります。
可視性クライアントが読み取り要求に Watch を添付し、Watch がトリガーされている間にデータを再度読み取ると、クライアントは Watch メッセージを受信する前に更新されたデータを確実に確認できなくなります。つまり、更新通知は更新結果に先行します。
順序性複数の更新によって複数のウォッチがトリガーされる場合、ウォッチがトリガーされる順序は更新の順序と一致します。

2. 分散ロックとリーダー選出のポイント

1. 最大で1人がロックを獲得/リーダーになる

分散ロック (ここでは特に排他ロック) の場合、いつでも最大 1 つのプロセス (単一プロセス内のロックの場合は 1 つのスレッド) がロックを取得できます。

リーダー選挙では、いつでも最大 1 人がリーダーとして選出されます。そうしないと、スプリットブレインが発生します。

2. 再入場をロックする/自分がリーダーであることを確認する

分散ロックの場合、ロックを取得したプロセスがロックを解放する前に再度ロックを取得できること、つまりロックの再入可能性を保証する必要があります。

リーダー選出のためには、リーダーはリーダーシップを獲得したこと、つまりリーダーであることの確認ができる必要があります。

3. ロックを解除する/リーダーシップを放棄する

ロック取得者は取得したロックを正しく解放でき、ロックを取得したプロセスがクラッシュした場合は、他の競合プロセスがロックを取得できるようにロックが自動的に解放され、デッドロック状態が回避される必要があります。

リーダーは自発的にリーダーシップを放棄でき、リーダーがいるプロセスがクラッシュした場合は、リーダーシップが自動的に解放され、他の参加者が再びリーダーシップを競い合い、リーダーがいない状態にならないようにする必要があります。

4. 認識ロックの解除/リーダーシップの放棄

ロックを取得したパーティがロックを解除すると、そのロックを競合する他のパーティはロックの解除を感知し、再度ロックの取得を試みる必要があります。

元のリーダーがリーダーシップを放棄すると、他の参加者はその出来事を感知し、選挙プロセスを再開できるはずです。

5. 不公平な党首選挙

上記の側面から、分散ロックとリーダー選挙の技術的なポイントは非常に似ており、実際にそれらの実装メカニズムも似ていることがわかります。この章では、リーダー選挙を例に挙げて、2 つの実装原則を説明します。分散ロックの実装原理はほぼ同じです。

6. マスター選択プロセス

次の図に示すように、3 つの Zookeeper クライアントが同時にリーダーの座を競っていると仮定します。これら 3 つのクライアントは、Ephemeral ノードと Non-sequence ノードを Zookeeper クラスターに同時に登録し、パスはすべて /zkroot/leader になります (エンジニアリングの実践では、パス名はカスタマイズできます)。

上図に示すように、非シーケンスノードであるため、3 つのクライアントのうち 1 つだけが正常に作成され、他のノードの作成は失敗します。この時点で、正常に作成されたクライアント (上図のクライアント 1) がリーダーとして正常に実行されます。他のクライアント (上図のクライアント 2 とクライアント 3) はフォロワーになります。

7. リーダーシップを放棄する

リーダーがリーダーシップを放棄するつもりなら、/zkroot/leader ノードを削除するだけです。

リーダープロセスが予期せずクラッシュした場合、リーダープロセスと Zookeeper 間のセッションが終了し、ノードは一時ノードであるため自動的に削除されます。

この時点で、/zkroot/leader ノードは存在しなくなります。選挙に参加している他のクライアントにとっては、前リーダーがリーダーシップを放棄したことになります。

8. リーダーシップの放棄の認識

上図からわかるように、ノードの作成に失敗したノードは Follower になるだけでなく、/zkroot/leader に Watch も登録されます。リーダーがリーダーシップを放棄すると、つまりノードが削除されると、すべてのフォロワーに通知が届きます。

9. 再選

古いリーダーがリーダーシップを放棄したことを感知すると、すべてのフォロワーは、次の図に示すように、新しいラウンドのリーダーシップ選挙を開始できます。

上の図からわかるように

新しいリーダー選挙の方法は、最初のリーダー選挙の方法とまったく同じです。どちらもノード作成要求を開始します。作成が成功すると、リーダーになります。それ以外の場合は、フォロワーになり、フォロワーがノードを監視します。
新たな選挙の結果は予測できず、第 1 回選挙の順位とは何の関係もありません。このため、この制度は不公平なモデルと呼ばれています。

10. 不公平モデルの概要

不公平モードは実装が簡単で、各ラウンドの選挙方法はまったく同じです。
競合相手が少ないほど効率が高くなります。各フォロワーは、ノードが削除される時刻がまったく同じではないことを Watch を通じて感知します。 1 人のフォロワーが通知を受け、選挙を開始する限り、その時点で新しいリーダーが選出されることが保証されます。
Zookeeper クラスターの負荷が大きいため、スケーラビリティが低くなります。数万のクライアントが選挙に参加すると、数万の書き込み要求が同時に Zookeper に送信されることになります。「Zookeeper Architecture」の記事で説明されているように、Zookeeper にはシングルポイント書き込みの問題があり、書き込みパフォーマンスは高くありません。同時に、リーダーがリーダーシップを放棄すると、Zookeeper は数万のフォロワーに同時に通知する必要があり、システムに大きな負荷がかかります。

3. 公正なリーダー選挙

1. マスター選択プロセス

下の図に示すように、公平なリーダーシップ選出では、各クライアントが /zkroot/leader ノードを作成し、そのタイプは Ephemeral および Sequence になります。

シーケンス型ノードなので、上図の 3 つのクライアントはすべて正常に作成されていますが、シーケンス番号が異なります。この時点で、各クライアントは、正常に作成したノードのシリアル番号が現時点で最小であるかどうかを判断します。はいの場合、クライアントはリーダーであり、そうでない場合はフォロワーです。

上図では、クライアント 1 が作成したノード番号は 1、クライアント 2 が作成したノード番号は 2、クライアント 3 が作成したノード番号は 3 です。最小シーケンス番号は 1 であり、ノードはクライアント 1 によって作成されたため、クライアント 1 がリーダーです。

2. リーダーシップを放棄する

リーダーが自発的にリーダーシップを放棄する場合は、リーダーが作成したノードを削除するだけです。

リーダーが配置されているプロセスが予期せずクラッシュした場合、リーダーと Zookeeper 間のセッションは終了します。作成されたノードは Ephemeral タイプであるため、ノードは自動的に削除されます。

3. リーダーシップの放棄の認識

不公平モードとは異なり、各フォロワーはリーダーによって作成されたノードを監視するのではなく、自分のシーケンス番号よりもわずかに小さいシーケンス番号を持つノードを監視します。

上図では、ノードは合計 1、2、3 の 3 つあり、クライアント 2 は /zkroot/leader1 を監視し、クライアント 3 は /zkroot/leader2 を監視します。 (注: シリアル番号は 1 桁ではなく 10 桁である必要があります。便宜上、ここでは 1 桁の数字を使用しています)

リーダーがダウンすると、/zkroot/leader1 が削除され、クライアント 2 に通知されます。この時点では、クライアント 3 は /zkroot/leader2 を監視しているため通知されません。

4. 再選

クライアント 2 は、/zkroot/leader1 が削除されたという通知を受信した後、すぐに新しいリーダーにはなりません。代わりに、まずシーケンス番号 2 が現在の最小のシーケンス番号であるかどうかを判断します。このシナリオでは、そのシーケンス番号は確かに最小です。したがって、クライアント 2 が新しいリーダーになります。

クライアント 1 がリーダーシップを放棄する前にクライアント 2 がクラッシュした場合、クライアント 3 に通知されることに注意することが重要です。この時点では、クライアント 3 はすぐにリーダーにはなりませんが、まずそのシーケンス番号 3 が現在の最小シーケンス番号であるかどうかを判断する必要があります。当然、クライアント 1 によって作成された /zkroot/leader1 がまだ存在するため、クライアント 3 は新しいリーダーにはならず、クライアント 2 のシーケンス番号 2 の前のシーケンス番号 (1) のウォッチを作成します。このプロセスを下の図に示します。

5. 公平性モデルのまとめ