Задачи System Design
Задачи с условием, требованиями и масштабом. Каждую решают у доски: 45 минут, интервьюер видит схему, проверка читает её по семи осям.
48 задач
Все задачи
ЛёгкаяГенератор уникальных идентификаторов64 бита на время, номер и счётШестьдесят четыре бита делят между временем, номером генератора и счётчиком, и у каждого деления есть срок годности. Случайные 64 бита при двух миллионах выдач в секунду дадут первое совпадение примерно через 45 минут, UUID не помещается в bigint, а опасны два сбоя: два генератора с одним номером и часы, которые пошли назад.
СредняяGoogle Calendarсобытия, повторы и часовые поясаНесколько сотен записей в секунду — масштаб здесь ничего не решает. Решает время: повторяющееся событие нельзя развернуть заранее, а событие в 10:00 по местному времени и в 07:00 UTC — не одно и то же дважды в год.
СредняяImage Serviceхранение и раздача картинокПринять два терабайта картинок в сутки, подготовить варианты и отдавать их за сто миллисекунд в любой точке мира. Нерв задачи в том, как байты попадают в хранилище и выходят из него и в какой момент чужой файл можно показывать.
СредняяInstagramфотографии, подписки и лентаВосемь публикаций в секунду и триста пятьдесят открытий ленты — запись здесь бесплатна. Вся задача в том, что у одного автора сто подписчиков, а у другого десять миллионов, и одна стратегия сборки ленты их не покрывает.
СредняяNotification Serviceуведомления по каналамОдно уведомление — это несколько доставок в разные каналы, каждая со своим поставщиком и своим способом упасть. И одно правило важнее всех остальных: промо-рассылка на десять миллионов не должна задержать сброс пароля.
СредняяPastebinсервис текстовых сниппетовВставил текст — получил ссылку. Идентификатор короткий и случайный, но дальше начинается своё: тело, срок жизни, приватность и вирусный горячий ключ, который кладёт систему в одной точке.
СредняяRate Limiterограничение частоты запросовРешить за две миллисекунды, пропустить запрос или отдать 429. Данных здесь почти нет: вся задача в том, как держать общий счётчик на десятках инстансов API и что делать, когда хранилище счётчиков недоступно.
СредняяSpotifyкаталог, потоковое аудио и плейлистыПятьдесят восемь гигабайт в секунду раздачи — и каталог в пятьсот терабайт на одно качество, который почти не растёт. Конечность каталога и есть решение: закодировать один раз и отдавать из сети доставки.
СредняяURL Shortenerсокращатель ссылок уровня Bit.lyСократить длинную ссылку и отдавать по короткой мгновенный редирект. Запись здесь тривиальна: вся задача в дешёвом чтении под нагрузкой и в уникальном коротком коде на миллиарде ссылок.
СредняяWeb Crawlerобход вебаПолтора гигабита в секунду не проблема. Проблема в том, что с каждого сайта можно брать одну страницу в секунду, а почти все найденные ссылки ведут туда, где мы уже были.
СредняяWebhook Systemприём событий от внешних системПриём событий от внешних сервисов, где нагрузки почти нет, а вся трудность в семантике доставки: событие придёт дважды, придёт не по порядку и однажды не обработается вовсе.
СредняяБронирование мест и номеровПятьдесят тысяч человек приходят за пять тысяч мест в одну минуту. Ресурс именной и конечный: место 14 в ряду 7 существует в одном экземпляре и не заменяется соседним.
СредняяОнлайн-аукцион: ставки и закрытие лотаПятьсот ставок в секунду в один лот, и каждая обязана сравниться с текущим максимумом: такую конкуренцию не размазать, её выстраивают в очередь. И лот, который закрывается сам, ровно в объявленную секунду.
СредняяПодсказки при вводеПодсказок в восемь раз больше, чем самих поисков, а предрасчёт для всех префиксов стоит сотни гигабайт. Задача не про префиксное дерево, а про то, что в него не помещается.
СредняяПоиск заведений рядомОдин и тот же запрос «в радиусе пяти километров» находит двадцать заведений в пригороде и двадцать тысяч в центре города. Задача про то, как уложиться в 300 мс при таком разбросе плотности.
СредняяПоиск по каталогу маркетплейсаПолнотекстовый поиск по ста миллионам товаров — решённая задача. Нерешённая рядом: счётчики у значений фильтров, которые зависят от выбранных фильтров и пересчитываются на каждый запрос, тысячи раз в секунду.
СредняяПриложение знакомств: колода и взаимный лайкЛента, где повтор ломает продукт, а матч должен возникнуть ровно один раз, даже когда двое лайкнули друг друга одновременно. Нерв задачи — дёшево помнить, что человеку уже показывали, и закрыть гонку взаимного лайка.
СредняяРаспределённый кэшКэш превращает миллион запросов в секунду в пятьдесят тысяч к базе. Вся задача — удержать это соотношение, когда узел добавили, узел потеряли, кластер поднялся пустым или истёк горячий ключ.
СредняяСчётчик просмотров объявленийЗадача выглядит как «прибавить единицу» и на этом ловит. Настоящий вопрос — что считать: обновление страницы, человека или человека за сутки. От ответа зависит, уместится ли счёт в 800 МБ или потребует терабайт.
СредняяТаблица лидеров сезонаместо каждого из 400 миллионовПока таблица помещается в один узел, место игрока — одна команда. На 400 миллионах игроков таблицу режут на шарды, и позиция игрока в своём шарде уже ничего не говорит о его месте в сезоне. Как ответить «какое я место» каждому из 400 миллионов, пока результаты идут по сто пятьдесят тысяч в секунду, — вся задача.
СложнаяCoinKeeperучёт личных финансов с импортом из банкаСервис личных финансов: ручные доходы и расходы плюс импорт операций из банка. Нерв задачи — узкое место вне вашей системы, лимит банка, и две разные цены ошибки: ручная запись не должна потеряться, а импортированная — продублироваться.
СложнаяDistributed Job Schedulerзадания по расписаниюМиллионы заданий, и каждую секунду надо знать, у каких подошло время. Плюс честный ответ на главный вопрос: «ровно один раз» недостижимо, достижимы аренда против одновременности и идемпотентность против повторов.
СложнаяGoogle Mapsкарта, маршруты и живые пробкиПолмиллиона запросов в секунду за картинкой карты и пятьдесят тысяч за маршрутом — это две разные системы под одним приложением. Вся задача в том, чтобы не проектировать их как одну.
СложнаяLeetCodeзапуск чужого кода и живая таблица результатовЗапуск незнакомого и возможно враждебного кода и живая таблица результатов на сто тысяч участников. Две почти не связанные задачи под одним продуктом: изоляция исполнения и ранжирование в реальном времени.
СложнаяLive-комментариипоток под трансляциейТысяча комментариев в секунду и миллион зрителей дают миллиард сообщений в секунду. Нерв задачи — какая часть этого потока должна дойти до экрана и как найти открытое соединение зрителя среди сотен процессов.
СложнаяRAGответы по корпусу документовОтветы по закрытому корпусу, где у каждого документа свои права. Нерв задачи: нужный фрагмент должен попасть в контекст покупной модели, а попал ли он, надо уметь измерить.
СложнаяUberподбор водителя и поток координатШестьсот тысяч обновлений координат в секунду против двухсот тридцати заказов: основную нагрузку создаёт телеметрия. Плюс подбор, где одна заявка и один водитель должны совпасть ровно один раз.
СложнаяWhatsAppдоставка сообщений и офлайнБольше миллиона сообщений в секунду, несколько устройств у каждого получателя и требование не хранить сообщение дольше, чем нужно для доставки. Нерв задачи в том, что считать доставленным и когда сообщение можно удалить.
СложнаяX (Twitter)лента, репосты, счётчики и поискТвит весит полкилобайта, но публикация автора с десятками миллионов подписчиков — это миллионы вставок в чужие ленты. Нерв задачи: разлёт в ленты, счётчики на вирусном твите и поиск, который находит твит через секунды.
СложнаяYouTubeзагрузка, перекодирование и раздача видеоФайл в 256 ГБ нельзя передать одним запросом, перекодировать одним потоком и раздать с одного сервера, а смотреть его начинают за полсекунды. Задача про то, что делать с размером на каждом из этих трёх этапов.
СложнаяАгрегация рекламных событийпредварительно сейчас, точно к утруМинута отчёта должна появиться через секунды, а итог дня, по которому выставят счёт, — совпасть с сырыми событиями до штуки. Между этими цифрами телефоны, досылающие события через часы, повторы, упавшие узлы и ошибки в коде. Задача — один код, который даёт обе цифры и умеет пересчитать прошлое.
СложнаяБиржа: книга заявок и раздача котировокОднопоточное исполнение здесь — решение, а не ограничение: оно даёт детерминизм. А произведение изменений на подписчиков не помещается ни в какую сеть, и выбрасывать изменения нельзя: доставляется не каждое изменение, а верное текущее состояние.
СложнаяДрузья рядомпоток координат по графу дружбыДрузья в радиусе 5 км вживую: 333 тысячи координат в секунду, у каждой свой круг получателей, и этот круг постоянно меняется. Нерв задачи в адресной рассылке и в отзыве доступа, который должен обогнать следующую координату.
СложнаяИнференс языковой моделиДвенадцать запросов в секунду, а ограничен дорогой ускоритель: его память и время. Нерв задачи в том, чтобы карта не простаивала и не переполнялась.
СложнаяКорзина и оформление заказаЧетыреста попыток в секунду зарезервировать один и тот же остаток и три владельца данных, которых нельзя закрыть одной транзакцией. Нерв задачи: деньги и остаток, объём здесь невелик.
СложнаяМультирегионклассы данных, репликация и отказ регионаСкорость света не оптимизируется, и все решения здесь про то, как не ждать сто пятьдесят миллисекунд там, где ждать нельзя, и что делать с данными, которые ждать обязаны. Отказ региона и требования к размещению данных добавляют ещё два ограничения.
СложнаяОбъектное хранилищеСто петабайт хранит любой набор дисков. Трудность в другом: знать, где лежат сто миллиардов объектов, и отвечать на это за миллисекунды. Задача про каталог, а не про байты.
СложнаяОчередь сообщенийГигабайт в секунду пишется на обычные диски легко — если писать последовательно в конец файла. Всё устройство подчинено этому: журнал вместо очереди, позиция вместо статуса, порядок только внутри раздела.
СложнаяПлатёжный шлюз и кошелёкТысяча операций в секунду — нагрузки здесь нет. Задача про то, как из повторов сложить списание ровно один раз, когда внешний эквайрер отвечает когда хочет, а баланс должен быть проверяем.
СложнаяПочтовый сервисПоловина этой системы вам не принадлежит. Чужой сервер отвечает когда захочет, может принять письмо и положить в спам, а может отказать без объяснения.
СложнаяРаспределённое KV-хранилищеСогласованность выбирается в каждом запросе, а реплики обязаны сойтись к одному содержимому, пока часть кластера всегда недоступна.
СложнаяРекламный аукцион и учёт показовВыбрать победителя из двух тысяч кандидатов за пятьдесят миллисекунд и не потратить чужой бюджет сверх согласованного. Точность и задержка здесь обе стоят денег, и размен между ними приходится называть числом.
СложнаяРекомендательная системаЛента рекомендаций на сто миллионов человек в сутки. Правильного ответа у неё нет, а система учится на данных, которые сама же породила.
СложнаяСбор метрик с миллиона серверовДесять миллионов точек в секунду — решаемая задача. Систему убивает число уникальных рядов: метка с идентификатором запроса порождает новые ряды быстрее, чем хранилище успевает их принимать.
СложнаяСинхронизация файлов между устройствамиФайл правится на трёх устройствах, часть из них была офлайн, и все обязаны прийти к одному состоянию, не потеряв ничью правку молча. Нерв задачи: найти изменения среди десятков тысяч файлов и не гонять по сети мегабайты ради небольшой правки.
СложнаяСовместное редактирование документаДвести тысяч операций в секунду здесь не проблема, и рассылка правок почти не множит трафик. Вся задача в том, что две правки одного диапазона текста — это не гонка, а обычный режим работы, и его надо спроектировать, а не предотвратить.
СложнаяТоп-K по потоку событийЕсли каждый узел считает свой топ-100 и результаты складываются, ответ может оказаться неверным при безупречных логах. Задача про условия, при которых частичные результаты складываются.
СложнаяЦифровой кошелёкмиллион переводов в секунду между разделамиВнутренний кошелёк, в котором перевод связывает два произвольных счёта, а в пик их миллион в секунду. Нерв задачи — перевести деньги между счетами на разных узлах так, чтобы они не появились из ниоткуда и не пропали.