Вам не нужно изучать какую‑либо теорию, кроме этой статьи, чтобы начать собеседоваться. После прочтения смело приступайте к решению типовых System Design задач.

Изучая System Design, вы часто видите только теоретические материалы. В этой статье я постарался показать в том числе практическую реализацию многих вещей, чтобы вы не просто готовились к собеседованиям, но и знали, как эти вещи используются в реальном мире.

Содержание

Часть 1:

1. Зачем изучать проектирование систем?

2. Что такое сервер?

3. Задержка и пропускная способность

4. Масштабирование и его типы
   + Вертикальное
   + Горизонтальное

5. Автоматическое масштабирование

6. Оценка на коленке

7. Теорема CAP

   Часть 2:

8. Масштабирование базы данных
   + Индексирование
   + Партиционирование
   + Архитектура «master-slave»
   + Multi-master
   + Шардирование
   + Недостатки Шардирования

9. SQL и NoSQL СУБД. Когда какую базу данных использовать?
   + SQL СУБД
   + NoSQL СУБД
   + Особенности масштабирования
   + Когда использовать ту или иную базу данных?

   Часть 3:

10. Микросервисы
    + Что такое монолит и микросервис?
    + Почему мы разбиваем наше приложение на микросервисы?
    + Когда следует использовать микросервисы?
    + Как клиенты отправляют запросы?

11. Load Balancer
    + Зачем нам нужен балансировщик нагрузки?
    + Алгоритмы балансировщика нагрузки

12. Кэширование
    + Введение в кэширование
    + Преимущества кэширования
    + Типы кэшей
    + Подробное описание Redis

    Часть 4:

13. Хранилище BLOB-объектов
    + Что такое BLOB и зачем нам нужно хранилище BLOB?
    + AWS S3

14. Сеть доставки контента (CDN)
    + Знакомство с CDN
    + Как работает CDN?
    + Ключевые понятия в CDN

15. Message Broker
    + Асинхронное программирование
    + Зачем мы добавили посредника для передачи сообщений?
    + Queue
    + Stream
    + Кейсы использования

16. Apache Kafka Deep dive
    + Когда использовать Kafka
    + Внутреннее устройство Kafka

    Часть 5:

17. Pub/Sub

18. Event-Driven Архитектура
    + Введение
    + Зачем использовать EDA?
    + Система нотификаций с id
    + Система с передачей всего состояния

19. Distributed Systems

20. Leader Election

21. Big Data Tools

    Часть 6:

22. Consistency Deep Dive
    + Когда использовать Strong Consistency, Eventual Consistency
    + Как добиться Strong, Eventual Consistency

23. Consistent Hashing

24. Data Redundancy and Data Recovery
    + Зачем мы делаем резервные копии баз данных?
    + Различные способы резервного копирования данных
    + Непрерывное резервное копирование

25. Proxy
    + Что такое прокси сервер?
    + Прямой и обратный прокси сервер
    + Создание собственного обратного прокси-сервера

26. Как решить любую проблему, связанную с проектированием системы?

Consistency Deep Dive

В большинстве случаев наши приложения не сохраняют состояние. Они не хранят никаких данных. Данные и различные состояния сущностей для исполнения логики приложения хранятся в СУБД.

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

Мы используем базы данных как «чёрный ящик». Поэтому здесь вам, возможно, не придётся много программировать, но не пропускайте этот раздел. Это очень важно. В будущем, если вы будете программировать какое-либо приложение с отслеживанием состояния или создавать собственную базу данных, эти концепции будут вам полезны. Кроме того, какую бы базу данных вы ни использовали, например DynamoDB, Cassandra, MongoDB и т. д., проверьте, какой тип согласованности она обеспечивает.

В контексте System Design Интервью используется 2 типа согласованности(прим. переводчика - дальше устоявшиеся термины):

1. Strong Consistency (строгая согласованность)

2. Eventual Consistency (согласованность в конечном счёте)

Strong Consistency

