Стратегии генерации surrogate keys

В уроке 2 мы установили: surrogate key — искусственный идентификатор без смысла, и он стал стандартом для primary key. Но «surrogate key» не отвечает на вопрос «откуда брать значения». Автоинкремент? Случайный UUID? Хеш от бизнес-данных? Это четыре разные стратегии, и у каждой — своя физика и свои последствия.

Сразу важная установка: это не рейтинг. Здесь нет «лучшей» стратегии, которую надо выбирать всегда. Есть trade-off матрица: каждая стратегия выигрывает по одним критериям и проигрывает по другим, и выбор зависит от того, что важно вашей системе — централизованная она или распределённая, нужна ли воспроизводимость ключа, важен ли порядок вставки для индекса. Разберём четыре стратегии по одним и тем же осям.

Оси сравнения

Чтобы сравнивать честно, зафиксируем критерии:

• Ширина — сколько байт занимает ключ. Влияет на размер индекса и скорость JOIN (последний урок модуля — про это детально).
• Монотонность — растут ли значения по возрастанию. Монотонный ключ хорошо ложится в B-tree индекс (вставки идут в конец); случайный — фрагментирует индекс.
• Распределённость генерации — можно ли генерировать ключ независимо в нескольких местах без центрального координатора.
• Воспроизводимость — можно ли получить тот же ключ повторно из тех же входных данных.
• Утечка информации — раскрывает ли ключ что-то наблюдателю (объём данных, время создания).

Стратегия 1: identity / sequence — монотонное целое

Identity (в PostgreSQL — GENERATED ... AS IDENTITY, исторически SERIAL; в MySQL — AUTO_INCREMENT) даёт ключу следующее целое из счётчика: 1, 2, 3, … Под капотом — объект sequence, который выдаёт числа по запросу.

CREATE TABLE users (
    user_id INTEGER GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
    name    TEXT NOT NULL
);
INSERT INTO users (name) VALUES ('Ann'), ('Bob');
-- user_id назначаются автоматически: 1, 2

Профиль по осям:

• Ширина: 4 байта (INTEGER) или 8 байт (BIGINT). Самый узкий вариант — это его главное преимущество.
• Монотонность: да, строго возрастает. Идеально для B-tree: новые строки добавляются в правый край индекса, фрагментации нет.
• Распределённость: нет. Sequence — централизованный счётчик. При параллельной загрузке из нескольких источников или в нескольких шардах все воркеры конкурируют за один счётчик — это узкое место и точка отказа.
• Воспроизводимость: нет. Перезагрузите данные — получите другие номера. Ключ нельзя вычислить из бизнес-данных.
• Утечка: да. Последовательные id раскрывают объём (user_id = 84217 — значит пользователей примерно столько) и позволяют перебор (/users/1, /users/2, …).

Где уместен: одна централизованная база (классический OLTP), где не нужна распределённая генерация. Самый узкий ключ, быстрейший JOIN — если ограничения по распределённости не мешают.

Стратегия 2: UUID — независимая генерация

UUID (Universally Unique Identifier) — 128-битный идентификатор, 16 байт. Его можно сгенерировать где угодно без координации: вероятность совпадения двух UUID пренебрежимо мала.

Важно: версии UUID различаются, и для ключей это критично.

UUIDv4 — полностью случайный (122 случайных бита).

UUIDv7 — введён сравнительно недавно (стандартизирован в RFC 9562, 2024); содержит временную метку в старших битах плюс случайность в младших. Поэтому UUIDv7 монотонно возрастает во времени.

-- PostgreSQL
CREATE TABLE events (
    event_id UUID PRIMARY KEY DEFAULT gen_random_uuid(),  -- v4, случайный
    payload  JSONB
);

Профиль по осям:

• Ширина: 16 байт. В 2-4 раза шире INTEGER/BIGINT. Индекс толще, JOIN медленнее, чем по целому.
• Монотонность: зависит от версии. UUIDv4 — НЕ монотонен (полностью случаен). UUIDv7 — монотонен (время в старших битах).
• Распределённость: да, отличная. Любой сервис, любой воркер генерирует UUID независимо, без сети, без координатора. Это главное преимущество.
• Воспроизводимость: нет. UUID случаен (хотя бы частично) — повторно тот же не получить.
• Утечка: UUIDv4 не раскрывает ничего — нельзя перебрать, нельзя оценить объём. UUIDv7 раскрывает время создания (метка времени в ключе) — иногда это нежелательно.

