Генератор уникальных ID в распределённой системе: UUID v4 и v7, Snowflake и сегменты

Как генерировать уникальные ID без одной базы: автоинкремент, UUID v4 и v7, Snowflake, сегменты из БД. Формат по битам, сортируемость, коллизии, откат часов и код на Python.

19 мин чтениясистемный дизайн · распределённые системы · базы данных · собеседования

Коротко

СпособРазмерСортируется по времениКоординацияГлавный минус
Автоинкремент в одной БД64 битадаодна база на всехузкое место и точка отказа
Автоинкремент с шагом (Flickr)64 битапримерноN баз, настроенных заранеетрудно добавить узел
UUIDv4128 битнетне нужнаслучайные вставки в индекс, длинный
UUIDv7128 битда, с точностью до мсне нужнадлинный, в ID видно время создания
Snowflake64 битада, с точностью до мсуникальный номер узлазависит от часов, нужен реестр номеров
Сегменты из БД (Leaf)64 битатолько внутри узлаБД раз в N тысяч IDдыры в нумерации, нет порядка между узлами
  • Если не знаете, что выбрать для первичного ключа в новой системе, берите UUIDv7: генерируется где угодно, сортируется по времени и хорошо ведёт себя в B-дереве.
  • Если нужен компактный 64-битный ключ и вы готовы раздавать номера узлам — Snowflake.
  • Если ID должны быть плотными числами (номер заказа), но без запроса в базу на каждый — сегменты.

Задача «спроектируйте генератор ID» встречается на собеседованиях и сама по себе, и как подзадача в любом большом дизайне: лента новостей, чат, шардированная база. Ниже — все варианты по порядку, с форматом по битам и кодом.

Требования

Начните с вопросов. От ответов зависит, какой из вариантов подойдёт.

ВопросТипичный ответЧто это меняет
Уникальность глобальная или в таблице?глобальнаяавтоинкремент в каждой базе отдельно не подходит
Нужна ли сортировка по времени?да, для ленты и пагинацииUUIDv4 отпадает
Какой размер допустим?64 битаUUID отпадает, остаются Snowflake и сегменты
Сколько ID в секунду?10 тыс., в пике 100 тыс.одна база на каждый ID не выдержит или будет на пределе
Можно ли угадывать ID?нет, ID видны в URLпоследовательные номера опасны
Допустимы ли дыры в нумерации?даможно выдавать блоками и терять остатки

«Сортируется по времени» почти всегда означает примерно: ID, созданные в одну миллисекунду на разных машинах, могут лечь в любом порядке. Строгий глобальный порядок требует одной точки, и это противоречит распределённости. Проговорите это сразу.

Автоинкремент: базовая точка

BIGSERIAL в PostgreSQL или AUTO_INCREMENT в MySQL — лучший генератор, пока у вас одна база. Короткие числа, строгий порядок, ноль кода.

Проблемы начинаются с ростом:

  • Одна точка. Каждая вставка на любом сервере приложений идёт за номером в одну базу.
  • ID известен только после вставки. Нельзя сначала сгенерировать ID, отдать его клиенту и связать с ним несколько записей до коммита.
  • Шардирование. Независимые последовательности на разных шардах выдадут одинаковые номера.
  • Утечка информации. По двум номерам заказов конкурент оценит ваш оборот, а последовательные ID в URL перебираются циклом. Если проверка прав забыта, это прямой путь к утечке чужих данных.

Вариант Flickr: несколько баз с шагом

В 2010 году Flickr описал «тикет-серверы»: две базы MySQL, одна выдаёт нечётные номера, другая чётные.

-- Сервер 1 SET @@auto_increment_increment = 2; SET @@auto_increment_offset = 1; -- 1, 3, 5, ... -- Сервер 2 SET @@auto_increment_increment = 2; SET @@auto_increment_offset = 2; -- 2, 4, 6, ...

Падение одной базы не останавливает выдачу. Минусы: добавить третий сервер без перенастройки всех нельзя, а номера с разных серверов перемешиваются во времени — один сервер может уйти далеко вперёд другого.

UUID: координация не нужна

