Эффективная генерация сортируемых GUID для первичных ключей БД на клиенте

Использовать Guid.NewGuid() в качестве первичного ключа в базе данных — плохая с точки зрения производительности идея. Это связано с тем, что в SQL Server, MySQL и некоторых других БД для первичных ключей создаются кластерные индексы, которые определяют, как строки будут храниться на диске. GUID — это по сути случайное значение, поэтому новая строка может попасть в начало, середину или конец таблицы. Серверу БД в этом случае придётся перемещать другие строки, что приведёт к фрагментации данных, а их извлечение может занять больше времени, если вам нужно извлечь несколько добавленных последовательно записей (например, когда вы добавляете набор связанных сущностей, которые потом будут извлекаться вместе — БД понадобится прочитать данные из разрозненных страниц вместо последовательного чтения набора данных).

Поэтому, чаще всего, лучше пользоваться сгенерированными БД первичными ключами. В SQL Server, например, есть функция NEWSEQUENTIALID(), которая генерирует последовательные GUIDы. Зачем может понадобиться генерировать ключи именно на клиенте и как это правильно сделать?

Проблема

Для создания первичных ключей сущности большинство людей прибегают к одному из следующих подходов:

• Использование в качестве первичного ключа int и генерация таких ключей базой данных при вставке новой строки.

• Использование GUID и опции генерации на уровне БД.

• Самостоятельная генерация GUID в своём приложении и вставка строки с этим идентификатором.

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

Генерируемый БД Integer в качестве идентификатора

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

Это упрощает работу с тестовыми данными и поддержку, когда идентификаторы используюстя в URL-адресах: можно запомнить ID нужной сущности, быстро получить её в коде или по адресу, вбив нужный идентификатор:

GET https://localhost/api/book/1
GET https://localhost/api/book/2
GET https://localhost/api/book/2/pages/112

Какие недостатки у таких ключей?

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

Во-втроых, это усложняет код INSERT, поскольку вы должны убедиться, что возвращаете сгенерированные идентификаторы. EntityFramework под капотом назначает ID сущностям после вставки, но в случае с Dapper вам придётся делать это самим.

Третья проблема возникает только в высоконагруженных приложениях — при вставке большого количества строк БД должна блокировать генератор идентификаторов чтобы избежать использования одного ID несколькими сущностями, это может стать узким местом в приложении. Если БД масштабируется и используется master-master репликация, то всё становится ещё сложнее — в разных БД существуют разные настройки, которые могут генерировать записи с пропусками (например, первый сервер будет генерировать только нечетные идентификаторы, а второй только четные) или генерировать идентификаторы из разных подмножеств.

Резимуруя этот подход:

• Читаемые и запоминаемые URL.

• Проблемы с идемпотентностью.

• В некоторых случаях нужно дополнительно озаботиться возвращением идентификаторов при вставке.

• Снижение производительности в высококонкурентной среде.

• Усложняет масштабирование.

Генерируемый БД GUID в качестве идентификатора

При использовании сгенерированных БД гуидов мы можем избавиться от части проблем — например, NEWSEQUENTIALID() использует для генерации значений данные оборудования (MAC-адрес сетевой карты и "идентификатор часов"), поэтому сгенерированный с помощью неё иденитфикатор остается глобально уникальным. Это избавляет от необходимости дополнительной настройки генерации последовательности иденификаторов при репликации.

Функция генерирует корректно сортируемые последовательности, так что данные будут вставляться последовательно, а при слиянии данных с нескольких реплик эти данные так же будут локально последовательными.

52DE358F-45F1-E311-93EA-00269E58F20D
53DE358F-45F1-E311-93EA-00269E58F20D
54DE358F-45F1-E311-93EA-00269E58F20D
55DE358F-45F1-E311-93EA-00269E58F20D
56DE358F-45F1-E311-93EA-00269E58F20D

В MySQL функция UUID() генерирует UUID версии 1, что делает их так же частично сортируемыми.

Стоит сразу заметить, что в PostgreSQL данные хранятся иначе, поэтому использование непоследовательных GUID не влияет катастрофически на производительность базы данных.

В случае генерируемых БД идентификаторов мы всё ещё вынуждены мириться с сложностью реализации идемпотентности в запросах и необходимостью заботиться о возвращении идентификаторов при вставке. Также тот факт, что гуиды являются 128-битными значениями по сравнению с 32-битными целыми числами, приводит к увеличению общего размера данных.

Генерируемый клиентом GUID в качестве идентификатора

Решение проблем генеририуемых БД первичных ключей заключается в использовании созданных клиентом идентификаторов. У этого подхода тоже есть различные плюсы и минусы!

