第11章：设计一个信息推送系统

来源： https://github.com/Admol/SystemDesign

说明： 由于国内访问github不太稳定，故将相关文章搬运到此，若涉及侵权，请联系删除！

第11章：设计一个信息推送系统

在本章中，您需要设计一个信息推送系统。 什么是信息推送？ 根据 Facebook 帮助页面，“动态是位于首页中间不断更新的动态列表。动态包括您在 Facebook 上关注的用户、公共主页和小组发布的状态更新、照片、视频、链接、应用事件和点赞。”[1]。 这是一个流行的面试问题。 类似的常见问题有：设计 Facebook 信息推送、Instagram 推送、Twitter 时间线等。

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

第一组解释问题是为了了解当面试官要求你设计一个信息推送系统时，她的想法是什么。最起码，你应该弄清楚要支持哪些功能。下面是一个候选人与面试官互动的例子。

候选人：这是一个移动应用程序吗？还是一个网络应用？或者两者都是？

面试官：都是

候选人：哪些是重要的特征？

面试官：用户可以发布帖子，并在信息流页面上看到她朋友的帖子。

候选人：信息是按逆时针顺序排序，还是按任何特定顺序，如主题得分？例如，你的亲密朋友的帖子有更高的分数。

面试官：为了简单起见，让我们假设推送是按逆时针顺序排序的。

候选人：一个用户可以有多少个朋友？

面试官：5000

候选人：业务流量是多少？

面试官：1000万DAU

候选人：推送可以包含图片、视频，还是只有文字？

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

现在你已经收集了需求，我们把重点放在设计系统上。

第2步：提出高层次的设计方案并获得认同

该设计分为两个流程：信息流发布和信息流构建：

  • 信息发布（Feed publishing）：当用户发布帖子时，相应的数据被写入缓存和数据库。帖子被推送到她朋友的动态中。
  • 信息流构建（Newsfeed building）：为简单起见，我们假设信息推送是通过按时间倒序聚合朋友的帖子来构建的。

信息流发布 API

信息流 API是客户与服务器通信的主要方式。这些API是基于HTTP的，允许客户执行操作，其中包括发布状态、检索信息流、添加朋友等。

我们讨论两个最重要的API：信息流发布 API 和信息流检索 API。

  • 信息流发布 API

    要发布一个帖子，将向服务器发送一个HTTP POST请求。该API显示如下。

    1

    POST /v1/me/feed

    参数：

    • content：帖子内容的文本。
    • auth_token：它用于验证API请求。

  • 信息流检索 API

    检索信息流的API如下：

    1

    GET /v1/me/feed

    参数：

    • auth_token：它用于验证API请求。

信息发布（Feed publishing）

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

  • User（用户）：用户可以在浏览器或移动应用程序上查看信息流。一个用户通过API发布内容为 “你好 “的帖子： /v1/me/feed?content=Hello&auth_token={auth_token}
  • Load balancer（负载均衡器）：将流量分配给网络服务器。
  • Web servers（网络服务器）：网络服务器将流量重定向到不同的内部服务。
  • Post service（帖子服务）：在数据库和缓存中持久保存帖子。
  • Fanout service（扇出服务）：推送新内容到朋友的信息流。信息流数据存储在缓存中，以便快速检索。
  • 通知服务：通知朋友有新内容，并发送推送通知。

信息流构建（Newsfeed building）

在这一节中，我们将讨论信息流是如何在幕后构建的。

图11-3显示了高层设计。

  • User（用户）：一个用户发送了一个请求来检索她的信息。 该请求看起来像这样：/v1/me/feed。
  • Load balancer（负载均衡器）：将流量分配给网络服务器。
  • Web servers（网络服务器）：网络服务器将请求路由到信息发布服务。
  • Newsfeed service（信息馈送服务）：信息馈送服务从缓存中获取信息。
  • Newsfeed cache（信息流缓存）：存储渲染信息流所需的信息ID。

第3步：深入设计

高层设计简要地涵盖了两个流程：信息发布和信息流构建。在这里，我们更深入地讨论这些主题。

信息发布深入研究

图 11-4 概述了信息发布的详细设计。我们已经讨论了高层次设计中的大部分组件，我们将重点关注两个组件：Web 服务器和扇出服务。

web 服务

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

扇出服务

Fanout 是将帖子传递给所有朋友的过程。两种类型的扇出模型是：写扇出（也称为推模型）和读扇出（也称为拉模型）。两种模型各有利弊。我们解释他们的工作流程并探索支持我们系统的最佳方法。

写扇出

