Изменился ли файл (самый быстрый алгоритм хеширования)?

Btrfs использует CRC32, для обнаружения случайных изменений типа bit rot этого достаточно. Производительность:

 % sudo btrfs scrub status /home
scrub status for 9dffdcdb-5777-4667-8b85-be5372b38531
	scrub started at Sun Jan 20 20:12:58 2019 and finished after 00:01:28
	total bytes scrubbed: 282.76GiB with 0 errors

Говорят мд5 рвёт црц32 в два раза: https://stackoverflow.com/a/329105/3558278 (смоти на даты, я ничего не утверждаю, возможно это уже не актуально)

CRC32 — это код коррекции. Есть чексуммы, которые быстрее CRC32.

2ТС: https://en.m.wikipedia.org/wiki/List_of_hash_functions#Checksums

Какие алгоритмы быстрее md5?

Банальная сумма.

Вообще, как эту фигню (определение изменился файл или нет) сделать правильно и максимально ускорить?

Делай как rdfind: Сверяй длину файла, первый символ, последний символ и только потом сумма.

Ммммм — годно!

Есть xxHash:

Сверяй длину файла, первый символ, последний символ и только потом сумма.

Так если файлы не поменялись то значит все перечисленные операции будут переменены к каждому файлу. В чем ускорение? Тут зависит что у ТС будет чаще случаться, часто ли будут почти все файлы с изменениями?

Может лучше пересмотреть архитектуру приложения, сделать его резидентом и использовать что-то вроде такого https://www.linuxjournal.com/content/linux-filesystem-events-inotify

часто ли будут почти все файлы с изменениями

Не часто, даже скажем редко, это из ряда вон ситуация. Но отреагировать надо.

inotify

Кроссплатформа. И это не постоянный мониторинг, а разовая операция при запуске приложения, но файлов много.

Всегда использовал для этого murmur, оказывается есть вариант лучше.

Первый символ как правило бессмысленно - у большинства файлов будет одно и тоже начало и меняться будет только тело. Если и сверять, то с некоторым отступом. Ну хоть 17.

Я как-то думал над этим на досуге при больших объёмах файлов (один файл 1-10 Гб, файлов на 1 Тб). Пришел к выводу, что если это не критично и ФС поддерживает время изменения, то можно использовать его. А так если софт управляется юзером, давать возможность отменить/выполнить сканирование вручную.

Если и сверять, то с некоторым отступом. Ну хоть 17.

Можно и с отступом. А для файлов меньше 17байт сохранять два раза последний символ. Согласен.

ммм, а чо тест CRC32 без интринсиков?

Который в smhasher? Вопросы к ним.

Не, два раза последний не катит. Я бы сохранял три: начало, середина, конец. Вне зависимости от размера файла. Для середины pos = floor(size / 2), если файл в два байта то сохранять первый, первый, второй. если один, то первый, первый, первый. Ну и fseek наше всё.

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

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

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

Смотри почему первый символ бессмысленно сверять - если это скажем скрипт PHP то первый символ скорее всего будет <, если это bash - то #, у файлов LO - P и так далее. Первый символ (байт) зависит от типа файла и у одного и того же типа файла почти всегда будет одинаковым. А разным типам у нас принято давать разные расширения, т.е. у файлов с одинаковыми именами первый символ с вероятностью близкой к 99% будет одинаковым. Нет никакого смысла его сверять - это не дает никакой информации.

Однако в моём случае это не приемлемо т.к. на реально не изменившихся файлах всегда будет полная проверка проходить.

Как вот это соотносится с этим:

не сильно критичны коллизии.

?

То что тебе предлагают и есть чексумма. Просто коллизий дофига.

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

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

Но все это может оказать медленным очень если у тебя какой-нибудь PHP и будет работать в разы дольше md5. В это случае не будет ничего лучше чем тупо протестировать все функции хэша встроенный в язык и выбрать самые быстрые. Никто тебе не даст ответа что это будет на твоих файлах. Так как вычисление одной функции на 1Гб это одно, а вычисление 1024 функций на 1024 файлах по 1Мб - это другое. Отношения размера файлов к их количеству важны.

