ベクトル クロック アルゴリズムの概要_PHP チュートリアル

ベクトル クロック アルゴリズムの概要

1. バックグラウンドを使用する

まず、ベクトル クロックが必要なシナリオについて説明します。データを書き込むとき、多くの場合、データが単一のポイントに保存されないことを望みます。たとえば、db1 と db2 は両方とも書き込みサービスを同時に提供でき、両方とも全量のデータを保存します。クライアントがどのデータベースに書き込む場合でも、乱雑なデータ書き込みの問題を心配する必要はありません。ただし、実際のシナリオでは、並行して同時に変更が行われることがよくあります。これにより、db1 と db2 の間でデータの不整合が発生します。そこで、いくつかの解決策を考え出した人もいました。ベクトルクロックもその 1 つです。わかりやすい。ただし、競合の問題は完全に解決されたわけではありません。Realistic 分散ストレージでは、さらに多くのスキルが追加されます。

ここでは逆転の物語とベクトルクロックを紹介します。最初に実際的な例を示して読者が感覚的に理解できるようにし、その後アルゴリズムのルールについて説明します。

2. たとえば

ベクトル クロックは実際にはバージョン番号のセット (バージョン番号 = 論理クロック) であり、データを 3 つのコピーに保存する必要があり、3 db のストレージが必要であるとします (A、B、C で表されます)。 )、ベクトル次元は 3 です。各データベースには 0 から始まるバージョン番号があり、ベクトル バージョン [A:0、B:0、C:0] を形成します。
ステップ 1: 初期状態では、すべてのマシンは [A: 0,B:0, C:0];

DB_A——> [A:0, B:0, C:0]

DB_B—— > [A:0, B:0, C:0]

DB_C——> [A:0, B:0, C:0]ステップ 2:アプリケーションがショッピング モールであると仮定し、腎臓 6 iPhone6 の価格 5888 を入力します。クライアントは、書き込むデータベース マシンをランダムに選択します。ここで、A が選択されたとします。 、データはおおよそ次のようになります:
{key=iphone_price; value=5888; vclk=[
A:1,B:0,C:0]}

ステップ 3: 次に、A はデータを同期します。 B と C; 最終的な同期結果は次のようになります

DB_A——

> {key=iphone_price=5888; :0]}

DB_B——> {key=iphone_price; vclk=[ A:1, B:0,C:0]}

DB_C—— > {key=iphone_price; value=5888; vclk=[ A:1,B:0,C:0]}

ステップ 4:数分で価格が 6888 に変動し、販売員が価格を更新しました。このとき、システムは書き込みストレージとして B をランダムに選択するため、結果は次のようになります。 : 0,C:0]}DB_B——> {key=iphone_price; vclk=[A:1,

B:1

,C:0]}

DB_C——> {key=iphone_price; value=5888; vclk=[A:1,B:0,C:0]}

ステップ 5: B は更新は他のいくつかのストアに同期されます DB_A——> {key=iphone_price; value=6888; DB_B——

> {key=iphone_price; vclk=[A:1,

B:1,C:0]}

DB_C——

> {key=iphone_price; value=6888; vclk=[A:1,

B:1

,C:0]} 同期を開始しましょう以下のデモ。

ステップ 6: 価格は再び変動し、4000 になります。今回は C を選択して次のように記述します。 1,B:1,C:0]}DB_B——> {key=iphone_price; vclk=[A:1,B:1,C:0]} ステップ7 : C はアップデートを A と B に同期します。いくつかの問題により、A にのみ同期されます。結果は次のとおりです。 =[A:1 ,B:1, C:1

]}DB_B——> {key=iphone_price=6888; 1,C:0 ]}

DB_C——> {key=iphone_price; vclk=[A:1,B:1,C:1]}

ステップ 8: 価格再び変動し、システムは B を選択し、

DB_A——

> {key=iphone_price=6888; 1 ]} DB_B——> {key=iphone_price; vclk=[A:1,

B:2, C:0]} DB_C——> {key=iphone_price; vclk=[A:1,B:1,C:1]}

ステップ 9: B の場合A と C を更新するときに問題が発生します。A 自身のベクトル クロックは [A:1, B:1, C:1] で、更新メッセージによってもたらされるベクトル クロックは [A:1,B:2 , C: 0]、B:2 は B:1 より新しいですが、C:0 は C1 より古いです。このとき、矛盾した競合が発生します。矛盾の問題を解決するにはどうすればよいでしょうか?ベクトル クロック戦略では解決策は提供されず、ユーザー自身が解決する必要があります。現在のデータに矛盾があることが通知されるだけです。 3. ルールの紹介

実際には、バージョン番号の変更には 2 つのルールがあります。これらは比較的単純です

1. データが変更されるたびに、このノードのバージョン番号は 1 ずつ増加します。たとえば、上記の手順 8 で B に書き込むと、B:1 から B:2 に他のノードのバージョン番号は変わりません。

2. データが同期されるたびに (同期と変更は異なる書き込み操作であることに注意してください)、次の 3 つの状況が発生します:

a: このノードのベクトル バージョンは、によって伝送されるベクトル バージョンよりも低くなります。メッセージ (以下) 現在のノードが [A:1, B:2,C:3]} の場合、伝送されるメッセージは [A:1, B:2,C:4] または [A: 2、B:3、C:4]など。 このとき、結合ルールは各成分の最大値をとる。

b: このノードのベクトル バージョンは、メッセージによって運ばれるベクトル バージョンよりも高いです。このとき、ローカル データは同期データよりも新しいと考えられ、同期されるバージョンは直接破棄されます。

c: たとえば、上記のステップ 9 では、一部のコンポーネントのバージョンが大きく、一部のコンポーネントのバージョンが最新であるかを判断できません。紛争の仲裁が必要です。

4. 競合解決

実際、これより優れた競合解決バージョンはありません。著者がこれまでに知っている限り、タイムスタンプの追加は戦略です。具体的な方法は、データ更新のタイムスタンプ（タイムスタンプ）という別次元の情報を追加することです。 [A:1, B:2,C:4, ts:123434354]、競合が発生した場合、2 つのデータの ts を比較し、値が大きいほど比較後に更新されることを示し、それを最終データとして選択します。 。そしてベクトルクロックを見直します。

5. その他の問題

1. バックアップが多すぎる場合、ベクトルクロックの次元は保存されたデータバックアップの数と等しくなります。ベクトルが長すぎる原因となります。ただし、現時点ではこの問題は発生していないようです。通常、バックアップ数 = 3 で十分です。もう少し量があっても、それほど長くはありません。

2. 競合を修正する場合、多くの修正方法があります。修正のためにバックグラウンド サーバーに配置されるものもあれば、クライアントが調停した後、サーバーに書き戻されるものもあります。エラーを修正する機会は数多くあります。データの読み取り時に不一致が検出される場合もあれば、同期中に不一致が検出された場合に修正される場合もあります。実際には、誰もが自分自身の選択をします。

http://www.bkjia.com/PHPjc/1103187.html

www.bkjia.com

本当

http://www.bkjia.com/PHPjc/1103187.html

技術記事

ベクトル クロック アルゴリズムの概要 1. 使用の背景 まず、ベクトル クロックを使用する必要があるシナリオについて説明します。データを書き込むとき、多くの場合、データが単一のポイントに保存されないことを望みます。 db1、db2 など...