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

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

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

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

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

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.

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

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

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

1. LexicalUUID by Twitter

2. Snowflake by Twitter

3. Flake by Boundary

4. ShardingID by Instagram

5. KSUID by Segment

6. Elasticflake by P. Pearcy

7. FlakeID by T. Pawlak

8. Sonyflake by Sony

9. orderedUuid by IT. Cabrera

10. COMBGUID by R.Tallent

11. ULID by A. Feerasta

12. SID by A. Chilton

13. pushID by Google

14. XID by O. Poitrey

15. ObjectID by MongoDB

16. CUID 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 сохранены для совместимости с другими версиями идентификаторов (см. уже упомянутую статью).

Первые 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 зарезервирована для тех панков, которым всё нужно делать по-своему, и не содержит в себе большого количества ограничений.

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

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

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

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

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

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

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