Есть гугловый Highwayhash.

TFSовцы хвалятся, что их SeaHash быстрый.

Какой коррекции? По 32 битам ничего особо не скорректируешь.

А какая задача? Может быть inotify/auditd лучше подходят?

Просто если у тебя 10тб данных на шпинделе, то не важно каким алгоритмом хеши считать.

Таблица со скоростью hash-функций.

Недостоверная информация, корректная и легко проверяемая см https://github.com/rurban/smhasher#summary

Есть гугловый Highwayhash.

Не «гугловый», а сделанный чуваками имеющими отношения к google.

Отдельно стоит сказать об их утверждение что оно «fast and strong».

Без SSE4.2 работает неприемлемо медленно, а «доказательство» стойкости = буквально культ карго (сделали как в SipHash, не важно что из соломы).

Без SSE4.2 работает неприемлемо медленно

Где это ты нашел процессоры без SSE4.2? Уже AVX-512 во всю применяют.

На счёт достоверности не знаю, но одна таблица для 32 бит, а вторая для 64.

Хотя достоверность тоже странная. Вот, например, порядок:

• Spooky32
• xxHash64

$ cat /proc/cpuinfo |grep 'name'
model name	: Intel(R) Core(TM)2 CPU         T7200  @ 2.00GHz

ты не прав, дядя. всего каких то пару лет назад отправил на пенсию свой туалатин 1300, представь себе.

Без SSE4.2 работает неприемлемо медленно

Где это ты нашел процессоры без SSE4.2? Уже AVX-512 во всю применяют.

Полным-полно, RTFM. Но не важно, главное - это не переносимо.

