Эта статья раскрывает подходы по использованию GUID в роли первичного ключа или кластерного индекса при этом описываются способы обхода основных неудобств связанных с GUID, на основании COMB модели для последовательных значений GUID разработанных в статье Джимми Нильсона. Большинство реализаций являются специфичными для MS SQL Server, в то время как основная идея похоже используется во многих библиотеках и фреймворках(включая NHibernate). В статье предпринимается попытка использовать общий гибкий подход для возможности использования COMB в других популярных базах данных: Oracle, PostgreSQL, MySQL. Так же мы рассмотрим некоторые особенности .net в свете наших задач.

Проблематика GUID

Исторически сложилось так, что наиболее общим подходом в проектировке БД для идентификации конкретной строки использовалась целочисленная последовательность. Как правило, такая последовательность генерируется на стороне сервера в момент вставки новой строки. Такой простой и ясный подход подходит для многих приложений.

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

Одной из альтернатив становится использование GUID в роли первичного ключа. GUID - это 128-битное значение, которое поддерживает разумно-гарантированную уникальность независимо от времени и пространства. Стандарт для создания GUID описан в документе RFC 4122, но большинство современных алгоритмов по созданию GUID используют либо очень большое случайное число, либо формируют значение исходя из некоторой случайной информации комбинированной с чем-то локальным (ранее такое формирование было у MS, они создавали GUID на основе MAC адреса, но в последствии это было не безопасно и так же нарушало privacy).

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

Так в чем же проблема?

Проблема в производительности. Для получения наилучшей производительности большинство баз данных хранят строки в кластеризованных индексах, т.е. строки в таблицах реально хранятся на диске в некотором отсортированном порядке. Это делает поиск нужной строки таким же простым, как поиск индекса, но этот же механизм делает вставку нового значения очень медленной, если новое значение не попадает в конец списка. Для примера рассмотрим такой пример:

ID	Name
1	Holmes, S.
4	Watson, J.
7	Moriarty, J.

Все достаточно просто: строки содержатся в порядке возрастания ID. Если мы добавим строку с номером 8, то проблем не будет - строка просто встанет в конец списка.

ID	Name
1	Holmes, S.
4	Watson, J.
7	Moriarty, J.
8	Lestrade, I.

Пусть теперь надо вставить строку с номером 5:

ID	Name
1	Holmes, S.
4	Watson, J.
5	Hudson, Mrs.
7	Moriarty, J.
8	Lestrade, I.

Строки 7 и 8 должны быть сдвинуты вниз для того, чтобы освободить место для новой записи. Не проблема в данном случае, но когда мы говорим об этой операции, когда в таблице миллионы строк, это становится настоящей проблемой. И когда вы захотите сделать сотни вставок в секунду, это может быть действительно сложно.

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

Последовательные GUID

Итак, какое же решение можно применить? Основная проблема в высокой степени разрозненности данных в GUID. В таком случае мы можем постараться сделать GUID более последовательным и предсказуемым. Подход COMB (составное из COMBined GUID\timestamp) заменяет часть GUID значением которое гарантированно возрастает, или как минимум не убывает с каждым новым значением. Как можно догадаться из определения СОМВ, для этих целей применяется значение сгенерированное из текущей даты и времени.

Для иллюстрации сказанного представим набор стандартных GUID:

fda437b5-6edd-42dc-9bbd-c09d10460ad0
2cb56c59-ef3d-4d24-90e7-835ed5968cdc
6bce82f3-5bd2-4efc-8832-986227592f26
42af7078-4b9c-4664-ba01-0d492ba3bd83

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

Теперь представим гипотетический список специальных GUID:

00000001-a411-491d-969a-77bf40f55175
00000002-d97d-4bb9-a493-cad277999363
00000003-916c-4986-a363-0a9b9c95ca52
00000004-f827-452b-a3be-b77a3a4c95aa

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

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

128-битный GUID состоит из 4 основных блоков: Data1, Data2, Data3, Data4 - которые вы можете увидеть на примере:

11111111-2222-3333-4444-444444444444

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

К несчастью, базы данных по разному работают с GUID. Некоторые из них (MS SQL, PostgreSQL) имеют встроенный тип для работы с GUID. БД без встроенной поддержки работают с GUID как с текстовым полем длинной в 36 символов. Оракл обычно использует "сырой" набор байт в колонке типа raw(16).

Дополнительной сложности прибавляет факт того, что MS SQL упорядочивает GUID по последним 6 значимым байтам (последние 6 байт в блоке Data4). Т.ч. если мы хотим создать последовательный GUID для использования в SQL Server, то надо последовательную часть вставлять в конец. Большая других систем ожидает увидеть последовательную часть в начале.

Алгоритм

