Messenger

В этой главе мы рассмотрим проектирование чат-системы. Почти каждый пользуется каким-либо чат-приложением. На рисунке 1 показаны некоторые из самых популярных приложений на рынке.

Рисунок 1

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

Шаг 1 — Понять задачу и определить рамки дизайна

Очень важно договориться, какой именно тип чат-приложения мы проектируем. На рынке есть мессенджеры для переписки один на один, такие как Facebook Messenger, WeChat и WhatsApp, есть рабочие чаты с фокусом на групповое общение, например Slack, а есть игровые чаты, такие как Discord, где важны большие группы и низкая задержка для голосового общения.

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

Кандидат: Какой именно чат мы проектируем? 1 on 1 или групповой?
Интервьюер: Должны поддерживаться и 1 on 1, и групповой чат.

Кандидат: Это мобильное приложение? Веб-приложение? Или и то и другое?
Интервьюер: И то и другое.

Кандидат: Какой масштаб приложения? Стартап или очень большая система?
Интервьюер: Система должна поддерживать 50 миллионов DAU.

Кандидат: Какой лимит числа участников в групповом чате?
Интервьюер: Максимум 100 человек.

Кандидат: Какие функции важны? Нужны ли вложения?
Интервьюер: 1 on 1 чат, групповой чат и индикатор онлайна. Система поддерживает только текстовые сообщения.

Кандидат: Есть ли ограничение на размер сообщения?
Интервьюер: Да, длина текста должна быть меньше 100 000 символов.

Кандидат: Нужна ли сквозная шифрация?
Интервьюер: Пока нет, но если останется время, можем обсудить.

Кандидат: Как долго нужно хранить историю чата?
Интервьюер: Всегда.

В этой главе мы фокусируемся на проектировании чат-приложения наподобие Facebook Messenger с упором на такие возможности:

• Переписка один на один с низкой задержкой доставки

• Небольшие групповые чаты (максимум 100 человек)

• Online presence

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

• Push notifications

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

Шаг 2 — Предложить высокоуровневый дизайн и согласовать его

Чтобы построить качественный дизайн, нужно понимать основы взаимодействия клиента и сервера. В чат-системе клиентами могут быть как мобильные, так и веб-приложения. Клиенты не общаются друг с другом напрямую. Вместо этого каждый клиент подключается к chat service, который поддерживает все перечисленные выше функции. Сначала сосредоточимся на базовых операциях. Chat service должен уметь:

• Принимать сообщения от других клиентов

• Находить правильных получателей для каждого сообщения и пересылать сообщение им

• Если получатель не онлайн, хранить сообщения для него на сервере, пока он не появится в сети

На рисунке 2 показаны отношения между клиентами (отправителем и получателем) и chat service.

Рисунок 2

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

В большинстве клиент-серверных приложений запросы инициирует клиент. Это верно и для стороны отправителя в чат-приложении. На рисунке 2, когда отправитель посылает сообщение получателю через chat service, используется хорошо проверенный временем HTTP-протокол. В этом сценарии клиент открывает HTTP-соединение с chat service, отправляет сообщение и сообщает сервису доставить его получателю. Keep-alive здесь эффективен, потому что позволяет держать persistent connection с chat service и уменьшает число TCP-handshake. На стороне отправителя HTTP вполне подходит, и многие популярные chat applications, например Facebook [1], изначально использовали HTTP для отправки сообщений.

Однако сторона получателя устроена сложнее. Так как HTTP инициируется клиентом, серверу не так просто отправить сообщение клиенту сам по себе. За годы были придуманы разные техники имитации server-initiated communication: polling, long polling и WebSocket. Это важные подходы, которые часто обсуждаются на интервью по системному дизайну, поэтому разберем их по очереди.

Polling

Как показано на рисунке 3, polling — это техника, при которой клиент периодически спрашивает у сервера, появились ли новые сообщения. В зависимости от частоты опроса polling может быть дорогим. Он может тратить ценные серверные ресурсы, чтобы снова и снова отвечать «нет».

Рисунок 3

Long polling

Поскольку обычный polling неэффективен, следующим шагом стал long polling, показанный на рисунке 4.

Рисунок 4

В long polling клиент держит соединение открытым до тех пор, пока не появятся новые сообщения или не наступит timeout. Как только клиент получает новые сообщения, он сразу отправляет следующий запрос и повторяет процесс. У long polling есть несколько недостатков:

