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

Question

В настоящее время я играю с 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

Answer 1

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

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

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

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

Answer 2

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

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

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

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

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

Выборка ключей в отсортированном порядке, по-видимому, не повышает производительность.

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

Какие настройки рекомендуются для случая интенсивного чтения?

Что я не знаю, извините, но выможет читать:

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