Принимая во внимание тот факт, что базы данных по разному работают с GUID, не может быть единого алгорима, который удовлетворяет всем потребностям. Придется управлять способом создания в зависимости от того, как БД работает с GUID. После проведения некоторых экспериментов, я выделил три основных подхода, которые должны покрыть все случаи:

• Создание последовательного GUID в виде строки
• Создание последовательного GUID в виде двоичных данных
• Создание последовательного GUID, с последовательной частью в конце для MS SQL

(Почему GUID могут не совпадать в виде строки и набора байт? Потому что то, как .Net оперирует GUID может не совпадать со строковыми представлениями на little-endian системах, а большинство машин использующих .Net являются little-endian. Подробности далее.)

Выбор стратегии можно представить в виде следующего перечисления:

После этого можно определить метод для создания GUID, который будет принимать перечисление:

Но как именно мы будет создавать последовательный GUID? Какую именно часть мы оставим "случайной", а какую заменим на временной отпечаток? Исходная спецификация для COMB с реализацией для MS SQL, заменяет последние 6 байт на значение времени. Это частично за рамками удобства, так как те 6 байт используются для упорядочивания, но 6 байт для времени будет достаточно. Оставшихся 10 байт будет достаточно для случайной компоненты.

Итак, как только что было сказано, начнем с получения 10 случайных байт:

Для генерирования случайной компоненты GUID используется класс RNGCryptoServiceProvider, так как System.Random имеет некоторые особенности, которые делают его непригодным для нашей задачи. Значения генерируемые им соответствуют некоторому определенному шаблону и начинают повторяться не более чем через 2³² итерации. Так как мы полагаемся на случайность, то постараемся получить как можно более честное случайное число и класс RNGCryptoServiceProvider дает такую возможность.

Отлично, теперь у нас есть данные и осталось заменить часть их на временной штамп. Мы договорились, что это должен быть шестибайтовый штамп, но на основе чего его создавать? Очевидный вариант - это использовать DateTime.Now и перевести каким-нибудь образом дату к 6-байтовому массиву. Использование свойства Ticks так же заманчиво, т.к. оно возвращает количество 100-наносекундных интервалов прошедших с 1 января 1 года. В любом случае здесь есть несколько проблем.

Во-первых, Ticks возвращает 64-битное число, а у нас есть только 48 бит, и если мы избавимся от двух байт, то оставшиеся 48-бит с учетом 100-наносекндного интервала дадут менее года до того, как значения начнут повторяться. Это разрушит порядок, который мы пытаемся настроить и убьет производительность базы данных, на которую мы так надеялись. Так как большинство приложений рассчитаны более чем на один год использования, то стоит использовать другую временную размерность.

Другая сложность состоит в том, что DateTime.Now имеет ограничение по разрешающей способности во времени. В соответствии с документами, значение может быть обновлено только каждые 10 миллисекунд. По ходу дела на некоторых системах этот период может быть меньше, но мы не можем полагаться на это.

Хорошие новости заключаются в том, что два недостатка в каком-то смысле отменяют друг друга: ограниченная разрешающая способность означает, что мы не можем использовать все значение Ticks, однако мы можем использовать его опосредованно. Разделим значение поля на 10000 чтобы получить значение укладывающееся в 48-бит. Я собираюсь использовать миллисекунды, так как это дает возможность использовать эти значения до 5800 года, до того как значения пойдут на второй круг, думаю этого будет достаточно для многих современных приложений.

Небольшая заметка, перед тем как двинуться дальше. Использование разрешения в 1 миллисекунду является достаточным для многих задач. Я экспериментировал с дополнительными счетчиками и меньшей разрешающей способностью, но это не имело большого смысла так как различия были минимальны. Базы отлично справляются с сотнями GUID с единым временным отпечатком, так что это не проблема.

Теперь у нас есть отпечаток времени. Так как мы получили набор байт с помощью BitConverter, то потребуется проверка системы на последовательность байт.

Осталось только все совместить в соответствии с перечислением SequentialGuidType:

В целом все достаточно хорошо, однако стоит учитывать особенности .Net в том, как он представляет GUID. Для фреймворка это не простая последовательность байт. Он представляет GUID как структуру содержащую 32-битное целочисленное, 2  16-битных целочисленных и 8 индивидуальный байт.

Что нам с этого? Основная проблема опять состоит в порядке байт. Опять необходимо переставлять их порядок, но только для строкового представления для little-endian систем.

Остается теперь самое простое - вернуть результат всех вычислений:

Использование

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

Database	GUID Column	SequentialGuidType Value
Microsoft SQL Server	uniqueidentifier	SequentialAtEnd
MySQL	char(36)	SequentialAsString
Oracle	raw(16)	SequentialAsBinary
PostgreSQL	uuid	SequentialAsString
SQLite	varies	varies

