Использование CRC в качестве дайджеста для обнаружения дубликатов среди файлов

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

rsync уже решил эту проблему, используя в целом описанный вами подход.

Однако я хотел бы знать, может ли кто-нибудь порекомендовать, какой 32-битный алгоритм CRC (т.е. какой полином?) Лучше всего подходит для минимизации вероятности коллизий в этой ситуации?

Вы не увидите большой разницы между хорошо подобранными полиномами CRC. Скорость может быть для вас более важной, и в этом случае вы можете использовать аппаратный CRC, например crc32 инструкция по современным процессорам Intel. Этот использует полином CRC-32C (Кастаньоли) . Вы можете сделать это действительно быстро, используя все три арифметических модуля на одном ядре параллельно, вычисляя CRC на трех буферах в одном цикле, а затем комбинируя их. См. Ниже, как объединить CRC.

Или вы можете быстро вычислить CRC всего набора, как если бы вы выполнили CRC всего, но с использованием уже вычисленных CRC частей. Посмотрите на crc32_combine() в zlib. Это было бы лучше, чем брать CRC для кучи CRC. Комбинируя, вы сохраняете все математические качества алгоритма CRC.

Ответ Марка Адлера был удачным. Если бы я снял шляпу программиста и надел шляпу математика, кое-что из этого было бы очевидным. У него не было времени объяснять математику, так что я здесь для тех, кому интересно.

Процесс вычисления CRC - это, по сути, процесс полиномиального деления. Многочлены имеют коэффициенты по модулю 2, то есть коэффициент каждого члена равен 0 или 1, следовательно, многочлен степени N может быть представлен N-битным числом, каждый бит является коэффициентом члена (и процесс выполнения полиномиальное деление означает выполнение целого ряда операций XOR и сдвига). При проверке CRC блока данных мы рассматриваем «данные» как один большой многочлен, то есть длинную строку битов, каждый бит представляет коэффициент члена в многочлене. Назовем наш полином блока данных A. Для каждой «версии» CRC был выбран полином для CRC, который мы назовем P. Для 32-битных CRC P является полиномом. со степенью 32, поэтому в нем 33 члена и 33 коэффициента. Поскольку верхний коэффициент всегда равен 1, он является неявным, и мы можем представить многочлен 32-й степени 32-битным целым числом. (С вычислительной точки зрения это на самом деле довольно удобно.) Процесс вычисления CRC для блока данных A - это процесс нахождения остатка от деления A на P. То есть A всегда можно записать

A = Q * P + R

где R - многочлен степени меньше степени P, то есть R имеет степень 31 или меньше, поэтому он может быть представлен 32-битным целым числом. R - это, по сути, CRC. (Небольшое примечание: обычно к A добавляется 0xFFFFFFFF, но здесь это неважно.) Теперь, если мы объединим два блока данных A и B, «полином», соответствующий объединению двух блоков, будет полиномом для A, сдвинутым слева "на количество битов в B плюс B. Другими словами, многочлен для A&B равен A * S + B, где S - это многочлен, соответствующий единице, за которой следует N нулей, где N - количество биты в B. (т.е. S = x ** N). Тогда что мы можем сказать о CRC для A&B? Предположим, мы знаем A = Q * P + R и B = Q '* P + R', т.е. R - это CRC для A, а R '- это CRC для B. Предположим, мы также знаем, что S = q * P + r. потом

A * S + B = (Q*P+R)*(q*P+r) + (Q'*P+R')
          = Q*(q*P+r)*P + R*q*P + R*r + Q'*P + R'
          = (Q*S + R*q + Q') * P    + R*r + R'

Таким образом, чтобы найти остаток, когда A * S + B делится на P, нам нужно только найти остаток, когда R * r + R 'делится на P. Таким образом, чтобы вычислить CRC конкатенации двух потоков данных A и B , нам нужно знать только отдельные CRC потоков данных, то есть R и R ', и длину N конечного потока данных B (чтобы мы могли вычислить r). Это также содержание одного из комментариев Marks other: если длины конечных потоков данных B ограничены несколькими значениями, мы можем предварительно вычислить r для каждой из этих длин, что делает комбинацию двух CRC довольно тривиальной. (Для произвольной длины N вычисление r нетривиально, но это намного быстрее (log_2 N), чем повторное деление по всей длине B.)

Примечание: приведенное выше не является точным описанием CRC. Происходят некоторые сдвиги. Чтобы быть точным, если L - многочлен, представленный 0xFFFFFFFF, то есть L = x * 31 + x * 30 + ... + x + 1, а S_n - это «сдвиг влево на n битов» полином, то есть S_n = x ** n, тогда CRC блока данных с полиномом A из N битов является остатком, когда (L * S_N + A) * S_32 делится на P, то есть когда (L&A) * S_32 равно делится на P, где & - оператор «конкатенации».

Кроме того, я не согласен с одним из комментариев Марка, но он может поправить меня, если я ошибаюсь. Если мы уже знаем R и R ', сравнение времени для вычисления CRC A&B с использованием вышеупомянутой методологии по сравнению с вычислением его прямым способом не зависит от отношения len (A) к len (B) - к вычислить его "прямым" способом, действительно не нужно повторно вычислять CRC для всего связанного набора данных. Используя наши обозначения выше, нужно только вычислить CRC R * S + B. То есть вместо того, чтобы предварительно отложить 0xFFFFFFFF до B и вычислить его CRC, мы добавляем R к B и вычисляем его CRC. Таким образом, это сравнение времени для повторного вычисления CRC B со временем для вычисления r (с последующим делением R * r + R 'на P, что, вероятно, тривиально и несущественно по времени).

