系统设计::设计一个聊天系统

设计一个聊天系统

在这一章中，我们探讨了一个聊天系统的设计。几乎每个人都在使用一个聊天应用程序。图 12-1 显示了市场上一些最流行的应用程序。

聊天应用程序对不同的人执行不同的功能。敲定确切的要求是极其重要的。例如，当面试官想到一对一的聊天时，您不希望设计一个专注于群组聊天的系统。探索功能要求是很重要的。

理解问题并确定设计范围

就要设计的聊天应用程序的类型达成一致是至关重要的。在市场上，有像 Facebook Messenger、微信和 WhatsApp 这样一对一的聊天应用，也有像 Slack 这样专注于群组聊天的办公聊天应用，或者像 Discord 这样专注于大型群组互动和低语音聊天延迟的游戏聊天应用。

第一组澄清问题应该明确面试官要求你设计一个聊天系统时，她心里想的到底是什么。至少要弄清楚你是应该专注于一对一的聊天还是群组聊天应用。你可以问以下一些问题。

应聘者：我们应该设计什么样的聊天应用程序？一对一还是基于群组？
面试官：它应该同时支持 1 对 1 和群组聊天。
应聘者：这是一个移动应用吗？还是网络应用？或者两者都是？
面试官：都是。
应聘者：这个应用程序的规模是多少？是创业公司的应用还是大规模的？
面试官：它应该支持 5000 万日活跃用户（DAU）。
应聘者：对于群组聊天，群组成员的限制是什么？
面试官：最多 100 人
应聘者：聊天软件的哪些功能很重要？能否支持附件？
面试官：1 对 1 聊天，群聊，在线指标。系统只支持文字信息。
应聘者：信息大小有限制吗？
面试官：是的。是的，文本长度应小于 10 万个字符。
应聘者：是否需要端对端加密？
面试官：不需要。目前不需要，但如果时间允许，我们会讨论这个问题。
应聘者：我们应将聊天记录保存多长时间？
面试官：永远。

在这一章中，我们将重点设计一个类似于 Facebook messenger 的聊天应用，并强调以下特点。

  • 一对一的聊天，传递延迟低
  • 小型群组聊天（最多 100 人）。
  • 显示在线
  • 支持多种设备。同一账户可以同时登录多个账户。
  • 推送通知

就设计规模达成一致也很重要。我们将设计一个支持 5000 万 DAU 的系统。

提出高层次的设计并获得认同

为了开发一个高质量的设计，我们应该对客户和服务器的通信方式有一个基本的了解。在一个聊天系统中，客户端可以是移动应用程序或 Web 应用程序。客户端之间并不直接交流。相反，每个客户端都连接到一个聊天服务，它支持上面提到的所有功能。让我们专注于基本操作。聊天服务必须支持以下功能。

  • 接收来自其他客户的消息。
  • 为每条消息寻找合适的收件人，并将消息转发给收件人。
  • 如果收件人不在线，在服务器上保留该收件人的消息，直到她在线。

图 12-2 显示了客户端（发送者和接收者）和聊天服务之间的关系。

当客户打算开始聊天时，它使用一个或多个网络协议连接到聊天服务。对于一个聊天服务，网络协议的选择很重要。让我们与面试官讨论一下这个问题。

对于大多数客户/服务器应用程序，请求是由客户发起的。对于聊天应用程序的发送方来说也是如此。在图 12-2 中，当发送方通过聊天服务向接收方发送消息时，它使用经过时间考验的 HTTP 协议，这是最常见的网络协议。在这种情况下，客户端打开与聊天服务的 HTTP 连接并发送消息，通知服务将消息发送给接收方。keep-alive 对此很有效，因为 keep-alive 头允许客户端与聊天服务保持持久的连接。它也减少了 TCP 握手的次数。HTTP 在发送方是一个很好的选择，许多流行的聊天应用程序，如 Facebook[1]最初使用 HTTP 来发送消息。

然而，接收方就比较复杂了。由于 HTTP 是由客户发起的，所以从服务器上发送消息并不是一件小事。多年来，许多技术被用来模拟服务器发起的连接：轮询、长轮询和 WebSocket。这些都是在系统设计访谈中广泛使用的重要技术，所以让我们逐一检查一下