Для базы SQLite нет родного представления для GUID, но есть расширения, которые эмулируют поддержку. Так или иначе GUID может быть представлен как 16 байтным массивом, так и строкой в 36 символов.

Вот несколько примеров GUID полученных с помощью нового метода NewSequentialGuid(SequentialGuidType.SequentialAsString):

39babcb4-e446-4ed5-4012-2e27653a9d13
39babcb4-e447-ae68-4a32-19eb8d91765d
39babcb4-e44a-6c41-0fb4-21edd4697f43
39babcb4-e44d-51d2-c4b0-7d8489691c70

И еще пример NewSequentialGuid(SequentialGuidType.SequentialAsBinary):

b4bcba39-58eb-47ce-8890-71e7867d67a5
b4bcba39-5aeb-42a0-0b11-db83dd3c635b
b4bcba39-6aeb-4129-a9a5-a500aac0c5cd
b4bcba39-6ceb-494d-a978-c29cef95d37f

Если посмотреть эти данные с помощью ToSting(), то можно заметить кое-что странное. Первые два блока будут записаны в обратном порядке. Это происходит как раз из-за обсуждаемой проблемы с big\little-endian системами. Если эти данные записать в виде строки, то будут проблемы с производительностью. Решением может стать использование Guid.ToByteArray():

39babcb4eb5847ce889071e7867d67a5
39babcb4eb5a42a00b11db83dd3c635b
39babcb4eb6a4129a9a5a500aac0c5cd
39babcb4eb6c494da978c29cef95d37f

Тесты

Для тестирования были взяты следующие системы: MS SQL Server 2008, MySQL 5.5, Oracle XE 11.2 и PostgreSQL 9.1. Все базы работали на Win7 на домашней машине.

Тесты запускались с помощью консольных приложений предоставляемых с каждой базой. Вставлялось 2 миллиона строк с GUID в виде первичного ключа и с текстовым значением в 100 символов.Использовались все методы описанные в статье. Для контроля использовался так же Guid.NewGuid(), а так же первичный ключ целочисленного типа. Время замерялось в секундах после вставки каждого миллиона. Вот что получилось:

Для MS SQL результаты в целом такими и ожидались, ведь SequentialAtEnd был сделан как раз для этой базы данных. Различия с целочисленным значением всего в 8.4%.

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

Управляться с Oracle оказалось сложнее. Сохраняя GUID в колонку raw(16) можно ожидать, что метод SequentialAsBinary будет самым быстрым, и это так, но даже произвольные GUID не были слишком медленными, не столь медленными по сравнению с целочисленным ключом. Даже более того, последовательные GUID оказались быстрее чем целочисленные ключи, что тяжело было предсказать и принять! Я конечно подозреваю, что тут сыграла роль моей некомпетентности в написании запроса для Oracle, и если кто-то опровергнет данные дайте мне знать.

Так же как и с Oracle производительность с произвольным GUID не оказалась удручающей. Как и ожидалось, метод с SequentialAsString оказался самым быстрым, почти в два раза быстрее произвольного GUID.

Дополнительные соображения

Есть еще несколько вещей, которые стоит принять во внимание. В данной статье мы много времени уделили времени вставки значений в базу, но совершенно упустили из виду время формирования самого GUID, по сравнению с Guid.NewGuid(). Конечно, время формирования дольше. Я могу создать миллион произвольных GUID за 140 ms, но на создание последовательных уйдет 2800 ms, что в 20 раз медленнее.

Быстрые тесты показали, что львиная доля такого замедления приходится на использование сервиса RNGCryptoServiceProvider для генерирования произвольных данных. Переключение на System.Random снизило время выполнения до 400 ms. Я все еще не рекомендую этот способ из-за описанных опасностей.

Является ли такое замедление проблемой? Лично для себя я решил, что нет. До тех пор пока ваше приложение не использует интенсивные вставки данных (а тогда стоит рассмотреть саму целесообразность использования GUID), стоимость генерирования согласуется с временем работы самой базы и ее дальнейшей быстрой работы.

Другая возможная проблема: будут ли 10 байт достаточны для гарантирования уникальности? С учетом временного штампа это означает, что два любых GUID созданных в период больший чем несколько миллисекунд будут гарантированно разными.  Но что с GUID, которые создаются действительно очень быстро в одном промежутке времени. В таком случае 10 байт дают нам оценку в 2⁸⁰, или 1,208,925,819,614,629,174,706,176 возможных комбинаций. Т.е. вероятность будет такой же как и то, что в этот момент ваша база данных и все бэкапы будут одновременно атакованы и уничтожены ордой диких свиней.

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

Итоговый код

Надеюсь, что было интересно и полезно читать этот материал.

• Купить программное обеспечение компании Microsoft
• Каталог программ СУБД/БАЗЫ ДАННЫХ
• Каталог программ Oracle