UUID версии 7, или как не потеряться во времени при создании идентификатора

В течение многих лет я противостоял засилью UUID как ключей в базах данных, но со временем и практикой до меня дошло. Они действительно удобны, когда речь идёт о распределённых системах. Генерировать новый идентификатор на разных концах планеты не так-то просто. Создание псевдослучайных идентификаторов решает эту проблему.

Хотя, подобные решения, не всегда хороши. В отличие от обыкновенных цифровых значений, которые легко кешировать и сортировать, UUID не так гибки в использовании. UUID версии 7 предназначен как раз для того, чтобы разобраться с подобными проблемами.

Добро пожаловать в мир отсортированных случайностей.

Сами по себе UUID это не просто набор случайных битов. Существует несколько вариантов их генерации. @AloneCoder ^[1] в своей статье как генерируются UUID ^[2] в подробностях описывает уже существующие форматы идентификаторов, версии с первой по пятую.

UUID в базах данных

Почему нам необходимо генерировать UUID, а не просто брать случайные данные? Ну, ответов может быть множество. Сохранение данных о хосте, который сгенерировал последовательность, сохранение времени и тому подобных значений, позволяет сделать UUID более информативными. Подобный подход можно использовать при создании распределённых вычислительных систем. Например, вместо того, чтобы грузить базу данных запросами с датой, можно просто выбрать те идентификаторы, которые содержат в себе эту дату.

Всё бы хорошо, но вот именно это и не очень-то просто. Выбирать даты из строковых значений UUID это та ещё свистопляска. Почему? Ну, давайте посмотрим на последовательность генерации UUIDv1.

1. Берутся младшие 32 бита текущей временной метки UTC. Это будут первые 4 байта (8 шестнадцатеричных символов) UUID [TimeLow].

2. Берутся средние 16 битов текущей временной метки UTC. Это будут следующие 2 байта (4 шестнадцатеричных символа) [TimeMid].

3. Следующие 2 байта (4 шестнадцатеричных символа) конкатенируют 4 бита версии UUID с оставшимися 12 старшими битами текущей временной метки UTC (в которой всего 60 битов) [TimeHighAndVersion].

Как всё замечательно запутано. На самом деле, распарсить дату из такого идентификатора достаточно просто, но парсинг это парсинг. Это не весело и нагружает процессор.

Герой дня

Встречайте, UUIDv7!

На данный момент Версия 7 - это черновик RFC, доступный по адресу https://datatracker.ietf.org/doc/html/draft-peabody-dispatch-new-uuid-format-01 ^[3].

Основная разработка ведётся силами двух разработчиков: bradleypeabody ^[4] и kyzer-davis ^[5]. читатели и хабраалиены могут поучаствовать в обсуждении и написании формата на гитхабе https://github.com/uuid6/uuid6-ietf-draft/ ^[6].

Пять дней назад эта спецификация вызвала оживлённую дискуссию на hackernews ^[7].

При разработке спецификаций, были рассмотрены следующие форматы генерации UUID:

1. LexicalUUID ^[8] by Twitter

2. Snowflake ^[9] by Twitter

3. Flake ^[10] by Boundary

4. ShardingID ^[11] by Instagram

5. KSUID ^[12] by Segment

6. Elasticflake ^[13] by P. Pearcy

7. FlakeID ^[14] by T. Pawlak

8. Sonyflake ^[15] by Sony

9. orderedUuid ^[16] by IT. Cabrera

10. COMBGUID ^[17] by R.Tallent

11. ULID ^[18] by A. Feerasta

12. SID ^[19] by A. Chilton

13. pushID ^[20] by Google

14. XID ^[21] by O. Poitrey

15. ObjectID ^[22] by MongoDB

16. CUID ^[23] by E. Elliott

И так, что же такого особого в UUIDv7 и чем он отличается от предыдущих версий?

Эта версия идентификатора бинарно-сортируемая. То есть, вам больше не нужно конвертировать значения UUID в какой-либо другой формат, чтобы понять какое из них больше и меньше.

Ну а нам-то какая разница? Можно же сделать select id, creation_date order by creation_date и жить себе спокойно.

- Обыватель.

Вы не поняли вопроса.

Тут дело не в том, как вам, программисту, удобнее делать SELECT. Вопрос в том, как база данных хранит индексы. Созданные последовательно, UUIDv4 будут выглядеть случайными. Соответственно, при записи значений этих индексов в базу данных, даже если значения были созданы в один и тот же промежуток времени, кластеризация будет нагружать индексы при записи.

Представьте, у вас есть высоконагруженная система. 100 серверов генерируют новые записи с UUID несколько раз в секунду, и всё это летит в Redis, которые грузит эти данные в Postgresql.

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

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

Удобно, а?

Но, как же это работает?

Ок, в отношении самой даты — тут всё просто. Запишите число, как unix timestamp и у вас есть что-то бинарно-сортируемое. Только я вас прошу, не стоит записывать эту дату кусками, в разнобой. Просто и понятно, первые 36 битов содержат в себе одно число. Но, если вы пытаетесь записать миллисекунды, то всё становится сложнее.

Давайте поговорим о математике. О приближении и лимитах. Любимая тема, а? Давайте посмотрим на следующую запись секунды: 05,625. Пять целых, шестьсот двадцать пять секунд. Отбрасываем 5, поскольку это будет записано в unix timestamp.

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

Достаточно, просто, правда? Если сложить все числа в этом ряду, то вы получите единицу. А что если складывать не каждый? Ну, с этим можно что-то сделать. Давайте присвоим каждому числу из этого ряда один бит. Каждый бит будет показывать, если этот член присутствует в ряду или нет.

