XNUMX 人の学生と XNUMX つの分散 Key-Value ストア

または、ZooKeeper、etcd、Consul KV 用のクライアント C++ ライブラリをどのように作成したか

分散システムの世界では、クラスターの構成に関する情報の保存、ノード構成の管理、障害のあるノードの検出、リーダーの選択などの典型的なタスクが多数あります。 その他。 これらの問題を解決するために、特別な分散システム、つまり調整サービスが作成されました。 ここで、そのうちの XNUMX つ、ZooKeeper、etcd、Consul に興味を持ちます。 Consul の豊富な機能のうち、Consul KV に焦点を当てます。

本質的に、これらすべてのシステムはフォールトトレラントで線形化可能なキー/値ストアです。 両者のデータ モデルには大きな違いがありますが、これについては後ほど説明しますが、実際上は同じ問題を解決します。 明らかに、調整サービスを使用する各アプリケーションはいずれかのアプリケーションに関連付けられているため、異なるアプリケーションで同じ問題を解決する複数のシステムを XNUMX つのデータ センターでサポートする必要が生じる可能性があります。

この問題を解決するというアイデアはオーストラリアのコンサルティング会社から生まれ、それを実行するのは私たち学生の小さなチームでした。それがこれからお話しすることです。

私たちは、ZooKeeper、etcd、Consul KV を操作するための共通インターフェイスを提供するライブラリを作成することができました。 このライブラリは C++ で書かれていますが、他の言語に移植する計画もあります。

データモデル

XNUMX つの異なるシステムに共通のインターフェイスを開発するには、それらのシステムの共通点と相違点を理解する必要があります。 それを理解しましょう。

飼育係

キーはツリーに編成され、ノードと呼ばれます。 したがって、ノードについては、その子のリストを取得できます。 znode の作成 (create) と値の変更 (setData) の操作は分離されており、既存のキーのみを読み取り、変更できます。 ウォッチは、ノードの存在の確認、値の読み取り、および子の取得の操作にアタッチできます。 Watch は、サーバー上の対応するデータのバージョンが変更されたときに起動される XNUMX 回限りのトリガーです。 一時ノードは障害を検出するために使用されます。 これらは、それらを作成したクライアントのセッションに関連付けられます。 クライアントがセッションを閉じるか、ZooKeeper への存在の通知を停止すると、これらのノードは自動的に削除されます。 単純なトランザクションがサポートされています。これは、すべてが成功するか、少なくとも XNUMX つが不可能な場合は失敗する一連の操作です。

etcd

このシステムの開発者は明らかに ZooKeeper に触発されており、したがってすべてが異なる方法で行われました。 キーには階層はありませんが、辞書順に並べられたセットを形成します。 特定の範囲に属するすべてのキーを取得または削除できます。 この構造は奇妙に見えるかもしれませんが、実際には非常に表現力豊かで、階層ビューをそれを通じて簡単にエミュレートできます。

etcd には標準の比較および設定操作はありませんが、トランザクションという優れた操作があります。 もちろん、これらは 3.3 つのシステムすべてに存在しますが、etcd トランザクションは特に優れています。 これらは、チェック、成功、失敗の XNUMX つのブロックで構成されます。 最初のブロックには一連の条件が含まれ、XNUMX 番目と XNUMX 番目のブロックには操作が含まれます。 トランザクションはアトミックに実行されます。 すべての条件が true の場合は成功ブロックが実行され、それ以外の場合は失敗ブロックが実行されます。 API XNUMX では、成功ブロックと失敗ブロックにネストされたトランザクションを含めることができます。 つまり、ほぼ任意の入れ子レベルの条件構造をアトミックに実行することが可能です。 どのようなチェックと操作が存在するかについて詳しくは、 ドキュメンテーション.

ここにも時計が存在しますが、少し複雑で再利用可能です。 つまり、キー範囲にウォッチをインストールした後は、最初のアップデートだけでなく、ウォッチをキャンセルするまで、この範囲内のすべてのアップデートを受信します。 etcd では、ZooKeeper クライアント セッションに相当するものはリースです。

領事K.V.

ここにも厳密な階層構造はありませんが、Consul は階層構造が存在するように見せることができます。つまり、指定されたプレフィックスを持つすべてのキーを取得および削除できます。つまり、キーの「サブツリー」を操作できます。 このようなクエリは再帰的と呼ばれます。 さらに、Consul は、接頭辞の後に指定された文字を含まないキーのみを選択できます。これは、直接の「子」を取得することに相当します。 しかし、これはまさに階層構造の外観であることを覚えておく価値があります。親が存在しない場合にキーを作成したり、子がシステムに保存され続けている間に子を持つキーを削除したりすることは十分に可能です。

