需求
让我们设计一个像Facebook Messenger这样的即时消息服务，用户可以通过web和移动界面相互发送文本消息。
1.什么是Facebook Messenger？
Facebook Messenger是一种软件应用程序，它向用户提供基于文本的即时消息服务。Messenger用户可以通过手机和Facebook网站与Facebook好友聊天。
2.系统的要求和目标
我们的信使应满足以下要求：
功能要求：
1.Messenger应支持用户之间的一对一对话。2.Messenger应跟踪其用户的在线/离线状态。3.Messenger应支持聊天历史记录的持久存储。
非功能性要求：
1.用户应具有实时聊天体验，且延迟最小。
2.我们的制度应该高度一致；用户应该能够在所有浏览器上看到相同的聊天历史记录
他们的设备。
3.Messenger的高可用性是可取的；为了客户的利益，我们可以容忍低可用性一致性
扩展要求：
•群聊：Messenger应支持多人在群聊中相互交谈。
•推送通知：Messenger应能够在用户收到新消息时通知用户离线。
3.容量估计和限制
假设我们每天有5亿活跃用户，平均每个用户每天发送40条消息；这给我们每天200亿条信息。
存储估计：
假设一条消息平均为100字节，因此要存储一天的所有消息，我们需要2TB的存储空间。
200亿条消息*100字节=>2 TB/天
要存储五年的聊天历史，我们需要3.6 PB的存储空间。
2 TB*365天*5年~=3.6 PB
除了聊天信息，我们还需要存储用户信息、消息元数据（ID、时间戳等）。更不用说，上面的计算没有考虑数据压缩和复制。
带宽估计：
如果我们的服务每天获得2TB的数据，这将为我们每秒提供25MB的传入数据。
2 TB/86400秒~=25 MB/s
由于每个传入的消息都需要发送给另一个用户，因此上传和下载都需要相同的25MB/s带宽。
扩展估计：
每天总消息存储量为200亿条，每天存储量为2TB
存储5年3.6PB输入数据25MB/s输出数据25MB/s
4.高级设计
在高层次上，我们需要一个聊天服务器，它将是中心部分，协调用户之间的所有通信。当一个用户想要向另一个用户发送消息时，他们将连接到聊天服务器并将消息发送到服务器；然后，服务器将该消息传递给其他用户，并将其存储在数据库中。
详细的工作流程如下所示：
1.用户A通过聊天服务器向用户B发送消息。
2.服务器接收消息并向用户A发送确认。
3.服务器将消息存储在其数据库中，并将消息发送给用户B。
4。User-B接收消息并向服务器发送确认。
5.服务器通知用户A消息已成功传递给用户B。发送消息的请求流
5.详细部件设计
让我们首先尝试构建一个简单的解决方案，其中所有内容都在一台服务器上运行。在高层，我们的系统需要处理以下用例：
1.接收传入消息并传递传出消息。
2.从数据库中存储和检索消息。
3.记录哪些用户在线或离线，并通知所有相关用户
这些状态会发生变化。
让我们逐一讨论这些场景：
A.消息处理
我们如何有效地发送/接收信息？要发送消息，用户需要连接到服务器并为其他用户发布消息。要从服务器获取消息，用户有两个选项：
1.拉模式：用户可以定期询问服务器是否有任何新消息。
2.推送模式：用户可以保持与服务器的连接打开，并且可以依赖于服务器
每当有新消息时通知他们。
如果我们使用第一种方法，那么服务器需要跟踪仍在等待传递的消息，一旦接收用户连接到服务器请求任何新消息，服务器就可以返回所有挂起的消息。为了最大限度地减少用户的延迟，他们必须非常频繁地检查服务器，如果没有挂起的消息，大部分时间他们将得到一个空响应。这将浪费大量资源，看起来不是一个有效的解决方案。
如果我们采用第二种方法，即所有活动用户都保持与服务器的连接打开，那么一旦服务器收到消息，它就可以立即将消息传递给预期用户。这样，服务器就不需要跟踪挂起的消息，我们将有最小的延迟，因为消息在打开的连接上立即传递。
客户端如何保持与服务器的开放连接？
我们可以使用HTTP长轮询或WebSocket。在长轮询中，客户端可以从服务器请求信息，期望服务器不会立即响应。如果在收到轮询时服务器没有客户端的新数据，则服务器将保持请求打开并等待响应，而不是发送空响应
响应信息变得可用。一旦有了新信息，服务器会立即向客户端发送响应，完成打开请求。在收到服务器响应后，客户机可以立即发出另一个服务器请求，以便将来进行更新。这在延迟、吞吐量和性能方面提供了很多改进。长轮询请求可能会超时，也可能会收到与服务器的断开连接，在这种情况下，客户端必须打开一个新请求。
服务器如何跟踪所有打开的连接，从而有效地将消息重定向到用户？
服务器可以维护一个哈希表，其中“key”是用户id，“value”是连接对象。因此，每当服务器收到用户的消息时，它都会在哈希表中查找该用户以查找连接对象，并在打开请求时发送消息。
当服务器收到脱机用户的消息时会发生什么情况？
如果接收方已断开连接，服务器可以通知发送方传递失败。如果是临时断开连接，例如，接收器的长轮询请求刚刚超时，那么我们应该期待用户重新连接。在这种情况下，我们可以要求发件人重试发送邮件。此重试可以嵌入到客户端的逻辑中，这样用户就不必重新键入消息。服务器还可以将消息存储一段时间，并在接收器重新连接后重试发送。
我们需要多少聊天服务器？
让我们计划在任何时候建立5亿个连接。假设一台现代服务器可以在任何时候处理50K并发连接，我们将需要10K这样的服务器。
我们如何知道哪个服务器拥有与哪个用户的连接？
我们可以在聊天服务器前面引入一个软件负载均衡器；它可以将每个用户标识映射到服务器以重定向请求。
服务器应如何处理“传递消息”请求？
服务器在收到新消息时需要执行以下操作：1）将消息存储在数据库中2）将消息发送给接收者，3）向发送者发送确认。
聊天服务器将首先找到为接收者保留连接的服务器，并将消息传递给该服务器以将其发送给接收者。然后，聊天服务器可以向发送者发送确认；我们不需要等待将消息存储在数据库中（这可能发生在后台）。
Messager如何维护消息的顺序？
我们可以为每条消息存储一个时间戳，即服务器接收消息的时间。这仍然无法确保为客户端正确排序消息。服务器时间戳无法确定消息的确切顺序的场景如下所示：
1.User-1向User-2的服务器发送消息M1。
2.服务器在T1接收M1。
3.同时，用户2向用户1的服务器发送消息M2。
4.服务器在T2处接收消息M2，使得T2>T1。
5.服务器向用户2发送消息M1，向用户1发送消息M2。
所以User-1会先看到M1，然后是M2，而User-2会先看到M2，然后是M1
为了解决这个问题，我们需要为每个客户端的每条消息保留一个序列号。此序列号将确定每个用户消息的确切顺序。使用此解决方案，两个客户端都将看到消息序列的不同视图，但此视图在所有设备上都是一致的。
B存储和检索数据库中的消息
每当聊天服务器收到新消息时，它都需要将其存储在数据库中。为此，我们有两种选择：
1.启动一个单独的线程，该线程将与数据库一起存储消息。
2.向数据库发送异步请求以存储消息。
在设计数据库时，我们必须牢记以下几点：
- 1.如何有效地使用数据库连接池。
- 2.如何重试失败的请求。
- 3.在何处记录即使重试也失败的请求。
- 4.所有问题解决后，如何重试这些记录的请求（重试后失败）。
我们应该使用哪种存储系统？
我们需要有一个数据库，可以支持一个非常小的更新率高，也可以快速获取一系列的记录。这是必需的，因为我们需要在数据库中插入大量的小消息，并且在查询时，用户最感兴趣的是按顺序访问这些消息。
我们不能像MySQL那样使用RDBMS，也不能像MongoDB那样使用NoSQL，因为我们无法在用户每次接收/发送消息时从数据库读/写一行。这不仅会使我们的服务的基本操作以高延迟运行，还会在数据库上造成巨大的负载。
通过像HBase这样的宽列数据库解决方案，我们可以轻松满足这两个需求。HBase是一个面向列的键值NoSQL数据库，可以针对一个键将多个值存储到多个列中。HBase以Google的BigTable为模型，运行在Hadoop分布式文件系统（HDFS）之上。HBase将数据分组，将新数据存储在内存缓冲区中，一旦缓冲区已满，它会将数据转储到磁盘。这种存储方式不仅有助于快速存储大量小数据，还可以通过键或扫描行范围获取行。HBase也是一个高效的数据库，用于存储各种大小的数据，这也是我们的服务所需要的。
客户端应该如何有效地从服务器获取数据？
从服务器获取数据时，客户端应分页。对于不同的客户端，页面大小可能不同，例如，手机屏幕较小，因此我们需要在视口中减少消息/对话的数量。
C管理用户的状态
我们需要跟踪用户的在线/离线状态，并在状态发生变化时通知所有相关用户。由于我们在服务器上为所有活动用户维护一个连接对象，因此我们可以很容易地从中了解用户的当前状态。随时拥有5亿活跃用户，如果有必要的话
将每个状态更改广播给所有相关的活动用户，将消耗大量资源。我们可以围绕此进行以下优化：
- 1.每当客户端启动应用程序时，它都可以提取其好友列表中所有用户的当前状态。
- 2.每当一个用户向另一个已脱机的用户发送消息时，我们都可以向发送失败消息发送程序并更新客户端上的状态。
- 3.每当用户联机时，服务器总是可以以几秒钟的延迟广播该状态秒，以查看用户是否没有立即脱机。
- 4.客户机可以从服务器上获取显示在用户屏幕上的用户的状态视口。这不应该是一个频繁的操作，因为服务器正在广播联机状态,我们可以暂时忍受用户陈旧的脱机状态。
- 5.每当客户机开始与另一个用户进行新的聊天时，我们都可以提取当时的状态。
设计概要：
客户端将打开与聊天服务器的连接以发送消息；然后，服务器将其传递给请求的用户。所有活动用户都将保持与服务器的连接打开以接收消息。每当新消息到达时，聊天服务器就会在长轮询请求中将其推送到接收用户。消息可以存储在HBase中，它支持快速的小更新，并且范围广泛
基于搜索。服务器可以向其他相关用户广播用户的联机状态。客户端可以不太频繁地为在客户端视口中可见的用户获取状态更新。
6.数据分区
由于我们将存储大量数据（5年3.6PB），我们需要将其分发到多个数据库服务器上。
我们的分区方案是什么？
- 基于UserID的分区：假设我们基于UserID的散列进行分区，这样我们就可以将用户的所有消息保存在同一个数据库中。如果一个DB碎片是4TB，我们将拥有“3.6PB/4TB~=900”碎片五年。为了简单起见，假设我们保留1K个碎片。因此，我们将通过“hash（UserID）00”找到碎片号，然后从中存储/检索数据。此分区方案还可以非常快速地获取任何用户的聊天历史记录。
一开始，我们可以使用较少的数据库服务器，在一台物理服务器上驻留多个碎片。因为我们可以在一台服务器上有多个数据库实例，所以我们可以很容易地在一台服务器上存储多个分区。我们的散列函数需要理解这个逻辑分区方案，以便它能够映射一台物理服务器上的多个逻辑分区。
由于我们将存储无限的消息历史记录，我们可以从大量的逻辑分区开始，这些分区将映射到更少的物理服务器，并且随着存储需求的增加，我们可以添加更多的物理服务器来分发我们的逻辑分区。
- 基于MessageID的分区：如果我们将用户的不同消息存储在单独的数据库碎片上，则获取聊天的一系列消息将非常缓慢，因此我们不应采用此方案。
7.缓存
我们可以将一些最近的消息（比如最后15条）缓存在用户视口（比如最后5条）中可见的一些最近的对话中。由于我们决定将用户的所有消息存储在一个碎片上，因此用户的缓存也应该完全驻留在一台机器上。
8.负载平衡
我们需要在聊天服务器前安装负载平衡器；它可以将每个用户标识映射到一个为用户保留连接的服务器，然后将请求定向到该服务器。类似地，我们的缓存服务器也需要一个负载平衡器。
9容错和副本
当聊天服务器出现故障时会发生什么情况？我们的聊天服务器与用户保持连接。如果服务器宕机，我们是否应该设计一种机制将这些连接转移到其他服务器？很难将TCP连接故障转移到其他服务器；一种更简单的方法是在连接丢失时让客户端自动重新连接。
我们应该存储用户消息的多个副本吗？我们不能只有用户数据的一个副本，因为如果保存数据的服务器崩溃或永久关闭，我们没有任何机制来恢复数据。为此，我们要么在不同的服务器上存储数据的多个副本，要么使用里德-所罗门编码等技术来分发和复制数据。
10扩展要求
A.群聊
我们可以在系统中拥有单独的群组聊天对象，这些对象可以存储在聊天服务器上。群组聊天对象由GroupChatID标识，并且还将维护属于该聊天的人的列表。我们的负载平衡器可以根据GroupChatID和服务器处理来引导每个群组聊天消息，该群组聊天可以遍历聊天的所有用户，以找到处理每个用户连接的服务器来传递消息。
在数据库中，我们可以将所有组聊天存储在基于GroupChatID分区的单独表中。
B提醒推送
在我们当前的设计中，用户只能向活动用户发送消息，如果接收用户处于脱机状态，我们会向发送用户发送失败消息。推送通知将使我们的系统能够向脱机用户发送消息。
对于推送通知，每当出现新消息或事件时，每个用户都可以从其设备（或web浏览器）选择加入以获取通知。每个制造商都维护一组服务器，用于将这些通知推送到用户。
为了在我们的系统中提供推送通知，我们需要设置一个通知服务器，该服务器将接收脱机用户的消息并将其发送到制造商的推送通知服务器，然后该服务器将它们发送到用户的设备。
参考资料
grok_system_design_interview.pdf
