分散システムの原理を20,000語で詳しく解説した入門書

  [[333060]]

1 コンセプト

1.1 モデル

ノード

特定のエンジニアリング プロジェクトでは、ノードは多くの場合、オペレーティング システム上のプロセスです。この記事のモデルでは、ノードは完全かつ分割不可能な全体であると見なされます。プログラム プロセスが実際には比較的独立した複数の部分で構成されている場合、モデル内でプロセスを複数のノードに分割できます。

異常な

• マシンのダウンタイム: マシンのダウンタイムは最も一般的な異常の 1 つです。大規模クラスターにおける毎日のダウンタイムの確率は、約 1,000 分の 1 です。実際には、ダウンしたマシンの回復時間は通常 24 時間と考えられており、マシンを再起動するには通常、手動による介入が必要です。
• ネットワーク異常: メッセージが失われ、2 つのノードが相互に完全に通信できなくなり、「ネットワークの断片化」が発生します。
• メッセージが順序どおりではありません。送信された順序どおりに宛先ノードに到着しない可能性が一定数あります。無効または期限切れのネットワーク メッセージがシステムの正確性に影響を与えないように、ネットワーク メッセージの順序が乱れる問題を処理するには、シーケンス番号などのメカニズムの使用を検討してください。
• データエラー;信頼性の低い TCP。 TCP プロトコルは、アプリケーション層に信頼性の高い接続指向の伝送サービスを提供します。ただし、分散システムのプロトコル設計では、TCP プロトコルに基づいている場合、すべてのネットワーク通信が信頼できるとは限りません。
• TCP プロトコルは、同じ TCP リンク内のネットワーク メッセージの順序が乱れないようにすることしかできませんが、TCP リンク間のネットワーク メッセージの順序は保証できません。
• 分散 3 状態: ノードが別のノードに対して RPC (リモート プロシージャ コール) 呼び出しを開始する場合、つまり、ノード A が別のノード B にメッセージを送信し、ノード B が受信したメッセージの内容に基づいて特定の操作を完了し、別のメッセージを通じて操作の結果をノード A に返す場合、この RPC 実行の結果には、「成功」、「失敗」、「タイムアウト (不明)」の 3 つの状態があり、これらは分散システムの 3 つの状態と呼ばれます。
• ストレージ データの損失: ステートフル ノードの場合、データの損失は状態の損失を意味し、保存された状態は通常、他のノードからのみ読み取りおよび復元できます。
• *例外処理の原則*: 多数のエンジニアリング実践によってテストされてきた例外処理の黄金律は、設計段階で考慮された異常な状況はシステムの実際の運用で必ず発生しますが、システムの実際の運用で遭遇する異常は設計段階では考慮されない可能性があるというものです。したがって、需要指標が許さない限り、システム設計中に異常な状況を無視することはできません。

1.2 インスタンス

レプリカ/コピーとは、分散システム内のデータまたはサービスに提供される冗長性を指します。データ レプリケーションとは、異なるノードに同じデータを保存することを指します。ノードに保存されたデータが失われた場合、レプリカからデータを読み取ることができます。

データ複製は、分散システムがデータ損失の異常を解決する唯一の方法です。別の種類のレプリカはサービス レプリカであり、複数のノードが同じサービスを提供するものです。このサービスは通常、ノードのローカル ストレージに依存せず、必要なデータは通常他のノードから取得されます。

レプリケーション プロトコルは、分散システム全体の理論的な中核です。

レプリカの一貫性

分散システムでは、レプリカ制御プロトコルを使用して、システム内の各レプリカから読み取られたデータが特定の制約の下で同じであることを保証します。これをレプリカ一貫性と呼びます。レプリカの一貫性は、特定のレプリカではなく、分散システムを指します。

• 強力な一貫性: どのユーザーまたはノードも、いつでもデータの最新更新コピーを読み取ることができます。強い一貫性は、一貫性の要件の最も高いレベルであり、実際に達成するのが最も困難でもあります。
• 単調な一貫性: いつでも、特定の更新後にユーザーが特定のデータの値を読み取ると、ユーザーはこの値より古い値を読み取ることはありません。
• 単調な一貫性は、強い一貫性よりも弱いですが、非常に実用的な一貫性レベルです。一般的に言えば、ユーザーは自分の視点から観察された一貫性のみを気にし、他のユーザーの一貫性には注意を払わないからです。
• セッションの一貫性: 特定のセッションで特定の更新後にユーザーが特定のデータの値を読み取ると、そのユーザーはこのセッション中、この値より古い値を読み取ることはありません。
• セッション一貫性は、セッションの概念を導入することで、単調一貫性に基づく制約をさらに緩和します。セッションの一貫性は、単一ユーザーの単一セッション内でのデータの単調な変更のみを保証するものであり、異なるユーザー間または同じユーザーの異なるセッション間の一貫性は保証しません。
• 実際には、PHP のセッション概念など、セッションの概念に正確に対応するメカニズムが多数存在します。
• 最終的な一貫性: 最終的な一貫性では、更新が成功すると、各レプリカ上のデータが最終的に完全に一貫した状態に達することが求められますが、完全に一貫した状態に達するのに必要な時間は保証されません。
• 結果的一貫性システムの場合、ユーザーが常に特定のレプリカのデータを読み取る限り、単調一貫性と同様の効果が得られます。ただし、ユーザーがレプリカの読み取りを変更すると、一貫性は保証されなくなります。
• 弱い一貫性（ウィーク一貫性）：更新が成功すると、ユーザーは一定時間内に更新された値を読み取ることができず、あるレプリカで新しい値を読み取ることができたとしても、他のレプリカで新しい値を読み取ることができるという保証はありません。
• 弱一貫性システムは、一般的に実際に使用するのが困難です。弱一貫性システムを使用する場合、アプリケーション側はシステムを利用できるようにするためにより多くの作業を行う必要があります。

1.3 分散システムを測定するための指標

• パフォーマンス: システムのスループットとは、システムが特定の時間に処理できるデータの総量を指します。これは通常、システムが 1 秒あたりに処理するデータの総量で測定されます。
  • システムの応答遅延とは、システムが特定の機能を完了するまでにかかる時間を指します。
  • システムの同時実行性とは、システムが特定の機能を同時に完了する能力を指し、通常は 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 つの主要なタイプの問題を解決します。

データ更新の基本プロセス