Consul は監視の代わりに、HTTP リクエストをブロックします。 本質的に、これらはデータ読み取りメソッドへの通常の呼び出しであり、他のパラメーターとともに、データの既知の最後のバージョンが示されます。 サーバー上の対応するデータの現在のバージョンが指定されたバージョンよりも大きい場合は、応答がすぐに返されます。それ以外の場合は、値が変更されたときに応答が返されます。 いつでもキーにアタッチできるセッションもあります。 セッションを削除すると関連付けられたキーも削除される etcd や ZooKeeper とは異なり、セッションを単純にキーからリンク解除するモードがあることに注意してください。 利用可能 トランザクション、分岐はありませんが、あらゆる種類のチェックがあります。

すべてを一緒に入れて

ZooKeeper には最も厳密なデータ モデルがあります。 etcd で使用できる表現力豊かな範囲クエリは、ZooKeeper や Consul では効果的にエミュレートできません。 すべてのサービスの最良のものを組み込もうとした結果、次の重要な例外を除いて、ZooKeeper インターフェイスとほぼ同等のインターフェイスが完成しました。

• シーケンス、コンテナ、TTL ノード サポートされていません
• ACLはサポートされていません
• set メソッドは、キーが存在しない場合にキーを作成します (ZK では、この場合 setData はエラーを返します)。
• set メソッドと cas メソッドは分離されています (ZK では本質的に同じものです)
• Erase メソッドは、ノードをそのサブツリーとともに削除します (ZK では、ノードに子がある場合、delete はエラーを返します)。
• 各キーにはバージョンが XNUMX つだけあります - 値バージョン (ZK では それらのXNUMXつがあります)

シーケンシャル ノードが拒否されるのは、etcd と Consul にシーケンシャル ノードのサポートが組み込まれておらず、結果として得られるライブラリ インターフェイス上にユーザーが簡単に実装できるためです。

頂点を削除するときに ZooKeeper と同様の動作を実装するには、etcd と Consul でキーごとに個別の子カウンターを維持する必要があります。 メタ情報の保存を避けようとしたため、サブツリー全体を削除することにしました。

実装の微妙な点

さまざまなシステムでのライブラリ インターフェイスの実装のいくつかの側面を詳しく見てみましょう。

etcd の階層

etcd で階層ビューを維持することは、最も興味深いタスクの XNUMX つであることが判明しました。 範囲クエリを使用すると、指定されたプレフィックスを持つキーのリストを簡単に取得できます。 たとえば、で始まるすべてのものが必要な場合、 "/foo"、範囲を求めています ["/foo", "/fop")。 ただし、これではキーのサブツリー全体が返されるため、サブツリーが大きい場合には受け入れられない可能性があります。 当初はキー変換メカニズムを使用する予定でしたが、 zetcdで実装。 これには、キーの先頭に、ツリー内のノードの深さに等しい XNUMX バイトが追加されます。 例を挙げてみましょう。

"/foo" -> "u01/foo"
"/foo/bar" -> "u02/foo/bar"

次に、キーの直接の子をすべて取得します "/foo" 範囲をリクエストすることで可能 ["u02/foo/", "u02/foo0")。 はい、ASCII で "0" 直後に立つ "/".

しかし、この場合、頂点の削除をどのように実装すればよいでしょうか? 型のすべての範囲を削除する必要があることがわかりました。 ["uXX/foo/", "uXX/foo0") XXの場合は01からFFまで。 そして、私たちは遭遇しました 操作回数制限 XNUMX 回のトランザクション内で。

その結果、単純なキー変換システムが発明され、キーの削除と子のリストの取得の両方を効果的に実装できるようになりました。 最後のトークンの前に特殊文字を追加するだけで十分です。 例えば：

"/very" -> "/u00very"
"/very/long" -> "/very/u00long"
"/very/long/path" -> "/very/long/u00path"

次にキーを削除します "/very" 削除に変わります "/u00very" そして範囲 ["/very/", "/very0")、およびすべての子を取得します - 範囲からのキーのリクエストで ["/very/u00", "/very/u01").

ZooKeeper でのキーの削除

すでに述べたように、ZooKeeper では、ノードに子がある場合はノードを削除できません。 キーをサブツリーとともに削除したいと考えています。 どうすればいいですか？ 私たちはこれを楽観的に行っています。 まず、サブツリーを再帰的に走査し、個別のクエリで各頂点の子を取得します。 次に、サブツリーのすべてのノードを正しい順序で削除しようとするトランザクションを構築します。 もちろん、サブツリーの読み取りと削除の間に変更が発生する可能性があります。 この場合、トランザクションは失敗します。 さらに、サブツリーは読み取りプロセス中に変更される可能性があります。 たとえば、このノードがすでに削除されている場合、次のノードの子に対するリクエストはエラーを返す可能性があります。 どちらの場合も、プロセス全体をもう一度繰り返します。

このアプローチでは、キーに子がある場合、キーの削除は非常に効果的ではなくなります。また、アプリケーションがキーの削除と作成を行ってサブツリーを操作し続ける場合は、さらに効果が低くなります。 ただし、これにより、etcd および Consul での他のメソッドの実装が複雑になることを回避できました。