• Отправитель и получатель могут быть подключены к разным chat server. HTTP-серверы обычно stateless. Если балансировка делается через round robin, сервер, который принял сообщение, может не иметь long-polling connection с клиентом-получателем.

• У сервера нет хорошего способа понять, что клиент отключился.

• Этот подход неэффективен. Даже если пользователь почти не общается, long polling все равно периодически создает соединения после timeout.

WebSocket

Наиболее распространенное решение для асинхронных обновлений от сервера к клиенту — WebSocket. На рисунке 5 показано, как он работает.

Рисунок 5

WebSocket connection инициируется клиентом. Оно двустороннее и persistent. Начинается как обычное HTTP-соединение, а затем может быть upgraded до WebSocket через стандартный handshake. Через такое persistent connection сервер уже может сам отправлять обновления клиенту. WebSocket обычно хорошо работает даже за firewall, потому что использует порты 80 или 443 — те же, что HTTP/HTTPS.

Ранее мы говорили, что на стороне отправителя HTTP — хороший вариант, но раз WebSocket двусторонний, нет серьезной технической причины не использовать его и для отправки. На рисунке 6 показано, как WebSocket (ws) используется и со стороны отправителя, и со стороны получателя.

Рисунок 6

Использование WebSocket и для отправки, и для получения упрощает дизайн и делает реализацию на стороне клиента и сервера более прямолинейной. Поскольку WebSocket-соединения persistent, критически важным становится эффективное управление соединениями на сервере.

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

Только что мы сказали, что WebSocket выбран как основной протокол общения между клиентом и сервером из-за своей двусторонней природы. Но важно понимать, что все остальное не обязано работать поверх WebSocket. На практике большинство других функций чат-приложения — регистрация, логин, профиль пользователя и т. д. — могут использовать обычный request/response over HTTP. Посмотрим чуть глубже на высокоуровневые компоненты системы.

Как показано на рисунке 7, chat system делится на три большие категории: stateless services, stateful services и third-party integration.

Рисунок 7

Stateless services

Stateless services — это классические публичные request/response-сервисы, которые отвечают за логин, регистрацию, профиль пользователя и прочие стандартные функции.

Они находятся за load balancer, задача которого — направлять запросы в правильные сервисы в зависимости от request path. Эти сервисы могут быть как монолитом, так и набором микросервисов. Многие из таких stateless services не обязательно строить самостоятельно: на рынке уже есть решения, которые легко интегрировать. Единственный stateless-сервис, который мы подробнее разберем, — это service discovery. Его основная задача — дать клиенту список DNS host names chat-серверов, к которым клиент может подключиться.

Stateful service

Единственный stateful service — это chat service. Он stateful, потому что каждый клиент поддерживает persistent network connection с chat server. Обычно клиент не переключается на другой chat server, пока текущий остается доступным. Service discovery тесно координируется с chat service, чтобы не допускать перегрузки серверов.

Third-party integration

Для chat app самое важное стороннее интеграционное решение — push notification. Оно нужно, чтобы сообщать пользователю о новых сообщениях, даже когда приложение не запущено. Правильная интеграция push notification очень важна. Подробнее об этом можно посмотреть в главе про notification system.

Масштабируемость

На маленьком масштабе все перечисленные выше сервисы могут поместиться на одном сервере. Даже в масштабе нашей задачи теоретически можно уместить все пользовательские соединения на одном современном cloud server. Скорее всего, ограничением станет число concurrent connections, которые сервер умеет держать. В нашем сценарии при 1 миллионе concurrent users, если предположить, что каждое пользовательское соединение требует примерно 10 КБ памяти на сервере, нужно всего около 10 ГБ RAM для хранения всех соединений на одной машине.

Но если предложить дизайн, где все живет на одном сервере, это будет очень тревожным сигналом для интервьюера. Ни один инженер не будет проектировать такой масштаб на одном сервере. Single server design неприемлем по многим причинам, и самая важная из них — single point of failure.

Тем не менее начать с single server design вполне нормально. Главное — явно проговорить, что это лишь стартовая точка. Если собрать все вместе, получаем скорректированный high-level design на рисунке 8.

Рисунок 8

