Генерация ID в распределённой системе, часть 1 Задача считает | Java: fill the gaps

Генерация ID в распределённой системе, часть 1

Задача считается сеньорной и входит в категорию system design. Вариантов решения много, и выбирать нужно с умом. Чтобы примерно сориентироваться, обозначу основные варианты и опорные точки.

Над чем подумать в самом начале:

Насколько уникальным должен быть ID?
В рамках одного сервиса
Уникальным в пределах системы в течение какого-то времени
Глобально уникальным в течение всей жизни системы

Два последних варианта влияют на длину id. Чем он короче, тем скорее наступит переполнение. Чем длиннее — тем больше памяти займёт id

Как часто нужно генерировать id?

Влияет на размер и немного на реализацию

Если сущность отдаётся за пределы системы, что видит внешний пользователь?

id как есть: /user/123
Декодированный id через Base64: /user/MTIz
Зашифрованный id: /user/67FA78

Формат

Возрастающая последовательность

Глобальный счётчик, последовательность в БД или местный AtomicLong

Случайный набор цифр

Глобально уникальный UUID или локальный Random
Самый быстрый вариант

Вариации Snowflake

Формат Snowflake придумали в Twitter. В оригинале id формируется как комбинация

timestamp + machine_id + sequence_id
(значения складываются как строки, а не как числа)

timestamp — количество миллисекунд
machine_id — id сервера
sequence_id — возрастающая последовательность

id содержит что-то полезное
Можно сортировать по полям, входящим в id
Глобальная уникальность

Machine id часто меняют на пару (id рабочей машины + id процесса) или (id датацентра + id сервера). Можно вдохновиться и составить свою комбинацию полей

Технические моменты Snowflake

Чтобы timestamp не получался слишком большим, отсчитывайте миллисекунды от какой-то даты отсчёта.

Machine id извлекается в начале работы сервиса
из распределённого счётчика. Например, из Zookeeper
из конфига, если при развёртывании ведётся счётчик

Для возрастающей последовательности подойдёт локальный AtomicLong или sequence в БД.

Генерация ID в базе данных

Часто говорят, что генерация id через БД — плохое решение. Все сущности должны проходить через один экземпляр БД, чтобы не было дубликатов, и это ограничивает масштабируемость.

В следующем посте расскажу, как решить эту проблему:)

Генерация через БД подходит, если объект и так сохраняется в базе данных. Если взаимодействий с БД нет (например, нужно id сообщения для кафки), конечно, нужны другие решения.

Как формировать Snowflake id на основе sequence в БД?

Шок контент: в хранимой процедуре. Формирование id — технический момент, а не бизнес-логика. Поэтому такое решение ок.

Как формируется UUID, может ли он повторяться?

Стандарт UUID описывает 5 стратегий генерации UUID. Метод UUID.randomUUID() использует Version 4, генерацию с помощью случайных чисел. Я тоже не доверяю случайным числам, но формулы обещают, что всё будет ок