1. データの更新はプライマリノードによって調整されます。
2. 外部ノードはプライマリノードに更新操作を送信します
3. プライマリ ノードは同時実行制御を実行します。つまり、同時更新操作の順序を決定します。
4. プライマリノードは更新操作をセカンダリノードに送信する
5. プライマリノードは、セカンダリノードの完了ステータスに基づいて更新が成功したかどうかを判断し、その結果を外部ノードに返します。

エンジニアリングの実践では、プライマリが同時に他の N 個のレプリカにデータを直接送信する場合、各セカンダリの更新スループットはプライマリの合計出力ネットワーク帯域幅によって制限され、最大値はプライマリ ネットワーク出力帯域幅の 1/N になります。

この問題を解決するために、一部のシステム (GFS など) では、プライマリが最初のセカンダリ コピーに更新を送信し、最初のセカンダリ コピーが 2 番目のセカンダリ コピーに更新を送信するというように、リレー アプローチを使用してデータを同期します。

データ読み取り方法

データの読み取り方法も一貫性に大きく関係します。最終的な一貫性のみが必要な場合は、任意のレプリカから読み取るだけで十分です。

セッションの一貫性が必要な場合は、レプリカのバージョン番号を設定し、更新ごとにバージョン番号を増やし、ユーザーがレプリカを読み取るときにバージョン番号を検証することで、ユーザーが読み取るデータがセッション スコープ内で単調に増加していることを確認できます。プライマリ/セカンダリでさらに難しいのは、強力な一貫性を実現することです。

データ更新プロセスはプライマリによって制御されるため、プライマリレプリカ上のデータは最新である必要があり、プライマリレプリカ上のデータのみが常に読み取られる場合、強力な一貫性を実現できます。プライマリ レプリカが読み取り専用の場合、セカンダリ レプリカは読み取りサービスを提供しません。

実際には、レプリカがマシンにバインドされておらず、データ セグメント単位で維持されている場合、プライマリ レプリカのみが読み取りサービスを提供するため、多くのシナリオでマシン リソースが無駄になりません。

レプリカをクラスター全体に分散します。プライマリもランダムに決定されると仮定すると、各マシンには一部のデータのプライマリ レプリカと他のデータ セグメントのセカンダリ レプリカが存在します。したがって、サーバーは実際には読み取りサービスと書き込みサービスの両方を提供します。

セカンダリ ノードの可用性はプライマリ ノードによって制御されます。プライマリがセカンダリ レプリカの更新に失敗すると、プライマリはセカンダリ レプリカを使用不可としてマークし、ユーザーは使用不可のレプリカを読み取れなくなります。使用できないセカンダリ レプリカは、プライマリとのデータの同期を続行できます。プライマリとのデータ同期が完了すると、プライマリはレプリカを使用可能としてマークできます。

このアプローチにより、プライマリかセカンダリかを問わず、利用可能なすべてのレプリカが読み取り可能になり、一定期間内にセカンダリ レプリカがプライマリと一致する最新の状態に更新されるか、使用不可としてマークされるため、より高い一貫性の要件を満たすことができます。このアプローチでは、中央メタデータ管理システムを利用して、どのレプリカが使用可能で、どのレプリカが使用可能でないかを記録します。ある意味では、このアプローチはシステムの可用性を低下させることによってシステムの一貫性を向上させます。

プライマリレプリカの決定と切り替え

プライマリ-セカンダリ プロトコルでは、プライマリ レプリカをどのように決定するかがもう 1 つの中心的な問題です。特に、元のプライマリ レプリカが配置されているマシンがクラッシュした場合は、セカンダリ レプリカが新しいプライマリ レプリカになるようにプライマリ レプリカを切り替える何らかのメカニズムが必要になります。

通常、プライマリ・セカンダリ型の分散システムでは、どのレプリカがプライマリであるかという情報はメタデータに属し、専用のメタデータ サーバーによって管理されます。更新操作を実行する場合、まずメタデータ サーバーにクエリを実行してレプリカのプライマリ情報を取得し、さらにデータ更新プロセスを実行します。

分散システムにおけるノード異常の確実な検出には一定の検出時間が必要であるため、そのような検出時間は通常 10 秒レベルです。これはまた、プライマリが異常になると、システムがプライマリへの切り替えを開始するまでに最大 10 秒の検出時間がかかることを意味します。この 10 秒間、プライマリが存在しないため、システムは更新サービスを提供できません。システムがプライマリ コピーのみを読み取ることができる場合、この期間中は読み取りサービスを提供することもできません。このことから、プライマリ・バックアップ型レプリカ・プロトコルの最大の欠点は、プライマリの切り替えによって発生する一定のサービス停止時間であることがわかります。

データ同期

不整合のあるセカンダリ コピーをプライマリと同期 (調整) する必要があります。

矛盾には、次の 3 つの一般的な形式があります。

1. ネットワークの断片化などの異常により、セカンダリのデータがプライマリのデータより遅れます。

2 番目に、特定のプロトコルでは、セカンダリ上のデータがダーティな場合があり、破棄する必要があります。いわゆるダーティ データとは、プライマリ コピーでは特定の更新操作が実行されないが、セカンダリ コピーでは不要な変更操作が実行され、セカンダリ コピーでデータ エラーが発生することです。

3. セカンダリは、データがまったくない新しく追加されたレプリカであり、他のレプリカからデータをコピーする必要があります。

セカンダリ データが遅れている最初のケースでは、一般的な同期方法は、プライマリで操作ログ (通常は REDO ログ) を再生して、プライマリの更新の進行状況に追いつくことです。

ダーティ データの場合、ダーティ データを生成しない分散プロトコルを設計する方がよいアプローチです。プロトコルがダーティ データを生成する可能性がある場合、ダーティ データを生成する確率を非常に低いレベルにまで下げる必要があります。そうすることで、ダーティ データが発生した場合、ダーティ データを含むコピーを単純に破棄することができ、コピーにデータが存在しないのと同じになります。

さらに、一部の UNDO ログベースの方法は、ダーティ データを削除するように設計できます。セカンダリ コピーにデータがまったくない場合は、プライマリ コピーからデータを直接コピーするのが一般的です。この方法は、ログを再生して更新の進行状況を追跡するよりもはるかに高速です。ただし、プライマリ レプリカは、データをコピーするときに更新サービスを継続的に提供できる必要があるため、プライマリ レプリカでスナップショット機能をサポートする必要があります。つまり、ある瞬間のレプリカ データのスナップショットが取得され、そのスナップショットがコピーされます。コピーが完了したら、ログを再生することでスナップショット作成後の更新操作を追跡します。

分散型レプリカ制御プロトコル

