(495) 925-0049, ITShop интернет-магазин 229-0436, Учебный Центр 925-0049
  Главная страница Карта сайта Контакты
Поиск
Вход
Регистрация
Рассылки сайта
 
 
 
 
 

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

Источник: habrahabr
steamru

Использование 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
Перед выполнением вставки сброшены буферные кеши и сама вставка производится в одну транзакцию, дабы уменьшить количество обращений к журналу транзакций. Каждый скрипт был запущен трижды, в качестве времени выполнения взят параметр "Общее время выполнения" из статистики клиента. Замеры производились на MSSQL Server 2012.

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

  1 2 3 Среднее
CombGuid 2795 2882 2860 2845,667
RandomGuid 3164 3129 3111 3134,667

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

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

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

Ссылки по теме


 Распечатать »
 Правила публикации »
  Обсудить материал в конференции Microsoft »
Обсудить материал в конференции Дизайн, графика, обработка изображений »
Написать редактору 
 Рекомендовать » Дата публикации: 06.03.2014 
 

Магазин программного обеспечения   WWW.ITSHOP.RU
Microsoft Windows Professional 10, Электронный ключ
Microsoft Office 365 Профессиональный Плюс. Подписка на 1 рабочее место на 1 год
Microsoft System Center Standard Core Sngl License/Software Assurance Pack OLP 2Licenses NoLevel CoreLic Qualified
Microsoft Visual Studio Professional w/MSDN AllLng License/Software Assurance Pack OLP 1 License No Level Qualified
Microsoft Visual Studio Professional w/MSDN AllLng Software Assurance OLP 1 License No Level Qualified
 
Другие предложения...
 
Курсы обучения   WWW.ITSHOP.RU
 
Другие предложения...
 
Магазин сертификационных экзаменов   WWW.ITSHOP.RU
 
Другие предложения...
 
3D Принтеры | 3D Печать   WWW.ITSHOP.RU
 
Другие предложения...
 
Новости по теме
 
Рассылки Subscribe.ru
Информационные технологии: CASE, RAD, ERP, OLAP
Безопасность компьютерных сетей и защита информации
Новости ITShop.ru - ПО, книги, документация, курсы обучения
Программирование на Microsoft Access
CASE-технологии
eManual - электронные книги и техническая документация
Работа в Windows и новости компании Microsoft
 
Статьи по теме
 
Новинки каталога Download
 
Исходники
 
Документация
 
Обсуждения в форумах
Как извлечь рисунки из файла Word (42)
Вообще-то есть еще способ - сделать в Word-е Copy рисунка, открыть Microsoft Photo Editor и там:...
 
Сдача экзаменов Microsoft гарантия 100% (13)
Сдача экзаменов Microsoft гарантия 100%. Дополнительная информация по E-mail.
 
Подключение JavaScript (305)
Всем привет! Я подключаю JavaScript нижеприведенным образом. Код: <script...
 
Как восстановить рабочий стол? Помогите срочно надо! (3)
Windows 7 максимальная. В учетной записи сменила пароль и выключила комп, после включения...
 
Пять возможностей Windows, о которых вы могли не знать (5)
пыщпыщ
 
 
 



    
rambler's top100 Rambler's Top100