К содержимому
Войти

Java Road Map

🏛️ System design на мидла

System design на собеседовании — секция, где за час ты проектируешь сервис с нуля: сокращатель ссылок, ленту, рассылку уведомлений. Кода почти нет, есть доска, требования и вопросы интервьюера. Правильной схемы тут нет, смотрят на ход мысли. Какие требования ты уточнил, как прикинул нагрузку, чем платишь за каждое решение. Всё, что было в предыдущих модулях курса, здесь собирается в одну систему

🗺️ Как проходит секция

В Авито секцию описывают тремя этапами: 5–10 минут на понимание задачи и границ системы, 20 минут на высокоуровневую схему, 30 минут на погружение в детали. Задача бывает общей («спроектируй Авито») или узкой, ближе к работе команды («бэкенд для сервиса нотификаций»)

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

От мидла ждут рабочую схему, которая закрывает требования, и умение объяснить, почему здесь Postgres, а не Cassandra, и почему очередь, а не синхронный вызов. От синьора и тимлида в Авито отдельно ждут взгляда на систему целиком: что сломается через год, где узкое место при росте в десять раз, как это эксплуатировать. Мидлу полезно показать хотя бы один такой риск сам, не дожидаясь вопроса

🧭 План ответа

Порядок шагов важнее, чем красота схемы. Его стоит проговаривать вслух: «требования собрали, давай прикинем нагрузку», чтобы интервьюер видел, где ты сейчас

  1. Требования. Функциональные: что делает пользователь. Нефункциональные: сколько пользователей, допустимая задержка, что важнее при сбое, доступность или согласованность. Раздели на «обязательно» и «вне рамок» и согласуй с интервьюером, иначе через 20 минут выяснится, что ты проектировал не то
  2. Оценка нагрузки. RPS на чтение и запись, объём данных, соотношение чтений и записей. Это две минуты арифметики, которые потом объясняют каждое решение
  3. API. Три-пять методов: POST /links, GET /{code}. Use cases из первого шага ложатся в них почти один к одному
  4. Схема. Клиент, балансировщик, сервисы, хранилища, кэш, очереди и стрелки между ними. Начни с самого простого варианта, который работает, и усложняй только там, где оценка нагрузки этого требует
  5. Модель данных. Таблицы или ключи, первичный ключ, индексы, по какому полю шардировать
  6. Детали. Интервьюер выберет одно-два места и попросит углубиться: генерация кода ссылки, как не потерять уведомление, что будет при падении кэша
  7. Ревью. За пять минут до конца пройди по требованиям и покажи, где каждое закрыто. Что не успел, назови словами

У Google SRE похожий цикл называется NALSD: сначала ответить, возможно ли это в принципе, потом можно ли лучше, потом влезает ли в реальное железо и бюджет, и наконец переживёт ли отказ машины или дата-центра

🧮 Оценка нагрузки

Здесь не нужна точность. Нужен порядок величины, чтобы понять, хватит одного Postgres или нужен шардинг, держать данные в памяти или на диске

Опорные числа для арифметики:

ЧтоСколько
Секунд в сутках86 400, для прикидки 10^5
Секунд в месяцеоколо 2,5 млн
1 запрос в секундуоколо 2,5 млн запросов в месяц
Обращение к памяти100 нс
Случайное чтение 4 КБ с SSD150 мкс
Запрос туда и обратно внутри дата-центра500 мкс
Последовательное чтение 1 МБ с SSD1 мс
Пакет из Калифорнии в Нидерланды и обратно150 мс

Числа задержек из классической таблицы «Latency numbers every programmer should know». Железо с тех пор ускорилось, но порядок соотношений тот же: память на три порядка быстрее SSD, а запрос через океан в 300 раз дольше запроса внутри дата-центра

Посчитаем сокращатель ссылок. Допустим, интервьюер согласился на 1 млн новых ссылок и 100 млн переходов в сутки:

  • запись: 1 млн / 86 400 ≈ 12 в секунду
  • чтение: 100 млн / 86 400 ≈ 1 200 в секунду, чтений в 100 раз больше, чем записей
  • пик: трафик неровный, закладываем в несколько раз больше среднего. Коэффициент назови вслух, например 5, тогда около 6 000 чтений в секунду
  • объём: запись около 500 байт (код, длинный URL, автор, дата), 500 МБ в сутки, около 180 ГБ в год
  • длина кода: за 10 лет наберётся 3,65 млрд ссылок. 62 символа в шести позициях дают 62^6 ≈ 57 млрд вариантов, хватит шести символов