轮询

如图 12-3 所示，轮询是一种技术，客户端定期询问服务器是否有消息可用。根据轮询的频率，轮询的成本可能很高。它可能会消耗宝贵的服务器资源来回答一个大部分时间都没有答案的问题。

长轮询

因为轮询可能是低效的，接下来的进展是长轮询（图 12-4）。

在长期轮询中，客户端保持连接开放，直到有实际可用的新消息或达到一个超时阈值。一旦客户端收到新消息，它立即向服务器发送另一个请求，重新启动这个过程。长时间轮询有一些缺点。

  • 发送者和接收者可能不会连接到同一个聊天服务器。基于 HTTP 的服务器通常是无状态的。如果您使用轮询进行负载平衡，接收信息的服务器可能没有与接收信息的客户端建立长轮询连接。
  • 服务器没有很好的方法来告诉客户是否断开了连接。
  • 这是很低效的。如果一个用户不怎么聊天，长轮询仍然会在超时后进行定期连接。

WebSocket

WebSocket 是从服务器向客户端发送异步更新的最常见解决方案。图 12-5 显示了它的工作原理。

WebSocket 连接是由客户端发起的。它是双向的和持久的。它以 HTTP 连接的形式开始，并可通过一些定义明确的握手方式 “升级 “为 WebSocket 连接。通过这种持久的连接，服务器可以向客户端发送更新。即使有防火墙，WebSocket 连接通常也能工作。这是因为它们使用 80 或 443 端口，这些端口也被 HTTP/HTTPS 连接使用。

前面我们说过，在发送方，HTTP 是一个很好的协议，但由于 WebSocket 是双向的，所以没有充分的技术理由不使用它来发送。图 12-6 显示了 WebSockets（ws）在发送方和接收方的使用情况。

通过使用 WebSocket 进行发送和接收，它简化了设计，并使客户端和服务器上的实现更加直接。由于 WebSocket 连接是持久的，因此有效的连接管理在服务器端至关重要。

高层设计

刚才我们提到，选择 WebSocket 作为客户端和服务器之间的主要通信协议，是因为它的双向通信，需要注意的是，其他一切都不一定是 WebSocket。事实上，聊天应用程序的大多数功能（注册、登录、用户资料等）都可以使用 HTTP 上的传统请求/响应方法。让我们深入了解一下，看看系统的高级组件。

如图 12-7 所示，聊天系统被分成三大类：无状态服务、有状态服务和第三方集成。

无状态服务

无状态服务是传统的面向公众的请求/响应服务，用于管理登录、注册、用户资料等。这些是许多网站和应用程序的共同特征。

无状态服务位于负载均衡器后面，其工作是根据请求路径将请求路由到正确的服务。这些服务可以是单体的，也可以是单独的微服务。我们不需要自己建立许多这样的无状态服务，因为市场上有一些服务可以很容易地被整合。我们将深入讨论的一个服务是服务发现。它的主要工作是给客户提供一个客户可以连接到的聊天服务器的 DNS 主机名列表。

有状态的服务

唯一有状态的服务是聊天服务。该服务是有状态的，因为每个客户都与聊天服务器保持持久的网络连接。在这个服务中，只要服务器仍然可用，客户端通常不会切换到另一个聊天服务器。服务发现与聊天服务密切协调，以避免服务器过载。我们将在深入研究中详细介绍。

第三方整合

对于一个聊天应用程序，推送通知是最重要的第三方整合。它是一种在新消息到来时通知用户的方式，即使应用程序没有运行。正确整合推送通知是至关重要的。更多信息请参考第 10 章 设计一个通知系统。

可扩展性

在小规模的情况下，上面列出的所有服务都可以装在一台服务器中。即使在我们设计的规模下，理论上也可以在一台现代云服务器中容纳所有的用户连接。一台服务器所能处理的并发连接数很可能是限制性因素。在我们的方案中，在 100 万并发用户的情况下，假设每个用户连接在服务器上需要 10K 的内存（这是一个非常粗略的数字，非常依赖于语言的选择），它只需要大约 10GB 的内存来容纳所有的连接在一个盒子上。