UUID — 128-битное число, которое каждый узел генерирует сам. Текущий стандарт — RFC 9562 2024 года, он заменил RFC 4122 и добавил версии 6, 7 и 8. В любой версии 4 бита отданы под номер версии и 2 бита под вариант, они стоят на фиксированных местах. Поэтому в записи xxxxxxxx-xxxx-7xxx-yxxx-xxxxxxxxxxxx первая цифра третьей группы — это версия.

UUIDv4

Всё, кроме этих 6 служебных бит, случайно: 122 бита из криптостойкого генератора.

Насколько реальна коллизия? Парадокс дней рождения: при nn значениях из пространства NN вероятность хотя бы одного совпадения

p≈1−e−n2/2N,N=2122p \approx 1 - e^{-n^2 / 2N}, \quad N = 2^{122}

import math BITS = 122 # случайных бит в UUIDv4 space = 2**BITS def p_collision(n: int) -> float: # парадокс дней рождения: p ≈ 1 - exp(-n² / 2N) return -math.expm1(-n * n / (2 * space)) def n_for(p: float) -> float: return math.sqrt(2 * space * -math.log1p(-p)) print(f"{n_for(0.5):.2e}") # 2.71e+18 UUID до 50% шанса коллизии print(f"{n_for(1e-9):.2e}") # 1.03e+14 UUID до шанса один на миллиард print(f"{p_collision(10**12):.1e}") # 9.4e-14 для триллиона UUID print(n_for(0.5) / 1e9 / 86400 / 365) # 86.08... лет при миллиарде UUID в секунду

expm1 и log1p здесь не для красоты: при таких маленьких вероятностях 1 - math.exp(-x) возвращает ровно ноль из-за округления.

Вывод: математически коллизий v4 можно не бояться. На практике их видели, но причина всегда в плохом источнике случайности: одинаковое зерно генератора после клонирования виртуальной машины, Math.random() вместо криптостойкого генератора. Поэтому уникальный индекс в базе всё равно оставляют, а ошибку вставки обрабатывают повтором.

Настоящая проблема v4 — случайный порядок. Первичный ключ в PostgreSQL и MySQL хранится в B-дереве. Последовательные ключи дописываются в правый край, и горячие страницы индекса живут в памяти. Случайные ключи попадают в произвольные листья: страницы читаются с диска, делятся пополам, индекс распухает. На больших таблицах вставка заметно замедляется. Механика подробно разобрана в статье про B-дерево и статье про индексы.

UUIDv7

v7 решает именно это. Раскладка по RFC 9562:

БитыПолеЧто внутри
48unix_ts_msмиллисекунды с 1 января 1970 по UTC
4ver0111, то есть 7
12rand_aслучайные биты или счётчик
2var10
62rand_bслучайные биты

Время стоит в старших битах, поэтому ID, созданные позже, больше и как числа, и как строки. В индекс они дописываются почти в конец, как автоинкремент. 48 бит миллисекунд хватит примерно до 10889 года.

Внутри одной миллисекунды порядок не гарантирован, если все 74 оставшихся бита случайны. RFC предлагает три способа сделать генератор монотонным: отдать часть бит под счётчик, увеличивать случайную часть на случайный шаг или добавить биты более точного времени. Python 3.14 в uuid.uuid7() использует 42-битный счётчик, PostgreSQL 18 во встроенной uuidv7() — 12 бит дробной части миллисекунды.

Если у вас Python до 3.14, генератор пишется за пару десятков строк:

import os import time import uuid class UUID7: """UUIDv7 по RFC 9562: 48 бит времени в мс, 12 бит счётчика, 62 случайных бита.""" def __init__(self): self.last_ms = -1 self.counter = 0 def __call__(self) -> uuid.UUID: ms = time.time_ns() // 1_000_000 if ms > self.last_ms: self.counter = int.from_bytes(os.urandom(2)) & 0x7FF # старт со случайного места, старший бит 0 — запас else: ms = self.last_ms # та же миллисекунда или часы откатились self.counter += 1 if self.counter > 0xFFF: # счётчик переполнен: занимаем следующую мс ms += 1 self.counter = 0 self.last_ms = ms rand_b = int.from_bytes(os.urandom(8)) & ((1 << 62) - 1) value = ms << 80 | 0x7 << 76 | self.counter << 64 | 0b10 << 62 | rand_b return uuid.UUID(int=value) def uuid7_time_ms(u: uuid.UUID) -> int: return u.int >> 80 new_id = UUID7() ids = [new_id() for _ in range(100_000)] u = ids[0] print(u, u.version, u.variant == uuid.RFC_4122) # 01a1b531-db91-749c-... 7 True print(ids == sorted(ids), len(set(ids))) # True 100000 print(abs(uuid7_time_ms(u) - time.time_ns() // 1_000_000) < 5_000) # True

Разберём решения в коде:

  • Счётчик стартует со случайного значения, но со старшим битом 0. Так ID не начинаются каждую миллисекунду с одинакового 000, и при этом остаётся запас минимум в 2048 значений до переполнения.
  • Откат часов обрабатывается так же, как та же миллисекунда: продолжаем на последнем известном времени. Порядок внутри процесса сохраняется.
  • Переполнение счётчика переносит нас в следующую миллисекунду раньше реального времени. RFC это разрешает. Для 4096 ID за миллисекунду из одного процесса нужно больше 4 млн ID в секунду, так что на практике это редкость.
  • int.from_bytes без указания порядка байт работает с Python 3.11. В более ранних версиях допишите "big".

Монотонность гарантирована только внутри одного генератора. Два процесса в одну миллисекунду выдадут ID в произвольном порядке, и это нормально.

Минусы v7. 16 байт против 8 у BIGINT: первичный ключ и все внешние ключи на него вдвое толще. 36 символов в URL. И в каждом ID видно время создания: если по ID пользователя нельзя узнавать дату регистрации, v7 не подходит, наружу отдают отдельный случайный идентификатор.

Другие форматы того же семейства

  • ULID — те же 48 бит миллисекунд плюс 80 случайных бит, записанные 26 символами в base32 Крокфорда. Появился раньше v7 и решал ту же задачу. Для новых систем v7 удобнее: это обычный UUID, и база хранит его в родном типе.
  • MongoDB ObjectId — 12 байт: 4 байта времени в секундах, 5 случайных байт на процесс, 3 байта счётчика. Сортируется по секундам.

Snowflake: 64 бита и номер машины

Twitter анонсировал Snowflake в 2010 году, когда переезжал с MySQL на Cassandra и потерял автоинкремент. Требования были жёсткими: 64 бита, примерная сортировка по времени, десятки тысяч ID в секунду без координации на каждый.

БитыПолеСмысл
1знаквсегда 0, чтобы число было положительным int64
41времямиллисекунды от своей эпохи
10номер узладо 1024 генераторов; Twitter делил на 5 + 5 бит: дата-центр и машина
12счётчикдо 4096 ID за миллисекунду на узел

Что следует из раскладки:

  • 41 бит миллисекунд — это 69,7 года. Поэтому отсчёт ведут не от 1970 года, а от своей эпохи. У Twitter это 1288834974657, 4 ноября 2010 года, значит, ID кончатся около 2080-го.
  • Пропускная способность: 4096 ID за миллисекунду, это около 4 млн в секунду на узел.
  • Уникальность держится на номере узла. Два узла с одинаковым номером выдадут дубли. Это главная операционная проблема Snowflake.
import threading import time EPOCH_MS = 1288834974657 # эпоха Twitter: 4 ноября 2010 WORKER_BITS, SEQ_BITS = 10, 12 MAX_WORKER = (1 << WORKER_BITS) - 1 # 1023 MAX_SEQ = (1 << SEQ_BITS) - 1 # 4095 class Snowflake: def __init__(self, worker_id: int, clock=lambda: time.time_ns() // 1_000_000): if not 0 <= worker_id <= MAX_WORKER: raise ValueError("worker_id must be in [0, 1023]") self.worker_id = worker_id self.clock = clock self.last_ms = -1 self.seq = 0 self.lock = threading.Lock() def next_id(self) -> int: with self.lock: now = self.clock() if now < self.last_ms: if self.last_ms - now > 5: # часы ушли назад сильно: лучше упасть raise RuntimeError(f"clock moved back by {self.last_ms - now} ms") now = self.last_ms # мелкий откат: живём на старом времени if now == self.last_ms: self.seq = (self.seq + 1) & MAX_SEQ if self.seq == 0: # 4096 ID за миллисекунду кончились while now <= self.last_ms: now = self.clock() else: self.seq = 0 self.last_ms = now return (now - EPOCH_MS) << (WORKER_BITS + SEQ_BITS) | self.worker_id << SEQ_BITS | self.seq def parse(snowflake_id: int) -> dict: return { "unix_ms": (snowflake_id >> (WORKER_BITS + SEQ_BITS)) + EPOCH_MS, "worker": snowflake_id >> SEQ_BITS & MAX_WORKER, "seq": snowflake_id & MAX_SEQ, } gen = Snowflake(worker_id=7) ids = [gen.next_id() for _ in range(10_000)] print(ids == sorted(ids), len(set(ids))) # True 10000 print(parse(ids[0])["worker"], ids[0].bit_length() <= 63) # 7 True print(parse(1888944671579078978)) # реальный ID поста в X # {'unix_ms': 1739194479256, 'worker': 360, 'seq': 322}

Последняя строка разбирает настоящий ID: время 1739194479256 — это 10 февраля 2025 года, 13:34:39.256 UTC, узел 360, и в ту миллисекунду он уже выдал 322 ID до этого.

Откат часов

Snowflake верит часам. А часы на серверах ходят назад: NTP подводит их, виртуальную машину мигрируют на другой хост, кто-то правит время руками. Если время ушло назад, а счётчик сброшен, генератор повторит уже выданные ID.

Варианты реакции:

  1. Мелкий откат — несколько миллисекунд — пережидаем или, как в коде выше, продолжаем на последнем известном времени.
  2. Крупный откат — отказываемся выдавать ID и снимаем узел с балансировки. Дубль хуже, чем недоступность одного генератора из многих.
  3. Профилактика: настраивают NTP на плавную подстройку (slew) вместо скачков и при старте сверяют время с последним выданным ID, сохранённым на диске.

Проверим поведение на поддельных часах:

# Продолжение: Snowflake, EPOCH_MS и parse из кода выше ticks = iter([EPOCH_MS + 100, EPOCH_MS + 100, EPOCH_MS + 98, EPOCH_MS + 50]) g = Snowflake(worker_id=1, clock=lambda: next(ticks)) a, b, c = g.next_id(), g.next_id(), g.next_id() # третий вызов: часы откатились на 2 мс print(a < b < c, parse(c)) # True {'unix_ms': 1288834974757, 'worker': 1, 'seq': 2} try: g.next_id() # откат на 50 мс except RuntimeError as e: print(e) # clock moved back by 50 ms

Откуда узлу взять номер

10 бит — это 1024 номера на весь кластер, и раздать их надо без пересечений:

  • Конфиг или порядковый номер пода. В Kubernetes у StatefulSet есть стабильные номера app-0, app-1. Просто, но подходит только для фиксированного набора машин.
  • Координатор. Twitter использовал ZooKeeper. Узел при старте занимает свободный номер как эфемерную запись, она исчезает, когда узел умирает.
  • Аренда в базе или etcd. Узел берёт номер с TTL и продлевает его. Если продлить не удалось, узел перестаёт выдавать ID раньше, чем номер может достаться другому. Те же рассуждения про аренду, что и в статье про распределённые блокировки.

Номер нельзя выдавать повторно сразу после смерти узла: если у старого владельца часы спешили, новый может догнать его ID. Безопасно выждать время, на которое часы могли разойтись.

Как искать по времени

ID упорядочены по времени, значит, по ним можно резать диапазоны без отдельного индекса по дате. Нижняя граница для момента tt — это ID с нулевыми номером узла и счётчиком:

from bisect import bisect_left # EPOCH_MS, WORKER_BITS, SEQ_BITS — из кода Snowflake выше def min_id_at(unix_ms: int) -> int: """Самый маленький Snowflake ID, который мог появиться в момент unix_ms.""" return (unix_ms - EPOCH_MS) << (WORKER_BITS + SEQ_BITS) ms = 1739194479256 ids = sorted([1888944671579078978, min_id_at(ms - 60_000) + 5, min_id_at(ms + 60_000) + 9]) start = bisect_left(ids, min_id_at(ms)) end = bisect_left(ids, min_id_at(ms + 1)) print(ids[start:end]) # [1888944671579078978] — только ID из этой миллисекунды

