Основы system design

Что это за секция

На system design просят спроектировать сервис: «сократитель ссылок», «ленту новостей», «чат», «систему уведомлений». Правильного ответа нет — оценивают, как вы рассуждаете: выясняете ли требования, считаете ли нагрузку, знаете ли строительные блоки и их компромиссы, видите ли узкие места. Для junior такая секция бывает редко, для middle — упрощённая, для senior — обязательна.

Структура ответа на 45–60 минут

Ведите диалог: интервьюер подскажет, на чём сосредоточиться. Рисуйте схему по ходу разговора.

Строительные блоки

Масштабирование базы данных

• Вертикальное — больше CPU/памяти/дисков. Просто, но есть предел.
• Реплики чтения — копии базы, получающие изменения с ведущей (асинхронно). Чтения распределяются, запись — по-прежнему на одну машину. Минус — задержка репликации: пользователь может не увидеть только что записанное (решение — читать своё с ведущей).
• Шардирование — данные делятся между базами по ключу (user_id % N, диапазоны, консистентное хеширование). Масштабирует запись, но усложняет запросы между шардами, транзакции и решардинг.
• Индексы, денормализация, кеш, вынос аналитики в отдельное хранилище (ClickHouse) — часто дают больше, чем шардирование.

Кеширование

• Cache-aside (чаще всего): приложение читает из кеша, при промахе — из базы и кладёт в кеш с TTL. При записи — удаляет ключ.
• Write-through: запись идёт и в кеш, и в базу.
• Риски: устаревшие данные, «шторм» запросов к базе при одновременном истечении популярного ключа (решение — блокировка на пересчёт, случайный разброс TTL), холодный старт.

Консистентное хеширование

При обычном hash(key) % N добавление одного сервера перемещает почти все ключи — кеш «обнуляется». Консистентное хеширование размещает серверы и ключи на кольце; ключ принадлежит ближайшему серверу по часовой стрелке. При добавлении сервера переезжает лишь ~1/N ключей.

import bisect, hashlib

def h(value: str) -> int:
    return int(hashlib.md5(value.encode()).hexdigest(), 16)

class Ring:
    def __init__(self, nodes, vnodes=100):
        self.ring = sorted((h(f"{node}#{i}"), node) for node in nodes for i in range(vnodes))
        self.keys = [k for k, _ in self.ring]

    def node_for(self, key: str) -> str:
        i = bisect.bisect(self.keys, h(key)) % len(self.ring)
        return self.ring[i][1]

keys = [f"user:{i}" for i in range(10_000)]

def moved(before, after):
    return sum(before(k) != after(k) for k in keys) / len(keys)

mod3 = lambda k: f"s{h(k) % 3}"
mod4 = lambda k: f"s{h(k) % 4}"
print(f"hash % N:        переехало {moved(mod3, mod4):.0%} ключей при добавлении 4-го сервера")

ring3, ring4 = Ring(["s0", "s1", "s2"]), Ring(["s0", "s1", "s2", "s3"])
print(f"консистентное:   переехало {moved(ring3.node_for, ring4.node_for):.0%} ключей")

from collections import Counter
print("распределение по серверам:", sorted(Counter(map(ring4.node_for, keys)).items()))

Виртуальные узлы (vnodes) — много точек на кольце для каждого сервера — выравнивают нагрузку.

Ключевые понятия

• Задержка и пропускная способность: p50/p95/p99 времени ответа и RPS. Ориентиры: память — наносекунды, SSD — ~100 мкс, запрос в пределах дата-центра — ~0.5 мс, между континентами — ~100 мс.
• Доступность: 99.9% — 8.8 часа простоя в год, 99.99% — 53 минуты. Достигается избыточностью: несколько экземпляров, реплики, несколько зон доступности.
• CAP: при разделении сети — выбор между согласованностью и доступностью. Согласованность в конечном счёте (eventual consistency) — данные сойдутся, но не мгновенно; приемлемо для лент и счётчиков, неприемлемо для баланса счёта.
• Идемпотентность: повтор запроса не меняет результат. Ключ идемпотентности для платежей, upsert вместо insert, дедупликация сообщений из очереди.
• Ограничение частоты (rate limiting): token bucket или скользящее окно в Redis; отвечаем 429 с Retry-After.
• Деградация: при отказе рекомендаций показываем популярное; таймауты и автоматические выключатели (circuit breaker), чтобы падение одного сервиса не утащило остальные.
• Наблюдаемость: метрики, логи, трассировка, алерты.

Разбор: сокращатель ссылок

1. Требования

