Полное руководство по собеседованию на должность системного дизайнера в 2022 году

В начале года мы опубликовали руководство «Системный дизайн в 2022 году», чтобы помочь вам сориентироваться в мире системного дизайна. В нем подробно описаны фундаментальные концепции системного проектирования и приведены ссылки на соответствующие ресурсы, которые помогут вам глубже понять их. Как от разработчика, от вас будут все больше ожидать понимания и применения концепций системного проектирования в вашей работе. По мере накопления опыта и продвижения по карьерной лестнице вопросы системного проектирования будут занимать все большее место в процессе собеседования. Поэтому важно изучить основы системного проектирования, чтобы обеспечить себе успех в карьере и на собеседованиях.

С помощью этого руководства мы хотим помочь вам подготовиться к собеседованию по системному дизайну. Мы надеемся помочь вам понять следующее:

• Что такое собеседование по системному дизайну?
• Как подготовиться к собеседованию по системному дизайну
• Фундаментальные концепции и модели на собеседовании по проектированию системы
  • Теорема PACELC
  • Heartbeat
  • AJAX опрос
  • Длительный опрос HTTP
  • WebSockets
  • События, отправляемые сервером (SSE)
• Разбор распространенных вопросов интервью по проектированию систем
  • Проектирование Uber
  • Дизайн TinyURL
  • Дизайн Instagram
• Список распространенных вопросов собеседования по системному дизайну
• Как подойти к любому вопросу собеседования по системному дизайну
• Шпаргалка для собеседования по системному дизайну
• Ресурсы для собеседования по системному дизайну

Давайте начнем!

Что такое собеседование по разработке системы?

В своем блоге соучредитель и генеральный директор компании Educative Фахим уль Хак рассказывает о том, как развивалось собеседование по кодированию за последние 25 лет, и делится тем, чего мы можем ожидать в будущем. Некоторые из ключевых моментов включают:

• В начале 2000-х годов компании фокусировались на части интервью, связанной с кодированием, а также на «мозговых тизерах». Основная идея заключалась в том, что креативность и навыки решения проблем связаны с успешным кодированием. Проблема с этими «мозговыми тизерами» заключалась в том, что многие вопросы требовали знания реальных сценариев, которые на самом деле не отражали реальных проблем программирования.
• Затем произошло то, что известно как «Веб 2.0» и рост социальных сетей. Использование Интернета стало массовым, и возникла необходимость в высокоэффективных и масштабируемых крупномасштабных системах. Разработка приложений, ориентированных на потребителя, двигалась в сторону веба и кросс-платформенных операций.
  • В это время интервьюирование начало меняться. Google перестал использовать «мозговые тизеры» и заставлял кандидатов решать реальные проблемы с помощью кода. Распределенные системы существовали, но еще не было устоявшихся лучших практик. Вопросы масштабирования решались органически, а не алгоритмически, а «системный дизайн» только начинал входить в круги программистов.
• В середине 2000-х годов ситуация начала меняться. Появились MapReduce, BigTable и масштабируемое управление данными, и начали формироваться методы работы с большими системами. Затем пришло время облачных вычислений.
  • В это время интервью начали меняться еще больше. В 2012 году Facebook добавил «Проектирование систем» в циклы собеседований. «Игрушечные» проблемы стали стандартизированными. Все это привело к нынешней эпохе интервью с кодированием.
• Сейчас мы видим, что интервью по кодингу — это живой организм, который постоянно меняется в ответ на потребности продукта и рынка и изменения архитектуры. При проведении собеседования сегодня очень важно вернуться к основам разработки программного обеспечения, системного проектирования, структур данных и алгоритмов, а также понять, как компоненты связаны друг с другом в объектно-ориентированном программировании и многозвенных системах.
  • Мы также знаем, что собеседования в разных компаниях немного отличаются друг от друга. Например, собеседование в Amazon включает в свои вопросы принципы лидерства. Важно изучить компанию, в которой вы проводите собеседование, чтобы подготовиться к различным нюансам, которые существуют в разных компаниях.

