👼🏼 🧔🏾 📷 複製されたオブジェクト。パート1：はじめに 📴 👊🏻 👎🏼

まえがき この出版物は、著者自身の記事の翻訳です。したがって、翻訳でエラーを見つけた場合、実際にはそのエラーが元の記事にあることが判明する可能性があります。

注釈

悲惨さがあります。
苦しむ理由があります。
苦しみの停止があります。
苦しみを取り除く方法があります。

4仏教の高貴な真実

この記事では、 複製されたオブジェクトまたは省略されたreplobの概念を紹介する初期のプロトタイプについて説明します。このようなオブジェクトは、分散システムをプログラミングするときに発生するコードの複雑さとの闘いをさらに再考したものです。 Replobは、サードパーティのサービスへの依存を排除し、関連するデータと機能を表すユーザーオブジェクトに一貫した変更を実装します。このアイデアは、C ++言語の表現力と、分散トランザクション内での複雑なロジックの使用を可能にするオブジェクト指向アプローチの使用に基づいています。これにより、フォールトトレラントなアプリケーションとサービスの開発が大幅に簡素化されます。後続の記事では、開発中のアプローチについてさらに詳しく説明します。

はじめに

警告この記事で言及されているほとんどすべてのメソッドには、ダーティメモリハッキングとC ++言語の異常な使用が含まれています。そのため、このような倒錯に寛容でない場合は、この記事を読まないでください。

現在、分散システムに関連するトピックは最も興味深いものの1つであり、開発者や科学者を含む多くの人々を魅了しています。人気は簡単に説明されています。さまざまな操作を実行し、データを保存するための安全な環境を提供する信頼できるフォールトトレラントシステムを作成する必要があります。

同時に、分散システムの一貫性を維持することも重要な役割を果たします。高レベルの一貫性を確保するには、かなりの代償が伴います。今日、一貫性の最も弱い形式を提供する多くのソリューションがあります。いわゆる長期的な一貫性（最終的な一貫性）です。一方では、そのようなソリューションは比較的優れたパフォーマンスを発揮しますが、他方では、操作のトランザクションセマンティクスを必要とする多くの分野で使用することはできません。実際には、 厳密な一貫性や線形化可能 性などの強力な一貫性レベルの1つを使用してシステムについて考える方がはるかに簡単です。これらのレベルの一貫性により、一連の操作の実行の安全なセマンティクスを備えた信頼性の高いアプリケーションの開発がはるかに容易になります。

復習

人生が示すように、幸福はほとんどの人が考えるよりも外部のものに依存しません。

ウォーレン・カウパー

分散システムを開発するには、特別なサービスが最もよく使用されます。これらのサービスは、分散タスクの非同期性や、ネットワークの問題、アプリケーションのクラッシュ、ハードウェアの障害など、さまざまな種類の障害に関連する複雑さに対処する便利な方法を提供する必要があります。分散環境では、これらの問題は通常のものとは見なされませんが、ごく普通のものとして扱う必要があります。したがって、分散システムで発生する問題を解決するための信頼性の高い一貫したサービスを作成するタスクが現場に登場します。

最新のシステムでは、 Zookeeper （ほとんど）またはetcd （開発中）などのフォールトトレラントサービスを使用しています。彼らは分散コンセンサスアルゴリズムを使用します： Zab （Zookeeper）またはRaft （etcd）は、操作の線形化を保証します。ここでの考え方は次のとおりです。最初のステップでは、リーダーが選出され、指定されたリーダー（マスター）が特定の順序でメッセージをキャプチャします。これにより、必要なレベルの一貫性が確保されます。 Zookeeperのドキュメントでは、Zookeeper はステートマシンのレプリケーションではなくプライマリバックアップを使用してアプローチを実装すると主張していますが、これらのアプローチの唯一の違いは、プライマリバックアップがレプリカで指定された順序に基づいていることと、レプリケーションステートマシンは、クライアントが指定したシーケンスに基づいています。ここでは、両方のアプローチが、開発されたマスターベースのコンセンサスアルゴリズムを使用した一連の決定論的操作に同意することが重要だと思います。

既存のアプローチの議論

イベントを制御することはできませんが、イベントに適合する必要があることを常に覚えておく必要があります。

エピクテトゥス