如果我们提出一个所有东西都装在一台服务器上的设计，这可能会在面试官心中引起很大的反响。没有技术专家会在一台服务器中设计这样的规模。由于许多因素，单台服务器的设计是一个失败者。单一的故障点是其中最大的。

然而，从单服务器设计开始是完全可以的。只要确保面试官知道这是个起点。把我们提到的一切放在一起，图 12-8 显示了调整后的高层设计。

在图 12-8 中，客户端与聊天服务器保持一个持久的 WebSocket 连接，以进行实时消息传递。

  • 聊天服务器促进消息的发送/接收。
  • 存在感服务器管理在线/离线状态。
  • API 服务器处理一切，包括用户登录、注册、更改资料等。
  • 通知服务器发送推送通知。
  • 最后，键值存储用于存储聊天历史。当一个离线用户上线时，她会看到她之前所有的聊天历史。

存储

在这一点上，我们已经准备好了服务器，服务已经开始运行，第三方集成已经完成。在技术栈的深处是数据层。数据层通常需要一些努力才能得到正确的结果。我们必须做出的一个重要决定是决定使用正确的数据库类型：关系型数据库还是 NoSQL 数据库？为了做出一个明智的决定，我们将研究数据类型和读/写模式。

在典型的聊天系统中存在两种数据类型。第一类是通用数据，如用户资料、设置、用户朋友列表。这些数据被存储在强大而可靠的关系数据库中。复制和分片是满足可用性和可扩展性要求的常用技术。

第二种是聊天系统特有的：聊天历史数据。了解读/写模式很重要。

  • 聊天系统的数据量是巨大的。之前的一项研究[2]显示，Facebook messenger 和 Whatsapp 每天处理 600 亿条信息。
  • 只有最近的聊天记录被频繁访问。用户通常不会去查找旧的聊天记录。
  • 虽然在大多数情况下都会查看最近的聊天记录，但用户可能会使用需要随机访问数据的功能，如搜索、查看你提到的信息、跳转到特定的信息等。这些情况应该由数据访问层来支持。
  • 对于 1 对 1 的聊天应用程序，读与写的比例约为 1:1。

选择正确的存储系统，支持我们所有的用例是至关重要的。我们推荐键值存储，理由如下。

  • 键值存储允许轻松地进行横向扩展。
  • 键值存储为访问数据提供了非常低的延时。
  • 关系型数据库不能很好地处理长尾[3]的数据。当索引变大时，随机访问是很昂贵的。
  • 键值存储被其他被证明可靠的聊天应用程序所采用。例如，Facebook Messager和 Discord 都使用键值存储。Facebook Messager使用 HBase[4]，而 Discord 使用 Cassandra[5]。

数据模型

刚才，我们谈到了使用键值存储作为我们的存储层。最重要的数据是消息数据。让我们仔细看一下。

1 对 1 聊天的消息表 图 12-9 显示了 1 对 1 聊天的消息表。主键是 message_id，它有助于决定消息序列。我们不能依靠 created_at 来决定消息的顺序，因为两条消息可能同时被创建。

群聊的消息表

图 12-10 显示了群聊的消息表。复合主键是（channel_id, message_id）。channel 和 group 在这里代表相同的含义。 channel_id 是分区键，因为群聊中的所有查询都在一个频道中操作。

消息 ID

如何生成 message_id 是一个值得探索的有趣话题。Message_id 承担着确保消息顺序的责任。为了确定消息的顺序，message_id 必须满足以下两个要求。

  • ID 必须是唯一的。
  • ID 应该是可以按时间排序的，也就是说，新行的 ID 比旧行的 ID 高。

我们怎样才能实现这两个保证呢？我想到的第一个想法是 MySql 中的 “auto_increment “关键字。然而，NoSQL 数据库通常不提供这样的功能。

第二个方法是使用一个全局性的 64 位序列号生成器，如 Snowflake[6]。这将在 “第七章：在分布式系统中设计一个唯一的 ID 生成器 “中讨论。

最后一种方法是使用本地序列号生成器。本地意味着 ID 只在一个组内是唯一的。本地 ID 发挥作用的原因是，在一对一的信道或一个组的信道内维持消息序列就足够了。与全局 ID 的实现相比，这种方法更容易实现。

深究设计

