Прокручивающийся хеш

Было предложено разделить эту статью на новую статью под названием Content-Defined Chunking . ( Обсудить ) ( август 2020 )

Прокатки хэш (также известная как рекурсивное хеширование или прокатка контрольная сумма) является хэш - функцией , где входным хешируются в окне , которое проходит через вход.

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

Одним из основных приложений является алгоритм поиска строки Рабина – Карпа , который использует скользящий хеш, описанный ниже. Еще одно популярное приложение - программа rsync , которая в качестве скользящего хеша использует контрольную сумму на основе adler-32 Марка Адлера . Сетевая файловая система с низкой пропускной способностью (LBFS) использует отпечаток Рабина в качестве скользящего хэша. FastCDC (Fast Content-Defined Chunking) использует эффективный для вычислений отпечаток Gear в качестве скользящего хэша.

В лучшем случае скользящие хеш-значения попарно независимы ^[1] или строго универсальны . Например, они не могут быть независимыми по трем направлениям .

Полиномиальный скользящий хеш [ править ]

Строка алгоритм поиска Рабин-Карп часто объясняется использование подвижной хэш - функции , которая использует только умножения и сложения:

${\displaystyle H=c_{1}a^{k-1}+c_{2}a^{k-2}+c_{3}a^{k-3}+...+c_{k}a^{0}}$,

где - константа, и - входные символы (но эта функция не является отпечатком Рабина , см. ниже).${\displaystyle a}$${\displaystyle c_{1},...,c_{k}}$

Чтобы избежать манипулирования огромными значениями, все вычисления производятся по модулю . Выбор и имеет решающее значение для получения хорошего хеширования; см. линейный конгруэнтный генератор для более подробного обсуждения.${\displaystyle H}$ ${\displaystyle n}$${\displaystyle a}$${\displaystyle n}$

Удаление и добавление символов просто включает добавление или вычитание первого или последнего члена. Чтобы сдвинуть все символы на одну позицию влево, необходимо умножить всю сумму на . Чтобы сдвинуть все символы на одну позицию вправо, нужно разделить всю сумму на . Обратите внимание, что в арифметике по модулю можно выбрать множитель, обратный, на который можно умножить, чтобы получить результат деления без фактического выполнения деления.${\displaystyle H}$${\displaystyle a}$${\displaystyle H}$${\displaystyle a}$${\displaystyle a}$ ${\displaystyle a^{-1}}$${\displaystyle H}$

Отпечаток Рабина [ править ]

Отпечатков пальцев Рабина еще один хэш, который также интерпретирует входные данные в виде полинома, но над полем Галуа GF (2) . Вместо того, чтобы рассматривать ввод как полином из байтов, он рассматривается как полином из битов, и вся арифметика выполняется в GF (2) (аналогично CRC32 ). Хеш - это результат деления этого многочлена на неприводимый многочлен над GF (2). Можно обновить отпечаток Рабина, используя только входной и выходной байты, что фактически делает его скользящим хешем.

Поскольку он имеет того же автора, что и алгоритм поиска строки Рабина – Карпа, который часто объясняется другим, более простым скользящим хешем, и поскольку этот более простой скользящий хеш также является полиномом, оба скользящих хеш-значения часто ошибочно принимают друг за друга. Программное обеспечение для резервного копирования restic использует отпечаток Рабина для разделения файлов с размером большого двоичного объекта от 512 байт до 8 МБ. ^[2]

Циклический полином [ править ]

Хеширование с помощью циклического полинома ^[3], иногда называемого Бужашем, также простое, но его преимущество заключается в том, что он позволяет избежать умножений, используя вместо этого сдвиг в форме бочки . Это форма хеширования табуляции : предполагается, что в интервале есть некоторая хеш-функция от символов до целых чисел . Эта хеш-функция может быть просто массивом или хеш-таблицей, отображающей символы в случайные целые числа. Пусть функция будет циклическим двоичным вращением (или круговым сдвигом ): она поворачивает биты на 1 влево, сдвигая последний бит в первую позицию. Например, . Позвольте быть побитовым исключающим или . Хеш-значения определены как${\displaystyle h}$${\displaystyle [0,2^{L})}$${\displaystyle s}$${\displaystyle s(101)=011}$${\displaystyle \oplus }$

${\displaystyle H=s^{k-1}(h(c_{1}))\oplus s^{k-2}(h(c_{2}))\oplus \ldots \oplus s(h(c_{k-1}))\oplus h(c_{k}),}$

где умножение на степень двойки может быть выполнено двоичным сдвигом. Результат - число в .${\displaystyle [0,2^{L})}$

Вычисление хеш-значений в скользящем режиме выполняется следующим образом. Позвольте быть предыдущим значением хеш-функции. Поворот один раз: . Если это символ должен быть удален, вращать его раз: . Затем просто установите${\displaystyle H}$${\displaystyle H}$${\displaystyle H\leftarrow s(H)}$${\displaystyle c_{1}}$${\displaystyle k}$${\displaystyle s^{k}(h(c_{1}))}$

${\displaystyle H\leftarrow s(H)\oplus s^{k}(h(c_{1}))\oplus h(c_{k+1}),}$

где новый персонаж.${\displaystyle c_{k+1}}$

