проблематика GUID
Історично склалося так, що найбільш загальним підходом у проектуванні БД для ідентифікації конкретної рядки використовувалася целочисленная послідовність. Як правило, така послідовність генерується на стороні сервера в момент створити новий рядок. Такий простий і ясний підхід підходить для багатьох додатків.
Тим не менш, є кілька ситуацій, коли такий підхід не буде хороший. При широкому застосуванні ORM фреймворків більшість користувачів намагаються уникнути зайвих складнощів на стороні БД, а формування ключа на стороні БД до таких складнощів можна віднести. Реплікація баз даних так само стає важкою, якщо покладатися тільки на єдиний внутрішньобазовими сервіс для генерації ключів. Потрібне зовнішнє джерело для мінімізації залежностей від того, як генеруються ключі.
Основним перевагою GUID є можливість генерації його на льоту, на стороні клієнта без необхідності перевірки унікальності в базі даних. На перший погляд це ідеальне рішення проблеми унікальних ключів.
Так в чому ж проблема?
Проблема в продуктивності. Для отримання найкращої продуктивності більшість баз даних зберігають рядки в кластеризованих індексах, тобто рядки в таблицях реально зберігаються на диску в деякому відсортованому порядку. Це робить пошук потрібного рядка таким же простим, як пошук індексу, але цей же механізм робить вставку нового значення дуже повільної, якщо нове значення не влучає у кінець списку. Для прикладу розглянемо такий приклад:
Рядки 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 - які ви можете побачити на прикладі:
Більшість алгоритмів, які використовуються сьогодні і особливо використовувані .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. Подробиці далі.)
Вибір стратегії можна представити у вигляді наступного перерахування:
view source print?
Але як саме ми будемо створювати послідовний GUID? Яку саме частину ми залишимо "випадкової", а яку замінимо на тимчасовій відбиток? Вихідна специфікація для COMB з реалізацією для MS SQL, замінює останні 6 байт на значення часу. Це частково за рамками зручності, так як ті 6 байт використовуються для упорядкування, але 6 байт для часу буде достатньо. Тих, хто залишився 10 байт буде досить для випадкової компоненти.
Отже, як тільки що було сказано, почнемо з отримання 10 випадкових байт:
view source print?
var rng = new System.Security.Cryptography.RNGCryptoServiceProvider ();
byte [] randomBytes = new byte [10];
Для генерування випадкової компоненти GUID використовується клас RNGCryptoServiceProvider. так як System.Random має деякі особливості, які роблять його непридатним для нашої задачі. Значення генеруються їм відповідають деякому певним шаблоном і починають повторюватися не більше ніж через 2 32 ітерації. Так як ми покладаємося на випадковість, то постараємося отримати якомога чесніше випадкове число і клас RNGCryptoServiceProvider дає таку можливість.
По-перше, Ticks повертає 64-бітове число, а у нас є тільки 48 біт, і якщо ми позбудемося двох байт, то що залишилися 48-біт з урахуванням 100-наносекндного інтервалу дадуть менше року до того, як значення почнуть повторюватися. Це зруйнує порядок, який ми намагаємося налаштувати і вб'є продуктивність бази даних, на яку ми так сподівалися. Так як більшість додатків розраховані більш ніж на один рік використання, то варто використовувати іншу тимчасову розмірність.
Хороші новини полягають в тому, що два недоліки в якомусь сенсі скасовують один одного: обмежена роздільна здатність означає, що ми не можемо використовувати всі значення Ticks, проте ми можемо використовувати його опосередковано. Розділимо значення поля на 10000 щоб отримати значення вкладається в 48-біт. Я збираюся використовувати мілісекунди, так як це дає можливість використовувати ці значення до 5800 року, до того як значення підуть на друге коло, думаю цього буде достатньо для багатьох сучасних додатків.
Невелика замітка, перед тим як вирушити далі. Використання дозволу в 1 мілісекунду є достатнім для багатьох завдань. Я експериментував з додатковими лічильниками і меншою роздільною здатністю, але це не мало великого сенсу так як відмінності були мінімальні. Бази відмінно справляються з сотнями GUID з єдиним тимчасовим відбитком, так що це не проблема.
view source print?
long timestamp = DateTime.Now.Ticks / 10000L;
byte [] timestampBytes = BitConverter.GetBytes (timestamp);
Тепер у нас є відбиток часу. Так як ми отримали набір байт за допомогою BitConverter, то буде потрібно перевірка системи на електронних даних.
view source print?
В цілому все досить добре, проте варто враховувати особливості .Net в тому, як він представляє GUID. Для фреймворка це не проста сукупність електронних даних. Він являє GUID як структуру містить 32-бітове цілочисельне, 2 16-бітних цілочисельних і 8 індивідуальний байт.
Що нам з того? Основна проблема знову складається в порядку байт. Знову необхідно переставляти їх порядок, але тільки для строкового подання для little-endian систем.
view source print?
if (guidType == SequentialGuidType.SequentialAsString
Array.Reverse (guidBytes, 0, 4);
Array.Reverse (guidBytes, 4, 2);
Залишається тепер найпростіше - повернути результат всіх обчислень:
view source print?
return new Guid (guidBytes);
Використання
Для використання методу необхідно визначити, що за базу даних ви використовуєте і який тип GUID найбільше підійде. Ось невеликі підказки по використанню:
Для бази 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
Тести запускалися за допомогою консольних додатків надаються з кожною базою. Вставляли 2 мільйони рядків з GUID у вигляді первинного ключа і з текстовим значенням в 100 сімволов.Іспользовалісь все методи описані в статті. Для контролю використовувався так само Guid.NewGuid (), а так же первинний ключ целочисленного типу. Час замірявся в секундах після вставки кожного мільйона. Ось що вийшло:
Для MS SQL результати в цілому такими і очікувалися, адже SequentialAtEnd був зроблений саме для цієї бази даних. Відмінності з цілочисельним значенням всього в 8.4%.
Управлятися з 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 80. або 1,208,925,819,614,629,174,706,176 можливих комбінацій. Тобто ймовірність буде такою ж як і те, що в цей момент ваша база даних і все бекапи будуть одночасно атаковано і знищені ордою диких свиней.
Остання проблема, яка вас може зацікавити, це те, що отримані GUID технічно не сумісні зі стандартом RFC 4122. Чесно, я не думаю, що це велика проблема, я не знаю жодної бази даних яка реально перевіряє внутрішній устрій GUID і упущення версії GUID дає нам додаткові байти для збільшення унікальності ключа.
підсумковий код
view source print?