На рисунке 8 клиент поддерживает persistent WebSocket connection с chat server для real-time messaging.

• Chat servers обеспечивают отправку и получение сообщений.

• Presence servers управляют online/offline status.

• API servers отвечают за логин, регистрацию, изменение профиля и прочие функции.

• Notification servers отправляют push notifications.

• Наконец, key-value store используется для хранения истории чатов. Когда offline user снова выходит в сеть, он видит всю предыдущую историю.

Хранилище

На этом этапе у нас уже есть серверы, сервисы и сторонние интеграции. Глубже по стеку лежит data layer, и здесь особенно важно принять правильные решения. Один из ключевых выборов — использовать relational database или NoSQL database. Чтобы ответить осмысленно, нужно посмотреть на типы данных и read/write pattern.

В типичной chat system есть два вида данных. Первый — generic data: user profile, settings, список друзей и т. д. Такие данные удобно хранить в надежной relational database. Для удовлетворения требований по availability и scalability обычно применяются replication и sharding.

Второй тип уникален для chat systems: chat history data. Тут особенно важно понимать read/write pattern.

• Объем данных у chat systems огромный. Исследование [2] показывает, что Facebook Messenger и WhatsApp вместе обрабатывают порядка 60 миллиардов сообщений в день.

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

• Хотя в большинстве случаев нужны свежие сообщения, пользователи могут использовать функции, требующие random access: поиск, просмотр упоминаний, переход к конкретным сообщениям и т. д. Data access layer должен поддерживать и такие случаи.

• Соотношение чтений к записям в 1 on 1 chat apps примерно 1:1.

Правильно выбранная storage system критически важна, и мы рекомендуем key-value stores по таким причинам:

• Key-value stores легко горизонтально масштабируются.

• Key-value stores обеспечивают очень низкую latency при доступе к данным.

• Relational databases плохо работают с long tail [3] данных. Когда индексы становятся большими, random access дорожает.

• Key-value stores уже используются в надежных real-world chat applications. Например, Facebook Messenger использует HBase [4], а Discord — Cassandra [5].

Модели данных

Только что мы решили использовать key-value stores как storage layer. Самые важные данные здесь — это сообщения. Посмотрим на них внимательнее.

Таблица сообщений для 1 on 1 чата

На рисунке 9 показана message table для личных переписок. Primary key — это message_id, который помогает определить порядок сообщений. Полагаться на created_at нельзя, потому что два сообщения могут быть созданы одновременно.

Рисунок 9

Таблица сообщений для группового чата

На рисунке 10 показана message table для group chat. Composite primary key — это (channel_id, message_id). Здесь channel и group означают одно и то же. channel_id выбран как partition key, потому что все запросы в group chat выполняются внутри конкретного channel.

Рисунок 10

Message ID

Генерация message_id — интересная тема. Именно message_id отвечает за порядок сообщений. Чтобы порядок можно было восстановить, message_id должен удовлетворять двум требованиям:

• ID должны быть уникальными.

• ID должны сортироваться по времени, то есть новые строки должны иметь больший ID, чем старые.

Как этого добиться? Первая идея — использовать _auto_increment_ в MySQL. Но NoSQL databases обычно такой возможности не дают.

Второй подход — использовать глобальный 64-bit sequence number generator вроде Snowflake [6]. Он разбирался в главе про генератор уникальных ID.

Третий подход — локальный sequence number generator. Локальный означает, что ID уникален только внутри одной группы. Это работает, потому что для нас достаточно поддерживать правильную последовательность сообщений внутри 1 on 1 канала или группового канала. Такой подход проще в реализации, чем глобальный ID generator.

Шаг 3 — Детальный разбор дизайна

На интервью по системному дизайну обычно ожидается, что вы углубитесь в некоторые из компонентов high-level design. Для chat system особенно полезно подробнее обсудить service discovery, message flows и online/offline indicator.

Service discovery

Главная роль service discovery — рекомендовать клиенту лучший chat server по критериям вроде географического расположения, текущей нагрузки сервера и т. д. Apache Zookeeper [7] — популярное open-source решение для service discovery. Оно регистрирует все доступные chat servers и выбирает лучший сервер для клиента на основе заранее определенных правил.

На рисунке 11 показано, как работает service discovery (Zookeeper).

Рисунок 11

1. User A пытается войти в приложение.

