NoSQLデータベースの分散アルゴリズムの詳細な説明

システムのスケーラビリティは、分散システムの調整、フェイルオーバー、リソース管理、その他多くの機能を含む NoSQL ムーブメントの発展の主な理由です。これにより、NoSQL は、何でも入れられる大きなバスケットのように聞こえます。 NoSQL の動きは分散データ処理に根本的な技術的変化をもたらしたわけではありませんが、さまざまなプロトコルとアルゴリズムに関する広範な研究と実践を引き起こしました。これらの試みを通じて、いくつかの効果的なデータベース構築方法が徐々にまとめられてきました。この記事では、NoSQL データベースの分散特性について体系的に説明します。

次に、障害検出のためのレプリケーションなどのいくつかの分散戦略について説明します。これらの戦略は太字で示されており、3 つのセクションに分かれています。

• データの一貫性。 NoSQL では、分散システムにおける一貫性、フォールト トレランスとパフォーマンス、低レイテンシ、高可用性の間でトレードオフを行う必要があります。一般的に、データの一貫性は必須であるため、このセクションでは主にデータのレプリケーションとデータの回復について説明します。
• データの配置。データベース製品は、さまざまなデータ分散、クラスター トポロジ、およびハードウェア構成に対応できる必要があります。このセクションでは、データ分散を分散および調整して、障害をタイムリーに解決し、永続性の保証、効率的なクエリを提供し、トレーニングにおけるリソース (メモリやハードディスク領域など) のバランスの取れた使用を確保する方法について説明します。
• ピアツーピアシステム。リーダー選出などの技術は、フォールト トレランスと強力なデータ一貫性を実現するために、複数のデータベース製品で使用されてきました。ただし、分散型データベース (中央機関なし) でも、グローバルな状態を追跡し、障害やトポロジの変更を検出する必要があります。このセクションでは、システムを一貫した状態に保つためのいくつかの手法について説明します。システム調整。リーダー選出のような調整技術は、

データの一貫性

ご存知のとおり、分散システムではネットワークの分離や遅延が発生することがよくあります。この場合、分離された部分は使用できなくなるため、一貫性を犠牲にせずに高い可用性を維持することは不可能です。この事実はしばしば「CAP 定理」と呼ばれます。しかし、分散システムでは一貫性は非常にコストがかかるため、可用性だけでなく、他の多くのトレードオフについても妥協が必要になることがよくあります。これらのトレードオフを研究するために、分散システムの一貫性の問題はデータの分離とレプリケーションによって引き起こされることに注目し、レプリケーションの特性を研究することから始めます。

• 可用性。ネットワークが分離した場合でも、残りの部分は読み取りおよび書き込み要求を処理できます。
• 読み取りと書き込みの遅延。読み取りおよび書き込み要求は短時間で処理できます。
• 読み取りと書き込みのスケーラビリティ。読み取りおよび書き込みの圧力は、複数のノードで均等に共有できます。
• フォールトトレランス。読み取りおよび書き込み要求の処理は、特定のノードに依存しません。
• データの永続性。特定の条件下ではノード障害が発生してもデータが失われることはありません。

一貫性。一貫性は以前の特性よりもはるかに複雑であり、いくつかの異なる観点について詳細に議論する必要があります。 しかし、一貫性理論や並行性モデルについては、この記事の範囲を超えているため、あまり詳しく説明しません。ここでは、いくつかのシンプルな機能で構成された合理化されたシステムのみを使用します。

読み取りと書き込みの一貫性。読み取りと書き込みの観点から見ると、データベースの基本的な目標は、レプリカが収束する時間 (つまり、更新がすべてのレプリカに配信されるまでの時間) をできるだけ短くして、最終的な一貫性を確保することです。この弱い保証に加えて、より強力な一貫性機能がいくつかあります。

書き込み後の読み取り一貫性。データ項目 X に対する書き込み操作の影響は、X に対する後続の読み取り操作で常に表示されます。

読み取り後の一貫性。データ項目 X に対する読み取り操作の後、X に対する後続の読み取り操作では、最初の戻り値と同じ値またはそれより新しい値が返される必要があります。

一貫性を持って書きます。パーティション化されたデータベースでは、書き込みの競合が頻繁に発生します。データベースはこの競合を処理し、複数の書き込み要求が異なるパーティションによって処理されないようにする必要があります。この点に関して、データベースはいくつかの異なる一貫性モデルを提供します。

アトミック書き込み。データベースが API を提供する場合、書き込み操作は単一のアトミック割り当てのみになります。書き込みの競合を回避する方法は、各データの「最新バージョン」を見つけることです。これにより、更新が行われた順序に関係なく、更新の最後にすべてのノードが同じバージョンを取得できるようになります。ネットワーク障害や遅延により、ノード間で更新の一貫性が失われることがよくあります。 データ バージョンは、タイムスタンプまたはユーザー指定の値で表すことができます。これは Cassandra で使用されるアプローチです。

