Java: быстрый дисковый хэш-набор

Question

Мне нужно хранить большой хэш-набор, способный содержать до 200 миллионов 40-битных значений. Было бы приемлемо сохранить его как 200 миллионов 64-битное значение (несмотря на потери 200 миллионов * 16 бит).

Требования:

• крошечный объем памяти (дисковое пространство не проблема, память есть)

• быстрые contains(long l) и add(long l) методы (намного быстрее, чем SQL)

• встроенный

• бесплатно и без неприятного лицензирования (без Berkeley DB). LGPL штраф.

• нет ложных срабатываний и ложных отрицательных, поэтому такие вещи, как дисковые фильтры Блума, не то, что мне нужно

SQL - это , а не , что мне нужно здесь.

Потому что я действительно думаю, что я больше чего-то хочу быстро , как это (обратите внимание, что решение намного быстрее, чем решение SQL):

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

Есть ли у Google такой API Java?

Будет ли работать быстрая реализация пары ключ / значение на диске, в которой я бы использовал только «ключ»?

Или что-то еще?

Я бы лучше не изобретал weel.

Answer 1

Попробуйте sg-cdb (странный порт gizmo cdb djb), а затем поменяйте файл RandomAccessFile на BufferedRandomAccessFile (есть хороший пример в коде jai-imageio).

Я получаю умопомрачительное сочинение. Через крышу (потому что все это буферизовано, затем совершено одним махом). Однако производительность чтения для буферизованного RAF не изменилась.

Я мог бы потратить время на сравнение с массовым импортом H2, может быть сравним, хотя и не уверен.

База данных проста: ключ => значение. Поиск поддерживается только на ключ. В моем случае это ключи (случайные числа в кодировке base32 + уникальные int в кодировке base32), так что местность не особо помогает. Значения представляют собой массивы из 120 случайных байтов.

нагрузок (вставка sql)

h2, с кешем 131 МБ (включая сброс, не запуск):

4 мая 2011 г. 23:45:10 test.TestH2Simple main : добавленные вставки добавлены в: 101625 мс

размер базы данных: Около 140 МБ

размер партии: 2000 : выполненные вставки добавлено в: 116875 мс

размер партии: 10000 : вставлено выполнено добавлено: 70234 мс

сравнить с портом sg-cdb (странная штуковина) cdb:

с RandomAccessFile: вставка без сброса: 21688 мс, сбрасывание: 30359 мс, всего: 52047 мс размер файла на диске: 66,1 МБ (69 316 632 байта)

с BufferedRandomAccessFile: около 6,5 секунд

конечно, это не совсем справедливое сравнение, поскольку H2 непрерывно сбрасывает данные во время вставки, тогда как sg-cdb - нет. Это следует учитывать при выполнении сравнения. Вероятно, было бы справедливо сравнить вставку sg-cdb с массовой вставкой H2

читает (sql select)

SG-CDB

: поиск: 490000 закончено: 1304544550439 занято: 17547 мс, счетчик: 0

H2

: выбор выполняется за: 19579 мс

Относительно файлов, отображаемых в память: кажется, они не то, что вы ищете. Отличная производительность при работе с файлами MMap - это когда вы отображаете в памяти около 100 МБ или более (мой опыт).

Answer 2

Если вы можете позволить себе 128 ГБ диска, вы можете хранить один бит на 40-битное значение. Затем вы можете использовать файл произвольного доступа, чтобы проверить установленный бит или изменить его. Вам не нужно будет вставлять какие-либо значения или поддерживать индекс.

Answer 3

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

Большинство баз данных - реляционных или нет - реализуют свои индексы в виде B-дерева, поэтому вы говорите об эквиваленте хранения индекса без других данных, прикрепленных к нему.

У вас будет несколько процессов, одновременно обновляющих это хранилище данных?