• Любая операция чтения после операции записи всегда будет возвращать самую последнюю запись.

• Как только запись будет подтверждена, все последующие чтения будут отражать эту запись.

• Все реплики должны согласовать текущее значение, прежде чем подтверждать запись.

• Система работает так, как будто существует только одна копия данных.

Когда выбирать strong consistency?

• Банковская система, в которой пользователь переводит деньги с одного счёта на другой.

• Торговое приложение, в котором пользователь получает самую свежую и точную информацию о ценах на акции.

Eventual Consistency

• Это не гарантирует немедленную согласованность после операции записи, но обеспечивает то, что в конечном итоге, через некоторое время, все операции чтения будут возвращать одно и то же значение.

• Может пройти некоторое время, прежде чем все реплики отобразят последнюю запись.

• Поскольку здесь вы пошли на компромисс с согласованностью, вы получите высокую доступность (теорема CAP).

• Если две реплики содержат разные данные, то для разрешения конфликтов необходимо использовать какой-либо «механизм разрешения конфликтов».

Когда следует выбрать eventual consistency?

• Приложения для социальных сетей. Если количество лайков под какими-либо постами непостоянно и позже исправляется, то всё в порядке.

• Каталоги товаров в приложениях для электронной коммерции.

Способы достижения strong consistency

1. Синхронная репликация
   При выполнении операции записи все реплики обновляются до подтверждения записи клиенту. Пример: распределённые базы данных, такие как Google Spanner, используют синхронную репликацию.

2. Протоколы на основе кворума
   В распределённых базах данных используется схема «leader-follower», которую мы изучали в разделе о распределённых системах. Когда follower завершает операцию записи или чтения, он подтверждает это лидеру.
   Кворум для чтения — это количество followers, возвращающих данные для чтения. Предположим, что для ключа user_id_2 значение «Михаил» возвращается 5 узлами. Тогда кворум для чтения равен 5.
   Кворум для записи — это количество followers, которые подтверждают запись для конкретного ключа. При строгой согласованности, если W — это кворум для записи, а R — кворум для чтения, то W + R > N где N — общее количество узлов. Пример: AWS DynamoDB и Cassandra

3. Алгоритмы консенсуса
   Обширная тема в области распределённых систем, поэтому мы не будем её здесь рассматривать. Вкратце, в ней используется алгоритм выбора лидера. Запись или чтение считаются успешными, если их подтверждают более 50% узлов. Если вы хотите узнать об этом больше, изучите Raft. Это простой алгоритм консенсуса. Пример: Docker Swarm использует Raft внутри.

Способы достижения конечной согласованности

1. Асинхронная репликация
   Записи подтверждаются немедленно, а обновления распространяются на реплики в фоновом режиме. Пример: распространено в базах данных NoSQL, таких как Cassandra, MongoDB и DynamoDB (режим по умолчанию).

2. Протоколы на основе кворума (с ослабленной согласованностью)
   Кворум для чтения + кворум для записи ≤ количество узлов
   Пример: Amazon DynamoDB.

3. Векторные часы
   Это тоже обширная и нишевая тема. Мы не будем ее здесь обсуждать.
   Пример: AWS DynamoDB

4. Протокол Gossip(сплетни)
   Позволяет узлам обмениваться сигналами с подмножеством других узлов, распространяя обновления по всей системе. Сигналы — это просто HTTP- или TCP-запросы, отправляемые периодически каждые 2–3 секунды. Таким образом, мы обнаруживаем любые отказавшие узлы. Для отказавших узлов мы настраиваем степень согласованности в зависимости от того, сколько реплик должно быть доступно для чтения и записи.Например, DynamoDB и Cassandra используют этот протокол.

Consistent Hashing

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

Поскольку в этом процессе задействованы данные, согласованное хеширование в основном используется в приложениях с отслеживанием состояния, а система является распределённой.

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

Зачем нам нужно последовательное хеширование?

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

• Сгенерируйте ключ с помощью любой функции хеширования (например, SHA256, SHA128, MD5 и т. д.).