2. Load balancer отправляет login request на API servers.

3. После аутентификации пользователя service discovery находит для User A лучший chat server. В этом примере выбирается server 2, и информация о нем возвращается обратно пользователю.

4. User A подключается к chat server 2 через WebSocket.

Потоки сообщений

Очень полезно понимать end-to-end flow чат-системы. В этом разделе разберем 1 on 1 чат, message synchronization между несколькими устройствами и flow группового чата.

Поток 1 on 1 чата

На рисунке 12 показано, что происходит, когда User A отправляет сообщение User B.

Рисунок 12

1. User A отправляет сообщение в Chat server 1.

2. Chat server 1 получает message ID от ID generator.

3. Chat server 1 отправляет сообщение в message sync queue.

4. Сообщение сохраняется в key-value store.

5.a. Если User B онлайн, сообщение пересылается в Chat server 2, к которому подключен User B.

5.b. Если User B офлайн, push notification отправляется через PN servers.

6. Chat server 2 пересылает сообщение User B. Между User B и Chat server 2 поддерживается persistent WebSocket connection.

Синхронизация сообщений между несколькими устройствами

У многих пользователей несколько устройств. Посмотрим, как синхронизировать сообщения между ними. На рисунке 13 показан пример такого процесса.

Рисунок 13

На рисунке 13 у User A два устройства: телефон и ноутбук. Когда User A входит в chat app с телефона, он устанавливает WebSocket connection с Chat server 1. Аналогично подключается и ноутбук.

Каждое устройство поддерживает переменную cur_max_message_id, которая хранит максимальный message ID, уже известный устройству. Сообщения считаются новыми, если выполняются два условия:

• recipient ID совпадает с ID текущего пользователя.

• message ID в key-value store больше, чем cur_max_message_id.

Поскольку на каждом устройстве свой cur_max_message_id, message synchronization становится простой: каждое устройство независимо получает новые сообщения из KV store.

Поток небольшого группового чата

По сравнению с 1 on 1 чатом логика group chat сложнее. На рисунках 14 и 15 показан этот flow.

Рисунок 14

На рисунке 14 показано, что происходит, когда User A отправляет сообщение в group chat. Предположим, в группе три участника: User A, User B и User C. Сначала сообщение от User A копируется в message sync queue каждого участника группы: одна копия для User B и одна — для User C. На message sync queue можно смотреть как на inbox получателя. Такой дизайн хорош для небольших group chat, потому что:

• Он упрощает message sync flow: каждому клиенту достаточно проверять только собственный inbox, чтобы получать новые сообщения.

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

WeChat использует похожий подход и ограничивает размер группы 500 участниками [8]. Но для больших групп хранить копию сообщения для каждого участника уже неприемлемо.

Со стороны получателя пользователь может принимать сообщения от нескольких отправителей. У каждого получателя есть свой inbox (message sync queue), в котором лежат сообщения от разных людей. На рисунке 15 показан такой дизайн.

Рисунок 15

Online presence

Индикатор online presence — важная функция почти любого чат-приложения. Обычно он выглядит как зеленая точка рядом с аватаром или именем пользователя. Разберем, что происходит за кулисами.

В high-level design presence servers отвечают за хранение online status и общение с клиентами через WebSocket. Есть несколько потоков, которые могут менять online status. Посмотрим на каждый.

Логин пользователя

Flow логина уже разбирался в разделе Service discovery. После того как между клиентом и real-time service устанавливается WebSocket connection, online status пользователя A и timestamp last_active_at сохраняются в KV store. После логина presence indicator показывает пользователя как online.

Рисунок 16

Logout пользователя

Когда пользователь выходит из приложения, выполняется flow logout, показанный на рисунке 17. Online status в KV store меняется на offline, и presence indicator показывает пользователя офлайн.

Рисунок 17

Потеря соединения

Нам всем хотелось бы, чтобы интернет-соединение всегда было стабильным, но это далеко не всегда так. Поэтому этот сценарий нужно учитывать в дизайне. Когда пользователь теряет интернет, persistent connection между клиентом и сервером разрывается. Наивный способ обработки — сразу помечать пользователя как offline, а после восстановления связи снова ставить online. Но у этого подхода есть серьезный недостаток: пользователи часто кратковременно теряют и восстанавливают связь. Например, сигнал может пропадать в туннеле. Если обновлять статус при каждом таком микроразрыве, indicator будет мигать слишком часто, и пользовательский опыт окажется плохим.