Из этих цифр выходят решения. Запись в 12 в секунду выдержит один Postgres с большим запасом. 180 ГБ в год тоже не проблема для одной базы на первые годы. Упираемся только в чтения, и они просятся в кэш. Даже 10 млн горячих ссылок по 500 байт — это 5 ГБ, они помещаются в один Redis

🛠️ Три типовые задачи

Сокращатель ссылок

Схема простая: сервис ссылок за балансировщиком, Postgres с таблицей links(code PK, url, user_id, created_at), Redis перед ним для переходов. Всё интересное в двух вопросах

Как получить код. Есть три способа:

СпособКак работаетЧем платишь
Счётчик и base62Берём следующий id из последовательности и переводим в 62-ричную системуКоды идут подряд, все ссылки можно перебрать. Одна последовательность на всех: сервисы берут id блоками по тысяче
Хеш от URLMD5 от URL, первые 7 символов в base62Коллизии: проверяем уникальность и при совпадении пересчитываем с солью
Случайный код7 случайных символов, вставка с уникальным индексомПри конфликте повтор. Пока база заполнена на доли процента, повторы редкие

Go · Перевод id в base62

package main

import "fmt"

const alphabet = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"

// encode переводит id из счётчика в короткий код
func encode(id uint64) string {
	if id == 0 {
		return string(alphabet[0])
	}
	var buf [11]byte // 62^11 > 2^64, длиннее 11 символов код не бывает
	i := len(buf)
	for id > 0 {
		i--
		buf[i] = alphabet[id%62]
		id /= 62
	}
	return string(buf[i:])
}

func main() {
	fmt.Println(encode(125), encode(1_000_000), encode(3_650_000_000))
	// 21 4c92 3Z11JK
}

Какой редирект отдавать. 301 по стандарту HTTP кэшируется по умолчанию: браузер запомнит адрес и больше к тебе не придёт, а ты не посчитаешь переходы и не сможешь отключить вредную ссылку. 302 по умолчанию не кэшируется, каждый переход проходит через сервис. Если нужна аналитика, отвечай 302: каждый переход придёт к тебе, и эту нагрузку примет кэш

Лента новостей

Пользователь открывает ленту и видит свежие посты тех, на кого подписан. Есть два пути:

  • fan-out on write: при публикации поста кладём его id в готовую ленту каждого подписчика, например в список в Redis. Чтение ленты мгновенное, зато запись дорогая: у автора с тысячей подписчиков одна публикация превращается в тысячу вставок
  • fan-out on read: лента собирается в момент открытия, из последних постов всех подписок. Запись дешёвая, чтение тяжёлое, а лент открывают намного больше, чем пишут постов

В разборе этой задачи в system-design-primer заложено 500 млн постов в сутки и в среднем 10 доставок на пост. Это 5 млрд вставок в ленты в сутки, около 60 000 в секунду, против 100 000 чтений ленты в секунду. Отсюда стандартный ответ: гибрид. Обычным авторам раскладываем посты по лентам при записи. Авторам с миллионами подписчиков не раскладываем: их свежие посты подмешиваем при чтении и пересортировываем. В кэше держим только несколько сотен последних записей и только ленты активных пользователей, остальным собираем ленту из базы при входе

Рассылка уведомлений

Сервису нужно отправить push, письмо или SMS по событию: заказ оплачен, пришло сообщение. Скорость тут вторична. Главное — гарантии: уведомление не теряется, не уходит дважды и не будит человека в три часа ночи

  1. Сервис-источник публикует событие через outbox, чтобы оно не пропало между коммитом и отправкой
  2. Сервис уведомлений проверяет настройки пользователя (на что подписан, тихие часы), выбирает канал, собирает текст из шаблона
  3. Кладёт задачу в отдельную очередь на каждый канал. Упавший провайдер SMS не тормозит push
  4. Воркеры отправляют провайдеру: APNs, FCM, SMTP. Ошибку повторяют с задержкой, после нескольких попыток задача уходит в DLQ
  5. Перед отправкой воркер проверяет notification_id в таблице отправленных: брокер доставляет хотя бы раз, и без этой проверки повтор дойдёт до человека вторым письмом

