В базах данных в качестве первичных ключей часто используют случайные UUID. Один из известных недостатков случайных UUID заключается в том, что их неупорядоченность (UUID4) может вызывать большое количество дополнительных обращений к страницам кластеризованных индексов (clustered index), потому что строки вставляются в случайные места B-дерева, и его приходится постоянно перебалансировать. В этой статье я попытаюсь помочь вам выработать более интуитивное понимание того, как влияют на производительность все эти дополнительные операции со страницами.
Хотя статья посвящена конкретно SQLite, проблема случайных UUID касается и других баз данных, использующих кластеризованные индексы.
Что такое кластеризованные индексы?
Кластеризованные индексы определяют физический порядок хранения строк в таблице. Из-за этого:
Для каждой таблицы может существовать только один кластеризованный индекс (строки можно физически отсортировать только одним способом).
Кластеризованный индекс — это таблица.
Некластеризованный индекс хранит только индексированные столбцы плюс указатель на сами данные строк, которые находятся в другом месте.
Rowid
У каждой обычной таблицы SQLite есть внутренний 64-битный целочисленный первичный ключ, называющийся rowid. Данные таблицы хранятся в структуре B-дерева, содержащей по одному элементу на каждую строку таблицы и использующей в качестве ключа значение rowid. По сути, это кластеризованный индекс SQLite. Порядок физического хранения строк соответствует порядку rowid.
Без rowid
SQLite также поддерживает таблицы WITHOUT ROWID. У этих таблиц нет внутреннего rowid. Вместо него кластеризованным индексом становится объявляемый вами первичный ключ. Зачем использовать таблицы без rowid? Просто потому что благодаря этому не нужно хранить индекс rowid и индекс первичных ключей, что снижает объём записи. Но при этом для получения самих данных всё равно требуется дополнительный поиск даже в случае, когда в качестве rowid используется первичный ключ (если только индекс не покрывающий).
Примечание: в SQLite таблицы с rowid реализованы в виде B+-деревьев, в которых всё содержимое хранится в листьях, а таблицы WITHOUT ROWID реализованы в виде обычных B-деревьев, где содержимое хранится и в листьях, и в промежуточных узлах.
Отправная точка
Давайте зададим отправную точку производительности с обычным целочисленным первичным ключом rowid. Вставим 10 миллионов строк группами по 1 миллиону.
(d/q writer ["CREATE TABLE IF NOT EXISTS event(id INTEGER PRIMARY KEY, data BLOB)"]) (dotimes [_ 10] (time (d/with-write-tx [db writer] (dotimes [_ 1000000] (d/q db ["INSERT INTO event (data) values (?)" data])))))
Результаты:
Общее количество строк | Время в миллисекундах |
|---|---|
1000000 | 838 |
2000000 | 762 |
3000000 | 819 |
4000000 | 713 |
5000000 | 721 |
6000000 | 757 |
7000000 | 692 |
8000000 | 702 |
9000000 | 696 |
10000000 | 715 |
Примерно миллион вставок в секунду.
UUID4 без ROWID
А теперь попробуем UUID4.
(d/q writer ["CREATE TABLE IF NOT EXISTS event(id BLOB PRIMARY KEY, data BLOB) WITHOUT ROWID"]) (dotimes [_ 10] (time (d/with-write-tx [db writer] (dotimes [_ 1000000] (d/q db ["INSERT INTO event (id, data) values (?, ?)" (random-uuid4-bytes) data])))))
Результаты:
Общее количество строк | Время в миллисекундах |
|---|---|
1000000 | 2649 |
2000000 | 5644 |
3000000 | 7137 |
4000000 | 8352 |
5000000 | 9359 |
6000000 | 9817 |
7000000 | 10490 |
8000000 | 11130 |
9000000 | 11668 |
10000000 | 12586 |
О, нет! Что произошло, почему вставки стали медленнее в 14-16 раз?!
Профилирование
Разница получилась большой, но давайте не будем гадать о причинах, ведь можно выполнить профилирование.
Ниже показан нормализованный diffgraph. Он сравнивает два снэпшота профилирования (в данном случае INTEGER и UUID4) и показывает различия в структуре flame-графика. В отличие от обычного diffgraph, показывающего абсолютные изменения, нормализованный вид согласует общее количество сэмплов между двумя сравниваемыми профилями. Благодаря этому мы можем увидеть относительные различия в виде процентов. Это важно, потому что наши профили будут выполняться в течение разного времени.
Цвет обозначает направление изменения: синий означает, что в этой функции потрачено меньше времени во втором профиле (UUID4), чем в первом (INTEGER); красный означает, что больше времени потрачено во втором профиле. Яркость цвета обозначает относительное изменение в количестве сэмплов для самого кадра (собственная дельта времени).
Из diffgraph видно, то мы тратим гораздо больше времени на балансировку дерева, чтение и запись. Это вызвано тем, что из-за неупорядоченности UUID4 они упорядочиваются случайно, что заставляет SQLite постоянно перебалансировать B-дерево.
UUID7 без ROWID
Теоретически, мы можем исправить ситуацию при помощи упорядоченного по времени UUID7. Давайте посмотрим, насколько всё улучшится.
(d/q writer ["CREATE TABLE IF NOT EXISTS event(id BLOB PRIMARY KEY, data BLOB) WITHOUT ROWID"]) (dotimes [_ 10] (time (d/with-write-tx [db writer] (dotimes [_ 1000000] (d/q db ["INSERT INTO event (id, data) values (?, ?)" (random-uuid7-bytes) data])))))
Результаты:
Общее количество строк | Время в миллисекундах |
|---|---|
1000000 | 1372 |
2000000 | 1280 |
3000000 | 1365 |
4000000 | 1250 |
5000000 | 1256 |
6000000 | 1270 |
7000000 | 1246 |
8000000 | 1257 |
9000000 | 1245 |
10000000 | 1258 |
Показатели стали более приемлемыми, но всё равно результаты хуже, чем у отправной точки. Первичные ключи блоба UUID занимают 16 байт, а целочисленные первичные ключи — 8 байт.
UUID4 с ROWID
А теперь попробуем UUID4 с ROWID. Это значит, что кластеризованным индексом будет скрытый rowid. Плюс этого в том, что rowid последователен. Недостаток в том, что теперь у таблицы будет два индекса, поэтому объём записываемых данных увеличится.
(d/q writer ["CREATE TABLE IF NOT EXISTS event(id BLOB PRIMARY KEY, data BLOB)"]) (dotimes [_ 10] (time (d/with-write-tx [db writer] (dotimes [_ 1000000] (d/q db ["INSERT INTO event (id, data) values (?, ?)" (random-uuid4-bytes) data])))))
Результаты:
Общее количество строк | Время в миллисекундах |
|---|---|
1000000 | 2003 |
2000000 | 2324 |
3000000 | 3285 |
4000000 | 4399 |
5000000 | 5194 |
6000000 | 5659 |
7000000 | 6215 |
8000000 | 6467 |
9000000 | 6924 |
10000000 | 7119 |
Показатели не такие хорошие, как у UUID7 без ROWID; частично это вызвано тем, что мы всё равно создаём индекс со случайными вставками (даже несмотря на то, что это не кластеризованный индекс).
Заключение
Надеюсь, этим постом мне удалось продемонстрировать недостатки первичных ключей SQLite в UUID и способы работы с ними.
Полный код бенчмарков выложен на Github.
Повышение производительности SQLite предварительной сортировкой
Выше мы показали, что UUID4 может сильно влиять на скорость вставок и продемонстрировали, как может помочь UUID7. Но что насчёт других данных, которые могут содержать случайность? В этом случае мы не можем использовать UUID7 для решения наших проблем.
Случайные данные
Мы будем использовать 160-битные (20 байт) случайные значения, сгенерированные SecureRandom, аналогичные тем, которые описывались в статье Нила Мэддена. Почему? Потому что для таких вещей, как токены сессий, вероятно, не стоит использовать UUID7 (они могут приводить к утечкам информации, не обладать достаточной энтропией для вашего сценария использования и так далее). Кроме того, такие значения могут представлять любые данные со случайным первичным ключом (или неупорядоченные более специфичным образом).
Вот код для их генерации:
(defn random-unguessable-uid [] (let [buffer (byte-array 20)] (.nextBytes secure-random buffer)))
Давайте посмотрим на производительность.
(d/q writer ["CREATE TABLE IF NOT EXISTS event(id BLOB PRIMARY KEY, data BLOB) WITHOUT ROWID"]) (dotimes [_ 10] (time (d/with-write-tx [db writer] (dotimes [_ 1000000] (d/q db ["INSERT INTO event (id, data) values (?, ?)" (random-unguessable-id) data])))))
Результаты:
Общее количество строк | Время в миллисекундах |
|---|---|
1000000 | 2478 |
2000000 | 4927 |
3000000 | 6262 |
4000000 | 7195 |
5000000 | 8257 |
6000000 | 8704 |
7000000 | 9244 |
8000000 | 9771 |
9000000 | 10387 |
10000000 | 11103 |
Примерно сотня тысяч вставок в секунду. Всё медленно, как и с UUID4.
Предварительная сортировка
Определяющая характеристика B+-дерева заключается в его упорядоченности. Последовательные операции записи происходят быстро. Случайные данные противоречат этому, вызывая разделения страниц и перебалансировку деревьев.
Но мы ведь уже группируем данные. Что, если сортировать их перед вставкой?
Во-первых, нам понадобится быстрый способ сравнения наших случайных id. Они имеют размер 20 байт, поэтому не хочется выполнять итерации по ним, а значит, просто возьмём первые 8 байт и преобразуем их в long. Вероятно, для обеспечения достаточно хорошей сортировки нам не нужно сравнивать весь байтовый массив. Важно здесь то, что для согласованности с SQLite это сравнение беззнаковое.
При сравнении двух значений BLOB результат определяется при помощи memcmp().
Примечание: вероятно, это не самый быстрый способ сортировки случайных данных. Я писал пост без подключения к Интернету (он слишком отвлекает), поиск в наши дни тоже ужасен, поэтому в основном я работаю со старой доброй офлайн-документацией и использую нечёткий поиск текста при помощи dash (аналог zeal из linux). Если вы знаете более быстрый или оптимальный способ сортировки байтовых массивов на Java/Clojure, то напишите мне!
(defn bytes->long [^bytes bytes] (-> (ByteBuffer/wrap bytes 0 8) (ByteBuffer/.getLong 0))) (defn byte-compare "Compares the first 8 most significant bytes of a byte array. Big Endian (matches SQLites blob sort)." [a b] (Long/compareUnsigned (bytes->long a) (bytes->long b)))
Давайте взглянем на производительность:
(d/q writer ["CREATE TABLE IF NOT EXISTS event(id BLOB PRIMARY KEY, data BLOB) WITHOUT ROWID"]) (dotimes [_ 10] (time (d/with-write-tx [db writer] (->> (repeatedly 1000000 random-unguessable-id) (sort byte-compare) (run! (fn [id] (d/q db ["INSERT INTO event (it, data) values (?, ?)" id data])))))))
Результаты:
Общее количество строк | Время в миллисекундах |
|---|---|
1000000 | 1987 |
2000000 | 2251 |
3000000 | 2296 |
4000000 | 2614 |
5000000 | 2687 |
6000000 | 3244 |
7000000 | 3118 |
8000000 | 3311 |
9000000 | 3485 |
10000000 | 3835 |
Интересно! Несмотря на оверхед, сортировка группы данных повышает производительность примерно в 2-3 раза.
Заключение
Надеюсь, этот пост показал, что группирование при работе с неупорядоченными данными позволяет использовать полезные оптимизации наподобие предварительной сортировки.
Полный код бенчмарков доступен на Github.
