80

マークル ツリーは、複数の分散型レプリケート キー/値ストアで反エントロピー メカニズムとして使用されます。

反エントロピー メカニズムが良いことであることは間違いありません。本番環境では、一時的な障害が発生するだけです。マークルツリーが一般的なアプローチである理由がよくわかりません。

  • 完全なマークル ツリーをピアに送信するには、ツリーの最下位レベルに格納されている各キー値のハッシュと共に、ローカル キー空間をそのピアに送信する必要があります。

  • ピアから送信されたマークル ツリーを比較するには、独自のマークル ツリーが必要です。

両方のピアには、ソートされたキー/値ハッシュ スペースが既に用意されている必要があるため、不一致を検出するために線形マージを実行してみませんか?

維持費を考慮に入れると、ツリー構造が何らかの節約をもたらすとは確信していません。また、ツリーの葉を介した線形パスが、ワイヤーを介して表現をシリアル化するためだけに既に行われているという事実もあります。

これを解決するためのストローマンの代替案は、ノードにハッシュ ダイジェストの配列を交換させることです。ハッシュ ダイジェストは段階的に更新され、モジュロ リング位置によってバケット化されます。

私は何が欠けていますか？

4

1 に答える 1

89

マークル ツリーは、同期時に転送されるデータの量を制限します。一般的な前提は次のとおりです。

  1. ネットワーク I/O は、ローカル I/O + ハッシュの計算よりもコストがかかります。
  2. 並べ替えられたキー スペース全体を転送すると、いくつかのステップで比較を段階的に制限するよりもコストがかかります。
  3. キー スペースは、類似性よりも不一致が少ないです。

マークル ツリー交換は次のようになります。

  1. ツリーのルート (1 つのハッシュ値のリスト) から始めます。
  2. オリジンは、現在のレベルでハッシュのリストを送信します。
  3. 宛先は、ハッシュのリストをそれ自体と比較してから、異なるサブツリーを要求します。違いがない場合は、リクエストを終了できます。
  4. リーフ ノードに到達するまで、手順 2 と 3 を繰り返します。
  5. オリジンは結果セットのキーの値を送信します。

典型的なケースでは、キー スペースの同期の複雑さは log(N) になります。はい、極端に言えば、共通のキーがない場合、操作はソートされたハッシュのリスト全体 O(N) を送信することと同じになります。書き込みが入ると動的にマークル ツリーを構築し、シリアル化された形式をディスクに保持することで、マークル ツリーを構築する費用を償却できます。

Dynamo や Cassandra がどのようにマークル ツリーを使用しているかについては話せませんが、Riak はクラスタ内同期にそれらを使用することをやめました (ほとんどの場合、ほのめかされたハンドオフと読み取り修復で十分です)。一部の内部アーキテクチャのビットが変更された後、それらを後で追加する予定です。

Riak の詳細については、メーリング リストに参加することをお勧めします: http://lists.basho.com/mailman/listinfo/riak-users_lists.basho.com

于 2011-03-30T17:18:01.603 に答える