Вчера я баловался с проектом API, которым занимаюсь уже долгое время. Подобные проекты мы обычно переписываем снова и снова на протяжении многих лет, чтобы поддерживать высокий уровень дофамина от рефакторинга. Вы понимаете, о чём я. На этот раз совершенно внезапно я кое-что осознал. Мне нужно отрефакторить одну вещь. Я достаточно активно пользуюсь UUID, поэтому URL моих ресурсов очень длинные и некрасивые.

В зависимости от версии и варианта в UUID есть множество разной информации, но по большей мере это куча случайных битов, которые и обеспечивают свойство «универсальной уникальности», которое нам так нравится. Но если по какой-то причине вам не нравится проверенный временем стандарт с огромной экосистемой нативной поддержки... то эта статья для вас!

Что же это такое?

Позвольте мне без лишних слов представить вам dotvezz/smolid. Это реализованная на Go схема ID, обеспечивающая очень полезные свойства! Пример того, как выглядит smolid: acpje64aeyez6. Он…

• удобен для URL: короткий и ненапряжный в своей используемой по умолчанию кодировке base32 без заполнителей

• упорядочен по времени с высокой локальностью индексов базы данных

  • как и UUIDv6/7!

• он достаточно быстр и уникален во многих сценариях использования

• позволяет встраивать id простых типов

  • Запомните это, мы вскоре к этому вернёмсяlater.

  • (Хочу посвятить этому целый раздел, чтобы можно было пожаловаться на небольшое неудобство)

И всё это помещается в 8 байт! На Go всё это хранится в одном uint64! В столбец Postgres bigint* можно уместить много полезного!

* Это намёк. Начислю вам бонусные очки, если вы уже догадались о проблеме, которую моя дурная голова не видела, пока я не начал хвастаться перед друзьями.

Подробности реализации

При располовинивании UUID* придётся пойти на жертвы. Самая важная из них заключается в существенном снижении энтропии, поэтому глобальной уникальности никто обещать не может. Встроенная временная метка сильно помогает в предполагаемых сценариях применения API, и в некоторых случаях smolid имеет 13-20 бит энтропии поверх временной метки. Я назвал его «достаточно уникальным», но у него обнаружились серьёзные недостатки, о которых я расскажу позже.

* Помните, что UUID имеет длину всего 16 байт. В строковом виде он выглядит очень длинным из-за шестнадцатеричного кодирования.

Давайте разберём все 64 бита нашего 8-байтного ID!

 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
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|                          time_high                            |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|    time_low     |ver|t| rand  | type or rand|       rand      |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

• Временная метка (41 бит): старший 41 бит, описывающий временную метку с миллисекундной точностью

  • Допустимый диапазон временных меток: с 2025-01-01 00:00:00 по 2094-09-07 15:47:35

• Версия (2 бита): биты 41-42 зарезервированы под версию.

  • v1 — это 01

• Флаг типа (1 бит): бит 43 используется в качестве булева флага. Если он установлен, поле «Type/Rand» — это встроенный идентификатор типа.

• Случайная часть (4 бита): оставшиеся 4 бита 6-го байта заполнены псевдослучайными данными.

• Тип/случайные данные (7 бит): если флаг типа установлен, это поле содержит идентификатор типа. В противном случае он заполняется псевдослучайными данными.

• Случайная часть (9 бит): оставшийся байт заполнен псевдослучайными данными, обеспечивающими достаточную уникальность.

Своя эпоха и 41-битная временная метка (намеренный отказ от решения самой важной решённой проблемы)

Одним из лучших событий в восхитительном мире идентификаторов объектов стал RFC 9562, ратифицированный в середине 2024 года: в нём появились UUIDv6 и v7. Оба они нативно сортируемы по времени. но делается это немного по-разному…

• UUIDv6:

  • 60 бит выделено на временную метку

  • Григорианская эпоха

  • 100-наносекундная точность

  • Диапазон допустимых временных меток: с 1582-10-15 00:00:00 до 5236-03-3 21:21:00

• UUIDv7:

  • 48 бит выделено на временную метку

  • Эпоха Unix

  • Миллисекундная точность

  • Диапазон допустимых временных меток: с 1970-01-01 00:00:00 до 10889-08-02 05:31:50

В RFC есть отличный раздел, полностью посвящённый вопросам временных меток; рекомендую прочитать его!

Когда я примерно четыре часа назад начал работать над smolid, одной из первых сложностей стал поиск баланса между полезностью временных меток. версионностью, функциональностью и энтропией. Мне очень хотелось сохранить миллисекундную точность временных меток, но 48 бит отъедали три четверти от моего 64-битного бюджета. Возможно, вы слышали о проблеме 2038 года. И я тоже! Я даже слышал, что её называют «хорошей проблемой». Если 32-битная система выживала так долго, что переполниться в 2038 году, должно быть, она довольно сильна.

Если уж она достаточно хороша для этой системы, то хороша и для меня! Поэтому позвольте мне представить эпоху smolid: миллисекунды с 2025-01-01. Имея в запасе 41 бит, она переполнится ровно 2094-09-07 в 15:47:35. На мой взгляд, это достаточно неплохо, но могу представить, что эта проблема (наряду со многими другими) помешает вам использовать smolid.

Кстати, помните, я говорил, что всё это удобно помещается в Postgres bigint и добавил зловещий символ «*»? Что ж, оказывается, стандарт ISO/IEC SQL не определяет беззнаковые integer, и PostgreSQL действительно их не поддерживает! Поэтому потрясающая локальность индексов базы данных, которой я хвастался, теряется, когда старшие биты меняются 2059-11-04 в 19:53:47

