Самый быстрый постоянный ключ / значение в дБ для ключей фиксированного размера и только вставка / выборка (без удаления / обновления)?

Question

Учитывая следующие требования постоянного хранилища ключей / значений:

• Требуются только выборка, вставка и полная итерация всех значений (для экспорта)
• Нет удаления значений или обновления значений
• Ключи всегда одного размера
• Код, встроенный в хост-приложение

И учитывая этот шаблон использования:

• Выборки случайны
• Вставки и выборки чередуются без предсказуемости
• Ключи являются случайными и вставляются в случайном порядке

Какова наилучшая структура / алгоритм данных на диске с учетом требований?

Может ли пользовательская реализация превысить производительность реализаций на основе LSM (Log Structured Merge) (т.е. leveldb, rocksdb)?

Будет ли высокопроизводительная пользовательская реализация для этих требований также значительно проще в реализации?

Answer 1

Хотя может быть возможно иметь лучшую производительность пользовательской реализации для ваших требований, хорошо настроенная RocksDB должна быть в состоянии превзойти большинство таких пользовательских реализаций в вашем случае. Вот что я хотел бы настроить RocksDB:

Во-первых, поскольку у вас нет обновлений и удалений, лучше всего сжать все данные в большие файлы в RocksDB. Поскольку RocksDB сортирует эти ключи в настраиваемом порядке, наличие больших файлов обеспечивает более высокую скорость чтения, поскольку двоичный поиск по некоторым большим файлам быстрее, чем по нескольким маленьким файлам. Как правило, наличие больших файлов снижает производительность сжатия - процесс реорганизации большой части данных в RocksDB таким образом, что 1. объединяются несколько обновлений, связанных с одним ключом; 2. выполнить удаление, чтобы освободить место на диске; 3. сохранить данные отсортированы. Однако, поскольку у вас нет обновлений и удалений, большие файлы обеспечивают высокую скорость чтения и записи.

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

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

Что касается операции сканирования, поскольку RocksDB выполняет внутреннюю сортировку данных в настраиваемом пользователем порядке, сканирование может быть выполнено очень эффективно с использованием итератора RocksDB.

Более подробную информацию об основах RocksDB можно найти здесь.