Одним из преимуществ является то, что это просто. Все современные языки имеют доступные генераторы GUID; в .NET это метод Guid.NewGuid(), который возвращает случайный 128-битный идентификатор.

Вы можете установить это значение в качестве ID для добавляемой сущности, и вам не нужно беспокоиться о проверке, с каким идентификатором она была добавлена в БД. Используете ли вы EF Core или Dapper, Postgres или SqlServer, код будет одинаковым. Данные при запросе на вставку перемещаются только в одном направлении, от клиента к базе данных, а не в двух направлениях, как в случае с генерируемым БД первичным ключом.

Если вы создаете идентификаторы в своем клиентском коде, у вас теперь есть доступ к различным шаблонам идемпотентности. Например, представьте, что вы включаете GUID в запрос, но запрос завершается сбоем из-за ошибки сервера. Вы можете просто отправить тот же запрос еще раз, зная, что сервер сможет идентифицировать его как «дубликат», поэтому ему нужно только повторить часть действия, которое привело к ошибке или просто вернуть ответ об успешном создании сущности. Таким образом, вы можете избежать создания дубликатов.

Уникальность гуидов — это и их сильные стороны, и их слабость. С точки зрения разработчика и пользователя, с /book/55DE358F-45F1-E311-93EA-00269E58F20D работать не так просто, как с /book/1.

Тип Guid в .NET реализует UUID версии 4, то есть генерируемый полностью случайным образом идентификатор. С точки зрения базы данных эта случайность может вызвать большие проблемы. Случайность идентификаторов может привести к серьезной фрагментации индекса, что увеличивает размер вашей базы данных и влияет на общую производительность.

Если подводить итог для опции генерируемого на клиенте GUID, то получится следующее:

• Легко использовать и код остаётся универсальным при переходе между разными БД.

• Позволяет сделать запросы идемпотентными без дополнительного уровня абстракции.

• Нет необходимости читать значения из БД после вставки.

• Нечеловекочитаемые URL.

• Больший объем данных по сравнению с целочисленными идентификаторами.

• Могут вызвать проблемы с производительностью БД из-за фрегментации индекса.

Преимущества сортируемого GUID

У гуидов есть несколько преимуществ, и, кроме проблем с человекочитаемостью, один большой недостаток с фрагментацией индекса, вызванной их полной случайностью. А нам всего-то и нужен сортируемый последовательно-возрастающий глобально-уникальный идентификатор чтобы использовать его в качестве ключа. Где его взять?

Самый простой ответ — нам нужен тот самый UUID версии 1, который используется функциями БД для генерации идентификаторов. Но есть несколько проблем. В BCL нет полной реализации RFC 4211, и, судя по комментариям в github дотнета, такую поддержку прямо сейчас добавлять не планируется. Если поискать по nuget-пакетам, то какого-то одного стандарта де-факто, который бы активно использовался и поддерживался сообществом тоже нет. Я нашёл библиотеку Vlingo.Xoom.UUID, которая завляет поддержку RFC 4211. Ещё один способ из хабростатьи про GUID в качестве первичных ключей предлагает использовать DllImport к библиотеке, которая используется SQL Server для генерации идентификаторов — такой способ вызовет очевидную проблему с переносимостью.

internal static class NativeMethods
{
    [DllImport("rpcrt4.dll", SetLastError = true)]
    public static extern int UuidCreateSequential(out Guid guid);
}

Но у UUID версии 1 на мой взгляд есть недостатки на уровне самого стандарта. Во-первых, для метки времени используется количество 100-наносекундных интервалов, прошедших с 15 октября 1582 года. Это совсем не то, как мы привыкли думать о timestamp в нашем повседневном программировнии. Во-вторых, в случае с UUID версии 1 метка времени внутри идентификатора частично перевернута, то есть старшие биты таймстампа сдвинуты к младшим битам в самом UUID. Это объясняет тот факт, что в примере с NEWSEQUENTIALID() менялись именно старшие разряды идентификатора. Такой порядок делает лексикографическое упорядочивание немного бессмысленным.

Мы могли бы просто переставить биты внутри UUID и вернуть время и упорядоченность к изначальному виду от старших бит к младшим, но это дополнительное усложение, которое всё ещё предполагает использовать непривычный timestamp совсеместно с дополнительной логикой защиты от коллизий (в случае, если в 100нс интервал генерируется несколько идентификаторов). Хочется чего-то более нативного.

