Создание хранилища значений ключей на диске с параллелизмом в Java

Question

Мне нужно прочитать набор файлов и разбить их на пары ключ-значение, и сохранить их как (ключ, список значений) для этого ключа на диске, во многом как парадигма map-Reduce.Все на одном компьютере, хотя.Я мог бы, например, написать разные списки в разных файлах и назвать файлы ключом.Это кажется очень плохим способом ведения дел.Для начала, если у вас есть миллиард ключей, вы получите миллиард файлов.Очевидно, что это не сработает, и мне понадобится какое-то отображение памяти.Мне также понадобятся разные потоки, выполняющие работу с картой, поэтому, если они будут записывать в этот же буфер, между ними будет какая-то синхронизация.Если у меня есть сопоставление буфера ключ-значение и синхронизация по буферам, то потоки не должны наступать друг на друга, поэтому я думаю, что эта часть должна работать.Вопрос в том, как мне сделать сопоставление значений на диск.Как мне написать буферы, которые соответствуют разным ключам в одном файле?Если бы кто-то мог указать мне правильное направление, это было бы очень ценно.Мои знания в этой области довольно пафосны.Еще раз спасибо.

Answer 1

С практической точки зрения было бы легко сделать это с BerkeleyDB, , как предложил Лирик.

Если вы больше интересуетесь теорией, чем практикой, я бы посоветовал вам подходить к этому как к операции "внешней сортировки". То есть прочитайте как можно больше ввода в память, а затем сортируйте по ключу Запишите отсортированный фрагмент как один файл. Отсортированные файлы могут быть легко объединены в один файл.

Среди других приложений, это подход, используемый Lucene для создания «инвертированных индексов» для поиска текста. «Ключи» - это слова в документах, а «значения» - это список документов, в которых встречается слово. Lucene читает документы и для каждого слова создает запись в документе. Когда память заполнена, она записывает сегмент индекса на диск. Когда на диске много сегментов индекса, они объединяются в один сегмент. Фактически, вы также можете адаптировать индексатор Lucene к вашей задаче.

Работа может быть разделена на несколько потоков. Однако вы должны быть чувствительны к конфликту дисков. Пропуск одновременного чтения и записи большого количества файлов значительно замедлит работу обычного диска. Там могут быть возможности для планирования некоторых мероприятий одновременно. Возможно, вы могли бы прочитать новые данные из одного файла во время записи предыдущего отсортированного фрагмента на диск, особенно если на машине установлено два дисковода. Конечно, использование SSD для временного хранения некоторых из отсортированных сегментов очень помогло бы.

Answer 2

Я думаю, Oracle Berkeley DB может быть как раз для вас:

Berkeley DB предназначен для хранения данных в виде непрозрачного байтаМассивы данных в парах ключ / значение, проиндексированных одним из доступных методов доступа, как показано выше.

Беркли очень устойчив, зрел и быстр, но если вы хотите использовать более легкий подходзатем используйте SQLite .

Другой вариант - использовать Google LevelDB;он написан на C ++, но вокруг него Java-оболочки .LevelDB невероятно быстр и очень легкий!

Не имея никаких подробностей о вашем проекте, я могу только сказать:

• Со всеми этими решениямипары ключ / значение будут храниться в одном и том же файле (при необходимости несколько экземпляров могут быть сохранены в отдельных файлах, но я не понимаю, почему это так).
• BerkeleyDB и LevelDB имеют действительно хорошее кэширование и отображениеВозможности.
• BDB и LDB также допускают сжатие (не уверен, что SQLite тоже).
• В зависимости от распределения ключей (т. е. возможно, если вы используете хорошую функцию хеширования, такую ​​как Google CityHash ), вы можете добиться действительно хорошей локальности данных, чтобы уменьшить количество сканирований таблиц.
• Вы, вероятно, должны написать свой собственный потокобезопасный буфер (ы), и вам следует избегать записи нескольких потоков в BDB / LDB, посколькуэти решения основаны на дисках, и вам обычно не нужны операции многопоточного дискового ввода-вывода.

Критика: - Я не уверен, что вы подразумеваете под "Отображение буфера ключ-значение "... Вы отображаете буфер для каждого ключа?Зачем тебе это?

Answer 3

Хроническая карта должно быть хорошим решением этой проблемы.

Как правило, она очень эффективна как с точки зрения скорости операций, так и с точки зрения потребляемой памяти, т. Е. Она намного быстрее чем BerkeleyDB, предложенный ранее.

Хроническая карта - это сегментированное хранилище, позволяющее параллельную обработку сегментов, т.е.g:

for (int i = 0; i < chronicleMap.segments(); i++) {
  int segmentIndex = i;
  executor.submit(() -> {
    chronicleMap.segmentContext(segmentIndex).forEachSegmentEntry(entry -> {
      // do processing with entry.key() and entry.value(),
      // value() could be a List or some Iterator-like abstraction
    });
  });
}

См. MapSegmentContext Javadocs .

Однако наличие (логически) нескольких значений на ключ не всегда может быть эффективно обработано с помощью ChronicleКарта .Но в вашем случае, если вам нужна только обработка статического набора значений для каждого ключа, а не добавление / удаление значений, это может работать хорошо.

Answer 4

Вы смотрели на использование Hadoop ?