マスターベースの分散コンセンサスアルゴリズムの欠点は明らかです。マスターのクラッシュに関連する状態を処理するには、一定の時間がかかります。マスターの落下を検出するためのタイムアウトは、新しいマスターを選択する可能性が高いためにパフォーマンスに悪影響を及ぼす可能性があるため、非常に小さくすることはできません。同時に、マスターのフォール処理の遅延が大幅に増加するため、タイムアウトを非常に大きくすることはできません。したがって、実際には、メッセージ処理の遅延と、マスターの再選の可能性との間に妥協点があります。これは、一般的な場合、ネットワーク条件とクラスターマシンのパフォーマンスに依存します。同時に、コンセンサスアルゴリズムのパフォーマンスは、ウィザードの存続可能性に厳密に依存し、パフォーマンスの復元とデータの一貫性の維持にかなりの時間がかかる場合があります。このようなロジックには、少なくともいくつかのネットワークメッセージングが必要であり、不完全な操作を修正します。このプロセスは、各参加者が新しいマスターとして宣言できるため、転倒がない場合でも一定期間の収束を保証しません。したがって、一部の操作では、システムが比較的長時間使用できない場合があります。

ぽっちゃり：ほとんどの問題は約15秒以下続き、そのうちの52は約30秒でした。
MongoDB ：時間はさまざまでしたが、レプリカは1分間ウィザードを選択しました...ウィザードの選択中、クラスターは書き込み可能ではありませんでした。
Zookeeper ：15秒ほど後に新しいリーダーが選出され、録音が再び続けられました。ただし、[n3 n4 n5]ノードのいずれかにアクセスできるクライアントのみが書き込み可能で、[n1 n2]ノードに接続されたクライアントはリーダーに接続しようとしたときにタイムアウトで処理を完了しました。

トランザクションのセマンティクスと重要なシナリオ

ロジックとは、自分が正しいと自信を持って間違いを犯す技術です。

J.W.クラッヒ

トランザクションセマンティクスを非自明なロジックに適用することは、最も難しい問題の1つです。 Zookeeperのような信頼できるリポジトリがあり、次の一連の操作を実行するとします。

作業用にストレージの一部のデータをプロセスメモリにダウンロードします。
データを処理し、結果を取得するための重要なロジックの使用。
結果をリポジトリに保存します。

このシナリオは、いくつかのアプローチを適用することで解決できます。

悲観的なブロッキング

悲観的ブロッキングは、マルチスレッドアプリケーションのミューテックスアプローチと同様に、使用されるリソースの明示的なブロッキングに基づいています。上記のタスクは、次の一連の操作を適用することで解決できます。

操作を完了するための排他ロックの取得。
上記の操作（ダウンロード、使用、保存）を実行します。
ロック解除。

このスキームの欠点は、アクセスの排他性の要件から直接生じます。

排他的ロックは、ロック/ロック解除操作のレイテンシを大幅に増加させます。その結果、運用の合計時間が悪化します。
操作の途中でプロセスがクラッシュすると、一貫性のないデータを受け取る可能性があります（残念ながら、Zookeeperにはロック解除段階でいくつかの操作を原子的に適用する機能があります）。これには、プロセスのドロップとそれに続くリソースのロック解除を検出するための追加時間が必要であり、このような操作の合計時間が長くなります。

Zookeeperのようなシステムには明示的なロックおよびロック解除機能がないことを強調したいと思います。悲観的なブロッキングの場合、特別なレシピを使用する必要がありますが、このようなトランザクションには追加の遅延が発生します（ ZooKeeper Synchronization Inefficiencyの対処も参照）。

この点で、問題を解決する別の方法がシーンに表示されます。

楽観的なブロック

楽観的なスキームは、以前のアプローチのパフォーマンスの問題を回避しようとしています。アイデアは、操作をコミットする前にデータの実際の状態を確認することです。

ストレージから現在のデータ状態をダウンロードします。
自明ではないロジックのローカルアプリケーションと、書き込みのための一連の操作の作成。
他のトランザクションがデータを変更していないことのアトミック検証、および書き込みのための一連の操作の修正。
テストが失敗した場合=>最初のステップから操作を繰り返します。

3番目のステップのすべてのアクションは、変更の確認とコミットを含め、アトミックに実行する必要があります。このようなスキームは、インクリメンタルバージョンカウンターを使用して実装できます。更新操作が成功した場合、カウンターを1つ増やします。考え方は、「交換と比較」操作を使用することです。これは、データのバージョンが変更されていないこと、つまりデータ自体が変更されていないことをアトミックにチェックします。

ただし、このスキームには欠点もあります。

