系统设计面试笔记 第 17 章

第 17 章 附近的朋友

引言

本章重点设计一个可扩展的后端，用于支撑这样一款应用：用户可以共享自己的位置，并发现附近的朋友。

与邻近服务那一章的主要区别在于：本问题中位置在不断变化，而在那一章中，商家地址基本保持不变。

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

以下是推动面试进行的一些问题：

  • 候选人：地理上多近才算“附近”？
  • 面试官：5 英里，这个数字应当可配置。
  • 候选人：距离是按直线距离计算，还是要考虑诸如朋友之间隔着一条河之类的情况？
  • 面试官：按直线距离计算，这是一个合理的假设。
  • 候选人：这款应用有多少用户？
  • 面试官：10 亿用户，其中 10% 使用附近的朋友功能。
  • 候选人：我们需要存储位置历史吗？
  • 面试官：需要，它可能很有价值，例如用于机器学习。
  • 候选人：可以假设不活跃的朋友会在 10 分钟后从该功能中消失吗？
  • 面试官：可以。
  • 候选人：需要考虑 GDPR 等法规吗？
  • 面试官：不需要，以便简化问题。

功能性需求

  • 用户应能在手机应用上看到附近的朋友。每个朋友都带有距离和时间戳，时间戳表示该位置的更新时间。
  • 附近的朋友列表应每隔几秒更新一次。

非功能性需求

  • 低延迟：能及时收到位置更新、不出现太大延迟非常重要。
  • 可靠性：偶尔丢失个别数据点可以接受，但系统总体上应保持可用。
  • 最终一致性（Eventual Consistency）：位置数据存储不需要强一致性。不同副本在接收位置数据时出现几秒钟的延迟是可以接受的。

粗略估算

以下估算用于确定潜在的规模：

  • 附近的朋友是指位于 5 英里半径内的朋友。
  • 位置刷新间隔为 30 秒。人类步行速度较慢，因此不需要过于频繁地更新位置。
  • 平均每天有 1 亿用户使用该功能，其中 10% 为同时在线用户，即 1000 万。
  • 平均每个用户有 400 个朋友，他们都使用附近的朋友功能。
  • 应用每页显示 20 个附近的朋友。
  • 位置更新 QPS = 1000 万 / 30 ≈ 每秒约 33.4 万次更新

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

在探讨 API 和数据模型设计之前，我们先研究一下要使用的通信协议，因为它不像传统的请求-响应通信模型那么普遍。

高层设计

从高层来看，我们希望在对等端之间建立有效的消息传递。这可以通过点对点（peer-to-peer）协议实现，但对于连接不稳定、功耗限制又很严格的手机应用来说并不现实。

更实际的做法是使用一个共享的后端，作为向你想触达的朋友进行扇出（fan-out）的机制：

扇出后端

后端要做什么？

  • 接收所有活跃用户的位置更新。
  • 对于每一次位置更新，找出所有应该接收它的活跃用户，并转发给他们。
  • 如果朋友之间的距离超过配置的阈值，就不转发位置数据。

这听起来很简单，但挑战在于如何按照我们所面对的规模来设计系统。

我们先从一个较简单的设计开始，再在深入探讨部分讨论更高级的方案：

简单的高层设计
  • 负载均衡器：把流量分发到 REST API 服务器以及双向的 WebSocket 服务器。
  • REST API 服务器：处理辅助性任务，例如管理好友、更新个人资料等。
  • WebSocket 服务器：有状态的服务器，负责把位置更新请求转发给相应的客户端。它还负责在手机客户端初始化时，为其填充附近朋友的位置数据（稍后详细讨论）。
  • Redis 位置缓存：用于存储每个活跃用户的最新位置数据。缓存中的每个条目都设置了 TTL。TTL 过期后，用户即被视为不再活跃，其数据会从缓存中删除。
  • 用户数据库：存储用户及好友关系数据。关系型数据库或 NoSQL 数据库都可以用于此目的。
  • 位置历史数据库：存储用户位置数据的历史记录，它不一定直接用于附近的朋友功能，而是用于记录历史数据以供分析。
  • Redis Pub/Sub：用作轻量级消息总线，为每个用户的位置更新提供各自的频道（topic）。
