系统设计-Ch12-设计一个聊天系统

设计一个聊天系统

几乎每个人都会使用聊天app，下图展示了一些应用市场上最为流行的聊天app：

市场上的聊天app并不是同质化的，针对不同类型的用户，不同的聊天app会侧重不同的功能。在市场上，有Fackbook、Messenger、微信和Whatsapp等一对一聊天应用，Slack等专注于群聊的办公室聊天应用，或Discord等专注于大型群聊和低语音聊天延迟的游戏聊天应用。因此面试官确定准确的需求是非常重要的。

Step1：Understand the problem and establish design scope

对于”设计一个聊天系统“这个系统设计话题，我们可以向面试官提出以下问题：

  • Q：我们应该设计一个什么样的聊天应用？一对一还是群聊？

    A：它应该支持一对一聊天和群聊

  • Q：是一个移动应用程序还是一个Web应用程序?

    A：二者兼而有之

  • Q：哪些功能对于这个聊天功能很重要呢？像是发表情，传文件？

    A：一对一聊天低延迟，多人聊天（最多100人），其他人的在线情况，系统暂时仅支持文本聊天

  • Q：消息有大小限制么？

    A：是的，文本长度应该少于100000个字符

  • Q：是否需要端到端加密？

    A：暂时不需要，如果时间允许，我们会讨论的

  • Q：我们要把聊天记录保存多久？

    A：永远

  • Q：同一个账户可以同时登录到多个设备么？

    A：是的，应该支持

  • Q：这个应用的规模是多大？

    A：计划是5000万日活跃用户(DAU)

Step2：Propose high-level design and get buy-in

我们首先应该对客户端和服务端如何通信有基本的了解，在聊天系统中，客户端可以是手机应用，也可以是Web应用。但客户端之间不能直接进行通信，而是每个客户端的消息都通过服务端的Chat Service转发给另一个客户端（群聊就是另外多个客户端）。让我们把重心放在基本操作上，Chat Service必须支持以下功能：

  • 接收来自其它客户端（发送者）的信息
  • 为每条信息找到正确的接收者
  • 如果接收者不在线，把接收者的信息暂存在服务器上，直到它联机为止

下图展示了客户端（发送方sender和接收方receiver）

当客户端打算开始聊天时，它会使用一个或多个网络协议连接聊天服务。对于聊天服务来说，网络协议的选择很重要，让我们来和面试官详细讨论一下：

对于大多数Client/Server架构的应用程序，请求都是由客户端发起的。对于聊天应用也是如此，在上图中，当发送方通过Chat Service向接收方发送消息时，它使用HTTP(s)协议，这是最常见的Web协议。在这种情况下客户端与服务端的Chat Service建立HTTP连接并发送消息，来通知Chat Service把消息转发给接收方。这个时候建立keep-alive是更加高效的，因为keep-alive header允许客户端保持与服务端的Chat Service持久连接，可以减少TCP的握手次数。因此HTTP在发送方是一个不错的选择，许多流行的聊天应用程序(如Facebook)最初使用HTTP发送消息。

然而，接收方这一边要复杂一些，由于HTTP协议在C/S架构中一般都是客户端发起的，因此从服务端发送消息并非易事。多年来，许多技术用于模拟服务器启动的连接：Polling(轮询)，Long Polling(长轮询)和WebSocket。这些都是在系统设计面试中广泛使用的重要技术，因此让我们来一一介绍它们。

Network Protocols

Polling

如下图所示，轮询是一种客户端定期询问服务器是否有可用消息的技术，根据轮询频率不同，轮询的成本也不同。它可能会消耗宝贵的服务器资源来返回当前没有消息的结果。

Long Polling

由于轮询并不高效，下一个要介绍的是长轮询，如下图所示：

在长轮询中，客户端保持连接打开(keep-alive)，直到有新消息或者达到HTTP连接超时阈值。一旦客户端收到新消息，它会立即重启这个进程(重新对HTTP连接计时)，向服务器发送另一个请求。

缺点：

  • 发送方和接收方可能连接到的不是同一个聊天服务器。基于HTTP的服务器是无状态的。如果使用round robin(循环调度)的负载均衡策略，则接收消息的服务器和接收消息的客户端无法建立长轮询连接。
  • 服务端没有比较好的办法来判断客户端是否已断开连接
  • 效率低下。如果用户不经常聊天，长轮询仍然会在超时后定期连接，这无疑浪费服务器资源

WebSocket

WebSocket是从服务端到客户端发送异步更新(asynchronous update)的最常见解决方案，如下图所示：

与HTTP协议不同，WebSocket协议在客户端和服务器之间只建立一次连接，之后就可以保持连接状态，客户端和服务器之间可以随时互相发送消息，实现实时通信和数据传输。客户端和服务器之间的通信是基于帧（frame）进行的，帧是WebSocket协议中的最小数据单位，包含一个或多个数据块，可以是文本或二进制数据。