Разница v4 и v7 — это прямая иллюстрация trade-off:

UUIDv4: случайность -> нельзя угадать время, НО фрагментирует B-tree индекс
        (каждая вставка попадает в случайное место индекса)

UUIDv7: время в старших битах -> вставки идут в конец индекса (как sequence),
        НО ключ раскрывает время создания строки

Стратегия 3: hash — детерминированный ключ из бизнес-данных

Hash-ключ — это значение хеш-функции (MD5, SHA-256) от business key строки. Идея: ключ не генерируется счётчиком и не случаен — он вычисляется из самих данных. Одинаковый business key всегда даёт одинаковый hash.

Эта стратегия — основа Data Vault (отдельный модуль курса), где hash-ключи используются для hub/link-таблиц.

-- Концептуально: ключ = хеш от business key
-- hash('[email protected]') -> детерминированное 256-битное значение
SELECT md5('[email protected]')    AS md5_key;     -- 16 байт (128 бит)
SELECT sha256('[email protected]') AS sha256_key;  -- 32 байта (256 бит)

Профиль по осям:

• Ширина: MD5 — 16 байт, SHA-256 — 32 байта. Шире целого; SHA-256 ещё и заметно шире UUID.
• Монотонность: нет, никогда. Выход хорошей хеш-функции выглядит случайным — те же проблемы с фрагментацией B-tree индекса, что у UUIDv4.
• Распределённость: да, и это ключевое. Hash детерминирован: любой воркер, зная business key, вычисляет ОДИН И ТОТ ЖЕ ключ независимо — без сети, без координатора, без обращения к другим воркерам. Именно поэтому Data Vault может грузить hub, link и satellite параллельно: каждый процесс сам считает hash, и ключи у всех совпадут.
• Воспроизводимость: да, полная. Это уникальное свойство hash. Перезагрузите данные с нуля — ключи будут те же. Можно сопоставлять данные между средами (dev/prod) по ключу.
• Утечка: хеш сам по себе ничего не раскрывает.

Коллизии и парадокс дней рождения — «до железа»

У hash-ключа есть свойство, которого нет у остальных стратегий: теоретическая возможность коллизии. Два разных business key могут дать один и тот же hash. Разберём математику честно.

Хеш-функция отображает бесконечное множество входов в конечное множество выходов фиксированной длины. SHA-256 даёт 256 бит — это 2 в степени 256 возможных значений. Раз входов больше, чем выходов, коллизии существуют в принципе. Вопрос — насколько они вероятны на практике.

Интуиция подсказывает: «значений 2^256, это гигантское число, при миллиарде строк шанс ничтожен». Интуиция права, но недооценивает один эффект — парадокс дней рождения. Вероятность коллизии растёт не пропорционально числу строк N, а пропорционально N в квадрате. Причина: коллизия — это совпадение любой пары из N элементов, а число пар равно примерно N в квадрате делить на 2.

Грубая оценка вероятности хотя бы одной коллизии при N элементах и пространстве из M значений:

P(коллизия) приблизительно равно  N^2 / (2 * M)

Для SHA-256:  M = 2^256

Подставим N = 10^12 (триллион строк — больше, чем у почти любой системы):

  P  ~  (10^12)^2 / (2 * 2^256)
     =  10^24 / (2 * 2^256)
     ~  10^24 / 10^77
     ~  10^-53

10^-53 — это вероятность настолько малая, что она много меньше
вероятности отказа диска, ошибки оперативной памяти из-за
космического луча или ошибки самого процессора при вычислении.

Вывод для SHA-256 однозначен: коллизии — это теоретический non-issue на практике. При любом реалистичном объёме данных вероятность коллизии SHA-256 настолько мала, что её можно не учитывать — другие компоненты системы (железо, сеть) откажут несравнимо раньше. Не нужно бояться SHA-256-ключей из-за коллизий.

