Использование CRC в качестве дайджеста для обнаружения дубликатов среди файлов
Основное использование CRC и аналогичных вычислений (таких как Fletcher и Adler), по-видимому, для обнаружения ошибок передачи. Таким образом, большинство исследований, которые я видел, похоже, посвящено проблеме вероятности обнаружения мелкомасштабных различий между двумя наборами данных. Мои потребности немного отличаются.
Далее следует очень приблизительное описание проблемы. Детали гораздо сложнее, но приведенное ниже описание иллюстрирует функциональность, которую я ищу. Этот небольшой отказ от ответственности предназначен для защиты от таких ответов, как "Почему вы решаете свою проблему таким образом, когда вам легче ее решить другим способом, который я предлагаю?" - Мне нужно решить мою проблему таким образом по множеству причин, которые не имеют отношения к этому вопросу или сообщению, поэтому, пожалуйста, не размещайте такие ответы.
Я имею дело с коллекциями наборов данных (размер ~1 МБ) в распределенной сети. Вычисления выполняются для этих наборов данных, и скорость / производительность имеют решающее значение. Мне нужен механизм, позволяющий избежать повторной передачи наборов данных. То есть мне нужен какой-то способ генерации уникального идентификатора (UID) для каждого набора данных заданного размера. (Затем я передаю размер набора данных и UID с одного компьютера на другой, и принимающему устройству необходимо запрашивать передачу данных только в том случае, если у него его еще нет локально, на основе UID.)
Это похоже на разницу между использованием CRC для проверки изменений в файле и использованием CRC в качестве дайджеста для обнаружения дубликатов среди файлов. Я не видел никаких дискуссий о последнем использовании.
Я не занимаюсь вопросами подделки, то есть мне не нужно криптографическое хеширование на прочность.
В настоящее время я использую простой 32-битный CRC сериализованных данных, и это до сих пор мне хорошо помогало. Однако я хотел бы знать, может ли кто-нибудь порекомендовать, какой 32-битный алгоритм CRC (т.е. какой полином?) Лучше всего подходит для минимизации вероятности столкновений в этой ситуации?
Другой вопрос, который у меня есть, немного более тонкий. В моей текущей реализации я игнорирую структуру моего набора данных и фактически просто CRC сериализованную строку, представляющую мои данные. Однако по разным причинам я хочу изменить свою методологию CRC следующим образом. Предположим, мой набор данных верхнего уровня представляет собой набор некоторых необработанных данных и нескольких подчиненных наборов данных. Моя текущая схема по существу объединяет необработанные данные и все подчиненные наборы данных, а затем CRC - результат. Тем не менее, в большинстве случаев у меня уже есть CRC подчиненных наборов данных, и я предпочел бы создать свой UID набора данных верхнего уровня путем объединения необработанных данных с CRC подчиненных наборов данных, а затем CRC это конструкция. Вопрос в том, как использование этой методологии влияет на вероятность столкновений?
Чтобы выразить это на языке, который позволит мне обсудить свои мысли, я определю немного обозначений. Позвоните в мой набор данных верхнего уровня Tи предположим, что он состоит из набора необработанных данных R и подчиненные наборы данных Si, i=1..n, Я могу написать это как T = (R, S1, S2, ..., Sn), Если & представляет конкатенацию наборов данных, моя оригинальная схема может рассматриваться как:
UID_1(T) = CRC(R & S1 & S2 & ... & Sn)
и моя новая схема может рассматриваться как
UID_2(T) = CRC(R & CRC(S1) & CRC(S2) & ... & CRC(Sn))
Тогда мои вопросы: (1) если T а также T' сильно отличаются, что алгоритм CRC минимизирует prob( UID_1(T)=UID_1(T') )и какой алгоритм CRC минимизирует prob( UID_2(T)=UID_2(T') )и как эти две вероятности сравниваются?
Мои (наивные и неосведомленные) мысли по этому поводу таковы. Предположим, различия между T а также T' WLOG говорят, что только в одном подчиненном наборе данных S1!=S1', Если это случится CRC(S1)=CRC(S1')тогда явно у нас будет UID_2(T)=UID_2(T'), С другой стороны, если CRC(S1)!=CRC(S1')тогда разница между R & CRC(S1) & CRC(S2) & ... & CRC(Sn) а также R & CRC(S1') & CRC(S2) & ... & CRC(Sn) это небольшая разница только в 4 байтах, поэтому способность UID_2 обнаруживать различия фактически совпадает со способностью CRC обнаруживать ошибки передачи, т.е. его способность обнаруживать ошибки только в нескольких битах, которые не разделены между собой. Поскольку это то, для чего предназначены CRC, я думаю, что UID_2 довольно безопасен, поскольку CRC, который я использую, хорош для обнаружения ошибок передачи. Чтобы выразить это с точки зрения нашей записи,
prob( UID_2(T)=UID_2(T') ) = prob(CRC(S1)=CRC(S1')) + (1-prob(CRC(S1)=CRC(S1'))) * probability of CRC not detecting error a few bits.
Позвольте вызвать вероятность того, что CRC не обнаружит ошибку в несколько бит Pи вероятность того, что он не обнаружит большие различия в наборе данных большого размера Q, Выше может быть написано примерно как
prob( UID_2(T)=UID_2(T') ) ~ Q + (1-Q)*P
Теперь я немного поменяю свой UID следующим образом. Для "фундаментальной" части данных, то есть набора данных T=(R) где R - это просто double, integer, char, bool и т. д., определите UID_3(T)=(R), Тогда для набора данных T состоящий из вектора наборов подчиненных данных T = (S1, S2, ..., Sn)определить
UID_3(T) = CRC(ID_3(S1) & ID_3(S2) & ... & ID_3(Sn))
Предположим, конкретный набор данных T имеет подчиненные наборы данных, вложенные m-уровни глубокие, то, в каком-то смутном смысле, я думаю, что
prob( UID_3(T)=UID_3(T') ) ~ 1 - (1-Q)(1-P)^m
Учитывая, что эти вероятности малы в любом случае, это может быть аппроксимировано как
1 - (1-Q)(1-P)^m = Q + (1-Q)*P*m + (1-Q)*P*P*m*(m-1)/2 + ... ~ Q + m*P
Так что, если я знаю свой максимальный уровень вложенности m, и я знаю P а также Q для различных CRC я хочу выбрать CRC, который дает мне минимальное значение для Q + m*P, Если, как я подозреваю, может быть, P~QВышесказанное упрощает это. Моя вероятность ошибки для UID_1 P, Моя вероятность ошибки для UID_3 (m+1)P, где m мой максимальный уровень вложенности (рекурсии).
Все это кажется разумным?
3 ответа
Мне нужен механизм, позволяющий избежать повторной передачи наборов данных.
rsync уже решил эту проблему, используя общий подход, который вы изложили.
Тем не менее, я хотел бы знать, может ли кто-нибудь порекомендовать, какой 32-разрядный алгоритм CRC (т.е. какой полином?) Лучше всего подходит для минимизации вероятности столкновений в этой ситуации?
Вы не увидите большой разницы среди правильно выбранных полиномов CRC. Скорость может быть более важна для вас, и в этом случае вы можете использовать аппаратную CRC, например, crc32 инструкция по современным процессорам Intel. Тот использует полином CRC-32C (Castagnoli). Вы можете сделать это очень быстро, используя все три арифметических устройства на одном ядре параллельно, вычислив CRC для трех буферов в одном цикле, а затем комбинируя их. Ниже показано, как комбинировать CRC.
Тем не менее, в большинстве случаев у меня уже есть CRC подчиненных наборов данных, и я предпочел бы построить свой UID набора данных верхнего уровня путем объединения необработанных данных с CRC подчиненных наборов данных, а затем CRC этой конструкции,
Или вы можете быстро вычислить CRC всего набора, как если бы вы сделали CRC для всего этого, но с использованием уже рассчитанных CRC кусков. смотреть на crc32_combine() в злиб. Это было бы лучше, чем принимать CRC из набора CRC. Комбинируя, вы сохраняете всю математическую ценность алгоритма CRC.
Марк Адлер ответил ударом. Если бы я снял шляпу программистов и надел шляпу математиков, кое-что из этого должно было быть очевидным. У него не было времени, чтобы объяснить математику, поэтому я буду здесь для тех, кто заинтересован.
Процесс вычисления CRC по сути является процессом деления полинома. Полиномы имеют коэффициенты mod 2, то есть коэффициент каждого члена равен 0 или 1, следовательно, полином степени N может быть представлен N-битным числом, причем каждый бит является коэффициентом члена (и процесс выполнения Полиномиальное деление сводится к выполнению целого ряда операций XOR и Shift. При CRC'е блока данных мы рассматриваем "данные" как один большой полином, то есть длинную строку битов, каждый бит представляет коэффициент члена в полиноме. Назовем наш многочлен блока данных А. Для каждой "версии" 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. (Небольшое примечание: обычно один предваряется 0xFFFFFFFF к A, но это неважно здесь.) Теперь, если мы объединяем два блока данных A и B, "полином", соответствующий объединению двух блоков, является полиномом для A, сдвинут слева "на число битов в B, плюс B. Другими словами, полином для A&B является A*S+B, где S - это полином, соответствующий 1, за которым следуют 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). Это также содержание одного из замечаний других комментариев: если длины конечных потоков данных 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 с сервера А, и синхронизация работала должным образом в идеальном случае.
Если мы вспомним возможность коллизий и то, что для ее создания не всегда требуется столько данных (например, 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, которая на практике, вероятно, не окажет такого большого влияния на вашу производительность.