• Функциональные: создать короткую ссылку для длинного URL (опционально — свой алиас, срок жизни); переход по короткой ссылке → редирект; статистика переходов.
• Нефункциональные: редирект быстрый (< 50 мс) и высокодоступный; ссылки не должны угадываться перебором подряд (желательно); читается гораздо чаще, чем создаётся.
• Не делаем: аккаунты, редактирование ссылок.

2. Оценки

dau = 10_000_000                 # пользователей в день
new_links_per_user = 0.1         # создают ссылки не все
reads_per_link = 100             # переходов на одну ссылку
avg_record_bytes = 500           # URL + метаданные

writes_per_day = dau * new_links_per_user
write_rps = writes_per_day / 86_400
read_rps = write_rps * reads_per_link
storage_5y_gb = writes_per_day * 365 * 5 * avg_record_bytes / 1e9
codes_needed_5y = writes_per_day * 365 * 5

print(f"запись:  {write_rps:,.0f} RPS в среднем, пик ~{write_rps * 3:,.0f}")
print(f"чтение:  {read_rps:,.0f} RPS в среднем, пик ~{read_rps * 3:,.0f}")
print(f"данные за 5 лет: {storage_5y_gb:,.0f} ГБ, ссылок: {codes_needed_5y:,.0f}")
for length in range(5, 9):
    print(f"base62 длины {length}: {62 ** length:,} вариантов")

Вывод: нагрузка на запись скромная (одна база справится), чтение ~1000+ RPS с пиками — нужен кеш; данных умеренно (около терабайта за 5 лет, это одна база); 6 символов base62 уже хватает (56 млрд вариантов против 1,8 млрд ссылок), 7 дают запас на рост и делают случайные коды труднее для перебора.

3. API

POST /api/links          {"url": "https://...", "alias": "promo", "expires_at": "..."}
                         → 201 {"code": "aZ3kQ9x", "short_url": "https://sho.rt/aZ3kQ9x"}
GET  /{code}             → 301/302 Location: <длинный URL>   (404, если нет; 410, если истекла)
GET  /api/links/{code}/stats → {"clicks": 1234, "by_day": [...]}

301 кешируется браузером (меньше нагрузки, но мы теряем статистику повторных переходов), 302 — каждый переход идёт через нас. Обычно выбирают 302, если статистика важна.

4. Модель данных

CREATE TABLE links (
    code        VARCHAR(16) PRIMARY KEY,
    url         TEXT NOT NULL,
    created_at  TIMESTAMPTZ NOT NULL DEFAULT now(),
    expires_at  TIMESTAMPTZ
);
-- клики пишем не в эту таблицу (горячая точка), а в очередь → агрегаты в аналитическом хранилище

5. Как генерировать код

import secrets, string

ALPHABET = string.digits + string.ascii_lowercase + string.ascii_uppercase

def encode(n: int) -> str:
    chars = []
    while True:
        n, rem = divmod(n, 62)
        chars.append(ALPHABET[rem])
        if n == 0:
            return "".join(reversed(chars))

print(encode(125), encode(10_000_000_000))

def random_code(length=7):
    return "".join(secrets.choice(ALPHABET) for _ in range(length))

existing = set()
def create(url):
    while True:                          # в реальной БД: INSERT ... ON CONFLICT DO NOTHING и повтор
        code = random_code()
        if code not in existing:
            existing.add(code)
            return code

print([create("https://example.com") for _ in range(3)])

6. Схема и узкие места

• Чтение: Redis-кеш (cache-aside) — популярные ссылки почти не доходят до базы; реплики для промахов.
• Клики: не UPDATE links SET clicks = clicks + 1 на каждый переход (горячая строка), а событие в очередь и пакетная агрегация.
• Отказоустойчивость: несколько экземпляров API в разных зонах, реплики базы, Redis с репликой; при падении Redis — работаем с базой (медленнее, но работаем).
• Защита: rate limiting на создание, проверка URL на фишинг, запрет редиректов на внутренние адреса.
• Рост: при миллиардах ссылок — шардирование по code (консистентное хеширование) или NoSQL-хранилище «ключ — значение».

Как тренироваться

Разберите таким же планом: ленту новостей (fan-out при записи против чтения), чат (WebSocket, доставка, хранение истории), систему уведомлений (очереди, повторы, дедупликация), загрузку файлов (presigned URL в S3, обработка в фоне), счётчик просмотров (приблизительные структуры, батчинг). Каждый раз проговаривайте: требования → оценки → API → данные → схема → узкие места.

Итог

• Структура: требования → оценки → API → модель данных → схема → узкие места → итог.
• Блоки: балансировщик, stateless-сервисы, БД с репликами и шардированием, кеш, очереди, объектное хранилище, CDN.
• Компромиссы называть явно: согласованность против доступности, 301 против 302, хеш против счётчика.
• Цифры «на салфетке» превращают абстрактный разговор в инженерный.