Jump to content

Роллинг хеша

(Перенаправлено с скользящего хеширования )

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

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

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

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

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

[ редактировать ]

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

,

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

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

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

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

[ редактировать ]

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

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

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

[ редактировать ]

Хеширование циклическим полиномом [3] — иногда называемый Бужаш — также прост и имеет то преимущество, что позволяет избежать умножения и вместо этого использовать сдвиг ствола . Это форма хеширования таблиц : предполагается, что существует некоторая хеш-функция. от символов к целым числам в интервале . Эта хэш-функция может быть просто массивом или хэш-таблицей, отображающей символы в случайные целые числа. Пусть функция быть циклическим двоичным вращением (или круговым сдвигом ): он поворачивает биты на 1 влево, перемещая последний бит в первую позицию. Например, . Позволять быть побитовым исключающим или . Хэш-значения определяются как

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

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

где это новый персонаж.

Хеширование циклическими полиномами является строго универсальным или попарно независимым: просто сохраните первый биты. То есть взять результат и отклонить любые последовательные биты. [1] На практике этого можно добиться целочисленным делением .

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

[ редактировать ]

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

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

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

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

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

[ редактировать ]

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

где

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

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

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

Отпечаток устройства и алгоритм фрагментирования на основе контента 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
    Mask0x0000d93003530000LL
    fp0
    i0
    
    // buffer size is less than minimum chunk size
    if nMinSize then
        return n
    if nMaxSize then
        nMaxSize
    
    // Skip the first MinSize bytes, and kickstart the hash
    while i < MinSize do
        fp ← (fp << 1 ) + Gear[src[i]]
        ii + 1
     
    while i < n do
        fp ← (fp << 1 ) + Gear[src[i]]
        if !(fp & Mask) then
            return i
        ii + 1
   
    return i

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

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

[ редактировать ]

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

См. также

[ редактировать ]
  1. ^ Jump up to: Перейти обратно: а б с Дэниел Лемир, Оуэн Кейзер: Рекурсивное хеширование 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.
  4. ^ Jump up to: Перейти обратно: а б «Основание — введение в структуру фрагментов, определяемых контентом (CDC)» . 2015.
  5. ^ Хорват, Адам (24 октября 2012 г.). «Роллинговый хэш Рабина Карпа — фрагменты динамического размера на основе хешированного содержимого» .
  6. ^ Jump up to: Перейти обратно: а б «Структуры данных и форматы файлов — документация Borg — Dedupliating Archiver 1.1.5» . borgbackup.readthedocs.io . Проверено 24 мая 2018 г.
  7. ^ "Алгоритм Rsyncrypto" .
  8. ^ Дэн; Ху, Юйчун; Чжан, Юйчэн (2005). Хун; Фэн , Ся, Вэнь; Цзян , ISBN  9781931971300 . Проверено 24 июля 2020 г. {{cite book}}: |website= игнорируется ( помогите )
  9. ^ Ся, Вэнь; Цзян, Хун; Фэн, Дэн; Тиан, Лей; Фу, Мин; Чжоу, Юкунь (2014). «Ddelta: подход к быстрому дельта-сжатию на основе дедупликации». Оценка производительности . 79 : 258–272. дои : 10.1016/j.peva.2014.07.016 . ISSN   0166-5316 .
  10. ^ Jump up to: Перейти обратно: а б Ся, Вэнь; Цзоу, Сянъюй; Цзян, Хун; Чжоу, Юкунь; Лю, Чуаньи; Фэн, Дэн; Хуа, Ю; Ху, Юйчун; Чжан, Юйчэн (16 июня 2020 г.). «Разработка быстрого группирования по содержанию для систем хранения данных на основе дедупликации» . Транзакции IEEE в параллельных и распределенных системах . 31 (9): 2017–2031. дои : 10.1109/TPDS.2020.2984632 . S2CID   215817722 . Проверено 22 июля 2020 г.
[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: e31eceb5c53e092f8723daf4cdbea9f2__1717049520
URL1:https://arc.ask3.ru/arc/aa/e3/f2/e31eceb5c53e092f8723daf4cdbea9f2.html
Заголовок, (Title) документа по адресу, URL1:
Rolling hash - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)