Какие алгоритмы хеширования распараллеливаются? Оптимизация хеширования больших файлов на многоядерных процессорах

Какой у вас SSD? Моя реализация MD5 на языке C работает со скоростью 400 МБ / с на одном ядре Intel Core2 (2,4 ГГц, не последний Intel). У вас действительно есть SSD с пропускной способностью 1,6 ГБ / с? Я хочу того же !

Хеширование дерева может применяться к любой хэш-функции. Есть несколько тонкостей, и спецификация Skein пытается с ними справиться, интегрируя некоторые метаданные в саму функцию (это не сильно влияет на производительность), но «древовидный режим» Skein не является «Skein» в том виде, в котором он был представлен SHA-3. Даже если Skein выбран как SHA-3, вывод хэша в древовидном режиме не будет таким же, как вывод «plain Skein».

Надеюсь, что в какой-то момент будет определен стандарт для описания общего хеширования дерева. Прямо сейчас их нет. Тем не менее, некоторые протоколы были определены с поддержкой пользовательского хеширования дерева с хеш-функцией Tiger под названием «TTH» (Tiger Tree Hash) или «THEX» (Tree Hash Exchange Format). Спецификация TTH кажется немного неуловимой; Я нахожу упоминания о черновиках, которые либо переместились, либо исчезли навсегда.

Тем не менее, я немного сомневаюсь в этой концепции. Это отчасти изящно, но обеспечивает повышение производительности только в том случае, если вы можете читать данные быстрее, чем может обрабатывать одно ядро, и при правильной функции и правильной реализации одно ядро ​​может хэшировать довольно много данных в секунду. Для хеширования дерева, распределенного по нескольким ядрам, требуется, чтобы данные отправлялись в соответствующие ядра, а 1,6 ГБ / с - не самая маленькая пропускная способность за всю историю.

SHA-256 и SHA-512 работают не очень быстро.Среди кандидатов SHA-3, предполагая, что процессор x86 в 64-битном режиме, некоторые из них достигают высокой скорости (более 300 МБ / с на моем Intel Core2 Q6600 2,4 ГГц, с одним ядром - вот что я могу получить SHA-1 тоже), например BMW, SHABAL или Skein. С криптографической точки зрения, эти конструкции слишком новы, но MD5 и SHA-1 уже криптографически «сломаны» (довольно эффективно в случае MD5, скорее теоретически для SHA-1), поэтому любой из кандидатов на второй этап SHA-3 все должно быть в порядке.

Когда я ограничиваю себя «провидцем», я предвижу, что процессоры будут продолжать становиться быстрее, чем ОЗУ, до такой степени, что стоимость хеширования будет затмевалась пропускной способностью памяти: у ЦП будет запас тактовых циклов, пока он ждет данные из основной оперативной памяти. В какой-то момент необходимо будет изменить всю модель потоковой передачи (одна большая оперативная память для многих ядер).

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

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

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

Лучшее решение зависит от того, каковы ваши ограничения и куда вы можете инвестировать пространство, время или мощность процессора.