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

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

Генерация короткой ссылки сводится к преобразованию длинного URL в уникальный короткий идентификатор. Основные подходы: хеширование с обработкой коллизий, счётчик с base62-кодированием, либо генерация случайной строки с проверкой уникальности. Ключевые требования - детерминированность, устойчивость к коллизиям, масштабируемость и возможность обратного преобразования. В Go обычно используют murmur3 или xxhash для хеша, затем кодируют в base62, либо применяют распределённый ID-генератор (например, Snowflake) с последующим кодированием.

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

Основная задача - получить короткий идентификатор (обычно 6-10 символов) из длинного URL. Существует три базовых подхода:

1. Хеширование: берём хеш от URL (MD5, SHA-1, murmur3), берём первые N байт, кодируем в base62. Проблема - коллизии: разные URL могут дать одинаковый хеш. Решение - проверка в БД и добавление соли или увеличение длины.

2. Счётчик: глобальный монотонный ID (например, из БД или Redis INCR), затем кодируем в base62. Детерминированно, без коллизий, но требует централизованного счётчика. Для распределённости используют сегментированные счётчики или Snowflake.

3. Случайная генерация: генерируем случайную строку из алфавита [a-zA-Z0-9], проверяем уникальность в БД. Просто, но при большом объёме растёт число коллизий и повторных попыток.

На практике часто комбинируют: берут хеш, проверяют коллизию, при коллизии добавляют соль или увеличивают длину. Для высоконагруженных систем предпочтителен подход со счётчиком или Snowflake, так как он не требует повторных запросов к БД.

Важный момент - обратное преобразование: короткий код должен быть ключом в БД, где хранится оригинальный URL. Поэтому код должен быть уникальным индексом, а не просто результатом хеша без проверки.

На практике

Для senior-позиции важно показать понимание trade-off между подходами. Например:

• Хеширование даёт детерминированность (один URL - один код), но при изменении URL меняется код. Это удобно для кэширования, но требует обработки коллизий.
• Счётчик даёт компактные коды, но раскрывает порядок создания (можно угадать следующий ID).
• Случайные строки безопаснее с точки зрения угадывания, но требуют больше ресурсов на проверку уникальности.

Также нужно обсудить масштабирование: как генерировать ID в распределённой системе без единой точки отказа. Варианты - Redis INCR с шардированием, ZooKeeper, Snowflake (time + machine ID + sequence).

Дополнительно стоит упомянуть про кэширование (hot URLs), TTL для неиспользуемых ссылок, аналитику переходов.

Пример кода

GO
package main

import (
    "crypto/md5"
    "encoding/binary"
    "math/big"
)

const alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789"

// encodeBase62 converts a uint64 to a base62 string
func encodeBase62(num uint64) string {
    if num == 0 {
        return string(alphabet[0])
    }
    var result []byte
    base := uint64(len(alphabet))
    for num > 0 {
        result = append([]byte{alphabet[num%base]}, result...)
        num /= base
    }
    return string(result)
}

// generateShortCode hashes the URL and returns a short code
func generateShortCode(url string) string {
    hash := md5.Sum([]byte(url))
    // take first 8 bytes as uint64
    num := binary.BigEndian.Uint64(hash[:8])
    // mask to 62^6 range (approx 56 billion) for 6-char code
    num = num % (62 * 62 * 62 * 62 * 62 * 62)
    return encodeBase62(num)
}

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

Начните с краткого описания задачи и требований: уникальность, длина, скорость генерации, масштабируемость. Затем перечислите подходы, сравните их по сложности, коллизиям, производительности. Покажите, что понимаете ограничения каждого. Обязательно упомяните хранение: код - первичный ключ в таблице, оригинальный URL - значение. Для senior важно показать, как решать проблему коллизий в распределённой системе и как обеспечить горизонтальное масштабирование. Завершите примером кода и обсуждением edge cases (пустой URL, очень длинный URL, юникод).

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

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

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

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