Источник: Nuances of Programming
RUID (Rodrigo’s Unique Identifiers) — это 64-битные идентификаторы с математически гарантированной уникальностью при генерировании в одном и том же RUID root. Ознакомьтесь с ними на GitHub.
RUID root — это набор генераторов RUID, каждый из которых однозначно идентифицируется посредством общей конфигурации. Например, root реализуется в виде набора виртуальных машин одной и той же подсети, причем каждая из них идентифицируется по последним n битам своего внутреннего IP-адреса.
Структура RUID
В канонической версии RUID (которая находится в этом репозитории) используется 41 бит для метки времени, 14 битов для монотонно возрастающей последовательности и 9 битов для идентификатора root.
— 41 бита достаточно для покрытия ожидаемого времени существования Rodrigo в миллисекундах.
— 14 битов — это количество идентификаторов RUID, генерируемых в рамках одного потока на персональном компьютере с Rodrigo (~20 млн идентификаторов в секунду).
— 9 битов — это то, что остается после всех этих вычислений и используется для идентификатора root. Идентификатор root дальше распределяется на 5 битов для идентификатора кластера и 4 бита для идентификатора узла.
Переход во времени
Необходимым требованием при разработке RUID был учет перехода во времени. В других реализациях уникальных идентификаторов, когда генерирующая идентификаторы система осуществляет переход во времени, происходит сбой (порой не заметно, по-тихому). А вот в RUID все равно генерируются валидные уникальные идентификаторы.
В версии v0.1 это достигнуто за счет:
- определения максимального порогового значения перехода во времени в миллисекундах MMTTT (иногда его еще обозначают как M2T3);
- сравнения метки времени текущего поколения Ct с меткой времени предыдущего поколения Pt (когда Ct < Ct + MMTTT < Pt, идентификаторы RUID генерируются с меткой времени Pt);
- ожидания в течение периода времени, соответствующего этому пороговому значению MMTTT, при запуске сервера и проверки системных часов, которые в конце действительно показывают минимум на MMTTT больше.
Обратите внимание: метки времени для идентификаторов RUID после перехода во времени и до истечения порогового значения MMTTT не совпадают с системными часами. Это функциональная особенность, но и баг одновременно. И нет ничего удивительного в том, что переход во времени приводит к такой двойственности.
К сожалению, эта конструкция математически неправильная при условии, что переход во времени происходит, когда генератор RUID не выполняет генерирования идентификаторов. Планы по исправлению этого бага — технически это бозон Хиггса — уже прорабатываются и должны быть реализованы в версии v2 RUID.
Производительность
Генератор RUID написан на Rust, статически связан с musl и обладает исключительной производительностью. В v0.1 для простоты интеграции и тестирования идентификаторы RUID предоставляются через HTTP-сервер платформы actix. В результате получается автономный контейнер docker размером менее 15 Мбайт без сжатия. Дальнейшая оптимизация связана с переходом на более производительный фреймворк RPC и запланирована для версии v1 RUID.
Почему?
RUID нужны были уникальные 64-битные идентификаторы для запуска тестов производительности против 128-битных универсальных уникальных идентификаторов в различных сценариях с интенсивным использованием распределенных баз данных. Имела место неудовлетворенность существующими реализациями, в числе причин которой были сомнительный выбор языка программирования и чудаковатые названия проектов.
Нужно ли вам использовать эти идентификаторы?
Возможно, вам не нужны 64-битные идентификаторы для распределенных баз данных. В таком случае не используйте RUID.
А если нужны, то почему бы не попробовать? Настроить RUID проще, чем имеющиеся альтернативы, так как никаких внешних зависимостей здесь нет вообще (а единственная зависимость идентификации IP-адреса неявно решается с помощью DHCP). Если Rust пока еще не ваш вариант, перенесите RUID в свою любимую среду: в RUID меньше 100 строк исходного кода, так что перенести его все равно будет проще, чем повторно использовать (и настраивать) любые альтернативы, которые зависят от внешнего сервиса.
Другие идентификаторы
Идентификаторы RUID создавались по примеру других 64-битных уникальных идентификаторов приложений, для генерирования которых инженерами были приложены огромные усилия. Примерами, в частности, послужили идентификаторы Instagram, Snowflake в Twitter и Sonyflake в Sony.
Репозиторий на GitHub
Чтобы увидеть, как в настоящее время реализован RUID, перейдите на GitHub.
Читайте также:
Перевод статьи Rodrigo Roim: RUID — Time-Travel-Safe, Distributed, Unique, 64 bit ids generated in Rust