分散レプリカ制御プロトコルには中央ノードがありません。プロトコル内のすべてのノードは完全に平等であり、ノードは平等な協議を通じて合意に達します。そのため、分散型プロトコルでは、集中型ノードの異常によってサービスが停止するなどの問題がありません。

分散型プロトコルの最大の欠点は、プロトコルのプロセスが通常複雑であることです。特に、分散プロトコルが強力な一貫性を実現する必要がある場合、プロトコルのプロセスは複雑になり、理解しにくくなります。プロセスの複雑さにより、分散型プロトコルの効率やパフォーマンスは、集中型プロトコルよりも一般的に低くなります。不適切な類推としては、集中型レプリカ制御プロトコルが独裁システムに似ているというものがあります。このシステムは効率的ですが、中央ノードに大きく依存します。中央ノードに異常が発生すると、システムに大きな影響が生じます。分散型レプリカ制御プロトコルは、民主主義システムに似ています。ノードは集合的に交渉し、非効率的ですが、個々のノードの異常はシステム全体にあまり影響を与えません。

2.3リースメカニズム

リースメカニズムは最も重要な分散プロトコルであり、さまざまな実用的な分散システムで広く使用されています。

リースベースの分散キャッシュシステム

基本的な問題の背景は次のとおりです。分散システムには、システムのメタデータであるデータを保存および維持する中央サーバーノードがあります。システム内の他のノードは、中央サーバーノードにアクセスして、そのメタデータを読み取り、変更します。

システム内のさまざまな操作はメタデータに依存しているため、メタデータを読み取る各操作が中央サーバーノードにアクセスすると、中央サーバーノードのパフォーマンスがシステムのボトルネックになります。この目的のために、メタデータキャッシュは各ノードのメタデータ情報をキャッシュするように設計されているため、中央サーバーノードへのアクセスが減少し、パフォーマンスが向上します。

一方、システムの正しい操作は、各ノードにキャッシュされたデータが常に中央サーバーのデータと一致し、キャッシュのデータが古いデータと汚れたデータになることを要求するメタデータの正確性に厳密に依存します。最後に、設計されたキャッシュシステムは、ノードのクラッシュ、ネットワークの中断、その他の異常を可能な限り最大限に処理できるようにし、システムの可用性を最大化できるはずです。

この目的のために、キャッシュシステムはリースメカニズムを使用して設計されており、その基本原則は次のとおりです。

中央サーバーが各ノードにデータを送信すると、ノードへのリースも発行します。各リースには、クレジットカードの有効期限と同様に、有効期限があります。リースの有効期限は通常、12：00：10などの特定の時点です。実際の時間がこの時期を超えると、リースは期限切れになります。このように、リースの有効期間は、ノードがリースを受信する時間とは関係ありません。ノードが受信したときにリースが期限切れになった可能性があります。ここでは、最初に中央サーバーと各ノードのクロックが同期されていると仮定します。リースに対する時計の非同期の影響については、次のセクションで説明します。中央サーバーが発行するリースの意味は次のとおりです。リースの有効期間中、中央サーバーは、対応するデータの値が変更されないことを保証します。したがって、データとリースを受信した後、ノードはローカルキャッシュにデータを追加します。対応するリースが回復すると、ノードは対応するローカルキャッシュデータを削除します。データを変更するとき、Central Serverは最初にすべての新しい読み取り要求をブロックし、データの値を変更する前に、データが以前に発行されたすべてのリースが期限切れになるのを待ちます。

リースキャッシュに基づいて、クライアントノードはメタデータを読み取ります

1. メタデータがすでにローカルキャッシュにあり、リースが有効かどうかを判断します。 1.1はい：キャッシュ内のメタデータを直接返します。 1.2いいえ：中央サーバーノードをリクエストして、メタデータ情報を読み取ります。 1.2.1読み取り要求を受信した後、サーバーはメタデータと対応するリースを返します。 1.2.2クライアントがサーバーによって返されるデータを正常に受信するかどうか。 1.2.2.1失敗またはタイムアウト：プロセスを終了し、障害を読み取り、再試行できます。 1.2.2.2成功：メタデータとメタデータのリースをメモリに記録し、メタデータを返します。
2. リースキャッシュに基づいて、クライアントノード2.1によってメタデータを変更するプロセスは、ノードがメタデータをサーバーに変更するリクエストを開始します。 2.2変更リクエストを受信した後、サーバーはすべての新しい読み取りデータ要求をブロックします。つまり、読み取りリクエストを受信しますが、データは返されません。 2.3サーバーは、メタデータに関連するすべてのリースがタイムアウトを待ちます。 2.4サーバーはメタデータを変更し、クライアントノードに成功した変更を返します。

上記のメカニズムは、各ノードのキャッシュが常に中央サーバーの中心と一致するようにすることができます。これは、セントラルサーバーノードがデータの送信中にノードに対応するリースを付与するためです。リースの有効期間中、サーバーはデータを変更しないため、クライアントノードはリースの有効期間中にデータを安全にキャッシュできます。上記のリースメカニズムのフォールトトレランスの鍵は、クライアントがその後クラッシュするかどうかに関係なく、クライアントがそれを受信するかどうかに関係なく、サーバーがデータとリースを送信すると、サーバーがリースを待つだけで、対応するクライアントnodeがデータを破壊することなく、データを破壊することを続けるために、対応するクライアントnodeがデータを変更することを保証する必要があることです。

上記の基本的なプロセスには、パフォーマンスとユーザビリティの問題がありますが、簡単に最適化および変更できます。最適化ポイント1：メタデータを変更するとき、サーバーは最初にすべての新しい読み取り要求をブロックする必要があり、その結果、読み取りサービスがありません。これは、新しいリースの発行が新しいクライアントノードが常にリースを保持し、データをキャッシュするのを防ぎ、「ライブロック」を形成するためです。最適化方法は非常に簡単です。サーバーがデータ変更プロセスを入力した後、読み取りリクエストを受信すると、データはデータのみを返しますが、リースは発行しません。その結果、変更プロセスの実行中、クライアントはメタデータを読み取ることができますが、メタデータをキャッシュすることはできません。さらに最適化すると、変更プロセスに入ると、サーバーが発行するリースの有効期間が、発行されたリースの最大有効期間として選択されます。このようにして、サーバーが変更プロセスに入った後、クライアントはメタデータをキャッシュし続けることができますが、新しいリースの発行により、すべてのリースが失効するためのサーバーの待ち時間は延長されません。

