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

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

Длина короткой ссылки определяется из формулы энтропии: при алфавите из 62 символов (a-z, A-Z, 0-9) и желаемой вероятности коллизии менее 1% для N ссылок в год нужно примерно log62(N² / (2 × 0.01)) символов. Для 10 млн ссылок в год достаточно 6 символов (≈56 млрд комбинаций), для 1 млрд - 7 символов. На практике берут 7-8 символов с запасом, учитывая пиковые нагрузки и долгий срок жизни.

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

Коллизии в коротких ссылках - это задача о днях рождения. Если у нас A символов в алфавите и длина L, то пространство S = A^L. При генерации N ссылок вероятность хотя бы одной коллизии приблизительно P ≈ N² / (2S). Отсюда L = log_A(N² / (2P)).

Ключевые параметры:

• Нагрузка - количество новых ссылок в единицу времени (обычно в год или в день).
• Время жизни - сколько ссылки остаются активными. Если ссылки не удаляются, то N - это суммарное количество за всё время жизни системы.
• Алфавит - чем больше символов, тем короче ссылка при той же энтропии. Base62 - стандарт, Base64 с + и / требует URL-encoding, поэтому реже используется.
• Допустимая вероятность коллизии - для production обычно 0.1%-1%, но для критичных систем (например, платёжные ссылки) - 0.001% и ниже.

Пример расчёта для 100 млн ссылок за 10 лет (10 млн/год) с вероятностью коллизии 0.1%:

• N = 10^8, P = 0.001
• S = N² / (2P) = 10^16 / 0.002 = 5 × 10^18
• L = log62(5 × 10^18) ≈ 10.4 → нужно 11 символов.

Но на практике используют не случайную генерацию, а счётчик или хэш с проверкой. Тогда длина может быть меньше: например, для 10 млн ссылок достаточно 6 символов, если генерировать последовательно.

Также важно учитывать, что коллизии можно обрабатывать: при генерации проверять существование ключа и перегенерировать. Это снижает требования к длине, но добавляет latency и нагрузку на БД.

На практике

В реальных системах обычно:

• Берут длину 6-8 символов для Base62. Этого хватает для большинства сервисов (до 100 млн ссылок).
• Используют проверку на коллизию при вставке (unique index + retry).
• Для очень высоких нагрузок (биллионы ссылок) - 9-10 символов или переходят на UUID-подобные схемы с префиксом.
• Учитывают, что пользователи могут вводить ссылки вручную - слишком длинные неудобны, слишком короткие - рискованны.
• Для временных ссылок (например, одноразовых) можно уменьшить длину, так как N - это только активные ссылки.

Пример кода

PYTHON
import math
import secrets
import string

ALPHABET = string.ascii_letters + string.digits  # 62 символа

def required_length(num_links: int, collision_prob: float = 0.001) -> int:
    """Минимальная длина для случайной генерации."""
    space = num_links ** 2 / (2 * collision_prob)
    return math.ceil(math.log(space, len(ALPHABET)))

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

# Пример: 10 млн ссылок, вероятность коллизии 0.1%
print(required_length(10_000_000))  # 6

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

Начни с формулы birthday paradox, покажи расчёт для конкретного примера. Затем обсуди trade-off: случайная генерация vs счётчик. Для счётчика длина меньше, но есть проблемы с угадыванием ссылок и последовательностью. Для случайной - безопаснее, но длиннее. Упомяни, что на практике добавляют проверку коллизий и retry, поэтому можно взять длину с запасом в 1-2 символа. Если спросят про время жизни - объясни, что важно суммарное количество ссылок за весь период, а не в год.

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

• Понимание combinatorics и birthday paradox.
• Умение переводить требования (нагрузка, вероятность) в конкретные числа.
• Знание практических подходов: Base62, проверка коллизий, безопасная генерация.
• Умение рассуждать о trade-off между длиной, безопасностью и удобством.

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

• Забывают про время жизни и считают только годовую нагрузку.
• Используют линейную оценку вместо квадратичной (N² / 2S).
• Не учитывают, что коллизии можно обрабатывать retry, а не только увеличивать длину.
• Предлагают UUID без сокращения - это 32 символа, что неудобно для коротких ссылок.
• Путают энтропию с длиной: например, считают, что 6 символов Base62 - это 62^6, но не проверяют, хватает ли этого для N.