> Как справляться с коллизиями при генерации коротких ссылок (Python)

Короткий ответ

Коллизии при генерации коротких ссылок решаются комбинацией трёх подходов: использование достаточно большого пространства идентификаторов (например, base62 от 7+ символов), проверка уникальности перед вставкой с retry-логикой при коллизии, и, при необходимости, переход на суффиксный или итеративный вариант генерации. Ключевой trade-off - между длиной ссылки, вероятностью коллизии и стоимостью проверки. Для высоконагруженных систем добавляют кэширование проверок и предгенерацию пулов идентификаторов.

Подробное объяснение

Коллизия возникает, когда два разных длинных URL получают одинаковый короткий код. Это ломает инвариант "один код - один URL". Основные стратегии:

1. Увеличение пространства ключей - base62 (a-z, A-Z, 0-9) даёт 62^n комбинаций. При n=7 это ~3.5 триллиона. Вероятность коллизии при случайной генерации оценивается через birthday paradox: для 10 млн ссылок при n=7 вероятность коллизии ~1.4%. При n=8 - ~0.005%.

2. Проверка перед вставкой - генерируем код, пытаемся вставить в БД с уникальным индексом. При violation - генерируем заново. Это надёжно, но добавляет latency и нагрузку на БД при высокой конкуренции.

3. Детерминированная генерация - используем хэш от исходного URL (MD5, SHA-256) и берём первые N байт. Коллизии возможны, но при одинаковом входе всегда одинаковый выход. Проблема - предсказуемость и возможность подбора.

4. Счётчик + кодирование - глобальный атомарный счётчик (например, Redis INCR), значение кодируется в base62. Коллизии исключены, но ссылки предсказуемы и есть единая точка отказа.

5. Суффиксный подход - при коллизии добавляем случайный суффикс или увеличиваем длину. Например, abc123 → abc123x. Это компромисс между простотой и надёжностью.

На практике чаще всего комбинируют: генерируют случайный код из достаточно большого пространства, проверяют уникальность, при коллизии - retry (обычно до 3-5 попыток), затем увеличивают длину. Для систем с очень высокой нагрузкой используют предгенерацию пулов кодов в памяти.

На практике

Для senior-позиции важно не просто назвать алгоритм, а обсудить:

• Выбор длины кода - исходя из ожидаемого количества ссылок и допустимой вероятности коллизии. Формула: n = ceil(log_base(Total * k / -ln(1-p))), где p - допустимая вероятность.
• База данных - уникальный индекс на колонку кода обязателен. Использование INSERT ... ON CONFLICT DO NOTHING в PostgreSQL или аналогов.
• Retry-логика - ограниченное число попыток, экспоненциальный backoff, логирование частоты коллизий как метрики.
• Кэширование - проверка существования кода в Redis перед обращением к БД, но с учётом race condition.
• Масштабирование - при шардировании БД уникальность индекса должна сохраняться на уровне всего кластера.
• Безопасность - не использовать последовательные коды для чувствительных данных, так как они угадываемы.

Пример кода

PYTHON
import secrets
import string
from sqlalchemy.exc import IntegrityError

ALPHABET = string.ascii_letters + string.digits  # base62
BASE = len(ALPHABET)
MAX_RETRIES = 5

def generate_code(length: int = 7) -> str:
    """Криптографически безопасная случайная строка base62."""
    return ''.join(secrets.choice(ALPHABET) for _ in range(length))

def create_short_link(db_session, original_url: str) -> str:
    for attempt in range(MAX_RETRIES):
        code = generate_code()
        try:
            db_session.add(ShortLink(code=code, url=original_url))
            db_session.commit()
            return code
        except IntegrityError:
            db_session.rollback()
            # при последней попытке увеличиваем длину
            if attempt == MAX_RETRIES - 1:
                code = generate_code(length=8)
                db_session.add(ShortLink(code=code, url=original_url))
                db_session.commit()
                return code
    raise RuntimeError("Failed to generate unique code")

Альтернатива с предгенерацией пула:

PYTHON
def pregenerate_pool(size: int = 1000) -> list[str]:
    """Генерируем пул кодов заранее, помечаем как available."""
    codes = [generate_code() for _ in range(size)]
    # batch insert в отдельную таблицу с уникальным индексом
    return codes

def get_available_code(db_session) -> str:
    # атомарно выбираем и помечаем код как used
    code = db_session.execute(
        text("SELECT code FROM code_pool WHERE used = false LIMIT 1 FOR UPDATE SKIP LOCKED")
    ).scalar()
    if not code:
        raise PoolExhausted()
    db_session.execute(text("UPDATE code_pool SET used = true WHERE code = :code"), {"code": code})
    db_session.commit()
    return code

Как отвечать на собеседовании

Начните с чёткого определения проблемы: коллизия - это нарушение уникальности кода. Затем структурируйте ответ:

1. Опишите базовые подходы (случайная генерация, счётчик, хэш) и их trade-off.
2. Объясните, почему случайная генерация с проверкой - самый распространённый вариант.
3. Упомяните математическую оценку вероятности коллизии - это показывает глубину.
4. Перейдите к практическим деталям: уникальный индекс, retry, кэш, метрики.
5. Если спросят про масштабирование - обсудите предгенерацию пулов и шардирование.

Хороший тон - задать уточняющий вопрос: "Какое ожидаемое количество ссылок и требования к длине?" Это демонстрирует системное мышление.

Что проверяет интервьюер

• Понимание trade-off между длиной кода и вероятностью коллизии.
• Знание работы с БД (уникальные индексы, обработка IntegrityError).
• Умение проектировать отказоустойчивые алгоритмы (retry, backoff).
• Осведомлённость о проблемах масштабирования и безопасности.
• Способность обсуждать альтернативы и обосновывать выбор.

Типичные ошибки

• Предложение только увеличить длину кода без анализа вероятности.
• Игнорирование уникального индекса в БД - полагание только на проверку в коде (race condition).
• Бесконечный retry без ограничения - деградация под нагрузкой.
• Использование предсказуемых кодов (счётчик) без учёта безопасности.
• Отсутствие метрик на частоту коллизий - нельзя вовремя заметить проблему.
• Неучёт того, что при шардировании уникальность индекса должна быть глобальной.