最後に、=キャッシュメカニズムとマルチコピーメカニズムの違い。キャッシュメカニズムは、複数のノードにデータのコピーを保存するという点で、マルチコピーメカニズムに似ています。しかし、キャッシュメカニズムははるかに簡単です。キャッシュされたデータはいつでも削除および破棄できます。キャッシュを押すと、データソースにアクセスしてデータを読み取る必要があります。ただし、コピーメカニズムは異なります。コピーを自由に捨てることはできません。コピーが紛失するたびに、サービス品質が低下します。コピーの数が特定のレベルに低下すると、サービスはしばしば利用できなくなります。

リースメカニズムの分析

リースの定義：リースは、一定の有効期間にわたって発行者によって付与されたコミットメントです。発行者がリースを発行すると、受信者がそれを受け取るかどうかに関係なく、そしてリースが期限切れにならない限り、受信者がどのような状態にあるとしても、発行者はその約束を厳密に順守しなければなりません。一方、受信者は、リースの有効期間中に発行者の約束を使用できますが、リースの有効期限が切れると、受信者は発行者の約束を引き続き使用してはなりません。

リースメカニズムには高い断層トレランスがあります。まず、有効期間を導入することにより、リースメカニズムはネットワークの異常に非常によく耐えることができます。リース発行プロセスは、ネットワーク上の一方向通信のみに依存しています。受信者が発行者にメッセージを送信できなくても、リースの発行に影響しません。

リースの有効期間は固定期間であるため、リースのセマンティクスは、リースが送信される特定の時間とは何の関係もないため、発行者が受信者に同じリースを繰り返し送信できます。発行者がリースの送信に時々失敗する場合でも、発行者はリースを再送信するだけで問題を解決できます。リースが受信者によって正常に受け入れられると、その後のリースメカニズムはネットワーク通信に依存せず、ネットワークが完全に切断されていてもリースメカニズムは影響を受けません。

さらに、リースメカニズムは、ノードの障害をより耐えることができます。発行者がダウンした場合、ダウンしている発行者は通常、以前の約束を変更することができず、リースの正しさに影響しません。発行者が復元された後、発行者が以前のリース情報を復元した場合、発行者は引き続きリースコミットメントを遵守します。発行者がリース情報を復元できない場合、リースメカニズムを破壊しないように、最大​​リースタイムアウトがすべてのリースを無効にするのを待つだけです。

たとえば、前のセクションのキャッシュシステムの例では、サーバーがダウンすると、メタデータは間違いなく変更されません。再開後、最大リースタイムアウト時間を待つ必要があり、すべてのノードのキャッシュ情報がクリアされます。

受信者がダウンしている状況のために、発行者はより多くのフォールトトレランスを行う必要はありません。彼はリースが期限切れになり期限切れになるのを待つ必要があり、その後、彼は約束を取り消すことができます。実際には、以前に許可、アイデンティティなどを取り消すことです。最後に、リースメカニズムはストレージに依存しません。発行者は、発行されたリース情報を持続できるため、期間中に有効なリースがダウンタイムの回復後も有効であることができます。ただし、これはリースメカニズムの最適化にすぎません。たとえば、以前の分析では、発行者がリース情報を持続しなくても、最大リース時間を待つことで以前に発行されたすべてのリースを無効にすることができ、それによりメカニズムが引き続き効果的であることを保証します。

リースメカニズムは有効期限に依存します。これには、発行者と受信者のクロックが同期される必要があります。一方では、発行者の時計がレシーバーの時計よりも遅い場合、レシーバーがリースの有効期限が切れていると考えると、発行者はリースが有効であると信じています。受信者は、リースの有効期限が切れる前に新しいリースを申請することにより、この問題を解決できます。一方、発行者の時計が受信者の時計よりも速い場合、発行者がリースの有効期限が切れていると信じている場合、受取人はまだリースが有効であると信じています。発行者は、他のノードにリースを発行し、コミットメントが失敗することを引き起こし、システムの正しさに影響を与える場合があります。このような同期からのクロックの場合、発行者の有効期間を受信者の有効期間よりわずかに大きく設定することは一般的な慣行であり、24時間のエラーが大きいだけではリースの有効性への影響を回避できます。

リースメカニズムに基づいてノードステータスを決定します

分散プロトコルは、ノード状態の認識におけるグローバルな一貫性に依存しています。つまり、ノードQが特定のノードAが異常であると考えると、ノードAもそれ自体を例外と見なす必要があるため、ノードAは「デュアルマスター」問題の発生を回避するプライマリとして停止します。

この問題を解決するには、2つの方法があります。第一に、設計された分散プロトコルは、「ダブルマスター」エラーに耐えることができます。つまり、ノード状態のグローバルな一貫性の理解に依存していないか、グローバルな一貫性状態は交渉全体の結果です。

第二に、リースメカニズムを使用します。最初のアイデアは、集中設計の使用を放棄し、このセクションの議論の範囲を超えた分散設計に切り替えることです。以下は、リースメカニズムを使用してノードステータスを決定することに焦点を当てています。

中央ノードは、他のノードにリースを送信します。ノードが有効なリースを保持している場合、ノードは正常にサービスを提供できると考えられます。例2.3.1では、ノードA、B、およびCでは、自分のステータスを報告するために定期的に心拍を送信します。ハートビートを受信した後、ノードQはリースを送信し、ノードQがノードA、B、およびCのステータスを確認し、リースの有効期間中にノードが正常に機能することを示します。ノードQは、プライマリノードに特別なリースを与えることができ、ノードがプライマリとして機能することを示します。ノードQが新しいプライマリに切り替えたい場合は、以前のプライマリリースが期限切れになるのを待つだけで、「デュアルマスター」問題なしに新しいプライマリノードに新しいリースを安全に発行できます。

実際のシステムでは、中央ノードを使用してリースを送信することも非常に危険です。中央ノードがダウンするか、ネットワークが異常になると、すべてのノードにはリースがありません。これにより、システムは非常に利用できなくなります。この目的のために、実際のシステムは常に複数の中央ノードを使用して互いに複製されるため、高い可用性を持ち、外の世界にリースを発行する機能を提供する小さなクラスターになります。ぽっちゃりとZookeeperはどちらもそのようなデザインに基づいています。

リースの有効期限の選択

このプロジェクトでは、一般的に選択されるリース期間は10秒で、実証済みのエクスペリエンス値です。実際には、参照として使用し、適切な期間を包括的に選択できます。

2.4クォーラムメカニズム