Redis Pub/Sub 的用法

在上例中，WebSocket 服务器订阅与其相连的用户所对应的频道，每当收到位置更新时，就把它转发给相应的用户。

周期性位置更新

周期性位置更新的流程如下：

周期性位置更新
  • 手机客户端向负载均衡器发送位置更新。
  • 负载均衡器把位置更新转发到该客户端在 WebSocket 服务器上的持久连接。
  • WebSocket 服务器把位置数据保存到位置历史数据库。
  • 位置缓存中的位置数据得到更新。WebSocket 服务器还会把位置数据保存在内存中，供该用户后续的距离计算使用。
  • WebSocket 服务器通过 Redis Pub/Sub 把位置数据发布到该用户的频道。
  • Redis Pub/Sub 把位置更新广播给该用户频道的所有订阅者，也就是负责该用户的朋友的那些服务器。
  • 订阅了该频道的 WebSocket 服务器收到位置更新后，计算出这次更新应当发给哪些用户，然后发送出去。

下面是同一流程更详细的版本：

详细的周期性位置更新

平均而言，每次需要转发 40 条位置更新，因为每个用户平均有 400 个朋友，其中同一时刻有 10% 在线。

API 设计

我们需要支持的 WebSocket 例程：

  • 周期性位置更新：用户把位置数据发送给 WebSocket 服务器。
  • 客户端接收位置更新：服务器发送朋友的位置数据和时间戳。
  • WebSocket 客户端初始化：客户端发送用户位置，服务器返回附近朋友的位置数据。
  • 订阅新朋友：WebSocket 服务器发送一个手机客户端需要跟踪的朋友 ID，例如当该朋友首次上线时。
  • 取消订阅某个朋友：WebSocket 服务器发送一个朋友 ID，手机客户端应当取消对其的订阅，例如因为该朋友下线了。

HTTP API：用于辅助性职责的传统请求/响应接口。

数据模型

  • 位置缓存存储 user_id 与 lat,long,timestamp 之间的映射。Redis 非常适合做这个缓存，因为我们只关心当前位置，而且它支持我们这个场景所需的 TTL 淘汰。
  • 位置历史表存储相同的数据，只不过存放在一张包含上述四列的关系型表中。这类数据可以用 Cassandra 存储，因为它针对写多读少的负载做了优化。

第 3 步：深入设计

我们来讨论如何扩展这个高层设计，使其能够在目标规模下工作。

各组件的扩展性如何？

  • API 服务器：可以通过自动伸缩组（autoscaling group）和复制服务器实例轻松扩展。
  • WebSocket 服务器：我们可以轻松地横向扩展 WebSocket 服务器，但需要确保在下线某台服务器时优雅地关闭现有连接。例如，可以在负载均衡器中把服务器标记为“排空（draining）”状态，停止向它分配新连接，然后再把它最终从服务器池中移除。
  • 客户端初始化：客户端首次连接服务器时，服务器会获取该用户的好友列表，在 Redis Pub/Sub 上订阅他们的频道，从缓存中获取他们的位置，最后转发给客户端。
  • 用户数据库：我们可以按 user_id 对数据库进行分片。通过一个由专门团队管理的独立服务和 API 来对外提供用户/好友数据，可能也是合理的做法。
  • 位置缓存：我们可以通过启动多个 Redis 节点轻松地对缓存进行分片。此外，TTL 限定了任一时刻可能占用的最大内存。不过，我们仍然需要应对大量的写入负载。
  • Redis Pub/Sub 服务器：我们利用了这样一个事实：已初始化但未被使用的频道不会消耗内存。因此，可以为所有使用附近的朋友功能的用户预先分配频道，从而避免诸如用户上线时才创建新频道并通知活跃的 WebSocket 服务器之类的麻烦。

