Хеш от содержимого объекта в качестве идентификатора объекта: быстрые альтернативы для SHA256 - PullRequest
Новая
       11

Хеш от содержимого объекта в качестве идентификатора объекта: быстрые альтернативы для SHA256

0 голосов
/ 29 октября 2018

Я работаю над дизайном Адресуемого контентом хранилища , поэтому я ищу хэш-функцию для генерации идентификаторов объектов. Каждый объект должен получить короткий идентификатор, основанный на его содержании, таким образом: object_id = hash(object_content).

Необходимые условия:

  1. Хэш-функция должна быть быстрой.
  2. Вероятность столкновения должна быть как можно ниже.
  3. Оптимальная длина идентификатора составляет 32 байт для адресации 256^32 объектов в максимуме (но это требование может быть ослаблено).

Принимая во внимание эти требования, я взял хэш SHA256, но, к сожалению, он недостаточно быстр для моих целей. Самыми быстрыми реализациями SHA256, которые я смог протестировать, были openssl и boringssl: на моем рабочем столе Intel Core I5 6400 это давало около 420 MB/s на ядро. Другие реализации (например, crypto/rsa в Go) еще медленнее. Я хотел бы заменить SHA256 другой хэш-функцией, которая обеспечивает те же гарантии коллизий, что и SHA256, но дает лучшую пропускную способность (не менее 600 MB/s на ядро).

Пожалуйста, поделитесь своим мнением о возможных вариантах решения этой проблемы.

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

1 Ответ

0 голосов
/ 01 ноября 2018

Проверить Cityhash и HighwayHash . Оба имеют 256-битные варианты и намного быстрее, чем SHA256. Cityhash быстрее, но это не криптографический хеш. HighwayHash медленнее (но все же быстрее, чем SHA256), и безопасный хэш.

Все современные некриптографические хеши * на 1009 * намного быстрее, чем SHA256. Если вы хотите использовать 128-битный хеш, у вас будет больше параметров .

Обратите внимание, что вы можете рассмотреть возможность использования 128-битного хэша, поскольку этого может быть достаточно для вашей цели. Например, если у вас есть 10 10 различных объектов, вероятность того, что вы столкнетесь с качественным 128-битным хешем, будет меньше 10 -18 . Проверьте таблицу здесь .

...