次の合意をしましょう。更新操作（書き込み）は一連のシーケンシャルプロセスであり、更新操作の順序は他のメカニズム（たとえば、プライマリセコンアーキテクチャのプライマリによって決定される順序）を通じて決定されます。各更新操作はWiとしてマークされています。私は、更新操作の単調に増加するシーケンス番号です。各Wiが正常に実行された後、コピーデータは異なるデータバージョンと呼ばれ、VIと呼ばれます。各コピーが履歴のすべてのバージョンからデータを保存していると仮定します。

write-all-read-one

write-all-read-one（略してワロ）は、最も単純なコピー制御ルールです。名前が示すように、更新時にすべてのコピーを書きます。すべてのコピーの更新が成功する場合にのみ、更新は成功すると見なされ、したがって、すべてのコピーが一貫していることを保証し、データを読み取るときにコピーのデータを読み取ることができます。

更新操作はすべてのNレプリカで成功する必要があるため、レプリカの例外があると更新操作が成功する可能性があります。更新操作は失敗し、更新サービスは利用できません。更新サービスの場合、nレプリカはありますが、システムはレプリカの例外に耐えることはできません。一方、Nレプリカの1つが正常である限り、システムは読書サービスを提供できます。読み取りサービスの場合、Nレプリカがある場合、システムはN-1レプリカの例外に耐えることができます。上記の分析から、Waro読み取りサービスの可用性は高いことがわかりますが、更新サービスの可用性は高くありません。レプリカが使用されていても、更新サービスの可用性はレプリカなしに相当します。

クォーラム定義

クォーラムメカニズムの下では、すべてのNレプリカのwで更新操作が成功すると、更新操作は「正常に送信された更新操作」と呼ばれ、対応するデータは「正常に送信されたデータ」と呼ばれます。 R> nwとしましょう。Wiの更新操作はWレプリカでのみ成功しているため、データを読むときはほとんどのRレプリカを読む必要があります。 W+r> nであるため、WIの特定の更新がWレプリカで成功した場合、Rレプリカで構成されるセットには、成功したWレプリカで構成されるセットと交差する必要があるため、Rレプリカを読むことで、Wiの更新データVIを読むことができます。

図2-10に示すように、定足数メカニズムの原理はヴィンセントの図で表すことができます。

特定のシステムには5つのレプリカ、w = 3、r = 3、最初の5つのレプリカのデータが一貫しており、そのすべてがV1であり、特定の更新操作W2は最初の3つのレプリカで成功し、レプリカの状況は（V2 V2 V2 V1 V1）になります。

現時点では、3つのレプリカにはV2を含める必要があります。上記の定義では、w = n、r = 1、つまりワロが取得されるとします。つまり、ワロはクォーラムメカニズムの特別なケースです。ワロの分析と同様に、定足数メカニズムの可用性が分析されます。 QuorumパラメーターをW+r = n+1に制限します。 wレプリカで更新操作を成功させる必要があるため、n-w+1のレプリカが異常になると、更新操作が成功する可能性があります。更新操作はwレプリカで成功することはなく、更新サービスは利用できません。

一方、N-R+1レプリカが異常になると、Wレプリカとの交差点を持つレプリカのコレクションを読み取り、読み取りサービスの一貫性が低下することを保証することは不可能です。

繰り返しますが、クォーラムメカニズムのみに依存することで、強い一貫性を保証することはできません。クォーラムメカニズムが利用可能な場合にのみ最新のバージョン番号を決定できないため、最新のコミットされたバージョン番号が特定のメタデータサーバーまたはメタデータクラスターによってメタデータとして管理されない限り、最新の正常にコミットされたバージョン番号を決定することは困難です。次のセクションでは、状況について説明することができますが、最新の成功したバージョン番号は、クォーラムメカニズムによってのみ決定できます。

定足数メカニズムの3つのシステムパラメーターn、w、およびRは、システムの可用性を制御し、ユーザーに対するシステムのサービスコミットメントでもあります。せいぜいデータのnレプリカがありますが、データが正常に更新されると、ユーザーはユーザーに返されます。一貫性要件が高いQuorumシステムの場合、システムはいつでも失敗したデータを読み取らないことを約束する必要があります。つまり、データ読み取りはW Replicasで正常に行われたデータです。

正常に送信された最新のデータをお読みください

クォーラムメカニズムは、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などのシステムはログを分散システムに保存し、システムの断層許容度をさらに高めます。

ログとチェックポイントをやり直します

高速スタンドアロンクエリシステムを設計し、すべてのデータをメモリに保存して高速データクエリを実現し、各更新操作のデータのごく一部（キー価値のキーなど）を更新します。問題は、ログテクノロジーを使用して、メモリクエリシステムのダウンタイム回復を実現することです。データベーストランザクションとは異なり、この問題モデルのすべての成功した更新操作が有効になります。これは、データベース内の各トランザクションに対して1つの更新操作のみを持つことと同等であり、各更新操作を直ちに提出することができます（自動コミット）。

ログをやり直します

• 更新操作の結果（たとえば、K1 = 1を設定し、K1 = 1を記録）を付録モードでディスクログファイルに記録します
• 更新操作に従って、メモリ内のデータを変更する
• アップデートに正常に戻ります

Redo Logのプロセスから、更新操作が完了した後の結果としてREDOがログを書き込むことがわかります（この記事では元に戻すことはありませんが、これは元に戻すログとの違いの1つです）。さらに、書き込みログファイルを順番に追加するため、順次書き込むディスクなどのストレージデバイスでより効率的です。

Redo Logを使用してダウンタイムを復元するのは非常に簡単です。ログを「再生」するだけです。

プロセス2.5.2：ログのダウンタイム回復をやり直します

ログファイルの各更新操作の結果をゼロから読み、これらの結果を使用してメモリ内のデータを変更します。

また、REDO Logのダウンタイム回復プロセスからも、ログファイルに書き込まれた更新結果のみがダウンタイム後に復元できることも確認できます。これは、ログファイルを最初に更新する必要がある理由でもあり、次にメモリ内のデータがREDOログプロセスで更新されます。

メモリ内のデータが最初に更新された場合、ユーザーはすぐに更新されたデータを読み取ることができます。メモリの変更を完了してログへの書き込みの間にダウンタイムが発生すると、最後の更新操作を復元することはできませんが、ユーザーは以前に更新されたデータを読み取り、矛盾を引き起こす可能性があります。

チェックポイント

