Контрольная сумма: CRC или хеш?

Если оставить в стороне соображения производительности и безопасности, и если предположить, что хеш-функция с идеальным лавинным эффектом, что я должен использовать для контрольной суммы блоков данных: CRC32 или хэш, усеченный до N байтов? Т.е. у которых будет меньшая вероятность пропустить ошибку? Конкретно:

  1. CRC32 против 4-байтового хеша
  2. CRC32 против 8-байтового хеша
  3. CRC64 против 8-байтового хеша

Блоки данных должны многократно передаваться по сети и сохраняться на диске. Блоки могут иметь размер от 1 КБ до 1 ГБ.

Насколько я понимаю, CRC32 может обнаруживать до 32-битных флипов со 100% надежностью, но после этого его надежность приближается к 1-2^(-32), а для некоторых паттернов намного хуже. Идеальная 4-байтовая надежность хеширования всегда равна 1-2^(-32), так что разберитесь.

8-байтовый хэш должен иметь гораздо лучшую общую надежность (2^(-64) шанс пропустить ошибку), поэтому следует ли ему отдавать предпочтение перед CRC32? Что насчет CRC64?

Думаю, ответ зависит от типа ошибок, которых можно ожидать при такой операции. Скорее всего, мы увидим редкие 1-битные перевороты или массивные повреждения блоков? Кроме того, учитывая, что в большинстве систем хранения и сетевого оборудования реализована своего рода CRC, не следует ли уже позаботиться о случайном переключении битов?


checksum hash crc32 error-detection
person ayurchen    schedule 26.01.2013    source источник
comment
Я думаю, я не понимаю, что означает общий хеш.   -  person lc.    schedule 26.01.2013
comment
Хорошо, удалил генерал, мое плохое.   -  person ayurchen    schedule 26.01.2013

Ответы (2)


arrow_upward
12
arrow_downward

Только вы можете сказать, достаточно ли 1-2 -32 для вашего приложения. Эффективность обнаружения ошибок между CRC- n и n битами хорошей хеш-функции будет очень близка к той же, поэтому выберите тот, который быстрее. Скорее всего, это CRC- n.

Обновление:

Вышеупомянутое «Это скорее всего CRC- n» весьма вероятно. Это маловероятно, если используются очень высокопроизводительные хэш-функции. В частности, CityHash оказывается почти таким же быстрым, как CRC-32, рассчитанный с использованием Аппаратная инструкция Intel crc32! Я протестировал три процедуры CityHash и инструкцию Intel crc32 на файле размером 434 МБ. Версия инструкции crc32 (которая вычисляет CRC-32C) заняла 24 мс процессорного времени. CityHash64 занял 55 мс, CityHash128 60 мс и CityHashCrc128 50 мс. CityHashCrc128 использует ту же аппаратную инструкцию, но не вычисляет CRC.

Чтобы выполнить расчет CRC-32C так быстро, мне пришлось поработать с тремя crc32 инструкциями на трех отдельных буферах, чтобы использовать три блока арифметической логики параллельно в одном ядре, а затем записать внутренний цикл в ассемблер. CityHash чертовски быстр. Если у вас нет инструкции crc32, вам будет сложно вычислить 32-битный CRC так же быстро, как CityHash64 или CityHash128.

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

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

Еще одно обновление четыре года спустя:

Еще быстрее семейство xxhash. Теперь я бы порекомендовал это вместо CRC для некриптографического хеша.

person Mark Adler    schedule 26.01.2013
comment
Что ж, есть некоторые хэш-функции, такие как CityHash или MurMurHash, которые могут обрабатывать несколько байтов за такт для сообщений 1K, поэтому они, вероятно, превзойдут неускоренное вычисление CRC32. И они производят 128-битный вывод для загрузки. Поэтому мне было интересно, есть ли в CRC что-то концептуальное, что делает его контрольной суммой лучше, чем хороший хэш. Но я думаю, вы правы, все дело в количестве битов, поэтому я думаю, что выберу хеш. - person ayurchen; 27.01.2013
comment
Нет, в CRC нет ничего, что могло бы улучшить контрольную сумму, если, возможно, ваш источник шума - небольшое количество битовых переворотов. Я не знаю, гарантированно ли какие-либо хеш-функции обнаруживают все возможные перевороты от 1 до n, как это гарантировано CRC- n. - person Mark Adler; 27.01.2013
comment
Вы правы насчет CityHash. Я был удивлен, увидев, насколько это быстро. - person Mark Adler; 28.01.2013

arrow_upward
0
arrow_downward

Отложив в сторону вопросы «производительности»; вы можете рассмотреть возможность использования одной из функций SHA-2 (скажем, SHA-256).

person Joseph Lee    schedule 28.01.2013
comment
Ух ты. Это действительно не считая проблем с производительностью. SHA-256 занимает в 100 раз больше, чем CRC-32, или в 50 раз дольше, чем CityHash. И без причины, поскольку это приложение не требует криптографического хеша. - person Mark Adler; 28.01.2013
comment
Ну, вообще-то мог бы. Может быть, это не совсем SHA-256, поскольку мне не нужна криптографическая стойкость, но, учитывая, что количество бит в контрольной сумме имеет первостепенное значение, изучение 256-битных хэшей может иметь смысл. Я просто не уверен, что есть еще какие-нибудь, кроме SHA-256, и есть ли они хоть какие-нибудь. Также это не для хеширования коротких строк для хеш-таблицы, это для сообщений контрольной суммы, которая обычно должна превышать 1 КБ. Я предполагаю, что это вопрос сравнительного анализа, чтобы увидеть, сколько накладных расходов это может принести. Я обязательно сохраню это как вариант. - person ayurchen; 29.01.2013
comment
Просто сделал быстрый поиск, и вот вы: 256-битная версия CityHash! Должен быть на порядок быстрее, чем SHA. - person ayurchen; 29.01.2013