System Design

Appearance

第十一章：设计一个新闻订阅系统 ​

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

图11-1

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

第一个问题集旨在弄清面试官在让你设计一个新闻订阅系统时的意图。至少，你需要弄清楚需要支持哪些功能。以下是一个候选人与面试官的对话示例：

候选人：这是一个移动应用吗？还是网页应用？或者两者兼有？
面试官：两者兼有。

候选人：有哪些重要功能？
面试官：用户可以发布帖子，并在新闻订阅页面看到好友的帖子。

候选人：新闻订阅是按时间倒序排列，还是按照其他特定顺序，例如按主题分数？比如，来自密友的帖子得分更高。
面试官：为了简化问题，我们假设订阅内容按时间倒序排列。

候选人：用户最多可以有多少好友？
面试官：5000个。

候选人：流量有多大？
面试官：每日活跃用户为1000万。

候选人：订阅内容可以包含图片、视频，还是仅限文字？
面试官：可以包含媒体文件，包括图片和视频。

现在你已经收集了需求，我们接下来专注于系统设计。

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

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

  • 订阅发布：当用户发布帖子时，相关数据会写入缓存和数据库，帖子会被推送到好友的新闻订阅中。
  • 新闻订阅构建：为了简化，我们假设新闻订阅通过聚合好友的帖子并按时间倒序排列构建。

新闻订阅API ​

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

订阅发布API ​

发布帖子时，客户端将发送一个HTTP POST请求到服务器。API如下所示：

POST /v1/me/feed
参数:
- content: 帖子的文本内容。
- auth_token: 用于验证API请求的身份。

新闻订阅获取API ​

获取新闻订阅的API如下所示：

GET /v1/me/feed
参数:
- auth_token: 用于验证API请求的身份。

订阅发布流程 ​

图11-2展示了订阅发布流程的高层设计。

图11-2

  • 用户：用户可以通过浏览器或移动应用查看新闻订阅。用户通过API发送内容为“Hello”的帖子：

    /v1/me/feed?content=Hello&auth_token={auth_token}

  • 负载均衡器：分配流量到各个Web服务器。

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

  • 帖子服务：将帖子持久化存储到数据库和缓存中。

  • 广播服务：将新内容推送到好友的新闻订阅中。新闻订阅数据存储在缓存中，以便快速检索。

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

新闻订阅构建 ​

本节讨论新闻订阅在后台是如何构建的。图11-3展示了高层设计。

图11-3

  • 用户：用户发送请求以获取她的新闻订阅。请求如下所示：

    /v1/me/feed

  • 负载均衡器：负载均衡器将流量重定向到Web服务器。

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

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

  • 新闻订阅缓存：存储渲染新闻订阅所需的新闻订阅ID。

第 3 步 - 深入设计 ​

高层设计简要介绍了两个流程：订阅发布 和 新闻订阅构建。在这里，我们将深入讨论这些主题。

订阅发布的深入分析 ​

图11-4概述了订阅发布的详细设计。我们在高层设计中已经讨论了大多数组件，这里我们将重点关注两个组件：Web服务器 和 广播服务。

图11-4

Web服务器 ​

除了与客户端通信外，Web服务器还负责执行身份验证和速率限制。只有使用有效的auth_token登录的用户才被允许发布帖子。系统会限制用户在一定时间内发布帖子的数量，这是防止垃圾信息和滥用内容的关键措施。

广播服务 (Fanout service) ​

广播是将帖子分发给所有好友的过程。广播有两种模型：写时广播（也称为推送模型）和读时广播（也称为拉取模型）。这两种模型各有优缺点。我们将解释它们的工作流程，并探索支持我们系统的最佳方法。

  • 写时广播：在这种方法中，新闻订阅在写入时预先计算。新发布的帖子会在发布后立即推送到好友的缓存中。

    优点：

    • 新闻订阅是实时生成的，可以立即推送给好友。
    • 获取新闻订阅的速度快，因为新闻订阅在写入时已经预先计算好。

    缺点：

    • 如果用户有很多好友，获取好友列表并为所有好友生成新闻订阅将会很慢且耗时，这被称为热键问题。
    • 对于不活跃或很少登录的用户，预先计算的新闻订阅会浪费计算资源。

  • 读时广播
    在这种方法中，新闻订阅是在读取时生成的。这是一种按需模型，当用户加载其主页时，会拉取最近的帖子。

    优点：

    • 对于不活跃或很少登录的用户，读时广播更为有效，因为它不会在这些用户上浪费计算资源。
    • 数据不会被推送给好友，因此不存在热键问题。

    缺点：

    • 获取新闻订阅的速度较慢，因为新闻订阅未预先计算。