В статье «Полное руководство по системному проектированию в 2022 году» на сайте Educative мы рассказываем, почему так важно изучать системное проектирование в качестве разработчика. Вкратце, это важно потому, что на протяжении всей вашей карьеры от вас будут все больше ожидать понимания концепций системного дизайна и их применения. На ранних этапах вашей карьеры концепции системного проектирования помогут вам уверенно решать задачи по разработке программного обеспечения. На более поздних этапах вашей карьеры системное проектирование станет гораздо более важной частью процесса собеседования. Компании хотят видеть, что вы умеете работать с масштабируемыми, распределенными крупномасштабными системами.

Теперь, когда мы знаем немного больше о собеседовании по системному дизайну, давайте обсудим, как к нему подготовиться.

Как подготовиться к собеседованию по проектированию систем

В книге «Как подготовиться к собеседованию по разработке системы в 2022 году» генеральный директор и соучредитель компании Educative Фахим уль Хак делится тем, чему он научился, проводя сотни собеседований по разработке системы в Microsoft, Facebook, а теперь и в Educative. Вот несколько основных выводов:

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

Почему важно подготовиться стратегически

Как уже упоминалось ранее, способ подготовки к собеседованию в Amazon, вероятно, будет отличаться от способа подготовки, например, в Slack. Хотя в целом процесс собеседования в разных компаниях имеет общие черты, есть и явные различия, к которым вы должны подготовиться. Это одна из причин, почему стратегическая подготовка так важна. Если вы намеренно и тщательно составите план подготовки к собеседованию, вы будете чувствовать себя более уверенно в долгосрочной перспективе.

CodingInterview.com — это отличный бесплатный ресурс, содержащий более 20 руководств по прохождению собеседований в конкретных компаниях, которые помогут вам максимально увеличить шансы на успех.

Основополагающие понятия на собеседовании по системному дизайну

Полное руководство по проектированию систем в 2022 году на сайте Educative охватывает большинство основ распределенных систем и проектирования систем. Я рекомендую начать свое путешествие именно с него. В этом руководстве мы рассмотрим некоторые концепции, которые не освещены в другом руководстве.

Теорема PACELC

Вопрос, на который не отвечает теорема CAP: «Какие возможности есть у распределенной системы, если нет сетевых разделов?». Теорема PACELC отвечает на этот вопрос.

Теорема PACELC утверждает следующее о системе, которая реплицирует данные:

Первые три буквы теоремы, PAC, те же, что и в теореме CAP. Расширением здесь является ELC. Теорема предполагает, что мы поддерживаем высокую доступность путем репликации. Когда происходит сбой, преобладает теорема CAP. Если сбоя нет, нам все равно придется учитывать компромисс между согласованностью и латентностью реплицированной системы.

Примерами системы PA/EC являются BigTable и HBase. Они всегда будут выбирать согласованность, отказываясь от доступности и меньшей латентности. Примерами системы PA/EL являются Dynamo и Cassandra. Они выбирают доступность вместо согласованности, когда происходит разделение. В противном случае они выбирают меньшую задержку. Примером системы PA/EC является MongoDB. В случае раздела она выбирает доступность, но в остальном гарантирует согласованность.

Чтобы узнать больше об этих системах, прочитайте статью «Распределенные системы для практиков» на сайте Educative.

Сердцебиение

Сердцебиение — это механизм, который помогает нам обнаружить сбои в распределенной системе. Если есть центральный сервер, то все серверы периодически посылают на него сообщение heartbeat, чтобы показать, что он все еще жив и функционирует. Если центрального сервера нет, все серверы случайным образом выбирают набор серверов и посылают этому набору сообщение о сбое каждые несколько секунд. Таким образом, если в течение некоторого времени не поступает никаких сообщений о сердцебиении, система может заподозрить, что произошел сбой или авария.

Чтобы узнать больше о сердцебиении, прочитайте статью Grokking the System Design Interview на сайте Educative.

Опрос AJAX

Опрос — это стандартная техника, используемая большинством приложений AJAX. Идея заключается в том, что клиент многократно опрашивает сервер для получения данных. Клиент делает запрос и ждет ответа сервера с данными. Если данных нет, сервер возвращает пустой ответ.

Чтобы узнать больше об опросе AJAX, прочитайте статью Масштабируемость и проектирование систем для разработчиков на сайте Educative.

Длительный опрос HTTP

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

Чтобы узнать больше о HTTP long-polling, прочитайте статью Scalability & System Design for Developers на сайте Educative.

WebSockets