Отличные новости — именно для решения этой задачи есть библиотека NewId, которая позволяет генерировать лексикографически упорядоченные по времени создания идентификаторы. Сама библиотека основана на Snowflake_ID, который разработан специально для использования в распределенных системах, и Flake, который развивает идеи UUID версии 1. Самый простой способ понять, что это значит, — показать, как выглядят идентификаторы, сгенерированные NewId.

foreach (var i in Enumerable.Range(0, 5))
{
    Guid id = NewId.NextGuid();
    Console.WriteLine(id);
}

Пример результата работы программы:

d3630000-5d0f-0015-2872-08da3058ad5a
d3630000-5d0f-0015-4837-08da3058ad5b
d3630000-5d0f-0015-8f37-08da3058ad5b
d3630000-5d0f-0015-2fd8-08da3058ad5b
d3630000-5d0f-0015-ed68-08da3058ad5c

NewId использует в качестве данных для создания идентификатора 3 источника:

• Worker/process ID, который отвечает за уникальность между процессами/сервером — именно он отвечает за общую для всех идентификаторов часть, а идентификатор конкретного процесса можно включить дополнительно для избежания коллизий между процессами в рамках одной машины.

• Timestamp, который обеспечивает сортируемость идентификатора.

• Последовательно возрастающий идентификатор.

Объединив 3 части вместе, вы можете получить идентификатор, который будет частично отсортированным благодаря компоненту метки времени. Включив идентификатор процесса, можно избежать коллизий при генерации идентификаторов несколькими процессами. А использование части с последовательно возрастающим идентификатором позволяет генерировать 2^16-1 идентификаторов в миллисекунду в рамках одного процесса:

Код генерации идентификатора для самых любознательных

На сколько же NewId снижает фрагментацию индекса?

Сравнение фрагментации индекса при использовании разных генераторов UUID

В сравнительном эксперементе я решил сравнить степень фрагментации и плотность данных от несколько генераторов UUID в качестве первичных ключей:

• Guid.NewGuid()

• [DllImport("rpcrt4.dll", SetLastError = true)]

• Vlingo.UUID.TimeBasedGenerator.GenerateGuid c опцией GuidGenerationMode.WithUniquenessGuarantee

• MassTransit.NewId.NextGuid()

• MassTransit.NewId.NextSequentialGuid()

В тесте для простой таблицы с идентификатором и текстовым полем будет добавляться 10 тысяч записей, каждая с случайной задержкой 100-500 миллисекунд, таким образом в идентификаторе будут участвовать таймштампы за 50 минут одного дня.

NewId, по-видимому, в значительной степени ориентирован на сервер SQL Server. Поэтому, и потому, что для MySQL я не нашёл понятного способа измерить фрагментацию данных и эффективность использования дискового пространства, тесты проводились именно на SQL Server.

Развернем Docker-образ SQL Server:

docker run -d --name sql1 --hostname sql1 \
    -e "ACCEPT_EULA=Y" \
    -e "SA_PASSWORD=Passw0rd!" \
    -p 1433:1433 \
    mcr.microsoft.com/mssql/server:2019-latest

Создадим 4 простые таблицы для разных типов сгенерированных идентификаторов:

CREATE TABLE dbo.normal_guids (
  Id uniqueidentifier PRIMARY KEY,
  Dummy varchar(50) NOT NULL
);

CREATE TABLE dbo.dllimport_guids (
  Id uniqueidentifier PRIMARY KEY,
  Dummy varchar(50) NOT NULL
);

CREATE TABLE dbo.vlingouuid_guids (
  Id uniqueidentifier PRIMARY KEY,
  Dummy varchar(50) NOT NULL
);

CREATE TABLE dbo.newid_guids (
  Id uniqueidentifier PRIMARY KEY,
  Dummy varchar(50) NOT NULL
);

Создадим в таблицах тестовые данные при помощи старого-доброго ADO.NET:

using System.Data;
using Vlingo.UUID;
using Microsoft.Data.SqlClient;

var connString = @"Server=127.0.0.1,1433;Database=Master;User Id=SA;Password=Passw0rd!;TrustServerCertificate=True";
using var connection = new SqlConnection(connString);
await connection.OpenAsync();

foreach (var i in Enumerable.Range(0, 10_000))
    await InsertGuid(connection, "normal_guids", Guid.NewGuid());

foreach (var i in Enumerable.Range(0, 10_000))
{
    NativeMethods.UuidCreateSequential(out var guid);
    await InsertGuid(connection, "dllimport_guids", guid);
}

var vlingoGenerator = new Vlingo.UUID.TimeBasedGenerator();
foreach (var i in Enumerable.Range(0, 10_000))
    await InsertGuid(connection, "vlingouuid_guids", vlingoGenerator.GenerateGuid(GuidGenerationMode.WithUniquenessGuarantee));

