ZooKeeper レシピとソリューション

• ZooKeeper を使用した上位レベルの構成要素の作成ガイド
  • エラー処理に関する重要な注意点
  • すぐに使えるアプリケーション：名前サービス、構成、グループメンバーシップ
  • バリア
    • 二重バリア
  • キュー
    • 優先度付きキュー
  • ロック
    • 回復可能なエラーとGUID
    • 共有ロック
    • 取り消し可能な共有ロック
  • 二段階コミット
  • リーダー選出

ZooKeeper を使用した上位レベルの構成要素の作成ガイド

この記事では、ZooKeeper を使用して高階関数を実装するためのガイドラインを示します。これらはすべてクライアント側で実装された規約であり、ZooKeeperからの特別なサポートは必要ありません。コミュニティがこれらの規約をクライアント側のライブラリにまとめ、使いやすさと標準化を促進することを期待しています。

ZooKeeperの最も興味深い点の1つは、ZooKeeperが *非同期* 通知を使用しているにもかかわらず、キューやロックなどの *同期* 一貫性プリミティブを構築するために使用できることです。ご覧のように、これはZooKeeperが更新に全体的な順序を課し、この順序を公開するメカニズムを持っているため可能です。

以下のレシピは、ベストプラクティスを採用しようと試みています。特に、ポーリング、タイマー、またはその他の「群れ効果」を引き起こし、トラフィックのバーストを引き起こしてスケーラビリティを制限するものを避けています。

ここに含まれていない、想像できる多くの便利な関数があります。取り消し可能な読み書き優先度ロックはその1つの例です。そして、ここで言及されている構成要素の一部（特にロック）は、イベントハンドルやキューなどの他の構成要素の方が同じ機能を実行するためのより実用的な手段である場合でも、特定の点を示しています。一般的に、このセクションの例は思考を刺激するように設計されています。

エラー処理に関する重要な注意点

レシピを実装する際には、回復可能な例外を処理する必要があります（FAQを参照）。特に、いくつかのレシピはシーケンシャルエフェメラルノードを使用しています。シーケンシャルエフェメラルノードを作成する際、サーバーでcreate（）が成功するが、ノードの名前をクライアントに返す前にサーバーがクラッシュするというエラーケースがあります。クライアントが再接続すると、セッションはまだ有効であり、そのためノードは削除されません。これは、クライアントが自分のノードが作成されたかどうかを知ることは困難であることを意味します。以下のレシピには、これを処理するための対策が含まれています。

すぐに使えるアプリケーション：名前サービス、構成、グループメンバーシップ

名前サービスと構成は、ZooKeeperの主要なアプリケーションの2つです。これら2つの機能は、ZooKeeper APIによって直接提供されます。

ZooKeeperによって直接提供されるもう1つの機能は、 *グループメンバーシップ* です。グループはノードによって表されます。グループのメンバーは、グループノードの下にエフェメラルノードを作成します。異常終了したメンバーのノードは、ZooKeeperが障害を検出すると自動的に削除されます。

バリア

分散システムは、条件が満たされるまでノードのセットの処理をブロックし、その時点ですべてのノードが処理を進めることができるように、 *バリア* を使用します。バリアは、バリアノードを指定することでZooKeeperで実装されます。バリアノードが存在する場合は、バリアが有効です。擬似コードを次に示します。

1. クライアントは、 *watch* をtrueに設定して、ZooKeeper APIの **exists（）** 関数をバリアノードで呼び出します。
2. **exists（）** がfalseを返す場合、バリアはなくなっていて、クライアントは処理を進めます。
3. それ以外の場合、**exists（）** がtrueを返す場合、クライアントはバリアノードの監視イベントをZooKeeperから待ちます。
4. 監視イベントがトリガーされると、クライアントは **exists（）** 呼び出しを再発行し、バリアノードが削除されるまで再び待ちます。

二重バリア

二重バリアにより、クライアントは計算の開始と終了を同期させることができます。十分なプロセスがバリアに参加すると、プロセスは計算を開始し、完了したらバリアを離れます。このレシピは、ZooKeeperノードをバリアとして使用する方法を示しています。