WebSocket обеспечивает полнодуплексные каналы связи через одно TCP-соединение. Он обеспечивает постоянное соединение между клиентом и сервером. Обе стороны могут использовать это соединение, чтобы начать отправку данных в любое время. Клиент устанавливает соединение через WebSocket handshake. Если процесс проходит успешно, сервер и клиент могут начать обмен данными в обоих направлениях в любое время.

Чтобы узнать больше о WebSockets, прочитайте статью Масштабируемость и проектирование систем для разработчиков на сайте Educative.

События, отправляемые сервером (SSEs)

Клиент может установить долгосрочное соединение с сервером с помощью SSEs. Сервер использует это соединение для отправки данных клиенту. Если клиент хочет отправить данные на сервер, для этого необходимо использовать другую технологию или протокол.

Чтобы узнать больше о событиях, отправляемых сервером, ознакомьтесь со статьей Scalability & System Design for Developers на сайте Educative.

Как упоминалось выше, для более полного обзора основ ознакомьтесь с полным руководством по проектированию систем в 2022 году. Для практической работы с этими основами ознакомьтесь с Scalability & System Design for Developers.

Обзор распространенных вопросов собеседования по системному проектированию

Существует множество различных вопросов, с которыми вы можете столкнуться во время собеседования по системному проектированию. Сегодня мы рассмотрим три распространенных вопроса и их решения. В конце этого раздела мы предоставим вам ресурс, где вы сможете узнать о более распространенных вопросах SDI.

Дизайн Uber

Этот пример решения проблемы взят из другой статьи. Для получения более подробного руководства мы рекомендуем ознакомиться с проектом Design Uber на сайте Educative. Там вы сможете глубже изучить примеры использования и дополнительные вопросы и соображения.

Обзор проблемы

При проектировании Uber необходимо учитывать два типа пользователей: водители и пользователи. Требования к системе следующие:

• Водители могут часто уведомлять сервис о местоположении и доступности.
• Пользователи могут видеть всех ближайших водителей в режиме реального времени
• Пользователи могут запросить поездку, указав место назначения и время забора.
• Близлежащие водители получают уведомление, когда пользователю требуется поездка.
• После того как поездка принята, водитель и пользователь могут видеть местоположение друг друга на протяжении всей поездки.
• После завершения поездки водитель завершает поездку и становится доступным для других пользователей.

Ограничения

Ограничения очень важно учитывать перед проектированием Uber. Эти ограничения обычно различаются в зависимости от времени суток и местоположения. Мы будем проектировать Uber со следующими ограничениями и оценками:

• 300 миллионов пользователей и 1 миллион водителей в системе
• 1 миллион активных клиентов и 500 тысяч активных водителей в день
• 1 миллион поездок в день
• Все активные водители сообщают о своем текущем местоположении каждые три секунды
• Система связывается с водителями в режиме реального времени, когда пользователь запрашивает поездку.

Проектные соображения

• Нам необходимо обновлять структуры данных для отражения местоположения водителей каждые три секунды. Чтобы обновить водителя до нового местоположения, нам нужно найти подходящую сетку на основе его предыдущего местоположения.
• Если новое местоположение не принадлежит к текущей сетке, нам нужно удалить водителя из сетки и снова вставить его в соответствующую сетку. Если новая сетка достигает максимального предела, мы должны переразбить ее.
• Нам нужен быстрый механизм для распространения информации о текущем местоположении ближайших водителей среди пользователей в этом районе. Наша система должна уведомлять водителя и пользователя о местонахождении автомобиля в течение всего времени поездки.

Принимая во внимание эти соображения, мы можем определить, что QuadTree не является идеальным вариантом, поскольку мы не можем гарантировать, что дерево будет обновляться так быстро, как это требуется нашей системе. Мы можем хранить последнюю позицию водителя в хэш-таблице и обновлять наше QuadTree реже. Мы хотим гарантировать, что текущее местоположение водителя будет отражено в QuadTree в течение 15 секунд. Мы назовем нашу хэш-таблицу DriverLocationHT.

Решение проблемы

DriverLocationHT

Нам нужно хранить в хэш-таблице DriverID, который отражает текущее и предыдущее местоположение водителя. Это означает, что для хранения каждой записи нам потребуется 35 байт. Давайте разобьем это на отдельные части:

1. DriverID (3 байта)
2. Старая широта (8 байт)
3. Старая долгота (8 байт)
4. Новая широта (8 байт)
5. Новая долгота (8 байт)

Поскольку мы предполагаем один миллион, нам потребуется следующая память:

Теперь обсудим пропускную способность. Если мы получим DriverID и местоположение, это потребует (3 + 16 => 19 байт). Эта информация собирается каждые три секунды с 500 тысяч ежедневно активных водителей, поэтому мы получим 9,5 МБ каждые три секунды.

Для случайного распределения мы можем распределить DriverLocationHT на нескольких серверах на основе DriverID. Это поможет обеспечить масштабируемость, производительность и отказоустойчивость. Мы будем называть машины, хранящие эту информацию, «серверами расположения драйверов». Эти серверы будут делать еще две вещи. Как только сервер получит обновленную информацию о местоположении водителя, он передаст ее соответствующим пользователям. Сервер также уведомит соответствующий сервер QuadTree, чтобы обновить местоположение водителя.

Трансляция местоположения водителя

Нам нужно транслировать местоположение водителя пользователям. Мы можем использовать модель Push, чтобы сервер передавал местоположение соответствующим пользователям. Мы можем использовать службу уведомлений и построить ее на модели издателя/подписчика.

Когда пользователь открывает приложение, он будет запрашивать сервер, чтобы найти ближайших водителей. На стороне сервера мы подпишем пользователя на все обновления от ближайших водителей. Каждое обновление местоположения водителя в DriverLocationHT будет транслироваться всем подписавшимся пользователям. Это обеспечит отображение текущего местоположения каждого водителя.

Мы предположили один миллион активных пользователей и 500 тысяч активных водителей в день. Предположим, что пять пользователей подписаны на одного водителя. Мы можем хранить эту информацию в хэш-таблице для быстрого обновления.

Нам нужно хранить идентификаторы водителя и пользователя. Нам нужно 3 байта для DriverID и 8 байт для UserID, поэтому нам потребуется 21 МБ памяти:

Теперь о пропускной способности. На каждого активного водителя у нас приходится 5 подписчиков. В сумме это достигает:

Нам нужно отправлять DriverID (3 байта) и их местоположение (16 байт) каждую секунду, что требует:

Служба уведомлений

Для эффективной реализации службы уведомлений мы можем использовать либо длинный опрос HTTP, либо push-уведомления. Пользователи подписываются на ближайших водителей, когда они впервые открывают приложение. Когда новые водители появляются в их районах, нам необходимо динамически добавлять подписку на нового пользователя/водителя. Для этого мы отслеживаем область, за которой наблюдает пользователь. Однако это может оказаться довольно сложным.

Вместо того чтобы передавать эту информацию, мы можем спроектировать систему таким образом, чтобы пользователи получали информацию с сервера. Пользователи будут отправлять свое текущее местоположение, чтобы сервер мог найти ближайших водителей из нашего QuadTree. Затем клиент может обновить свой экран, чтобы отразить текущее местоположение водителей.

Для повторного разделения мы можем создать подушку безопасности, чтобы каждая сетка выросла за предел, прежде чем мы решим разделить ее. Предположим, что наши сетки могут вырасти или уменьшиться на дополнительные 10% до того, как мы их разделим. Это уменьшит нагрузку при разделении сетки.

Проектирование TinyURL

Этот пример решения задачи взят из другой статьи. Для получения более подробного руководства мы рекомендуем ознакомиться со статьей Design TinyURL на сайте Educative.

Обзор проблемы

TinyURL — это служба сокращения URL, которая создает более короткие псевдонимы для длинных URL. Пользователи выбирают эти сокращенные URL и перенаправляются на оригинальный URL. Эта услуга полезна, поскольку короткие ссылки экономят место и их легче набирать. Рассмотрим некоторые функциональные и нефункциональные требования к проектированию TinyURL:

Функциональные требования:

• Наш сервис будет генерировать более короткий псевдоним оригинального URL, который можно легко скопировать и вставить.
• Короткая ссылка должна перенаправлять пользователей на оригинальную ссылку
• Пользователи должны иметь возможность выбрать пользовательскую короткую ссылку для своего URL.
• Срок действия коротких ссылок будет истекать через определенное по умолчанию время, которое пользователи могут указать.

Нефункциональные требования:

• Система должна быть высокодоступной
• Перенаправление URL должно происходить в режиме реального времени с минимальной задержкой
• Сокращенные ссылки не должны быть предсказуемыми

Оценки пропускной способности и ограничения

Наша система будет требовательна к чтению. Будет большое количество запросов на перенаправление по сравнению с новыми сокращениями URL. Предположим, что соотношение чтения и записи будет 100:1. Чтение — это запросы на перенаправление, а запись — новые сокращения URL.

Оценка трафика

Предположим, что у нас есть 500 миллионов новых сокращений URL в месяц. Исходя из соотношения чтения и записи 100:1, мы можем ожидать 50 миллиардов перенаправлений за тот же период:

Теперь мы определим количество запросов в секунду (QPS) нашей системы. Возьмем месячную сумму в 50 миллиардов, чтобы рассчитать новые сокращения URL в секунду:

Снова применив соотношение 100:1 для чтения и записи, перенаправления URL в секунду составят:

Расчеты для хранения данных

Предположим, что мы будем хранить каждый запрос на сокращение URL и связанную с ним ссылку в течение пяти лет. Поскольку мы ожидаем, что каждый месяц будет появляться 500 миллионов новых URL-адресов, общее количество объектов, которые мы будем хранить в течение пяти лет, составит 30 миллиардов:

Пока предположим, что каждый хранимый объект будет иметь размер примерно 500 байт. Это означает, что на пятилетний период нам потребуется 15 ТБ хранилища:

Оценка пропускной способности

Мы ожидаем 200 новых URL в секунду для запросов на запись. Это делает общее количество входящих данных нашего сервиса 100 КБ в секунду:

Для запросов на чтение мы ожидаем примерно 20 000 перенаправлений URL каждую секунду. Тогда общий объем исходящих данных для нашего сервиса составит 10 МБ в секунду:

Оценка памяти

Нам нужно определить, сколько памяти нам понадобится для хранения кэша часто посещаемых горячих URL. Если следовать правилу 80/20, то 20% URL-адресов будут генерировать 80% трафика. Мы хотели бы кэшировать эти 20% горячих URL. Поскольку у нас 20 000 запросов в секунду, мы получим 1,7 миллиарда запросов в день:

Чтобы кэшировать 20% этих запросов, нам понадобится 170 ГБ памяти:

Стоит отметить, что будет много дублирующих запросов на один и тот же URL. Это означает, что реальное использование памяти будет меньше 170 ГБ.

Системные API

Мы можем использовать REST API для раскрытия функциональности нашего сервера. В этом примере показано определение API для создания и удаления URL-адресов без использования сервиса:

createURL(api_dev_key, original_url, custom_alias=None, user_name=None,
 expire_date=None)

Параметры

Дизайн базы данных

Давайте рассмотрим некоторые наблюдения о данных, которые мы храним:

• Сервис должен хранить миллиарды записей
• Сервис требователен к чтению
• Каждый объект небольшой (<1,000)
• Между каждой записью нет связей (за исключением хранения информации о том, какой пользователь создал короткую ссылку).

Схема

Теперь мы рассмотрим схемы баз данных. Нам нужна таблица для хранения информации о сопоставлениях URL, а также база данных для данных о пользователях, создавших короткие ссылки.

Какую базу данных мы должны использовать?

Лучшим выбором будет база данных NoSQL, например DynamoDB или Cassandra, поскольку мы будем хранить миллиарды строк без каких-либо связей между объектами.

Базовый дизайн системы и алгоритмы

Наша главная задача — как мы будем генерировать короткий и уникальный ключ при задании URL. Для данного примера мы сделаем это путем кодирования URL. Мы можем вычислить уникальный хэш данного URL, например MD5 или SHA256. Затем хэш можно закодировать для отображения. Эта кодировка может быть base36, base62 или base64. Сегодня мы будем использовать base64.

Теперь мы рассмотрим, каким должен быть короткий ключ: длиной в шесть, восемь или десять символов. При использовании кодировки base64 ключ из шести символов даст 64^6 = ~68,7 миллиарда возможных строк. Восьмисимвольный ключ даст 64^8 = ~281 триллион возможных строк. Предположим, что шестисимвольного ключа достаточно.

