系统设计面试的行家指南（中）（2）

系统设计面试的行家指南（中）（1）https://developer.aliyun.com/article/1481939

十一、设计新闻订阅系统

在这一章中，你被要求设计一个新闻订阅系统。什么是新闻订阅源？根据脸书的帮助页面，“新闻提要是在你的主页中间不断更新的故事列表。新闻源包括状态更新、照片、视频、链接、应用活动 、 ，以及你在脸书上关注的人、页面和群组的赞。这是一个常见的面试问题。常见的类似问题有：设计脸书新闻提要、Instagram 提要、Twitter 时间线等。

第一步——了解问题并确定设计范围

第一组澄清性问题是当面试官让你设计一个新闻反馈系统时，你要明白她在想什么。至少，您应该弄清楚要支持哪些特性。下面是一个应聘者与面试官互动的例子：

考生 :这是手机 app 吗？还是一个 web app？还是两者都有？

面试官 :双方

候选人 :有哪些重要特征？

采访： 用户可以发表帖子，并在新闻订阅页面上看到她朋友的帖子。

候选人 : 新闻提要是按时间倒序排序还是按话题分数等任何特定顺序排序？例如，来自你亲密朋友的帖子得分更高。

面试官 : 为了简单起见，我们假设提要是按时间倒序排序的。

候选人 : 一个用户可以有多少好友？

面试官 : 5000

候选人 :车流量是多少？

面试官：1000 万 DAU

候选：feed 可以包含图片、视频，或者只是文字？

面试官 :可以包含媒体文件，包括图片和视频。

现在你已经收集了需求，我们集中精力设计系统。

第二步——提出高水平的设计并获得认同

设计分为两个流程：feed 发布和新闻 feed 构建。

Feed 发布：当用户发布帖子时，相应的数据被写入缓存和数据库。她朋友的新闻订阅源上有一个帖子。

新闻提要构建：为了简单起见，我们假设新闻提要是通过按时间倒序聚合朋友的帖子构建的。

新闻源 API

新闻提要 API 是客户端与服务器通信的主要方式。这些 API 是基于 HTTP 的，允许客户端执行操作，包括发布状态、检索新闻提要、添加好友等。我们讨论两个最重要的 API:提要发布 API 和新闻提要检索 API。

Feed 发布 API

要发布帖子，将向服务器发送 HTTP POST 请求。API 如下所示：

后/v1/me/进给

参数：

内容：内容是帖子的正文。

auth _ token:用于认证 API 请求。

新闻订阅源检索 API

检索新闻提要的 API 如下所示：

GET /v1/me/feed

参数：

auth _ token:用于认证 API 请求。

饲料出版

图 11-2 显示了提要发布流程的高层设计。

用户：用户可以在浏览器或移动应用程序上查看新闻源。一个用户通过 API 发布了一个内容为“你好”的帖子：

/v1/me/feed？内容=你好&认证令牌= {认证令牌}

负载均衡器：将流量分配给 web 服务器。

Web 服务器：Web 服务器将流量重定向到不同的内部服务。

Post 服务：在数据库和缓存中持久保存帖子。

Fanout 服务：向好友的新闻推送新内容。新闻订阅源数据存储在缓存中，以便快速检索。

通知服务：通知好友有新内容，发送推送通知。

新闻大楼

在本节中，我们将讨论新闻提要是如何在幕后构建的。图 11-3 显示了高层设计：

用户：用户发送请求来检索她的新闻提要。请求看起来是这样的： / v1/me/feed。

负载平衡器：负载平衡器将流量重定向到 web 服务器。

Web 服务器：Web 服务器将请求路由到新闻订阅服务。

新闻订阅服务：新闻订阅服务从缓存中获取新闻订阅。

新闻提要缓存：存储呈现新闻提要所需的新闻提要 id。

第三步——设计深潜

概要设计简要地涵盖了两个流程：提要发布和新闻提要构建。在这里，我们更深入地讨论这些话题。

