1 コンセプト 1.1 モデル ノード 特定のエンジニアリング プロジェクトでは、ノードは多くの場合、オペレーティング システム上のプロセスです。この記事のモデルでは、ノードは完全かつ分割不可能な全体であると見なされます。プログラム プロセスが実際には比較的独立した複数の部分で構成されている場合、モデル内でプロセスを複数のノードに分割できます。 異常な
1.2 インスタンス レプリカ/コピーとは、分散システム内のデータまたはサービスに提供される冗長性を指します。データ レプリケーションとは、異なるノードに同じデータを保存することを指します。ノードに保存されたデータが失われた場合、レプリカからデータを読み取ることができます。 データ複製は、分散システムがデータ損失の異常を解決する唯一の方法です。別の種類のレプリカはサービス レプリカであり、複数のノードが同じサービスを提供するものです。このサービスは通常、ノードのローカル ストレージに依存せず、必要なデータは通常他のノードから取得されます。 レプリケーション プロトコルは、分散システム全体の理論的な中核です。 レプリカの一貫性 分散システムでは、レプリカ制御プロトコルを使用して、システム内の各レプリカから読み取られたデータが特定の制約の下で同じであることを保証します。これをレプリカ一貫性と呼びます。レプリカの一貫性は、特定のレプリカではなく、分散システムを指します。
単調な一貫性: いつでも、特定の更新後にユーザーが特定のデータの値を読み取ると、ユーザーはこの値より古い値を読み取ることはありません。
セッション一貫性は、セッションの概念を導入することで、単調一貫性に基づく制約をさらに緩和します。セッションの一貫性は、単一ユーザーの単一セッション内でのデータの単調な変更のみを保証するものであり、異なるユーザー間または同じユーザーの異なるセッション間の一貫性は保証しません。 実際には、PHP のセッション概念など、セッションの概念に正確に対応するメカニズムが多数存在します。
結果的一貫性システムの場合、ユーザーが常に特定のレプリカのデータを読み取る限り、単調一貫性と同様の効果が得られます。ただし、ユーザーがレプリカの読み取りを変更すると、一貫性は保証されなくなります。
弱一貫性システムは、一般的に実際に使用するのが困難です。弱一貫性システムを使用する場合、アプリケーション側はシステムを利用できるようにするためにより多くの作業を行う必要があります。 1.3 分散システムを測定するための指標
システムの応答遅延とは、システムが特定の機能を完了するまでにかかる時間を指します。 システムの同時実行性とは、システムが特定の機能を同時に完了する能力を指し、通常は QPS (1 秒あたりのクエリ数) で測定されます。 上記の 3 つのパフォーマンス指標は、互いに制限し合うことがよくあります。高いスループットを追求するシステムでは、低レイテンシを実現することが難しい場合が多くあります。システムの平均応答時間が長い場合、QPS を増やすことも困難です。
システムの可用性は、システムのダウンタイムと通常のサービス時間の比率、または特定の機能の失敗数と成功数の比率によって測定できます。可用性は分散の重要な指標であり、システムの堅牢性を測定し、システムのフォールト トレランスを反映します。
分散システムの2つの原則 2.1 データ配信 いわゆる分散システムは、その名前が示すように、複数のコンピューターを使用して、単一のコンピューターでは解決できないコンピューティング、ストレージ、およびその他の問題を共同で解決します。 スタンドアロン システムと分散システムの最大の違いは、問題の規模、つまり計算して保存するデータの量の違いにあります。 分散方式を使用して単一マシンの問題を解決するには、まず、問題を複数のマシンを使用して解決できる分散方式に分解し、分散システム内の各マシンが元の問題のサブセットを担当するようにします。コンピューティングとストレージの両方の入力オブジェクトはデータであるため、分散システムの入力データをどのように分解するかが分散システムの基本的な問題になります。 ハッシュ方式 ハッシュ分散データの欠点も明らかで、最も顕著なのはスケーラビリティの低さです。クラスターのサイズを拡張する必要がある場合は、ほぼすべてのデータを移行して再配布する必要があります。エンジニアリングでは、ハッシュデータを分散させるシステムを拡張する場合、クラスターサイズを指数関数的に拡張し、データに応じてハッシュを再計算することがよくあります。この方法では、拡張を完了するために、元々マシン上にあったデータの半分だけを別の対応するマシンに移行すれば済みます。 ハッシュ方式のスケーラビリティが低いという問題に対処するための 1 つのアイデアは、ハッシュ値を除算係数によって単純にマシンにマッピングするのではなく、対応する関係を専用のメタデータ サーバーによってメタデータとして管理することです。同時に、ハッシュ値のモジュロの数はマシンの数よりも大きいことが多いため、同じマシンが複数のハッシュのモジュロ剰余を担当する必要があります。ただし、大量のメタデータは、より複雑なメカニズムを使用して維持する必要があります。ハッシュ分散データのもう 1 つの欠点は、特定のデータ特徴値のデータが著しく不均一になると、「データ スキュー」問題が発生しやすくなることです。 ハッシュ分散データのもう 1 つの欠点は、特定のデータ特徴値のデータが著しく不均一になると、「データ スキュー」の問題が発生しやすくなることです。 データ範囲による分布 データ範囲による分散は、もう 1 つの一般的なデータ分散方法であり、特性値の範囲に応じてデータを異なる間隔に分割し、クラスター内の各サーバー (グループ) が異なる間隔でデータを処理できるようにします。 エンジニアリングでは、データ移行などの負荷分散操作を容易にするために、各間隔で提供されるデータの量を可能な限り同じにするために、間隔を動的に分割するテクノロジがよく使用されます。ある区間内のデータ量が多い場合、区間を「分割」して、各データ区間内のデータ量が可能な限り比較的一定のしきい値以下に維持されるように、区間を 2 つの区間に分割します。 一般的に、データ分散情報をメモリ内に保持するには、専用サーバーが必要になることがよくあります。このデータ分布情報はメタ情報と呼ばれます。大規模クラスターの場合でも、メタデータの規模が大きいため、単一のコンピューターで独立して維持することはできないため、複数のマシンをメタデータ サーバーとして使用する必要があります。 データ量による分布 データ量分布データは、特定のデータ特性とは関係ありません。代わりに、データは順次増加するファイルと見なされ、ファイルは比較的固定されたサイズに従って複数のデータ ブロック (チャンク) に分割されます。異なるデータ ブロックが異なるサーバーに配布されます。 データ範囲別にデータを分散する場合と同様に、データ量別にデータを分散する場合も、データブロックの具体的な分散を記録し、メタデータ サーバーを使用して分散情報をメタデータとして管理する必要があります。 具体的なデータ内容に依存しないため、データ量によるデータの分散は一般的にデータの偏りの問題がなく、データは常に均等に分割されてクラスターに分散されます。 クラスターを再ロードする必要がある場合は、データ ブロックを移行するだけで実行できます。クラスターの拡張には大きな制限はありません。データベースの一部を新しく追加したマシンに移行するだけで、容量を拡張できます。 データ量によってデータを分割することの欠点は、より複雑なメタデータの管理が必要になることです。範囲別にデータを分散する方法と同様に、クラスターサイズが大きい場合、メタデータの量も大きくなり、メタデータの効率的な管理が新たな課題になります。 一貫性のあるハッシュ コンシステント ハッシュは、エンジニアリングで広く使用されているもう 1 つのデータ分散方法です。コンシステント ハッシュは、もともと P2P ネットワークの分散ハッシュ テーブル (DHT) の共通データ分散アルゴリズムとして使用されていました。 コンシステントハッシュの基本的な方法は、ハッシュ関数を使用してデータまたはデータ特徴のハッシュ値を計算し、ハッシュ関数の出力値ドメインを閉ループにすることです。つまり、ハッシュ関数によって出力される最大値は、最小値の前の値になります。ノードはこのリング上にランダムに分散されており、各ノードはハッシュ値ドメイン全体のデータを時計回りに自分自身から次のノードまで処理する責任を負います。 コンシステント ハッシュ方式では、コンシステント ハッシュ リング上のノードの位置をメタデータとして管理する必要があり、ハッシュを直接使用してデータを配布するよりも複雑になります。ただし、ノードの位置情報にはクラスター内のマシンの規模のみが関連しており、そのメタデータの量は、データ範囲やデータ量によって分散されるデータの量よりもはるかに少ないのが通常です。 この目的のために、一般的な改良アルゴリズムは仮想ノードの概念を導入することです。システムが最初に作成されるときに、多くの仮想ノードが作成されます。仮想ノードの数は、通常、将来のクラスター内のマシンの数よりもはるかに多くなります。仮想ノードは、一貫性のあるハッシュ値ドメイン リング上に均等に分散されます。それらの機能は、基本的な一貫性ハッシュ アルゴリズムのノードの機能と同じです。各ノードに複数の仮想ノードを割り当てます。 データを操作するときは、まずデータのハッシュ値を通じてリング上の対応する仮想ノードを見つけ、次にメタデータを参照して対応する実ノードを見つけます。仮想ノードの改善を使用すると、いくつかの利点があります。 まず、ノードが使用できなくなると、複数の仮想ノードが使用できなくなり、その結果、複数の隣接する実ノードが障害が発生したノードの負荷を負うことになります。同様に、新しいノードが追加されると、複数の仮想ノードを割り当てることができるため、新しいノードは複数の元のノードの負荷に耐えることができます。全体的な視点で見ると、容量拡張時の負荷分散が実現しやすくなります。 レプリケーションとデータ配信 分散システムのフォールト トレランスと可用性の向上の基本的な手段は、レプリカを使用することです。データコピーの配布方法は、主にシステムのスケーラビリティに影響します。基本的なデータ複製戦略は、マシンをユニットとして使用し、複数のマシンが互いのレプリカとして機能し、レプリカ マシン間のデータはまったく同じになることです。この戦略は、上記のさまざまなデータ配布方法に適用できます。非常にシンプルなのが利点ですが、データの回復効率が低く、スケーラビリティが高くないのが欠点です。 より適切なアプローチは、マシンをレプリカ ユニットとして使用するのではなく、データをより適切なデータ セグメントに分割し、そのデータ セグメントをレプリカとして使用することです。 実際には、各データ セグメントのサイズは可能な限り均等にされ、特定のサイズ内で制御されることがよくあります。データ セグメントには、セグメント、フラグメント、チャンク、パーティションなど、さまざまな名前があります。データ セグメントの選択は、データの分散方法に直接関係します。 ハッシュ データ分割方式では、各ハッシュ バケットの後の残りをデータ セグメントとして使用できます。データ セグメントのサイズを制御するために、バケットの数はクラスター サイズよりも大きく設定されることが多いです。データがデータ セグメントに分割されると、レプリカはデータ セグメント単位で管理できるため、レプリカはマシンと厳密に関連付けられなくなり、各マシンが特定のデータ セグメントのレプリカを担当できるようになります。 レプリカの配布がマシンから独立すると、データ損失後の回復効率が非常に高くなります。これは、マシンのデータが失われると、そのマシン上のデータ セグメントのコピーが、少数のレプリカ マシンだけではなく、クラスター全体のすべてのマシンに分散されるため、クラスター全体から同時にデータをコピーして復元でき、クラスター内の各データ ソース マシンは非常に少ないリソースでコピーを作成できるためです。リカバリのデータソースとなるマシンがすべて 1MB/秒に制限されている場合でも、100 台のマシンがリカバリに参加すると、リカバリ速度は 100MB/秒に達します。 さらに、レプリカの配布はマシンから独立しており、クラスターのフォールト トレランスにも役立ちます。マシンがクラッシュした場合、クラッシュしたマシンのレプリカがクラスター全体に分散されているため、クラッシュしたマシンにかかる負荷は自然にクラスター全体に分散されます。 最後に、レプリカの配布はマシンから独立しており、クラスターの拡張にも役立ちます。理論的には、クラスターのサイズが N 台のマシンの場合、新しいマシンが追加されると、新しい負荷分散を実現するために、各マシンから新しいマシンに 1/N ~ 1/N+1 の比率でデータ セグメントを移行するだけで済みます。データはクラスター内の各マシンから移行されるため、データ復旧と同様に効率も高くなります。 エンジニアリングにおいて、データセグメントに完全に従ってレプリカを作成すると、管理する必要があるメタデータのオーバーヘッドが増加し、レプリカのメンテナンスの難易度もそれに応じて増加します。妥協案としては、いくつかのデータ セグメントをデータ セグメント グループにグループ化し、データ セグメント グループの粒度に基づいてコピーを管理するという方法があります。そうすることで、レプリカの粒度をより適切な範囲内で制御できます。 ローカライズされたコンピューティング 分散システムでは、データの分散方法がコンピューティングの分散方法にも深く影響します。分散システムでは、コンピューティング ノードとコンピューティング データを保存するストレージ ノードは、同じ物理マシン上に存在することも、異なる物理マシン上に存在することもできます。 コンピューティング ノードとストレージ ノードが異なる物理マシン上に配置されている場合、計算されたデータはネットワーク経由で転送する必要があります。この方法は非常にコストがかかり、ネットワーク帯域幅がシステム全体のボトルネックになる可能性もあります。 もう 1 つのアプローチは、可能な限りストレージ ノードと同じ物理マシン上のコンピューティング ノードに計算をスケジュールすることです。これは、ローカライズ コンピューティングと呼ばれます。ローカライズされたコンピューティングは、コンピューティング スケジューリングの重要な最適化であり、「モバイル コンピューティングはモバイル データよりも悪い」という重要な分散スケジューリングの考え方を具体化します。 データ配信方法の選択 実際のエンジニアリングの実践では、ニーズと実装の複雑さに応じてデータ配布方法を合理的に選択できます。さらに、データ配布方法は柔軟に組み合わせて使用することができ、多くの場合、さまざまな方法の利点を組み合わせて、全体的に優れた結果を達成します。 例えば、データの偏りの問題を解決するために、ハッシュ分布に基づいてデータ量に応じてデータを分散させる方法を紹介します。データはユーザーIDのハッシュ値に応じて分割されます。特定のユーザー ID のデータ量が特に多い場合、このユーザーのデータは常に特定のマシンに保存されます。このとき、データ量によってデータを分散する方法が導入され、ユーザーデータの量をカウントし、一定のしきい値に従ってユーザーのデータを複数の均一なデータセグメントに分割し、これらのデータセグメントをクラスターに分散します。ほとんどのユーザーのデータ量はしきい値を超えないため、メタデータにはしきい値を超えるユーザーのデータ セグメント分布情報のみを保存し、メタデータのサイズを制御します。ハッシュ分散方式とデータ量に基づくデータ分散方式を組み合わせたこの方式は、実際のシステムで使用され、良好な結果が得られました。 2.2 基本的なコピープロトコル レプリカ制御プロトコルとは、レプリカが特定の可用性と一貫性の要件を満たすように、特定のプロトコル プロセスに従ってレプリカ データの読み取りおよび書き込み動作を制御する分散プロトコルを指します。システムが一定の可用性を持つように、レプリカ制御プロトコルは異常な状態に対して一定の耐障害性を備えている必要があります。同時に、レプリカ制御プロトコルは一定レベルの一貫性を提供できる必要があります。 CAP 原則 (セクション 2.9 で詳細に分析) によれば、強力な一貫性を満たし、ネットワーク異常が発生した場合でも利用できるレプリケーション プロトコルを設計することは不可能です。このため、実際のレプリカ制御プロトコルでは、特定のニーズに応じて、可用性、一貫性、パフォーマンスなどの要素の間で常に妥協が行われます。 レプリカ制御プロトコルは、「集中型レプリカ制御プロトコル」と「分散型レプリカ制御プロトコル」の 2 つのカテゴリに分けられます。 集中コピー制御プロトコル 集中型レプリカ制御プロトコルの基本的な考え方は、中央ノードがレプリカ データの更新を調整し、レプリカ間の一貫性を維持することです。 この図は、集中型レプリケーション プロトコルの一般的なアーキテクチャを示しています。集中型レプリカ制御プロトコルの利点は、プロトコルが比較的単純であり、レプリカ関連の制御がすべて中央ノードによって完了することです。同時実行制御は中央ノードによって完了するため、分散同時実行制御の問題が単一マシン同時実行制御の問題に簡素化されます。 いわゆる同時実行制御とは、複数のノードがレプリカ データを同時に変更する必要がある場合に、「書き込み-書き込み」や「読み取り-書き込み」などの同時実行の競合を解決する必要があることを意味します。スタンドアロン システムでは、同時実行制御にロックなどの方法がよく使用されます。分散同時制御の場合、ロックもよく使用される方法ですが、ロックを統一的に管理する中央ノードがない場合、完全に分散されたロック システムが必要になり、プロトコルが非常に複雑になります。 集中型レプリカ制御プロトコルの欠点は、システムの可用性が集中型ノードに依存することです。中央ノードに異常が発生したり、中央ノードとの通信が中断されたりすると、システムは特定のサービス(通常は少なくとも更新サービス)を失います。したがって、集中型レプリカ制御プロトコルの欠点は、一定のサービスダウンタイムが発生することです。 プライマリセカンダリプロトコル プライマリ-セカンダリ タイプのプロトコルでは、レプリカは 2 つのカテゴリに分けられ、1 つのレプリカのみがプライマリ レプリカとなり、プライマリ以外のレプリカはすべてセカンダリ レプリカとなります。プライマリ レプリカを維持するノードは中央ノードとして機能し、データの更新、同時実行制御、レプリカの一貫性の調整の維持を担当します。 プライマリ-セカンダリ プロトコルは、一般的に、データ更新プロセス、データの読み取り方法、プライマリ レプリカの決定と切り替え、およびデータ同期 (調整) という 4 つの主要なタイプの問題を解決します。 データ更新の基本プロセス
エンジニアリングの実践では、プライマリが同時に他の N 個のレプリカにデータを直接送信する場合、各セカンダリの更新スループットはプライマリの合計出力ネットワーク帯域幅によって制限され、最大値はプライマリ ネットワーク出力帯域幅の 1/N になります。 この問題を解決するために、一部のシステム (GFS など) では、プライマリが最初のセカンダリ コピーに更新を送信し、最初のセカンダリ コピーが 2 番目のセカンダリ コピーに更新を送信するというように、リレー アプローチを使用してデータを同期します。 データ読み取り方法 データの読み取り方法も一貫性に大きく関係します。最終的な一貫性のみが必要な場合は、任意のレプリカから読み取るだけで十分です。 セッションの一貫性が必要な場合は、レプリカのバージョン番号を設定し、更新ごとにバージョン番号を増やし、ユーザーがレプリカを読み取るときにバージョン番号を検証することで、ユーザーが読み取るデータがセッション スコープ内で単調に増加していることを確認できます。プライマリ/セカンダリでさらに難しいのは、強力な一貫性を実現することです。 データ更新プロセスはプライマリによって制御されるため、プライマリレプリカ上のデータは最新である必要があり、プライマリレプリカ上のデータのみが常に読み取られる場合、強力な一貫性を実現できます。プライマリ レプリカが読み取り専用の場合、セカンダリ レプリカは読み取りサービスを提供しません。 実際には、レプリカがマシンにバインドされておらず、データ セグメント単位で維持されている場合、プライマリ レプリカのみが読み取りサービスを提供するため、多くのシナリオでマシン リソースが無駄になりません。 レプリカをクラスター全体に分散します。プライマリもランダムに決定されると仮定すると、各マシンには一部のデータのプライマリ レプリカと他のデータ セグメントのセカンダリ レプリカが存在します。したがって、サーバーは実際には読み取りサービスと書き込みサービスの両方を提供します。 セカンダリ ノードの可用性はプライマリ ノードによって制御されます。プライマリがセカンダリ レプリカの更新に失敗すると、プライマリはセカンダリ レプリカを使用不可としてマークし、ユーザーは使用不可のレプリカを読み取れなくなります。使用できないセカンダリ レプリカは、プライマリとのデータの同期を続行できます。プライマリとのデータ同期が完了すると、プライマリはレプリカを使用可能としてマークできます。 このアプローチにより、プライマリかセカンダリかを問わず、利用可能なすべてのレプリカが読み取り可能になり、一定期間内にセカンダリ レプリカがプライマリと一致する最新の状態に更新されるか、使用不可としてマークされるため、より高い一貫性の要件を満たすことができます。このアプローチでは、中央メタデータ管理システムを利用して、どのレプリカが使用可能で、どのレプリカが使用可能でないかを記録します。ある意味では、このアプローチはシステムの可用性を低下させることによってシステムの一貫性を向上させます。 プライマリレプリカの決定と切り替え プライマリ-セカンダリ プロトコルでは、プライマリ レプリカをどのように決定するかがもう 1 つの中心的な問題です。特に、元のプライマリ レプリカが配置されているマシンがクラッシュした場合は、セカンダリ レプリカが新しいプライマリ レプリカになるようにプライマリ レプリカを切り替える何らかのメカニズムが必要になります。 通常、プライマリ・セカンダリ型の分散システムでは、どのレプリカがプライマリであるかという情報はメタデータに属し、専用のメタデータ サーバーによって管理されます。更新操作を実行する場合、まずメタデータ サーバーにクエリを実行してレプリカのプライマリ情報を取得し、さらにデータ更新プロセスを実行します。 分散システムにおけるノード異常の確実な検出には一定の検出時間が必要であるため、そのような検出時間は通常 10 秒レベルです。これはまた、プライマリが異常になると、システムがプライマリへの切り替えを開始するまでに最大 10 秒の検出時間がかかることを意味します。この 10 秒間、プライマリが存在しないため、システムは更新サービスを提供できません。システムがプライマリ コピーのみを読み取ることができる場合、この期間中は読み取りサービスを提供することもできません。このことから、プライマリ・バックアップ型レプリカ・プロトコルの最大の欠点は、プライマリの切り替えによって発生する一定のサービス停止時間であることがわかります。 データ同期 不整合のあるセカンダリ コピーをプライマリと同期 (調整) する必要があります。 矛盾には、次の 3 つの一般的な形式があります。 1. ネットワークの断片化などの異常により、セカンダリのデータがプライマリのデータより遅れます。 2 番目に、特定のプロトコルでは、セカンダリ上のデータがダーティな場合があり、破棄する必要があります。いわゆるダーティ データとは、プライマリ コピーでは特定の更新操作が実行されないが、セカンダリ コピーでは不要な変更操作が実行され、セカンダリ コピーでデータ エラーが発生することです。 3. セカンダリは、データがまったくない新しく追加されたレプリカであり、他のレプリカからデータをコピーする必要があります。 セカンダリ データが遅れている最初のケースでは、一般的な同期方法は、プライマリで操作ログ (通常は REDO ログ) を再生して、プライマリの更新の進行状況に追いつくことです。 ダーティ データの場合、ダーティ データを生成しない分散プロトコルを設計する方がよいアプローチです。プロトコルがダーティ データを生成する可能性がある場合、ダーティ データを生成する確率を非常に低いレベルにまで下げる必要があります。そうすることで、ダーティ データが発生した場合、ダーティ データを含むコピーを単純に破棄することができ、コピーにデータが存在しないのと同じになります。 さらに、一部の UNDO ログベースの方法は、ダーティ データを削除するように設計できます。セカンダリ コピーにデータがまったくない場合は、プライマリ コピーからデータを直接コピーするのが一般的です。この方法は、ログを再生して更新の進行状況を追跡するよりもはるかに高速です。ただし、プライマリ レプリカは、データをコピーするときに更新サービスを継続的に提供できる必要があるため、プライマリ レプリカでスナップショット機能をサポートする必要があります。つまり、ある瞬間のレプリカ データのスナップショットが取得され、そのスナップショットがコピーされます。コピーが完了したら、ログを再生することでスナップショット作成後の更新操作を追跡します。 分散型レプリカ制御プロトコル 分散レプリカ制御プロトコルには中央ノードがありません。プロトコル内のすべてのノードは完全に平等であり、ノードは平等な協議を通じて合意に達します。そのため、分散型プロトコルでは、集中型ノードの異常によってサービスが停止するなどの問題がありません。 分散型プロトコルの最大の欠点は、プロトコルのプロセスが通常複雑であることです。特に、分散プロトコルが強力な一貫性を実現する必要がある場合、プロトコルのプロセスは複雑になり、理解しにくくなります。プロセスの複雑さにより、分散型プロトコルの効率やパフォーマンスは、集中型プロトコルよりも一般的に低くなります。不適切な類推としては、集中型レプリカ制御プロトコルが独裁システムに似ているというものがあります。このシステムは効率的ですが、中央ノードに大きく依存します。中央ノードに異常が発生すると、システムに大きな影響が生じます。分散型レプリカ制御プロトコルは、民主主義システムに似ています。ノードは集団で交渉するため非効率的ですが、個々のノードの異常がシステム全体に大きな影響を与えることはありません。 2.3 リースの仕組み リース メカニズムは最も重要な分散プロトコルであり、さまざまな実用的な分散システムで広く使用されています。 リースベースの分散キャッシュシステム 基本的な問題の背景は次のとおりです。分散システムには、システムのメタデータであるデータを保存および管理する中央サーバー ノードが存在します。システム内の他のノードは、中央サーバー ノードにアクセスして、そのメタデータを読み取ったり変更したりします。 システム内のさまざまな操作はメタデータに依存しているため、メタデータを読み取る各操作が中央サーバーノードにアクセスすると、中央サーバーノードのパフォーマンスがシステムのボトルネックになります。このため、メタデータ キャッシュは各ノードにメタデータ情報をキャッシュするように設計されており、これにより中央サーバー ノードへのアクセスが削減され、パフォーマンスが向上します。 一方、システムの正しい動作はメタデータの正確性に厳密に依存しており、各ノードにキャッシュされたデータが中央サーバーのデータと常に一致していること、およびキャッシュ内のデータが古くてダーティなデータであってはならないことが求められます。最後に、設計されたキャッシュ システムは、ノードのクラッシュ、ネットワークの中断、その他の異常を可能な限り最大限に処理し、システムの可用性を最大化できる必要があります。 この目的のために、リースメカニズムを使用してキャッシュシステムが設計されており、その基本原理は次のとおりです。 中央サーバーは各ノードにデータを送信するときに、ノードにリースも発行します。各リースには、クレジットカードの有効期限と同様に有効期限があります。リースの有効期限は通常、12:00:10 などの特定の時点です。実際の時間がこの時点を超えると、リースは期限切れになります。このように、リースの有効期間は、ノードがリースを受信した時間とは関係ありません。ノードがリースを受信した時点でリースが期限切れになっている可能性があります。ここではまず、中央サーバーと各ノードのクロックが同期されていると仮定します。クロックの非同期がリースに与える影響については、次のセクションで説明します。中央サーバーが発行するリースの意味は、リースの有効期間中、中央サーバーは対応するデータの値が変更されないことを保証することです。したがって、ノードはデータとリースを受信した後、データをローカル キャッシュに追加します。対応するリースがタイムアウトすると、ノードは対応するローカル キャッシュ データを削除します。データを変更する場合、中央サーバーはまずすべての新しい読み取り要求をブロックし、データに対して以前に発行されたすべてのリースの有効期限が切れるまで待ってから、データの値を変更します。 リースキャッシュに基づいて、クライアントノードはメタデータを読み取ります。
上記のメカニズムにより、各ノード上のキャッシュが中央サーバー上のセンターと常に一致することが保証されます。これは、中央サーバー ノードがデータを送信する際に、対応するリースをノードに付与するためです。リースの有効期間中、サーバーはデータを変更しないため、クライアント ノードはリースの有効期間中、データを安全にキャッシュできます。上記のリースのメカニズムのフォールト トレランスの鍵は、サーバーがデータとリースを送信すると、クライアントがそれを受信するかどうか、クライアントがその後クラッシュするかどうか、またはその後のネットワークが正常であるかどうかに関係なく、サーバーはリースがタイムアウトするのを待つだけで、対応するクライアント ノードがデータをキャッシュし続けないようにし、キャッシュの一貫性を損なうことなくデータを変更できることです。 上記の基本的なプロセスにはパフォーマンスと使いやすさに関する問題がいくつかありますが、簡単に最適化および変更できます。最適化ポイント 1: メタデータを変更する場合、サーバーは最初にすべての新しい読み取り要求をブロックする必要があり、その結果、読み取りサービスが利用できなくなります。これは、新しいリースの発行によって新しいクライアント ノードがリースとキャッシュ データを常に保持し、「ライブロック」が形成されるのを防ぐためです。最適化の方法は非常に簡単です。サーバーがデータ変更プロセスに入った後、読み取り要求を受信すると、データを返すだけで、リースは発行しません。その結果、変更プロセスの実行中に、クライアントはメタデータを読み取ることはできますが、メタデータをキャッシュすることはできません。さらに最適化されるのは、変更プロセスに入るときに、サーバーによって発行されたリースの有効期間が、発行されたリースの最大有効期間として選択されることです。この方法では、サーバーが変更プロセスに入った後もクライアントはメタデータをキャッシュし続けることができますが、新しいリースの発行により、すべてのリースの有効期限が切れるまでのサーバーの待機時間は延長されません。 最後に、=cache メカニズムとマルチコピー メカニズムの違いについて説明します。キャッシュ メカニズムは、複数のノードにデータのコピーを保存するという点で、マルチコピー メカニズムに似ています。しかし、キャッシュのメカニズムははるかに単純です。キャッシュされたデータはいつでも削除および破棄することができ、キャッシュにアクセスした結果、データを読み取るためにデータ ソースにアクセスするだけで済みます。ただし、コピーのメカニズムは異なります。コピーは任意に破棄することはできません。コピーが失われるたびに、サービスの品質が低下します。コピー数が一定レベルまで減少すると、多くの場合、サービスは利用できなくなります。 リースの仕組みの分析 リースの定義: リースは、発行者によって一定の有効期間にわたって付与されるコミットメントです。発行者がリースを発行すると、受取人がリースを受け取ったかどうか、また受取人がその後どのような状態にあるかに関係なく、リースが期限切れにならない限り、発行者はその約束を厳守する必要があります。一方、受領者はリースの有効期間中は発行者の約束を使用することができますが、リースの有効期限が切れると、受領者は発行者の約束を継続して使用することはできません。 リース メカニズムは高い耐障害性を備えています。まず、有効期間を導入することで、リース メカニズムはネットワークの異常に対して非常に耐性を持つようになります。リース発行プロセスは、ネットワーク上の一方向通信のみに依存します。受信者が発行者にメッセージを送信できない場合でも、リースの発行には影響しません。 リースの有効期間は固定された時点であるため、リースのセマンティクスはリースが送信される特定の時間とは関係がなく、発行者から受信者に同じリースを繰り返し送信できます。発行者がリースの送信に時々失敗する場合でも、発行者はリースを再送信するだけで問題を解決できます。リースが受信者によって正常に受け入れられると、その後のリース メカニズムはネットワーク通信に依存せず、ネットワークが完全に切断されてもリース メカニズムは影響を受けません。 さらに、リース メカニズムはノード障害に対する耐性が向上します。発行者がダウンした場合、ダウンタイムの発行者は通常、以前のコミットメントを変更することができず、リースの正確性に影響を与えません。発行者のマシンが復旧した後、発行者が以前のリース情報を回復すれば、発行者は引き続きリース契約を遵守できます。発行者がリース情報を回復できない場合は、最大リース タイムアウトを待機してすべてのリースを無効にするだけでよく、リース メカニズムが破壊されることはありません。 たとえば、前のセクションのキャッシュ システムの例では、サーバーがダウンすると、メタデータは確実に変更されなくなります。回復後は、最大リース タイムアウトを待つだけで、すべてのノードのキャッシュ情報がクリアされます。 受信者がクラッシュした場合でも、発行者はそれ以上のフォールト トレラント処理を実行する必要はありません。リースの期限が切れるまで待って、約束を撤回するだけです。実際には、これは以前に付与された権限と ID を取り消すことを意味します。最後に、リース メカニズムはストレージに依存しません。発行者は発行したリース情報を保持できるため、有効期間内のリースは、システムがダウンタイムから回復した後も引き続き有効になります。しかし、これはリース メカニズムの最適化にすぎません。前に分析したように、発行者がリース情報を保持しない場合でも、最大リース時間待つことで以前に発行されたすべてのリースを無効にすることができるため、メカニズムが引き続き有効であることが保証されます。 リース メカニズムは有効期間に依存しており、発行者と受信者のクロックが同期されている必要があります。一方、発行者のクロックが受信者のクロックよりも遅い場合、受信者がリースの期限が切れたと見なした場合でも、発行者はリースを有効と見なす可能性があります。受取人は、リースの期限が切れる前に新しいリースを申請することでこの問題を解決できます。一方、発行者のクロックが受信者のクロックよりも速い場合、発行者がリースの有効期限が切れたと判断しても、受信者はリースがまだ有効であると判断します。発行者が他のノードにリースを発行すると、コミットメントが失敗し、システムの正確性に影響を与える可能性があります。このようなクロックの非同期の場合、通常は、リースの有効性に影響を与えないように、発行者の有効期間を受信者の有効期間よりわずかに長く、クロック エラーよりわずかに長く設定します。 リースメカニズムに基づいてノードのステータスを決定する 分散プロトコルは、ノード ステータス認識のグローバルな一貫性に依存します。つまり、ノード Q がノード A が異常であると判断すると、ノード A も異常であると判断する必要があり、その結果、ノード A はプライマリとしての機能を停止して、「デュアル マスター」問題が回避されます。 この問題を解決するには2つの方法があります。まず、設計された分散プロトコルは「デュアルマスター」エラーを許容できます。つまり、ノードステータスのグローバル一貫性に依存しません。または、グローバル一貫性ステータスは完全なネゴシエーションの結果です。 次に、リースの仕組みを活用します。集中型設計を放棄して分散型設計を採用するという最初のアイデアは、このセクションの範囲外です。以下の説明では、リース メカニズムを使用してノードのステータスを決定することに焦点を当てます。 中央ノードは他のノードにリースを送信します。ノードが有効なリースを保持している場合、そのノードは正常にサービスを提供できるとみなされます。例 2.3.1 では、ノード A、B、C は引き続き定期的にハートビートを送信して、自身のステータスを報告します。ハートビートを受信した後、ノード Q はリースを送信し、ノード Q がノード A、B、C のステータスを確認し、リースの有効期間内にノードが正常に動作することを許可することを示します。ノード Q はプライマリ ノードに特別なリースを付与して、そのノードがプライマリとして動作できることを示します。ノード Q が新しいプライマリに切り替えたい場合、以前のプライマリのリースが期限切れになるのを待つだけで、その後は「デュアル マスター」の問題なしに、新しいプライマリ ノードに新しいリースを安全に発行できます。 実際のシステムでは、リースの送信に中央ノードが使用される場合にも大きなリスクがあります。中央ノードがダウンしたり、ネットワークに異常が発生すると、すべてのノードにリースがなくなり、システムの可用性が大幅に低下します。このため、実際のシステムでは常に複数の中央ノードを互いのコピーとして使用し、小さなクラスターを形成します。この小さなクラスターは高い可用性を備えており、外部にリースを発行する機能を提供します。 Chubby と Zookeeper はどちらもこのデザインに基づいています。 リース有効期間の選択 エンジニアリング プロジェクトでは、一般的に選択されるリース期間は 10 秒です。これは検証された経験値であり、実践においては適切な期間を総合的に選択するための参考として使用できます。 2.4 クォーラムメカニズム まず、更新操作 (書き込み) は一連の連続したプロセスであるという点に同意しましょう。更新操作の順序は他のメカニズムによって決定されます (たとえば、プライマリ - セカンダリ アーキテクチャでは、順序はプライマリによって決定されます)。各更新操作は wi で表されます。ここで、i は更新操作の単調に増加するシリアル番号です。 wi が正常に実行されるたびにレプリカ データが変更されます。これは異なるデータ バージョンと呼ばれ、vi で示されます。各レプリカにはデータのすべての履歴バージョンが保存されていると想定します。 すべて書き込み、1 つ読み取り Write-all-read-one (略して WARO) は、最も単純なコピー制御ルールです。名前が示すように、更新中にすべてのコピーが書き込まれます。更新はすべてのコピーで成功した場合にのみ成功したとみなされ、すべてのコピーの一貫性が確保されます。この方法では、データを読み取るときに任意のコピーからデータを読み取ることができます。 更新操作は N 個のレプリカすべてで成功する必要があるため、更新操作は成功することしかできません。したがって、1 つのレプリカに異常が発生すると、更新操作は失敗し、更新サービスは利用できなくなります。更新サービスの場合、レプリカは N 個ありますが、どのレプリカでも異常は許容されません。一方、N 個のレプリカのうち 1 つが正常であれば、システムは読み取りサービスを提供できます。読み取りサービスの場合、レプリカが N 個ある場合、システムは N-1 個のレプリカ異常を許容できます。上記の分析から、WARO 読み取りサービスの可用性は高いが、更新サービスの可用性は高くないことがわかります。レプリカが使用されている場合でも、更新サービスの可用性はレプリカがない場合と同等になります。 定足数の定義 クォーラム メカニズムでは、更新操作 wi が N 個のレプリカのうち W 個で成功すると、その更新操作は「正常に送信された更新操作」と呼ばれ、対応するデータは「正常に送信されたデータ」と呼ばれます。 R>NWとします。更新操作 wi は W 個のレプリカでのみ成功するため、データを読み取るときは、wi によって更新されたデータ vi が読み取れるようにするために、最大 R 個のレプリカを読み取る必要があります。更新 wi が W レプリカで成功した場合、W+R>N なので、任意の R レプリカのセットは成功した W レプリカのセットと交差する必要があり、そのため、R レプリカを読み取ると、wi が更新された後にデータ vi が確実に読み取られます。 図 2-10 に示すように、クォーラム メカニズムの原理は、ヴィンセント図で表すことができます。 システムには 5 つのレプリカがあり、W = 3、R = 3 です。最初は、5 つのレプリカのデータは一貫しており、すべて v1 です。最初の 3 つのレプリカで更新操作 w2 が成功し、レプリカの状況は (v2 v2 v2 v1 v1) になります。 この時点で、3 つのレプリカのセットには必ず v2 が含まれている必要があります。上記の定義では、W = N、R = 1 とすると WARO になります。つまり、WARO はクォーラム メカニズムの特殊なケースです。 WARO の分析と同様に、クォーラム メカニズムの可用性が分析されます。クォーラムパラメータを W+R=N+1 に制限します。更新操作は W 個のレプリカで成功する必要があるため、N-W+1 個のレプリカが異常になると、W 個のレプリカで更新操作は成功せず、更新サービスは利用できなくなります。 一方、N-R+1 個のレプリカが異常になると、W 個のレプリカと交差するレプリカ セットを読み取ることができる保証がなくなり、読み取りサービスの一貫性が低下します。 もう一度強調しておきたいのは、クォーラム メカニズムだけに頼っていては強力な一貫性は保証できないということです。クォーラム機構のみの場合、正常に送信された最新のバージョン番号を特定することは不可能であるため、特定のメタデータ サーバまたはメタデータ クラスタによって最新の送信バージョン番号がメタデータとして管理されていない限り、正常に送信された最新のバージョン番号を特定することは困難です。次のセクションでは、正常に送信された最新のバージョン番号がクォーラム メカニズムのみによって決定できる状況について説明します。 クォーラム メカニズムの 3 つのシステム パラメータ N、W、および R は、システムの可用性を制御し、ユーザーに対するシステムのサービス コミットメントでもあります。データのコピーは最大 N 個ありますが、データの W 個のコピーが正常に更新されると、ユーザーには成功が返されます。高い一貫性要件を持つクォーラム システムの場合、システムは、送信に失敗したデータをいかなる時点でも読み取らないことも保証する必要があります。つまり、読み取られるデータはすべて、W レプリカで正常に送信されたデータです。 正常に送信された最新のデータを読む クォーラム メカニズムでは、N 個のレプリカのうち W 個を正常に更新するだけで済みます。 R レプリカを読み取る場合、正常に送信された最新のデータを読み取ることができます。ただし、失敗した更新が存在するため、R のコピーを単に読み取るだけでは、どのバージョンのデータが最新の送信データであるかを必ずしも判断できるわけではありません。強力な一貫性を持つクォーラム システムの場合、W 個未満のデータがある場合 (X であると想定)、そのバージョンの W 個のレプリカが正常に読み取られるまで他のレプリカの読み取りを続行し、そのデータは正常に送信された最新のデータになります。すべてのレプリカのデータ数が W を満たすのに明らかに不十分な場合、R で 2 番目に大きいバージョン番号を持つレプリカが、正常に送信された最新のレプリカになります。 たとえば、(v2 v1 v1) を読むときは、残りのコピーを読み続けます。読み取られた残りの 2 つのコピーが (v2 v2) の場合、v2 が最後に送信されたコピーです。読み取られた残りの 2 つのコピーが (v2 v1) または (v1 v1) の場合、v1 が正常に送信された最新のバージョンになります。後続の 2 つのコピーのいずれかがタイムアウトするか失敗すると、どのバージョンが正常に送信された最新のバージョンであるかを判断することは不可能になります。 クォーラム メカニズムのみを使用する場合、正常に送信された最新のバージョンを決定するには、最大で R+ (WR-1)=N 個のコピーを読み取る必要があることがわかります。いずれかのコピーに異常がある場合、正常に送信された最新のバージョンを読み取る機能が利用できない場合があります。 実際のプロジェクトでは、クォーラム メカニズムを通じて正常に送信された最新のバージョンが読み取られることを避けるために、他の技術的手段を可能な限り使用する必要があります。たとえば、クォーラム メカニズムをプライマリ - セカンダリ制御プロトコルと組み合わせて使用すると、プライマリを読み取ることで最新のコミット済みデータを読み取ることができます。 クォーラムメカニズムに基づいてプライマリレプリカを選択する データを読み取るときは、一貫性の要件に応じてさまざまなアプローチを使用できます。強力な一貫性で正常に送信された最新のデータをすぐに読み取る必要がある場合は、プライマリ レプリカ上のデータのみを読み取るか、前のセクションの方法を使用して読み取ることができます。 セッションの一貫性が必要な場合は、以前に読み取られたデータのバージョン番号に基づいて、各レプリカを選択的に読み取ることができます。弱い一貫性のみが必要な場合は、任意のレプリカから読み取るように選択できます。 プライマリ-セカンダリ プロトコルでは、プライマリに障害が発生した場合、新しいプライマリを選択する必要があり、その後、セカンダリ レプリカがプライマリとデータを同期します。 通常、新しいプライマリを選択する作業は中央ノードによって完了します。クォーラム メカニズムの導入後、一般的に使用されるプライマリ選択方法は、データの読み取り方法と似ており、つまり、中央ノードが R 個のコピーを読み取り、R 個のコピーの中でバージョン番号が最も高いコピーを新しいプライマリとして選択します。新しいプライマリが少なくとも W 個のレプリカとのデータ同期を完了すると、新しいプライマリとして読み取りおよび書き込みサービスを提供します。 まず、R コピーの中で最もバージョン番号が高いコピーには、正常に送信された最新のデータが含まれている必要があります。さらに、最も高いバージョン番号が正常に送信されたデータであるとは判断できませんが、新しいプライマリはその後、セカンダリとデータを同期するため、このバージョンのコピーの数は W に達し、このバージョンのデータが正常に送信されたデータになります。 たとえば、N=5、W=3、R=3 のシステムでは、ある瞬間のレプリカの最大バージョン番号は (v2 v2 v1 v1 v1) になります。この時点で、v1 はシステム内で最後に正常に送信されたデータであり、v2 は中間状態にある正常に送信されなかったデータです。この時点で元のプライマリコピーが異常であり、中央ノードがプライマリ切り替えを実行していると仮定します。このタイプの「中間」データが「ダーティ データ」として削除されるか、新しいデータとして同期された後に有効になるかは、このデータが新しいプライマリの選択に参加できるかどうかによって完全に決まります。以下では、これら 2 つの状況を個別に分析します。 まず、図 2-12 に示すように、中央ノードが 3 つのレプリカと正常に通信し、読み取られたバージョン番号が (v1 v1 v1) の場合、任意のレプリカがプライマリとして選択されます。新しいプライマリは、正常に送信された最新のバージョンとして v1 を使用し、他のレプリカと同期します。第 1 レプリカと第 2 レプリカでデータを同期する場合、第 1 レプリカと第 2 レプリカのバージョン番号がプライマリよりも大きいため、それらはダーティ データであり、セクション 2.2.2.4 で説明したダーティ データの処理方法で解決できます。 実際には、新しいプライマリは、最後の 2 つのレプリカとの同期を完了した後にデータ サービスを提供して、その後、自身のバージョン番号を v2 に更新することもあります。システムが後続の v2 が前の v2 とまったく同じであることを保証できない場合、新しいプライマリが最初のレプリカと 2 番目のレプリカとデータを同期するときに、データのバージョン番号を比較するだけでなく、更新操作の特定の内容も比較して、同じかどうかを確認する必要があります。 次に、中央ノードが他の 3 つのレプリカと正常に通信し、読み取られたバージョン番号が (v2 v1 v1) の場合、バージョン番号 v2 のレプリカが新しいプライマリとして選択されます。その後、新しいプライマリが他の 2 つのレプリカとのデータ同期を完了すると、v2 を満たすレプリカの数が W に達し、正常に送信された最新のレプリカになります。新しいプライマリは通常の読み取りおよび書き込みサービスを提供できます。 2.5 ログ技術 ログ テクノロジーは、ダウンタイム回復のための主要なテクノロジーの 1 つです。ログ技術はもともとデータベース システムで使用されていました。厳密に言えば、ログ技術は分散システム技術ではありませんが、分散システムの実践では、ログ技術はダウンタイム回復に広く使用されています。 BigTable などのシステムでも、システムのフォールト トレランスをさらに強化するために、分散システムにログを保存します。 REDOログとチェックポイント 高速なスタンドアロン クエリ システムを設計し、すべてのデータをメモリに格納して高速データ クエリを実現し、更新操作が実行されるたびにデータの小さな部分 (キー値内のキーなど) を更新します。現在の問題は、ログ テクノロジを使用してメモリ クエリ システムのクラッシュ回復を実現することです。データベース トランザクションとは異なり、この問題モデルでは、成功したすべての更新操作が有効になります。これは、各データベース トランザクションに 1 つの更新操作のみがあり、各更新操作はすぐにコミットでき、コミットする必要がある (自動コミット) ことに相当します。
更新操作の結果(たとえば、K1=1 に設定した場合は、K1=1 を記録する)をディスク上のログ ファイルに追加形式で書き込みます。 更新によってメモリ内のデータを変更する 更新成功を返す Redo Log プロセスから、Redo は更新操作の結果をログに書き込むことがわかります (この記事では Undo Log については説明していませんが、これが Undo Log との違いの 1 つです)。また、ログ ファイルは順番に書き込まれるため、ディスクなどの順番の書き込みに強いストレージ デバイスではより効率的です。 Redo ログを使用してダウンタイムから回復するのは非常に簡単です。ログを「再生」するだけです。 プロセス 2.5.2: REDO ログ ダウンタイム リカバリ ログ ファイル内の各更新操作の結果を最初から読み取り、その結果を使用してメモリ内のデータを変更します。 また、REDO ログのダウンタイム リカバリ プロセスから、ダウンタイム後にリカバリできるのはログ ファイルに書き込まれた更新結果のみであることもわかります。このため、Redo Log プロセスでは、まずログ ファイルを更新し、次にメモリ内のデータを更新する必要があります。 メモリ内のデータが最初に更新された場合、ユーザーは更新されたデータをすぐに読み取ることができます。メモリの変更が完了してからログを書き込むまでの間にクラッシュが発生した場合、最後の更新操作を復元することはできませんが、ユーザーが以前に更新されたデータを読み取っていた可能性があり、不整合の問題が発生します。
簡略化されたモデルでは、チェックポイント テクノロジのプロセスは、メモリ内のデータを、簡単に再ロードできる方法で完全にディスクにダンプし、ダウンタイム回復中に再生する必要があるログ データを削減することです。 プロセス: チェックポイント
プロセス: チェックポイントベースのダウンタイム回復プロセス ディスクにダンプされたデータをメモリにロードします。 ログ ファイルを後ろから前に向かってスキャンし、最後の「チェック ポイントの終了」ログを探します。 最後の「チェックポイントの終了」ログから最新の「チェックポイントの開始」ログを見つけ、このログ以降のすべての更新操作ログを再生します。 元に戻す/やり直しログなし データがディスク上に保持されている場合、更新のバッチは複数の更新操作で構成され、それらの操作はアトミックに有効になる必要があります。つまり、同時に有効になるか、いずれも有効にならないかのいずれかになります。 0/1 ディレクトリ テクノロジには、ディレクトリ 0 とディレクトリ 1 と呼ばれる 2 つのディレクトリ構造があります。また、現在使用中のディレクトリを記録するマスター レコードと呼ばれる別の構造もあり、これはアクティブ ディレクトリと呼ばれます。マスター レコードは、ディレクトリ 0 またはディレクトリ 1 の使用を記録します。ディレクトリ 0 またはディレクトリ 1 は、ログ ファイル内の各データの場所を記録します。 0/1 ディレクトリのデータ更新プロセスは常に非アクティブ ディレクトリ上で実行されますが、データが有効になる前にマスター レコードの 0 と 1 の値が反転され、マスター レコードが切り替わります。 プロセス: 0/1 ディレクトリデータ更新プロセス
0/1 ディレクトリの更新プロセスは非常に簡単です。 0 ディレクトリと 1 ディレクトリのマスター レコードを切り替えることで、一連の変更をアトミックに行うことができます。 0/1 ディレクトリは、バッチ トランザクション操作のアトミック性を、ディレクトリ手段によるマスター レコードのアトミック スイッチングに帰します。 複数のレコードのアトミック変更は一般に実装が困難ですが、単一のレコードのアトミック変更は多くの場合実現可能であるため、問題の実装の難しさは軽減されます。 0/1ディレクトリの考え方はエンジニアリングで広く使用されており、その形式は上記のプロセスに限定されません。メモリ内の 2 つのデータ構造を切り替えることや、ディスク上の 2 つのファイル ディレクトリを切り替えることなどが考えられます。 2.6 2相コミットプロトコル 2 フェーズ コミット プロトコルは、古典的な強力な一貫性を持つ集中型レプリカ制御プロトコルです。このプロトコルにはエンジニアリング上の多くの問題がありますが、このプロトコルを研究することで、分散システムのいくつかの典型的な問題を理解するのに役立ちます。 プロセスの説明 2 フェーズ コミット プロトコルは、典型的な「集中型コピー制御」プロトコルです。このプロトコルでは、参加ノードは、集中型コーディネーター ノード (コーディネーター) と N 個の参加ノード (参加者) の 2 つのカテゴリに分類されます。各参加ノードは、上記の背景紹介でデータベースのコピーを管理するノードです。 2フェーズコミットの考え方は比較的単純です。最初のフェーズでは、コーディネーターはすべての参加者にトランザクションをコミットできるかどうかを尋ね(参加者に投票を求め)、すべての参加者がコーディネーターに投票します。 第 2 フェーズでは、コーディネーターはすべての参加者の投票結果に基づいてトランザクションをグローバルにコミットできるかどうかを決定し、すべての参加者に決定を実行するように通知します。 2 フェーズ コミット プロセスでは、参加者は投票を変更できません。 2 フェーズ コミット プロトコルがグローバルにコミットされるための前提は、すべての参加者がトランザクションをコミットすることに同意することです。参加者の 1 人がトランザクションの中止に投票した場合、トランザクションは中止される必要があります。 プロセス: 2 フェーズ コミット コーディネーター プロセス
プロセス: 2 フェーズ コミット コーディネーター プロセス
例外処理 ダウンタイムリカバリ
プロトコル分析 2フェーズのコミットプロトコルは、エンジニアリングの実践ではめったに使用されません。主な理由は次のとおりです。
断層の許容度とパフォーマンスを改善できる改善された2フェーズコミットプロトコルがいくつかありますが、そのようなプロトコルはエンジニアリングではまだ使用されておらず、その理論的価値は実際の重要性よりも大きくなります。 2.7 MVCC MVCC(マルチバージョンcocurrentコントロール)テクノロジー。 MVCCテクノロジーはもともとデータベースシステムで提案されていましたが、このアイデアはスタンドアロン分散システムに限定されず、分散システムでも効果的です。 MVCCは、複数のバージョンのデータを使用して同時実行制御を実装するテクノロジーです。基本的なアイデアは、各トランザクションの新しいバージョンのデータを生成することです。データを読み取るときは、データの異なるバージョンを選択して、完全なトランザクション結果を読み取ることができます。 MVCCを使用する場合、各トランザクションは既に効果的なベースバージョンに基づいて更新され、トランザクションは並行して実行できるため、グラフのような構造が生成されます。 基本データのバージョンは1で、2つのトランザクションが同時に生成されます。トランザクションAとトランザクションBの両方のトランザクションは、データを局所的に変更しました(これらの変更はトランザクション自体にのみ表示され、実際のデータに影響しません)。次に、最初にトランザクションAがコミットされ、データバージョン2を生成しました。データバージョン2に基づいて、トランザクションCが開始され、トランザクションCが引き続きコミットされ、データバージョン3を生成しました。最後に、トランザクションBがコミットされました。現時点では、トランザクションBの結果をトランザクションCの結果とマージする必要があります。データの競合がない場合、つまりトランザクションBがトランザクションAとCによって変更された変数を変更していない場合、トランザクションBはコミットできません。 MVCCプロセスは、SVNなどのバージョン制御システムのプロセス、つまりSVNなどのバージョン制御システムがMVCCコンセプトを使用します。実際のデータに影響を与えないために、トランザクションが基本データバージョンに基づいてローカル変更を行う場合、通常、それを行うには2つの方法があります。 1つは、データをベースデータバージョンに完全にコピーして、変更することです。 SVNはこの方法を使用し、SVNのチェックアウトはコピープロセスです。もう1つは、完全なデータではなく、各トランザクションの更新操作のみを記録することです。データを読み取ると、データのベースバージョンに更新操作が適用され、結果が計算されます。このプロセスは、SVNの増分コミットにも似ています。 2.8 Paxosプロトコル Paxosプロトコルは、エンジニアリングの実践で証明されている強力な一貫性と高可用性を備えた数少ない分散分布プロトコルの1つです。 Paxosプロトコルのプロセスは比較的複雑ですが、その基本的な考え方は理解するのが難しくありません。これは人間社会の投票プロセスに似ています。 Paxosプロトコルには、完全に等しい参加ノード(Accpetorsと呼ばれる)のグループがあります。これらのノードのそれぞれは、イベントで解像度を作成し、ノードの半分以上によって合意されている場合、解像度が効果的になります。 Paxosプロトコルは、ノードの半分以上が正常である限り機能し、ダウンタイムやネットワーク部門などの異常な状況に効果的に抵抗する可能性があります。 役割 提案者:提案者。複数の提案者がいる可能性があり、提案者は提案(価値)を提案します。いわゆる値は、「変数の値を特定の値に変更する」、「現在のプライマリを特定のノードに設定する」など、プロジェクトの任意の操作になります。Paxosプロトコルでは、これらの操作は値として均一に抽出されます。異なる提案者は、異なるまたは矛盾する価値を提案することができます。たとえば、ある提案者は「変数xを1に設定する」ことを提案し、別の提案者は「変数xを2に設定する」ことを提案します。ただし、Paxosプロセスの同じラウンドでは、せいぜい1つの値のみを承認できます。アクセプター:承認者。 nアクセプターがあり、提案者によって提案された価値は、渡すことができる前に半分以上(n/2+1)のアクセプターによって承認されなければなりません。アクセプターは互いに完全に独立しています。学習者:学習者。学習者は承認された価値を学びます。学習とは、各提案者の価値選択結果を読むことです。値が提案者の半分以上によって渡された場合、学習者はこの値を学びました。これはクォーラムメカニズムに似ていることを思い出してください。値はw = n/2 + 1アクセプターによって承認される必要があるため、学習者は少なくともn/2 + 1アクセプターを読む必要があります。最大のnアクセプターの結果を読んだ後、合格した価値を学ぶことができます。上記の3つの役割は、論理的な区分にすぎません。実際には、ノードは3つの役割すべてを同時に再生できます。 プロセス Paxosプロトコルはラウンドで実行され、各ラウンドには数があります。 Paxosプロトコルの各ラウンドは、値を承認する場合と承認しない場合があります。特定の値がPaxosプロトコルの特定のラウンドで承認されている場合、その後のPaxosラウンドはこの値のみを承認できます。プロトコルプロセスの上記のラウンドは、Paxosプロトコルインスタンスを構成します。つまり、Paxosプロトコルインスタンスは1つの値のみを承認できます。これは、Paxosプロトコルの強力な一貫性の重要な現れでもあります。 Paxosプロトコルの各ラウンドは、段階、準備段階、承認段階に分割されます。これら2つの段階では、提案者とアクセプターに独自の処理手順があります。 プロセス:提案者のプロセス(準備段階)
プロセス:ACCPETORプロセス(準備フェーズ) prepare(b)と呼ばれるプロペッサーからメッセージを受信します。パラメーターBは、アクセプターが受け取った最大PAXOSラウンド数です。 Vは、アクセプターによって承認された値であり、空になる可能性があります。 1.1 b> bの場合、Promise(b、v_b)に応答し、b = bを設定します。これは、b未満の数字で提案を受け入れないことが保証されていることを意味します。 1.2それ以外の場合は、返信拒否(b)(承認段階) 受信(b、v)、2.1 b <bの場合、nack(b)に応答します。提案者がこのアクセプターによって受け入れられた数が多い提案があることを暗示していることを意味します。このアクセプターによって承認された値がvであることを示します。受け入れられたメッセージを放送します。 例 基本的な例には、5人のアクセプターと1人の提案者がいますが、ネットワークまたはダウンタイムの異常はありません。各ACCPETORの変数BとVの変化、および提案者の変数Bの変更に焦点を当てます。
同様に、Paxosインスタンスでは、後続の提案者がより高いシーケンス番号でPaxosプロトコルを開始したとしても、承認された値を変更することはできません。 Paxosプロトコルの中核は、「承認された値を変更できない」ことです。これは、プロトコル全体の正しさの基礎でもあります。 Paxosプロトコルは人為的に設計されており、その設計プロセスはプロトコルの派生プロセスでもあります。 Paxosプロトコルは定足数メカニズムを使用し、W = r = n/2+1を選択します。 簡単に言えば、プロトコルはAcceptorを更新する提案者のプロセスです。アクセプターがアセプターの半分以上を正常に更新すると、更新は成功します。学習者は、クォーラムに従ってアクセプターを読み取ります。値が提案者の半分以上によって正常に読み取られると、それは承認された値であることを意味します。このプロトコルは、ラウンドを導入することでデッドロックを回避し、より高いラウンドでの提案が下位ラウンドで提案されます。プロトコル設計の重要なポイントは、「Paxosアルゴリズムインスタンス中に1つの値のみが承認される」の制約を満たす方法です。 2.9キャップ キャップ理論の定義は非常に単純です。 3文字のキャップは、分散システムの3つの矛盾した特性を表しています。
CAP理論は、分散プロトコルを設計することは不可能であるため、CAPの3つの属性を同時に完全に所有すること、つまり1)このプロトコルの下のレプリカは常に強力な一貫性であり、2)サービスは常に利用可能であり、3)プロトコルはネットワークパーティションの例外を許容できます。分散システムプロトコルは、CAP間でのみ妥協することができます。 熱力学の第2法則は、永続的なモーションマシンが存在できないことを示しているため、永続的なモーションマシンを設計しようとしないでください。同様に、CAP理論の重要性は、このシステムが理論的に存在しないことが証明されているため、CAPの3つの主要な属性を完全に所有する完全なシステムを設計しようとしないことを明確に提案することです。
|
<<: 企業はクラウドでデータ駆動型開発をどのように実現できるでしょうか?
>>: クラウド コンピューティング サービスが ERP を近代化する方法
8年間運営してきたVPSベンダーのHostusが最後にプロモーションを行ったのは今年5月でした。今日...
国内の5A級観光スポットの情報化建設を調査・研究するため、国内観光情報化研究チーム-智力動力は5Aレ...
私がこの記事を書こうと思った主な理由は、インターネット関連従事者の労働強度が絶えず高まっており、国内...
1. RBAC の概要RBAC では、4 つの新しいトップレベル リソース オブジェクトが導入されて...
SEO の道を歩み始めた経緯を振り返ると、もう限界で、背水の陣で戦うしかないという気持ちになります。...
みなさんこんにちは。私はハルビンバーチャルリアリティデザインです。最近、キーワードのランキングを研究...
今日のインターネット時代には、何万ものウェブサイトが存在し、毎日多くの新しいウェブサイトが作成されて...
ほぼすべての SEO 担当者は、Web サイトの検索トラフィックのほとんどが、単一検索の少ないロング...
Maple-hostingは主にオランダのサーバーを提供しています。その最大の特徴は、著作権を無視し...
現在、百度は意識的にウェブサイトのランキングに手動で介入し始めています。これは私が以前の記事で述べた...
reprisehosting の特別価格サーバー (独自の AS: AS62838、VPS ブランド...
一方では、世界的にトラフィックのピークが到来し、他方では、コアシステムは 100% クラウド上にあり...
「私は Dropbox のヘビーユーザーです。米国にいた頃、家族で合計 6 台のコンピューターを使用...
ResearchAndMarkets によると、世界のヘルスケア クラウド インフラストラクチャ市場...
私はウェブ編集者として2年以上働いています。この職業は退屈すぎるという印象を持つ人が多いようです。ウ...