最終整合性で使用するMerkle Treesの説明

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

私は何を見逃しているのでしょうか?

どのように解決するのですか？

メルクルツリーは、同期する際のデータ転送量を制限します。一般的な前提は

1. ネットワーク I/O は、ローカル I/O + ハッシュの計算よりも高価である。
2. ソートされたキー空間全体を転送することは、いくつかのステップに渡って徐々に比較を制限するよりも高価です。
3. キースペースは類似性よりも不一致の方が少ない。

Merkle Treeの交換はこのようになります。

1. ツリーのルート (1 つのハッシュ値のリスト) から開始します。
2. オリジンは現在のレベルのハッシュのリストを送信します。
3. デスティネーションはハッシュのリストを自分のと照らし合わせて差分を取り 異なるサブツリーを要求します。もし 差分がなければ、リクエストは終了します。
4. リーフノードに到達するまで、ステップ2と3を繰り返す。
5. オリジンは、結果として得られるセットのキーの値を送信します。

典型的なケースでは、キー空間を同期させる複雑さはlog(N)になります。そう、極端な話、共通のキーがない場合、この操作はハッシュのソートされたリスト全体を送信することと同じになり、O(N) になります。書き込みがあったときに動的に Merkle ツリーを構築し、ディスク上にシリアライズされたフォームを保持することで、Merkle ツリーの構築費用を償却することができます。

DynamoやCassandraがどのようにMerkleツリーを使用するかは言えませんが、Riakはクラスタ内同期のためにそれらを使用することを止めました（ほとんどの場合、ヒンテッドハンドオフとリードリペアで十分です）。私たちは、いくつかの内部アーキテクチャのビットが変更された後、それらを後で追加する計画を持っています。

Riakに関するより多くの情報については、メーリングリストに参加することをお勧めします。 http://lists.basho.com/mailman/listinfo/riak-users_lists.basho.com