Чтобы решить эту проблему, вводится heartbeat mechanism. Периодически онлайн-клиент отправляет heartbeat event на presence servers. Если presence servers получают heartbeat от клиента в течение некоторого времени, например x секунд, пользователь считается online. Иначе — offline.

На рисунке 18 клиент отправляет heartbeat каждые 5 секунд. После трех heartbeat events клиент отключается и не восстанавливает связь в течение x = 30 секунд (значение выбрано произвольно для демонстрации логики). После этого online status меняется на offline.

Рисунок 18

Fanout online status

Как друзья User A узнают об изменении его статуса? На рисунке 19 показан один из вариантов. Presence servers используют publish-subscribe model, в которой каждая пара друзей поддерживает свой channel. Когда статус User A меняется, событие публикуется в три канала: channel A-B, A-C и A-D. Эти каналы подписаны соответственно пользователями B, C и D. Благодаря этому друзья легко получают обновления статуса. Взаимодействие клиентов с серверами идет через real-time WebSocket.

Рисунок 19

Такой дизайн эффективен для небольшой группы пользователей. Например, WeChat использует похожий подход, потому что размер группы ограничен 500 участниками. Для больших групп оповещать всех о каждом изменении статуса слишком дорого и долго. Если в группе 100 000 участников, каждое изменение статуса генерирует 100 000 событий. Чтобы снять это узкое место, можно запрашивать online status только тогда, когда пользователь открывает группу или вручную обновляет friend list.

Шаг 4 — Подведем итоги

В этой главе мы представили архитектуру chat system, поддерживающей и 1-to-1 chat, и небольшие group chat. Для real-time communication между клиентом и сервером используется WebSocket. Chat system включает следующие компоненты: chat servers для real-time messaging, presence servers для online presence, push notification servers для push notifications, key-value stores для хранения истории чатов и API servers для остальных функций.

Если в конце интервью останется время, можно обсудить еще несколько тем:

• Расширение чат-приложения для поддержки media files, таких как фото и видео. Media files существенно больше текста, поэтому тут интересны темы compression, cloud storage и thumbnails.

• End-to-end encryption. WhatsApp поддерживает сквозное шифрование сообщений: читать их могут только отправитель и получатель. См. материал [9].

• Client-side caching сообщений помогает сократить объем данных, передаваемых между клиентом и сервером.

• Улучшение load time. Slack построил географически распределенную сеть для кэширования данных пользователей, каналов и других сущностей, чтобы ускорить загрузку [10].

• Error handling.

• Сбой chat server. Один chat server может держать сотни тысяч, а то и больше persistent connections. Если chat server выходит из строя, service discovery (Zookeeper) должен предоставить клиентам новый сервер для переподключения.

• Механизм повторной отправки сообщений. Retry и queueing — распространенные техники для resend.

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

Справочные материалы

[1] Erlang at Facebook:
https://www.erlang-factory.com/upload/presentations/31/EugeneLetuchy-ErlangatFacebook.pdf

[2] Messenger and WhatsApp process 60 billion messages a day:
https://www.theverge.com/2016/4/12/11415198/facebook-messenger-whatsapp-number-messages-vs-sms-f8-2016

[3] Long tail: https://en.wikipedia.org/wiki/Long_tail

[4] The Underlying Technology of Messages:
https://www.facebook.com/notes/facebook-engineering/the-underlying-technology-of-messages/454991608919/

[5] How Discord Stores Billions of Messages:
https://discord.com/blog/how-discord-stores-billions-of-messages

[6] Announcing Snowflake:
https://blog.twitter.com/engineering/en_us/a/2010/announcing-snowflake.html

[7] Apache ZooKeeper: https://zookeeper.apache.org/

[8] From nothing: the evolution of WeChat background system (Article in Chinese):
https://www.infoq.cn/article/the-road-of-the-growth-weixin-background

[9] End-to-end encryption:
https://faq.whatsapp.com/en/android/28030015/

[10] Flannel: An Application-Level Edge Cache to Make Slack Scale:
https://slack.engineering/flannel-an-application-level-edge-cache-to-make-slack-scale-b8a6400e2f6b