System Design

Appearance

设计 Facebook Messenger ​

我们来设计一个类似于 Facebook Messenger 的即时消息服务，让用户可以通过网页和移动端发送文本消息。

1. 什么是 Facebook Messenger？ ​

Facebook Messenger 是一款软件应用，提供基于文本的即时消息服务。Messenger 用户可以通过手机或 Facebook 网站与其 Facebook 好友聊天。

2. 系统的需求和目标 ​

我们的 Messenger 应满足以下需求：

功能性需求：

  1. Messenger 应支持用户之间的一对一对话。
  2. Messenger 应能够跟踪用户的在线/离线状态。
  3. Messenger 应支持聊天记录的持久化存储。

非功能性需求：

  1. 用户应能体验到低延迟的实时聊天。
  2. 系统应具备高度一致性，用户在所有设备上都应能看到相同的聊天记录。
  3. Messenger 应具有高可用性；在追求一致性的前提下，可容忍较低的可用性。

扩展需求：

  • 群聊：Messenger 应支持多人在群组中进行交流。
  • 推送通知：当用户离线时，Messenger 应能够通知用户收到新消息。

3. 容量估算和约束 ​

假设我们有 5 亿日活跃用户，平均每位用户每天发送 40 条消息，这意味着每天的消息总量为 200 亿条。

存储估算：假设每条消息平均占用 100 字节，那么每天需要 2TB 的存储空间。

200亿条消息 * 100字节 = 2TB/天

要存储五年的聊天记录，大约需要 3.6 PB 的存储空间。

2TB * 365天 * 5年 \approx 3.6 PB

除了聊天消息，我们还需要存储用户信息、消息的元数据（如 ID、时间戳等）。以上计算未考虑数据压缩和复制需求。

带宽估算：如果我们的服务每天接收 2TB 数据，则每秒大约会有 25MB 的数据流入。

2TB / 86400秒 \approx 25 MB/s

由于每条传入消息需要发送给另一用户，上传和下载均需要相同的 25MB/s 带宽。

高层估算：

图6-1

4. 高层设计 ​

在高层设计中，我们需要一个作为核心的聊天服务器，用于协调用户之间的所有通信。当用户想要向另一用户发送消息时，会连接到聊天服务器，并将消息发送给服务器；服务器随后将消息传递给接收用户，并将消息存储到数据库中。

图6-2

详细的工作流程如下：

  1. 用户A通过聊天服务器向用户B发送消息。
  2. 服务器接收到消息，并向用户A发送确认回执。
  3. 服务器将消息存储到数据库中，并将消息发送给用户B。
  4. 用户B收到消息，并向服务器发送确认回执。
  5. 服务器通知用户A，消息已成功送达用户B。

图6-3

图6-4

图6-5

5. 详细组件设计 ​

首先，我们尝试构建一个简单的解决方案，将所有功能运行在一台服务器上。从高层次来看，系统需要处理以下用例：

  1. 接收传入消息并发送传出消息。
  2. 在数据库中存储和检索消息。
  3. 记录用户的在线或离线状态，并通知所有相关用户状态的变化。

接下来逐一分析这些场景：

a. 消息处理 ​

如何高效地发送和接收消息？
要发送消息，用户需要连接服务器并向其他用户发送消息。要从服务器接收消息，用户有两种选择：

  1. 拉取模式：用户可以定期向服务器请求查看是否有新消息。
  2. 推送模式：用户可以保持与服务器的连接，依靠服务器在有新消息时通知他们。

如果采用第一种方式，服务器需要跟踪尚未送达的消息，一旦接收用户连接服务器并请求新消息时，服务器即可返回所有未送达的消息。为了减少用户的延迟，用户需要频繁地检查服务器，但如果没有新消息，大多数时候会得到空响应。这会浪费大量资源，不是一个高效的解决方案。

如果采用第二种方式，即所有活跃用户都保持与服务器的连接，那么一旦服务器收到消息，可以立即将消息传递给目标用户。这样，服务器无需跟踪未送达消息，并且由于消息可以通过开放连接即时传递，延迟可以降到最低。

客户端如何保持与服务器的长连接？
我们可以使用HTTP长轮询或WebSocket。在长轮询中，客户端向服务器请求信息，并预期服务器不会立即响应。如果服务器在接收到轮询请求时没有新数据，则会保持请求打开，等待新信息可用时立即发送响应完成该请求。客户端收到响应后可以立即发出另一个请求以获取后续更新。这种方式显著提升了延迟、吞吐量和性能。长轮询请求可能会超时或接收到服务器的断开信号，此时客户端需要重新发起新请求。