foreach (var i in Enumerable.Range(0, 10_000))
    await InsertGuid(connection, "newid_guids", MassTransit.NewId.NextGuid());

async Task InsertGuid(SqlConnection sqlConnection, string table, Guid id)
{
	await using var command = new SqlCommand($@"INSERT INTO dbo.{table} (Id, Dummy) VALUES (@ID, 'test')", sqlConnection);
	command.Parameters.Add(new("ID", SqlDbType.UniqueIdentifier) { Value = id });
	await command.ExecuteNonQueryAsync();
	await Task.Delay(Random.Shared.Next(100, 500));
}

Чтобы посмотреть размер каждого индекса и его фрагментацию, используем стащенный из этой статьи запрос:

SELECT OBJECT_NAME(ips.OBJECT_ID)
     ,avg_fragmentation_in_percent
     ,avg_page_space_used_in_percent
     ,page_count
FROM sys.dm_db_index_physical_stats(DB_ID(), NULL, NULL, NULL, 'SAMPLED') ips
         INNER JOIN sys.indexes i ON (ips.object_id = i.object_id)
    AND (ips.index_id = i.index_id)
ORDER BY avg_fragmentation_in_percent DESC

Результаты:

                        avg_frag_in_percent   avg_page_space_used_in_percent   page_count
normal_guids            97.53086419753086     71.66382505559672                81
dllimport_guids         5.084745762711865     98.3951321966889                 59
vlingouuid_guids        3.389830508474576     98.3951321966889                 59
newid_guids             5.084745762711865     98.3951321966889                 59

Полученные данные легко объяснить из информации, которую мы уже знаем. Во-первых, сгенерированные случайно идентификаторы приводят к большой фрагментации данных поскольку новые элементы вставляются на случайную позицию. NewId вызвали только 5-процентную фрагментацию, а Vlingo.UUID всего 3-процентную фрагментацию. Ещё при использовании Guid остается больше пустого места на каждый странице с данными (возможно, из-за постоянных перемещений данных во время вставки), поэтому вам нужно больше страниц для хранения того же объема данных (81 против 59). Это тоже станет источником некоторого снижения производительности при использовании гуидов.

Но на самом деле влияние фрагментации при чтении данных совсем не так велико, как может представляться — скорее можно назвать его незначительным. Вот пример замера производительности при чтении 10.000 записей и 100.000 записей в запросе:

Настоящая проблема c производительностью гуидов начинается в больших таблицах при вставке данных — потому что индекс перестраивается случайным образом, а сервер БД не может сделать предсказания для следующего набора данных. Один из бенчмарков сравнивает производительность добавления 5 миллионов записей батч-запросами по 100.000 записей каждая в таблицу c автоинкрементным целым ключом, UUID версии 1, 4 или подхаченной "последовательной" версии 4 после манипуляции с битами. По результатам видно, что после полутора миллионов записей UUID версии 4 начинает деградировать, а время вставки быстро растет:

В другом бенчмарке сравнивается добавление записей в БД, где ключи генерируются разными функциями SQL: uuid_generate_v4(), uuid_time_nextval() и uuid_sequence_nextval() с разным набором параметров. Тесты проводятся в трёх условиях: на изначально пустой таблице, помещающейся в оперативную память таблице и явно не влезающей в оперативную память таблице. С ростом объёма данных тоже видно значительное снижение скорости добавления новых данных:

Выводы

Библиотеки NewId и Vlingo.UUID явно делают свою работу. Первая создана и развивается специально для решения проблемы с первичными ключами в базах данных, где данные строк хранятся в кластерных индексах. Вторая — утилитарный пакет платформы XOOM компании Vlingo и не имеет даже публичной документации.

Стоит ли его использовать? Ответ, как обычно — "зависит". Но это точно хорошая альтернатива, если вам нужно генерировать первичные ключи на клиенте и работать с MySQL или MS SQL Server.

Что почитать

1. "Первичный ключ – GUID или автоинкремент?", @YuriyIvon

2. "Generating sortable Guids using NewId", Andrew Lock | .NET Escapades

3. "MySQL Performance When Using UUID For Primary Key", Programster's Blog

4. "Sequential UUID Generators", Tomas Vondra in 2ndQuadrant blog

5. "Index fragmentation revisited", Tibor Karaszi's SQL Server blog

6. "Flake: A Decentralized, K-Ordered Unique ID Generator in Erlang", Dietrich Featherston

7. "Announcing Snowflake", Twitter engineering blog

8. "What is the Guid in .NET?", Johan Vergeer

9. RFC 4122: A Universally Unique IDentifier (UUID) URN Namespace