Как rsync алгоритм правильно определяет повторяющиеся блоки?

Я нахожусь на персональных поисках, чтобы изучить, как 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. Хешируйте второй блок. Этот хеш существует в списке значений? 12345 -> 255 (да, так пропуск)
  3. Хешируйте третий блок. Этот хеш существует в списке значений? 12345 -> 255 (да, так пропуск)
  4. Хешируйте четвертый блок. Этот хеш существует в списке значений? fghij -> 520 (да, так пропуск)
  5. Больше никаких данных, мы сделаны.

Так как каждый хеш был найден в списке значений, мы приходим к заключению, что A и B являются тем же. Который, по моему скромному мнению, не верно.

Это кажется мне, это произойдет каждый раз, когда существует больше чем один блок, которые совместно используют тот же хеш. Я знаю, что пропустил шаг вычисления и проверки сильного хеша, но это не будет иметь значения, так как вторые и третьи блоки являются точно тем же

Что я пропускаю?

7
задан Kai 1 April 2010 в 03:26
поделиться

1 ответ

Алгоритм rsync посылает две контрольные суммы: одну для каждого блока и "скользящую" контрольную сумму для всего файла. В вашем примере A увидит разницу в скользящей контрольной сумме, когда доберется до "удвоенного" блока.

6
ответ дан 7 December 2019 в 09:59
поделиться
Другие вопросы по тегам:

Похожие вопросы: