12. 设计 Facebook 的新闻信息流

12. 设计 Facebook 的新闻信息流

难度等级：困难

让我们设计 Facebook 的新闻信息流，新闻信息流包含一个用户关注的所有用户和页面的帖子、图像、视频以及状态更新。类似服务：Twitter 新闻信息流、Instagram 新闻信息流、Quora 新闻信息流。

1. 什么是 Facebook 新闻信息流？

新闻信息流是一个在 Facebook 主页的中间持续更新的内容列表。新闻信息流包括一个用户关注的用户、页面和群组的状态更新、图像、视频、链接、应用活动以及「喜欢」。换言之，新闻信息流是从图像、视频、地点、状态更新以及其他活动中体现的你的朋友以及你的生活故事的完整可滚动的汇总。

对于任何你设计的社交媒体网站——Twitter、Instagram 或 Facebook——你需要新闻信息流系统显示朋友和关注对象的更新。

2. 系统的要求和目标

让我们为 Facebook 设计一个满足以下要求的新闻信息流：

功能性要求

  1. 新闻信息流的生成基于用户关注的用户、页面和群组发布的帖子。

  2. 用户可能有很多朋友以及关注大量的页面和群组。

  3. 信息流可能包含图像、视频或者只是文本。

  4. 我们的服务应该支持为所有活跃用户将新到达的帖子添加到新闻信息流中。

非功能性要求

  1. 我们的系统应该可以实时生成任何用户的新闻信息流——终端用户看到的最大延迟是 2 秒。

  2. 当一个新的新闻信息流请求进入时，帖子添加到用户的信息流时间不应该超过 5 秒。

3. 容量估算和限制条件

我们假设平均一个用户有 300 个朋友并关注 200 个页面。

流量估算：我们假设有 3 亿日活用户，其中每个用户平均每天获取 5 次时间线。每天共有 15 亿次新闻信息流请求，或者每秒 17500 次请求。

存储估算：平均情况下，我们假设每个用户的信息流中有大约 500 个帖子需要存入内存以提升获取速度。另外假设平均每个帖子的大小是 1KB。这意味着我们需要为每个用户存储大约 500KB 的数据。为了存储所有活跃用户的全部这些数据，我们需要 150TB 的内存。如果一台服务器可以存储 100GB 内存，我们需要大约 1500 台机器的内存保留所有活跃用户的最靠前的 500 个帖子。

4. 系统 API

提示：当我们确定需求之后，定义系统 API 总是好的做法，可以显性说明系统应该是什么样的。

我们可以使用 SOAP 或 REST API 将我们的服务的函数公开。以下为获取新闻信息流的 API 的定义：

getUserFeed(api_dev_key, user_id, since_id, count, max_id, exclude_replies)

参数： api_dev_key（string）：一个已注册的帐号的 API 开发者关键字。关键字将和其他字段一起根据用户分配的额度限制用户。 user_id（number）：用户 ID，系统将为该用户生成新闻信息流。 since_id（number）：（可选）定义返回结果的 ID 下限，返回结果的 ID 必须大于（即更近）给定的 ID。 count（number）：（可选）指定尝试获取的信息流项目数量，每个不同的请求最多 200 个信息流项目。 max_id（number）：（可选）定义返回结果的 ID 上限，返回结果的 ID 必须小于（即更远）给定的 ID。 exclude_replies（boolean）：（可选）这个参数将避免回复出现在返回的时间线中。

返回：（JSON） 返回包含信息流项目列表的 JSON 对象。

5. 数据库设计

有三个主要的对象：用户、实体（例如页面、群组等）和信息流项目（或帖子）。以下是对实体间关联的一些观察：

  • 一个用户可以关注其他实体，以及和其他用户成为朋友。

  • 用户和实体都可以发布信息流内容，信息流内容可以包含文本、图像或视频。

  • 每条信息流内容有一个 UserID，指向创建该信息流内容的用户。简单起见，我们假设只有用户可以创建信息流内容，虽然 Facebook 的页面也能发布信息流内容。

  • 每条信息流内容有一个可选的 EntityID，指向创建该信息流内容的页面或群组。