アトミックな読み取り、変更、書き込み。アプリケーションでは、単一のアトミック書き込み操作ではなく、読み取り、変更、書き込みのシーケンスを実行する必要がある場合があります。 2 つのクライアントが同じバージョンのデータを読み取り、それを変更し、変更されたデータを書き戻すと、アトミック書き込みモデルに従って、後の更新によって前の更新が上書きされます。この動作は、場合によっては正しくありません (たとえば、2 つのクライアントが同じリスト値に新しい値を追加する場合)。データベースは少なくとも 2 つのソリューションを提供します。

紛争予防。 読み取り、変更、書き込みはトランザクションの特殊なケースと見なすことができるため、分散ロックやPAXOS [20, 21]などのコンセンサスプロトコルによってこの問題を解決できます。このテクノロジーは、任意の分離レベルでのアトミックな読み取り、変更、書き込みセマンティクスとトランザクションをサポートします。もう 1 つのアプローチは、分散同時書き込み操作を回避し、特定のデータ項目に対するすべての書き込み操作を単一のノード (グローバル マスターまたはパーティション マスター) にルーティングすることです。競合を回避するには、ネットワーク分離の場合にデータベースの可用性を犠牲にする必要があります。このアプローチは、強力な一貫性保証を提供する多くのシステム (ほとんどのリレーショナル データベース、HBase、MongoDB など) で一般的に使用されています。

競合検出。データベースは同時更新における競合を追跡し、そのうちの 1 つをロールバックするか、両方のバージョンを維持してクライアントに解決させるかを選択します。同時更新は通常、ベクタークロック[19]（楽観的ロックの一種）を使用するか、完全なバージョン履歴を維持することによって追跡されます。このアプローチは、Riak、Voldemort、CouchDB で使用されています。

ここで、一般的に使用されるレプリケーション手法を詳しく見て、説明した特性に従って分類してみましょう。最初の図は、システムの一貫性、スケーラビリティ、可用性、およびレイテンシの観点から、さまざまなテクノロジ間の論理的な関係と、さまざまなテクノロジ間のトレードオフを示しています。 2 番目の図は、各テクノロジを詳細に示しています。

複製係数は 4 です。読み取り/書き込みコーディネーターは、外部クライアントまたは内部プロキシ ノードにすることができます。

#p#

一貫性に基づいて、最も弱いテクニックから最も強いテクニックまで、すべてのテクニックを見ていきます。

(A、反エントロピー) 次の戦略に基づくと、一貫性は最も弱くなります。書き込み時に、更新するノードを選択します。読み取り時に、バックグラウンドのアンチエントロピー プロトコルを通じて新しいデータが読み取りノードに送信されていない場合、読み取られたデータは古いデータのままになります。 (アンチエントロピー プロトコルについては、次のセクションで詳しく説明します)。このアプローチの主な特徴は次のとおりです。

伝播遅延が大きいため、データ同期にはあまり役立ちません。そのため、通常は、計画外の不整合を検出して修復するための補助機能としてのみ使用されます。 Cassandra は、反エントロピー アルゴリズムを使用して、ノード間でデータベース トポロジやその他のメタデータ情報を転送します。

弱い一貫性の保証: 障害が発生していない場合でも、書き込みの競合や読み取り/書き込みの不整合が発生する可能性があります。

ネットワーク分離下での高可用性と堅牢性。非同期バッチ処理により、1 つずつの更新が置き換えられ、優れたパフォーマンスが実現します。

新しいデータには最初はコピーが 1 つしかないため、耐久性の保証は弱くなります。

(B) 上記のパターンを改良したものとして、いずれかのノードがデータの更新要求を受信したときに、利用可能なすべてのノードに更新を非同期に送信するというものがあります。これは有向反エントロピーとも呼ばれます。

純粋な反エントロピーと比較すると、このアプローチはパフォーマンスをわずかに犠牲にするだけで一貫性を大幅に向上させます。ただし、形式的な一貫性と永続性は変わりません。

ネットワーク障害またはノード障害のために一部のノードが利用できない場合、更新は最終的にアンチエントロピー伝播プロセスを通じてノードに配信されます。

（C）以前のモードでは、ヒント付きハンドオーバー技術[8]の使用により、ノード操作の失敗をより適切に処理できます。障害が発生したノードの予想される更新は追加のプロキシ ノードに記録され、特定のノードが利用可能になったらそのノードに配信されるようにマークされます。これにより一貫性が向上し、レプリケーションの収束時間が短縮されます。

(D、1 回限りの読み取りと書き込み) ハンドオーバーを促すノードは更新が配信される前に障害が発生する可能性があるため、いわゆる読み取り修復を通じて一貫性を確保する必要があります。各読み取り操作は、データを保存しているすべてのノードからデータの概要 (署名やハッシュなど) を要求する非同期プロセスを開始します。各ノードから返される概要に矛盾があることが判明した場合、各ノードのデータ バージョンは統合されます。 「一度だけ読み取り、一度だけ書き込み」という用語を使用して、A、B、C、D の手法の組み合わせを指定します。いずれも厳密な一貫性の保証は提供しませんが、自己完結型の方法として実際に使用できます。