Хеширование с помощью циклических многочленов является строго универсальным или попарно независимым: просто сохраните первые биты. То есть взять результат и отбросить все последовательные биты. ^[1] На практике это достигается целочисленным делением .${\displaystyle L-k+1}$${\displaystyle H}$${\displaystyle k-1}$${\displaystyle H\rightarrow H\div 2^{k-1}}$

Нарезка на основе содержимого с использованием скользящего хеша [ править ]

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

Самый простой подход к вычислению динамических фрагментов - это вычисление скользящего хэша, и если он соответствует шаблону (например, все младшие N бит - нули), то это граница фрагмента. Такой подход гарантирует, что любое изменение в файле повлияет только на его текущий и, возможно, следующий фрагмент, но ни на что другое.

Когда границы известны, блоки необходимо сравнить по их хеш-значениям, чтобы определить, какой из них был изменен и нуждается в передаче по сети. ^[4] Программа резервного копирования Attic использует алгоритм Buzhash с настраиваемым диапазоном размеров фрагментов для разделения потоков файлов. ^[5]

Нарезка на основе содержимого с использованием скользящей суммы [ править ]

Несколько программ, включая gzip (с --rsyncableопцией) и rsyncrypto, выполняют нарезку на основе содержимого на основе этой конкретной (невзвешенной) скользящей суммы: ^[6]

${\displaystyle S(n)=\sum _{i=n-8195}^{n}c_{i},}$

${\displaystyle H(n)=S(n)\mod 4096,}$

где

• ${\displaystyle S(n)}$представляет собой сумму 8196 последовательных байтов, заканчивающихся байтом (требуется 21 бит памяти),${\displaystyle n}$
• ${\displaystyle c_{i}}$это байт файла,${\displaystyle i}$
• ${\displaystyle H(n)}$представляет собой «хеш-значение», состоящее из нижних 12 битов .${\displaystyle S(n)}$

Сдвиг окна на один байт просто включает добавление нового символа к сумме и вычитание самого старого символа (уже не находящегося в окне) из суммы.

Везде, где эти программы разрезают файл между и . Такой подход гарантирует, что любое изменение в файле повлияет только на его текущий и, возможно, следующий фрагмент, но не на другой фрагмент.${\displaystyle n}$${\displaystyle H(n)==0}$${\displaystyle n}$${\displaystyle n+1}$

Отпечаток устройства Gear и алгоритм фрагментации на основе контента FastCDC [ править ]

Алгоритм Content-Defined Chunking (CDC) должен вычислять хэш-значение потока данных побайтно и разбивать поток данных на части, когда хеш-значение соответствует заранее заданному значению. Однако побайтовое сравнение строки приведет к значительным накладным расходам на вычисления. FastCDC ^[7] предлагает новый и эффективный подход Content-Defined Chunking. Он использует алгоритм быстрого хеширования Gear ^[8], пропускающий минимальную длину, нормализуя распределение размеров фрагментов и, наконец, что не менее важно, каждый раз прокручивая два байта для ускорения алгоритма CDC, что может обеспечить примерно в 10 раз более высокую пропускную способность. чем подход CDC, основанный на Рабине. ^[9]

Базовый псевдокод версии представлен следующим образом:

алгоритм FastCDC input: data buffer src , длина данных n , вывод: точка отсечения i  MinSize ← 2 КБ // минимальный размер фрагмента 2 КБ MaxSize ← 64 КБ // максимальный размер фрагмента 64 КБ fp ← 0  i ← MinSize  Mask ← 0x0000d93003530000LL  // размер буфера меньше минимального размера блока если  n ≤ MinSize,  то  вернуть  n,  если  n ≥ MaxSize,  то  n ← MaxSize     while  i < n  do  fp ← ( fp << 1) + Gear [ src [ i ]] if  ! ( fp & Mask ) тогда  вернуть  i    вернуть  я

Где Gear array - это предварительно рассчитанный массив хеширования. Здесь FastCDC использует алгоритм хеширования Gear, который может быстро вычислять результаты скользящего хеширования и сохранять равномерное распределение результатов хеширования, как у Рабина. По сравнению с традиционным алгоритмом хеширования Рабина, он обеспечивает гораздо более высокую скорость. Эксперименты показывают, что при сегментировании потока данных он может генерировать почти такое же распределение размеров блоков за гораздо более короткое время (около 1/10 фрагментов на основе рабина ^[9] ).

Вычислительная сложность [ править ]

Все скользящие хеш-функции линейны по количеству символов, но их сложность в зависимости от длины окна ( ) варьируется. Скручивающийся хеш Рабина – Карпа требует умножения двухбитовых чисел, целочисленное умножение - в . ^[10] Хеширование диаграмм циклическими многочленами может выполняться за линейное время. ^[1]${\displaystyle k}$${\displaystyle k}$${\displaystyle O(k\log k2^{O(\log ^{*}k)})}$

Программное обеспечение [ править ]

• Rollinghashcpp - это бесплатная реализация на C ++ нескольких скользящих хеш-функций.
• Rollinghashjava - это Java-реализация скользящих хеш-функций с лицензией Apache.

См. Также [ править ]

• MinHash
• шинглинг

Внешние ссылки [ править ]

• MIT 6.006: Введение в алгоритмы 2011 - Конспект лекций - скользящий хеш

Сноски [ править ]