深入探讨 Redis Pub/Sub 组件的扩展

维护所有 Pub/Sub 频道大约需要 200GB 内存。使用 2 台各有 100GB 内存的 Redis 服务器就能做到。

然而，考虑到我们每秒需要推送约 1400 万次位置更新，假设单台服务器每秒能处理约 10 万次推送，那么至少需要 140 台 Redis 服务器才能承受这样的负载。

因此，我们需要一个分布式 Redis 服务器集群来应对繁重的 CPU 负载。

为了支持分布式 Redis 集群，我们需要使用服务发现组件（例如 ZooKeeper 或 etcd）来跟踪哪些服务器是存活的。

我们需要在服务发现组件中编码的数据如下：

频道分布数据

WebSocket 服务器使用从 ZooKeeper 获取的这些编码数据，确定某个频道位于哪台服务器上。为了提高效率，哈希环数据可以缓存在每台 WebSocket 服务器的内存中。

至于集群的扩容或缩容，可以设置一个每日任务，根据历史流量数据按需调整集群规模。我们也可以为集群预留多余的容量，以应对负载高峰。

Redis 集群可以被视为有状态的存储服务器，因为它为频道维护了一些状态，并且需要与订阅者协调，使它们切换到集群中新增的节点上。

在扩缩容操作中，我们必须留意一些潜在问题：

  • 由于频道被迁移，WebSocket 服务器会发出大量重新订阅请求。
  • 在操作期间，可能会漏掉客户端的一些位置更新，这对本问题来说可以接受，但我们仍应尽量减少这种情况。可以考虑在一天中流量最低的时候进行此类操作。
  • 我们可以利用一致性哈希（Consistent Hashing），在增加或移除服务器时尽量减少被迁移的频道数量。
一致性哈希

添加/删除好友

每当添加或删除一个好友时，负责受影响用户的 WebSocket 服务器都需要订阅或取消订阅该好友的频道。

由于“附近的朋友”功能是一个更大应用的一部分，我们可以假设：手机客户端可以注册回调，在任一此类事件发生时触发，客户端随后会向 WebSocket 服务器发送消息，让其执行相应的操作。

好友很多的用户

我们可以对一个人能拥有的好友总数设置上限，例如 Facebook 的好友上限是 5000 个。

负责处理这种“鲸鱼”用户的 WebSocket 服务器负载可能会更高一些，但只要我们有足够多的 WebSocket 服务器，就不会有问题。

附近的陌生人

如果面试官希望修改设计，加入这样一个功能：偶尔能在附近的朋友地图上看到一个随机的陌生人出现，该怎么办？

一种处理方法是基于 geohash 定义一个 Pub/Sub 频道池：

基于 geohash 的 Pub/Sub

位于该 geohash 范围内的任何人都订阅相应的频道，以接收随机用户的位置更新：

按 geohash 分发位置更新

我们也可以同时订阅多个 geohash，以应对某人离得很近、却位于相邻 geohash 中的情况：

geohash 边界

Redis Pub/Sub 的替代方案

除了用 Redis 做 Pub/Sub，另一种方案是使用 Erlang，这是一门针对分布式计算应用优化过的通用编程语言。

借助它，我们可以创建数以百万计的轻量 Erlang 进程，它们彼此之间相互通信。我们可以在分布式 Erlang 应用中同时处理 WebSocket 连接和 Pub/Sub 频道。

不过，使用 Erlang 的一个挑战在于它是一门小众编程语言，可能很难招到优秀的 Erlang 开发者。

第 4 步：总结

我们成功设计了一个支持附近的朋友功能的系统。

核心组件：

  • WebSocket 服务器：客户端与服务器之间的实时通信
  • Redis：位置数据的快速读写 + Pub/Sub 频道

我们还探讨了如何扩展 RESTful API 服务器、WebSocket 服务器、数据层和 Redis Pub/Sub 服务器，并探讨了 Redis Pub/Sub 的一种替代方案。此外，我们还探讨了“附近的陌生人”功能。