WebSocket协议使用HTTP/1.1协议的Upgrade头部字段来升级连接，从HTTP协议切换到WebSocket协议。在握手阶段，客户端向服务器发送Upgrade请求，请求升级为WebSocket协议。如果服务器支持WebSocket协议，它将发送响应，客户端和服务器之间的连接就升级为WebSocket连接。

需要注意的是，WebSocket协议在使用时需要注意安全性问题，因为它允许客户端和服务器之间进行双向通信，如果未做好安全措施，可能会导致安全隐患。常见的安全措施包括使用SSL/TLS加密协议、使用安全的身份验证机制等。

之前我们说过，HTTP在发送方是一个不错的选择，许多流行的聊天应用程序最初使用HTTP发送消息，但由于WebSocket是支持双向通信的，我们在发送方也使用WebSoket显然是更好的选择。

上一节我们提到，WebSocket被选为客户端和服务器之间的主要通信协议，用于双向通信。需要注意的是，除了Chat Service其它的服务都不必是WebSocket协议。事实上，聊天应用程序的大多数功能(注册、登录、用户配置文件等)都可用使用HTTP上的传统request/response方法。让我们深入了解一下系统的高级组件。

High-Level Design

如下图所示，聊天系统分为三大类，无状态服务(Stateless)，有状态服务(Stateful)和第三方集成(Thrid-party)：

Stateless Service

无状态服务就是传统的request/response服务，用于管理登录、注册、用户配置等这些许多网站和应用程序的常见功能。无状态服务位于负载均衡器后面，由负载均衡器根据请求路径将请求路由到正确的服务。这些服务可以是单体式架构，也可以是单独的微服务架构。

我们将深入讨论的一项服务是服务发现，它的主要工作是向客户端提供客户端可以连接的服务器的DNS主机列表。

Stateful Service

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

Thrid-party Integration

对于聊天应用来说，推送通知是最重要的第三方集成，这是一种在新消息到达时通知用户的方式，即使聊天应用没有运行。有关更多的信息，可用参考第10章设计通知系统。

把上述服务整合起来，就得到了如下分布式架构：

  • WebSocket：

    • Chat Servers用于发送/接收消息
    • Presence Servers管理在线/离线状态

  • Http：

    • API Servers处理其它事务，包括用户登录、注册、更改配置等功能

  • Thrid-Party

    • Notification Servers发送推送通知

  • 最后，key-value存储引擎存储聊天历史记录。当离线用户重新上线时，她能看到以前的所有聊天记录

Storage

技术栈的深层是数据层，我们必须做出一个重要的决定：是使用SQL还是NoSQL数据库？
为了做出明智的决定，我们将重新审视一下我们的数据类型和读写模式：

在一个典型的聊天系统中存在两种类型的数据。第一种是通用数据，如用户资料、用户设置和好友列表。这些数据存储在强大可靠的关系型数据库（SQL）中，随使可用复制和分片技术扩展数据库；第二种是聊天系统独有的数据–聊天历史数据，聊天历史中的消息可能包含文本、图片、音频和视频等多种类型的数据，这些数据的结构可能不同，难以在关系型数据库中进行高效地存储和查询。NoSQL数据库通常可以更好地处理大规模的数据存储和访问，并且就聊天消息这种半结构化/非结构化数据而言，可以比SQL更容易实现水平扩展，此外，NoSQL数据库通常具有更高的性能和更低的延迟，这对于处理实时聊天数据非常重要。因此我们更推荐使用Key-Value键值存储的NoSQL数据库。

Data Model

现在我们来仔细看看消息数据的设计。

Message table for 1 to 1 chat

下图展示了1对1的聊天消息表设计，主键是<message_id>，它有助于决定消息序列的有序性，我们不能通过created_at来决定消息序列，因为可以同时创建多个消息。

Message table for group chat

下图展示了群聊的聊天消息表设计，复合主键是<channel_id, message_id>，channel在这里跟group是一个意思。channel_id是分区键，因为群聊中的所有查询都在同一个通道中操作。

<message_id>负责确定消息的顺序，因此必须满足以下两个要求：

  • <message_id>必须是唯一的
  • <message_id>应该按照时间粗略有序

如何生成<message_id>，可以参考第七章：设计分布式ID生成器

Step3：Design deep dive

在系统设计面试中，通常你需要深入了解高级设计中的一些组件。对于聊天系统，服务发现(Service Discovery)，消息流(Message Flows)和在线/离线指标(online/ offline indicator)值得深入探讨。

Service Discovery

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

