問題タブ [vector-clock]

さまざまなデバイスで実行されている私のコードでは、それらのデバイス間で送信されるメッセージの順序を決定する必要があります。したがって、ベクトルクロックを使用するとイベントの順序付けが可能になるため、ベクトルクロックを使用したいと思います。

そのために使用できる確立されたフレームワーク/パブリック API はありますか? または参照実装=または、ゼロからコーディングする必要がありますか?

参照とヒントをありがとう

イベントログとそのベクタークロックで構成されるログファイルがたくさんあります。ここで、任意の2つのイベントのベクトルクロックを比較するときに、ベクトルクロックの各コンポーネントの二乗和の合計のルートを取り、その結果を使用して別のイベントの結果と比較し、小さい方の値が他の値よりも優先されますか？

たとえば、キー値ストアの更新で更新の競合があるかどうかを判断するのに十分な情報を提供できないスカラー論理クロックの観点から、ベクトル クロックの必要性を理解しています。

しかし、どの問題がまだベクトル クロックによって解決されておらず、よりかさばるマトリックス クロックによって解決されているのかわかりません。

私はCvRDTを読んでいて、Riak がすでにRiak 2にいくつか追加していることを知っています。

私の質問は:すべてのオブジェクトに関連付けられてgcounterいる基盤が同じ情報を記録しているように聞こえるのに、なぜ Riak は を実装するのでしょうか? 結果は、それぞれが同じ重要な情報を含む で保存されvclockませんか?gcountervclock

vclocks現時点での唯一の推測は、Riak がの目的で実際に重要なトリミング情報gcounter(つまり、インクリメントの数) をガベージ コレクションする可能性があるということです。

私は Erlang を特によく読めないので、Riakvclocksがこれらの特殊なケースのデータ型を格納していると誤って想定していたのかもしれません。ただし、問題は、標準の Riak の上に記述された自家製のソリューションvclocksにも当てはまります (したがって、永続化された各オブジェクトを継承します)。

編集：

それ以来、CvRDT をより実用的な方法で説明するために、次の記事を書きました。この記事では、上記で強調した冗長性についても触れています。

Conflict-free Replicated Data Types (CRDT) - 数学の少ないわかりやすい説明。

ベクター クロックがイベント間の因果関係を検出することは非常によく知られていますが、さまざまな実装方法があります。次の違い (利点/欠点) は何ですか。

• 送信時のみカチカチ（前）。
• 送信時のみカチカチ（後）。
• 受信時のティックと送信前のティック
• 受信時のティックと送信後のティック

スレッドが整数のアトミック インクリメントを使用して、グローバルに発生したイベントの数をカウントするクリティカル コード パスがあります。これはかなり高速ですが、整数を保持するキャッシュ ラインがコア間でバウンスする必要があります。NUMA システムでは、これにより大量の MESI トラフィックが作成されます。

ホットパットの疑似コードは、すべてのスレッドがこれを行うことです:

カウンターは単調に増加し、到達する必要がある値は事前にわかっています。

少なくとも 1 つのスレッドが、CHECK_VALUEインクリメントした後にグローバル カウンターに到達したと判断する必要がありますcounter。複数のスレッドがその結論を導き出すことは許容されます (その時点でいつでも同期できます - それはもはやホット パスではないため)。

counter単調であり、最終値がわかっている場合、アトミックインクリメントを使用して値を追跡するよりもうまくいくことは可能ですか?

revisionKeyしばらくの間、MongooseJS を使用してきました__v。これは、デフォルトでドキュメントに含まれるフィールドです。リビジョン番号の目的と、一般的にいつ更新されるかを理解しています。

__v最近、友人と「ベクター クロック」のアイデアについて話していたときに、このフィールドを持つ MongoDB と MongooseJS について言及しました。当時、これはベクトル時計のように聞こえました。しかし、ベクトルクロックについて少し読んだことがありますが、今はよくわかりません。

だから私は疑問に思っていversionKeyます.MongooseJSの属性と、__vそれがデフォルトで生成するフィールドは、ベクトルクロックと見なすことができますか? はい、またはいいえ、そしてその理由は?

私の考えは、タイムスタンプがクロックベースであり、常に前進し、一意であることが保証されている基本的な «vector clock» を実装することです。

たとえば、単純なテーブルでは次のようになります。

トリガーを使用して、挿入前にタイムスタンプ値を設定します。基本的に、2 つの挿入が同時に到着すると、未来に進みます。

次に、2 つの別々のクライアントで大量の挿入を実行します。

予想どおり、衝突が発生します。

@rach はオブジェクトと混合current_clock()することを提案しましたSEQUENCEが、それはおそらくTIMESTAMP型を取り除くことを意味します。分離の問題をどのように解決するかはわかりませんが...

これを回避する一般的なパターンはありますか?

あなたの洞察をありがとう:)