Вероятность коллизии UUID

Что такое Вероятность коллизии UUID

Интуиция «одна коллизия на 2¹²² значений» неверна — и ошибается в вашу пользу. Совпадение возможно между любыми двумя значениями, поэтому риск растёт как квадрат их количества. Стандартное приближение: p ≈ n² / (2 × 2122). Отсюда и известная цифра: около 2.7 × 10¹⁸ значений — примерно три триллиона в секунду в течение года — прежде чем вероятность дубля достигнет 50%.

На реальных объёмах числа успокаивают: миллиард UUID v4 даёт вероятность около 9 × 10^-20. Но на практике важны ещё две вещи. Во-первых, энтропия не лучше генератора: UUID на Math.random(), на сломанном ГПСЧ или с фиксированным зерном имеет куда меньше эффективных бит, чем предполагает формат. Во-вторых, формулы предполагают независимость: если два сервиса создают значения из одного и того же засеянного источника, граница дней рождения к ним неприменима.

Короткие идентификаторы — как раз тот случай, когда решение становится реальным. Та же математика с 64 битами вместо 122 означает, что миллиард значений уже несёт примерно 2.7% вероятности коллизии. Это не повод отказываться от компактных id — это повод подбирать их под задачу и держать в базе ограничение уникальности как последнюю линию защиты.

Как использовать

1. Посчитайте, сколько идентификаторов понадобится всего, включая исторические строки и импорт из других систем.
2. Найдите соответствующую вероятность в таблице ниже.
3. Если коллизия дорого обойдётся, оставьте ограничение UNIQUE: математика снижает шансы, но не отменяет необходимости в ограничении.

Сценарии

• Выбор между UUID и коротким id, где 64 бита могут быть достаточны для кеша и слишком малы для реестра.
• Ревизия чужого кода, который сам создаёт идентификаторы: проверять нужно источник энтропии, а не формат.
• Объяснение заказчику, почему «случайный» не означает «ограничение не нужно».

Сравнение Вероятность коллизии UUID с другими форматами

Примеры кода

Вероятность в Python

from math import exp

def collision_probability(n, bits=122):
    N = 2 ** bits
    return 1 - exp(-(n * n) / (2 * N))

for n in (10**6, 10**9, 10**12, 10**15, 2.7 * 10**18):
    print(f'{n:.0e}', collision_probability(n))

# 64-битные id достигают 2.7% на миллиарде значений
print(collision_probability(10**9, bits=64))

То же в одну строку (JavaScript)

const p = (n, bits = 122) => 1 - Math.exp(-(n * n) / (2 * 2 ** bits));

p(1e9);        // ~9.4e-20
p(1e9, 64);    // ~0.027

Ограничение в схеме

CREATE TABLE events (
  id uuid PRIMARY KEY,          -- или UNIQUE NOT NULL для не-ключевого поля
  created_at timestamptz NOT NULL DEFAULT now()
);
-- Математика делает коллизии маловероятными, ограничение — невозможными.

Частые вопросы