С другой стороны, аналогично c AES-NI. Однако, это вдвое быстрее HighwayHash, а еще переносимо и уровень стойкости понятен (для хорошего эффекта «перемешивания» достаточно 2-3 циклов, пример и пояснения см https://github.com/cmuratori/meow_hash/issues/38).

IMHO: HighwayHash довольно странное поделие. Цитата из https://habr.com/ru/post/339160/

Сравнение с HighwayHash: У меня двоякое отношение к этому неофициальному проекту сотрудников Google.
Во-первых: С одной стороны, хороший код и отличное техническое воплощение. С другой стороны, HighwayHash позиционируется как возможно криптографический стойкий (как минимум равный SipHash). Хотя доказательство «стойкости» сводится к результатам статистических тестов, но без возможности их воспроизвести (как-то я даже позволил себе лишнее).
Во-вторых: HighwayHash действительно быстр только на x86_64 c AVX2 или SSE41. Так не проще ли использовать AES-NI или акселерацию SHA?

Хотя достоверность тоже странная. Вот, например, порядок:

Не понял что странного?

На всякий:

xxHash32 - это 32-битный результат при 32-битных операциях, т.е. данные кушаются по 4 байта.

xxHash64 - это 64-битный результат при 64-битных операциях, т.е. данные кушаются по 8 байт.

На 32-битной платформе xxHash32 будет примерно вдвое быстрее xxHash64, а на 64-битном процессоре будет наоборот.

Ну и так далее. Для развлечения попробуйте make bench для https://github.com/leo-yuriev/t1ha, в том числе с/без добавления -m32 в CFLAGS, или под qemu (там есть готовый таргет).

Spooky32 и xxHash64 в разном порядке в разных таблицах у https://github.com/rurban/smhasher#summary

Для нижней написано, что это на 64-битной машине. Но для верхней не написано на чём изменения происходят. Если на той же, то почему результаты в таблицах не совпадают.

Полным-полно, RTFM. Но не важно, главное - это не переносимо.

Согласен, что на каком-нибудь MIPS оно не будет работать. Но учитывая текущую специфику использования железа, где Intel доминирует, важна ли эта переносимость?

IMHO: HighwayHash довольно странное поделие. Цитата из https://habr.com/ru/post/339160/
[...]

Как и автору поста мне криптостойкость не нужна. Я делаю балансировку на основе хэширования. Мне нужно много мегабитов прокачивать. Со случаями когда нужна именно криптостойкость я не сталкивался.

на большом кол-ве (большИх в том числе) файлов оно работает дико долго.

Может это не алгоритм, а файлы читаются долго? Ваш КО 😜

Согласен, что на каком-нибудь MIPS оно не будет работать. Но учитывая текущую специфику использования железа, где Intel доминирует, важна ли эта переносимость?

Как и автору поста мне криптостойкость не нужна. Я делаю балансировку на основе хэширования. Мне нужно много мегабитов прокачивать. Со случаями когда нужна именно криптостойкость я не сталкивался.

Это понятно, у всех примерно такие требования/взгляды. Но и в этом случае HighwayHash все равно не рациональный выбор.

Взяв t1ha вы получите чуть быстрее, но и переносимо (кратно быстрее в сравнении с HighwayHash на alien-платформах).

А в случае t1ha_aes кратно быстрее и на Intel, но с привязкой к AES-NI, вместо SSE41/AVX.

Отдельно стоит сказать про балансировку - как правило тут хешируются короткие ключи (порции данных). Поэтому t1ha будет просто быстрее, в том числе и с честным подсаливанием (а если использовать методику доказательства стойкости от HighwayHash, то не хуже SipHash).

Проверить просто: git clone https://github.com/leo-yuriev/t1ha && cd t1ha && make bench

Spooky32 и xxHash64 в разном порядке в разных таблицах у https://github.com/rurban/smhasher#summary

Для нижней написано, что это на 64-битной машине. Но для верхней не написано на чём изменения происходят. Если на той же, то почему результаты в таблицах не совпадают.

Пардон, вижу там одну таблицу, плюс ниже перечисление списка фаворитов. Предполагаю Reini опечатался, либо не обновил этот список после каких-то правок или смены компилятора.

файлы читаются долго?

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

у murmur коллизий мало. а вот у вышеописанного - не факт.

на современных интеловых процах есть отдельная инструкция для подсчета crc. Точных цифр не приведу, но из всего что я пробовал это быстрее всего. https://software.intel.com/sites/default/files/m/8/b/8/D9156103.pdf страница 61

Говорят мд5 рвёт црц32 в два раза

Говорят, что кур доят. crc32 на современных CPU поддерживается аппаратно.

у murmur коллизий мало. а вот у вышеописанного - не факт.

Я так понимаю «quality» в таблице это и есть как раз показатель качества распределения.

какой-то он странный. что такое 10? чего десять? попугаев?

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

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

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

Практически на всех Intel'ах доступны инструкции AES-NI и CLMUL (carry-less multiplication), которые позволяют хешировать кратно быстрее и принципиально качественнее.

Как пример https://github.com/lemire/clhash (CLMUL) и t1ha_aes (AES-NI) в https://github.com/leo-yuriev/t1ha.

какой-то он странный. что такое 10? чего десять? попугаев?

Действительно, похоже что какие-то жуткие попугаи.

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

Вот как-раз таки существуют «Критерий строго лавинного эффекта» и «Критерий независимости битов».

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

Поэтому для хорошей хеш-фунции (даже не криптостойной) совсем неважно что хешировать - строки, числа и т.д.

Для статистической проверки качества хеш-функций можно использовать актуальные версии SMHasher от Reini Urban и Yves Orton.

можно свою утильку накатать за 1 минуту :) под свои задачи и свои данные. таки числа - более повтояющиеся «строки». поэтому с ними у хэшей чаще проблемы. и не все хэши качественные.

можно свою утильку накатать за 1 минуту :) под свои задачи и свои данные

Так накатайте, но предлагаю таки глянуть что внутри SMHasher, NIST STS и DIEHARD :)

таки числа - более повтояющиеся «строки». поэтому с ними у хэшей чаще проблемы.

Это заблуждение. В случае чисел просто чуть проще проверить, ибо множество значений намного меньше. Но есть «хорошие» функции которые ломаются на Sparse-тесте в SMHasher.

и не все хэши качественные.

Качественных нет, есть недообследованные :)