単純化されたモデルでは、チェックポイントテクノロジーのプロセスは、リロードが簡単な方法でメモリ内のデータを完全にディスクにダンプすることであり、それによりダウンタイム回復中に再生する必要があるログデータを削減することです。

プロセス：チェックポイント

1. ログファイルに「チェックポイントを開始」を記録します
2. いくつかの簡単なリロードデータ組織でメモリにデータをディスクにダンプします
3. ログファイルに「終了チェックポイント」を記録します。チェックポイントプロセスでは、プロセス2.5.1に従ってデータを更新し続けることができます。このプロセス中、新しく更新されたデータは、実装に応じてディスクにダンプされたり、ディスクにダンプされたりできません。たとえば、チェックポイントがK1 = V1を開始し、チェックポイントがK1 = V2に更新されると、ディスクへのK1ダンプの値はV1またはV2になります。

プロセス：チェックポイントに基づくダウンタイム回復プロセス

ダンプをディスクデータにメモリにロードします。

ログファイルを背面から前方にスキャンして、最後の「エンドチェックポイント」ログを見つけます。

最後の「エンドチェックポイント」ログから最新の「開始チェックポイント」ログを見つけ、そのログの後にすべての更新操作ログを再生します。

NO NO UNDO/NO REDO LOG

データメンテナンスがディスクにある場合、更新のバッチは、アトミック効果を必要とするいくつかの更新操作で構成されています。つまり、同時に有効になるか、どれも有効になりません。

0/1ディレクトリテクノロジーには、ディレクトリ0（ディレクトリ0）とディレクトリ1（ディレクトリ1）と呼ばれる2つのディレクトリ構造があります。別の構造はマスターレコードと呼ばれます。現在使用されているディレクトリは、Active Directoryと呼ばれます。メインレコードでは、ディレクトリ0を使用したレコードまたはディレクトリ1を使用してレコード1。ログファイルの各データの位置はディレクトリ0またはディレクトリ1に記録されます。0/1ディレクトリのデータ更新プロセスは常に不活性ディレクトリで実行されますが、データが有効になる前に、メインレコードの値0と1はメインレコードを切り替えるために回復します。

プロセス：0/1ディレクトリデータ更新プロセス

1. アクティブディレクトリを完全に非アクティブディレクトリにコピーします。
2. 更新操作ごとに、操作後に値を記録する新しいログアイテムを作成し、非アクティブディレクトリ内の対応するデータの場所を新しく作成したログアイテムの場所に変更します。
3. マスターレコードを原子的に変更します。マスターレコードの値を反転して、非アクティブディレクトリが有効になるようにします。

0/1ディレクトリの更新プロセスは非常に簡単です。ディレクトリ0および1のメインレコードスイッチングにより、変更のバッチが効果的な原子になります。 0/1ディレクトリは、バッチトランザクション操作の原子性を、ディレクトリ平均を介したメインレコードのアトミックスイッチングに属性を属性します。

複数のレコードの原子修正は一般に実装が困難であるため、単一のレコードの原子変更を実装することができるため、問題を実装することの難しさを軽減します。

このプロジェクトでは、0/1ディレクトリのアイデアが広く使用されており、そのフォームは上記のプロセスに限定されません。メモリ内の2つのデータ構造間で前後に切り替えることも、ディスク上の2つのファイルディレクトリ間で前後に切り替えることもできます。

2.6 2段階の提出契約

2段階の提出プロトコルは、古典的に一貫した集中レプリカ制御プロトコルです。エンジニアリングにはこのプロトコルには多くの問題がありますが、このプロトコルを研究することは、分散システムのいくつかの典型的な問題をよく理解できます。

プロセスの説明

2段階の提出プロトコルは、典型的な「集中コピー制御」プロトコルです。このプロトコルでは、参加ノードは、集中コーディネーターノードとN参加者ノードの2つのカテゴリに分かれています。各参加者ノードは、上記のようにデータベースコピーを管理するノードです。

2つのステージを送信するというアイデアは比較的簡単です。最初の段階では、コーディネーターはすべての参加者に取引を提出できるかどうか（参加者に投票するように依頼してください）に尋ね、すべての参加者はコーディネーターに投票します。

第2フェーズでは、コーディネーターは、すべての参加者の投票結果に基づいて、取引をグローバルに提出できるかどうかに基づいて決定を下し、すべての参加者に決定を実施することを通知します。 2段階の提出プロセスでは、参加者は投票結果を変更することはできません。

2段階の提出契約をグローバルに提出できるという前提は、すべての参加者が取引の提出に同意することです。 1人の参加者が取引を放棄するために投票する限り、取引を放棄する必要があります。

プロセス：2段階の提出コーディネータープロセス

1. ローカルログ「begin_commit」を書き、待機状態を入力します。
2. すべての参加者に「メッセージを準備する」を送信します。
3. 参加者から送信された「メッセージを準備する」への応答を待って受け取ります。 3.1参加者から送信された「投票アボートメッセージ」を受け取った場合。 3.1.1ローカル「グローバルアボート」ログを書き、中止に入ります。 3.1.2すべての参加者に「グローバルアボートメッセージ」を送信します。 3.1.3中止状態を入力します。 3.2すべての参加者から送信された「投票」メッセージを受け取った場合。 3.2.1ローカル「グローバルコミット」ログを書き、コミット状態を入力します。 3.1.2すべての参加者に「グローバルコミットメッセージ」を送信します。
4. 参加者から「グローバルアボートメッセージ」または「グローバルコミットメッセージ」に送信された確認応答メッセージを待ちます。すべての参加者から確認メッセージが受信されると、ローカル「End_transaction」ログプロセスの執筆が終了します。

プロセス：2段階の提出コーディネータープロセス

1. ローカルログ「init」レコードを記述し、initステータスを入力します
2. ：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：:：：：：：：：：：：：：：：：：:：：：：：：：：：：：：：：：：：：：：：:：：：：：：：：：：：:：：：：：：：：：：：：：：：：：：：：：：：：：::：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：:づでしょしろうと：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：:：：：：：：：：：：：：：：：：：：：:：：：：：：：：：：：：：：：：：：:：：：：：：：：：：：：：：：：：:：：：：：：：：：：：：：：：：：：：：：：::：：：：：：：：：：：：：：：::：：：：：：：：：：：：：：：：：::：：：：：：：：：：：：：：：：：：：：：::：：：：：：：：：：：：：：：：：：：：::：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：.. ：：：： ：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：:：：：：：：：：：：：：：：：：:：：：：：：：：：：：：：：：：：：：：：:：：：：：：：：：：：:：：：：：：：：：：：：：：：：：：：：：：：：：::：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：:づでしょしろうと：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：:：：：：：：：：：：：：：：：：：：：:：：：：：：：：：：：：：：：：：：:：：：：：：：：：：：：：：：：：:：：：：：：：：：：：：：：：：：：：：：：::：：：：：：：：：：：：：：：::：：：：：：：：：：：：：：：：：::：：：：：：：：：：：：：：：：：：：：：::：：：：：：：：：：：：：：：：：：：：::：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：：.. ：：：：：： ：：：：：：：：：：：「投票」メッセージをコーディネーターに送信します2.2.3プロセスは、参加者の「グローバルアボート」メッセージを受信した場合、参加者2.2.4で終了し、応答できます。
3. 即使流程结束，但任何时候收到协调者发送的“global-abort”消息或“global-commit”消息也都要发送一个对应的确认消息。

