需求
让我们设计Facebook的新闻提要，其中包含来自Facebook的帖子、照片、视频和状态更新
用户关注的所有人和页面。类似服务：Twitter新闻源、Instagram新闻源、Quora新闻提要
难度等级：难
1.Facebook的新闻源是什么？
新闻订阅是脸谱网主页中间不断更新的故事列表。它包括状态更新、照片、视频、链接、应用程序活动以及来自用户访问的人员、页面和组的“喜好”。关注Facebook。换句话说，它是一个完整的可滚动版本的来自照片、视频、位置、状态更新和其他活动的朋友和你的生活故事
对于你设计的任何社交媒体网站——Twitter、Instagram或Facebook——你都需要一些新闻提要系统显示来自朋友和追随者的更新。
2.系统的要求和目标
让我们根据以下要求为Facebook设计一个新闻提要：
功能要求：
1.新闻提要将基于用户访问的人员、页面和组的帖子生成跟随。
2.一个用户可能有很多朋友，并且关注大量页面/组。
3.提要可能包含图像、视频或文本。
4.我们的服务应支持在所有活动的新闻提要中添加新帖子用户。
非功能性要求：
1.我们的系统应该能够实时生成任何用户的新闻提要-看到的最大延迟最终用户将是2s。
2.假设有一个新的新闻源请求，一篇文章不应该花费超过5秒的时间进入用户的提要进来。
3.容量估算和限制条件
让我们假设一个用户平均有300个朋友，关注200个页面。
流量估计：
假设每天有3亿活跃用户，每个用户都会获取他们的时间线。平均每天五次。这将导致每天15亿个新闻提要请求，约17500个每秒请求数。
存储估计：
平均而言，假设每个用户的提要中需要大约500篇文章，我们想保留在内存中以便快速获取。我们还假设平均每个帖子大小为1KB。这意味着我们需要为每个用户存储大约500KB的数据。储存所有这些所有活动用户的数据我们需要150 TB的内存。如果一台服务器可以容纳100GB，我们会需要大约1500台机器为所有活跃用户保留内存中的前500篇文章。
4.系统API
� 一旦我们确定了需求，定义系统API明确说明系统的期望值。我们可以使用SOAP或RESTAPI来公开服务的功能。以下可能是
获取新闻源的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。
count (number):可选；指定要尝试和检索的提要项的数量，最多为每个不同的请求200个。
max_id (number):可选；返回ID小于（即早于）或等于指定ID。
exclude_replies(boolean):：可选；此参数将阻止回复出现在返回的页面中时间线。
Returns: (JSON)）返回包含提要项列表的JSON对象
5.数据库设计
有三个主要对象：用户、实体（如页面、组等）和提要（或帖子）。这是关于这些实体之间关系的一些观察结果：
•用户可以跟随其他实体并与其他用户成为朋友。
•用户和实体都可以发布包含文本、图像或视频的提要。
•每个FeedItem都有一个用户ID，该ID将指向创建它的用户。为了简单起见，让我们假设只有用户可以创建提要项目，尽管Facebook页面上可以发布提要我也是。
•每个FeedItem可以选择性地具有一个EntityID，该ID指向其所在的页面或组，该职位已创建。
如果我们使用的是关系数据库，我们需要建模两种关系：用户-实体关系和用户-实体关系饲料媒体关系。由于每个用户都可以与许多人成为朋友，并关注许多实体，我们可以将此关系存储在单独的表中。“UserFollow”中的“Type”列标识正在跟踪的实体是用户或实体。类似地，我们可以有一个FeedMedia关系表
6.高层系统设计
从高层次上讲，该问题可分为两部分：
提要生成：新闻提要是从用户和实体（页面和页面）的帖子（或提要项）生成的用户遵循的组。因此，每当我们的系统收到为用户生成提要的请求时（说Jane），我们将执行以下步骤：
1.检索Jane跟踪的所有用户和实体的ID。
2.检索这些ID的最新、最流行和相关帖子。这些都是潜在的职位，我们可以在Jane的新闻提要中显示。
3.根据与Jane的相关性对这些职位进行排名。这表示Jane当前的提要。
4.将此提要存储在缓存中，并返回要在Jane提要上呈现的顶级帖子（比如20篇）。
5.在前端，当Jane完成当前提要时，她可以获取接下来的20个帖子，从服务器等。
这里需要注意的一点是，我们生成了一次提要并将其存储在缓存中。新的呢从Jane关注的人那里收到的帖子？如果Jane在线，我们应该有一个排名机制并将这些新帖子添加到她的提要中。我们可以定期（比如每五分钟）执行上述操作，对新帖子进行排名并将其添加到提要中的步骤。然后，可以通知Jane中有更新的项目。
提要发布：
每当Jane加载她的新闻提要页面时，她都必须请求并从中提取提要项服务器。当她到达当前提要的末尾时，她可以从服务器中提取更多数据。对于更新的项目服务器可以通知Jane，然后她可以提取，或者服务器可以推送这些新项目帖子。我们稍后将详细讨论这些选项。
在较高级别上，我们的新闻提要服务需要以下组件：
1.Web服务器：维护与用户的连接。此连接将用于传输数据用户和服务器之间的数据。
2.应用服务器：执行在数据库服务器中存储新帖子的工作流。我们还需要一些应用服务器来检索新闻提要并将其推送到最终用户。
3.元数据数据库和缓存：存储用户、页面和组的元数据。
4.帖子数据库和缓存：存储帖子及其内容的元数据。
5.视频和照片存储，以及缓存：Blob存储，用于存储帖子中包含的所有媒体。
6.新闻源生成服务：收集并排列所有相关帖子，供用户生成新闻源和存储在缓存中。此服务还将接收实时更新，并将添加这些更新
向任何用户的时间线提供更新的项目。
7.提要通知服务：通知用户有更新的项目可供其使用新闻提要。
下面是我们系统的高层架构图。用户B和C正在跟踪用户A。
Facebook新闻源架构7.详细部件设计
让我们详细讨论一下系统的不同组件。
a、 生产帖子
让我们举一个简单的例子，newsfeed生成服务从所有站点获取最新的帖子
Jane关注的用户和实体；查询如下所示：
代码语言：javascript复制(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.对于实时更新，服务器向用户推送（或通知）更新的帖子可能会导致非常严重的错误沉重的负担，特别是对于有很多追随者的人或页面。改善为了提高效率，我们可以预先生成时间线并将其存储在内存中。
离线生成新闻源：我们可以有专门的服务器不断生成新闻源，用户的新闻提要并将其存储在内存中。因此，每当用户为他们的用户请求新帖子时。feed，我们可以简单地从预先生成的存储位置提供它。使用此方案，用户的新闻提要不是在加载时编译的，而是定期编译的，并在用户需要时返回给用户请求它。
每当这些服务器需要为用户生成提要时，它们都会首先进行查询，以查看上次为该用户生成提要时。然后，从那时起将生成新的提要数据向前我们可以将这些数据存储在一个哈希表中，其中“key”是UserID，“value”是这样的结构：
代码语言：javascript复制Struct {
LinkedHashMap<FeedItemID, FeedItem> feedItems;
DateTime lastGenerated;
}我们可以将FeedItemId存储在类似于链接HashMap或TreeMap的数据结构中，这可以允许我们不仅可以跳转到任何提要项，还可以轻松地遍历映射。只要用户愿意获取更多提要项目，他们可以发送他们当前在新闻提要中看到的最后一个提要ID，我们可以
然后跳转到hash映射中的FeedItemID，并从那里返回下一批/页的提要项。对于一个用户的提要，我们应该在内存中存储多少提要项？最初，我们可以决定存储每个用户有500个提要项，但是这个数字可以在以后根据使用模式进行调整。例如
如果我们假设一个用户提要的一个页面上有20篇文章，而大多数用户浏览的文章不会超过20篇。在他们的提要的10页中，我们可以决定每个用户只存储200篇文章。对于任何想要查看的用户，更多的帖子（比存储在内存中的内容还多），我们可以随时查询后端服务器。
我们应该为所有用户生成（并保存在内存中）新闻提要吗？将会有很多用户不要频繁登录。这里有一些我们可以做的事情来处理这个问题；
1） 更直截了当的这种方法可以是，使用基于LRU的缓存，可以从内存中删除尚未删除的用户长时间访问他们的新闻提要2）一个更智能的解决方案可以找出用户的登录模式，预生成他们的新闻源。例如，用户在一天中的什么时间处于活动状态，以及一周中的哪几天，用户是否访问其新闻源？等
现在，让我们在下一节讨论“实时更新”问题的一些解决方案。
b、 提要发布
将帖子推给所有追随者的过程称为扇出。通过类比，推送方法是写入时称为扇出，而加载时称为拉入方法。让我们讨论不同的选择
用于向用户发布提要数据。
1.“拉”模型或扇出加载：此方法涉及保留所有最近的提要数据内存，以便用户可以在需要时从服务器中提取内存。客户可以提取提要定期或在需要时手动获取数据。这种方法可能存在的问题
a）在用户发出拉取请求之前，新数据可能不会显示给用户；
b）很难找到正确的pull cadence，因为大多数情况下，pull请求会导致空响应，如果没有新数据，造成资源浪费。
2.“推送”模式或写时扇出：对于推送系统，一旦用户发布了帖子，我们可以立即将此帖子推送给所有追随者。优点是在获取提要时
你不需要浏览你朋友的列表，为他们中的每一个人获取提要。这很重要减少读取操作。为了有效地处理这个问题，用户必须维护一个长轮询请求与服务器一起接收更新。这种方法的一个可能问题是用户拥有数百万追随者（名人用户）。服务器必须向很多人推送更新。
3.混合：处理提要数据的另一种方法可以是使用混合方法，即进行写入时扇出和负载时扇出的组合。具体地说，我们可以停止推波助澜来自拥有大量追随者的用户（名人用户），并且只为这些用户推送数据。他们有几百（或几千）个追随者。对于名人用户，我们可以让追随者拉更新。因为推送操作对于拥有大量数据的用户来说可能非常昂贵，朋友或追随者，通过为他们禁用扇出，我们可以节省大量资源。另一种替代方法是，一旦用户发布帖子，我们就可以限制扇出只给她的在线朋友。此外，为了从这两种方法中获得好处，需要将“推送通知”和“拉送服务”最终用户是一种很好的方式。纯粹的推或拉模型。
在每个请求中，我们可以向客户端返回多少个提要项？我们应该有一个最大限度对于用户在一个请求中可以获取的项目数（例如20个）。但是，我们应该让客户指定由于用户可能希望获取不同数量的提要，因此每个请求需要多少提要项发布取决于设备（移动设备与桌面）。
如果用户的新闻提要中有新帖子，我们是否应该始终通知用户？可能是每当有新数据可用时，用户都可以得到通知。但是，在移动设备上使用成本相对较高，可能会消耗不必要的带宽。因此，至少对于移动设备来说是这样，在这些设备中，我们可以选择不推送数据，而是让用户“拉刷新”以获取新帖子。
8.帖子排名
在新闻提要中对帖子进行排名最直接的方法是根据帖子的创建时间，但是今天的排名算法所做的远远不止这些，以确保“重要”职位的排名更高。
排名的高层次理念是首先选择使一篇文章变得重要的关键“信号”，然后了解如何组合它们来计算最终排名分数。更具体地说，我们可以选择与任何提要项的重要性相关的特性，例如。喜欢的数量、评论、共享、更新时间、帖子是否有图像/视频等，以及
然后，可以使用这些特征计算分数。这对于简单的排名来说已经足够了系统一个更好的排名系统可以通过不断评估我们是否在用户粘性、保留率、广告收入等方面取得进展。
9.数据分区
a、 分片帖子和元数据
因为我们每天都有大量的新帖子，而且我们的阅读量也非常高，所以我们需要将数据分发到多台机器上，以便我们能够高效地读/写数据。感谢你把我们的存储帖子及其元数据的数据库，我们可以采用与下面讨论的类似的设计搜索Twitter。
b、 分片馈送数据
对于存储在内存中的提要数据，我们可以基于UserID对其进行分区。我们可以试着储存一台服务器上用户的所有数据。在存储时，我们可以将UserID传递给将将用户映射到缓存服务器，我们将在其中存储用户的提要对象。另外，对于任何给定的用户，
因为我们预计存储的FeeditMeId不会超过500个，所以我们不会遇到feed，一个用户的数据不能放在一台服务器上。要获得用户的提要，我们必须始终进行查询。只有一台服务器。对于未来的增长和复制，我们必须使用一致的哈希。
参考资料
grok_system_design_interview.pdf
