Пост🖥 UUID: Как создать уникальный ID без центрального сервера?

🖥 UUID: Как создать уникальный ID без центрального сервера? Начало 1980-х. Вы — разработчик в Apollo Computer. Ваша команда работает над NCS — одной из первых систем для распределённых вычислений. Вам поручили решить важную проблему: - У вас есть множество серверов в разных городах - Каждый из них может регистрировать новых пользователей - Каждому новому пользователю нужен уникальный ID во всей распределённой системе. Иначе при синхронизации или обращении по сети будет непонятно, о каком из них речь На одной машине всё просто — даём каждому объекту порядковый номер: 1, 2, 3... Но если два сервера независимо дадут номер 1 своим объектам — получим коллизию Начинаем думать. ———— Попытка 1: Центральный сервер со счётчиком Самое очевидное решение — один сервер раздаёт ID всем остальным: Машина A → Центр: "Дай ID" Центр → Машина A: "Держи ID=1" Машина B → Центр: "Дай ID" Центр → Машина B: "Держи ID=2" Выкатываем в прод. Работает идеально! Гарантированно уникальные ID, никаких коллизий. Но через неделю начинаются проблемы: - Центральный сервер упал — вся система встала - Каждый запрос ID требует сетевого обращения — медленно - При росте нагрузки центр становится узким местом Для распределённой системы, где важна автономность узлов, это не подходит. Переделываем. ———— Попытка 2: Диапазоны для каждой машины Хорошо, давайте заранее раздадим каждой машине свой диапазон ID: Машина A: ID от 1 до 1,000,000 Машина B: ID от 1,000,001 до 2,000,000 Машина C: ID от 2,000,001 до 3,000,000 Это уже лучше — каждая машина действительно автономна! Выкатываем. На первый взгляд работает. Но потом выясняется: - Машина A исчерпала свой диапазон, нужно запрашивать новый → опять зависимость от центра - Машина B создала только 10 объектов из миллиона, остальные ID потрачены впустую - Добавление новых машин требует центральной координации для выдачи диапазонов Опять возвращаемся к центральной точке отказа. Это не то. ———— Попытка 3: Составные ключи Может использовать комбинацию machine_id + local_counter? Для machine_id можно взять MAC-адрес сетевой карты — он уникален глобально. Машина A, объект 1: "A-1" Машина A, объект 2: "A-2" Машина B, объект 1: "B-1" Это уже лучше — каждая машина действительно автономна! Выкатываем.. И получаем пачку новых проблем: - Машина перезагрузилась, забыла свой счётчик — получили коллизию ID - На каждой машине нужно хранить своё состояние счётчика, это усложняет систему Попытка 4: Время + ID машины А что если вместо счётчика использовать текущее время? timestamp + MAC-адрес - Время монотонно растёт — коллизий на одной машине не будет - MAC-адрес уникален глобально — коллизий между машинами не будет - Не нужно хранить счётчик! 🟢Это уже очень близко к рабочему решению. Примерно так и работали ранние UID в Apollo Но проблемы ещё остались: что если часы на машине сбросились? Или две операции произошли в одну микросекунду? На нагруженных системах это не редкость — при тысячах запросов в секунду коллизии по времени станут регулярным явлением. ———— Как же сложно! 😩 Вы сидите, смотрите на свои наброски и думаете: может проблема в самом подходе? И тут к вам подходит коллега из команды криптографии 🎩 Вы излагаете ему свою боль, после чего он пожимает плечами и задумчиво произносит: — Слушай, а зачем тебе гарантировать уникальность на 100%? Может, сделать вероятность коллизии настолько малой, что ей можно пренебречь? ... ... ??? Интересная мысль, давайте посчитаем! Возьмём для ID 128 бит — это немного, в память влезет. Сколько это вариантов? 2^128 = 340,282,366,920,938,463,463,374,607,431,768,211,456 Это 340 ундециллионов. Число настолько огромное, что его сложно осознать. Коллега-математик, с которым вы ходите вместе обедать помогает с прочувствовать масштаб: — Представь: 10 триллионов компьютеров (это больше, чем людей на Земле) генерируют по миллиарду UUID каждую секунду. Непрерывно. В течение 100 лет. Даже в этом сценарии мы истратим меньше одной миллионной доли всех возможных комбинаций. Впечатляет! Но как быть с парадоксом дней рождения? Обсудим это далее #guide #uuid