Как справляться с коллизиями при генерации коротких ссылок
Что проверяют
Понимаете ли вы, откуда берутся коллизии и почему проверка «есть ли такой код в базе» перед вставкой не спасает под нагрузкой. Следом обычно спрашивают, как сделать ссылки непредсказуемыми и как генерировать их с нескольких инстансов.
Как отвечать
Сравните три подхода:
- счётчик и base62: уникальный идентификатор из последовательности PostgreSQL кодируется алфавитом из 62 символов. Коллизий нет по построению, семь символов дают 62^7, примерно 3,5 триллиона кодов. Минус: коды идут подряд и перебираются. Помогает обратимое перемешивание идентификатора, например библиотекой Sqids, но это обфускация, а не защита;
- случайный код:
secrets.choiceпо алфавиту илиsecrets.token_urlsafe. Работает парадокс дней рождения: при 62^7 вариантов вероятность хотя бы одной коллизии доходит до 50% примерно на двух миллионах ссылок. Коллизии будут, их нужно обрабатывать; - хэш от URL: первые символы
md5илиsha256. Одинаковый URL даёт одинаковый код, это удобно для дедупликации, но обрезанный хэш сталкивается не реже случайного, а при коллизии хэш нельзя просто пересчитать: к входу добавляют соль или счётчик.
В любом варианте уникальность гарантирует база, а не приложение. На колонке кода стоит UNIQUE, вставка идёт сразу, при конфликте генерируется новый код. В SQLAlchemy или Django это перехват IntegrityError, в SQL INSERT ... ON CONFLICT (code) DO NOTHING RETURNING id: пустой результат означает коллизию. Число попыток ограничьте, после чего увеличивайте длину кода.
С несколькими инстансами и счётчиком каждый берёт диапазон идентификаторов пачкой, например через INCRBY в Redis на тысячу, и раздаёт его из памяти.
Где спотыкаются
Сначала проверяют, свободен ли код, потом вставляют. Между двумя запросами другой процесс успевает занять тот же код, это классическая гонка.
Генерируют код модулем random. Он не криптостойкий, последовательность можно предсказать, для публичных ссылок нужен secrets.
Берут md5(url).hexdigest()[:6] и считают коллизии редкими. Шесть шестнадцатеричных символов дают около 16,7 миллиона вариантов, и вероятность коллизии доходит до 50% уже на нескольких тысячах ссылок.