7

私は、rsync アルゴリズムがどのように機能するかを個人的に知りたいと思っています。読んで考えた結果、アルゴリズムが失敗したと思われる状況にたどり着きました。これが実際の実装でどのように解決されるかを理解しようとしています。

A が受信者で B が送信者であるこの例を考えてみましょう。

A = abcde1234512345fghij
B = abcde12345fghij

ご覧のとおり、唯一の変更点は12345削除されたことです。

ここで、この例を面白くするために、5 バイト (文字) のブロック サイズを選択してみましょう。弱いチェックサムを使用して送信者側で値をハッシュすると、次の値のリストが得られます。

abcde|12345|fghij

abcde -> 495
12345 -> 255
fghij -> 520

values = [495, 255, 520]

次に、A でハッシュ値が異なるかどうかを確認します。一致するブロックがあれば、次のチェックのためにそのブロックの最後までスキップできます。一致しないブロックがある場合は、違いが見つかりました。このプロセスを踏んでいきます。

  1. 最初のブロックをハッシュします。このハッシュは値リストに存在しますか? abcde -> 495（はい、スキップします）
  2. 2 番目のブロックをハッシュします。このハッシュは値リストに存在しますか? 12345 -> 255（はい、スキップします）
  3. 3 番目のブロックをハッシュします。このハッシュは値リストに存在しますか? 12345 -> 255（はい、スキップします）
  4. 4 番目のブロックをハッシュします。このハッシュは値リストに存在しますか? fghij -> 520（はい、スキップします）
  5. これ以上のデータはありません。

すべてのハッシュが値リストで見つかったので、A と B は同じであると結論付けます。私の謙虚な意見では、これは真実ではありません。

これは、同じハッシュを共有するブロックが複数ある場合に必ず発生するようです。強力なハッシュを計算してチェックするステップをスキップしたことはわかっていますが、2 番目と 3 番目のブロックはまったく同じであるため、違いはありません。

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

4

1 に答える 1

6

rsync アルゴリズムは 2 つのチェックサムを送信します。各チャンクに 1 つと、ファイル全体の「ローリング」チェックサムです。あなたの例では、「倍増」ブロックに到達すると、A はローリング チェックサムに違いが見られます。

于 2010-04-01T03:17:15.243 に答える