设计新闻推送系统（第一部分）
原文：Design News Feed System (Part 1)
译者：飞龙
自豪地采用谷歌翻译
如果你在系统设计面试问题的文章上关注了我们之前的文章，你可能会对新闻推送（译者注：推送、订阅、信息流都是 Feed）系统有多么常见感到惊讶。
无论你是在制作 Twitter，Instagram 还是 Facebook，你都需要某种新闻推送系统来显示来自关注/好友的更新。
实际上，关于新闻推送有一些有趣的细节，比如如何排序，如何优化发布等。所以在这篇文章中，我将介绍这个流行的问题 - 设计新闻推送系统。
问题
为了简单起见，让我们专注于设计 Facebook 的新闻馈送系统，因为不同的产品有不同的要求。
简要总结一下这个功能，当用户进入他们的主页时，他们会以特定的顺序看到好友的更新。推送可以包含图片，视频或文本，用户可能拥有大量的好友。
那么你如何从头开始设计这样的新闻推送系统呢？
子问题
如果你还没有想过这个问题，最好在阅读其余部分之前自行解决。虽然没有标准答案这样的东西，但是通过将你的解决方案与其他人进行比较，仍然可以学到很多东西。
我们开始吧。我们之前说过，面对如此庞大而模糊的系统设计问题时，最好是把大问题分解成子问题，再加上一些概要思想。
对于新闻推送系统，显然我们可以将其分为前端和后端。我将跳过前端，因为这在系统设计面试中并不常见。对于后端来说，三个子问题对我来说似乎至关重要：
- 数据模型。我们需要一些模型来存储用户和推送对象。更重要的是，当我们试图优化系统的读/写时，有很多的权衡。接下来我会详细解释
- 推送排名。 Facebook 的排名不仅仅按照时间顺序排列。
- 推送发布。当只有几百个用户时，发布可能是微不足道的。但是，如果有数百万甚至数十亿的用户，这可能开销较大。所以这里有一个规模问题。
数据模型
有两个基本对象：用户和推文。对于用户对象，我们可以存储用户 ID，名称，注册日期等等。对于推文对象，有推文 ID，推文类型，内容，元数据等，它们也应该支持图片和视频。
如果我们使用关系数据库，我们还需要建立两个关系：用户与推文的关系和好友关系。前者非常简单。我们可以创建一个用户-推文表，存储用户 ID 和相应的推文 ID。对于单个用户，如果他已经发布了多个推文，则可以包含多个条目。
对于好友关系，邻接表是最常见的方法之一。如果我们将所有的用户看作巨型图中的节点，连接节点的边表示好友关系。我们可以使用好友表来为边（好友关系）建模，它的每个条目包含两个用户 ID。通过这样做，大部分的操作都非常方便，例如获取用户的所有朋友一样，检查两个人是否是好友。
数据模型 - 续
在上面的设计中，让我们看看，当我们从用户的所有朋友获取推送时，会发生什么。
系统将首先从好友表中获取所有好友的用户 ID。然后从推文表中为每个好友提取所有的推文 ID。最后，根据推文表中的推文 ID 提取推文内容。你可以看到我们需要执行三个连接，这会影响性能。
一个常见的优化是将推文内容和推文 ID 一起存储在用户-推文中，这样我们就不需要再连接推文了。这种方法被称为去规范化，这意味着通过添加冗余数据，我们可以优化读取性能（减少连接数量）。
译者注：这里有些问题。由于每个推文只有一个作者，所以作者 ID 完全可以放进推文表里面，而且没有冗余。
缺点是显而易见的：
- 数据冗余。我们正在存储冗余数据，占用存储空间（经典的时空关系）。
- 数据一致性。每当我们更新推文时，我们需要更新推文表和用户-推文表。否则，数据不一致。这增加了系统的复杂性。
请记住，没有一种方法总是比其他方法更好（规范化与去规范化）。这是你想要优化读取还是写入的问题。
排名
排列推文最直接的方法是创建时间。显然，Facebook 做的不止于此。 “重要”的推文排在最前面。
在跳到排名算法之前，我通常会问为什么要改变排名？我们如何评估新排名算法是否更好？如果候选人自己提出这些问题，这绝对令人印象深刻。
优化排名的原因不是看起来是对的。相反，一切都应事出有因。假设有几个我们关心的核心指标，例如用户粘性，留存率，广告收入等。更好的排名系统可以显着改善这些指标，这也回答了如何评估是否取得进展。
所以回到问题 - 我们应该如何排列推文？一个常见的策略是根据各种特征计算推文得分，并根据分数对推文进行排名，这是所有排名问题最常用的方法之一。
更具体地说，我们可以选择几个与推文重要性最相关的特征，例如，分享/喜欢/评论的数量，更新的时间，推文是否有图像/视频等。然后，可以通过这些特征来计算得分，可能是线性组合。对于一个简单的排名系统来说，这通常足够了。
总结
在写这篇文章之前，我没有想到会有这么多细节，所以我不得不把这个文章一分为二。
在第二部分中，我们将讨论排名，推文发布的扩展性问题，以及其他有趣的主题的更多细节。
如果你觉得这篇文章有帮助，请分享给你的朋友，我会很感谢。 你也可以在这里查看更多的系统设计面试问题和分析。