设计新闻推送系统(第一部分)

原文:Design News Feed System (Part 1)

译者:飞龙

协议:CC BY-NC-SA 4.0

自豪地采用谷歌翻译

如果你在系统设计面试问题的文章上关注了我们之前的文章,你可能会对新闻推送(译者注:推送、订阅、信息流都是 Feed)系统有多么常见感到惊讶。

无论你是在制作 Twitter,Instagram 还是 Facebook,你都需要某种新闻推送系统来显示来自关注/好友的更新。

实际上,关于新闻推送有一些有趣的细节,比如如何排序,如何优化发布等。所以在这篇文章中,我将介绍这个流行的问题 - 设计新闻推送系统。

问题

为了简单起见,让我们专注于设计 Facebook 的新闻馈送系统,因为不同的产品有不同的要求。

简要总结一下这个功能,当用户进入他们的主页时,他们会以特定的顺序看到好友的更新。推送可以包含图片,视频或文本,用户可能拥有大量的好友。

那么你如何从头开始设计这样的新闻推送系统呢?

子问题

如果你还没有想过这个问题,最好在阅读其余部分之前自行解决。虽然没有标准答案这样的东西,但是通过将你的解决方案与其他人进行比较,仍然可以学到很多东西。

我们开始吧。我们之前说过,面对如此庞大而模糊的系统设计问题时,最好是把大问题分解成子问题,再加上一些概要思想。

对于新闻推送系统,显然我们可以将其分为前端和后端。我将跳过前端,因为这在系统设计面试中并不常见。对于后端来说,三个子问题对我来说似乎至关重要:

  • 数据模型。我们需要一些模型来存储用户和推送对象。更重要的是,当我们试图优化系统的读/写时,有很多的权衡。接下来我会详细解释
  • 推送排名。 Facebook 的排名不仅仅按照时间顺序排列。
  • 推送发布。当只有几百个用户时,发布可能是微不足道的。但是,如果有数百万甚至数十亿的用户,这可能开销较大。所以这里有一个规模问题。

数据模型

有两个基本对象:用户和推文。对于用户对象,我们可以存储用户 ID,名称,注册日期等等。对于推文对象,有推文 ID,推文类型,内容,元数据等,它们也应该支持图片和视频。

如果我们使用关系数据库,我们还需要建立两个关系:用户与推文的关系和好友关系。前者非常简单。我们可以创建一个用户-推文表,存储用户 ID 和相应的推文 ID。对于单个用户,如果他已经发布了多个推文,则可以包含多个条目。

对于好友关系,邻接表是最常见的方法之一。如果我们将所有的用户看作巨型图中的节点,连接节点的边表示好友关系。我们可以使用好友表来为边(好友关系)建模,它的每个条目包含两个用户 ID。通过这样做,大部分的操作都非常方便,例如获取用户的所有朋友一样,检查两个人是否是好友。

数据模型 - 续

在上面的设计中,让我们看看,当我们从用户的所有朋友获取推送时,会发生什么。

系统将首先从好友表中获取所有好友的用户 ID。然后从推文表中为每个好友提取所有的推文 ID。最后,根据推文表中的推文 ID 提取推文内容。你可以看到我们需要执行三个连接,这会影响性能。

一个常见的优化是将推文内容和推文 ID 一起存储在用户-推文中,这样我们就不需要再连接推文了。这种方法被称为去规范化,这意味着通过添加冗余数据,我们可以优化读取性能(减少连接数量)。

译者注:这里有些问题。由于每个推文只有一个作者,所以作者 ID 完全可以放进推文表里面,而且没有冗余。

缺点是显而易见的:

  • 数据冗余。我们正在存储冗余数据,占用存储空间(经典的时空关系)。
  • 数据一致性。每当我们更新推文时,我们需要更新推文表和用户-推文表。否则,数据不一致。这增加了系统的复杂性。

请记住,没有一种方法总是比其他方法更好(规范化与去规范化)。这是你想要优化读取还是写入的问题。

排名

排列推文最直接的方法是创建时间。显然,Facebook 做的不止于此。 “重要”的推文排在最前面。

在跳到排名算法之前,我通常会问为什么要改变排名?我们如何评估新排名算法是否更好?如果候选人自己提出这些问题,这绝对令人印象深刻。

优化排名的原因不是看起来是对的。相反,一切都应事出有因。假设有几个我们关心的核心指标,例如用户粘性,留存率,广告收入等。更好的排名系统可以显着改善这些指标,这也回答了如何评估是否取得进展。

所以回到问题 - 我们应该如何排列推文?一个常见的策略是根据各种特征计算推文得分,并根据分数对推文进行排名,这是所有排名问题最常用的方法之一。

更具体地说,我们可以选择几个与推文重要性最相关的特征,例如,分享/喜欢/评论的数量,更新的时间,推文是否有图像/视频等。然后,可以通过这些特征来计算得分,可能是线性组合。对于一个简单的排名系统来说,这通常足够了。

总结

在写这篇文章之前,我没有想到会有这么多细节,所以我不得不把这个文章一分为二。

在第二部分中,我们将讨论排名,推文发布的扩展性问题,以及其他有趣的主题的更多细节。

如果你觉得这篇文章有帮助,请分享给你的朋友,我会很感谢。 你也可以在这里查看更多的系统设计面试问题和分析。