例外処理

宕机恢复

1. 协调者宕机恢复协调者宕机恢复后，首先通过日志查找到宕机前的状态。如果日志中最后是“begin_commit”记录，说明宕机前协调者处于WAIT 状态，协调者可能已经发送过“prepare 消息”也可能还没发送，但协调者一定还没有发送过“global-commit 消息”或“global-abort 消息”，即事务的全局状态还没有确定。此时，协调者可以重新发送“prepare 消息” 继续两阶段提交流程，即使参与者已经发送过对“prepare 消息”的响应，也不过是再次重传之前的响应而不会影响协议的一致性。如果日志中最后是“global-commit”或“global-abort”记录，说明宕机前协调者处于COMMIT 或ABORT 状态。此时协调者只需重新向所有的参与者发送“global-commit 消息”或“global-abort 消息”就可以继续两阶段提交流程。
2. 参与者宕机恢复参与者宕机恢复后，首先通过日志查找宕机前的状态。如果日志中最后是“init”记录，说明参与者处于INIT 状态，还没有对本次事务做出投票选择，参与者可以继续流程等待协调者发送的“prepare 消息”。如果日志中最后是“ready”记录，说明参与者处于REDAY 状态，此时说明参与者已经就本次事务做出了投票选择，但宕机前参与者是否已经向协调者发送“vote-commit”消息并不可知。所以此时参与者可以向协调者重发“vote-commit”，并继续协议流程。如果日志中最后是“commit”或“abort”记录，说明参与者已经收到过协调者的“global-commit 消息”(处于COMMIT 状态)或者“global-abort 消息”(处于ABORT 状态)。至于是否向协调者发送过对“global-commit”或“global-abort”的确认消息则未知。但即使没有发送过确认消息，由于协调者会不断重发“global-commit”或“global-abort”，只需在收到这些消息时发送确认消息既可，不影响协议的全局一致性。

协议分析

两阶段提交协议在工程实践中真正使用的较少，主要原因有以下几点：

1. 两阶段提交协议的容错能力较差。从上文的分析可以看出，两阶段提交协议在某些情况下存在流程无法执行下去的情况，且也无法判断流程状态。在工程中好的分布式协议往往总是可以在即使发生异常的情况下也能执行下去。例如，回忆Lease 机制(2.3 )，一旦lease 发出，无论出现任何异常，Lease 服务器节点总是可以通过时间判定出Lease 是否有效，也可以用等待Lease 超时的方法收回Lease 权限，整个Lease 协议的流程不存在任何流程被阻塞而无法执行下去的情况。与Lease 机制的简单有效相比，两阶段提交的协议显得较为复杂且容错能力差。
2. 两阶段提交协议的性能较差。一次成功的两阶段提交协议流程中，协调者与每个参与者之间至少需要两轮交互4 个消息“prepare”、“vote-commit”、“global-commit”、“确认global-commit”。过多的交互次数会降低性能。另一方面，协调者需要等待所有的参与者的投票结果，一旦存在较慢的参与者，会影响全局流程执行速度。

虽然存在一些改进的两阶段提交协议可以提高容错能力和性能，然而这类协议依旧是在工程中使用较少的一类协议，其理论价值大于实践意义。

2.7 MVCC

MVCC(Multi-version Cocurrent Control，多版本并发控制)技术。MVCC 技术最初也是在数据库系统中被提出，但这种思想并不局限于单机的分布式系统，在分布式系统中同样有效。

MVCC 即多个不同版本的数据实现并发控制的技术，其基本思想是为每次事务生成一个新版本的数据，在读数据时选择不同版本的数据即可以实现对事务结果的完整性读取。在使用MVCC 时，每个事务都是基于一个已生效的基础版本进行更新，事务可以并行进行，从而可以产生一种图状结构。

基础数据的版本为1，同时产生了两个事务：事务A 与事务B。这两个事务都各自对数据进行了一些本地修改(这些修改只有事务自己可见，不影响真正的数据)，之后事务A 首先提交，生成数据版本2;基于数据版本2，又发起了事务C，事务C 继续提交，生成了数据版本3;最后事务B 提交，此时事务B 的结果需要与事务C 的结果合并，如果数据没有冲突，即事务B 没有修改事务A 与事务C 修改过的变量，那么事务B 可以提交，否则事务B 提交失败。MVCC 的流程过程非常类似于SVN 等版本控制系统的流程，或者说SVN 等版本控制系统就是使用的MVCC 思想。事务在基于基础数据版本做本地修改时，为了不影响真正的数据，通常有两种做法，一是将基础数据版本中的数据完全拷贝出来再修改，SVN 即使用了这种方法，SVN check out 即是拷贝的过程;二是每个事务中只记录更新操作，而不记录完整的数据，读取数据时再将更新操作应用到用基础版本的数据从而计算出结果，这个过程也类似SVN 的增量提交。

2.8 Paxos协议

Paxos 协议是少数在工程实践中证实的强一致性、高可用的去中心化分布式协议。Paxos 协议的流程较为复杂，但其基本思想却不难理解，类似于人类社会的投票过程。Paxos 协议中，有一组完全对等的参与节点(称为accpetor)，这组节点各自就某一事件做出决议，如果某个决议获得了超过半数节点的同意则生效。Paxos 协议中只要有超过一半的节点正常，就可以工作，能很好对抗宕机、网络分化等异常情况。

役割