服务器如何跟踪所有打开的连接以高效地将消息重定向给用户？服务器可以维护一个哈希表，其中“键”是用户ID，“值”是连接对象。当服务器收到某用户的消息时，它可以在哈希表中查找该用户的连接对象，并将消息发送到打开的请求中。

当服务器收到给离线用户的消息时会发生什么？
如果接收方已断开连接，服务器可以通知发送方消息未能传递。如果是暂时断开，例如接收方的长轮询请求超时，我们可以期望用户会重新连接。此时可以让发送方重试发送消息。重试逻辑可以嵌入到客户端中，这样用户无需重新输入消息。服务器也可以暂时存储消息，并在接收方重新连接后重试发送。

需要多少个聊天服务器？
假设支持同时连接5亿个用户，每台现代服务器可处理5万并发连接，则需要1万台服务器。

如何知道哪个服务器保存了用户的连接？
可以在聊天服务器前引入软件负载均衡器，将每个用户ID映射到对应的服务器以重定向请求。

服务器如何处理“消息投递”请求？
服务器接收新消息时需执行以下操作：

  1. 将消息存储到数据库；
  2. 将消息发送给接收方；
  3. 向发送方发送确认。 服务器会先找到保存接收方连接的服务器，将消息传递给该服务器以发送给接收方。随后，服务器向发送方发送确认；无需等待消息存储到数据库（该操作可在后台完成）。消息存储将在下一节讨论。

消息系统如何维护消息的顺序？
每条消息可以带有一个时间戳，表示服务器接收消息的时间。这并不能保证客户端的正确消息顺序。例如：

  1. 用户1发送消息M1给服务器传递给用户2。
  2. 服务器在时间T1接收到M1。
  3. 同时，用户2发送消息M2给服务器传递给用户1。
  4. 服务器在时间T2接收到M2，其中T2 > T1。
  5. 服务器将M1发送给用户2，将M2发送给用户1。

因此，用户1会先看到M1，再看到M2，而用户2会先看到M2，再看到M1。

为了解决这一问题，每个客户端的每条消息需带有一个序列号，用于确定每个用户的消息顺序。通过这种方式，两个客户端虽然看到的消息顺序不同，但每个用户在所有设备上都能看到一致的消息顺序。

b. 消息的存储与数据库检索 ​

每当聊天服务器收到新消息时，需要将其存储到数据库中。我们有两种选择：

  1. 启动一个单独的线程，与数据库交互以存储消息。
  2. 向数据库发送异步请求以存储消息。

在设计数据库时，需要注意以下几点：

  1. 如何高效地管理数据库连接池。
  2. 如何重试失败的请求。
  3. 如何记录那些重试后仍然失败的请求。
  4. 在所有问题解决后，如何重新尝试这些记录的失败请求。

应使用哪种存储系统？

我们需要一个支持高频率小规模更新并能快速获取一系列记录的数据库。这是因为大量小消息需要插入数据库，并且用户在查询时通常需要按顺序访问消息。

我们不能使用像MySQL这样的关系数据库或MongoDB这样的NoSQL数据库，因为无法在每次用户接收或发送消息时高效地进行数据库读写操作。这不仅会导致服务的基本操作出现高延迟，还会对数据库造成巨大负荷。

我们的需求可以通过宽列存储数据库（如 HBase）轻松满足。HBase是一种面向列的键值NoSQL数据库，能够针对一个键存储多个列的值。HBase基于Google的 BigTable 模型，并运行在Hadoop分布式文件系统（HDFS）之上。HBase将数据分组存储到内存缓冲区中，当缓冲区满时，将数据转存至磁盘。这种存储方式不仅可以快速存储大量小数据，还可以通过键或行范围扫描快速检索数据。此外，HBase适合存储大小不一的数据，这也符合我们的服务需求。

客户端如何高效地从服务器获取数据？

客户端在从服务器获取数据时应进行分页。分页大小可根据不同客户端而有所不同，例如，手机屏幕较小，因此在视窗中显示的消息或对话数量应较少。

c. 用户状态管理 ​

我们需要跟踪用户的在线/离线状态，并在状态变化发生时通知所有相关用户。由于我们在服务器上为所有活跃用户维护连接对象，因此可以轻松确定用户的当前状态。在任何时候有5亿个活跃用户的情况下，如果每次状态变化都要广播给所有相关的活跃用户，这将消耗大量资源。我们可以进行以下优化：

  1. 客户端在启动应用时，可以拉取其好友列表中所有用户的当前状态。
  2. 当用户向一个离线的用户发送消息时，可以向发送方发送失败通知，并在客户端更新该用户的状态。
  3. 当用户上线时，服务器可以延迟几秒钟后广播该状态，以确认用户不会立即离线。
  4. 客户端可以从服务器拉取在用户视窗中显示的用户的状态。这不应是频繁的操作，因为服务器会广播用户的在线状态，我们可以容忍用户的离线状态在一段时间内保持过时。
  5. 当客户端与另一个用户开始新聊天时，可以在此时拉取该用户的状态。

