第十二章：设计一个聊天系统 (Design A Chat System)

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

聊天应用程序为不同的人执行不同的功能。明确确切的需求非常重要。例如，如果面试官心里想着一对一聊天，而你却设计了一个专注于群聊的系统，那就不理想。因此，探索功能需求至关重要。

第 1 步 - 理解问题并确定设计范围

达成一致关于要设计的聊天应用类型至关重要。在市场上，有一对一聊天应用，如 Facebook Messenger、微信和 WhatsApp；也有专注于群聊的办公聊天应用，如 Slack；还有专注于大规模群体互动和低语音聊天延迟的游戏聊天应用，如 Discord。

首批澄清问题应当明确面试官在让你设计聊天系统时具体想要的是什么。至少要弄清楚你是否应该关注一对一聊天还是群聊应用。你可以问以下问题：

候选人：我们要设计什么样的聊天应用？是一对一的还是基于群组的？
面试官：它应该支持一对一和群组聊天。

候选人：这是移动应用吗？还是网页应用？或者两者都有？
面试官：两者都有。

候选人：这个应用的规模是多少？是初创应用还是大规模应用？
面试官：它应该支持每日活跃用户（DAU）5000万。

候选人：对于群聊，群成员的上限是多少？
面试官：最多支持100人。

候选人：对于聊天应用，哪些功能是重要的？它能支持附件吗？
面试官：一对一聊天、群聊、在线指示器。系统只支持文本消息。

候选人：有没有消息大小限制？
面试官：有，文本长度应少于100,000个字符。

候选人：是否需要端到端加密？
面试官：现在不需要，但如果时间允许，我们会讨论这个问题。

候选人：我们应该保存聊天记录多长时间？
面试官：永久保存。

在本章中，我们专注于设计一个类似于 Facebook Messenger 的聊天应用，重点关注以下功能：

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

同样，达成设计规模的一致意见也很重要。我们将设计一个支持每日活跃用户（DAU）5000万的系统。

第 2 步 - 提出高层设计并获得认可

要开发高质量的设计，我们应该对客户端和服务器之间的通信有基本的了解。在聊天系统中，客户端可以是移动应用或网页应用。客户端并不直接相互通信，而是每个客户端都连接到一个聊天服务，该服务支持上述所有功能。我们来关注基本操作。聊天服务必须支持以下功能：

• 接收来自其他客户端的消息。
• 找到每条消息的正确接收者，并将消息转发给接收者。
• 如果接收者不在线，将该接收者的消息保留在服务器上，直到接收者上线。

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

当客户端打算开始聊天时，它会使用一种或多种网络协议连接聊天服务。对于聊天服务，网络协议的选择非常重要。我们来和面试官讨论这个问题。

对于大多数客户端/服务器应用，请求是由客户端发起的。这对于聊天应用的发送方也是如此。在图12-2中，当发送者通过聊天服务向接收者发送消息时，它使用经过验证的 HTTP 协议，这是最常见的网络协议。在这种情况下，客户端与聊天服务建立 HTTP 连接并发送消息，通知服务将该消息发送给接收者。保持连接（keep-alive）在这里非常有效，因为保持连接头允许客户端与聊天服务维持持久连接。这还减少了 TCP 握手的次数。

HTTP 是发送方的一个不错的选择，许多流行的聊天应用程序（如 Facebook [1]）最初也是使用 HTTP 来发送消息的。

然而，接收方的情况就复杂一些。由于 HTTP 是客户端发起的，因此从服务器发送消息并不是简单的事情。多年来，许多技术被用于模拟服务器发起的连接：轮询、长轮询和 WebSocket。这些是系统设计面试中广泛使用的重要技术，我们来逐一审视它们。

轮询 (Polling)

如图12-3所示，轮询是一种技术，客户端定期询问服务器是否有可用消息。根据轮询频率，轮询可能会非常消耗资源。它可能会消耗宝贵的服务器资源来回答一个大多数时候都没有结果的问题。

长轮询 (Long Polling)

由于轮询可能效率低下，下一步进展是长轮询（如图12-4所示）。

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

• 发送者和接收者可能并未连接到同一聊天服务器。基于 HTTP 的服务器通常是无状态的。如果使用轮询（round robin）进行负载均衡，接收消息的服务器可能与接收该消息的客户端没有长轮询连接。
• 服务器没有好的方法来判断客户端是否断开连接。
• 效率低下。如果用户聊天不频繁，长轮询仍会在超时后定期建立连接。

WebSocket

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

WebSocket 连接由客户端发起。它是双向的并且是持久的。WebSocket 的生命周期始于 HTTP 连接，并通过一些明确的握手过程“升级”为 WebSocket 连接。通过这个持久连接，服务器可以向客户端发送更新。即使在防火墙的情况下，WebSocket 连接通常也能正常工作，因为它们使用的端口是 80 或 443，这些端口也用于 HTTP/HTTPS 连接。

之前我们提到，在发送方使用 HTTP 是一个不错的选择，但由于 WebSocket 是双向的，因此没有强有力的技术理由不在发送时也使用它。图12-6 显示了 WebSocket（ws）如何同时用于发送和接收。

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