ответ Марка Адлера касается технического вопроса, поэтому я не буду этим заниматься здесь. Здесь я собираюсь указать на серьезную потенциальную ошибку в алгоритме синхронизации, предложенном в вопросе ОП, и предложить небольшое улучшение.

Контрольные суммы и хэши предоставляют единое значение подписи для некоторых данных. Однако, поскольку они имеют конечную длину, количество возможных уникальных значений контрольной суммы / хэша всегда меньше возможных комбинаций необработанных данных, если данные длиннее. Например, 4-байтовый CRC может принимать только 4 294 967 296 уникальных значений, в то время как даже 5-байтовое значение, которое может быть данными, может принимать в 8 раз больше значений. Это означает, что для любых данных, длина которых превышает длину самой контрольной суммы, всегда существует одна или несколько комбинаций байтов с точно такой же подписью.

При использовании для проверки целостности предполагается, что вероятность того, что несколько другой поток данных приведет к одной и той же подписи, мала, поэтому мы можем предположить, что данные одинаковы, если подпись одинакова. Важно отметить, что мы начинаем с некоторых данных d и проверяем, что с учетом контрольной суммы c, вычисленной с использованием функции контрольной суммы, f, что f(d) == c.

Однако в алгоритме OP различное использование вносит незаметное пагубное снижение уверенности. В алгоритме OP сервер A будет начинать с необработанных данных [d1A,d2A,d3A,d4A] и генерировать набор контрольных сумм [c1,c2,c3,c4] (где dnA - n-й элемент данных на сервере A). Затем сервер B получит этот список контрольных сумм и проверит свой собственный список контрольных сумм, чтобы определить, отсутствуют ли какие-либо. Скажем, на сервере B есть список [c1,c2,c3,c5]. Тогда должно произойти то, что он запросит d4 с сервера A, и в идеальном случае синхронизация сработала правильно.

Если мы вспомним о возможности коллизий и о том, что для их создания не всегда требуется столько данных (например, CRC("plumless") == CRC("buckeroo")), то мы быстро поймем, что лучшая гарантия, которую предоставляет наша схема, - это то, что сервер B определенно не имеет d4A но он не может гарантировать, что у него есть [d1A,d2A,d3A]. Это потому, что возможно, что f(d1A) = c1 и f(d1B) = c1, хотя d1A и d1B различны, и мы хотели бы, чтобы на обоих серверах были оба. В этой схеме ни один из серверов никогда не может знать о существовании как d1A, так и d1B. Мы можем использовать все больше и больше контрольных сумм и хэшей, устойчивых к коллизиям, но эта схема никогда не может гарантировать полную синхронизацию. Это становится более важным, чем большее количество файлов должна отслеживать сеть. Я бы рекомендовал использовать криптографический хеш, например SHA1, для которого не было обнаружено коллизий.

Возможное снижение этого риска - введение избыточных хэшей. Один из способов сделать это - использовать совершенно другой алгоритм, поскольку, хотя это возможно crc32(d1) == crc32(d2), менее вероятно, что adler32(d1) == adler32(d2) одновременно. В этой статье говорится, что вы не получите всего таким образом. Если использовать обозначение OP, то также менее вероятно, что crc32('a' & d1) == crc32('a' & d2) и crc32('b' & d1) == crc32('b' & d2) одновременно истинны, поэтому вы можете "добавить" к комбинациям с меньшей вероятностью столкновений. Однако я думаю, что вы можете просто использовать хэш-функцию, устойчивую к столкновениям, такую ​​как SHA512, которая на практике, вероятно, не окажет большого влияния на вашу производительность.