如果我们使用关系型数据库，我们需要对两种关系建模：用户——实体关系和信息流内容——媒体关系。由于每个用户可以和很多人成为朋友以及关注大量实体，我们可以在一张独立的表中存储用户——实体关系。UserFollow 表中的 Type 列表示被关注的对象是用户还是实体。类似地，我们可以有一张表存储信息流内容——媒体关系。

User 表

User

PK

UserID: int

Name: varchar(20)Email: varchar(32)DateOfBirth: datetimeCreationDate: datetimeLastLogin: datatime

Entity 表

Entity

PK

EntityID: int

Name: varchar(20)Type: tinyintDescription: varchar(512)CreationDate: datetimeCategory: smallintPhone: varchar(12)Email: varchar(20)

UserFollow 表

UserFollow

PK

UserID: intEntityOrFriendID: int

Type: tinyint

FeedItem 表

FeedItem

PK

FeedItemID: int

UserID: intContents: varchar(256)EntityID: intLocationLatitude: intLocationLongitude: intCreationDate: datetimeNumLikes: int

FeedMedia 表

FeedMedia

PK

FeedItemID: intMediaID: int

Media 表

Media

PK

MediaID: int

Type: smallintDescription: varchar(256)Path: varchar(256)LocationLatitude: intLocationLongitude: intCreationDate: datetime

6. 高阶设计

高阶角度，这个问题可以分成两个部分：

信息流生成：新闻信息流从一个用户关注的用户和实体（页面和群组）发布的帖子（或信息流项目）生成。因此，任何时候当我们的系统接收到为一个用户（例如 Jane）生成信息流请求时，我们将执行以下步骤：

  1. 获取 Java 关注的所有用户和实体的 ID。

  2. 获取这些 ID 发布的最近、最流行和最相关的帖子。这些是可以在 Jane 的新闻信息流中展示的潜在帖子。

  3. 将这些帖子基于和 Jane 的相关性排序。这表示 Jane 的当前信息流。

  4. 将这个信息流存入缓存中，返回最靠前的帖子（例如 20 个）作为给 Jane 的信息流。

  5. 在前端，当 Jane 浏览到当前信息流的结尾时，她可以从服务器获取后面 20 个帖子，以此类推。

这里需要注意的一件事情时我们生成信息流依次并存入缓存。如果 Jane 关注的用户有新的帖子如何处理？如果 Jane 在线，我们应该有一个机制对这些新帖子排序并添加到她的信息流中。我们可以周期性地（例如每 5 分钟）执行上述步骤并将更新的帖子添加到她的信息流中。Jane 将会被通知她的信息流中有新的项目可以获取。

信息流发布：任何时候当 Jane 加载她的新闻信息流页面时，她必须从服务器请求并拉取信息流项目。当她浏览到当前信息流的结尾时，她可以从服务器拉去更多数据。对于更新的项目，或者服务器可以通知 Jane 然后她可以拉取新信息流，或者服务器可以将新信息流推送给用户。我们将详细讨论这些选项。

高阶角度，我们的新闻信息流服务需要以下部件：

  1. Web 服务器：维护和用户的连接。这个连接将用于在用户和服务器之间传送数据。

  2. 应用服务器：执行将新帖子存入数据库服务器的工作流。我们也需要一些应用服务器获取新闻信息流并将新闻信息流推送给终端用户。

  3. 元数据数据库和缓存：存储用户、页面和群组的元数据。

  4. 帖子数据库和缓存：存储帖子及其内容的元数据。

  5. 视频和图像存储和缓存：Blob 存储，存储帖子中包含的所有媒体。

  6. 新闻信息流生成服务：将一个用户的所有相关帖子整合和排序，生成新闻信息流并存入缓存。这个服务也将接收实时更新并将这些更新的项目添加到用户的时间线中。

  7. 信息流通知服务：通知用户他们的新闻信息流有更新的项目。

