Какая должна быть длина короткой ссылки, чтобы избежать коллизий при заданной нагрузке и времени жизни

Что проверяют

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

Как отвечать

Сначала посчитайте, сколько ссылок одновременно живёт в системе. При 100 новых ссылках в секунду и сроке жизни 5 лет это 100 × 86 400 × 365 × 5 ≈ 1,6 × 10¹⁰. Если просроченные коды не переиспользуются, считать надо все выданные за всё время.

Пространство кодов длины L в алфавите Base62 равно 62^L: 6 символов дают около 5,7 × 10¹⁰, 7 символов около 3,5 × 10¹², 8 символов около 2,2 × 10¹⁴. Дальше выбор зависит от способа генерации:

• счётчик: коллизий нет вовсе, код это номер в Base62. Для примера хватает 6 символов. Источник номера: sequence в PostgreSQL или INCR в Redis. Чтобы коды не шли подряд и их нельзя было перебрать, номер пропускают через обратимое перемешивание;
• случайный код с проверкой: secrets.choice по алфавиту, уникальный индекс и повтор при конфликте (INSERT ... ON CONFLICT DO NOTHING). Важна доля занятого пространства n/N: это вероятность попасть в занятый код при каждой вставке. Держите её ниже 1%, получится 7 символов;
• случайный код или хеш без проверки: вероятность хотя бы одной коллизии примерно n²/(2N). Для 1,6 × 10¹⁰ ссылок и риска 10⁻⁶ нужно N порядка 10²⁶, это 15 символов.

Первая коллизия в случайном пространстве ожидается уже около √N вставок: для 7 символов это пара миллионов ссылок, а не триллионы.

Где спотыкаются

Считают L = log₆₂(n) и называют это «без коллизий». Формула говорит только, что коды поместятся, а при случайной генерации коллизии начнутся гораздо раньше.

Берут первые символы от MD5 или SHA-256 длинной ссылки и не проверяют уникальность. Обрезанный хеш подчиняется тому же парадоксу дней рождения.

Используют модуль random вместо secrets. Его генератор предсказуем по выходу, а предсказуемые коды означают перебор чужих ссылок.