Как генерировать короткую ссылку в системе url shortener

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

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

Как отвечать

Сначала посчитайте ёмкость. Алфавит base62 (0-9a-zA-Z): 6 символов дают около 56,8 млрд вариантов, 7 символов около 3,5 трлн. Большинству сервисов 7 символов хватает с запасом.

Три рабочих подхода:

• счётчик и base62: уникальный int64 из последовательности в базе переводится в base62. Коллизий нет по построению. Чтобы база не стала узким местом, инстанс резервирует диапазон, например по 1000 номеров, и раздаёт его из памяти. Минус: коды идут подряд и легко перебираются, это лечат обратимым перемешиванием номера или библиотекой вроде Sqids;
• случайный код: 7 символов из crypto/rand, запись через INSERT ... ON CONFLICT DO NOTHING по уникальному индексу, при конфликте повтор. Из-за парадокса дней рождения первая коллизия вероятна уже на паре миллионов записей, так что проверка обязательна;
• хэш от URL: SHA-256 или xxhash, обрезанный до нужной длины. Одинаковые ссылки получают одинаковый код, это удобно для дедупликации, но коллизии после обрезки всё равно надо ловить.

В Go перевод в base62 пишут вручную делением на 62 или делают через big.Int.Text(62): strconv.FormatInt поддерживает основание только до 36.

Для редиректа отдавайте 302 или 307, если нужна статистика переходов: 301 браузер кэширует и дальше ходит мимо сервиса. Горячие коды держите в Redis перед базой.

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

Берут md5 и первые 8 символов base64 без проверки. Две разные ссылки однажды получат один код, и одна из них молча перезапишет другую.

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

Держат счётчик в памяти процесса через atomic.Int64. После рестарта он начинает с нуля, а два пода выдают одинаковые номера.