(E、いくつか読み取り、いくつか書き込み) 上記の戦略は、レプリケーションの収束時間を短縮するヒューリスティックな拡張です。より強力な一貫性を確保するには、可用性を犠牲にして、一定の読み取りと書き込みの重複を確保する必要があります。 通常は、一度に 1 つのレプリカだけではなく W 個のレプリカに書き込み、同時に R 個のレプリカから読み取ります。

まず、書き込みレプリカの数を W>1 に設定できます。

次に、R+W>N であるため、書き込みノードと読み取りノードの間には必然的に重複が生じ、読み取られる複数のデータ コピーのうち少なくとも 1 つは比較的新しいデータになります (上図では W=2、R=3、N=4)。このように、読み取り要求と書き込み要求が順番に実行される場合 (書き込み実行の後に読み取り)、一貫性は保証されます (単一ユーザーの読み取りと書き込みの一貫性) が、グローバルな読み取り一貫性は保証されません。下の図の例、R=2、W=2、N=3 を見てみましょう。2 つのレプリカの更新では書き込み操作は非トランザクションであるため、更新が完了していない場合、読み取りでは古い値の両方が読み取られるか、新しい値と古い値が 1 つずつ読み取られる可能性があります。

特定の読み取りレイテンシ要件については、R と W に異なる値を設定することで、書き込みレイテンシと耐久性を調整でき、その逆も同様です。

W <= N/2 の場合、複数の同時書き込みが異なるノードに書き込まれます (たとえば、書き込み操作 A は最初の N/2 ノードに書き込み、書き込み操作 B は最後の N/2 ノードに書き込みます)。 W>N/2 に設定すると、ロールバック モデルに準拠したアトミックな読み取り、変更、書き込み操作中に競合が適時に検出されるようになります。

厳密に言えば、このモードでは個々のノードの障害は許容できますが、ネットワーク分離に関してはそれほど耐障害性がありません。実際には、一貫性を犠牲にして特定のシナリオでの可用性を向上させるために、「おおよそのパス数」などの方法がよく使用されます。

(F、すべてを読み取り、一部を書き込む) データの読み取り時 (データの読み取りまたはダイジェストのチェック) にすべてのレプリカにアクセスすることで、読み取り一貫性の問題を軽減できます。これにより、少なくとも 1 つのノード上のデータが更新されている限り、新しいデータがリーダーに表示されるようになります。ただし、この保証はネットワーク分離の場合には機能しません。

(G、マスター-スレーブ) この手法は、アトミック書き込みや競合検出の永続性レベルの読み取り-変更-書き込みを提供するためによく使用されます。このレベルの競合防止を実現するには、集中管理方式またはロックを使用する必要があります。最も簡単な戦略は、マスター/スレーブ非同期レプリケーションを使用することです。特定のデータ項目に対するすべての書き込み操作は中央ノードにルーティングされ、そこで順番に実行されます。この場合、マスターノードがボトルネックになるため、スケーラビリティを確保するには、データを独立したシャード（異なるシャードには異なるマスターがある）に分割する必要があります。

(H、トランザクション読み取りクォーラム書き込みクォーラムおよび読み取り 1 つ書き込みすべて) 複数のレプリカを更新する方法では、トランザクション制御テクノロジを使用して書き込みの競合を回避できます。 よく知られているアプローチは、2 フェーズ コミット プロトコルを使用することです。ただし、コーディネータの障害によりリソースがブロックされる可能性があるため、2 フェーズ コミットは完全に信頼できるわけではありません。 PAXOSコミットプロトコル[20, 21]はより信頼性の高い代替手段ですが、パフォーマンスがわずかに低下します。 これを基に少し前進すると、1 つのレプリカを読み取り、すべてのレプリカを書き込むことができます。この方法では、すべてのレプリカの更新が 1 つのトランザクションにまとめられ、強力なフォールト トレラント一貫性が実現されますが、パフォーマンスと可用性が多少低下します。

上記の分析におけるトレードオフのいくつかを再度述べる価値があります。