このレシピの擬似コードでは、バリアノードを *b* として表します。すべてのクライアントプロセス *p* は、エントリ時にバリアノードに登録し、計算の準備ができたら登録を解除します。ノードは、以下の **Enter** プロシージャを介してバリアノードに登録し、 *x* クライアントプロセスが登録されるまで待機してから計算に進みます。（ここの *x* は、システムに合わせて決定する必要があります。）

エントリ時に、すべてのプロセスはreadyノードを監視し、エフェメラルノードをバリアノードの子として作成します。最後のプロセスを除く各プロセスはバリアに入り、5行目でreadyノードが表示されるのを待ちます。x番目のノード（最後のノード）を作成するプロセスは、子ノードのリストにx個のノードが表示され、readyノードを作成して他のプロセスを起動します。待機中のプロセスは終了する時間になるまでしか起動しないため、待機は効率的です。

終了時には、プロセスのノードがなくなるのを監視しているので、 *ready* などのフラグは使用できません。エフェメラルノードを使用することで、バリアに入った後に失敗したプロセスは、正しいプロセスが完了するのを妨げません。プロセスが終了する準備ができたら、プロセスのノードを削除し、他のすべてのプロセスが同じことをするのを待つ必要があります。

*b*の子としてプロセスノードが残っていない場合、プロセスは終了します。ただし、効率性を上げるために、最も低いプロセスノードをreadyフラグとして使用できます。終了する準備ができている他のすべてのプロセスは、存在する最も低いプロセスノードがなくなるのを監視し、最も低いプロセスの所有者は、他のプロセスノード（単純化のために最も高いものを選択）がなくなるのを監視します。これは、最後のノードを除いて、各ノードの削除時に1つのプロセスだけが起動することを意味します。最後のノードは削除されると全員を起動します。

キュー

分散キューは一般的なデータ構造です。ZooKeeperで分散キューを実装するには、最初にキューを保持するznode（キューノード）を指定します。分散クライアントは、 "queue-"で終わるパス名でcreate（）を呼び出し、create（）呼び出しで *sequence* フラグと *ephemeral* フラグをtrueに設定することで、キューに何かを追加します。 *sequence* フラグが設定されているため、新しいパス名は *path-to-queue-node*/queue-X という形式になり、Xは単調増加数です。キューから削除するクライアントは、ZooKeeperの **getChildren（）** 関数を *watch* をtrueに設定してキューノードで呼び出し、最も小さい番号のノードから処理を開始します。クライアントは、最初の **getChildren（）** 呼び出しから取得したリストを使い果たすまで、別の **getChildren（）** を発行する必要はありません。キューノードに子ノードがない場合、リーダーは監視通知を待ってキューを再度確認します。

注記

ZooKeeperレシピディレクトリには、キューの実装が既に存在します。これはリリースと共に配布されています -- リリースアーティファクトのzookeeper-recipes/zookeeper-recipes-queueディレクトリ。

優先度付きキュー

優先度付きキューを実装するには、汎用キューレシピに2つの簡単な変更を加えるだけです。まず、キューに追加するには、パス名は "queue-YY" で終わるようにし、YYは要素の優先度を表し、数値が小さいほど優先度が高くなります（UNIXと同じです）。次に、キューから削除する際に、クライアントは最新のchildrenリストを使用します。つまり、キューノードの監視通知がトリガーされた場合、クライアントは以前に取得したchildrenリストを無効にします。

ロック

グローバルに同期された、完全に分散されたロック。つまり、任意のスナップショット時点では、2つのクライアントが同じロックを保持していると考えていることはありません。これらはZooKeeperを使用して実装できます。優先度付きキューと同様に、まずロックノードを定義します。

注記

ZooKeeperレシピディレクトリには、ロックの実装が既に存在します。これはリリースと共に配布されています -- リリースアーティファクトのzookeeper-recipes/zookeeper-recipes-lockディレクトリ。

ロックを取得するクライアントは、次の操作を行います。