• Затем разделите полученное число на количество серверов, чтобы определить принадлежность.

Допустим, количество серверов равно 3.
Ключ 1 принадлежит серверу => (Хэш(ключ1) % 3)

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

Когда количество серверов становится динамическим, возникают проблемы.

Предположим, что в нашем предыдущем примере количество серверов изменилось с 3 до 2. Тогда теперь key1 принадлежит серверу => (Hash(key1) % 2). Это число может отличаться от предыдущего.

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

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

Как consistent hashing используется для определения того, какие данные принадлежат какому узлу?

• Мы берём идентификатор сервера (например, IP-адрес или идентификатор) и передаём его в хеш-функцию, такую как SHA128. Она сгенерирует случайное число в диапазоне [0, 2¹²⁸).

• Для визуализации мы поместим его в кольцо. Разделим кольцо на [0, 2¹²⁸), то есть на диапазон хеша. Какое бы число ни получилось в результате передачи server_id в хеш-функцию, поместите этот сервер в это место на кольце.

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

Любой ключ будет отправлен на ближайший сервер по часовой стрелке. В приведенном выше примере:

• ключ-1 и ключ-4 принадлежат узлу-1

• ключ-3 принадлежит Node-2

• Ключи 2 и 5 относятся к узлу 3

Предположим, что узел 2 удалён из приведённой выше схемы. Тогда ключ 3 будет принадлежать узлу 1, а другие ключи не изменятся. В этом и заключается сила последовательного хеширования. Оно обеспечивает минимальное перемещение ключей. Но последовательное хеширование не выполняет это перемещение. Вам нужно сделать это самостоятельно. Последовательное хеширование — это просто алгоритм, который определяет, какой ключ какому узлу принадлежит.

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

Использование согласованного хеширования: распределенные базы данных, такие как AWS DynamoDB, Apache Cassandra, Riak, используют его внутри системы.

Резервирование и восстановление данных

Избыточность - важное понятие в System Design. Оно означает создание нескольких копий одних и тех же данных.

Мы делаем нашу базу данных избыточной и храним копии данных на нескольких серверах.

Почему мы делаем базы данных избыточными?

• Резервное копирование данных гарантирует, что в случае стихийного бедствия, когда центр обработки данных, в котором физически находится наш сервер БД, будет затоплен или что-то в этом роде, мы не потеряем данные.

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

Различные способы резервного копирования данных

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

• Делайте ежедневное резервное копирование каждый вечер. При любых изменениях в базе данных делайте снимок (копируйте) и сохраняйте его на другом сервере баз данных.

• Делайте еженедельное резервное копирование.

Таким образом, если на сервере базы данных произойдёт сбой, у вас будут данные как минимум за последний день или за последнюю неделю.

Непрерывное Резервирование

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

При непрерывном резервировании мы настраиваем два разных сервера баз данных. Один из них является основным, а другой — резервным/репликой.

Когда мы выполняем какую-либо операцию чтения или записи, она выполняется в основной базе данных и синхронно или асинхронно (в зависимости от выбранной вами конфигурации) реплицируется в реплику. Эта реплика не участвует в операциях чтения/записи, выполняемых клиентом(рассматриваем лишь с т.зр. бэкапа). Её единственная задача — поддерживать синхронизацию с основной базой данных. Когда в основной базе данных происходит сбой, эта реплика становится основной базой данных и начинает обслуживать запросы. Таким образом, мы сделали нашу систему отказоустойчивой.

Ваша задача — настроить эту реплику в любом облачном провайдере и посмотреть, как это делается в реальном мире.
Вторая задача — сделать это локально. Настройте два сервера MySQL локально на ноутбуке и настройте репликацию. Напишите в основной сервер и посмотрите, реплицируется ли это в реплику.

Прокси - сервер

Что такое прокси-сервер?

Прокси-сервер — это промежуточный сервер, который находится между клиентом и другим сервером.