• 一貫性と可用性。 CAP 定理によって厳密なトレードオフが与えられています。ネットワーク分離の場合、データベースはデータを集中管理するか、データ損失のリスクを受け入れる必要があります。
• 一貫性とスケーラビリティ。 読み取り/書き込み一貫性の保証によってレプリカ セットのスケーラビリティが低下するにもかかわらず、アトミック書き込みモデルでのみ書き込み競合を比較的スケーラブルな方法で処理できることがわかります。アトミック読み取り-変更-書き込みモデルは、データに一時的なグローバル ロックを追加することで競合を回避します。これは、データまたは操作間の依存関係が、たとえ小規模または短期間であっても、スケーラビリティに悪影響を与える可能性があることを示しています。したがって、データ モデルを慎重に設計し、データを別々のシャードに保存することが、スケーラビリティにとって非常に重要です。
• 一貫性とレイテンシー。前述のように、データベースに強力な一貫性または耐久性を提供する必要がある場合は、すべてのレプリカの読み取り/書き込みを優先する必要があります。しかし、一貫性はリクエストのレイテンシに反比例することは明らかなので、複数のレプリカを使用する方がより合理的なアプローチになります。
• フェイルオーバーと一貫性/スケーラビリティ/レイテンシ。 興味深いことに、フォールト トレランスと一貫性、スケーラビリティ、レイテンシの間のトレードオフはそれほど深刻ではありません。ある程度のパフォーマンスと一貫性を犠牲にすることで、クラスターは最大 50,000 個のノード障害に耐えることができます。このトレードオフは、2 フェーズ コミットと PAXOS プロトコルの違いに明らかです。このようなトレードオフのもう一つの例としては、厳密なセッション処理を使用して「書き込んだものを読み取る」などの特定の一貫性保証を追加することが挙げられますが、これによりフェイルオーバーの複雑さが増します[22]。

#p#

反エントロピープロトコル、噂伝播アルゴリズム

次のシナリオから始めましょう。

ノードは多数あり、各データは複数のノードにコピーされます。各ノードは更新要求を独立して処理でき、各ノードは定期的に他のノードとステータスを同期するため、一定期間後にすべてのコピーの一貫性が保たれる傾向があります。同期プロセスはどのように進行しますか? 同期はいつ開始しますか? 同期するオブジェクトをどのように選択しますか? データをどのように交換しますか? 2 つのノードが常に古いデータを新しいバージョンのデータで上書きするか、両方のバージョンがアプリケーション層で処理するために保持されると想定しています。

この問題は、データの一貫性維持やクラスター ステータスの同期 (クラスター メンバー情報の伝播など) などのシナリオでよく発生します。この問題は、データベースを監視し、同期計画を策定するコーディネーターを導入することで解決できますが、分散型データベースの方が耐障害性が高くなります。分散化への主なアプローチは、慎重に設計された感染プロトコル[7]を利用することです。これは比較的単純ですが、良好な収束時間を提供し、任意のノードの障害やネットワークの分離を許容できます。伝染アルゴリズムには多くの種類がありますが、NoSQL データベースで使用されるため、ここでは反エントロピー プロトコルのみに焦点を当てます。

アンチエントロピー プロトコルでは、同期は固定スケジュールに従って実行され、各ノードは定期的に別のノードを選択してランダムに、または差異を排除するための何らかのルールに従ってデータを交換し、アンチエントロピー プロトコルには、プッシュ、プル、ハイブリッドの 3 種類があります。プッシュ プロトコルの原理は、単にランダムにノードを選択し、そのノードにデータ ステータスを送信することです。実際のアプリケーションでは、すべてのデータをプッシュするのは愚かなことなので、ノードは通常、次の図に示すように動作します。

ノード A は同期イニシエーターとして、A 上のデータのフィンガープリントを含むデータ サマリーを準備します。ノード B はサマリーを受信した後、サマリー内のデータとローカル データを比較し、データの差異のサマリーを A に返します。 ***、A は B に更新を送信し、B はデータを更新します。上の図に示すように、プル プロトコルとハイブリッド プロトコルは似ています。

アンチエントロピー プロトコルは、十分に優れた収束時間とスケーラビリティを提供します。下の図は、100 ノードのクラスター全体に更新を伝播するシミュレーションを示しています。各反復では、各ノードはランダムに選択された 1 つのピア ノードのみに接続します。

プル法はプッシュ法よりも収束性が優れていることがわかり、これは理論的に証明されている[7]。さらに、プッシュ方式では「収束テール」という問題があります。何度も繰り返した後、ほぼすべてのノードが走査されますが、影響を受けないノードがまだいくつか残っています。単純なプッシュ方式とプル方式と比較して、ハイブリッド方式の方が効率的なので、実用的なアプリケーションでは通常、ハイブリッド方式が使用されます。平均遷移時間はクラスター サイズの対数関数として増加するため、反エントロピーはスケーラブルです。

これらの技術は単純に見えますが、さまざまな制約下でのアンチエントロピー プロトコルのパフォーマンスに焦点を当てた研究はまだ数多く行われています。そのうちの1つは、より効率的な構造を通じてランダム選択の代わりにネットワークトポロジを使用するものである[10]。ネットワーク帯域幅が制限されている場合は伝送速度を調整したり、高度なルールを使用して同期するデータを選択したりします[9]。ダイジェスト計算にも課題がありますが、データベースはダイジェスト計算を支援するために最近の更新のログを保持しています。