我们采用混合方法，以获取两种方法的优势并避免它们的缺陷。由于快速获取新闻订阅至关重要，我们对大多数用户采用推送模型。对于名人或拥有大量好友/粉丝的用户，我们让其粉丝按需拉取新闻内容，以避免系统过载。一致性哈希是一种有效的技术，能够帮助减轻热键问题，因为它有助于更均匀地分布请求和数据。

图11-5展示了广播服务的详细设计，让我们深入了解这一服务。

图11-5

广播服务的工作流程如下：

  1. 从图数据库获取好友ID：图数据库非常适合用于管理好友关系和好友推荐。如果读者想深入了解这一概念，可以参考文献 [2]。

  2. 从用户缓存中获取好友信息：系统会根据用户设置过滤掉部分好友。例如，如果你将某人静音，即便你们还是好友，她的帖子也不会出现在你的新闻订阅中。另一种情况是，用户可以选择性地向某些好友分享信息，或对其他人隐藏。

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

  4. 广播工作器从消息队列中获取数据，并将新闻订阅数据存储到新闻订阅缓存中：你可以将新闻订阅缓存视为一个<post_id, user_id>的映射表。每当有新帖子发布时，它会附加到新闻订阅表中，如图11-6所示。如果在缓存中存储完整的用户和帖子对象，内存消耗将非常大，因此我们只存储ID。为了控制内存大小，我们设置了一个可配置的限制。用户滚动浏览数千条新闻订阅的可能性不大，大多数用户只对最新内容感兴趣，因此缓存未命中率较低。

  5. 将<post_id, user_id>存储到新闻订阅缓存中：图11-6展示了缓存中新闻订阅的一个示例。

图11-6

新闻订阅检索深入分析 ​

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

图11-7

正如图11-7所示，媒体内容（如图片、视频等）存储在CDN中以实现快速检索。下面我们来看看客户端如何检索新闻订阅。

  1. 用户发送请求以检索她的新闻动态。请求格式为：/v1/me/feed
  2. 负载均衡器将请求重新分配到 Web 服务器。
  3. Web 服务器调用新闻动态服务以获取新闻动态。
  4. 新闻动态服务从新闻动态缓存中获取帖子 ID 列表。
  5. 用户的新闻动态不仅仅是一个帖子 ID 列表。它还包含用户名、个人资料图片、帖子内容、帖子图片等。因此，新闻动态服务从缓存（用户缓存和帖子缓存）中获取完整的用户和帖子对象，以构建完整的新闻动态。
  6. 完整的新闻动态以 JSON 格式返回给客户端进行渲染。

缓存架构 ​

缓存对于新闻动态系统至关重要。我们将缓存层分为五层，如图 11-8 所示。

图11-8

  • 新闻动态：存储新闻动态的 ID。
  • 内容：存储每个帖子的数据信息。热门内容存储在热缓存中。
  • 社交图谱：存储用户关系数据。
  • 操作：存储用户是否点赞、回复帖子或对帖子采取其他操作的信息。
  • 计数器：存储点赞、回复、关注者、正在关注等的计数器。

第 4 步 - 总结 ​

在本章中，我们设计了一个新闻动态系统。我们的设计包含两个流程：动态发布和新闻动态检索。
与任何系统设计面试问题一样，没有完美的系统设计方法。每个公司都有其独特的限制，您必须设计一个适应这些限制的系统。理解设计和技术选择的权衡是重要的。如果还有几分钟时间，您可以讨论扩展性问题。为避免重复讨论，以下仅列出高层次的讨论要点。

扩展数据库：

  • 垂直扩展与水平扩展
  • SQL 与 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-friendrecommendations-with-neo4j.aspx