В базе это запрос WHERE id >= :from AND id < :to по первичному ключу. Тот же приём даёт курсорную пагинацию ленты: «дай 20 записей с ID меньше последнего виденного». Под капотом — бинарный поиск по отсортированным ключам.

Ловушка с JavaScript

64-битное число не помещается в Number: точных целых там только до 2532^{53}.

const o = JSON.parse('{"id": 1888944671579078978}') console.log(o.id) // 1888944671579079000 — последние цифры потеряны console.log(Number.isSafeInteger(o.id)) // false

Поэтому API Twitter отдавал рядом с id строковое поле id_str. Если ваши ID уходят в браузер, сериализуйте их строкой.

Вариант Instagram

Instagram в 2012 году взял идею Snowflake, но не стал поднимать отдельный сервис. Раскладка: 41 бит времени, 13 бит логического шарда, 10 бит последовательности. ID генерирует функция на PL/pgSQL прямо в PostgreSQL как значение по умолчанию для колонки. Номер шарда внутри ID сразу говорит, где лежит запись, и маршрутизатору не нужен отдельный справочник.

Сегменты: БД раз в тысячу ID

Если нужны плотные числа — номера заказов, счетов, — а в базу за каждым ходить дорого, используют выдачу диапазонами. Схема описана у многих компаний, самая известная реализация — Leaf от Meituan.

Таблица хранит для каждого типа ID последний выданный номер и размер шага. Сервер одним атомарным UPDATE забирает себе диапазон и раздаёт его из памяти.

import sqlite3 db = sqlite3.connect(":memory:", isolation_level=None) db.execute("CREATE TABLE id_alloc (biz_tag TEXT PRIMARY KEY, max_id INTEGER NOT NULL, step INTEGER NOT NULL)") db.execute("INSERT INTO id_alloc VALUES ('order', 0, 1000)") def take_segment(tag: str) -> range: """Атомарно сдвигаем max_id на step и получаем свой диапазон.""" max_id, step = db.execute( "UPDATE id_alloc SET max_id = max_id + step WHERE biz_tag = ? RETURNING max_id, step", (tag,) ).fetchone() return range(max_id - step + 1, max_id + 1) class SegmentIds: def __init__(self, tag: str, prefetch_at: float = 0.1): self.tag = tag self.prefetch_at = prefetch_at # когда израсходовали 10% — готовим следующий self.current = iter(take_segment(tag)) self.size = self.left = 1000 self.next_segment = None self.db_calls = 1 def next_id(self) -> int: if self.next_segment is None and self.left <= self.size * (1 - self.prefetch_at): self.next_segment = take_segment(self.tag) # в проде — в фоновом потоке self.db_calls += 1 if self.left == 0: self.current, self.size = iter(self.next_segment), len(self.next_segment) self.left, self.next_segment = self.size, None self.left -= 1 return next(self.current) a, b = SegmentIds("order"), SegmentIds("order") # два сервера ids_a = [a.next_id() for _ in range(1500)] ids_b = [b.next_id() for _ in range(500)] print(ids_a[:3], ids_b[:3]) # [1, 2, 3] [1001, 1002, 1003] print(len(set(ids_a) | set(ids_b)), a.db_calls, b.db_calls) # 2000 3 2

RETURNING в SQLite есть с версии 3.35. В PostgreSQL запрос тот же, в MySQL UPDATE и SELECT делают в одной транзакции.

Что здесь важно:

  • Двойной буфер. Следующий сегмент забирается заранее, когда текущий израсходован на 10%. Если база на минуту недоступна, сервер продолжает выдавать ID из запаса. Размер шага подбирают так, чтобы сегмента хватало на несколько минут пикового трафика.
  • Нагрузка на базу падает в step раз. При шаге 1000 и 100 тыс. ID в секунду база получает 100 запросов в секунду на весь кластер.
  • Дыры. Сервер упал — остаток его сегмента потерян навсегда. Для номеров заказов обычно не страшно. Для бухгалтерских документов, где нумерация обязана быть сплошной, этот способ не годится.
  • Порядок только внутри сервера. В примере сервер a выдаёт 1, 2, 3, а b в то же время — 1001, 1002. Заказ с номером 1001 может оказаться старше заказа 500.
  • База остаётся точкой отказа, просто отложенной на время буфера. Её реплицируют, как любую критичную базу.