高层设计

刚才我们提到选择 WebSocket 作为客户端与服务器之间的主要通信协议，因其支持双向通信。但需要注意的是，并非所有内容都必须使用 WebSocket。实际上，聊天应用的大多数功能（如注册、登录、用户配置文件等）可以使用传统的 HTTP 请求/响应方法。让我们深入探讨一下系统的高层组件。

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

无状态服务

无状态服务是传统的面向公众的请求/响应服务，用于管理登录、注册、用户配置文件等。这些功能在许多网站和应用程序中非常常见。无状态服务位于负载均衡器之后，负载均衡器的任务是根据请求路径将请求路由到正确的服务。这些服务可以是单体应用或独立的微服务。我们不需要自己构建许多无状态服务，因为市场上已经有可以轻松集成的服务。我们将深入讨论的一个服务是服务发现。其主要任务是向客户端提供可以连接的聊天服务器的 DNS 主机名列表。

有状态服务

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

第三方集成

对于聊天应用，推送通知是最重要的第三方集成。这是一种在新消息到达时通知用户的方式，即使应用未运行。正确集成推送通知至关重要。有关更多信息，请参阅第10章《设计一个通知系统》。

可扩展性

在小规模下，上述所有服务可以适合放在一台服务器上。即使在我们设计的规模上，理论上也可以将所有用户连接放在一台现代云服务器上。服务器能够处理的并发连接数量很可能是限制因素。在我们的场景中，当并发用户达到100万时，假设每个用户连接需要10KB的内存（这个数字非常粗略，且很大程度上取决于所选编程语言），那么只需要大约10GB的内存即可在一台机器上维持所有连接。

如果我们提出一个设计，所有东西都放在一台服务器上，这可能会在面试官心中引起警觉。没有技术人员会设计如此规模的单一服务器。单一服务器设计是一个致命问题，原因有很多，其中最大的原因是单点故障。

然而，开始时采用单一服务器设计是完全可以接受的。只要确保面试官知道这是一个起点。将我们提到的所有内容整合在一起，图12-8 显示了调整后的高层设计。

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

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

存储

此时，我们的服务器已经准备就绪，服务也在运行，第三方集成完成。技术栈的底层是数据层。数据层通常需要一些努力来正确实现。我们必须做出的一个重要决策是选择使用何种类型的数据库：关系型数据库还是NoSQL数据库？为了做出明智的决定，我们将检查数据类型和读写模式。

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

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

• 聊天系统的数据量是巨大的。早期研究 [2] 显示，Facebook Messenger和WhatsApp每天处理600亿条消息。
• 只有最近的聊天记录被频繁访问。用户通常不会查找旧聊天记录。
• 尽管在大多数情况下，用户会查看非常新的聊天历史，但他们可能会使用需要随机访问数据的功能，例如搜索、查看提及和跳转到特定消息等。这些情况应由数据访问层支持。
• 一对一聊天应用的读写比约为1:1。

选择正确的存储系统以支持我们所有的用例至关重要。我们推荐使用键值存储，原因如下：

• 键值存储允许轻松的横向扩展。
• 键值存储提供非常低延迟的数据访问。
• 关系型数据库无法很好地处理数据的长尾 [3]。当索引变得庞大时，随机访问的成本很高。
• 键值存储被其他可靠的聊天应用广泛采用。例如，Facebook Messenger和Discord都使用键值存储。Facebook Messenger使用HBase [4]，而Discord使用Cassandra [5]。

数据模型

刚才我们讨论了将键值存储用作我们的存储层。最重要的数据是消息数据。让我们仔细看一下。

一对一聊天的消息表

图12-9展示了一对一聊天的消息表。主键是message_id，它有助于确定消息顺序。我们不能依赖created_at来确定消息顺序，因为两条消息可以同时创建。

群聊的消息表

图12-10展示了群聊的消息表。复合主键为 (channel_id, message_id)。在此处，channel 和 group 表示相同的含义。channel_id 是分区键，因为群聊中的所有查询都在一个频道内操作。

消息ID

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

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

如何实现这两个保证？首先想到的是MySQL中的“auto_increment”关键字。然而，NoSQL数据库通常不提供这样的功能。

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

最后一种方法是使用本地序列号生成器。本地意味着ID仅在一个组内是唯一的。本地ID之所以可行，是因为在一对一通道或组通道中维护消息顺序已足够。与全局ID实现相比，这种方法更容易实现。

第3步 - 设计深入探讨

在系统设计面试中，通常要求你深入探讨高层设计中的某些组件。对于聊天系统，服务发现、消息流以及在线/离线状态指示器是值得深入研究的部分。

服务发现 (Service discovery)

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

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

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

消息流

了解聊天系统的端到端消息流是非常有趣的。在本节中，我们将探讨一对一聊天流、跨多设备的消息同步以及群聊消息流。

一对一聊天流

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