При использовании алгоритма MD5 наша хэш-функция выдаст 128-битное хэш-значение. Каждый символ base64 кодирует шесть битов хэш-значения. Это означает, что после кодирования мы получим строку из более чем 21 символа. Нам потребуется другой подход к выбору ключа, поскольку у нас есть место только для восьми символов в коротком ключе.

Мы можем взять для ключа первые шесть (или восемь) букв. Нам нужно предпринять шаги, чтобы исключить дублирование ключей. Мы можем поменять местами некоторые символы или выбрать символы, которых еще нет в строке кодировки, но здесь есть некоторые потенциальные препятствия:

• Если несколько пользователей введут один и тот же URL, они получат одну и ту же короткую ссылку.
• Части URL-адреса могут быть закодированы URL-адресом.

Обходным решением этой проблемы может стать добавление номера из последовательности к каждому URL короткой ссылки. Это сделает каждую ссылку уникальной, даже если несколько пользователей предоставят один и тот же URL. Другим обходным решением может быть добавление идентификатора пользователя к входному URL, но это будет работать только в том случае, если пользователь войдет в систему, и нам также потребуется генерировать ключ уникальности.

Разделение данных и репликация

Наша база данных будет хранить информацию о миллиардах URL-адресов. Чтобы сделать ее масштабируемой, нам потребуется ее разделить. Рассмотрим два различных подхода к разделению: на основе диапазона и на основе хэша.

Разбиение на основе диапазона: Мы можем хранить URL-адреса в отдельных разделах на основе первой буквы их хэш-ключа. Мы сохраняем все URL, первая буква хэш-ключа которых A, в одном разделе, и так далее. Такой подход может привести к несбалансированности серверов баз данных, что создаст неравномерную нагрузку.

Разбиение на основе хэша: Мы можем взять хэш хранимого объекта и вычислить, какой раздел использовать. Функция хэширования случайным образом распределит данные по разным разделам. Такой подход иногда приводит к перегрузке разделов. Если это происходит, мы можем использовать последовательное хэширование для решения этой проблемы.

Кэширование

Наш сервис должен иметь возможность кэшировать URL-адреса, к которым часто обращаются. Мы можем использовать решение, подобное Memcached, для хранения полных URL с соответствующими хэшами.

Требования к памяти кэша: Мы можем начать с 20% от ежедневного трафика и регулировать его в зависимости от моделей использования. Согласно нашим предыдущим расчетам, для кэширования 20% ежедневного трафика нам потребуется 170 ГБ памяти.

Политика вытеснения кэша: Мы хотим заменить ссылку на более популярный URL. Для нашей системы мы можем использовать политику Least Recently Used (LRU).

Балансировка нагрузки

Мы можем добавить уровень балансировки нагрузки в нашу систему в трех местах:

1. Между клиентами и серверами приложений
2. Между серверами приложений и серверами баз данных
3. Между серверами приложений и серверами кэша

Мы можем начать с подхода Round Robin, чтобы равномерно распределить входящие запросы между серверами.

Дизайн Instagram

Этот пример решения проблемы адаптирован из другой статьи. Для получения более подробного руководства мы рекомендуем ознакомиться с материалом Design Instagram на сайте Educative.

Обзор проблемы

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

Системные требования и цели

Рассмотрим некоторые функциональные и нефункциональные требования.

Функциональные требования:

• Пользователь должен иметь возможность осуществлять поиск на основе названий фотографий или видео.
• Пользователь должен иметь возможность загружать, скачивать и просматривать фотографии и видео.
• Пользователь должен иметь возможность следить за другими пользователями
• Система должна иметь возможность генерировать ленту новостей, состоящую из лучших фотографий и видео людей, за которыми следит пользователь.

Нефункциональные требования:

• Сервис должен быть высокодоступным
• Приемлемая задержка системы должна составлять около 200 миллисекунд для новостной ленты
• Система должна быть надежной, чтобы фотографии и видео никогда не терялись.

Функции, которые не входят в рамки данного проекта, включают добавление тегов к фотографиям, поиск фотографий с тегами, комментирование и тегирование пользователей.

Оценки емкости и ограничения

Мы будем основывать наш подход на следующих цифрах:

• 500 миллионов пользователей
• 1 миллион ежедневных активных пользователей
• 2 миллиона новых фотографий каждый день (со скоростью 23 новых фотографии в секунду)
• Средний размер файла фотографии 200 КБ
• Общее пространство, необходимое для хранения 1 дня фотографий: 2 миллиона * 200 КБ => 400 ГБ
• Общее пространство, необходимое для хранения фотографий в течение 10 лет: 400 ГБ * 365 дней * 10 лет => 1,425 ТБ.

Высокоуровневый дизайн системы

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

Схема базы данных

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

Мы можем хранить приведенную выше схему с парами ключ-значение, используя базу данных NoSQL. Метаданные для фотографий и видео будут находиться в таблице, где ключ будет PhotoID, а значение будет объектом, содержащим PhotoLocation, UserLocation, CreationTimestamp и так далее.

Мы можем использовать хранилище данных с широкими колонками, Cassandra, для хранения отношений между пользователями и фотографиями, а также списка учетных записей, за которыми следит пользователь. Ключом UserPhoto таблицы key будет UserID. Значение value будет списком PhotoIDs, которыми владеет пользователь. Они будут храниться в другом столбце. Этот шаблон будет аналогичен таблице UserFollow.

Фотографии и видео могут храниться в распределенном файловом хранилище, таком как HDFS.

Оценка объема данных

Давайте оценим, сколько данных войдет в каждую таблицу и какой общий объем хранилища нам понадобится на 10 лет.

Пользователь

Каждая строка в этой таблице будет иметь размер 68 байт, предполагая, что каждый int и dateTime имеет размер 4 байта:

Если у нас 500 миллионов пользователей, нам потребуется 32 ГБ общего объема памяти:

Фото

Каждая строка в этой таблице будет занимать 284 байта:

Если каждый день загружается 2 миллиона новых фотографий, нам понадобится 0,5 ГБ памяти на один день:

За 10 лет нам понадобится 1,88 ТБ хранилища.

UserFollow

Каждая строка в этой таблице будет занимать 8 байт. У нас есть 500 миллионов пользователей. Если каждый пользователь следует в среднем за 500 другими пользователями, нам потребуется 1,82 ТБ памяти для хранения таблицы UserFollow:

Общее пространство, необходимое для хранения всех таблиц в течение 10 лет, составит 3,7 ТБ:

Дизайн компонента

Загрузка фотографий часто происходит медленнее, чем чтение, поскольку они отправляются на диск. Пользователи, загружающие фотографии, будут использовать все доступные соединения, так как этот процесс очень медленный. Чтение не может обслуживаться, когда система загружена запросами на запись. Чтобы справиться с этим узким местом, мы можем разделить чтение и запись на отдельные серверы, чтобы не перегружать систему. Это позволяет нам эффективно оптимизировать каждую операцию.

Надежность и избыточность

Создание избыточности в системе позволяет нам создать резервную копию в случае сбоя системы. Мы не можем потерять ни одного файла и нуждаемся в высоконадежном приложении. Мы можем достичь этого, храня несколько копий каждой фотографии и видео, чтобы система могла получить медиа с сервера копирования в случае, если сервер погибнет. Мы применим этот дизайн к другим компонентам нашей архитектуры. При наличии в системе нескольких копий сервисов система будет работать, даже если один из сервисов умрет.

Шардинг данных

Одна из возможных схем для службы разделения метаданных — это разделение на основе PhotoID. Для решения описанных выше проблем мы можем генерировать уникальные PhotoID, а затем найти номер шарда через PhotoID % 10. В этом случае нам не нужно будет добавлять ShardID к PhotoID, потому что PhotoID будет уникальным для всей системы.

Генерация фотоидентификаторов

Мы не сможем определить PhotoID, имея автоинкрементирующую последовательность в каждом шарде. Нам нужно знать PhotoID, чтобы найти шард, где он будет храниться. Одним из решений может быть выделение отдельного экземпляра базы данных для генерации автоинкрементных идентификаторов.

Если наш PhotoID может уложиться в 64 бита, мы можем определить таблицу, содержащую только 64-битное поле ID. Всякий раз, когда мы хотим добавить фотографию в нашу систему, мы можем вставить новую строку в эту таблицу и взять этот ID в качестве PhotoID нашей новой фотографии.

Обеспечение надежности

Эта база данных, генерирующая ключи, может стать единой точкой отказа. Обходным решением для этого может быть определение двух таких баз данных, одна из которых генерирует четные идентификаторы, а другая — нечетные. Для MySQL такая последовательность может быть определена следующим скриптом:

KeyGeneratingServer1:
auto-increment-increment = 2
auto-increment-offset = 1
KeyGeneratingServer2:
auto-increment-increment = 2
auto-increment-offset = 2

Мы можем поставить балансировщик нагрузки перед обеими этими базами данных. Мы можем использовать Round Robin между ними, чтобы справиться с простоями. Один из этих серверов может генерировать больше ключей, чем другой. К счастью, если они рассинхронизируются таким образом, это не вызовет проблем для нашей системы. Мы можем расширить эту конструкцию, определив отдельные таблицы идентификаторов для пользователей, фотокомментариев или других объектов, присутствующих в нашей системе.

Балансировка нагрузки

Сервису потребуется крупномасштабная система доставки фотографий, чтобы доставлять данные пользователям по всему миру. Мы можем приблизить контент к пользователям с помощью географически распределенных кэш-серверов.

Список общих вопросов для собеседования по проектированию систем

• Разработка глобальной службы чата, подобной Facebook Messenger или WhatsApp
• Разработка социальной сети и доски объявлений, например Quora или Reddit
• Разработка глобального сервиса хранения и обмена файлами, например Dropbox или Google Drive
• Разработка глобального сервиса потокового видео, такого как YouTube или Netflix
• Разработка ограничителя скорости API для таких сайтов, как Firebase или GitHub
• Разработка сервера близости, как Yelp или Nearby Places/Friends
• Разработка сервиса, связанного с поисковыми системами, например Type-Ahead
• Дизайн Ticketmaster
• Дизайн Twitter
• Разработать веб-краулер

Чтобы узнать, как решить эти проблемы на собеседовании по проектированию систем, а также все основы проектирования систем, мы рекомендуем курс Scalability & System Design for Developers на сайте Educative.

Как подойти к любому вопросу SDI

В статье Топ-10 вопросов собеседования по системному проектированию для инженеров-программистов на сайте Educative мы описываем эффективный подход к ответу на любой вопрос собеседования по системному проектированию. Давайте посмотрим, что включает в себя этот подход:

• Укажите, что вы знаете/Уточните цели: Начинайте решение каждой проблемы с изложения того, что вы знаете. Сюда могут входить требуемые характеристики системы, проблемы, с которыми вы ожидаете столкнуться, а также то, какой трафик, по вашим ожиданиям, должна обрабатывать система. Этот процесс продемонстрирует интервьюеру ваши навыки планирования, а также позволит ему исправить возможные заблуждения до того, как вы перейдете к решению.
• Опишите компромиссы: Ваш интервьюер захочет получить представление о любом выборе, который вы сделаете при проектировании системы. В каждой точке принятия решения объясните, по крайней мере, один положительный и один отрицательный эффект вашего решения.
• Обсудите новые технологии: Завершите каждый вопрос обзором того, как и где система может выиграть, например, от машинного обучения. Это продемонстрирует, что вы готовы не только к текущим, но и к будущим решениям.> Чтобы узнать, как знания в области машинного обучения могут помочь вам в прохождении собеседования по проектированию систем, прочитайте статью Как машинное обучение дает вам преимущество в проектировании систем на сайте Educative.

Шпаргалка для собеседования по системному дизайну

Вот шпаргалка для собеседования по системному дизайну, которую можно использовать для быстрой справки:

Ресурсы для собеседования по системному дизайну

Курсы и пути обучения на сайте Educative

• Масштабируемость и проектирование систем для разработчиков
• Grokking Modern System Design для инженеров и менеджеров программного обеспечения
• Собеседование по продвинутому системному проектированию
• Проектирование систем машинного обучения
• Архитектура веб-приложений и программного обеспечения 101

Продолжить обучение на Образовательном

• Grokking Современное системное проектирование для инженеров-программистов и менеджеров
• Полное руководство по системному проектированию в 2022 году
• Топ-10 вопросов для интервью по системному проектированию для инженеров-программистов
• Прохождение собеседования по машинному обучению: Подходы к проектированию систем
• Как машинное обучение дает вам преимущество в системном проектировании

Счастливого обучения!

Начать обсуждение

Что вы можете посоветовать тем, кто участвует в собеседовании по системному дизайну? Была ли эта статья полезной? Дайте нам знать в комментариях ниже!