Прокатки хэш (также известная как рекурсивное хеширование или прокатка контрольная сумма) является хэш - функцией , где входным хешируются в окне , которое проходит через вход.
Несколько хеш-функций позволяют очень быстро вычислять скользящий хэш - новое значение хеш-функции быстро вычисляется с учетом только старого значения хеш-функции, старого значения, удаленного из окна, и нового значения, добавляемого в окно - аналогично тому, как Функция скользящего среднего может быть вычислена намного быстрее, чем другие фильтры нижних частот.
Одним из основных приложений является алгоритм поиска строки Рабина – Карпа , который использует скользящий хеш, описанный ниже. Еще одно популярное приложение - программа rsync , в которой в качестве скользящего хеша используется контрольная сумма на основе adler-32 Марка Адлера . Сетевая файловая система с низкой пропускной способностью (LBFS) использует отпечаток Рабина в качестве скользящего хэша. FastCDC (Fast Content-Defined Chunking) использует эффективный для вычислений отпечаток Gear в качестве скользящего хэша.
В лучшем случае скользящие хеш-значения попарно независимы [1] или строго универсальны . Например, они не могут быть независимыми по трем направлениям .
Полиномиальный скользящий хеш
Строка алгоритм поиска Рабин-Карп часто объясняется использование подвижной хэш - функции , которая использует только умножения и сложения:
- ,
где является константой, а являются входными символами (но эта функция не является отпечатком Рабина , см. ниже).
Во избежание манипулирования огромными значения, вся математика выполняется по модулю . Выбор а также критически важен для хорошего хеширования; см. линейный конгруэнтный генератор для более подробного обсуждения.
Удаление и добавление символов просто включает добавление или вычитание первого или последнего члена. Чтобы сдвинуть все символы на одну позицию влево, необходимо умножить всю сумму. от . Чтобы сдвинуть все символы на одну позицию вправо, необходимо разделить всю сумму от . Обратите внимание, что в арифметике по модулюможно выбрать мультипликативную обратную по которому можно умножить, чтобы получить результат деления без фактического выполнения деления.
Отпечаток пальца рабина
Отпечатков пальцев Рабина еще один хэш, который также интерпретирует входные данные в виде полинома, но над полем Галуа GF (2) . Вместо того, чтобы рассматривать ввод как полином из байтов, он рассматривается как полином из битов, и вся арифметика выполняется в GF (2) (аналогично CRC32 ). Хеш - это результат деления этого многочлена на неприводимый многочлен над GF (2). Можно обновить отпечаток Рабина, используя только входной и выходной байты, что фактически делает его скользящим хешем.
Поскольку он имеет того же автора, что и алгоритм поиска строки Рабина – Карпа, который часто объясняется другим, более простым скользящим хешем, и поскольку этот более простой скользящий хеш также является полиномом, оба скользящих хеш-значения часто ошибочно принимают друг за друга. Программное обеспечение для резервного копирования restic использует отпечаток Рабина для разделения файлов с размером большого двоичного объекта от 512 байт до 8 МБ. [2]
Циклический полином
Хеширование с помощью циклического полинома [3], иногда называемого Бужашем, также простое, но его преимущество заключается в том, что он позволяет избежать умножений, используя вместо этого сдвиг в форме бочки . Это форма хеширования табуляции : предполагается, что есть некоторая хеш-функция. от символов к целым числам в интервале . Эта хеш-функция может быть просто массивом или хеш-таблицей, отображающей символы в случайные целые числа. Пусть функциябыть циклическим двоичным вращением (или круговым сдвигом ): он поворачивает биты на 1 влево, сдвигая последний бит в первую позицию. Например,. Позволятьбыть побитовым исключающим или . Хеш-значения определены как
где умножение на степень двойки может быть выполнено двоичным сдвигом. Результат - число в.
Вычисление хеш-значений в скользящем режиме выполняется следующим образом. Позволятьбыть предыдущим значением хеш-функции. Повернуть однажды: . Если это персонаж, который нужно удалить, поверните его раз: . Затем просто установите
где это новый персонаж.
Хеширование с помощью циклических многочленов является строго универсальным или попарно независимым: просто оставьте первое биты. То есть взять результат и уволить любой последовательные биты. [1] На практике это может быть достигнуто целочисленным делением.
Нарезка на основе содержимого с использованием скользящего хеша
Одним из интересных вариантов использования скользящей хеш-функции является то, что она может создавать динамические блоки на основе содержимого потока или файла. Это особенно полезно, когда требуется отправить по сети только измененные фрагменты большого файла, и простое добавление байта в начале файла приведет к обновлению всех окон фиксированного размера, в то время как на самом деле только первые "кусок" был изменен.
Самый простой подход к вычислению динамических фрагментов - это вычисление скользящего хэша, и если он соответствует шаблону (например, все младшие N бит - нули), то это граница фрагмента. Такой подход гарантирует, что любое изменение в файле повлияет только на его текущий и, возможно, следующий фрагмент, но ни на что другое.
Когда границы известны, блоки необходимо сравнить по их хеш-значениям, чтобы определить, какой из них был изменен и нуждается в передаче по сети. [4] Программа резервного копирования Attic использует алгоритм Buzhash с настраиваемым диапазоном размеров фрагментов для разделения потоков файлов. [5]
Нарезка на основе содержимого с использованием скользящей суммы
Несколько программ, включая gzip (с --rsyncable
опцией) и rsyncrypto, выполняют нарезку на основе содержимого на основе этой конкретной (невзвешенной) скользящей суммы: [6]
где
- это сумма 8196 последовательных байтов, заканчивающихся байтом (требуется 21 бит памяти),
- это байт файла,
- представляет собой «хеш-значение», состоящее из нижних 12 битов .
Сдвиг окна на один байт просто включает добавление нового символа к сумме и вычитание самого старого символа (уже не находящегося в окне) из суммы.
Для каждого где , эти программы разрезают файл между а также . Такой подход гарантирует, что любое изменение в файле повлияет только на его текущий и, возможно, следующий фрагмент, но не на другой фрагмент.
Отпечаток устройства 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]
Программное обеспечение
- Rollinghashcpp - это бесплатная реализация на C ++ нескольких скользящих хеш-функций.
- Rollinghashjava - это Java-реализация скользящих хеш-функций с лицензией Apache.
Смотрите также
Внешние ссылки
Сноски
- ^ a b c Даниэль Лемир, Оуэн Кейзер: Рекурсивное хеширование n -грамм в лучшем случае попарно не зависит, Computer Speech & Language 24 (4), страницы 698–710, 2010. arXiv: 0705.4676 .
- ^ «Ссылки - документация restic 0.9.0» . restic.readthedocs.io . Проверено 24 мая 2018 .
- ^ Джонатан Д. Коэн, Рекурсивные функции хеширования для n -грамм, ACM Trans. Инф. Syst. 15 (3), 1997.
- ^ Хорват, Адам (24 октября 2012 г.). «Скользящий хеш Рабина Карпа - блоки динамического размера на основе хешированного содержимого» .
- ^ «Структуры данных и форматы файлов - документация Borg - Deduplicating Archiver 1.1.5» . borgbackup.readthedocs.io . Проверено 24 мая 2018 .
- ^ «Алгоритм Rsyncrypto» .
- ^ Ся, Вэнь; Чжоу, Юкунь; Цзян, Хун; Фэн, Дэн; Хуа Ю; Ху Юйчун; Лю, Цин; Чжан, Юйчэн. «FastCDC: быстрый и эффективный подход к разделению на блоки с определением содержимого для дедупликации данных» . USENIX . Проверено 24 июля 2020 .
- ^ Ся, Вэнь; Цзян, Хун; Фэн, Дэн; Тиан, Лэй; Фу, Мин; Чжоу, Юкун (2014). «Ddelta: основанный на дедупликации подход быстрого дельта-сжатия». Оценка производительности . 79 : 258–272. DOI : 10.1016 / j.peva.2014.07.016 . ISSN 0166-5316 .
- ^ а б Ся, Вэнь; Цзоу, Сянъюй; Цзян, Хун; Чжоу, Юкунь; Лю, Чуаньи; Фэн, Дэн; Хуа Ю; Ху Юйчун; Чжан, Юйчэн (16.06.2020). «Дизайн быстрого разбиения на блоки с определением содержимого для систем хранения на основе дедупликации данных» . Транзакции IEEE в параллельных и распределенных системах . 31 (9): 2017–2031. DOI : 10.1109 / TPDS.2020.2984632 . S2CID 215817722 . Проверено 22 июля 2020 .
- ^ М. Furer, Faster целочисленное умножение в: STOC '07, 2007, стр 57-66..