Берём нашу суб-секундную точность, 0,625 и начинаем записывать эту точность с помощью битов.

Первое число 1/2, то есть 0,5. Если наше значение точности больше этого числа, то выставляем битовое значение в 1 и вычитаем это число из нашего текущего значения точности. В итоге получаем, битовую последовательность 1 и 0,125 в остатке.

Смотрим дальше 1/4, 0,25, однозначно больше чем 0,125. Соответственно, последовательность превращается в 10 и мы идём смотреть дальше. Продолжаем в том же духе, и выясняем, что для того, чтобы записать 0,625 в бинарном формате таким образом, нам надо написать: 101, поскольку

Что самое приятное, в этой системе, так это то, что если вы урезаете количество бит с конца, то вы будете терять точность, но всё-же сохраните более или менее приближенное значение.

Значение сохраняется, и при этом, вы можете играть с количеством битов, которые вы расходуете на его запись. И — что самое главное — подобная запись производит бинарно-сортируемые значения.

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

bits = 12 
fraction = 0.321 
subsec = round(fraction * 2**bits)

Ну и, понятное дело, для того, чтобы раскодировать, нужно сделать обратное.

bits = 12
subsec = 1315
fraction = round(subsec / 2**bits, 3)

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

А в случае коллизий?

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

Для этого стандарт предусматривает наличие счётчика произвольной длинны, который должен монотонно увеличиваться, если даты совпадают.

И в дополнение, можно задать произвольное количество битов, которые будут идентифицировать компьютер, сгенерировавший значение. (Записывать MAC адрес в это поле не стоит, ибо уж слишком часто это вызывало вопросы с точки зрения безопасности).

Плюс, всё пространство, которое не используется для времени, счётчика и номера компьютера (порядка 54х бит) необходимо заполнять случайными значениями для предотвращения каких-либо совпадений на разных узлах.

Итого:

Как это выглядит в итоге:

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                            unixts                             |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|unixts |       subsec_a        |  ver  |       subsec_b        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|var|                   subsec_seq_node                         |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                       subsec_seq_node                         |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Вот пример того, как данные записываются в UUIDv7.

Поля ver и var сохранены для совместимости с другими версиями идентификаторов (см. уже упомянутую статью ^[2]).

Первые 36 бит занимает unix timestamp, что позволяет хранить даты до 4147-08-20 07:32:15 +0000 UTC. Очень надеюсь, что этого хватит, для текущих проектов. Данные в остальных полях могут заполняться суб-секундной точностью, данными о номере узла и счетчиком.

На данный момент количество битов, задействованное для сохранения суб-секундной точности, номера узла и счётчика, не определены стандартом. С точки зрения базы данных, эта информация не является особо важной. Идентификатор будет выглядеть как любой нормальный идентификатор и вы сможете использовать его везде, где используются подобные UUID. А если вы знаете изначальные значения чисел, которые вы использовали при создании идентификатора, вы сможете распарсить эти значения без особых проблем.

Вот вам наглядный пример этого идентификатора:

Что я знаю о 06115aa098-9277-0087-49a8-cb901fc2f7? Всё очень просто.

• Он был создан в 2021-08-12 16:08:57 -0700 UTC-7 (с unix timestamp 1628809737)

• Наносекунды записаны как 0.535995

• Счётчик в данном случае не использовался

• Номер компьютера, который создал этот идентификатор, равняется 7.

• Последние 56 бит содержат в себе случайные данные.

Как я это знаю? Я знаю изначальную конфигурацию генератора, в которой записано, что наносекундная точность должна занимать 16 бит, счётчик — не более восьми бит, и номер узла в 6 бит, всё остальное — случайные данные. (Поля отмеченные красным цветом - это ver и var, которые сохранены для обратной совместимости)

Более того, я знаю, что 06115ad596-0873-0087-5764-c1f3730d90 был создан позже, чем 06115aa098-9277-0087-49a8-cb901fc2f7, поскольку 06115ad больше, чем 06115aa. Чтобы мне это знать, мне даже не надо морочить голову с парсингом.

Почему же версия 7, а не 6?

На самом деле документ описывает три версии новых идентификаторов. 6, 7 и 8. Версия шесть обратно-совместима с версией 4, и сохраняет дату в старом формате. Версия 8 зарезервирована для тех панков, которым всё нужно делать по-своему, и не содержит в себе большого количества ограничений.

И что мне с этим делать?

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

На данный момент мы обсуждаем следующий вопрос: "Стоит ли фиксировать количество битов для суб-секундной точности в стандарте, или пусть программисты разбираются? ^[24]"

Далее, если у тебя руки чешутся, то здесь ^[25] можно посмотреть готовые генераторы для разных языков. (Java, Dart, Python, Golang, JS, и так далее)

Я написал свою имплементацию ^[26]на Golang. Эта очень странная версия, рассчитанная на то, что стандарт будет меняться, соответственно количество бит в каждом поле может измениться.

Более того, вот вам сайт-игрушка http://www.new-uuid.info ^[27]. Одностраничный сайт, написаный на go+WASM, который использует мой пакет для генерации этих идентификаторов онлайн. Вы можете покрутить ручки, и уяснить, куда и как будут записаны биты вашего UUID.

Короче, подключайтесь, необходимо ещё разобраться с большим количеством вопросов, и в течении следующего месяца мы будем подавать третий вариант черновика на RFC. Я думаю, что тут без Хабра не обойдётся.