Четыре классические задачи системного дизайна — от требований до узких мест. С цифрами, компромиссами и тем, что хочет услышать интервьюер.
Каждая задача идёт по этой схеме. Сами приёмы разобраны в подходе, масштабировании, данных и распределённых системах; здесь — применение. Листайте стрелками ← →, свайпом или кнопками внизу.
Посчитайте нагрузку. Главный вывод интервьюер ждёт сам: байты — дорого, метаданные — много мелких запросов. Это две разные системы.
POST /commit {path, base_rev, chunks:[хеши]}
→ 200 {rev} · 409 конфликт
→ 428 {missing:[h3,h7], upload_urls}
GET /delta?cursor=1050 → изменения, cursor
GET /notify?cursor=1050 # long-poll
namespace_id): file(ns, path, rev, chunks[]), chunk(hash, size, refcount), журнал изменений namespace с курсором.sha256. Через сервис они не идут: клиент пишет напрямую по presigned URL.Файл режется на куски, каждый адресуется хешем содержимого. Сервер хранит кусок один раз, клиент загружает только те, которых у сервера нет.
Нажимайте правки и сравните, сколько кусков придётся загрузить.
Попробуйте: выключите сеть у B, поправьте файл на обоих устройствах и включите сеть.
node_modules — 50 тысяч файлов по 2 КБ: упирается в метаданные, а не в байты. Пакетные коммиты, мелкие куски склеивают в один объект.Дедупликация общая на всех пользователей: клиент присылает хеш куска, и если такой кусок есть, загрузку пропускает. Что здесь не так?
Двигайте ползунки: память почти не меняется, а записей в секунду — сотни тысяч.
Карта делится на ячейки (geohash, S2 у Google, H3 у Uber), водитель хранится в своей. Поиск — это рассматриваемая ячейка и её соседи: точка у границы иначе не увидит машину в метре через край.
Нажмите на карту, чтобы поставить пассажира. Радиус поиска — 1 км.
# водитель, раз в 4 с:
GEOADD drv:msk 37.62 55.75 d42
# пассажир ищет машины рядом:
GEOSEARCH drv:msk FROMLONLAT 37.61 55.76
BYRADIUS 1 km ASC COUNT 20
# бронь водителя на 15 с:
SET lock:d42 ride:981 NX PX 15000
Шардируем по городу или по крупной ячейке: поиск почти всегда попадает в один шард. Цена — неравномерность. Концерт закончился — 40 тысяч человек на стадионе открывают приложение, и один шард получает поисков больше, чем весь остальной город.
Включите событие, затем попробуйте разные меры.
Розовым — три места, которые интервьюер попросит раскрыть.
Нельзя просто взять очередь URL и раздать воркерам: подряд идут ссылки с одного сайта, и робот положит его. Поэтому URL раскладывают по очередям хостов, а для каждого хоста помнят, когда к нему можно снова.
Crawl-delay). Перед этими очередями — очереди приоритетов: важные страницы раньше.Добавьте 30 URL с одного сайта, потом с разных — и сравните скорость.
#фрагмент, порядок и мусор в параметрах (utm_*, sessionid). Потом проверка «уже видели» — фильтр Блума: 10 млрд URL при 1% ложных срабатываний — ~12 ГБ. Ложное срабатывание — пропущенная новая страница, это приемлемо.?page=… без конца, идентификатор сессии в каждой ссылке. Защита — лимит глубины и длины URL, бюджет страниц на хост, детектор повторяющихся шаблонов пути.Frontier распределён по 50 узлам. Как разбить URL между ними?
Crawl-delay, robots.txt, DNS. При hash(host) всё это локально на одном узле, и пауза соблюдается без координации. При hash(url) 50 узлов одновременно ходят на один сайт, и нужен распределённый лимитер. Перекос от гигантских сайтов лечат бюджетом на хост.UPDATE … SET views = views + 1 по одной строке — это очередь на блокировке строки: несколько тысяч в секунду, и всё.+= n.Поднимите поток просмотров и посмотрите, когда растёт очередь.
Точный подсчёт — хеш-таблица на все различные запросы: сотни миллионов ключей, десятки гигабайт в узле потоковой обработки. Для топа это не нужно.
Устройте всплеск и сравните топ за 5 минут с топом за всё время.
События разбиты на 10 партиций по user_id. Каждая партиция считает свой топ-10 запросов, агрегатор сливает десять списков. Получится точный глобальный топ-10?
hash(query): каждый запрос считается целиком в одной партиции, и слияние локальных топов становится точным. Перед этим можно частично агрегировать на стороне продюсера.Похожие приёмы в задачах первой части — в разборе задач 1.
Сначала цифры, потом схема, потом — где она сломается.