最終的に一貫性のあるデータ型

前のセクションでは、2 つのノードが常にデータのバージョンをマージすると想定しました。しかし、更新の競合を解決するのは簡単ではなく、すべてのレプリカを最終的に意味的に正しい値に到達させることは驚くほど困難です。よく知られている例としては、Amazon Dynamoデータベースで削除されたエントリが再び現れるというケースがある[8]。

この問題を説明するために、次のような例を考えてみましょう。データベースは論理的にグローバルなカウンターを保持しており、各ノードはカウントを増減できます。各ノードは独自の値をローカルに維持できますが、これらのローカルカウントを単純な加算と減算で結合することはできません。次のような例を考えてみましょう。3 つのノード A、B、C があり、それぞれが追加操作を実行します。 A が B から値を取得してそれをローカル コピーに追加し、次に C が B から値を取得し、次に C が A から値を取得すると、C*** の値は 4 になりますが、これは誤りです。この問題の解決策は、ベクトルクロック[19]に似たデータ構造を使用して、各ノード[1]に1組のカウンターを維持することです。

1 クラス Counter { 2 int[] plus 3 int[] minus 4 int NODE_ID 5 6 increment() { 7 plus[NODE_ID]++ 8 } 9 10 decrement() { 11 minus[NODE_ID]++ 12 } 13 14 get() { 15 return sum(plus) – sum(minus) 16 } 17 18 merge(Counter other) { 19 for i in 1..MAX_ID { 20 plus[i] = max(plus[i], other.plus[i]) 21 minus[i] = max(minus[i], other.minus[i]) 22 } 23 } 24 }

Cassandraはカウントに同様のアプローチを使用しています[11]。状態ベースまたは操作ベースのレプリケーション理論を使用して、より複雑な最終的に一貫性のあるデータ構造を設計することもできます。例えば、[1]では次のような一連のデータ構造について言及されています。

• カウンター（加算と減算の演算）
• コレクション（追加および削除操作）
• グラフ（エッジまたは頂点の追加、エッジまたは頂点の削除）
• リスト（特定の位置に挿入、または特定の位置から削除）

最終的に一貫性のあるデータ型は、通常、機能が制限されており、追加のパフォーマンス オーバーヘッドが発生します。

#p#

データの配置

このセクションでは、分散データベース内のデータの配置を制御するアルゴリズムに焦点を当てます。これらのアルゴリズムは、データ項目を適切な物理ノードにマッピングし、ノード間でデータを移行し、メモリなどのリソースをグローバルに割り当てる役割を担います。

バランスの取れたデータ

まず、クラスター ノード間でシームレスなデータ移行を実現するシンプルなプロトコルから始めます。これは、クラスターの拡張 (新しいノードの追加)、フェイルオーバー (一部のノードがダウン)、データのバランス調整 (データがノード間で均等に分散されていない) などのシナリオでよく発生します。下の図 A のシナリオに示すように、3 つのノードがあり、データは 3 つのノードにランダムに分散されています (データがすべてキー値型であると想定)。

データベースが内部データ バランシングをサポートしていない場合は、上の図 B に示すように、各ノードにデータベース インスタンスを公開する必要があります。これには、図 C に示すように、手動でのクラスター拡張、移行するデータベース インスタンスの停止、新しいノードへの転送、新しいノードでの起動が必要です。データベースは各レコードを監視できますが、MongoDB、Oracle Coherence、開発中のRedis Clusterなど、多くのシステムでは、依然として自動バランス調整テクノロジが使用されています。つまり、データはシャードに分割され、各データ シャードは効率性を考慮して移行の最小単位として使用されます。当然、シャードの数はノードの数よりも多くなり、データ シャードはノード間で均等に分散されます。データ シャードを移行するときにクライアントのデータをノード間でリダイレクトする単純なプロトコルに従うことで、シームレスなデータ移行を実現できます。次の図は、Redis クラスターに実装された get(key) ロジックのステート マシンを示しています。

各ノードはクラスター トポロジを認識しており、任意のキーを対応するデータ シャードにマップし、データ シャードをノードにマップできることが前提となります。ノードは、要求されたキーがローカル シャードに属していると判断した場合、ローカルで検索します (上図の上部のボックス)。ノードは、要求されたキーが別のノード X に属していると判断した場合、*** リダイレクト コマンドをクライアントに送信します (上図の下のボックス)。 ***リダイレクトとは、クライアントがシャードとノード間のマッピングをキャッシュできることを意味します。シャード移行が進行中の場合、移行元ノードと移行先ノードは対応するシャードをマークし、シャード データを 1 つずつロックしてから、移行を開始します。移行元のノードは、まずローカルでキーを探します。見つからない場合は、キーが移行されたと想定して、クライアントを移行元のノードにリダイレクトします。このリダイレクトは 1 回限りのアクションであり、キャッシュできません。移行ノードはリダイレクトをローカルで処理しますが、通常のクエリは移行が完了する前に *** によってリダイレクトされます。

