在本章中，你被要求设计一个news feed系统。什么是news feed？根据Facebook官网上的说法，“news feed是一个在你的个人主页中的不断更新的故事列表。news feed包括你在Facebook上关注的人、页面和小组发布的状态更新信息、照片、视频、链接、应用活动和点赞”。这是一个常见的面试问题。面试者经常被问到的类似问题还有：如何设计Facebook的news feed系统、如何设计Instagram的feed系统、如何设计Twitter时间线(Twitter timeline)系统等。图-1展示了一个典型news feed系统在手机上的界面布局。
图-1
1.理解问题并确定设计的边界
下面是候选人和面试官对话的示例，确定设计的需求和边界。候选人：这是一个移动端应用，还是一个网页应用？或者都是？
面试官：都是。
候选人：它要有哪些重要功能？
面试官：用户可以在news feed页面发布帖子，幵且能看到好友发布的帖子。
候选人：news feed页面上的帖子是按照时间倒序排序的还是按照其他特定顺序排序的？比如，按照话题分数排序，或者优先展示亲密朋友的帖子。
面试官：为了简单起见，我们假设它们都是按照时间倒序排序的。
候选人：一个用户可以有多少个好友？
面试官：5000个。
候选人：网络流量是多少？
面试官：1000万DAU。
候选人：news feed中可以包含图片和视频吗？还是只能包含文本？
面试官：可以包含多媒体文件，图片和视频都可以。
2 高层级设计
这个系统分为两个流程：发布feed和构建news feed。•发布feed：当用户发布一个帖子时，相应的数据被写入缓存和数据库。帖子被推送到她好友的news feed中。
•构建news feed：为了简单起见，我们假设news feed是按时间倒序聚合好友的帖子而构建的。
2.1 news feed API
news feed API是客户端和服务器通信的主要方式。这些API是基于HTTP的，它们允许客户端实施一些操作，包括发布帖子、获取news feed、添加好友等。我们将讨论两个最重要的API：发布feed和获取news feed。发布feed
要发布帖子，必须向服务器发送一个HTTP POST请求。这个API如下所示：POST /v1/me/feed
这个API接受如下参数：
•content：帖子中的文本内容。
•auth_token：用于对API请求进行身份验证的令牌。
获取news feed
用来获取news feed的API如下所示：
GET /v1/me/feed
这个API接受auth_token参数，它是一个用于对API请求进行身份验证的令牌。
2.2 feed的发布
图-2显示了feed发布流程的高层级设计。•用户：用户可以在浏览器和移动应用中浏览news feed。下面是用户通过API发布一个内容为“Hello”的帖子的示例。
/v1/me/feed?content=Hello&auth_token={auth_token}
•负载均衡器：把流量分配到多个Web服务器上。
•Web服务器：Web服务器把请求重定向到不同的内部服务。
•帖子服务：将帖子持久化到数据库和缓存中。
图-2
•广播服务(Fanout Service)：把新内容推送到好友的news feed中。news feed数据存储在缓存中以便快速获取。
•通知服务：告知好友有新内容，并发送推送通知。
2.3 news feed的构建
在本节中，我们会讨论news feed在幕后是如何构建的。图-3展示了高层级的设计。
图-3
•用户：用户可以发送请求来获取其news feed。
•负载均衡器：将请求重定向到各个Web服务器。
•Web服务器：将请求转发到news feed服务。
•news feed服务：从缓存中拉取news feed。
•news feed缓存：存储在渲染news feed时必须用到的news feed ID。
3 设计继续深入
我们在第2节简单介绍了两个流程：发布feed和构建news feed。在本节我们将更深入地讨论这些话题。3.1 深入探讨feed的发布流程
图-4勾画了feed发布流程的详细设计。我们在11.2.2节已经讨论了大部分组件，这里将集中讨论两个组件：Web服务器和广播服务。
图-4
Web服务器
除了与客户端通信外，Web服务器也用于验证用户身份和限流。只有使用有效的auth_token登录的用户才允许发布帖子。系统也限制了用户在一段时间内可以发布的帖子的数量，这对于阻止发布垃圾信息和滥用内容很重要。广播服务
广播是把一个帖子发给所有好友的过程。有两种广播模型：写广播（也叫推送模型）和读广播（也叫拉取模型）。两种模型都有各自的优缺点。我们会解释它们的工作流程并探索支持我们系统的最佳方法。(1)写广播。采用这种方法，在写入的时候就预先计算好用户发布的帖子将被哪些好友订阅。用户的新帖子在发布之后就立刻被传递到好友的news feed缓存中。
写广播的优点是：
•实时生成news feed，并且立刻将其推送给好友。
•获取news feed很快，因为一个帖子在被写入的时候，系统就计算好了哪些人会订阅。
写广播的缺点是：
•如果用户有很多好友，获取好友列表并为所有人生成news feed会很慢且耗时。这也叫作热键问题(Hotkey Problem)。
•对不活跃的用户或者那些很少登录的用户，预计算news feed会浪费计算资源。
(2)读广播。直到读取的时候才生成news feed。这是一种按需模型。当用户加载主页时，再拉取最近的动态。读广播的优点是：
•对不活跃的用户或者那些很少登录的用户，效果更好，因为不会在他们身上浪费计算资源。
•不存在热键问题，因为数据不会被推给好友。
读广播的缺点是因为没有预先计算，所以获取news feed会很慢。
我们采用了混合方案，以利用这两个方法的优点，避开它们的缺点。因为快速获取news feed很重要，所以我们对大部分用户使用推送模型。对于名人或者有很多好友和粉丝的用户，我们让粉丝按需拉取新内容(news)来避免系统过载。一致性哈希可以帮我们更均匀地分配请求/数据，它是一个减轻热键问题的有用技术。
我们仔细研究一下广播服务，如图-5所示。
图-5
广播服务的工作流程如下：
1.从图数据库中获取好友ID。图数据库非常适合管理好友和好友推荐。
2.从用户缓存中获取好友信息，然后根据用户设置筛选好友。例如，如果你屏蔽了某人，那么她的帖子就不会出现在你的news feed上，尽管你们仍然是好友。用户可以选择性地与特定好友分享信息，或者隐藏信息不让其他人看到。
3.发送好友列表和新动态的ID给消息队列。
4.广播Worker从消息队列中获取数据，并将news feed数据存储在news feed缓存中。你可以将news feed缓存看作<post_id，user_id＞映射表。一旦新的帖子生成，就会被添加到这个表中，如图-6所示。如果我们把整个用户和帖子对象都存储在缓存里，占用的内存会非常大，因此只将ID（post_id和user_id）存储在缓存中。为了控制内存的消耗，我们设置了一个可配置的阈值。一个用户在news feed中浏览上千条帖子的概率很小。大部分用户只对最新的内容感兴趣，所以缓存未命中的概率很低。
5.将<post_id，user_id＞存储在news feed缓存中。图-6展示了存储在缓存中的news feed例子
图-6
3.2 深入探讨news feed的获取流程
图-7展示了获取news feed的详细流程。如图-7所示，多媒体内容（图片、视频等）存储在CDN中以便快速获取。我们来看一看客户端是如何获取news feed的。1.用户发送请求获取其news feed。请求看起来像这样：
/v1/me/feed
2.负载均衡器把请求重新分配给各Web服务器。
3.Web服务器请求news feed服务以获取news feed。
4.news feed服务从news feed缓存中获取帖子ID列表。
5.用户的news feed不仅包含帖子ID列表，还包含用户名、头像、帖子内容、帖子中的图片等。因此，news feed服务从缓存（用户缓存和帖子缓存）中获取完整的用户和帖子对象，来构建完整的news feed。
6.将整合好的news feed以JSON格式返回给客户端进行渲染。
图-7
3.3 缓存架构
缓存对于news feed系统来说非常重要。在这个系统中，我们把缓存分为5层，如图-8所示。
图-8
•news feed层：存储了news feed的ID。
•内容层：存储每条帖子的数据。流行的内容存储在热点内容缓存中。
•社交图谱层：存储用户关系数据。
•操作层：存储用户对帖子点赞、回复，或者进行其他操作的信息。
•计数器层：存储点赞、回复、关注等行为的计数数据。
4 总结
在本章中，我们设计了一个news feed系统。我们的设计主要包含两个流程：发布feed和获取news feed。和其他系统设计面试问题一样，不存在完美的系统设计方法。每个公司都有独特的限制条件，你必须设计一个能适应这些限制条件的系统。理解设计和技术选择上的权衡很重要。如果面试的最后还剩几分钟时间，你可以谈一谈扩展性问题。为了避免重复，下面仅列举了高层级的话题。
数据库的扩展：
•纵向扩展与横向扩展。
•关系型数据库与NoSQL。
•主从复制。
•读副本。
•一致性模型。
•数据库分片。
其他话题：
•保持网络层无状态。
•缓存尽量多的数据。
•支持多数据中心。
•通过消息队列来解耦组件。
•监控关键指标。比如，高峰期的QPS和当用户刷新其news feed时的延时都是值得监控的指标。
