Генератор KSUID

KSUID (K-Sortable Unique Identifier, уникальный идентификатор с сортировкой по времени) — это код длиной 27 символов, используемый для маркировки записей, таких как строки базы данных, записи журнала или запросы API. Он объединяет метку времени со случайными данными, поэтому идентификаторы, созданные позднее, всегда сортируются после идентификаторов, созданных ранее, хотя каждый из них практически уникален. Этот инструмент создаёт один KSUID в браузере и позволяет скопировать его.

Из чего состоит KSUID?

KSUID имеет длину 20 байт и состоит из двух частей:

Метка времени (4 байта): количество секунд с фиксированного начального момента, называемого эпохой KSUID.
Случайная полезная нагрузка (16 байт): данные, созданные криптографическим генератором случайных чисел браузера.

Затем эти 20 байт преобразуются в текст с помощью кодирования base62 — системы, представляющей числа с использованием 62 символов: цифр 0-9, прописных букв A–Z и строчных букв a–z. Результат всегда дополняется до длины ровно 27 символов, например 0qjBBlJIfbVLKwnJn4xpLGDr00e.

Поскольку метка времени расположена первой, два KSUID, созданные с интервалом в одну секунду, обычно сортируются в том же порядке, что и время их создания, если сравнивать их как обычный текст. Поскольку последние 16 байт являются случайными, два KSUID, созданные в одну и ту же секунду, почти наверняка будут различаться.

Эпоха KSUID

Большинство компьютерных систем отсчитывает время в секундах с 1 января 1970 г. («эпохи Unix»). В KSUID используется другая начальная точка — эпоха KSUID: 1 400 000 000 секунд после эпохи Unix, то есть 13 мая 2014 г., 16:53:20 по UTC.

Более поздняя начальная точка позволяет полю метки времени размером 4 байта охватывать больше полезных лет, прежде чем его диапазон будет исчерпан. Счётчик размером 4 байта (32 бита) может содержать не более 4 294 967 295 секунд. При отсчёте от эпохи KSUID этот период заканчивается примерно 19 июня 2150 г..

Формула KSUID

Строка KSUID создаётся в три этапа.

Найдите значение метки времени:

T = floor(current_unix_time_in_seconds) − 1,400,000,000
Сгенерируйте 16 случайных байт, R, используя криптографически стойкий генератор случайных чисел.
Объедините метку времени размером 4 байта и 16 случайных байт в один блок размером 20 байт, затем закодируйте этот блок в base62, дополнив результат до 27 символов:

KSUID = Base62( T ‖ R )

Здесь ‖ означает «разместить один за другим». Байты метки времени всегда идут первыми, благодаря чему итоговая строка правильно сортируется по времени.

Пример расчёта

Предположим, что часть метки времени KSUID равна 100000000. Поскольку эпоха KSUID наступает через 1 400 000 000 секунд после эпохи Unix, эта метка времени соответствует 14 июля 2017 г., 02:40:00 по UTC.

Если объединить эту метку времени с последовательностью из 16 байт 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16 (здесь она используется только для воспроизводимости примера; настоящий генератор использует случайные байты), кодирование base62 даёт:

0qjBBlJIfbVLKwnJn4xpLGDr00e

Эта строка содержит 27 символов и состоит только из цифр и букв, поэтому её можно напрямую использовать в URL или имени файла.

Как пользоваться инструментом генерации KSUID

Откройте страницу генератора KSUID.
Нажмите кнопку «Generate KSUID».
Инструмент создаёт один новый KSUID, используя текущее время и новые случайные байты, и отображает его на странице.
Нажмите кнопку «Copy KSUID», чтобы скопировать значение в буфер обмена.
Нажмите «Reset», чтобы очистить результат. Кнопка Reset появляется только после создания KSUID.

Каждое нажатие «Generate KSUID» создаёт ровно один идентификатор. Чтобы создать несколько KSUID, нажимайте кнопку отдельно для каждого нового идентификатора; пакетного режима или экспорта в файл в инструменте нет.

Генератор использует встроенный в современные браузеры API Web Crypto. Если этот API недоступен, инструмент выводит ошибку вместо создания идентификатора, поскольку не защищённый криптографически генератор случайных чисел может создавать идентификаторы, которые легче угадать или которые могут совпасть.

KSUID в сравнении с UUID

UUID (Universally Unique Identifier, универсальный уникальный идентификатор) — распространённый альтернативный формат идентификаторов. Наиболее широко используемая версия, UUID v4, имеет длину 36 символов и почти полностью состоит из случайных битов, поэтому по двум UUID нельзя понять, какой из них был создан первым.

KSUID отличается по трём параметрам:

Сортировка по времени. Начальные байты метки времени означают, что обычная алфавитная сортировка строк KSUID также упорядочивает их по времени создания.
Меньшая длина. KSUID содержит 27 символов, тогда как стандартный UUID — 36.
Отсутствие разделителей. UUID обычно записывается с дефисами (xxxxxxxx-xxxx-...), а в KSUID они отсутствуют.

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

Часто задаваемые вопросы

Что означает KSUID? K-Sortable Unique Identifier. Буква «K» указывает на возможность сортировки (в исходных заметках о разработке Segment, компании — создателе формата, это описано как «в некоторой степени сортируемый»).

Какова длина KSUID? 27 символов, закодированных с помощью base62 (цифры 0-9, прописные и строчные буквы).

Что такое эпоха KSUID? 13 мая 2014 г., 16:53:20 по UTC, то есть через 1 400 000 000 секунд после стандартной эпохи Unix — 1 января 1970 г..

Могут ли два KSUID совпасть? Это крайне маловероятно. Каждый KSUID содержит 16 случайных байт (128 бит), сгенерированных криптографически стойким генератором случайных чисел. Даже при создании множества KSUID в одну и ту же секунду вероятность случайного совпадения двух идентификаторов астрономически мала.

Можно ли восстановить время создания по KSUID? Да. Первые 4 байта декодированного значения содержат метку времени. Если прибавить это количество секунд к эпохе KSUID, получится исходное время создания.

Поддерживает ли этот инструмент создание нескольких KSUID одновременно? Нет. Инструмент создаёт один KSUID за каждое нажатие кнопки «Generate KSUID». Поля для указания количества, пользовательской метки времени или функции экспорта и скачивания нет.

Безопасно ли помещать KSUID в URL? Да. Кодирование base62 использует только цифры и буквы, поэтому для размещения KSUID в URL, имени файла или ключе базы данных не требуется дополнительное экранирование.

Источники

Репозиторий KSUID компании Segment на GitHub: https://github.com/segmentio/ksuid
"Generating good unique identifiers" Питера Бургона: https://peter.bourgon.org/blog/2019/05/20/generating-good-unique-ids.html

Генератор KSUID - Создание сортируемых уникальных идентификаторов