1. パス名を " *locknode*/guid-lock-" とし、 *sequence* フラグと *ephemeral* フラグを設定して **create（）** を呼び出します。 create（）の結果が失われた場合に備えて、 *guid* が必要です。以下の注記を参照してください。
2. 監視フラグを設定せずに（これは群れ効果を回避するために重要です）、ロックノードで **getChildren（）** を呼び出します。
3. ステップ **1** で作成されたパス名が最も小さいシーケンス番号のサフィックスを持っている場合、クライアントはロックを保持しており、クライアントはプロトコルを終了します。
4. クライアントは、次の最も小さいシーケンス番号を持つロックディレクトリのパスで、監視フラグを設定して **exists（）** を呼び出します。
5. **exists（）** がnullを返す場合、ステップ **2** に進みます。それ以外の場合、ステップ **2** に進む前に、前のステップのパス名の通知を待ちます。

ロック解除プロトコルは非常にシンプルです。ロックを解放するクライアントは、ステップ1で作成したノードを削除するだけです。

いくつか注目すべき点があります。

• ノードの削除は、各ノードが正確に1つのクライアントによって監視されているため、1つのクライアントしか起動しません。このようにして、群れ効果を回避します。

• ポーリングやタイムアウトはありません。

• ロックの実装方法により、ロックの競合の量、ロックの解除、ロックの問題のデバッグなどが容易にわかります。

回復可能なエラーとGUID

• **create（）** を呼び出す際に回復可能なエラーが発生した場合は、クライアントは **getChildren（）** を呼び出して、パス名で使用された *guid* を含むノードを確認する必要があります。これは、（上記で示されている）サーバーでcreate（）が成功するが、新しいノードの名前を返す前にサーバーがクラッシュするというケースを処理します。

共有ロック

ロックプロトコルを少し変更することで、共有ロックを実装できます。

注記

• このレシピでは、多数のクライアントがリードロックを待機しており、最小のシーケンス番号を持つ「write-」ノードが削除されたときにほぼ同時に通知を受け取るため、「群れ効果」が発生する可能性があります。実際、これは有効な動作です。待機しているすべてのリーダークライアントは、ロックを取得しているため解放されるべきです。「群れ効果」とは、実際には1台または少数のマシンしか続行できないのに、「群れ」全体を解放することを指します。

• ノードでのguidの使用方法については、ロックに関する注記を参照してください。

取り消し可能な共有ロック

共有ロックプロトコルのわずかな変更により、共有ロックプロトコルを変更することで、共有ロックを取消可能にすることができます。

リードロックとライトロックの両方のプロトコルの手順**1**では、**create( )**の呼び出し直後に、watchを設定して**getData( )**を呼び出します。クライアントが手順**1**で作成したノードに対して通知をその後受信した場合、そのノードに対してwatchを設定して**getData( )**を再度実行し、「unlock」という文字列を検索します。これは、クライアントがロックを解放する必要があることを示すシグナルです。これは、この共有ロックプロトコルでは、ロックノードに対して**setData()**を呼び出し、そのノードに「unlock」を書き込むことで、ロックを持つクライアントにロックの解放を要求できるためです。

このプロトコルでは、ロック所有者がロックの解放に同意する必要があることに注意してください。このような同意は、ロック所有者がロックを解放する前に何らかの処理を行う必要がある場合に特に重要です。もちろん、プロトコルで、ロック所有者が一定時間内にロックを削除しない場合、ロック解除者がロックノードを削除することを規定することで、「Revocable Shared Locks with Freaking Laser Beams」を実装することも常に可能です。

二段階コミット

二相コミットプロトコルは、分散システム内のすべてのクライアントがトランザクションのコミットまたは中止に同意できるようにするアルゴリズムです。

ZooKeeperでは、コーディネータがトランザクションノード（例：「/app/Tx」）と、参加している各サイトごとに1つの子ノード（例：「/app/Tx/s_i」）を作成することで、二相コミットを実装できます。コーディネータが子ノードを作成するときは、内容は未定義のままにします。トランザクションに参加している各サイトがコーディネータからトランザクションを受信すると、各サイトは各子ノードを読み取り、ウォッチを設定します。次に、各サイトはクエリを処理し、それぞれのノードに「commit」または「abort」を書き込むことで投票します。書き込みが完了すると、他のサイトに通知され、すべてのサイトがすべての投票を受け取るとすぐに、「abort」または「commit」のいずれかを決定できます。あるサイトが「abort」に投票した場合、ノードはそれより前に「abort」を決定できることに注意してください。