下图是我们的系统的高阶设计架构图。用户 B 和 C 关注用户 A。

7. 部件设计细节

我们具体讨论系统中的不同部件。

a. 信息流生成

我们考虑新闻信息流生成服务获取 Jane 关注的所有用户和实体最近发布的帖子的简单情形。查询语句如下：

(SELECT FeedItemID FROM FeedItem WHERE UserID in (
	SELECT EntityOrFriendID FROM UserFollow WHERE UserID = <current_user_id> and
type = 0(user))
)
UNION
(SELECT FeedItemID FROM FeedItem WHERE EntityID in (
	SELECT EntityOrFriendID FROM UserFollow WHERE UserID = <current_user_id> and
type = 1(entity))
)
ORDER BY CreationDate DESC
LIMIT 100

以下是信息流生成服务的该设计的问题：

  1. 当用户有大量朋友和关注对象时，速度会非常慢，因为必须对大量帖子执行排序、合并、排名操作。

  2. 我们在用户加载页面时生成时间线。这样的速度非常慢并且有高延时。

  3. 实时更新时，每个状态更新将导致所有关注者的信息流更新。这会导致我们的新闻信息流生成服务的大量积压。

  4. 实时更新时，服务器将更新的信息流推送给用户（或者通知用户）会造成极高的负载，特别是对于关注者数量众多的用户和页面。为了提升性能，我们可以预先生成时间线并将其存入内存。

新闻信息流的离线生成：我们可以有专用服务器持续生成用户的新闻信息流并将其存入内存。因此，任何时候当用户为信息流请求新的帖子时，我们可以简单地从预先生成并存储的位置获取帖子并服务用户。使用这个方案，用户的新闻信息流不是在加载时汇总，而是有规律地汇总，当用户请求时返回给用户。

任何时候当这些服务器需要给用户生成信息流时，服务器将首先查询该用户上次生成信息流的时间。然后，新的信息流数据将从该时间向后生成。我们可以将这样的数据存入哈希表中，哈希表的关键字是 UserID，哈希表的值是如下结构体：

Struct {
	LinkedHashMap<FeedItemID, FeedItem> feedItems;
	DateTime lastGenerated;
}

我们可以将 FeedItemID 存入一个类似于 LinkedHashMap 或 TreeMap 的数据结构，这样的数据结构允许我们不仅可以查询到任何信息流，还能方便地遍历映射。任何时候当用户想获取更多信息流项目时，他们可以将他们在新闻信息流中看到的最后一个 FeedItemID 发送，然后我们可以在哈希映射中找到该 FeedItemID 并返回从那里开始的下一批/下一个页面的信息流项目。

对于一个用户的信息流，我们应该在内存中存储多少信息流项目？初始时，我们可以决定为每个用户存储 500 个信息流项目，但是这个数字可以在后面基于使用模式调整。例如，如果我们假设用户信息流的一个页面有 20 个帖子，大多数用户从来不会浏览超过 10 页的信息流，我们可以决定只为每个用户存储 200 个帖子。对于任何项查看更多帖子（超过内存中的存储量）的用户，我们总是可以查询后端服务器。

我们是否应该为所有用户生成新闻信息流（并存入内存）？有很多用户并不会频繁登录。我们有几种办法可以处理这种情况。1. 一个更直接的方法是，通过基于最近最少使用的缓存将长期没有访问新闻信息流的用户从内存中移除。2. 一个更聪明的解决方案是计算用户的登录模式以预先生成他们的新闻信息流，例如，一个用户在一天的什么时间是活跃的，一个用户在一个星期的哪些天访问新闻信息流，等等。

下面的部分我们讨论「实时更新」问题的一些解决方案。

b. 信息流发布