下图展示了ZooKeeper的服务发现是如何工作的：

  1. 用户A尝试登录应用程序
  2. 负载均衡器向API服务器发送登录请求
  3. 后端对用户进行身份验证后，服务发现为用户A找到最佳的聊天服务器。在本例中，选择服务器2，并将服务器信息返回给用户A
  4. 用户A通过WebSocket连接聊天服务器2

Message Flows

聊天系统的端到端流程是很有趣的，我们将讨论1对1聊天流程、多设备间消息同步和群聊流程。

1 on 1 chat flow

下图展示了当用户A发送一条消息给用户B时会发生什么：

  1. User A向Chat Server1 发送聊天信息
  2. Chat Server1从ID生成器中获取<message_id>
  3. Chat Server1将消息发送到消息同步队列
  4. 消息写入存储到key-value数据库中
  5. 如果User B在线，聊天消息会转发到User B所在的Chat Server 2；如果User B不在线，则给推送PN Servers，由它发送推送通知
  6. Chat Server 2将消息转发给User B

Message synchronization across multiple devices

许多用户拥有多个设备(手机、平板、电脑等)，下图展示了在多个设备之间同步消息的示例：

在图中，User A拥有两个设备，一部手机和一台笔记本电脑。当用户A用手机登录聊天程序时，它会与Chat Server 1建立WebSocket连接。类似地，在用笔记本电脑登录时也会与Chat Server 1建立连接。

每台设备都维护了一个名为<cur_max_message_id>的变量，用于跟踪设备上的最新消息id。满足以下两个条件的消息被视为新消息：

  • 消息接收者ID等于当前登录的用户ID
  • 消息的message_id键值大于当前登录设备的<cur_max_message_id>

这样每台设备都能够很容易的从k-v数据库中拉取到自己的新消息。

Small group chat flow

与1对1聊天相比，群聊的逻辑更加复杂，下图展示了群聊的流程：

上图解释了当User A在群聊中发送消息时发生什么：
假设组中有3个成员(User A、User B、 User C)。首先，来自用户A的消息被复制到每个组成员的消息同步队列中—图中就被复制到了User B的消息同步队列和User C的消息同步队列。你可用把消息同步队列视为消息接收者的邮箱。每个接收者都只有一个消息同步队列，其中包含不同消息发送者的消息，如下图所示：

这种设计非常适合小型群聊：

  • 因为它简化了消息同步流程，因为每个客户端只需要检查自己的消息同步队列就能获取新消息
  • 当组内人数很少时，在每个消息接收者中存储一份副本并不算昂贵

微信就采用了类似的方法，它将一个群组成员限制在500人以内（200以上需要邀请，上限500)。

但是，对于拥有大量用户的群组，为每个成员创建一个消息同步队列来存储消息副本是不可接受的。

Online/Offline Indicator

在线状态指示器， 是许多聊天应用程序的基本功能。通常，你可用看用户的个人资料图片是否是彩色，或者看用户名旁边是否有一个绿点来判断一个用户是否在线。

在High-Level Design中，Presence Sever负责管理在线状态，并通过WebSocket与客户端进行通信。有几个流程会触发在线状态的更改，让我们逐个研究一下：

  • User Login：用户登录会建立WebSocket连接，把用户状态修改成在线
  • User Logout：用户等出会断开WebSocket连接，把用户状态修改成离线
  • **User disconnection：**用户断连，这种情况不能简单地直接修改用户状态，因为用户在短时间内频繁断开和重新连接是很常见的，这样频繁修改状态会对数据库造成不小的压力。因此，我们可用引入一种心跳机制来解决这个问题：让客户端定期向Presence Server发送检测信号，如果服务器在指定的时间内接收到了该信号，则用户被视为在线，否则，它将处于离线状态

Online Status Fanout

目前只是Presence Server知道所有用户状态，那么User A的朋友是如何知道User A的状态更改的呢？下图解释了它的工作原理：

Presence Server使用发布-订阅模型，其中每个**好友对(User A - User B)**维护一个channel，当用户A发送状态变化时，Presence Server会向图中每个channel发送一个通知事件，因此，朋友很容易获取在线状态的更新。

这个方式也是仅针对小用户群体是有效的，比如说微信也采用了类似的方式。但对于较大的群体来说（比如说10000个群成员），每当有状态修改时，会产生10000个通知事件。为解决性能瓶颈，一种可行的解决方案是仅当用户进入群聊或者手动刷新好友列表时，来获取最新的好友在线状态。

Step4：Warm up

如果你在面试结束前有多余的时间，你也可以跟面试官进一步探讨以下问题：

  • 如何实现同一个账户可以同时登录到多个设备？
  • 如何实现聊天信息的端到端加密？
  • 如何设计客户端缓存消息，来减少客户端和服务器之间的数据传输?
  • 媒体文件的大小明显远大于文本，云存储和媒体压缩技术也会是有趣的话题
  • 聊天消息撤销、重发机制设计