供稿出版深潜

图 11-4 概述了 feed 发布的详细设计。我们已经讨论了高层设计中的大部分组件，我们将集中讨论两个组件：web 服务器和扇出服务。

网络服务器

除了与客户端通信之外，web 服务器还执行身份验证和速率限制。只有使用有效 auth_token 登录的用户才可以发帖。该系统限制用户在一定时间内可以发布的帖子数量，这对防止垃圾邮件和滥用内容至关重要。

扇出服务

扇出是向所有朋友发送帖子的过程。两种类型的扇出模型是：写时扇出(也称为推模型)和读时扇出(也称为拉模型)。两种模式各有利弊。我们解释他们的工作流程，并探索支持我们系统的最佳方法。

写时扇出。 用这种方法， 新闻提要是在编写时间内预先计算好的。新帖子发布后会立即发送到朋友的缓存中。

优点：

新闻提要实时生成，可以立即推送给朋友。

获取新闻提要的速度很快，因为新闻提要是在编写时预先计算的。

缺点：

如果一个用户有很多朋友，那么获取他们的好友列表并为他们生成新闻提要会非常缓慢和耗时。叫做热键问题。

对于不活跃的用户或者很少登录的用户来说，预先计算的新闻提要浪费了计算资源。

扇出上读 。新闻提要是在读取时生成的。这是一种随需应变的模式。当用户加载她的主页时，最近的帖子被拉出来。

优点：

对于不活跃的用户或者那些很少登录的用户来说，读取上的扇出工作得更好，因为它不会在他们身上浪费计算资源。

数据不会推送给朋友，所以不存在热键问题。

缺点：

获取新闻提要很慢，因为新闻提要不是预先计算的。

我们采用了一种混合方法，以获得两种方法的优点并避免其中的缺陷。因为快速获取新闻提要至关重要，所以我们对大多数用户使用推送模型。对于有很多朋友/关注者的名人或用户，我们让关注者按需拉新闻内容，以避免系统过载。一致哈希是一种缓解热键问题的有用技术，因为它有助于更均匀地分布请求/数据。

让我们仔细看看扇出服务，如图 11-5 所示。

扇出服务的工作方式如下：

1。从图形数据库中获取朋友 id。图形数据库适合于管理朋友关系和朋友推荐。有兴趣的读者希望了解更多关于这个概念的信息，可以参考参考资料[2]。

2。从用户缓存中获取朋友信息。然后，系统会根据用户设置过滤掉朋友。例如，如果你将某人设为静音，即使你们仍然是朋友，她的帖子也不会显示在你的新闻订阅源上。帖子可能不会显示的另一个原因是，用户可以有选择地与特定的朋友分享信息，或者对其他人隐藏信息。

3。将好友列表和新帖子 ID 发送到消息队列。

4。扇出工作器从消息队列获取数据，并将新闻提要数据存储在新闻提要缓存中。你可以把新闻提要缓存想象成一个 的映射表。每当一个新的文章发表，它将被附加到新闻提要表中，如图 11-6 所示。如果我们将整个用户和 post 对象存储在缓存中，内存消耗会变得非常大。因此，只存储 id。为了保持较小的内存大小，我们设置了一个可配置的限制。用户在新闻订阅中滚动浏览数千条帖子的可能性很小。大部分用户只对最新的内容感兴趣，所以缓存缺失率很低。

5。在新闻提要缓存中存储。图 11-6 显示了新闻提要在缓存中的样子。

新闻提要检索深度剖析

图 11-7 展示了新闻提要检索的详细设计。

如图 11-7 所示，媒体内容(图片、视频等。)存储在 CDN 中，以便快速检索。让我们看看客户机如何检索新闻提要。

1。用户发送请求来检索她的新闻提要。请求看起来是这样的： /v1/me/feed

2。负载平衡器将请求重新分配给 web 服务器。

3。Web 服务器调用新闻提要服务来获取新闻提要。

