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

Question

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

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

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

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

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

Answer 1

Вот решение, которое я в итоге использовал:

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

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

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

Answer 2

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

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

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

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

Answer 3

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

Answer 4

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

Answer 5

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

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

Answer 6

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