Роллинг хеша

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

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

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

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

Полиномиальный скользящий хэш

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

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

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

Чтобы избежать манипуляций с огромными $H$ значения, вся математика выполняется по модулю $n$. Выбор $a$ и $n$ имеет решающее значение для получения хорошего хеширования; в частности, модуль $n$ обычно является простым числом. см . в разделе «Линейный конгруэнтный генератор» Дополнительную информацию .

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

Отпечаток пальца Рабина

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

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

Циклический полином

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

$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}),$

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

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

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

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

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

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

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

Простой подход к созданию динамических фрагментов состоит в вычислении скользящего хэша, и если значение хэша соответствует произвольному шаблону (например, все нули) в младших N битах (с вероятностью ${\textstyle {1 \over 2^{n}}}$, учитывая, что хэш имеет равномерное распределение вероятностей), тогда он выбран в качестве границы фрагмента. Таким образом, каждый фрагмент будет иметь средний размер ${\textstyle 2^{n}}$ байты. Этот подход гарантирует, что немодифицированные данные (на расстоянии более чем размера окна от изменений) будут иметь одинаковые границы.

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

Такое разделение по содержимому часто используется для дедупликации данных .

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

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

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

$H(n)=S(n)\mod 4096,$

где

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

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

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

Отпечаток устройства и алгоритм фрагментирования на основе контента FastCDC

Чанкинг — это метод разделения потока данных на набор блоков, также называемых кусками. Фрагментирование по содержимому (CDC) — это метод фрагментирования, при котором разделение потока данных основано не на фиксированном размере фрагмента, как при фрагментировании фиксированного размера, а на его содержимом.

Алгоритму Content-Defined Chunking необходимо побайтно вычислить хеш-значение потока данных и разбить поток данных на фрагменты, когда хэш-значение соответствует заранее определенному значению. Однако побайтовое сравнение строки приведет к тяжелым вычислительным затратам. ФастКДК предлагает новый и эффективный подход Content-Defined Chunking. Он использует быстродействующий алгоритм хэширования Gear, пропуск минимальной длины, нормализация распределения по размерам блоков и, наконец, что не менее важно, каждый раз прокручивание двух байтов для ускорения алгоритма CDC, который может обеспечить примерно в 10 раз более высокую пропускную способность, чем подход CDC на основе Рабина.

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

algorithm FastCDC
    input: data buffer src, 
           data length n, 
    output: cut point i
    
    MinSize ← 2KB     // split minimum chunk size is 2 KB
    MaxSize ← 64KB    // split maximum chunk size is 64 KB
    Mask ← 0x0000d93003530000LL
    fp ← 0
    i ← 0
    
    // buffer size is less than minimum chunk size
    if n ≤ MinSize then
        return n
    if n ≥ MaxSize then
        n ← MaxSize
    
    // Skip the first MinSize bytes, and kickstart the hash
    while i < MinSize do
        fp ← (fp << 1 ) + Gear[src[i]]
        i ← i + 1
     
    while i < n do
        fp ← (fp << 1 ) + Gear[src[i]]
        if !(fp & Mask) then
            return i
        i ← i + 1
   
    return i

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

Вычислительная сложность

Все скользящие хэш-функции могут вычисляться за линейное время по количеству символов и обновляться за постоянное время, когда символы смещаются на одну позицию. В частности, вычисление скользящего хеша Рабина-Карпа для строки длиной $k$ требует $O(k)$ модульные арифметические операции, а хеширование циклическими полиномами требует $O(k)$ побитовое исключающее ИЛИ и циклические сдвиги .

См. также

• MinHash — техника интеллектуального анализа данных
• ш-черепица

Внешние ссылки

• MIT 6.006: Введение в алгоритмы 2011 — Декламация 9 — Rolling Hash