1. 用户A将聊天消息发送到聊天服务器1。
2. 聊天服务器1从ID生成器获取消息ID。
3. 聊天服务器1将消息发送到消息同步队列。
4. 消息被存储在键值存储中。
   5.a. 如果用户B在线，消息将转发到用户B连接的聊天服务器2。
   5.b. 如果用户B离线，则推送通知服务器（PN服务器）发送推送通知。
5. 聊天服务器2通过WebSocket持久连接将消息转发给用户B。

跨多设备的消息同步

许多用户拥有多个设备。我们将解释如何在多个设备之间同步消息。图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，消息同步变得简单，因为每个设备都可以从键值存储中获取新消息。

小组群聊消息流

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

图12-14解释了当用户A在群聊中发送消息时会发生什么。假设群组中有3个成员（用户A、用户B和用户C）。首先，用户A的消息会复制到每个群成员的消息同步队列中：一个给用户B，另一个给用户C。你可以将消息同步队列视为收件人的收件箱。这种设计对于小型群聊来说非常合适，因为：

• 它简化了消息同步流程，每个客户端只需检查自己的收件箱即可获取新消息。
• 当群组成员较少时，在每个收件人的收件箱中存储消息副本并不会占用太多资源。

微信采用了类似的方式，并将群组人数限制为500人 [8]。然而，对于用户众多的群组，为每个成员存储消息副本是不可接受的。

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

在线状态

在线状态指示器是许多聊天应用中的核心功能。通常，你会在用户的头像或用户名旁边看到一个绿色的点。本节解释了背后的工作原理。

在高层设计中，状态服务器负责管理用户的在线状态，并通过WebSocket与客户端通信。有几个流程会触发在线状态的变化，我们来逐一分析这些流程。

用户登录

用户登录流程已在“服务发现”部分解释。当客户端与实时服务之间建立了WebSocket连接后，用户A的在线状态以及last_active_at（最后活动时间戳）会被存储在键值存储（KV store）中。登录后，在线状态指示器显示该用户为在线状态。

用户登出

当用户登出时，会执行如图12-17所示的登出流程。在线状态在键值存储中被更新为离线状态，状态指示器显示该用户为离线状态。

用户断开连接

我们都希望互联网连接始终稳定可靠，但现实中并非如此，因此我们必须在设计中解决这一问题。当用户断开互联网连接时，客户端与服务器之间的持久连接会丢失。一个简单的处理方法是将用户标记为离线，当连接重新建立时再将状态更改为在线。然而，这种方法有一个主要缺陷：用户在短时间内频繁断开和重新连接是很常见的。例如，当用户通过隧道时，网络连接可能会断开又恢复。如果每次断开/重新连接都更新在线状态，状态指示器将频繁变化，导致用户体验差。

为解决这个问题，我们引入了心跳机制。在线客户端会定期向状态服务器发送心跳事件。如果状态服务器在设定时间（例如x秒）内收到客户端的心跳事件，则该用户被视为在线。否则，用户被视为离线。

在图12-18中，客户端每5秒向服务器发送一次心跳事件。在发送了3次心跳事件后，客户端断开连接且在x = 30秒（这个数值仅用于展示逻辑）内未重新连接，在线状态将更改为离线。

上述设计对于小型用户群体是有效的。例如，微信采用了类似的方式，因为其群组人数限制为500人。然而，对于更大的群组，通知所有成员在线状态的开销很大且耗时。假设一个群组有100,000名成员，每次状态更改都会生成100,000个事件。

为了解决这个性能瓶颈，一个可能的解决方案是仅在用户进入群组或手动刷新好友列表时获取在线状态。

第 4 步 - 总结

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

如果在面试结束时还有额外的时间，可以讨论以下扩展点：

• 扩展聊天应用以支持媒体文件：例如照片和视频。媒体文件的大小远大于文本，压缩、云存储和缩略图是可以深入探讨的有趣话题。
• 端到端加密：WhatsApp支持消息的端到端加密，只有发送者和接收者可以读取消息。感兴趣的读者可以参考参考资料中的文章 [9]。
• 客户端消息缓存：缓存消息能够有效减少客户端与服务器之间的数据传输。
• 提升加载时间：Slack建立了地理分布式网络，以缓存用户数据、频道等，提升加载时间 [10]。
• 错误处理：
  • 聊天服务器错误：一个聊天服务器可能有成千上万甚至更多的持久连接。如果一个聊天服务器离线，服务发现（Zookeeper）会为客户端提供一个新的聊天服务器以重新建立连接。
  • 消息重发机制：重试和排队是常见的消息重发技术。

恭喜你走到这一步！给自己一个鼓励，做得很棒！

参考文献

[1] Erlang at Facebook: https://www.erlangfactory.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-numbermessages-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/facebookengineering/the-underlying-technology-of-messages/454991608919/

[5] How Discord Stores Billions of Messages: https://blog.discordapp.com/how-discordstores-billions-of-messages-7fa6ec7ee4c7

[6] Announcing Snowflake: https://blog.twitter.com/engineering/en_us/a/2010/announcingsnowflake.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-scaleb8a6400e2f6b