実装の複雑さ ：サービスは「交換との比較」およびパケットレコードの修正の操作を実装する必要があり、これら2つの操作をアトミックに実行できる必要があります。
高い競争力と高いコスト ：かなりの数の同時更新により、アルゴリズムは最初からステップを繰り返す必要があり、それにより頻繁なデータ変更から生じる競合のためにリソースを浪費します。

さらに、悲観的および楽観的ロックの場合、対応するシステムの階層キースペースで内部データをシリアル化する必要があります（たとえば、Zookeeper "znodes"またはetcd "nodes" ）。言及されたすべての事実は、開発中のアプリケーションを複雑にしますが、アプローチはさまざまな種類のエラーの影響を受けます。したがって、私は全く異なる方向に行きたいです。

複製されたオブジェクトの概念

単純に複合体にアプローチする必要があります。そうでなければ、私たちはそれを決して理解しません。

済州クリシュナムルティ

一歩後退して、 オブジェクト指向プログラミング （OOP）について思い出しましょう。ここにオブジェクトの概念があります。そのような各オブジェクトは、オブジェクトの状態を表す特定のデータを所有しています。さらに、オブジェクトには、オブジェクトをある状態から別の状態に変換する一連のメソッドが含まれています。

したがって、アイデアは、データ自体（ オブジェクトの状態 ）を複製するのではなく、クラスターのノード間でアクション（ オブジェクトのメソッド ）を複製することです。これらのアクションは、オブジェクトの状態を決定的に変更し、オブジェクト自体が複製されているような錯覚を作成します。同時に、線形化により、すべてのレプリカが同じアクションのシーケンスを受け入れることが保証されるため、検討中の分散オブジェクトの一貫した状態を取得できます。これは、ステートマシンのレプリケーションモデルに非常によく似ています。唯一の違いは、通常のオブジェクトを使用して状態を表し、 メソッドを使用してオブジェクトを変換するイベントを表すことです。このマッピングは、開発の複雑さを大幅に軽減し、コードを肥大化させることなくOOPの使用を最初にサポートするため、C ++言語のパワーを使用できます。

複製されたオブジェクトのプロパティ

複製されたオブジェクト（または単にreplob ）には次のプロパティがあります。

組み込み
マスターなし。
メモリ内のストレージ。
線形化可能な一貫性。
プロセスのFIFO保証。
高速ローカル読み取り。
競争力のある柔軟な分散トランザクション。
独立した同時トランザクションオプションのサポート。
ネイティブデータ構造のサポート。
ATSを構成できます。
レプリカセットのスムーズな劣化。
さまざまなネットワークの問題に対するセキュリティと生存性：
1. ネットワーク接続の中断。
2. 「ブリッジ」タイプのネットワーク接続の部分的な違反。
3. 一時的なネットワークの不安定。
4. ネットワークパケットの部分的な方向。

以下に各項目を簡単に確認します。

冗長では、罪を避けることはできませんが、彼の口の抑制は知的です。

伝道者

ビルトイン 。これはスタンドアロンのサービスではありません。機能はユーザープロセス内で機能し、レプリカ間のネットワークメッセージの数を減らすことで操作の遅延を減らします。このアプローチは、Zookeeperやetcdなどのサービスへの外部依存を完全に排除し、ネイティブインターフェイスを使用します。これにより、レプリケーションロジックとの対話が大幅に簡素化され、ユーザーに対して完全に透過的になります。

マスターなし 。アルゴリズムには専用のマスター（リーダー）はありません。したがって、各ノードは互いに区別できません。これにより、障害から回復する際の待ち時間が大幅に短縮され、ほとんどの場合、より予測可能な動作が作成されます。

メモリ内のストレージ 。現在の実装には永続層がなく、各要素はプロセスメモリ内のレプリカに分散されます。ただし、このアルゴリズムを使用すると、オブジェクトの永続プロパティを追加できます。

線形化可能な一貫性 。複製されたオブジェクトのアルゴリズムは、操作の線形化可能性を保証します。

プロセスのFIFO保証 。指定されたプロセスでは、すべての操作は、このプロセスで計画された順序（FIFO順序）で完了します。

高速ローカル読み取り 。特殊モードを使用すると、一貫性のレベルを一貫性のある一貫性に低下させることにより、データをローカルで読み取ることができます。これにより、レイテンシとシステム全体の負荷が大幅に削減されます。

競争力のある柔軟な分散トランザクション 。トランザクション内では、任意の複雑度の決定論的な一連の操作を使用できます。このようなトランザクションは、競争力のある方法で処理されます。

