sho.rt/aZ3kP9q
429 Too Many
fan-out ×10⁸
seq 41 ✓✓
Четыре классические задачи системного дизайна — по шагам настоящего интервью: требования, оценки, API, данные, схема, углубление, узкие места. С числами и компромиссами.
Серия «Системный дизайн», часть 5. Понятия из подхода, масштабирования, данных и распределённых систем здесь применяются, а не объясняются заново. Листайте ← →, свайпом или кнопками внизу.
На интервью 45 минут. Кандидаты чаще всего проваливаются не на знаниях, а на порядке: рисуют Kafka до того, как узнали, сколько будет запросов. Подробно о каждом шаге — в первой части серии.
Каждая задача ниже проходит эти шаги. Цифры — порядки величин, а не точные значения: на интервью важнее, какие выводы вы из них сделали.
Двигайте ползунки. Выводы из чисел: запись — копейки, чтение надо кэшировать, а общий объём через несколько лет уже не влезет в один сервер.
long_url по ключу». Ни соединений, ни диапазонов: это key-value.ON CONFLICT DO NOTHING, IF NOT EXISTS), иначе два пользователя получат один алиас.UPDATE counter: строка вирусной ссылки стала бы точкой конкуренции.
POST /api/v1/links
{"url": "https://…", "alias": "sale",
"expires_at": "2027-01-01"}
→ 201 {"short": "https://sho.rt/aZ3kP9q"}
GET /{key} → 302 Location: https://…
404, если нет или просрочена
GET /api/v1/links/{key}/stats?from=…&to=…
DELETE /api/v1/links/{key}
# links (KV, шард по key)
key PK │ long_url │ owner_id │ created_at │ expires_at
# clicks: Kafka → ClickHouse
key │ ts │ country │ referrer │ user_agent
Выберите способ и создавайте ссылки на разных серверах. Уроните сервер B.
Base62 — это [0-9a-zA-Z]: 62⁷ ≈ 3,5 трлн ключей. Кажется, что хватит надолго. Но если ключи случайные (хеш), первая коллизия ждёт не через триллион ссылок, а примерно через √(π·N/2) — около 2,4 млн.
Поэтому при хеше проверка коллизий обязательна, а при счётчике или диапазонах не нужна вовсе. Введите номер — увидите base62. Двигайте длину ключа и число ссылок.
Переключите код ответа и покликайте одним и тем же пользователем. Потом поменяйте цель ссылки.
Популярность ссылок подчиняется закону Ципфа: малая доля ссылок собирает почти все клики. Небольшой кэш снимает с базы основную нагрузку.
Ключи выдаёт счётчик: base62(id). Безопасник говорит: «Я открыл sho.rt/aZ3kP9q, потом aZ3kP9r — и попал в чужой приватный документ». Что делать?
…0001, …0002. Для приватных ссылок ещё и длиннее ключ, и проверка прав.Лимиты по ключу (пользователь, API-ключ, IP) и правилу — «100 в минуту и 1000 в час». Общие для всех N шлюзов, накладные расходы меньше миллисекунды, ответ 429 с Retry-After и X-RateLimit-Remaining.
Лимит здесь — 10 запросов за 10 секунд. Выберите поток запросов и алгоритм: зелёные пропущены, красные получили 429. Особенно интересен всплеск на границе окна.
-- KEYS[1] = rl:{user}:api
-- ARGV: ёмкость, жетонов в секунду, цена
local cap, rate = tonumber(ARGV[1]), tonumber(ARGV[2])
local cost = tonumber(ARGV[3])
local t = redis.call('TIME') -- часы Redis
local now = t[1] * 1000 + t[2] / 1000
local b = redis.call('HMGET', KEYS[1], 'tok', 'ts')
local tok = tonumber(b[1]) or cap
local ts = tonumber(b[2]) or now
tok = math.min(cap, tok + (now - ts) * rate / 1000)
local ok = tok >= cost
if ok then tok = tok - cost end
redis.call('HSET', KEYS[1], 'tok', tok, 'ts', now)
redis.call('PEXPIRE', KEYS[1],
math.ceil(cap / rate * 1000))
return ok and 1 or 0
Скрипт выполняется в Redis целиком, другие команды между его строками не вклиниваются. {user} — хеш-тег: в Redis Cluster все ключи пользователя попадут в один слот.
Клиент с лимитом 100 запросов в секунду. Меняйте число шлюзов, балансировку и режим, затем уроните Redis.
Лимит «100 запросов в минуту» сделан фиксированным окном: INCR rl:{user}:{минута} + EXPIRE 60. Сколько запросов клиент может гарантированно провести за любые 60 секунд подряд?
INCR атомарен и счётчик общий.post_id — 64-битный ID с временем внутри (Snowflake), сортируется по времени. Подписки — граф в обе стороны: «на кого я» и «кто на меня».
POST /api/v1/posts {"text", "media"}
GET /api/v1/feed?cursor=…&limit=20
→ {"items": […], "next_cursor": "…"}
PUT /api/v1/users/{id}/follow
Выберите стратегию и двигайте порог. Столбики — сколько постов в секунду публикуют авторы с таким числом подписчиков; закрашенные идут через push.
# fan-out: каждому подписчику автора
ZADD feed:{uid} {post_id} {post_id}
ZREMRANGEBYRANK feed:{uid} 0 -801 # 800 последних
# страница после курсора
ZREVRANGEBYSCORE feed:{uid} ({cursor} -inf LIMIT 0 20
Листайте ленту и добавляйте новые посты между страницами — сравните offset и курсор.
client_msg_id: клиент повторяет отправку, пока не получил ack. См. идемпотентность.
→ send {chat: 42, cid: "8f1e", body: "…"}
← ack {cid: "8f1e", seq: 1041}
← msg {chat: 42, seq: 1041, from: 7, body: "…"}
→ delivered {chat: 42, seq: 1041}
→ read {chat: 42, seq: 1041}
→ sync {chats: {42: 1037, 77: 310}}
Один шлюз держит 0,5–1 млн простаивающих соединений (десятки КБ памяти на каждое) → 200–400 серверов. Хранить историю — 20 млрд × ~200 Б = 4 ТБ в день до репликации. WhatsApp хранит сообщение только до доставки, Telegram — всегда: это первый вопрос к интервьюеру.
user → gateway с TTL, который продлевает heartbeat. По нему сервис чата находит, куда отдать сообщение.seq, пишет в хранилище, только потом шлёт ack отправителю. Нет соединения — пуш через APNs/FCM, а сообщение заберут синхронизацией.Отправляйте сообщения и смотрите путь по шагам. Отключите D, напишите ему, затем подключите снова.
seq — следующий номер в этом чате. Клиент показывает сообщения по seq, а не по времени прихода.sync after=N.seq», а не флаг на каждом сообщении: одна запись вместо тысячи.Отправьте пачку сообщений: сеть доставит их вперемешку. Включите потери и посмотрите, как клиент обнаруживает дыру.
-- Cassandra / ScyllaDB
CREATE TABLE messages (
chat_id bigint,
bucket int, -- окно в 10 дней
seq bigint,
sender_id bigint,
cid uuid, -- для дедупликации
body blob,
PRIMARY KEY ((chat_id, bucket), seq)
) WITH CLUSTERING ORDER BY (seq DESC);
Так хранит сообщения Discord: «последние 50 сообщений чата» — одно чтение подряд из одной партиции, а окно не даёт партиции расти вечно. Запись только дописывается — LSM-движку это идеально.
chat_id — и считает номера в памяти, восстанавливая счётчик из базы при переезде. Глобальный счётчик или LWT на каждое сообщение слишком дороги.В группе три участника пишут одновременно с разных шлюзов. Как сделать, чтобы все увидели сообщения в одном и том же порядке?
Правильного ответа нет. Есть обоснованные компромиссы.