Возможно, вам интересно, зачем мы ввели промежуточный уровень. У него есть несколько вариантов применения, которые мы рассмотрим.

Существует два вида прокси-серверов:
1. Прямой прокси-сервер
2. Обратный прокси-сервер

Прямой Прокси-сервер

Прямой прокси-сервер действует от имени клиента. Когда клиент отправляет запрос, этот запрос проходит через прямой прокси-сервер. Сервер не знает, кто является клиентом (IP-адрес). Сервер знает только IP-адрес прямого прокси-сервера.

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

Основная функция: скрывает клиента. Сервер видит только переадресацию, а не клиента.

Варианты использования:

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

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

• Организации (например, компании, колледжи и т. д.) устанавливают прокси-сервер для контроля использования интернета сотрудниками путём фильтрации определённых веб-сайтов.

Поток:

• Запросы клиентов www.abc.com.

• Прямой прокси-сервер получает запрос и перенаправляет его на сервер.

• Сервер отправляет ответ обратно на прокси-сервер.

• Прямой прокси-сервер отправляет ответ клиенту.

Вот и всё, что касается прямого прокси-сервера. При проектировании системы мы в основном уделяем внимание обратному прокси-серверу, а не прямому, потому что прямой прокси-сервер связан с клиентом (интерфейсом). При проектировании системы мы в основном создаём серверные (бэкенд) приложения.

Обратный Прокси-сервер

Обратный прокси-сервер действует от имени сервера. Клиенты отправляют запросы обратному прокси-серверу, который перенаправляет их на соответствующий сервер в бэкенде. Ответ возвращается обратно через обратный прокси-сервер клиенту.

При прямом проксировании серверы не знают, кто является клиентом, но при обратном проксировании клиент не знает о сервере. Они отправляют запрос обратному прокси-серверу. Задача обратного прокси-сервера — направить этот запрос на соответствующий сервер.

Основная функция: скрывает сервер. Клиент видит только обратный прокси-сервер, а не сервер.

Примером обратного прокси-сервера может служить балансировщик нагрузки. В балансировщиках нагрузки клиенты не знают о реальном сервере. Они отправляют запросы в балансировщики нагрузки.

Варианты использования:

• Балансировщик нагрузки, как вы видели выше.

• Завершение SSL-сессии: обеспечивает шифрование и дешифрование, снижая нагрузку на сервер.

• Кэширование: сохраняет статический контент для снижения нагрузки на сервер.

• Безопасность: защищает внутренние серверы от прямого доступа из Интернета.

Поток:

• Запросы клиентов www.abc.com.

• Обратный прокси-сервер получает запрос.

• Обратный прокси-сервер перенаправляет запрос на один из нескольких внутренних серверов.

• Сервер отправляет ответ обратно на прокси-сервер.

• Прокси-сервер отправляет ответ клиенту.

Пример обратного прокси-сервера: Ngnix, HAProxy

Упражнение для вас: изучите Ngnix и используйте его в своих дополнительных проектах.

Как решить любую проблему, связанную с проектированием системы?

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

• Поймите постановку проблемы
  Пример: Предположим, что задача состоит в том, чтобы создать приложение для электронной коммерции (например, Ozon/Wb). Затем определите, какие требования предъявляются к приложению и какие функции нам нужно реализовать.

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

• Сосредоточьтесь на эффективном решении каждой подзадачи
  Для каждой подзадачи сосредоточьтесь на следующих 4 аспектах:
  - База данных
  - Кэширование
  - Масштабирование и отказоустойчивость
  - Связь (асинхронная или синхронная)
  При решении любой подзадачи, возможно стоит её разбить ещё на подзадачи.

Вы закончили изучение базы System Design за 6 занятий! Поздравляю!

Рад, что цикл статей встретил такой большой и положительный отклик. Меня зовут Невзоров Владимир. Я практикующий инженер HighLoad систем. Больше System Design, в том числе подготовка к System Design Интервью на моём канале System Design World. Всего наилучшего!

Пишите пожелания к рассмотрению новых тем :)