Поверх всего стоят лимиты: не больше N уведомлений в час одному человеку и своя скорость на каждого провайдера, у него тоже квота

⚠️ Где ошибаются

  • Рисуют схему с первой минуты. Через двадцать минут выясняется, что интервьюер имел в виду другой масштаб или другую функцию. Сначала требования, даже если задача знакома: проговори их и согласуй
  • Сразу строят «как в Google». Шардинг, Kafka и десять микросервисов на 12 записей в секунду говорят интервьюеру, что ты не посчитал нагрузку. Начни с простого и усложняй, когда цифры заставляют
  • Называют технологию без причины. «Тут Cassandra» без объяснения ничего не стоит. Нужна причина и цена: «запись в десять раз чаще чтения, а транзакции не нужны, поэтому колоночная база, но тогда теряем произвольные запросы»
  • Не думают об отказах. Что будет, если упал кэш, отстала реплика, провайдер SMS отвечает за 30 секунд? Каждый такой вопрос от интервьюера показывает, что сам ты на него не посмотрел
  • Молчат. Интервьюер не видит мыслей. Рассуждения вслух, даже с ошибкой, которую ты потом сам поправил, оцениваются лучше, чем правильная схема, нарисованная молча

🎯 Вопросы с собеседований

Спроектируй сокращатель ссылок. С чего начнёшь?

С требований: только сокращение и переход или ещё аналитика, свои алиасы и срок жизни. Потом прикину нагрузку: при 1 млн ссылок и 100 млн переходов в сутки это 12 записей и 1 200 чтений в секунду, хранение около 180 ГБ в год. Отсюда схема: сервис за балансировщиком, Postgres с кодом в первичном ключе, Redis для переходов. Код получаю из счётчика через base62, шести символов хватит на десятилетия

301 или 302 для редиректа?

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

Как генерировать короткие коды без коллизий?

Счётчик плюс base62 коллизий не даёт вовсе: каждый id уникален. Чтобы последовательность не стала узким местом, каждый экземпляр сервиса берёт себе блок id и раздаёт его из памяти. Минус: коды идут подряд, и все ссылки можно перебрать. Если это важно, беру случайный код из 7 символов с уникальным индексом и повтором при конфликте

Лента: fan-out on write или on read?

On write делает чтение быстрым, потому что лента уже собрана, но публикация у автора с миллионом подписчиков становится миллионом вставок. On read наоборот, дешёвая запись и тяжёлое чтение, а читают ленту намного чаще. Обычно гибрид: обычным авторам раскладываем при записи, популярных подмешиваем при чтении

Как сделать, чтобы уведомление не ушло дважды?

Брокер доставляет хотя бы раз, поэтому повторы будут, вопрос в том, кто их отсечёт. У каждого уведомления свой id, воркер записывает его в таблицу отправленных с уникальным индексом и отправляет, только если записи не было. Остаётся окно, когда провайдер принял сообщение, а воркер упал до записи: его закрывает ключ идемпотентности у провайдера, если он есть, иначе редкий дубль принимают как цену

Что будет, если упадёт Redis перед базой?

Все чтения уйдут в Postgres разом. При 6 000 чтений в секунду в пике одна база может не выдержать, и упадёт уже она. Поэтому кэш ставят в нескольких экземплярах, на клиенте ставят таймаут и circuit breaker, а на базу держат запас и реплики для чтения

База не справляется с записью. Что делать?

Сначала понять, во что упираемся: индексы, блокировки, диск. Часто хватает убрать лишние индексы, писать пачками или вынести тяжёлую запись в очередь. Реплики тут не помогут, они разгружают только чтение. Если одна машина не тянет и после этого, шардирую по ключу, по которому идут запросы, например по user_id, и заранее думаю, как переносить данные при добавлении шарда

📚 Что почитать