Proposer：提案者。Proposer 可以有多个，Proposer 提出议案(value)。所谓value，在工程中可以是任何操作，例如“修改某个变量的值为某个值”、“设置当前primary 为某个节点”等等。Paxos 协议中统一将这些操作抽象为value。不同的Proposer 可以提出不同的甚至矛盾的value，例如某个Proposer 提议“将变量X 设置为1”，另一个Proposer 提议“将变量X 设置为2”，但对同一轮Paxos 过程，最多只有一个value 被批准。Acceptor：批准者。Acceptor 有N 个，Proposer 提出的value 必须获得超过半数(N/2+1)的Acceptor 批准后才能通过。Acceptor 之间完全对等独立。Learner：学习者。Learner 学习被批准的value。所谓学习就是通过读取各个Proposer 对value 的选择结果，如果某个value 被超过半数Proposer 通过，则Learner 学习到了这个value。回忆(2.4 ) 不难理解，这里类似Quorum 机制，某个value 需要获得W=N/2 + 1 的Acceptor 批准，从而学习者需要至少读取N/2+1 个Accpetor，至多读取N 个Acceptor 的结果后，能学习到一个通过的value。上述三类角色只是逻辑上的划分，实践中一个节点可以同时充当这三类角色。

プロセス

Paxos 协议一轮一轮的进行，每轮都有一个编号。每轮Paxos 协议可能会批准一个value，也可能无法批准一个value。如果某一轮Paxos 协议批准了某个value，则以后各轮Paxos 只能批准这个value。上述各轮协议流程组成了一个Paxos 协议实例，即一次Paxos 协议实例只能批准一个value，这也是Paxos 协议强一致性的重要体现。每轮Paxos 协议分为阶段，准备阶段和批准阶段，在这两个阶段Proposer 和Acceptor 有各自的处理流程。

流程：Proposer 的流程(准备阶段)

1. 向所有的Acceptor 发送消息“Prepare(b)”;这里b 是Paxos 的轮数，每轮递增
2. 如果收到任何一个Acceptor 发送的消息“Reject(B)”，则对于这个Proposer 而言本轮Paxos 失败，将轮数b 设置为B+1 后重新步骤1;(批准阶段，根据收到的Acceptor 的消息作出不同选择)
3. 如果接收到的Acceptor 的“Promise(b, v_i)”消息达到N/2+1 个(N 为Acceptor 总数，除法取整， 下同);v_i 表示Acceptor 最近一次在i 轮批准过value v。3.1 如果收到的“Promise(b, v)”消息中，v 都为空，Proposer 选择一个value v，向所有Acceptor 广播Accept(b, v);3.2 否则，在所有收到的“Promise(b, v_i)”消息中，选择i 最大的value v，向所有Acceptor 广播消息Accept(b，v);
4. 如果收到Nack(B)，将轮数b 设置为B+1 后重新步骤1;

流程：Accpetor 流程(准备阶段)

1. 接受某个Propeser 的消息Prepare(b)。参数B 是该Acceptor 收到的最大Paxos 轮数编号;V 是Acceptor 批准的value，可以为空1.1 如果b>B，回复Promise(b, V_B)，设置B=b; 表示保证不再接受编号小于b 的提案。1.2 否则，回复Reject(B) (批准阶段)
2. 接收Accept(b, v)， 2.1 如果b < B, 回复Nack(B)，暗示proposer 有一个更大编号的提案被这个Acceptor 接收了2.2 否则设置V=v。表示这个Acceptor 批准的Value 是v。广播Accepted 消息。

例

基本例子里有5 个Acceptor，1 个Proposer，不存在任何网络、宕机异常。我们着重考察各个Accpetor 上变量B 和变量V 的变化，及Proposer 上变量b 的变化。

1. 初期状態
2. Proposer 向所有Accpetor 发送“Prepare(1)”，所有Acceptor 正确处理，并回复Promise(1, NULL
3. Proposer 收到5 个Promise(1, NULL)，满足多余半数的Promise 的value 为空，此时发送Accept(1, v1)，其中v1 是Proposer 选择的Value。
4. 此时，v1 被超过半数的Acceptor 批准，v1 即是本次Paxos 协议实例批准的Value。如果Learner 学习value，学到的只能是v1

在同一个Paxos 实例中，批准的Value 是无法改变的，即使后续Proposer 以更高的序号发起Paxos 协议也无法改变value。Paxos 协议的核心就在于“批准的value 无法改变”，这也是整个协议正确性的基础。

Paxos 协议是被人为设计出来，其设计过程也是协议的推导过程。Paxos 协议利用了Quorom 机制，选择的W=R=N/2+1。

简单而言，协议就是Proposer 更新Acceptor 的过程，一旦某个Acceptor 成功更新了超过半数的Acceptor，则更新成功。Learner 按Quorum 去读取Acceptor，一旦某个value 在超过半数的Proposer 上被成功读取，则说明这是一个被批准的value。协议通过引入轮次，使得高轮次的提议抢占低轮次的提议来避免死锁。协议设计关键点是如何满足“在一次Paxos 算法实例过程中只批准一个Value”这一约束条件。

2.9 CAP

CAP 理论的定义很简单，CAP 三个字母分别代表了分布式系统中三个相互矛盾的属性：

1. Consistency (一致性)：CAP 理论中的副本一致性特指强一致性(1.3.4 );
2. Availiablity(可用性)：指系统在出现异常时已经可以提供服务;
3. Tolerance to the partition of network (分区容忍)：指系统可以对网络分区(1.1.4.2 )这种异常情况进行容错处理;

CAP 理论指出：无法设计一种分布式协议，使得同时完全具备CAP 三个属性，即1)该种协议下的副本始终是强一致性，2)服务始终是可用的，3)协议可以容忍任何网络分区异常;分布式系统协议只能在CAP 这三者间所有折中。

热力学第二定律说明了永动机是不可能存在的，不要去妄图设计永动机。与之类似，CAP 理论的意义就在于明确提出了不要去妄图设计一种对CAP 三大属性都完全拥有的完美系统，因为这种系统在理论上就已经被证明不存在。

• Lease 机制: Lease 机制牺牲了部分异常情况下的A，从而获得了完全的C 与很好的P。
• Quorum 机制: Quorum 机制，在CAP 三大因素中都各做了折中，有一定的C，有较好的A，也有较好的P，是一种较为平衡的分布式协议。
• 两阶段提交协议: 两阶段提交系统具有完全的C，很糟糕的A，很糟糕的P。
• Paxos 协议：同样是强一致性协议，Paxos 在CAP 三方面较之两阶段提交协议要优秀得多。Paxos 协议具有完全的C，较好的A，较好的P。Paxos 的A 与P 的属性与Quorum 机制类似，因为Paxos 的协议本身就具有Quorum 机制的因素