在系统设计面试中，通常希望你能深入了解高层设计中的一些组件。对于聊天系统，服务发现、消息流和在线/离线指标值得深入探讨。

服务发现

服务发现的主要作用是根据地理位置、服务器容量等标准，为客户推荐最佳的聊天服务器。Apache Zookeeper [7] 是一个流行的服务发现开源解决方案。它注册了所有可用的聊天服务器，并根据预定义的标准为客户挑选最佳聊天服务器。

图 12-11 显示了服务发现（Zookeeper）如何工作。

  1. 用户 A 试图登录到应用程序。
  2. 负载均衡器将登录请求发送到 API 服务器。
  3. 在后端认证用户后，服务发现为用户 A 找到最佳的聊天服务器。在这个例子中，服务器 2 被选中，服务器信息被返回给用户 A。
  4. 用户 A 通过 WebSocket 连接到聊天服务器 2。

消息流

了解一个聊天系统的端到端流程是很有意思的。在本节中，我们将探讨 1 对 1 的聊天流程、跨多个设备的信息同步和群组聊天流程。

1 对 1 数据流

图 12-12 解释了当用户 A 向用户 B 发送消息时发生的情况。

  1. 用户 A 向聊天服务器 1 发送一个聊天信息。
  2. 聊天服务器 1 从 ID 生成器中获得一个消息 ID。
  3. 聊天服务器 1 将消息发送到消息同步队列中。
  4. 消息被存储在一个键值存储器中。
  5. 如果用户 B 在线，该消息被转发到用户 B 连接的聊天服务器 2。
  6. 聊天服务器 2 将消息转发给用户 B。用户 B 和聊天服务器 2 之间有一个持久的 WebSocket 连接。

多个设备间的信息同步

许多用户有多个设备。我们将解释如何在多个设备上同步消息。图 12-13 显示了一个消息同步的例子。

在图 12-13 中，用户 A 有两台设备：一台手机和一台笔记本电脑。当用户 A 用手机登录聊天应用程序时，它与聊天服务器 1 建立了一个 WebSocket 连接。同样地，笔记本电脑和聊天服务器 1 之间也有一个连接。

每个设备都维护着一个名为 cur_max_message_id 的变量，它记录着设备上最新的消息 ID。满足以下两个条件的消息被认为是新闻消息。

  • 收件人 ID 等于当前登录的用户 ID。
  • 键值存储中的消息 ID 大于 cur_max_message_id 。

由于每个设备上都有不同的 cur_max_message_id，消息同步很容易，因为每个设备都可以从 KV 存储中获得新消息。

小群组聊天流程

与一对一的聊天相比，群组聊天的逻辑更复杂。图 12-14 和 12-15 解释了该流程。

图 12-14 解释了用户 A 在群聊中发送消息时发生的情况。假设群里有 3 个成员（用户 A、用户 B 和用户 C）。首先，用户 A 的消息被复制到每个组员的消息同步队列中：一个给用户 B，另一个给用户 C。你可以把消息同步队列看成是一个收件人的收件箱。这种设计选择对小型群组聊天来说是很好的，因为。

  • 它简化了消息同步的流程，因为每个客户只需要检查自己的收件箱就可以得到新的消息。
  • 当群组人数较少时，在每个接收者的收件箱中存储一份副本不会太昂贵。

微信使用类似的方法，它将一个群组限制在 500 个成员[8]。然而，对于有大量用户的群组，为每个成员存储一份信息副本是不可接受的。

在收件人方面，一个收件人可以接收来自多个用户的信息。每个收件人都有一个收件箱（消息同步队列），其中包含来自不同发送者的消息。图 12-15 说明了这种设计。

显示在线

在线状态指示器是许多聊天应用程序的一个基本功能。通常情况下，您可以在用户的个人照片或用户名旁边看到一个绿点。本节解释幕后发生的事情。

在高层设计中，在场服务器负责管理在线状态，并通过 WebSocket 与客户进行沟通。有几个流程会触发在线状态的变化。让我们来看看它们中的每一个。

用户登录

用户登录流程在 “服务发现 “部分进行了解释。在客户端和实时服务之间建立 WebSocket 连接后，用户 A 的在线状态和最后活动时间戳被保存在 KV 存储中。在场指示器显示用户在登录后处于在线状态。

