2 つのベクトル クロックを比較するときに文字列を比較できるように、ベクトル クロックをシリアル化する方法はありますか?
LevelDB を使用する場合、ベクトル クロックをレコード キーの一部として保存し、LevelDB が実行するデータベース キーの並べ替えを利用できるようにしたいと考えています。
2 に答える
1
私はパーティーに少し遅れていることを知っていますが、職場で同じ問題を抱えていて、解決策を見つけました. 問題の制約を少し緩和する必要がありますが、分散システムで有効なグローバル順序付けを作成するには十分に機能するはずです。
適切なベクトル クロック A および B では、
- A > B iff (if and only if) A のすべての要素が >= B の要素である
- A と B は同時でない場合 (A > B または B > A)
したがって、前 (<)、後 (>)、および同時の 3 つの状態があります。文字列の場合、有効な比較値は < と > の 2 つだけです。これらの制約が与えられた場合、制約を少し緩和して、次の結果を得ることができます。
- str(A) > str(B) if (ここだけではありません) A のすべての要素が >= B の要素である場合
- A と B が同時に存在する場合、str(A) > str(B) と str(B) > str(A) の両方が許容されます。
これらの制約を使用して、シリアル化された文字列値ですべてのイベントを並べ替えると、ベクトル クロックによって提供されるすべての部分的な並べ替えと一致する可能性のあるグローバルな並べ替えが得られます。つまり、すべてのイベントはすべての原因の後、その結果の前に配置されます。唯一の秘訣は、各アクターに一意の整数識別子が必要なことですが、とにかくベクトル クロックにはそのようなものが必要です。
これを行うための Python ライブラリを作成しました。ぜひご覧ください: https://github.com/ethanfrey/vclock
ベクトル クロックをシリアル化する方法だけを見たい場合は、こちらをご覧ください。ArrayCodec は、アクターの ID によってインデックス付けされた配列として格納された vclock に依存します。DictCodec は、キーが整数のアクター ID であるディクショナリに依存しています。基本実装は、1 クロックで 256 のアクターと 1,600 万のイベントをサポートし、アクターあたり 6 バイトですが、シリアル化により多くのバイトを使用することで簡単にスケールアップできます。
https://github.com/ethanfrey/vclock/blob/master/vclock/codec.py
于 2016-02-01T17:31:08.107 に答える