ZooKeeper に設定

ZooKeeper には、ツリー構造を操作するメソッド (create、delete、getChildren) と、ノード内のデータを操作するメソッド (setData、getData) が別々にあります。さらに、すべてのメソッドには厳密な前提条件があります。ノードがすでに作成されている場合、create はエラーを返します。データがまだ存在しない場合は、作成、削除、または setData します。 キーの存在を意識せずに呼び出せる set メソッドが必要でした。

XNUMX つのオプションは、削除と同様に楽観的なアプローチを取ることです。 ノードが存在するかどうかを確認します。 存在する場合は setData を呼び出し、存在しない場合は作成します。 最後のメソッドでエラーが返された場合は、もう一度最初から繰り返します。 まず注意すべきことは、存在テストは無意味であるということです。 すぐに create を呼び出すことができます。 正常に完了した場合は、ノードが存在せずに作成されたことを意味します。 それ以外の場合、create は適切なエラーを返します。その後、setData を呼び出す必要があります。 もちろん、呼び出しの間に、競合する呼び出しによって頂点が削除される可能性があり、setData もエラーを返します。 この場合、最初からやり直すこともできますが、それだけの価値はありますか?

両方のメソッドがエラーを返した場合、競合する削除が行われたことが確実にわかります。 set を呼び出した後にこの削除が行われたと想像してみましょう。 そのとき、私たちが確立しようとしている意味はすでに消去されています。 これは、実際には何も書き込まれていなくても、set が正常に実行されたと想定できることを意味します。

技術的な詳細

このセクションでは、分散システムから離れて、コーディングについて説明します。
お客様の主な要件の XNUMX つはクロスプラットフォームでした。つまり、サービスの少なくとも XNUMX つが Linux、MacOS、および Windows でサポートされている必要があります。 当初は Linux 向けにのみ開発し、その後他のシステムでもテストを開始しました。 これにより多くの問題が発生しましたが、しばらくの間、どのように対処すればよいのかまったくわかりませんでした。 その結果、XNUMX つの調整サービスはすべて Linux および MacOS でサポートされるようになりましたが、Windows では Consul KV のみがサポートされています。

私たちは最初から、サービスにアクセスするために既製のライブラリを使用しようとしました。 ZooKeeper の場合、選択は次のとおりでした。 ズーキーパー C++、最終的には Windows でコンパイルできませんでした。 ただし、これは驚くべきことではありません。このライブラリは Linux 専用として位置付けられています。 領事にとって唯一の選択肢は ppconsul。 サポートを追加する必要がありました セッション и トランザクション。 etcd の場合、最新バージョンのプロトコルをサポートする本格的なライブラリが見つからなかったため、単に 生成された grpc クライアント.

ZooKeeper C++ ライブラリの非同期インターフェイスからインスピレーションを得て、非同期インターフェイスも実装することにしました。 ZooKeeper C++ は、これに future/promise プリミティブを使用します。 残念ながら、STL では、これらは非常に控えめに実装されています。 たとえば、いいえ その後メソッド、渡された関数を将来の結果が使用可能になったときに適用します。 私たちの場合、そのようなメソッドは結果をライブラリの形式に変換するために必要です。 この問題を回避するには、顧客の要求により Boost などの重いサードパーティ ライブラリを使用できなかったため、独自の単純なスレッド プールを実装する必要がありました。

then の実装は次のように機能します。 呼び出されると、追加の Promise/Future ペアが作成されます。 新しい Future が返され、渡された Future は、対応する関数および追加の Promise とともにキューに配置されます。 プールのスレッドはキューからいくつかの先物を選択し、wait_for を使用してそれらをポーリングします。 結果が利用可能になると、対応する関数が呼び出され、その戻り値が Promise に渡されます。

etcd と Consul へのクエリを実行するために同じスレッド プールを使用しました。 これは、基礎となるライブラリが複数の異なるスレッドからアクセスできることを意味します。 ppconsul はスレッドセーフではないため、ppconsul への呼び出しはロックによって保護されます。
grpc は複数のスレッドから操作できますが、微妙な点があります。 etcd では、監視は grpc ストリーム経由で実装されます。 これらは、特定の種類のメッセージ用の双方向チャネルです。 ライブラリは、すべての監視に対して XNUMX つのスレッドと、受信メッセージを処理する XNUMX つのスレッドを作成します。 したがって、grpc はストリームへの並列書き込みを禁止します。 つまり、ウォッチを初期化または削除する場合は、前のリクエストの送信が完了するまで待ってから、次のリクエストを送信する必要があります。 同期に使用します 条件変数.

合計

自分自身を参照してください： liboffkv.

私たちのチーム： レイド・ロマノフ, イワン・グルシェンコフ, ドミトリー・カマルディノフ, ヴィクトル・クラピベンスキー, ヴィタリー・イワニン.

出所： habr.com