動的環境におけるデータのシャーディングとレプリケーション

私たちが懸念しているもう 1 つの問題は、レコードを物理ノードにマッピングする方法です。より直接的な方法は、キーの範囲が 1 つのノードに対応するように、各範囲のキーとノード間のマッピング関係を記録するテーブルを使用するか、キーのハッシュ値とノードの数を取得して取得した値をノード ID として使用することです。ただし、ハッシュ係数方式は、クラスターが変更された場合にはあまり役に立ちません。ノードを追加または削減すると、クラスター内のデータが完全に並べ替えられるためです。これにより、レプリケーションと障害回復が困難になります。

レプリケーションとフェイルオーバーの観点からこれを強化する方法は多数あります。最も良いのは一貫性のあるハッシュです。インターネット上にはすでにコンシステント ハッシュに関する紹介が多数あるため、ここでは完全性を保つために基本的な紹介のみを行います。次の図は、コンシステント ハッシュの基本原理を示しています。

一貫性のあるハッシュは、基本的にはキーと値のマッピング構造であり、キー (通常はハッシュ化) を物理ノードにマッピングします。ハッシュ後のキーの値空間は、順序付けられた固定長のバイナリ文字列です。当然、この範囲の各キーは、図 A の 3 つのノード A、B、C のいずれかにマッピングされます。レプリカのレプリケーションでは、値空間がリング状に閉じられ、図 B に示すように、すべてのレプリカが適切なノードにマップされるまでリングが時計回りに移動します。つまり、Y はノード B の範囲内にあるためノード B に配置され、最初のレプリカは C に、2 番目のレプリカは A に配置する必要があります。

この構造の利点は、ノードが追加または削除されたときに、隣接する領域のデータのみが再バランス調整されることです。図 C に示すように、ノード D を追加すると、データ項目 X にのみ影響し、Y には影響しません。同様に、ノード B を削除すると (またはその障害)、Y と X のレプリカにのみ影響し、X 自体には影響しません。しかし、参考文献[8]で述べられているように、このアプローチには利点だけでなく欠点もあります。リバランスの負担は、大量のデータを移動する隣接ノードによって負わされることになります。この問題は、図 D に示すように、各ノードを 1 つの範囲ではなく複数の範囲にマッピングすることで、ある程度軽減できます。これは、データの再バランス調整時に過度の負荷集中を回避しながら、モジュールベースのマッピングと比較してバランス調整操作の合計数を適度に低く抑えるトレードオフです。

大規模クラスターの完全かつ一貫性のあるハッシュ リングを維持するのは簡単ではありません。比較的小規模なデータベース クラスターの場合、これは問題にはなりません。ピアツーピア ネットワークでデータ配置とネットワーク ルーティングを組み合わせる方法を研究することは興味深いことです。良い例は Chord アルゴリズムです。これは、単一のノードを検索する効率のためにリングの整合性を犠牲にします。 Chord アルゴリズムも、キーをノードにマッピングするリングの考え方を使用しており、この点ではコンシステント ハッシュと非常によく似ています。違いは、特定のノードが短いリストを維持し、リング上のリスト内のノードの論理的な位置が指数関数的に増加することです (下の図を参照)。これにより、バイナリ検索を使用して、わずか数回のネットワーク ホップでキーを見つけることが可能になります。

この図は 16 個のノードのクラスターを示しており、ノード A がノード D に配置されたキーを検索する方法を示しています。 (A) はルートを示し、(B) はノード A、B、C のリングのローカル イメージを示します。分散システムにおけるデータ複製の詳細については[15]を参照してください。

#p#

複数の属性によるデータの分割

一貫性のあるハッシュのデータ配置戦略は、データが主キーによってのみアクセスされる場合は効果的ですが、複数の属性に基づいてクエリを実行する必要がある場合は、状況がはるかに複雑になります。シンプルなアプローチ (MongoDB で使用) は、他の属性を考慮せずに主キーを使用してデータを分散することです。この結果、主キーに基づくクエリは適切なノードにルーティングできますが、他のクエリの処理にはクラスター内のすべてのノードをトラバースする必要があります。クエリ効率の不均衡により、次の問題が発生します。

各データに複数の属性と対応する値が含まれるデータセットがあります。任意の数の属性を持つクエリが、実行のためにできるだけ少ないノードに割り当てられるようにするデータ分散戦略はありますか?

HyperDex データベースが解決策を提供します。基本的な考え方は、各属性を多次元空間内の軸と見なし、空間内の領域を物理ノードにマッピングすることです。クエリは、空間内の複数の隣接する領域で構成されるハイパープレーンにマッピングされるため、これらの領域のみがクエリに関連します。参考文献[6]の例を見てみましょう。

