CombGuid. Генерация “дружественных” к SQL серверам значений Guid в .net приложениях

Использование uuid в качестве первичного ключа для таблиц имеет множество преимуществ, одним из которых является возможность получать идентификаторы для создаваемых в клиентском приложении объектов самостоятельно, без обращения к серверу баз данных. Но использование uuid в качестве первичного ключа имеет и недостаток: guid-ы, сгенерированные клиентским приложением, могут быть недостаточно “дружелюбны” к SQL серверу, что в свою очередь может привести к оверхеду при добавлении новой записи. Возможное удорожание операции insert вытекает из того, что SQL сервер для хранения таблиц, по которым задан первичный ключ, обычно использует структуры известные как b-деревья. При добавлении новой записи в таблицу, SQL сервер, в соответствии с сортировкой по первичному ключу, ищет лист, на котором должна быть размещена вставляемая запись. Учитывая псевдослучайный алгоритм генерации uuid, сортировочный порядок новой записи также случаен и возможна ситуация, что лист, на котором должна быть размещена запись, полностью заполнен. В подобных случаях SQL серверу приходится разделять лист надвое и перестраивать ветви b-дерева, ведущие к этому листу. Чтобы не сталкивать SQL сервер с необходимостью постоянно перестраивать кластерный индекс при добавлении новых записей, можно вести генерацию значений первичного ключа в нарастающей последовательности. Один из вариантов генерации Guid в нарастающем порядке — это привязывать сортировочный порядок сгенерированного Guid к текущему времени. Сгенерированные подобным образом идентификаторы часто называют CombGuid, намекая на то, что строятся они из двух половинок — псевдослучайной части, как у обычных Guid, и строки, привязанной ко времени.

Как SQL сервер сравнивает uuid-ы

SQL сервер сортирует значения uuid отличным от .net способом. Сравнение ведется по байтовым группам справа-налево. Внутри байтовой группы сравнение ведется уже слева-направо. (Байтовой группой называется последовательность, ограниченная символом ‘-’.) Если сравнить два значения uuid,
@u1 = ‘206AEBE7-ABF0-47A8-8AA5-6FDDF39B9E4F’
и
@u2 =’0F8257A1-B40C-4DA0-8A37-8BBC55183CAE’, на выходе получится, что @u2>@u1, поскольку, как уже было сказано выше, SQL сервер начинает сравнение с крайних справа байтовых групп, где 6FDDF39B9E4F < 8BBC55183CAE. Если говорить более технически, наибольшее влияние на сортировочный порядок uuid в базах данных оказывают байты с 9 по 15, в порядке убывания.

Реализация CombGuid в библиотеке Magnum

В своем проекте мы используем библиотеку Magnum, частью которой является статический класс CombGuid с единственным методом Generate(), создающим привязанные ко времени Guid-ы. Magnum — библиотека с открытым исходным кодом, выложенная на GitHub. Я не поленился и посмотрел, как выглядит реализация метода создания Guid в этой библиотеке.

public static class CombGuid
{
	static readonly DateTime _baseDate = new DateTime(1900, 1, 1);

	public static Guid Generate()
	{
		byte[] guidArray = Guid.NewGuid().ToByteArray();

		DateTime now = DateTime.Now;

		// Get the days and milliseconds which will be used to build the byte string
		var days = new TimeSpan(now.Ticks - _baseDate.Ticks);
		TimeSpan msecs = now.TimeOfDay;

		// Convert to a byte array
		// Note that SQL Server is accurate to 1/300th of a millisecond so we divide by 3.333333
		byte[] daysArray = BitConverter.GetBytes(days.Days);
		byte[] msecsArray = BitConverter.GetBytes((long)(msecs.TotalMilliseconds/3.333333));

		// Reverse the bytes to match SQL Servers ordering
		Array.Reverse(daysArray);
		Array.Reverse(msecsArray);

		// Copy the bytes into the guid
		Array.Copy(daysArray, daysArray.Length - 2, guidArray, guidArray.Length - 6, 2);
		Array.Copy(msecsArray, msecsArray.Length - 4, guidArray, guidArray.Length - 4, 4);

		return new Guid(guidArray);
	}
}

Алгоритм довольно прост.
В 9-10 байте закодировано число дней, прошедших с 1 января 1900 года. Надо не забыть пересобрать исходники в 2079 году, когда количество прошедших дней перестанет умещаться в двух байтах. 11-15 байт использованы для кодирования миллисекунд с начала суток, зачем-то поделенных на 3.333333. В комментариях в коде указано, что эта операция связана с тем, что точность хранения временных меток в SQL сервере составляет 1/300 секунды. Довольно странное решение, учитывая, что нам в процессе генерирования uuid абсолютно неважно как SQL сервер хранит временные метки, мы используем миллисекунды только для создания uuid. Я немного погуглил этот вопрос, но понял только то, что автор библиотеки Magnum Chris Patterson скопировал код генерации CombGuid из Nhibernate. Как видно здесь, метод GenerateComb содержит тот же самый код. Справедливости ради надо отметить, что деление миллисекунд на 3.333333 особого влияния на работу алгоритма не оказывает, это просто лишний, необязательный шаг.

Guid vs CombGuid. Сравниваем скорость вставки в БД

Наконец, мы подошли к тому, ради чего все это затевалось, к сравнению на сколько uuid-ы, сгенерированные методом Guid.NewGuid(), медленнее своих собратьев, созданных через CombGuid.Generate(), в контексте вставки записей в таблицу SQL сервера.
Для теста я создал два скрипта, создающие таблицы на SQL сервере и вставляющие в эти таблицы 100000 строк. Первый скрипт вставляет в базу данных строки с Id, созданными с помощью метода CombGuid.Generate(), второй — с помощью метода Guid.NewGuid().

Кусочек тестового скрипта.

USE [CombIdTest]
GO
--сбрасываем кеши сервера
DBCC DROPCLEANBUFFERS;
DBCC FREEPROCCACHE;
CREATE TABLE [dbo].[CombId](
	[ID] [uniqueidentifier] NOT NULL,
	[Value] [varchar](4000) NOT NULL,
 CONSTRAINT [PK_CombId] PRIMARY KEY CLUSTERED 
(
	[ID] ASC
)WITH (PAD_INDEX = OFF, STATISTICS_NORECOMPUTE = OFF, IGNORE_DUP_KEY = OFF, ALLOW_ROW_LOCKS = ON, ALLOW_PAGE_LOCKS = ON) ON [PRIMARY]
) ON [PRIMARY]
GO
--вставку производим в рамках одной транзакции
begin transaction
 insert into CombId Values ('5cb31d3d-3793-428e-beb0-a2e4047e255c','somevalue');
 insert into CombId Values ('1e905fa1-e4d4-4a2c-a185-a2e4047e255d','somevalue');
-- еще 99998 операций insert
commit transaction

Перед выполнением вставки сброшены буферные кеши и сама вставка производится в одну транзакцию, дабы уменьшить количество обращений к журналу транзакций. Каждый скрипт был запущен трижды, в качестве времени выполнения взят параметр “Общее время выполнения” из статистики клиента.

Результаты измерений (в миллисекундах).

Преимущество скрипта, вставляющего записи содержащие CombGuid, чуть более 10 процентов над скриптом с “обычными” uuid. Использование CombGuid также положительно сказалось и на размере таблицы — ее размер оказался почти в полтора раза меньше: 3.75 Мб против 5,25 Мб.

Ну и пара вопросов напоследок

Что вы используете в качестве первичных ключей в ваших БД?
Если используете uuid или похожие на них байтовые структуры, как вы их генерируете?

Автор: steamru

Источник