4。新闻提要服务从新闻提要缓存中获取一个帖子 id 列表。

5。用户的新闻提要不仅仅是一个提要 id 列表。它包含用户名，个人资料图片，帖子内容，帖子图片等。因此，新闻提要服务从缓存(用户缓存和帖子缓存)中获取完整的用户和帖子对象，以构建完整的新闻提要。

6。完整的新闻提要以 JSON 格式返回给客户端进行呈现。

高速缓存架构

对于新闻订阅系统来说，缓存非常重要。我们将缓存层分为 5 层，如图 11-8 所示。

新闻提要：存储新闻提要的 id。

内容：存储每条帖子的数据。热门内容存储在热缓存中。

社交图：存储用户关系数据。

动作：它存储了用户是否喜欢某个帖子、回复某个帖子或对某个帖子采取其他动作的信息。

计数器：存储点赞、回复、关注者、关注等计数器。

步骤 4 -总结

在这一章中，我们设计了一个新闻订阅系统。我们的设计包含两个流程：提要发布和新闻提要检索。

和任何系统设计面试问题一样，设计一个系统没有完美的方法。每个公司都有其独特的限制，你必须设计一个系统来适应这些限制。理解设计和技术选择的权衡非常重要。如果还有几分钟，可以谈谈可伸缩性问题。为了避免重复讨论，下面只列出了高层次的话题。

缩放数据库：

垂直缩放与水平缩放

SQL vs NoSQL

主从复制

读取副本

一致性模型

数据库分片

其他谈话要点：

保持 web 层无状态

尽可能多地缓存数据

支持多个数据中心

丢失消息队列的几个组件

监控关键指标。例如，用户刷新新闻提要时的高峰时间和延迟时间的 QPS 值得关注。

祝贺你走到这一步！现在给自己一个鼓励。干得好！

参考资料

[1] How News Feed Works:
https://www.facebook.com/help/327131014036297/
[2] Friend of Friend recommendations Neo4j and SQL Sever:
http://geekswithblogs.net/brendonpage/archive/2015/10/26/friend-of-friend-recommendations-with-neo4j.aspx

十二、设计聊天系统

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

聊天应用为不同的人执行不同的功能。明确具体的要求是非常重要的。例如，当面试官想到的是一对一的聊天时，你不希望设计一个专注于群聊的系统。重要的是探究特征需求 。

步骤 1 -了解问题并确定设计范围

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

当面试官让你设计一个聊天系统时，第一组澄清性问题应该明确她到底在想什么。至少，弄清楚你应该专注于一对一聊天还是群聊应用。你可能会问的一些问题如下：

候选人 :我们要设计什么样的聊天应用？1 对 1 还是基于小组？

面试官 :应该支持 1 对 1 和群聊。

考生 :这是手机 app 吗？还是一个 web app？还是两者都有？

面试官 :都有。

候选人 :这个 app 的规模有多大？创业 app 还是海量规模？

面试官 :应该支持 5000 万日活跃用户(DAU)。

候选人 :群聊，群成员限制是多少？

面试官 :最多 100 人

候选人 :聊天 app 有哪些重要的功能？它能支持附件吗？

面试官 : 1 对 1 聊天，群聊，在线指标。系统只支持短信。

候选人 :邮件大小有限制吗？

面试官 :是的，文字长度要小于 10 万字。

候选人 :需要端到端加密吗？

采访者 :现在不需要，但是如果时间允许的话，我们会讨论的。

候选人 :聊天记录要保存多久？

面试官 :永远。

在本章中，我们将重点设计一个像脸书信使这样的聊天应用，重点是以下功能：

低交付延迟的一对一聊天

小型群聊(最多 100 人)

在线状态

多设备支持。同一个账号可以同时登录多个账号。

推送通知

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

第二步——提出高水平的设计并获得认同