用户登出

当一个用户注销时，会经过用户注销流程，如图 12-17 所示。在线状态在 KV 存储中被改变为离线。存在指示器显示一个用户是离线的。

用户断线

我们都希望我们的互联网连接是一致和可靠的。然而，情况并非总是如此；因此，我们必须在设计中解决这个问题。当用户从互联网上断开连接时，客户端和服务器之间的持久性连接就会丢失。处理用户断开连接的一个天真的方法是将用户标记为离线，并在连接重新建立时将其状态改为在线。然而，这种方法有一个重大缺陷。用户在短时间内频繁地断开和重新连接到互联网是很常见的。例如，当用户通过隧道时，网络连接可能会打开和关闭。在每次断开/重新连接时更新在线状态会使存在指标变化得过于频繁，导致用户体验不佳。

我们引入一个心跳机制来解决这个问题。定期地，一个在线的客户端向在场服务器发送一个心跳事件。如果存在服务器在一定时间内收到心跳事件，比如说来自客户端的 X 秒，那么用户就被认为是在线的。否则，它就处于离线状态。

在图 12-18 中，客户端每 5 秒向服务器发送一个心跳事件。在发送了 3 个心跳事件后，客户端被断开连接，并且在 x=30 秒内没有重新连接（这个数字是任意选择的，以显示逻辑）。在线状态被改变为离线。

在线状态 fanout

用户 A 的朋友如何知道状态变化？图 12-19 解释了它是如何工作的。存在服务器使用一个发布-订阅模型，其中每个朋友对维护一个频道。当用户 A 的在线状态改变时，它将事件发布到三个频道，即频道 A-B、A-C 和 A-D。这三个频道分别由用户 B、C 和 D 订阅。因此，朋友们很容易得到在线状态的更新。客户端和服务器之间的通信是通过实时 WebSocket。

上述设计对小规模的用户群是有效的。例如，微信使用类似的方法，因为它的用户群上限为 500 人。对于较大的群组，通知所有成员的在线状态是昂贵和耗时的。假设一个群有 100,000 个成员。每一个状态变化将产生 100,000 个事件。为了解决性能瓶颈，一个可能的解决方案是只在用户进入群组或手动刷新好友列表时获取在线状态。

总结

在本章中，我们介绍了一个聊天系统架构，它支持 1 对 1 的聊天和小群组聊天。WebSocket 用于客户端和服务器之间的实时通信。聊天系统包含以下组件：用于实时消息传递的聊天服务器、用于管理在线存在的存在服务器、用于发送推送通知的推送通知服务器、用于聊天历史持久性的键值存储以及用于其他功能的 API 服务器。

如果你在采访结束时有多余的时间，这里有额外的谈话要点。

  • 扩展聊天应用程序以支持媒体文件，如照片和视频。媒体文件的大小明显大于文本。压缩、云存储和缩略图是有趣的话题，可以谈一谈。
  • 端到端加密。Whatsapp 支持信息的端到端加密。只有发件人和收件人可以阅读信息。有兴趣的读者可以参考参考资料中的文章[9]。
  • 在客户端缓存消息，可以有效减少客户端和服务器之间的数据传输。
  • 提高加载时间。Slack 建立了一个地理分布的网络来缓存用户的数据、频道等，以提高加载时间[10]。
  • 错误处理。
    • 聊天服务器的错误。一个聊天服务器可能有几十万，甚至更多的持续连接。如果一个聊天服务器离线，服务发现（Zookeeper）会提供一个新的聊天服务器，让客户建立新的连接。
    • 消息重发机制。重试和排队是重新发送消息的常用技术。

恭喜你走到这一步! 现在给自己拍拍屁股吧。干得好!

参考材料

[1] Erlang at Facebook
[2] Messenger and WhatsApp process 60 billion messages a day
[3] Long tail
[4] The Underlying Technology of Messages
[5] How Discord Stores Billions of Messages
[6] Announcing Snowflake
[7] Apache ZooKeeper
[8] From nothing: the evolution of WeChat background system (Article in Chinese)
[9] End-to-end encryption
[10] Flannel: An Application-Level Edge Cache to Make Slack Scale