GUID у ролі швидкого первинного ключа для різних БД - About

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

Історично склалося так, що найбільш загальним підходом у проектуванні БД для ідентифікації конкретного рядка використовувалася ціла послідовність. Як правило, така послідовність генерується на стороні сервера в момент вставлення нового рядка. Такий простий і ясний підхід підходить для багатьох програм.

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

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

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

Проблема у продуктивності. Для отримання найкращої продуктивності більшість баз даних зберігають рядки кластеризованих індексах, тобто. Рядки в таблицях реально зберігаються на диску в деякому відсортованому порядку. Це робить пошук потрібного рядка таким же простим, як пошук індексу, але цей механізм робить вставку нового значення дуже повільною, якщо нове значення не потрапляє в кінець списку. Наприклад розглянемо такий приклад:

Все досить просто: рядки містяться в порядку зростання ID. Якщо ми додамо рядок із номером 8, то проблем не буде – рядок просто встане до кінця списку.

Нехай тепер треба вставити рядок із номером 5:

Рядки 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-982 4664-ba01-0d492ba3bd83

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

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

00000001-a411-491d-969a-77bf40f55175 00000002-d97d-4bb9-a493-cad277999363 00000003-916c-4986-a00 -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 за останніми шістьма значними байтами (останні шість байт у блоці 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 32 ітерації. Оскільки ми покладаємося на випадковість, тоПостараємося отримати якомога чесніше випадкове число і класRNGCryptoServiceProvider дає таку можливість.

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

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

Невелика замітка, перш ніж рушити далі. Використання роздільної здатності в 1 мілісекунду є достатнім для багатьох завдань. Я експериментував з додатковими лічильниками та меншою роздільною здатністю, але це не мало великого сенсу, оскільки відмінності були мінімальні. Бази відмінно справляються з сотнями GUID з єдиним відбитком часу, так що це не проблема.