Выбор UUID для первичного ключа таблицы

В базах данных, где в качестве алгоритма хранения первичного ключа используется B-tree, отдается предпочтение целочисленным типам данных. Это связано с рядом причин, включая производительность. Но что, если в качестве ключа нужно использовать UUID/GUID? Насколько сильно это повлияет на производительность? А можно ли сделать так, чтобы это влияние было сведено к минимуму?

Для начала нужно рассмотреть корень проблемы — особенности хранения индекса B-tree на диске. Файл индекса B-tree разбивается на блоки фиксированных размеров - страницы. Размер блока обычно принимается 4Кб (или 8Кб в зависимости от файловой системы). Благодаря этому чтение и запись страницы происходит атомарно, за одно обращение к файловой системе.

Каждая страница идентифицируется уникальным адресом и ассоциирована с некоторым упорядоченным диапазоном ключей. Физически страница представляет собой упорядоченный набор пар "начало диапазона - ссылка на страницу значений". Таким образом, страницы организуются в виде дерева, в котором в направлении от "корня" к "листьям" происходит сужение диапазонов. В итоге листовые страницы дерева в зависимости от реализации хранят либо значения, либо прямые ссылки на них.

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

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

С одной стороны, алгоритм гарантирует, что дерево остаётся сбалансированным и его глубина для N ключей никогда не превысит log(N), что в совокупности обеспечивает быстроту поиска. С другой стороны, при интенсивной записи пропускная способность напрямую зависит от ключа. Если каждая следующая операция добавления будет содержать случайный ключ, то очень много времени будет тратиться на создание страниц, они будут разряженными и ссылаться на небольшое количество значений, следовательно, индекс будет занимать больше места на диске.

Можно сказать, что добавление ключей в индекс B-tree будет максимально эффективным как в плане производительности, так и в плане размера индекса, если добавляемые ключи постоянно возрастают (или убывают). Или, выражаясь математическим языком, генератор ключей должен быть монотонной функцией. Например, если в качестве первичного ключа таблицы выбрано целое число и каждый следующий ключ получается путем инкрементирования предыдущего на единицу.

Получается, если первичным ключом является UUID, то проблемы неизбежны? И да, и нет. Во-первых, многое зависит от размера таблицы, интенсивности операций вставки, соотношения между чтением и записью. Во-вторых, чаще всего под UUID понимается UUIDv4 (или GUID в экосистеме Windows), в основе которого лежит генератор случайных чисел, который, естественно, не является монотонной функцией. Однако есть несколько версий UUID, точней, несколько способов его реализации, каждый из которых не лучше и не хуже другого и ориентирован на свой спектр задач.

Более подробную информацию о версиях и форматах UUID легко можно найти в сети. Наибольший интерес представляют версии UUIDv1, v6 и v7, т.к. они основаны на времени, а время, как известно, растет монотонно. (Версия UUIDv2 не рассматривается, т.к. является сложным и специфичным вариантом v1 и мало где поддерживается.)

Чтобы понять, как именно ведут себя UUID разных версий, представим их значения в виде больших целых чисел и нарисуем график зависимостей: по горизонтали — порядковый номер генерации, по вертикали — целочисленное представление UUID. Ниже приведены графики из 1000 UUID-ов каждой версии, генерация которых шла в течении 3 часов.

Как видно, UUIDv1 какое-то время монотонно растет, после чего происходит падение и цикл повторяется вновь. Продолжительность цикла составляет примерно 7.2 минуты, следовательно, каждые 7.2 минуты будет наблюдаться небольшое снижение производительности при вставке новых ключей (во всяком случае, теоретически). Так происходит из-за того, что в формате UUIDv1 время закодировано с обратным порядком байт — от младшего разряда к старшему. Поскольку младшие разряды меняются быстрей старших, появляется "цикличность", которая и наблюдается на графике.

Итак, мы выяснили, что теоретически UUIDv1, v6 и v7 должны работать лучше "привычного" UUIDv4, который основан на генераторе случайных чисел. Да, UUIDv1 имеет некоторые особенности, но насколько они будут критичны на практике, пока не очень понятно. Также непонятно, насколько эти версии UUID уступают по производительности целым числам.

Чтобы разобраться с этим, я сделал небольшое "домашнее" тестирование, взяв за основу PostgreSQL 14 и таблицу в формате "ключ-значение". В качестве ключа — предопределенная версия UUID, в качестве значения — массив байт фиксированного размера (1Кб). Фиксированная размерность значения выбрана специально, чтобы она не оказывала влияния во время тестирования. Тест состоит из двух этапов:

Показатели, которые собираемся наблюдать:

Код теста можно посмотреть на GitHub.

Интерпретация. Во-первых, UUID по размеру в два раза больше bigserial; во-вторых, случайный характер UUID делает индекс более "разряженным", изначально у него будет много полупустых страниц. Между тем, чем больше будет таблица, тем менее заметна будет разница, т.к. со временем все страницы индекса все равно будут заполняться. Индекс на основе bigserial сразу создает "плотный" индекс с минимальным количеством страниц, но это может негативно сказаться на времени записи (см. далее). Обратите внимание, что индексы на основе UUIDv1 и UUIDv6 также достаточно "плотные".

Интерпретация. Индекс на основе bigserial создает минимум страниц, их количество увеличивается линейно. Случайный характер UUID провоцирует быстрый рост числа страниц, следовательно, при вставке данных будет задействовано больше страниц, чтобы найти нужную для записи, следовательно, больше чтений с диска. Здесь UUIDv1 опять в лидерах и, скорей всего, по причине того, что обеспечивает минимум страниц в индексе (см. предыдущий график).

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

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

Интерпретация. Полагаю причина аналогична предыдущей ситуации. Больше чтений с диска — больше время выборки.

В целом, несмотря на наивность проведенного тестирования, полученные результаты вполне объяснимы, что вселяет уверенность в их правдоподобность. Осталось построить сводную таблицу по показателям. Для оценки показателей используем простейшую схему: 3 балла — за лучший результат, 2 — за средний, 1 — за худший.

По совокупности факторов наилучший результат показал UUIDv1 (неожиданно), а наихудший — UUIDv4 (ожидаемо). Целочисленный идентификатор работает не сильно лучше UUIDv6 и UUIDv7.

В качестве вывода позволю себе дать несколько советов.

P.s. Если вам интересна данная тематика, присоединяйтесь к моей новостной ленте в Telegram или здесь. Буду рад поделиться опытом. ;-)