为了开发高质量的设计，我们应该对客户机和服务器如何通信有一个基本的了解。在聊天系统中，客户端可以是移动应用程序，也可以是 web 应用程序。客户端之间不直接通信。相反，每个客户端连接到一个聊天服务，它支持上面提到的所有功能。让我们把注意力集中在基本操作上。聊天服务必须支持以下功能：

接收其他客户端的消息。

为每条消息找到合适的收件人，并将消息转发给收件人。

如果收件人不在线，将该收件人的邮件保存在服务器上，直到她在线。

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

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

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

然而，接收端要复杂一些。因为 HTTP 是客户端发起的，所以从服务器发送消息并不简单。多年来，许多技术被用来模拟服务器发起的连接：轮询、长轮询和 WebSocket。这些都是在系统设计面试中广泛使用的重要技术，所以让我们来检查一下它们。

投票

如图 12-3 所示，轮询是一种客户端定期询问服务器是否有消息可用的技术。根据轮询频率的不同，轮询的成本可能会很高。回答一个大多数情况下答案为“否”的问题可能会消耗宝贵的服务器资源。

长轮询

因为轮询可能是低效的，下一步是长轮询(图 12-4)。

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

发送者和接收者不能连接到同一个聊天服务器。基于 HTTP 的服务器通常是无状态的。如果使用循环法进行负载平衡，接收消息的服务器可能不会与接收消息的客户端建立长轮询连接。

服务器无法判断客户端是否断开。

效率低下。如果用户聊天不多，长轮询仍然会在超时后进行定期连接。

WebSocket

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

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

前面我们说过，在发送端，HTTP 是一个很好的协议，但是由于 WebSocket 是双向的，没有很强的技术理由不把它也用于接收。图 12-6 显示了 WebSockets (ws)是如何用于发送方和接收方的。

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

高层设计

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

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

无状态服务

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

无状态服务 位于负载均衡器之后，其工作是根据请求路径将请求路由到正确的服务。这些服务可以是整体的或单独的微服务。我们不需要自己构建许多这样的无状态服务，因为市场上有可以轻松集成的服务。我们将深入讨论的一项服务是服务发现。它的主要工作是给客户端一个聊天服务器的 DNS 主机名列表，客户端可以连接到这些服务器。

有状态服务

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

第三方整合

对于一个聊天 app 来说，推送通知是最重要的第三方整合。 恰当的整合推送通知至关重要。更多信息请参考第十章设计通知系统。

可扩展性

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

如果我们提出一个所有东西都放在一台服务器上的设计，这可能会在面试官的脑海中升起一面大红旗。没有哪个技术专家会在一台服务器上设计出如此大的规模。单服务器设计是一个交易破坏者，原因有很多。其中单点故障是最大的。

然而，从单一服务器设计开始也是非常好的。确保面试官知道这是一个起点。把我们提到的所有东西放在一起，图 12-8 显示了调整后的高层设计。

在图 12-8 中，客户端维护一个持久的 WebSocket 连接到一个聊天服务器，用于实时消息传递。

聊天服务器方便消息发送/接收。

呈现服务器管理在线/离线状态。

API 服务器处理一切事务，包括用户登录、注册、更改个人资料等。

通知服务器发送推送通知。

最后，键值存储用于存储聊天历史。当离线用户在线时，她将看到她以前的所有聊天记录。

存储

现在，我们已经准备好了服务器，启动了服务，完成了第三方集成。技术堆栈的最底层是数据层。数据层通常需要一些努力来使它正确。我们必须做出的一个重要决定是决定使用哪种类型的数据库：关系数据库还是 NoSQL 数据库？为了做出明智的决定，我们将检查数据类型和读/写模式。

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

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

聊天系统的数据量巨大。之前的一项研究[2]显示，脸书信使和 Whatsapp 每天处理 600 亿条信息。

只经常访问最近的聊天记录。用户通常不会查找旧聊天。

虽然在大多数情况下会查看最近的聊天记录，但用户可能会使用需要随机访问数据的功能，如搜索、查看您的提及、跳转到特定消息等。这些情况应该得到数据访问层的支持。