通过这种方法，信息流在写的时候就被预先计算了。一个新的帖子在发布后会立即被送到朋友的缓存中。

优点：

  • 动态消息是实时生成的，可以第一时间推送给朋友。
  • 获取信息流的速度很快，因为信息流是在写的时候预先计算的。

缺点：

  • 如果一个用户有很多朋友，获取朋友列表并为所有朋友生成信息流是很慢的，而且很耗时间。这被称为热键问题。
  • 对于不活跃的用户或那些很少登录的用户，预先计算的信息流会浪费计算资源。

读扇出

信息源是在阅读时间内产生的。这是一个按需分配的模式。当用户加载她的主页时，最近的帖子被拉出。

优点：

  • 对于不活跃的用户或那些很少登录的用户，读取时的扇出效果更好，因为它不会在他们身上浪费计算资源。
  • 数据不会被推送给朋友，所以不存在热键的问题。

缺点：

  • 获取信息源的速度很慢，因为信息源不是预先计算的。

我们采用了一种混合方法，以获得两种方法的好处并避免其中的缺点。由于快速获取信息流是至关重要的，我们对大多数用户使用推送模式。对于名人或有很多朋友/粉丝的用户，我们让粉丝按需提取信息内容以避免系统过载。一致性哈希是缓解热键问题的一个有用技术，因为它有助于更均匀地分配请求/数据。

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

扇出服务的工作原理如下：

  1. 从图形数据库中获取朋友 ID。 图数据库适用于管理朋友关系和朋友推荐。 希望了解更多有关此概念的感兴趣的读者应参阅参考资料 [2]。

  2. 从用户缓存中获取朋友信息。然后，系统根据用户设置过滤出朋友。例如，如果你把某人调成静音，她的帖子将不会显示在你的信息流中，尽管你们仍然是朋友。帖子可能不显示的另一个原因是，用户可以有选择地与特定的朋友分享信息或对其他人隐藏信息。

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

  4. Fanout worker 从消息队列中获取数据并将信息流数据存储在信息流缓存中。 你可以将信息流缓存视为一个 <post_id, user_id> 结构的映射表。 每当发布新帖子时，新帖子将被追加到信息流表中，如图 11-6 所示。 如果我们将整个用户和帖子对象存储在缓存中，内存消耗会变得非常大。 因此，仅存储 ID。 为了保持较小的内存大小，我们设置了一个可配置的限制。 用户滚动浏览信息流中数千个帖子的机会很小。 大多数用户只对最新的内容感兴趣，所以缓存未命中率低。

  5. 将 <post_id, user_id> 存储在信息流缓存中。 图 11-6 显示了缓存中信息流的示例。

信息源检索深入研究

图 11-7 说明了信息检索的详细设计。

如图11-7所示，媒体内容（图片、视频等）存储在CDN中，便于快速检索。 让我们看看客户端如何检索信息流。

  1. 一个用户发送了一个请求来检索她的信息流。该请求看起来像这样：/v1/me/feed
  2. 负载均衡将请求重新分配给网络服务器。
  3. Web 服务器调用信息流服务（News Feed Service）获取信息流。
  4. 信息流服务从信息流缓存中获得一个帖子ID列表。
  5. 用户的信息流不仅仅是 feed ID 列表。 它包含用户名、个人资料图片、帖子内容、帖子图片等。因此，信息流服务从缓存（用户缓存和帖子缓存）中获取完整的用户和帖子对象，以构建完全整合的信息流。
  6. 完全整合的信息流以JSON格式返回到客户端进行渲染。

  • 缓存架构

    缓存对于信息流系统非常重要。 我们将缓存层分为 5 层，如图 11-8 所示。

    • News Feed：它存储了信息的ID。
    • Content：它存储每个帖子的数据。受欢迎的内容被存储在热缓存中。
    • Social Graph：它存储用户关系数据。
    • Action：它存储有关用户是否喜欢帖子、回复帖子或对帖子执行其他操作的信息。
    • Counters：它存储点赞、回复、关注者、关注等的计数器。

第4步：总结

在本章中，我们设计了一个信息推送系统。 我们的设计包含两个流程：信息发布和信息检索。

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

数据库扩展：

  • 垂直扩展 vs 水平扩展
  • SQL vs NoSQL
  • 主从复制
  • 读写分离
  • 一致性模型
  • 数据库分片

其他谈话要点：

  • 保持网络层的无状态
  • 尽可能多地缓存数据
  • 支持多个数据中心
  • 使用消息队列降低耦合
  • 监控关键指标。 例如，高峰时段的 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