Контрольная сумма: CRC или хэш?
Помимо соображений производительности и безопасности, и предположения о хэш-функции с идеальным лавинным эффектом, которую я должен использовать для контрольных суммирующих блоков данных: CRC32 или хеш, усеченный до N байтов? Т.е. у которой будет меньше вероятность пропустить ошибку? В частности:
- CRC32 против 4-байтового хэша
- CRC32 против 8-байтового хэша
- CRC64 против 8-байтового хэша
Блоки данных должны передаваться по сети и многократно храниться на диске. Блоки могут быть размером от 1 КБ до 1 ГБ.
Насколько я понимаю, CRC32 может обнаруживать до 32-битных флипов со 100% надежностью, но после этого его надежность приближается 1-2^(-32) а по некоторым закономерностям гораздо хуже. Идеальная 4-байтовая надежность хеша всегда 1-2^(-32)так что пойди разберись.
8-байтовый хеш должен иметь намного лучшую общую надежность (2^(-64) шанс пропустить ошибку), так что должно быть предпочтительнее, чем CRC32? Что насчет CRC64?
Я предполагаю, что ответ зависит от типа ошибок, которые могут ожидаться в такой операции. Скорее всего, мы увидим редкие 1-битные перевороты или массивные повреждения блоков? Кроме того, учитывая, что большинство устройств хранения и сетевых технологий реализуют какой-то тип CRC, не следует ли уже позаботиться о случайных переворотах?
2 ответа
Только вы можете сказать, достаточно ли 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 необходимо изменить, чтобы обновить промежуточное состояние.
Альтернатива и то, что я сделал для быстрого и грязного тестирования, - это использование версий функций Seed, где я бы использовал CityHash из предыдущего буфера в качестве начального числа для следующего буфера. Проблема в том, что результат зависит от размера буфера. Если вы используете этот подход в буферах CityHash разного размера, вы получите разные значения хеша.
Другое обновление четыре года спустя:
Еще быстрее семейство xxhash. Я бы сейчас рекомендовал использовать CRC для некриптографического хэша.
Оставляя в стороне проблемы "производительности"; Вы можете рассмотреть возможность использования одной из функций SHA-2 (скажем, SHA-256).