独立した同時トランザクションオプションのサポート 。ユーザーは、コンセンサス実装の複数のインスタンスを使用して、独立したトランザクションを並列化できます。

ネイティブデータ構造のサポート 。開発者は、 std::vector

、 std::map

などの標準コンテナや、 boost::optional

、 boost::variant

またはコピーセマンティクスをサポートする他のデータ構造を使用できます。

ATSを構成できます 。ユーザーは、ネットワーク接続が失敗した場合に、線形化可能性と可用性を選択できます。

レプリカセットのスムーズな劣化 。レプリカの数が大幅に減少しても、システムの一貫性は維持されます。たとえば、レプリカの数を5から2に減らすことができ、状況によっては1つのレプリカに減らすこともできます。

さまざまなネットワーク問題のセキュリティと生存性 。ネットワークにはさまざまな問題があります（ Aphyr：ネットワークは信頼できるを参照してください）。同時に、アルゴリズムはこれらの場合に一貫性とパフォーマンスを維持します。

これらすべてのポイントについては、後続の記事で詳しく説明します。

例

勝利があなたに依存していない戦闘に参加しなければ、無敵になる可能性があります。

エピクテトゥス

このアプローチのすべての柔軟性とパワーを実証するために、かなり単純な例を検討します。

例：Key-Valueストレージ

次のインターフェイスを使用してレプリケートされたリポジトリを実装しましょう（略してstd::

およびboost::

名前空間は省略します）。

 struct KV { optional<string> get(const string& key) const; void set(const string& key, const optional<string>& value); private: unordered_map<string, string> kv_; };

簡単にするために、対称インターフェースを選択しました。空の値が渡された場合、 set

メソッドは対応するキーを削除します。通常のオブジェクトを使用する場合、対応する実装は次のとおりです。

 optional<string> KV::get(const string& key) const { if (kv_.count(key) == 0) return {}; return kv_.at(key); } void KV::set(const string& key, const optional<string>& value) { if (value) kv_[key] = *value; else kv_.erase(key); }

次に、通常のオブジェクトを複製されたオブジェクトに変換します。このために、私は単に追加します：

 DECL_REPLOB(KV, get, set)

ヒント

ヒント： DECL_REPLOB

の実装は次のとおりです。

 #define DECL_REPLOB DECL_ADAPTER

そして、次のコード行を使用してレプリカセットデータを複製できます。

 replob<KV>().set(string{"hello"}, string{"world!"});

KV::set

呼び出しKV::set

、レプリカセットのタイプKV

すべてのインスタンスに、指定されたペアが含まれます。インスタンスは、タイプKV

を介して参照できることに注意してください。つまり、各レプリカには、このオブジェクトの独自の単一インスタンスが含まれます。

線形化されたレベルの一貫性でデータを読み取るには、次のように記述します。

 auto world = replob<KV>().get(string{"hello"});

しかし、この読み取り操作のパフォーマンスを向上させるために、次のように記述します。

 auto localWorld = replobLocal<KV>().get(string{"hello"});

行くぞ！

取引

指定したキーの値を変更したいとします。素朴な方法は、次のようなコードを書くことです。

 auto world = replobLocal<KV>().get(string{"hello"}).value_or("world!"); replob<KV>().set(string{"hello"}, "hello " + world);

ここでの唯一の問題は、2つの連続したアトミック操作が合計アトミック操作を与えないことです（いわゆる第2種の競合状態 ）。したがって、トランザクション内にすべてのアクションを配置する必要があります。

 MReplobTransactInstance(KV) { auto world = $.get(string{"hello"}).value_or("world!"); $.set(string{"hello"}, "hello " + world); };

次に、これらすべてのアクションがすべてのレプリカにアトミックに適用されます。

結果トランザクション

次のタスクを検討してください。指定されたキーの値のサイズを計算する必要があります。これ以上簡単なことはありません：

 // use local instance because we do not need to update the object auto valueLength = MReplobTransactLocalInstance(KV) { return $.get(string{"hello"}).value_or("").size(); };

同じアプローチを使用してオブジェクトを変更できます。

 auto valueLength = MReplobTransactInstance(KV) { auto world = $.get(string{"hello"}); $.set(string{"another"}, world); return world.value_or("").size(); };

これらの操作はすべて、レプリカにアトミックに適用されます。

複数のreplobを持つトランザクション

2つの独立したキーと値のストレージインスタンスKV1

とKV2

があると仮定しましょう。 MReplobTransact