各データはユーザー情報であり、名、姓、電話番号の 3 つの属性を持ちます。これらの属性は 3 次元空間として表示され、各象限を物理ノードにマッピングすることが実行可能なデータ分散戦略です。 「First Name = John」のようなクエリは、4 つの象限を通過する平面に対応します。つまり、このクエリの処理には 4 つのノードのみが参加します。 2 つの属性制限を持つクエリは、上の図に示すように、2 つの象限を通る直線に対応するため、処理には 2 つのノードのみが関与します。

このアプローチの問題点は、属性の数に応じて空間象限が指数関数的に増加することです。その結果、属性制約が少数のクエリが、多くの空間領域、つまり多くのサーバーに投影されることになります。データ全体を多次元空間にマッピングするのではなく、属性が多いデータ項目を比較的属性の少ない複数のサブ項目に分割し、各サブ項目を独立したサブスペースにマッピングすると、この問題をある程度軽減できます。

これにより、クエリとノードのマッピングが改善されますが、この場合、データが複数の独立したサブスペースに分散され、各サブスペースが複数の物理ノードに対応するため、クラスター調整の複雑さが増します。データを更新するときは、トランザクションの問題を考慮する必要があります。参考文献[6]には、この技術に関するより詳しい情報と実装の詳細が記載されている。

パッシベーションコピー

一部のアプリケーションには強力なランダム読み取り要件があり、すべてのデータをメモリに保存する必要があります。この場合、データをシャーディングし、マスター ノードとスレーブ ノード間で各シャードを複製するには、各データをマスター ノードとスレーブ ノードの両方にコピーする必要があるため、通常、2 倍以上のメモリが必要になります。マスターノードに障害が発生した場合に代替として機能するには、スレーブノードのメモリサイズがマスターノードと同じである必要があります。ノードに障害が発生した場合にシステムが短時間の中断やパフォーマンスの低下を許容できる場合は、シャーディングは必要ありません。

次の図は、4 つのノードに 16 個のシャードがあり、各シャードのコピーがメモリ内に 1 つ、ディスク上に 1 つあることを示しています。

灰色の矢印はノード 2 のシャード レプリケーションを強調表示します。他のノード上のシャードも同様に複製されます。赤い矢印は、ノード 2 に障害が発生した場合にレプリカがメモリにロードされる方法を示しています。クラスター内でレプリカが均一に分散されているということは、ノード障害が発生した場合にアクティブ化されるレプリカを格納するために、少量のメモリのみを予約する必要があることを意味します。上の図では、クラスターは単一ノードの障害に耐えるためにメモリの 1/3 のみを予約しています。レプリカのアクティブ化 (ハードディスクからメモリへのロード) には時間がかかるため、復元されるデータのパフォーマンスが一時的に低下したり、サービスが中断されたりする可能性があることに注意することが重要です。

#p#

システム調整

このセクションでは、システム調整に関連する 2 つの手法について説明します。分散調整は比較的大きな分野であり、何十年にもわたって多くの人々が徹底的な研究を行ってきました。この記事では、実用化されている 2 つの技術についてのみ説明します。分散ロック、コンセンサスプロトコル、その他の基本的な技術に関する情報は、多くの書籍やオンラインリソースで見つけることができます。また、参考文献[17、18、21]を参照することもできます。

障害検出

障害検出は、あらゆるフォールト トレラント分散システムの必須機能です。実際、すべての障害検出プロトコルはハートビート通信メカニズムに基づいています。原理は非常に単純です。監視対象コンポーネントは、定期的にハートビート情報を監視プロセスに送信します（または、監視プロセスが監視対象コンポーネントをポーリングします）。一定期間ハートビート情報が受信されない場合は、無効であると見なされます。さらに、真に分散されたシステムには、他の機能要件もいくつか必要です。

適応型。障害検出では、一時的なネットワーク障害や遅延、およびクラスター トポロジ、負荷、帯域幅の変化に対処できる必要があります。しかし、これは非常に困難です。長時間応答しないプロセスが本当に障害を起こしているかどうかを判断する方法がないためです。したがって、障害検出では、障害識別時間 (実際の障害を特定するのにかかる時間、つまり、プロセスが応答を失ってからどのくらいの時間が経過すると障害が起きたと判断されるか) と誤報率の重要性を比較検討する必要があります。このトレードオフ要因は動的かつ自動的に調整できる必要があります。

柔軟性。一見すると、障害検出には、監視対象のプロセスが正常に動作しているかどうかを示すブール値を出力することだけが必要ですが、実際のアプリケーションではこれでは不十分です。参考文献[12]のMapReduceに似た例を見てみましょう。マスター ノードと複数のワーカー ノードで構成される分散アプリケーションがあります。マスター ノードはジョブ リストを維持し、リスト内のジョブをワーカー ノードに割り当てます。マスターノードは、さまざまなレベルの障害を区別できます。マスターノードはワーカーノードがクラッシュしたと疑う場合、このノードにジョブを割り当てなくなります。次に、時間が経過してもノードのハートビート情報が受信されない場合は、マスターノードはこのノードで実行されているジョブを他のノードに再割り当てします。 ***、マスターノードはノードに障害が発生したことを確認し、関連するすべてのリソースを解放します。