この実装の興味深い点は、コーディネータの役割が、サイトのグループを決定し、ZooKeeperノードを作成し、対応するサイトにトランザクションを伝播することだけであることです。実際、トランザクションノードに書き込むことで、ZooKeeperを使用してトランザクションを伝播することもできます。

上記のアプローチには、2つの重要な欠点があります。1つはメッセージの複雑さで、O(n²)です。2つ目は、一時ノードを通じてサイトの障害を検出できないことです。一時ノードを使用してサイトの障害を検出するには、サイトがノードを作成する必要があります。

最初の問題を解決するために、コーディネータだけがトランザクションノードの変更を通知され、コーディネータが決定に達するとサイトに通知されるようにできます。このアプローチはスケーラブルですが、すべての通信がコーディネータを経由する必要があるため、速度が遅いことに注意してください。

2番目の問題に対処するために、コーディネータがサイトにトランザクションを伝播し、各サイトが独自の一時ノードを作成するようにできます。

リーダー選出

ZooKeeperでリーダー選出を行う簡単な方法は、「提案」を表すznodesを作成するときに**SEQUENCE|EPHEMERAL**フラグを使用することです。考え方は、「/election」というznodesを持ち、各znodesがSEQUENCE|EPHEMERALの両方のフラグを使用して「/election/guid-n_」という子znodesを作成することです。シーケンスフラグを使用すると、ZooKeeperは「/election」の子に以前に追加されたものよりも大きいシーケンス番号を自動的に追加します。追加されたシーケンス番号が最小のznodesを作成したプロセスがリーダーです。

しかし、それだけではありません。リーダーの障害を監視することが重要です。そうすることで、現在のリーダーが障害が発生した場合に、新しいクライアントが新しいリーダーとして登場します。簡単な解決策は、すべてのアプリケーションプロセスが現在の最小znodesを監視し、最小znodesがなくなったときに新しいリーダーかどうかを確認することです（ノードが一時的なため、リーダーが失敗すると最小znodesはなくなります）。しかし、これにより群れ効果が発生します。現在のリーダーが失敗すると、他のすべてのプロセスが通知を受け取り、「/election」でgetChildrenを実行して「/election」の子の現在のリストを取得します。クライアントの数が多い場合、ZooKeeperサーバーが処理する必要がある操作の数にスパイクが発生します。群れ効果を回避するには、znodesのシーケンスで次のznodesを監視するだけで十分です。クライアントが監視しているznodesがなくなったという通知を受け取ると、より小さいznodesがない場合、新しいリーダーになります。これにより、すべてのクライアントが同じznodesを監視しないため、群れ効果が回避されます。

擬似コードを次に示します。

ELECTIONをアプリケーションの選択パスとします。リーダーになるために志願するには

1. SEQUENCEとEPHEMERALの両方のフラグを使用して、パス「ELECTION/guid-n_」にznodes zを作成します。
2. Cを「ELECTION」の子とし、Iをzのシーケンス番号とします。
3. jが最大のシーケンス番号で、j < iであり、n_jがC内のznodesである「ELECTION/guid-n_j」の変更を監視します。

znodesの削除の通知を受け取ったら

1. CをELECTIONの新しい子セットとします。
2. zがCで最小のノードである場合、リーダー手順を実行します。
3. そうでない場合、jが最大のシーケンス番号で、j < iであり、n_jがC内のznodesである「ELECTION/guid-n_j」の変更を監視します。

注記

• 子リストに先行するznodesがないznodesは、このznodesの作成者が現在のリーダーであることを認識していることを意味するものではありません。アプリケーションは、リーダーがリーダー手順を実行したことを確認するために、別のznodesを作成することを検討できます。

• ノードでのguidの使用方法については、ロックに関する注記を参照してください。