Подтвердить что ты не робот

Быстрые хэш-таблицы на основе диска?

У меня есть набор хэшей (первые 64 бита MD5, поэтому они распределены очень случайным образом), и я хочу видеть, есть ли новый хеш в наборе и добавить его в набор.

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

Некоторые идеи, которые я имел до сих пор:

  • Я пробовал просто хранить все это в таблице sqlite, но он становится действительно очень медленным, когда он не может вместить все в память.
  • Фильтры Bloom звучат так, будто у них будет очень высокий коэффициент ошибок. Я не против крошечной частоты ошибок (64-битный хеш дает 1 столкновение по набору элементов 4G уже), но ошибки, такие как 1%, слишком высоки.
  • Сохранять отсортированный список хэшей с пробелами в файле и изменять размер, если у меня недостаточно пробелов. Хаши равномерно распределены, поэтому даже очень простая схема должна работать.

Я пропустил что-то действительно очевидное? Любые подсказки, как реализовать хорошую хэш-таблицу на основе диска?

4b9b3361

ОТВЕТЫ

Ответ 1

Здесь решение, которое я в конечном итоге использовал:

  • Один файл для каждого набора
  • Файл содержит 2 ^ k ведра, каждый 256 байтов или 32 записи из 8 байтов.
  • Пустые записи просто обнулены (000... является допустимым хешем, но меня не волнует вероятность столкновения 2 ^ -64, если все может столкнуться со всем остальным уже по характеру хэширования).
  • Каждый хэш находится в ведре, который догадывается через его первые k бит
  • Если какой-либо ведро переполняется, удваивает размер файла и разбивает каждый ковш
  • Доступ осуществляется через mmap(), not read()/write()

Это просто невероятно быстрее, чем sqlite, хотя это низкоуровневый Perl-код и Perl действительно не предназначены для высокопроизводительных баз данных. Он не будет работать ни с чем менее равномерно распределенным, чем с MD5, поскольку он предполагает, что все будет очень однородным, чтобы упростить реализацию.

Я попробовал сначала с функцией seek()/sysread()/syswrite(), и это было очень медленно, mmap() действительно намного быстрее.

Ответ 2

У меня были некоторые проблемы с изображением вашей конкретной проблемы/необходимости, но мне все же пришлось подумать о Git и о том, как она хранит SHA1-ссылки на диске:

Возьмем шестнадцатеричное строковое представление заданного хэша, скажем, "abfab0da6f4ebc23cb15e04ff500ed54". Нарисуйте два первых символа хэша ( "ab", в нашем случае) и перейдите в каталог. Затем используйте остальные ( "fab0da6f4ebc23cb15e04ff500ed54" ), создайте файл и поместите в него материал.

Таким образом, вы получаете довольно приличную производительность на диске (в зависимости от вашего FS, естественно) с автоматической индексацией. Кроме того, вы получаете прямой доступ к любому известному хешу, просто заклинив разделитель каталога после двух первых символов ( "./ab/fab0da [..]" )

Извините, если я пропустил мяч целиком, но, если повезет, это может дать вам идею.

Ответ 3

Звучит как работа для Berkeley DB.

Ответ 4

Другие дисковые системы хэширования/структуры данных на основе диска включают линейное хеширование и расширяемое хеширование.

Ответ 5

Сначала мне приходят в голову два алгоритма:

  • Используйте b-tree.
  • Разделите цепочку самих хэшей, выполнив что-то вроде использования первых 10 бит вашего хэша для индексации в один из 1024 отдельных файлов, каждый из которых содержит отсортированный список всех хэшей, начиная с этих 10 бит. Это дает вам прыжок с постоянным временем в блок, который должен вписываться в память, и поиск журнала (n) после того, как вы загрузили этот блок. (или вы можете использовать 8 бит для хэша в 256 файлов и т.д.).

Ответ 6

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