スケーラビリティと堅牢性。システム機能としての障害検出は、システムの成長に合わせて拡張できる必要があります。堅牢で一貫性がある必要があります。つまり、通信障害が発生した場合でも、システム内のすべてのノードが一貫したビューを持つ必要があります (つまり、すべてのノードがどのノードが利用できないか、どのノードが利用できるかを認識し、ノードの認識が互いに矛盾しないようにする必要があります。また、一部のノードが特定のノード A が利用できないことを認識している一方で、他のノードが認識していないという状況があってはなりません)。

いわゆる累積障害検出器[12]は最初の2つの問題を解決でき、Cassandra[16]はこれにいくつかの修正を加えて実稼働に適用しました。基本的なワークフローは次のとおりです。

検出器は、監視対象リソースごとにハートビート情報の到着時間 Ti を記録します。

統計予測範囲内での到着時間の平均と分散を計算します。

到着時間の分布がわかっていると仮定すると (下の図には正規分布の式が含まれています)、ハートビート遅延の確率 (現在の時刻 t_now と最後の到着時刻 Tc の差) を計算し、この確率を使用して障害が発生したかどうかを判断できます。 [12]で示唆されているように、対数関数を使用して調整することで使いやすさを向上させることができます。この場合、出力 1 は誤判定 (ノードが故障する) の確率が 10% であることを意味し、2 は 1% を意味します。

監視エリアは重要度に応じて階層的に編成され、各エリアは噂伝播プロトコルまたは中央フォールトトレラントデータベースを介して同期されます。これにより、スケーラビリティ要件を満たし、ハートビート情報がネットワークに溢れるのを防ぐことができます[14]。これは次の図に示されています (6 つの障害検出器は 2 つのゾーンを形成し、噂伝播プロトコルまたは ZooKeeper などの堅牢性ライブラリを介して相互に通信します)。

コーディネーター選挙

コーディネータの選択は、強力な一貫性を備えたデータベースにとって重要な技術です。まず、マスタースレーブシステムにおけるマスターノードの障害回復を組織化できます。 2 番目に、ネットワークが分離した場合に、書き込みの競合を回避するために少数のノードを切断することができます。

Bully アルゴリズムは、比較的単純なコーディネータ選出アルゴリズムです。 MongoDB はこのアルゴリズムを使用してレプリカ セット内のプライマリを決定します。 Bully アルゴリズムの主なアイデアは、クラスターの各メンバーが自分がコーディネーターであることを宣言し、他のノードに通知できることです。他のノードは、この要求を受け入れるか、拒否してコーディネーターの競争に参加するかを選択できます。他のすべてのノードによって受け入れられたノードだけがコーディネーターになることができます。ノードはいくつかの属性を使用して、誰が勝つかを決定します。このプロパティは、静的 ID または最新のトランザクション ID などの更新されたメトリック (最速のノードが優先) にすることができます。

次の例は、bully アルゴリズムの実行プロセスを示しています。静的 ID をメトリックとして使用すると、ID 値が大きいノードが勝ちます。

1. 最初、クラスターには 5 つのノードがあり、ノード 5 が認識されたコーディネーターです。
2. ノード 5 がクラッシュし、ノード 2 と 3 が同時にこれを検出したとします。 2 つのノードがキャンペーンを開始し、ID が大きいノードにキャンペーン メッセージを送信します。
3. ノード 4 はノード 2 と 3 を削除し、ノード 3 はノード 2 を削除しました。
4. このとき、ノード 1 はノード 5 の障害を検出し、より大きな ID を持つすべてのノードに選出情報を送信します。
5. ノード 2、3、および 4 はすべてノード 1 を排除しました。
6. ノード 4 はノード 5 に選択情報を送信します。
7. ノード 5 は応答しないため、ノード 4 は自身が選出されたことを宣言し、このニュースを他のノードに通知します。

コーディネーター選出プロセスでは、参加ノードの数をカウントし、クラスター内のノードの少なくとも半数が選出に参加するようにします。これにより、ネットワークが分離した場合に、一部のノードのみがコーディネーターを選出できるようになります (ネットワークが互いに接続されていない複数のエリアに分割されている場合、コーディネーターの選出では、必然的に、そのエリアで使用可能なノードの数がクラスター内の元のノード数の半分を超えている限り、比較的ノード数の多いエリアのコーディネーターが選択されます。クラスターが複数のブロックに分離され、どのブロックにも元のノード数の半分を超えるノードがない場合は、コーディネーターを選出できません。もちろん、この場合、クラスターが引き続きサービスを提供できるとは期待しないでください)。

オリジナルリンク: http://www.liuhaihua.cn/archives/86957.html