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

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

Требования:

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

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

  • встроенный

  • бесплатно и без неприятных лицензий (без Berkeley DB). ЛГПЛ в порядке.

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

SQL — это не то, что мне нужно.

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

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

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

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

Или что-то другое?

Я бы предпочел не изобретать велосипед.


java hashset disk-based
person cocotwo    schedule 27.02.2010    source источник
comment
200 миллионов — это около 28 бит.   -  person Thorbjørn Ravn Andersen    schedule 27.02.2010
comment
@Thorbjorn: я говорю о хранении 200 миллионов значений, каждое из которых составляет 40 бит. Я никогда не говорил о хранении значений, которые могут содержать значение до 200 миллионов :)   -  person cocotwo    schedule 27.02.2010
comment
Из любопытства, вы пробовали это с SQLite и т. Д.? Я не видел никаких доказательств в вопросе, который вы связали с тем, что ОП отключил ведение журнала или даже создал индексы...   -  person Steven Huwig    schedule 27.02.2010
comment
@Steven Huwig: нет, и я указал, что SQL был не тем, чем я был после... Когда я говорил о чем-то быстром, я больше имел в виду ответы, подобные тому, который дал Питер Лоури :) Вы действительно думаете что в ответе, связанном с затратами времени на настройку SQLite, он будет близок к принятому ответу, в котором конкретно говорится, что он работает по кругу SQL? Мы не заботимся ни о реляционных свойствах, ни о гарантиях ACID и т. д. SQL для такой простой задачи — это огромное раздувание. Другими словами, золотой молоток.   -  person cocotwo    schedule 27.02.2010
comment
Запуск кругов (фактическая фраза в посте невероятно быстрее) вряд ли является количественной характеристикой, и методология настройки, предпринятая с SQLite, не описана в посте должным образом. Мой вопрос остается: вы уже реализовали слишком медленное решение, если да, то какое это решение и насколько оно должно быть быстрее? Преждевременная оптимизация — корень всех зол.   -  person Steven Huwig    schedule 27.02.2010
comment
@Steven Huwig: Мы занимаемся высокопроизводительными вычислениями с использованием Java (и Java на самом деле хороша в этом). Название игры — оптимизация. Я задал очень конкретный, не слишком нубский вопрос и конкретно сказал, что SQL — это не то, что мне нужно. Мне не нужны ответы типа SQL и XML. Мне нужны ответы, подобные тому, что дал Питер Лоури.   -  person cocotwo    schedule 02.03.2010
comment
Вы можете исключить SQL по неправильным причинам, использование любой из встроенных баз данных (которые имеют интерфейс sql) - не самая плохая идея. Особенно, если вам нужна некоторая защита непротиворечивости.   -  person eckes    schedule 27.05.2014

Ответы (3)


arrow_upward
2
arrow_downward

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

person Peter Lawrey    schedule 27.02.2010
comment
@Peter Lawrey: интересно... Интересно, что до этого у меня был еще один вопрос, о чем-то другом, где я спросил, какой самый быстрый способ в Java добиться случайного поиска в больших файлах :) К сожалению, в моем случае это невозможно: это необходимо установить на несколько компьютеров. Несколько гигабайт — это нормально, но 128 — это слишком много :( Мне нравится подход, в котором говорится... - person cocotwo; 27.02.2010
comment
Вы также можете использовать фильтр Блума, который примерно занимает 6 бит для 1% ложных срабатываний, чтобы определить, присутствует ли ключ. ЕСЛИ это операция, которую вы ищете. Если данные статические, также возможно дерево с большим разветвлением. - person eckes; 27.05.2014

arrow_upward
2
arrow_downward

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

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

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

База данных проста: ключ => значение. Поиск поддерживается только по ключу. В моем случае ключи (случайные целые числа в кодировке base32 + уникальные целые числа в кодировке 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 315 632 байта)

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

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

читает (sql выбирает)

sg-cdb

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

H2

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

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

person javatothebone    schedule 04.05.2011

arrow_upward
0
arrow_downward

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

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

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

person Steven Huwig    schedule 02.03.2010