System Design Notes

简体中文

English

简体中文

English

Appearance

第 17 章：附近的好友 ​

引言 ​

本章设计一款应用的可扩展后端，让用户分享自己的位置并发现附近的好友。

它与上一章附近地点服务的主要区别在于：这里的位置持续变化，而商家地址基本保持不变。

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

面试中可以先澄清这些问题：

  • 候选人：多近算“附近”？
  • 面试官：5 英里；这个数值应可配置。
  • 候选人：距离按直线计算吗？是否需要考虑好友之间隔着河流等情况？
  • 面试官：按直线距离计算是合理假设。
  • 候选人：应用有多少用户？
  • 面试官：10 亿用户，其中 10% 使用附近的好友功能。
  • 候选人：需要存储位置历史吗？
  • 面试官：需要，例如机器学习可能用到。
  • 候选人：可以假设不活跃的好友在 10 分钟后从功能中消失吗？
  • 面试官：可以。
  • 候选人：需要考虑 GDPR 等法规吗？
  • 面试官：为简化问题，暂不考虑。

功能需求 ​

  • 用户应能在移动应用中查看附近的好友。每位好友显示距离和时间戳，表示位置更新的时间。
  • 附近好友列表应每隔几秒更新一次。

非功能需求 ​

  • 低延迟：位置更新应尽快送达。
  • 可靠性：允许偶尔丢失位置数据点，但系统整体应保持可用。
  • 最终一致性：位置数据存储无需强一致性，不同副本之间出现几秒延迟可以接受。

粗略估算 ​

通过以下假设估算系统规模：

  • 附近的好友定义为 5 英里半径内的好友。
  • 每 30 秒刷新一次位置。人的步行速度不快，无需过于频繁地更新。
  • 平均每天有 1 亿用户使用该功能，其中 10% 同时在线，即 1000 万用户。
  • 每位用户平均有 400 位好友，且他们都使用附近的好友功能。
  • 应用每页显示 20 位附近好友。
  • 位置更新 QPS = 1000 万 / 30 ≈ 每秒 33.4 万次更新。

第 2 步：提出概要设计并达成共识 ​

在研究 API 和数据模型前，先讨论通信协议，因为这里的通信方式不同于常见的请求／响应模型。

概要设计 ​

我们需要在各方之间高效传递消息。虽然点对点协议可以做到，但移动应用的网络连接不稳定，且受电量限制，因此并不实用。

更可行的做法是使用共享后端，把更新分发给需要接收的好友：

<img src="/images/chapter-17/fan-out-backend.png" alt="后端扇出" width="500" />

后端负责：

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

流程看似简单，难点在于支撑目标规模。

先从较简单的设计入手，再在深入设计中讨论扩展方案：

<img src="/images/chapter-17/simple-high-level-design.png" alt="简单概要设计" width="500" />

  • 负载均衡器：将流量分配到 REST API 服务器和双向 WebSocket 服务器。

  • REST API 服务器：处理好友管理、个人资料更新等辅助任务。

  • WebSocket 服务器：有状态服务器，向相应客户端转发位置更新，也在移动客户端初始化时发送附近好友的位置（后文详述）。

  • Redis 位置缓存：存储每位活跃用户的最新位置。缓存项设置 TTL；过期后认为用户不再活跃，并移除其数据。

  • 用户数据库：存储用户与好友关系。可使用关系型数据库或 NoSQL 数据库。

  • 位置历史数据库：存储用户的位置历史。附近好友功能不一定直接使用它，但分析历史数据时会用到。

  • Redis 发布／订阅：作为轻量消息总线，为每位用户提供接收位置更新的频道。

    Redis 发布订阅用法

在上例中，WebSocket 服务器订阅已连接用户的频道；收到位置更新后，再转发给相应用户。

周期性位置更新 ​

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

<img src="/images/chapter-17/periodic-location-update.png" alt="周期性位置更新" width="500" />
  • 移动客户端向负载均衡器发送位置更新。
  • 负载均衡器通过该客户端的持久连接，把更新转发给 WebSocket 服务器。
  • WebSocket 服务器将位置数据写入位置历史数据库。
  • 更新位置缓存，并将该用户的位置保存在服务器内存中，供后续距离计算使用。
  • WebSocket 服务器通过 Redis 发布／订阅，将位置数据发布到用户频道。
  • Redis 将位置更新广播给该频道的全部订阅者，即负责该用户好友的服务器。
  • 订阅该频道的 WebSocket 服务器收到更新，计算哪些用户应收到更新，并发送给他们。

下面是同一流程的更详细示意：

<img src="/images/chapter-17/detailed-periodic-location-update.png" alt="详细的周期性位置更新" width="500" />

用户平均有 400 位好友，其中约 10% 同时在线，因此一次位置更新平均需要转发给 40 人。

API 设计 ​

需要支持以下 WebSocket 消息：

  • 周期性位置更新：用户向 WebSocket 服务器发送位置数据。
  • 客户端接收位置更新：服务器发送好友的位置数据和时间戳。
  • WebSocket 客户端初始化：客户端发送用户位置，服务器返回附近好友的位置数据。
  • 订阅新好友：例如好友首次上线时，WebSocket 服务器告知移动客户端应追踪的好友 ID。
  • 取消订阅好友：例如好友离线时，WebSocket 服务器告知移动客户端应取消订阅的好友 ID。

