Роллинг хеша

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

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

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

В лучшем случае скользящие хеш-значения попарно независимы. ^[1] или сильно универсальный . они не могут быть 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 МБ . ^[2]

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

Хеширование циклическим полиномом ^[3]— иногда называемый Бужаш — также прост и имеет то преимущество, что позволяет избежать умножения и вместо этого использовать сдвиг ствола . Это форма хеширования таблиц : предполагается, что существует некоторая хеш-функция. $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$ последовательные биты. ^[1] На практике этого можно добиться целочисленным делением $H\rightarrow H\div 2^{k-1}$ .

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

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

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

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

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

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

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

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 необходимо побайтно вычислить хеш-значение потока данных и разбить поток данных на фрагменты, когда хеш-значение соответствует предопределенному значению. Однако побайтовое сравнение строки приведет к тяжелым вычислительным затратам. ФастКДК ^[8] предлагает новый и эффективный подход Content-Defined Chunking. Он использует быстродействующий алгоритм хэширования Gear, ^[9] пропуск минимальной длины, нормализация распределения по размерам фрагментов и, наконец, что не менее важно, каждый раз прокручивание двух байтов для ускорения алгоритма CDC, который может обеспечить примерно в 10 раз более высокую пропускную способность, чем подход CDC на основе Рабина. ^[10]

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

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 от размера блоков на основе Рабина). ^[10]) при сегментации потока данных.

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

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

См. также

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

Сноски

^ Перейти обратно: ^а ^б ^с Дэниел Лемир, Оуэн Кейзер: Рекурсивное хеширование n -грамм в лучшем случае попарно независимо, Computer Speech & Language 24 (4), страницы 698–710, 2010. arXiv:0705.4676 .
^ «Ссылки — документация restic 0.9.0» . restic.readthedocs.io . Проверено 24 мая 2018 г.
^ Джонатан Д. Коэн, Рекурсивные функции хеширования для n -грамм, ACM Trans. Инф. Сист. 15 (3), 1997.
^ Перейти обратно: ^а ^б «Основы — введение в состав блоков, определяемых контентом (CDC)» . 2015.
^ Хорват, Адам (24 октября 2012 г.). «Рабин Карп скользящий хэш — фрагменты динамического размера на основе хешированного содержимого» .
^ Перейти обратно: ^а ^б «Структуры данных и форматы файлов — документация Borg — Dedupliating Archiver 1.1.5» . borgbackup.readthedocs.io . Проверено 24 мая 2018 г.
^ "Алгоритм Rsyncrypto" .
^ Дэн; Ху, Юйчун; Чжан, Юйчэн (2005). Хун; Фэн , Ся, Вэнь; Цзян , ISBN 9781931971300 . Проверено 24 июля 2020 г. {{cite book}}: |website= игнорируется ( помогите )
^ Ся, Вэнь; Цзян, Хун; Фэн, Дэн; Тиан, Лей; Фу, Мин; Чжоу, Юкунь (2014). «Ddelta: подход к быстрому дельта-сжатию на основе дедупликации». Оценка производительности . 79 : 258–272. дои : 10.1016/j.peva.2014.07.016 . ISSN 0166-5316 .
^ Перейти обратно: ^а ^б Ся, Вэнь; Цзоу, Сянъюй; Цзян, Хун; Чжоу, Юкунь; Лю, Чуаньи; Фэн, Дэн; Хуа, Ю; Ху, Юйчун; Чжан, Юйчэн (16 июня 2020 г.). «Разработка быстрого группирования по содержанию для систем хранения данных на основе дедупликации» . Транзакции IEEE в параллельных и распределенных системах . 31 (9): 2017–2031. дои : 10.1109/TPDS.2020.2984632 . S2CID 215817722 . Проверено 22 июля 2020 г.

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

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

[lemirekaser-1] Перейти обратно: ^а ^б ^с Дэниел Лемир, Оуэн Кейзер: Рекурсивное хеширование n -грамм в лучшем случае попарно независимо, Computer Speech & Language 24 (4), страницы 698–710, 2010. arXiv:0705.4676 .

[2] «Ссылки — документация restic 0.9.0» . restic.readthedocs.io . Проверено 24 мая 2018 г.

[3] Джонатан Д. Коэн, Рекурсивные функции хеширования для n -грамм, ACM Trans. Инф. Сист. 15 (3), 1997.

[restic_cdc-4] Перейти обратно: ^а ^б «Основы — введение в состав блоков, определяемых контентом (CDC)» . 2015.

[5] Хорват, Адам (24 октября 2012 г.). «Рабин Карп скользящий хэш — фрагменты динамического размера на основе хешированного содержимого» .

[borg_dedup-6] Перейти обратно: ^а ^б «Структуры данных и форматы файлов — документация Borg — Dedupliating Archiver 1.1.5» . borgbackup.readthedocs.io . Проверено 24 мая 2018 г.

[7] "Алгоритм Rsyncrypto" .

[Xia_Zhou_Jiang_Feng-8] Дэн; Ху, Юйчун; Чжан, Юйчэн (2005). Хун; Фэн , Ся, Вэнь; Цзян , ISBN 9781931971300 . Проверено 24 июля 2020 г. {{cite book}}: |website= игнорируется ( помогите )

[XiaJiang2014-9] Ся, Вэнь; Цзян, Хун; Фэн, Дэн; Тиан, Лей; Фу, Мин; Чжоу, Юкунь (2014). «Ddelta: подход к быстрому дельта-сжатию на основе дедупликации». Оценка производительности . 79 : 258–272. дои : 10.1016/j.peva.2014.07.016 . ISSN 0166-5316 .

[IEEE_Journals_&_Magazine_2020-10] Перейти обратно: ^а ^б Ся, Вэнь; Цзоу, Сянъюй; Цзян, Хун; Чжоу, Юкунь; Лю, Чуаньи; Фэн, Дэн; Хуа, Ю; Ху, Юйчун; Чжан, Юйчэн (16 июня 2020 г.). «Разработка быстрого группирования по содержанию для систем хранения данных на основе дедупликации» . Транзакции IEEE в параллельных и распределенных системах . 31 (9): 2017–2031. дои : 10.1109/TPDS.2020.2984632 . S2CID 215817722 . Проверено 22 июля 2020 г.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]