Сетевое железо - статьи

       

Быстрая сигнатура


Быстрая сигнатура очень важна для эффективности алгоритма rsync. Она работает как фильтр, предотвращая вычисление стойкой сигнатуры. Основная задача быстрой сигнатуры - это максимально быстрое её вычисление для каждого байтового смещения в файле.

Первоначально, для создания быстрой сигнатуры в rsync было опробовано простое склеивание первых и последних 4 байт блока. Хотя такой алгоритм в принципе работал, но был выявлен его серьёзный недостаток. Для определённых типов данных, например для tar файла, он слишком часто создавал одинаковые сигнатуры для разных частей файла, что приводило к многократному вычислению стойкой сигнатуры и как следствие падению производительности всего алгоритма.

Это привело к необходимости выбора нового алгоритма для вычисления быстрой сигнатуры, значение которого зависело бы от всех байт блока, но при этом вычисление оставалось таким же простым и быстрым. Им стал алгоритм похожий на adler32 от Марка Адлера. Adler32 - алгоритм расчёта контрольных сумм, похожий на довольно распространённый алгоритм CRC32, но при этом более быстрый.



Содержание раздела