Почему Get и MultiGet работают значительно медленнее для больших наборов ключей по сравнению с использованием Iterator?

В настоящее время я играю с RocksDB (C++), и мне было интересно узнать о некоторых показателях производительности, с которыми я столкнулся.

В целях тестирования ключи моей базы данных — это пути к файлам, а значения — это имена файлов. В моей базе данных около 2 миллионов записей. Я запускаю RocksDB локально на MacBook Pro 2016 (SSD).

В моем случае преобладают чтения. Полное сканирование ключей довольно распространено, как и сканирование ключей, включающее «значительное» количество ключей. (50%+)

Меня интересуют следующие наблюдения:

<сильный>1. Iterator намного быстрее, чем вызов Get при выполнении полного сканирования ключа.

Когда я хочу просмотреть все ключи в базе данных, я вижу улучшение производительности в 4-8 раз при использовании Iterator вместо вызова Get для каждого ключа. Использование MultiGet не имеет значения.

В случае вызова Get примерно 2M раз ключи были предварительно загружены в вектор и отсортированы лексикографически. Почему повторный вызов Get намного медленнее, чем использование Iterator? Есть ли способ сократить разрыв в производительности между двумя API?

<сильный>2. При извлечении примерно половины ключей производительность между использованием Iterator и Get становится незначительной.

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

Есть ли какое-то «волшебное» соотношение, при котором это становится верным для большинства баз данных? Например, если мне нужно просканировать более 25% ключей, то вызов Get будет быстрее, но если это 75% ключей, то вызов Iterator будет быстрее. Но эти цифры просто «составлены» в результате грубого тестирования.

<сильный>3. Получение ключей в отсортированном порядке не повышает производительность.

Если я предварительно отсортирую ключи, которые хочу получить, в том же порядке, в котором их вернет Iterator, это, по-видимому, не ускорит вызов Get несколько раз. Почему это? В документации упоминается, что перед пакетной вставкой рекомендуется сортировать ключи. Разве Get не выигрывает от того же упреждающего кэширования, что и Iterator?

<сильный>4. Какие настройки рекомендуются для случаев с большим объемом чтения?

Наконец, есть ли какие-либо специальные настройки, рекомендуемые для случая использования с интенсивным чтением, который может включать сканирование значительного количества ключей одновременно?

macOS 10.14.3, MacBook Pro 2016 SSD, RocksDB 5.18.3, Xcode 10.1


c++ rocksdb
person kennyc    schedule 26.03.2019    source источник
comment
Какие параметры компилятора используются для сборки кода? Вы планируете оптимизированную сборку?   -  person PaulMcKenzie    schedule 26.03.2019
comment
Я статически связываюсь с RocksDB, установленным Brew. В Xcode я выполняю сборку «Release». В основном я измеряю простой цикл for, который либо использует Iterator, либо делает несколько вызовов Get. Значения в обоих случаях считываются в вектор только для того, чтобы предотвратить какое-либо неактивное поведение. Каждый цикл выполняется несколько раз подряд для учета любого кэширования диска. Для меня это не микро-бенчмаркинг, а скорее грубый бенчмаркинг, и я вижу разницу более чем в 100% между двумя API, отсюда и запрос.   -  person kennyc    schedule 26.03.2019
comment
Я должен добавить, что режим «Выпуск» в Xcode равен -Os.   -  person kennyc    schedule 26.03.2019

Ответы (2)


arrow_upward
2
arrow_downward

RocksDB внутренне представляет свои данные в виде логарифмически структурированного дерева слияния, которое имеет несколько отсортированных слои по умолчанию (это можно изменить с помощью plugins/config). Интуиция из первого ответа Павла верна, за исключением того, что нет классического указателя; данные фактически сортируются на диске с указателями на следующие файлы. Операция поиска имеет в среднем логарифмическую сложность, но продвижение итератора в отсортированном диапазоне занимает постоянное время. Таким образом, для плотных последовательных чтений итерация выполняется намного быстрее.

Точка, в которой затраты уравновешиваются, определяется не только количеством ключей, которые вы читаете, но и размером базы данных. По мере роста базы данных поиск становится медленнее, а Next() остается постоянным. Самые последние вставки, вероятно, будут считаны очень быстро, поскольку они могут все еще находиться в памяти (memtables).

Сортировка ключей на самом деле просто улучшает скорость попадания в кеш. В зависимости от вашего диска разница может быть очень небольшой, например, если у вас есть твердотельный накопитель NVMe, разница во времени доступа уже не такая значительная, как это было, когда это была ОЗУ по сравнению с жестким диском. Если вам нужно выполнить несколько операций над одним и тем же или даже разными наборами ключей, выполняя их по порядку ключей (f (a-c) g (a-c) f (d-g)...), а не последовательно, это должно улучшить вашу производительность, поскольку вы будете иметь больше кэш-попаданий, а также извлекать выгоду из блочного кеша RocksDB.

Руководство по настройке является хорошей отправной точкой, особенно видео о решениях для баз данных, но если RocksDB слишком медленная, поэтому вы также можете использовать БД, основанную на другом алгоритме хранения. LSM, как правило, лучше подходит для рабочих нагрузок, требующих интенсивной записи, и, хотя RocksDB позволяет очень хорошо контролировать чтение, запись и увеличение пространства, решение на основе b-дерева или ISAM может быть намного быстрее для чтения диапазона/повторного чтения.

person midor    schedule 30.03.2019

arrow_upward
1
arrow_downward

Я ничего не знаю о RocksDB как таковой, но я могу ответить на многие вопросы из первых принципов.

Iterator значительно быстрее, чем вызов Get при выполнении полного сканирования ключей.

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

При извлечении примерно половины ключей производительность между использованием Iterator и Get становится незначительной.

Значит, вы пропускаете записи, вызывая iterator->Next () несколько раз? Если это так, то наступит момент, когда будет дешевле вызывать Get для каждого ключа, да. Когда именно это произойдет, будет зависеть от количества записей в индексе (поскольку это определяет количество уровней в дереве).

Получение ключей в отсортированном порядке не улучшает производительность.

Нет, я бы не ожидал. Get (предположительно) не имеет гражданства.

Какие настройки рекомендуются для варианта использования с большим объемом чтения?

Этого я не знаю, извините, но вы могли прочитать:

https://github.com/facebook/rocksdb/wiki/RocksDB-Tuning-Guide

person Paul Sanders    schedule 26.03.2019
comment
+1 Спасибо за понимание, Пол. Безгражданство Get, вероятно, является самым большим различием между ними, что имеет смысл, чем больше я занимался этим. - person kennyc; 27.03.2019