将一个帖子推送给所有的关注者的过程称为扇出。根据类比，推送的方法称为写扇出，拉取的方法称为加载扇出。我们讨论将信息流数据发布给用户的不同选项。

  1. 「拉取」模型或加载扇出：这个方法在内存中保留所有的最近信息流数据，使得用户在任何需要信息流数据的时候都可以从服务器拉去。客户端可以有规律地拉取信息流数据，或者在任何需要的时候手动拉取。这个方法可能的问题有：a) 如果用户不发起拉取请求，可能看不到新数据；b) 难以找到合适的拉取频率，因为大多数时候当没有新数据时拉取请求得到的结果是空的，导致资源的浪费。

  2. 「推送」模型或写扇出：对于推送系统，当用户发布帖子时，我们可以立即将这个帖子推送给所有关注者。好处是当获取信息流时，不需要遍历朋友列表从每个朋友处获得信息流，可以显著减少读操作。为了高效地处理，用户必须维护一个与服务器之间的长轮询请求用于接收更新。这个方法的一个可能的问题是当用户有数百万关注者时（名人用户），服务器必须将更新推送给大量用户。

  3. 混合：还有一个处理信息流数据的方法是使用混合方法，即结合写扇出和加载扇出。特别地，我们可以不从拥有大量关注者的用户（名人用户）推送帖子，只从拥有数百（或数千）关注者的用户推送帖子。对于名人用户，我们可以让关注者拉取更新。由于拉取操作对于拥有大量朋友或关注者的用户会有极大的开销，禁止为他们扇出可以节约大量资源。另一个方法是，当用户发布了一个帖子，我们可以将扇出的范围局限在该用户的在线的朋友中。而且，为了从两种方法获益，「推送通知」和「拉取服务」终端用户的结合是一个很好的方法。单纯的拉取或推送模型的功能更单一。

每个请求中，我们可以给客户端返回多少信息流项目？我们应该规定用户在一个请求中可以获取的项目数量上限（例如 20）。但是，我们应该让客户端明确它们想要在一个请求中获取多少个信息流项目，因为用户可能基于设备（手机或桌面）想要获取不同数量的帖子。

当有新的帖子可以加入用户的新闻信息流时，是否应该总是通知用户？任何时候当有新数据时就通知用户对于用户是很有帮助的。但是，在手机设备上，数据使用相对昂贵，通知用户可能消费不必要的带宽。因此，至少对于手机设备，我们可以选择不将数据推送给用户，而是让用户使用「拉取和刷新」获取新的帖子。

8. 信息流排名

对新闻信息流中的帖子排名的最直接的方法是基于帖子的创建时间，但是当今的排名算法考虑的因素不只是创建时间，而是有很多其他因素，以确保「重要」的帖子排名更靠前。排名的高阶想法是首先选择使得帖子重要的关键「信号」，然后将其结合计算最终的排名得分。

更具体地，我们可以选择任何信息流项目中与重要性相关的特征，例如喜欢数、评论数、分享数、更新时间、帖子是否有图像/视频等，然后使用这些特征计算得分。这种做法对于一个简单的排名系统已经足够普遍。一个更好的排名系统可以通过持续评估是否提升了用户粘度、用户留存、广告收益等的方法显著提升排名结果。

9. 数据分块

a. 将帖子和元数据分片

由于我们每天有大量的新帖子而且我们的读负载也非常高，我们需要将数据分布到多台机器上，使得我们的读写倒错可以高效。对于将存储帖子和元数据的数据库分片，我们的设计可以和「设计 Twitter」中讨论的方案相似。

b. 将信息流数据分片

对于存储在内存中的信息流数据，我们可以基于用户 ID 分块。我们可以尝试将一个用户的所有数据存入一台服务器。当存储时，我们可以将用户 ID 传给我们的哈希函数，哈希函数将用户映射到存储该用户的信息流对象的缓存服务器上。另外，对于任何给定的用户，由于我们预期存储的 FeedItemID 数量不超过 500，我们不会遇到一个用户的信息流对象无法存入一台服务器的情况。为了获得一个用户的信息流，我们始终只要查询一台服务器。对于后续的增长和重复，我们必须使用一致性哈希。

Previous11. 设计网络爬虫Next13. 设计 Yelp 或附近的朋友

Last updated