С MD5 ситуация иная — и дело не столько в случайных коллизиях по объёму, сколько в том, что MD5 криптографически сломан: придуманы алгоритмы, позволяющие СОЗНАТЕЛЬНО сконструировать два разных входа с одинаковым MD5. Для surrogate key из доверенных внутренних данных это обычно не фатально (никто не атакует ваши ключи специально), но MD5 — более слабый выбор: запас прочности у него меньше, и если данные хоть как-то приходят извне, конструируемые коллизии становятся реальным риском. Если выбираете hash-ключ — берите SHA-256, а не MD5.

Стратегия 4: Snowflake ID — распределённый и монотонный

Snowflake ID (придуман в Twitter) — 64-битный составной идентификатор. 64 бита разбиты на части:

Snowflake ID (64 бита):
[ timestamp (~41 бит) ][ machine/shard id (~10 бит) ][ sequence (~12 бит) ]

- timestamp     : миллисекунды -> ключ монотонно растёт во времени
- machine id    : номер машины/воркера -> разные воркеры не пересекаются
- sequence      : счётчик внутри одной миллисекунды на одной машине

Идея в том, чтобы получить и распределённость, и монотонность одновременно. Timestamp в старших битах делает ключ возрастающим (хорошо для B-tree); machine id гарантирует, что два воркера не сгенерируют одинаковый ключ без всякой координации между ними.

Профиль по осям:

• Ширина: 8 байт (BIGINT). Узкий — как обычное целое, вдвое уже UUID.
• Монотонность: да, благодаря timestamp в старших битах. Хорошо ложится в индекс.
• Распределённость: да. Координация нужна минимальная — только раздать воркерам уникальные machine id один раз при настройке; дальше каждый генерирует независимо.
• Воспроизводимость: нет. Snowflake ID завязан на время и счётчик, повторно тот же не получить.
• Утечка: да, раскрывает время создания (timestamp в ключе) и отчасти номер воркера.

Snowflake ID — это попытка взять сильные стороны sequence (узость, монотонность) и UUID (распределённость) сразу. Цена — нужна инфраструктура раздачи machine id и отсутствие воспроизводимости.

Trade-off матрица

Главная таблица урока. Ни одна строка не «лучшая» — у каждой свой профиль.

Как читать матрицу:

• Централизованная OLTP-база, один writer — sequence: самый узкий ключ, монотонный, распределённость не нужна.
• Данные генерируются на клиентах / в нескольких сервисах, нужна анонимность ключа — UUIDv4: независимая генерация, ничего не раскрывает.
• То же, но таблица быстро растёт и важна скорость вставки — UUIDv7 или Snowflake ID: распределённость плюс монотонность.
• Data Vault, параллельная загрузка, нужна воспроизводимость ключа между средами — hash (SHA-256): единственная стратегия с детерминированностью.

Попробуй сам

В PostgreSQL (или SQLite — где-то функции хешей называются иначе) проведите эксперимент со всеми четырьмя стратегиями:

1. Создайте таблицу с INTEGER GENERATED ALWAYS AS IDENTITY и вставьте 5 строк. Посмотрите на ключи — это sequence: 1, 2, 3, 4, 5.
2. Создайте таблицу с UUID DEFAULT gen_random_uuid() (UUIDv4) и вставьте 5 строк. Сравните: ключи случайны, порядка нет, ширина 16 байт.
3. Вычислите md5('test') и sha256('test') (или эквивалент). Запустите дважды — убедитесь, что результат одинаковый оба раза. Это и есть детерминированность: воспроизводимость, которой нет у sequence и UUID.
4. Возьмите матрицу из урока и распишите её для двух своих систем: (а) монолитное приложение с одной PostgreSQL-базой; (б) Data Vault warehouse, грузящий данные параллельно из 4 источников. Для каждой выберите стратегию и обоснуйте по осям — какие критерии решили выбор.
5. Прикиньте по формуле N^2 / (2*M) вероятность коллизии SHA-256 для вашего реального объёма данных (например, 100 млн строк). Убедитесь, что число настолько мало, что коллизий можно не бояться.