Как выбрать

НужноБерите
Одна база, нет планов шардироватьавтоинкремент
Ключ для новой системы, генерация где угодноUUIDv7
Публичный токен, по которому ничего нельзя понятьUUIDv4 или случайные 128 бит
Компактный 64-битный ключ, сортировка по времениSnowflake или его вариант
Номер шарда внутри IDSnowflake с полем шарда, как у Instagram
Плотные короткие номера для людейсегменты из БД
Короткий ключ для ссылкисчётчик и base62, как в сокращателе ссылок

Частый ответ на собеседовании: «внутренний первичный ключ — UUIDv7 или Snowflake, наружу — отдельный непрозрачный идентификатор». Так и порядок в индексе сохраняется, и бизнес-метрики не утекают через URL.

Вопросы вглубь

  • Как убедиться, что дублей нет? Уникальный индекс в хранилище остаётся последней линией обороны. Генератор может ошибиться из-за бага, часов или повторно выданного номера узла, а индекс — нет. Дубль при вставке ловится как ошибка, ID перевыпускается.
  • Почему не взять хеш от содержимого? Хеш одинаков для одинакового содержимого, а две разные записи с одинаковыми полями — нормальная ситуация. Хеш подходит для ключей дедупликации, а не для ID. Близкая тема — ключи идемпотентности, которые генерирует клиент.
  • Что будет через 69 лет? Эпоха выбирается так, чтобы до переполнения было далеко, а переход на новую раскладку планируется заранее. 41 бит от 2010 года — это 2080-й.
  • Генератор как отдельный сервис или библиотека? Библиотека быстрее и не добавляет сетевой вызов, но номер узла нужно раздавать каждому процессу приложения. Сервис проще в управлении номерами, но становится зависимостью на критическом пути. Snowflake в Twitter был сервисом, Instagram встроил генерацию в базу, UUIDv7 обычно генерируют в приложении.
  • Нужна ли строгая монотонность? Почти никогда. Если кажется, что нужна, уточните: обычно достаточно монотонности внутри одного пользователя или одного чата, а это решается счётчиком в его партиции.

Типичные ошибки

  • UUIDv4 как первичный ключ большой таблицы без оценки цены случайных вставок в B-дерево.
  • Snowflake без защиты от отката часов. Работает годами, пока NTP однажды не сдвинет время назад.
  • Номер узла из конфига, скопированного на две машины. Дубли без единой ошибки в логах.
  • 64-битные ID числом в JSON. Фронтенд молча округляет их и запрашивает несуществующие записи.
  • Последовательные ID в публичных URL без проверки прав — перебор чужих данных простым циклом.
  • Обещание строгого глобального порядка. В распределённой системе без общей точки его нет.
  • Math.random() или random.random() для генерации UUID. Только криптостойкий источник: os.urandom, secrets, crypto.randomUUID().

Что запомнить

  • Три базовых подхода: одна точка выдачи (автоинкремент, сегменты), случайность (UUIDv4), время + номер узла + счётчик (Snowflake, UUIDv7).
  • Время в старших битах делает ID сортируемыми и дружелюбными к B-дереву. Цена — зависимость от часов и утечка времени создания.
  • Коллизии UUIDv4 при нормальном генераторе случайных чисел — теоретическая проблема: 50% шанс наступает на 2,7⋅10182{,}7 \cdot 10^{18} ID.
  • Snowflake: 1 + 41 + 10 + 12 бит, около 70 лет от своей эпохи, 4096 ID за миллисекунду на узел. Слабые места — откат часов и раздача номеров узлов.
  • Сегменты дают плотные числа и снижают нагрузку на базу в тысячу раз, но оставляют дыры и не упорядочены между серверами.
  • Уникальный индекс в хранилище нужен при любом генераторе.

Потренироваться в спокойной обстановке

Все задачи