Инструменты разработчика · Генератор UUID
Случайные UUID первичные ключи и фрагментация B-дерева: что происходит на самом деле
· Почему это важно
uuid криптография API-интерфейс браузера
Случайные ключи v4 вставляются в случайные страницы индекса, и за это платят кластерные индексы. В этом посте объясняется механизм, стоимость хранения текста по сравнению с двоичным кодом, а также то, как упорядоченные по времени UUID меняют картину.
Вставки замедляются по мере роста таблицы — симптом, который заставляет администраторов баз данных задуматься о выборе ключа.
Вставка строки со случайным UUID в качестве первичного ключа в базе данных с кластерным индексом приводит к тому, что база данных вставляет новую строку в случайное место в структуре B-дерева. Последовательные ключи добавляются к самой правой конечной странице, сохраняя все вставки в небольшой резидентной области кэша. Случайные ключи разбрасывают вставки по всему индексу, заставляя базу данных просматривать и изменять страницы, расположенные далеко друг от друга в физическом хранилище. По мере роста таблицы и углубления дерева каждая вставка затрагивает больше страниц и вызывает больше операций I/O. Операция, которая казалась дешевой при тысяче строк, становится дорогой при миллионе. Это не теоретическая проблема; это проявляется в измеримом снижении пропускной способности вставки.
Как заполняется кластеризованное B-дерево — последовательные ключи добавляются к последней странице; случайные клавиши касаются страниц по всему индексу
Этот механизм имеет фундаментальное значение для работы B-деревьев, поскольку они поддерживают отсортированный порядок ключей на конечных страницах. Когда вы вставляете строку с ключом 10,001 в таблицу, в которой уже сохранены ключи от 1 до 10,000, база данных знает, где находится эта строка: в конце, на существующей крайней правой странице, если есть место, или на новой странице, добавленной справа. Когда вы вставляете строку со случайным UUID, например 7524fae2-7dec-11d0-a765-00a0c91e6bf6, в ту же таблицу, база данных должна перемещаться по дереву, чтобы найти конечную страницу, содержащую ключи в этом диапазоне UUID, найти точную позицию на этой странице и вставить строку. Если эта страница заполнена, она разделяется, перемещая половину своего содержимого на новую страницу и обновляя родительский узел.
Разделение страниц и нагрузка на кэш — почему случайная вставка стоит дороже I/O и почему эффект растет с размером таблицы
Случайные ключи создают наихудший шаблон вставки, поскольку каждая вставка попадает в случайную позицию в дереве, а не добавляется на самую правую страницу. База данных должна найти правильную страницу, что обычно требует нескольких чтений страниц — по одной на каждый уровень дерева. Затем он должен изменить эту страницу, что может вызвать разделение, распространяющееся вверх по дереву. Изменяется больше страниц, происходит больше операций записи, а пул буферов памяти заполняется страницами из разных областей дерева, а не остается сосредоточенным на активной точке вставки. Промахи в кэше увеличиваются, и I/O становится узким местом, при этом скорость вставки стабилизируется по мере увеличения масштаба таблицы.
Текстовый или двоичный — строки из 36 символов по сравнению с собственными столбцами uuid длиной 16 байт или двоичными (16) и влияние на размер индекса.
Стоимость не одинакова для разных СУБД, поскольку разные системы по-разному оптимизируют управление страницами. Базы данных с агрессивным сжатием, небольшими размерами страниц или операциями в памяти могут демонстрировать меньшую разницу в производительности между последовательными и случайными ключами. Базы данных с большими страницами, механическими дисками или строгими ограничениями памяти будут резко ухудшаться. Проблема наблюдаема и измерима: измерьте скорость вставки в 1,000 строках, 100,000 строках и 1,000,000 строках. Если скорость в секунду резко падает в больших масштабах, вы испытываете штраф за случайную вставку с вашей конкретной конфигурацией оборудования и базы данных.
Альтернативы, упорядоченные по времени — как UUIDv7 и ULID сохраняют уникальность при вставке в конец индекса
UUID в виде строк содержат 36 символов в текстовой форме или 16 bytes в виде двоичного типа UUID в зависимости от выбранного формата хранения. Строка символов 36 в столбце UTF-8 или ASCII равна 36 bytes по сравнению со 8 bytes для 64-битного целого числа. Индекс столбца string-UUID в три раза больше, чем индекс целочисленного столбца, при условии, что методы сжатия не применяются. Большие индексы означают, что меньше индексных страниц помещается в пул буферов, а это означает меньшее количество обращений к кешу при обходе дерева. Индекс меньшего размера, соответствующий RAM, работает лучше, чем большой индекс, который необходимо считывать с диска при каждом запросе, независимо от порядка вставки или шаблонов рабочей нагрузки.
Рабочий пример — та же рабочая нагрузка по вставке, описанная для таблицы случайных ключей и таблиц с упорядоченными по времени ключами, качественно, без придуманных тестов.
Разница в хранении имеет большое значение как для первичных, так и для вторичных индексов, поскольку каждый вторичный индекс, включающий первичный ключ, должен хранить полное 36-символьное UUID или 16-байтовое двоичное значение UUID. Это делает вторичные индексы значительно больше, чем индексы, использующие целочисленный ключ для поиска по первичному ключу. Репликация, резервное копирование и наборы результатов запросов растут пропорционально увеличению размера индекса. Генератор ToolAcre UUID создает двоично-совместимые значения; хранение их в двоичном (16) или GUID типах в зависимости от базы данных экономит место по сравнению с varchar(36) и повышает эффективность кэша по всем направлениям. Такая оптимизация хранилища имеет решающее значение для крупномасштабных систем.
Чего это не касается — таблицы и базы данных с кучей, где первичный ключ не кластеризован, где эффект меньше.
Обычной оптимизацией является внутреннее сохранение UUID в двоичном виде и отображение его в виде строки только тогда, когда это необходимо для API или пользовательских интерфейсов. Операции индекса и соединения работают в компактной двоичной форме; ответ API или код приложения преобразуются в строковое представление. Некоторые базы данных предлагают встроенные типы GUID или UUID, которые автоматически выполняют это преобразование. Другие требуют явных операций приведения. Разница в производительности между столбцами 36 байта и 16 байта реальна: таблица с миллионом строк и ключом столбца 36 байт и 16 байт UUID отличается на 20 MB для каждого уровня индекса, что может быть разницей между индексом, помещающимся в кэш L3, и требованием выборка памяти.
Вывод: узнайте свой индекс, прежде чем выбирать версию — генератор ToolAcre создает случайные UUID; используйте этот пост, чтобы решить, подходит ли это вашему механизму хранения
Компромисс между производительностью вставки, размером индекса и характеристиками запроса требует архитектурных решений, основанных на шаблонах рабочей нагрузки. Последовательный строковый ключ может быть быстро вставлен, если строки возрастают, например, строки на основе временных меток, но он будет занимать то же пространство, что и случайные UUID, и будет терять временную информацию. Случайный UUID семантически чище и не имеет компонента временной метки, который мог бы утечь, но медленнее вставляется в кластерный индекс и в целом занимает больше места в хранилище. Альтернативы с упорядочением по времени, такие как UUIDv7, сочетают в себе преимущества, сохраняя локальность вставки и избегая при этом утечек временных меток в случайных идентификаторах версии 4.