一对一聊天应用的读写比例约为 1:1。

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

键值存储允许简单的横向扩展。

键值存储提供非常低的数据访问延迟。

关系数据库不能很好地处理数据的长尾效应。当索引变大时，随机访问的代价很高。

键值存储被其他经过验证的可靠聊天应用所采用。例如，脸书信使和不和谐都使用键值存储。脸书信使用 HBase [4]，不和用卡珊德拉[5]。

数据模型

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

一对一聊天的消息表

图 12-9 显示了一对一聊天的消息表。主键是 message_id ，帮助决定消息顺序。我们不能依靠 created _ at 来决定消息顺序，因为可以同时创建两条消息。

群聊消息表

图 12-10 显示了群聊的消息表。复合主键是 (channel_id, message_id)。 渠道和集团在这里代表同一个意思。channel_id是分区键，因为群聊中的所有查询都在一个频道中操作。

消息 ID

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

id 必须唯一。

id 应该可以按时间排序，这意味着新行比旧行具有更高的 id。

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

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

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

步骤 3 -设计深度潜水

在系统设计面试中，通常你会深入了解概要设计中的一些组件。对于聊天系统，服务发现、消息传递流和在线/离线指标值得深入研究。

服务发现

服务发现的主要作用是根据地理位置、服务器容量等标准为客户推荐最佳的聊天服务器。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)服务器发送推送通知。

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 store 获得新消息。

小组聊天流程

与一对一聊天相比，群聊的逻辑更加复杂。图 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 存储中。在线状态指示器显示用户登录后在线。

用户注销

当用户注销时，会经历如图 12-17 所示的用户注销流程。KV 商店中的在线状态更改为离线。在线状态指示器显示用户离线。

用户断开

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

我们引入了心跳机制来解决这个问题。在线客户端定期向在线服务器发送心跳事件。如果存在服务器在特定时间内(比如说 x 秒)从客户端接收到心跳事件，则认为用户在线。否则，它是脱机的。

在图 12-18 中，客户端每 5 秒向服务器发送一次心跳事件。发送 3 个心跳事件后，客户端断开连接，不重新连接，inx = 30 秒(这个数字是任意选择的，用来演示逻辑)。联机状态更改为脱机。

在线状态扇出

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

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

步骤 4 -总结

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

如果你在采访结束时有额外的时间，以下是额外的谈话要点：

扩展聊天 app，支持照片、视频等媒体文件。媒体文件的大小远远大于文本。压缩、云存储和缩略图是有趣的话题。

端到端加密。Whatsapp 支持消息的端到端加密。只有发件人和收件人可以阅读邮件。感兴趣的读者可以参考参考资料[9]中的文章。

在客户端缓存消息可以有效减少客户端和服务器之间的数据传输。

提高加载时间。Slack 建立了一个地理上分散的网络来缓存用户的数据、频道等。为了更好的加载时间[10]。

错误处理。

聊天服务器出错。可能有几十万个，甚至更多的持久连接到聊天服务器。如果聊天服务器离线，service discovery (Zookeeper)将为客户端提供一个新的聊天服务器来建立新的连接。

消息重发机制。重试和排队是重新发送消息的常用技术。

祝贺你走到这一步！现在给自己一个鼓励。干得好！

参考资料

