Роллинг хэш

Тип хэш-функции

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

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

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

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

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

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

${\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 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] — иногда называемым Buzhash — также просто и имеет преимущество в том, что позволяет избежать умножений, используя вместо этого сдвиги в виде бочки . Это форма табуляции хеширования : она предполагает, что существует некоторая хеш-функция от символов до целых чисел в интервале . Эта хеш-функция может быть просто массивом или хеш-таблицей, отображающей символы в случайные целые числа. Пусть функция будет циклическим бинарным вращением (или круговым сдвигом ): она вращает биты на 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}}$

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

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

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

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

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

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

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

${\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}$

Алгоритм фрагментации на основе отпечатков пальцев и содержимого FastCDC

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

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

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

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

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

Сложность вычислений

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

Смотрите также

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

Сноски

1. Дэниел Лемир, Оуэн Кейзер: Рекурсивное хеширование n- грамм в лучшем случае попарно независимо, Computer Speech & Language 24 (4), страницы 698–710, 2010. arXiv:0705.4676.
2. "Ссылки — документация restic 0.9.0". restic.readthedocs.io . Получено 24.05.2018 .
3. Джонатан Д. Коэн, Рекурсивные функции хеширования для n -граммов, ACM Trans. Inf. Syst. 15 (3), 1997.
4. "Foundation - Знакомство с Content Defined Chunking (CDC)". 2015.
5. Хорват, Адам (24 октября 2012 г.). «Рабин Карп, скользящий хеш — динамические размеры фрагментов на основе хешированного содержимого».
6. "Структуры данных и форматы файлов — Документация Borg - Deduplicating Archiver 1.1.5". borgbackup.readthedocs.io . Получено 24.05.2018 .
7. «Алгоритм Rsyncrypto».
8. Ся, Вэнь; Чжоу, Юкунь; Цзян, Хун; Фэн, Дэн; Хуа, Ю; Ху, Юйчун; Лю, Цин; Чжан, Юйчэн (2005). FastCDC: быстрый и эффективный подход к дедупликации данных на основе содержимого. Ассоциация Усеникс. ISBN 9781931971300. Получено 24.07.2020 . {{cite book}}: |website=проигнорировано ( помощь )
9. Ся, Вэнь; Цзян, Хун; Фэн, Дэн; Тянь, Лэй; Фу, Мин; Чжоу, Юкунь (2014). «Ddelta: подход к быстрому дельта-сжатию, основанный на дедупликации». Оценка производительности . 79 : 258–272. doi :10.1016/j.peva.2014.07.016. ISSN  0166-5316.
10. Xia, Wen; Zou, Xiangyu; Jiang, Hong; Zhou, Yukun; Liu, Chuanyi; Feng, Dan; Hua, Yu; Hu, Yuchong; Zhang, Yucheng (2020-06-16). "Проектирование быстрого фрагментирования, определяемого содержимым, для систем хранения данных на основе дедупликации". IEEE Transactions on Parallel and Distributed Systems . 31 (9): 2017–2031. doi :10.1109/TPDS.2020.2984632. S2CID  215817722. Получено 2020-07-22 .

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

• MIT 6.006: Введение в алгоритмы 2011 - Чтение 9 - Rolling Hash