Оставлю эту проблему проекту PostgreSQL или ISO/IEC для решения до 2059 года.

Всего 2 бита на версию?

Сфера применения моего id достаточно узка, поэтому я вполне уверен, что мне никогда не придётся увеличивать версию выше v3. Но есть придётся, то я полностью заслуживаю те мучения, которые станут результатом моего решения.

Встроенные идентификаторы типов

Когда я размышлял о том, сколько байтов выделить под каждый элемент, то вспомнил о небольшом неудобстве, которое сильно меня раздражает. Очень часто мои коллеги присылают мне просьбы вида: «Бен, можешь дать мне информацию по этому ID?» и копипастят 9f3ac7ee-e5de-4cdf-b08d-f68cbe7f1d56, как будто я должен знать, что это такое. Это ID пользователя? ID способа оплаты? ID узла? ID запроса? Он вообще поступает из нашей сети? Часто просящий неспособен предоставить никакой другой информации, кроме «я увидел его в логе ошибок и подумал, что ты сможешь помочь».

Такое случается только со мной?

Как бы то ни было, я решил выделить достаточное количество битов, чтобы при этом не очень сильно снизить энтропию. В v1 выделено 7 бит, что позволяет встраивать в ID 128 типов. Это значит, что если вы используете эту фичу, сам ID сообщит, что это ID пользователя, ID устройства, ID файла или чего-то ещё в вашей системе (по крайней мере, если у вас меньше, чем 128 уникальных типов с ID).

«Достаточно уникальный» для многих сценариев использования

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

Так как присутствует компонент временной метки с миллисекундной точностью, то есть хотя бы шанс*, что у нас никогда не возникнет риска коллизий с другим ID, созданным позже или раньше более чем на 0,001 секунды (до 2094 года). В базе данных могут быть сотни миллионов пользователей, миллиарды постов и десятки миллиардов комментариев к постам и в среднем примерно одна новая запись каждую миллисекунду. При таком масштабе smolid номинально сможет обеспечивать уникальность благодаря одной только временной метке.

* Если считать, что часы системы, генерирующей эти ID, надёжны, что не гарантировано.

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

Вероятность коллизии в процентах посчитать довольно просто.

• Размер пространства ключей: 

• Частота генерации чисел в миллисекунду: 

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

Как же это будет выглядеть без встроенных типов (в нашем наилучшем сценарии) при 100 запросах в миллисекунду в течение одной секунды? Мы можем подставить переменные и скомбинировать два уравнения. Также я сократил , но больше не вносил никаких других упрощений.

Ура, вероятность коллизии 99,1% при обработке сотни тысяч новых ID в секунду. Дело плохо!

Мне очень нравится развлекаться с тегом <math> , а сравнения полезны, поэтому давайте посмотрим, что там дадут 74 бита энтропии UUIDv7. К счастью, временная метка UUIDv7 тоже имеет миллисекундную точность, из-за чего мы можем сравнивать напрямую, не меняя базовых допущений.

Отлично, 2⋅10-14%. Вероятность коллизии 0,000000000000002% после генерации сотни тысяч ID в секунду. Ноль, запятая, четырнадцать нулей и два процента. И это жертва, на которую я пошёл, урезав всего восемь байтов на запись, чтобы получить красивые URL. Как я и говорил, ухудшил UUID по ничтожнейшей из причин.

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

Как это выглядит на практике?

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

• Marshaler и Unmarshaler из encoding/json

• TextMarshaler и TextUnmarshaler из encoding

• Valuer из database/sql/driver и Scanner из database/sql

А если вы считаете, что имеет смысл расширить поддержку, то киньте PR или issue в github!

Вот простой пример на Go, демонстрирующий использование smolid с ID встроенного типа.

package blog

import (
	"context"

	"github.com/dotvezz/smolid"
)

const (
	TypeUser = iota
	TypePost
	TypeComment
	// . . .
)

type User struct {
	ID    smolid.ID
	Name  string
	Email string
}

// CreateUser
func CreateUser(ctx context.Context, u User) (User, error) {
	u.ID = smolid.NewWithType(TypeUser)
	
	query := `insert into users (id, name, email) values ($1, $2, $3)`
	
	_, err := pool.Exec(ctx, query, u.ID, u.Name, u.Email)
	
	return u, err
}

Постараюсь заранее ответить на возникающие вопросы

Вопрос: У тебя как там, нормально вообще всё?

Учитывая всё написанное, это вполне естественная реакция. Да, думаю, вполне! Спасибо, что беспокоитесь.

Вопрос: Ты реально собираешься этим пользоваться?

Ещё как! Это решает реальные (хоть и ничтожнейшие, что я признал в заголовке поста) проблемы в моих проектах. Я не буду заставлять пользоваться этим ID коллег на работе, но во многих моих личных проектах он действительно заменит gofrs/uuid.

Надеюсь, мне не придётся писать новый пост «Ухудшенный UUID оказался ошибкой». Время покажет.

Вопрос: Стоит ли мне этим пользоваться?

Если вам подходит, то почему бы и нет? У UUID есть множество вполне реальных и важных преимуществ, которые полезны для вас, пусть даже вы этого и не осознаёте. Поэкспериментируйте со smolid! Если это вдохновит вас, то можете попробовать придумать собственную схему ID для обучения и развлечения!

Вопрос: Напишешь ли ты расширение PostgreSQL, добавляющее нативную поддержку этого нового типа?

Возможно, но, скорее всего, нет.