图6-6

设计总结: 客户端将与聊天服务器建立连接以发送消息；服务器随后将消息转发给请求的用户。所有活跃用户将与服务器保持连接，以接收消息。当新消息到达时，聊天服务器会通过长轮询请求将其推送给接收用户。消息可以存储在HBase中，该数据库支持快速的小规模更新和基于范围的搜索。服务器可以向其他相关用户广播用户的在线状态。客户端可以以较低的频率拉取在客户端视窗中可见用户的状态更新。

6. 数据分区 ​

由于我们将存储大量数据（五年内为3.6PB），需要将数据分布到多个数据库服务器上。我们的分区方案是什么？

基于用户ID的分区： 假设我们基于用户ID的哈希值进行分区，以便将用户的所有消息保存在同一数据库中。如果一个数据库分片为4TB，那么五年内我们将需要“3.6PB/4TB ≈ 900”个分片。为简便起见，我们假设使用1000个分片。因此，我们将通过“hash(UserID) % 1000”来查找分片编号，然后从那里存储/检索数据。这种分区方案还可以快速获取任何用户的聊天历史。

在最初，我们可以从较少的数据库服务器开始，在一台物理服务器上驻留多个分片。由于我们可以在一台服务器上有多个数据库实例，因此可以轻松地在一台服务器上存储多个分区。我们的哈希函数需要理解这种逻辑分区方案，以便能够将多个逻辑分区映射到一台物理服务器上。

由于我们将存储无限历史消息，可以从较大的逻辑分区数量开始，将其映射到较少的物理服务器上，随着存储需求的增加，我们可以添加更多的物理服务器以分布我们的逻辑分区。

基于消息ID的分区： 如果我们将用户的不同消息存储在不同的数据库分片中，获取聊天的一系列消息将非常慢，因此我们不应采用这种方案。

7. 缓存 ​

我们可以在用户视窗中可见的最近几条（例如最后15条）消息和最近几次（例如最后5次）对话中进行缓存。由于我们决定将用户的所有消息存储在一个分片上，因此用户的缓存也应完全驻留在一台机器上。

8. 负载均衡 ​

我们需要在聊天服务器前设置一个负载均衡器，该负载均衡器可以将每个用户ID映射到持有该用户连接的服务器，然后将请求指向该服务器。类似地，我们还需要为缓存服务器设置负载均衡器。

9. 故障容忍和复制 ​

如果聊天服务器发生故障会怎样？

我们的聊天服务器与用户保持连接。如果一台服务器宕机，是否应该设计机制将这些连接转移到其他服务器？将TCP连接故障转移到其他服务器非常困难；更简单的方法是让客户端在连接丢失时自动重新连接。

我们应该存储用户消息的多个副本吗？

我们不能仅有一份用户数据的副本，因为如果持有数据的服务器崩溃或永久宕机，我们将没有任何机制来恢复这些数据。为此，我们要么需要在不同的服务器上存储数据的多个副本，要么使用像Reed-Solomon编码这样的技术来分配和复制数据。

10. 扩展需求 ​

a. 群聊 ​

我们可以在系统中有单独的群聊对象，这些对象可以存储在聊天服务器上。群聊对象由 GroupChatID 标识，并将维护一个参与该聊天的人员列表。我们的负载均衡器可以根据 GroupChatID 定向每条群聊消息，处理该群聊的服务器可以迭代聊天中所有用户，找到每个用户连接的服务器以传递消息。

在数据库中，我们可以将所有群聊存储在一个单独的表中，并根据 GroupChatID 进行分区。

b. 推送通知 ​

在我们当前的设计中，用户只能向活跃用户发送消息，如果接收用户处于离线状态，我们会向发送用户发送失败通知。推送通知将使我们的系统能够向离线用户发送消息。

对于推送通知，每个用户可以从其设备（或网页浏览器）中选择接收通知，以便在有新消息或事件时进行通知。每个制造商维护一组服务器，负责将这些通知推送到用户。

为了在我们的系统中实现推送通知，我们需要设置一个通知服务器，该服务器将离线用户的消息发送到制造商的推送通知服务器，然后由该服务器将消息发送到用户的设备。