修飾子を使用して、1つのトランザクションで異なるインスタンスの操作を結合できます。

 // the first transaction is distributed // performs value copying from KV2 to KV1 for the same key MReplobTransact { $.instance<KV1>().set( string{"hello"}, $.instance<KV2>().get(string{"hello"})); }; // the second transaction is applied locally // returns total value size calculation for the same key auto totalSize = MReplobTransactLocal { auto valueSize = [](auto&& val) { return val.value_or("").size(); }; return valueSize($.instance<KV1>().get(string{"hello"})) + valueSize($.instance<KV2>().get(string{"hello"})); };

最初のトランザクションはすべてのレプリカで分散されて実行されますが、これらのアクションはすべてアトミックに実行されます。

高度な例

ユーザー定義関数を使用したコレクションの繰り返しを見てみましょう。

 struct KV { optional<string> get(const string& key) const; void set(const string& key, const optional<string>& value); // generic method to iterate through the collection template<typename F> void forEach(F f) const { for (auto&& v: kv_) f(v); } private: unordered_map<string, string> kv_; };

ここでのタスクは、すべての値の合計行サイズを返すことです。

 auto valuesSize = MReplobTransactLocalInstance(KV) { size_t sz = 0; $.forEach([&sz](auto&& v) { sz += v.second.size(); }); return sz; };

ご覧のとおり、すべてが非常に簡単に実装されています。

今後の方向性

何に行きたいかを前もって知っていれば、この方向へのステップはまったく実験ではありません。

済州クリシュナムルティ

以前、私は、複製されたオブジェクトを使用してこのアプローチを使用する方法の例として、いくつかの単純ですが非常に興味深い意見を調べました。以降の記事では、使用するアイデアと概念を段階的に紹介します。

神のアダプター。
デッドロックまたは主観モデルのない非ブロッキング同期。
同種のアクターモデルまたはファンクターモデル 。
超汎用シリアル化。
動作修飾子。
IOおよびコルーチン。
CAP定理の一貫性と適用性の問題。
ウィザードなしのファントム、replob、およびコンセンサスアルゴリズム 。
実装例：
1. 原子障害検出器。
2. 分散スケジューラ。

結論

成熟とは、他人への依存から自分への依存への移行です。

フレデリック・パールズ

多くの異常なプロパティを持つ、フォールトトレラントな分散複製オブジェクトの組み込みについて説明しました。これらのプロパティは、信頼性の高い分散アプリケーションを作成する複雑さを大幅に軽減し、さまざまな新しいタスクでそのようなオブジェクトを適用するための新しい視野を開きます。

ウィザードを使用しないコンセンサスアルゴリズムにより、大幅な時間損失なしに、さまざまな障害状況を予測可能な方法で処理できます。組み込みのアプローチにより、データ読み取り時のネットワーク遅延がなくなります。同時に、強力な整合性モデルは複製されたオブジェクトと対話する便利な方法を提供し、分散トランザクション内で可能な限り柔軟に使用することもできます。

有用なコメントとヒントを提供してくれたセルゲイ・ポロフコ、ヤウヘニ・アホトニカウ、ペトル・プロホレンコフに感謝します。

セルフテストの質問

唯一の困難は、正しい質問をすることです。

フレデリック・パールズ

DECL_REPLOB

はどのように実装されますか？
ローカル操作と非ローカル操作の違いは何ですか？
ウィザードなしでコンセンサスアルゴリズムを実装することは可能ですか？
記事に記載されているすべての動作修飾子をリストします。

参照資料

[1]ドキュメント： Zookeeper

[2]ドキュメント： etcd

[3]記事： Zab：高性能放送

プライマリバックアップシステム

[4]記事：理解可能なコンセンサスアルゴリズムを求めて

（拡張バージョン）

[5] Zookeeperのドキュメント： Zabとパクソス。

[6]記事：疎結合分散システム向けのチャビーロックサービス。

[7] MongoDBドキュメント：レプリカセットのフェールオーバーにかかる時間

[8] Aphyrブログ： Zookeeper 。

[9]ドキュメント： ZooKeeperのレシピとソリューション：ロック。

[10]記事： ZooKeeperの同期の非効率性に対処する。

[11]ドキュメント： Zookeeper znodes 。

[12]ドキュメント： etcdノード。

[13] Wikipedia： State Machine Replication 。

[14] Aphyrブログ： The Network Is Reliable 。

[15]記事： ZooKeeper：インターネット規模のシステムの待機なしの調整。

複製されたオブジェクト。 パート1：はじめに

注釈