[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://blog.discordapp.com/how-discord-stores-billions-of-messages-7fa6ec7ee4c7
[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

十三、设计搜索自动补全系统

在谷歌上搜索或在亚马逊购物时，当你在搜索框中输入时，一个或多个匹配的搜索词就会呈现在你面前。此功能被称为自动完成、提前键入、随键入搜索或增量搜索。图 13-1 展示了一个谷歌搜索的例子，当在搜索框中输入“晚餐”时，显示了一个自动完成的结果列表。搜索自动完成是许多产品的重要功能。这就引出了面试问题：设计一个搜索自动完成系统，也叫“设计 top k”或“设计 top k 最常搜索的查询”。

步骤 1 -了解问题并确定设计范围

解决任何系统设计面试问题的第一步是问足够多的问题来澄清需求。下面是一个应聘者与面试官互动的例子：

候选人 :是只支持搜索查询开头的匹配，还是也支持中间的匹配？

面试官 :只在搜索查询的开头。

候选人 :系统应该返回多少个自动完成建议？

面试官 : 5

候选人 :系统如何知道返回哪 5 条建议？

面试官 :这个是由人气决定的，由历史查询频率决定的。

考生 :系统支持拼写检查吗？

面试官 :不，不支持拼写检查或自动更正。

候选人 :搜索查询是英文的吗？

面试官 :是的。如果最后时间允许，可以讨论多语言支持。

候选人 :我们允许大写和特殊字符吗？

面试官 :不，我们假设所有的搜索查询都有小写字母字符。

候选人 :有多少用户使用该产品？

面试官：1000 万 DAU。

要求

下面是对需求的总结：

快速响应时间：当用户键入搜索查询时，自动补全建议必须足够快地出现。一篇关于脸书的自动完成系统的文章[1]揭示了该系统需要在 100 毫秒内返回结果。否则会造成口吃。

相关：自动完成建议应该与搜索词相关。

排序：系统返回的结果必须按人气或其他排名模型排序。

可扩展：系统可以处理高流量。

高可用：当系统的一部分离线、变慢或遇到意外网络错误时，系统应保持可用和可访问。

信封估算的背面

假设日活跃用户 1000 万(DAU)。

一个普通人每天会进行 10 次搜索。

每个查询字符串 20 字节数据：

假设我们使用 ASCII 字符编码。1 个字符= 1 个字节

假设一个查询包含 4 个单词，每个单词平均包含 5 个字符。

即每次查询 4×5 = 20 字节。

对于搜索框中输入的每个字符，客户端都会向后端发送一个请求，请求自动完成建议。平均而言，每个搜索查询发送 20 个请求。例如，当您输入完“晚餐”时，以下 6 个请求将被发送到后端。

search?q=d
search?q=di
search?q=din
search?q=dinn
search?q=dinne
search?q =dinner
~每秒 24000 次查询(QPS) = 1000 万用户 * 10 次查询/天 * 20 个字符 / 24 小时 / 3600 秒。
高峰 QPS = QPS * 2 = ~ 4.8 万

假设 20%的日常查询是新的。1000 万 * 10 次查询/天 * 每次查询 20 字节 * 20% = 0.4 GB。这意味着每天有 0.4GB 的新数据添加到存储中。

第二步——提出高水平的设计并获得认同

在高层，系统被分成两部分：

数据收集服务：收集用户输入的查询，并实时汇总。对于大型数据集，实时处理是不实际的；然而，这是一个很好的起点。我们将在深潜中探索更现实的解决方案。

查询服务：给定一个搜索查询或前缀，返回 5 个最常搜索的词语。

数据收集服务

让我们用一个简单的例子来看看数据收集服务是如何工作的。假设我们有一个存储查询字符串及其频率的频率表，如图 13-2 所示。一开始，频率表是空的。之后，用户依次输入查询twitch、twitter、twitter和twillo。图 13-2 显示了频率表是如何更新的。

查询服务

假设我们有一个频率表，如表 13-1 所示。它有两个字段。

查询：存储查询字符串。

频率：表示查询被搜索的次数。

当用户在搜索框中键入“tw”时，会显示以下前 5 个搜索到的查询(图 13-3)，假设频率表基于表 13-1。

要获得前 5 个最常搜索的查询，请执行以下 SQL 查询：

当数据集很小时，这是一个可接受的解决方案。当它很大时，访问数据库成为一个瓶颈。我们将深入探讨优化。

系统设计面试的行家指南（中）（3）https://developer.aliyun.com/article/1481942