HTTP API：通过传统请求／响应方式处理辅助任务。

数据模型 ​

  • 位置缓存保存 user_id 到 lat,long,timestamp 的映射。这里仅关心当前位置，并且需要 TTL 淘汰，因此 Redis 很适合。
  • 位置历史表存放相同的数据，可用上述四列构成关系型表。由于 Cassandra 针对高写入负载进行了优化，也可以用于存储位置历史。

第 3 步：深入设计 ​

下面讨论如何扩展概要设计，使它能支撑目标规模。

各组件的扩展能力如何？ ​

  • API 服务器：通过自动扩缩容组增加服务器实例即可扩展。
  • WebSocket 服务器：可以横向扩展，但下线服务器时要妥善结束现有连接。例如，先在负载均衡器中将其标记为“排空”，停止向它发送新连接，再将其从服务器池移除。
  • 客户端初始化：客户端初次连接服务器时，服务器读取其好友列表，订阅好友的 Redis 频道，从缓存读取好友位置，最后转发给客户端。
  • 用户数据库：可以按 user_id 分片。也可以由专门团队维护服务和 API，对外提供用户与好友数据。
  • 位置缓存：启动多个 Redis 节点即可分片。TTL 限制了同时占用的最大内存，但仍需应对大量写请求。
  • Redis 发布／订阅服务器：已创建但未使用的频道不消耗内存。可以预先为所有使用该功能的用户分配频道，避免用户上线时临时创建频道并通知活跃的 WebSocket 服务器。

深入分析 Redis 发布／订阅的扩展 ​

维护所有发布／订阅频道约需 200 GB 内存，可由两台各有 100 GB 内存的 Redis 服务器承担。

不过系统每秒需要推送约 1400 万次位置更新。如果单台服务器每秒能处理约 10 万次推送，就至少需要 140 台 Redis 服务器。

因此，需要分布式 Redis 集群来处理密集的 CPU 负载。

为支持分布式 Redis 集群，需要 ZooKeeper 或 etcd 等服务发现组件，记录哪些服务器仍然存活。

服务发现组件要保存的数据如下：

<img src="/images/chapter-17/channel-distribution-data.png" alt="频道分布数据" width="500" />

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

扩缩容方面，可以根据历史流量设置每日任务调整集群规模，也可预留额外容量应对流量峰值。

Redis 集群需要当作有状态存储集群处理：频道保存一定状态，扩容时还须协调订阅者，将其迁移到新节点。

扩缩容期间要注意：

  • 频道迁移会引起大量 WebSocket 服务器重新订阅请求。

  • 客户端可能漏收部分位置更新。本题允许这种情况，但仍应尽量减少，例如选择每日流量最低时操作。

  • 使用一致性哈希可以在增加或移除服务器时，减少需要迁移的频道数量。

    一致性哈希

添加或删除好友 ​

好友关系变化时，负责受影响用户的 WebSocket 服务器需要订阅或取消订阅该好友的频道。

由于“附近的好友”是大型应用的一项功能，可以假设移动客户端能在好友变更事件发生时触发回调，并向 WebSocket 服务器发送消息，让其执行相应操作。

好友数量很多的用户 ​

可以限制好友总数，例如 Facebook 将好友上限设为 5000 人。

负责这类用户的 WebSocket 服务器可能承担较高负载，但只要 WebSocket 服务器数量充足，就能处理。

附近的陌生人 ​

如果面试官希望增加一项功能，让附近的陌生人偶尔出现在地图上，该如何修改设计？

一种办法是根据 Geohash 定义一组发布／订阅频道：

<img src="/images/chapter-17/geohash-pubsub.png" alt="Geohash 发布订阅" width="500" />

网格内的用户订阅相应频道，从而接收陌生用户的位置更新：

<img src="/images/chapter-17/location-updates-geohash.png" alt="基于 Geohash 的位置更新" width="500" />

还可以订阅多个 Geohash 频道，以处理用户很近但位于相邻网格的情况：

<img src="/images/chapter-17/geohash-borders.png" alt="Geohash 边界" width="500" />

Redis 发布／订阅的替代方案 ​

一种替代方式是使用 Erlang。它是一门通用编程语言，针对分布式计算应用做了优化。

利用 Erlang，可以启动数百万个相互通信的轻量进程，在分布式 Erlang 应用中同时处理 WebSocket 连接和发布／订阅频道。

但 Erlang 相对小众，可能难以招到经验丰富的开发者。

第 4 步：总结 ​

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

核心组件：

  • WebSocket 服务器：负责客户端与服务器之间的实时通信。
  • Redis：支持快速读写位置数据及发布／订阅频道。

本章还讨论了 REST API 服务器、WebSocket 服务器、数据层和 Redis 发布／订阅服务器如何扩展，介绍了 Redis 发布／订阅的替代方案，并探讨了“附近的陌生人”功能。