设计新鲜事（News Feed）系统

新鲜事系统是啥？

各种各样的新鲜事系统，如 Facebook，Twitter，微博，微信朋友圈，以微博为例：

• 时间线，就是打开一个用户的首页，看到的以时间为序列展示的，该用户的微博、转发等等
• 新鲜事，你打开微博，看到的你所关注的用户、明星、大V等发布的内容，以时间为序列展示在你的首页的内容。

4S分析法解构问题

场景 - Scenario

分析该系统需要设计哪些功能，得设计多流弊？

最简单的，就是将这些功能列举出来：

• 发布/转发新鲜事；
• 时间线/新鲜事；
• 用户关注/取消关注；
• 登录/注册；
• 搜索新鲜事；
• 用户 Profile 的展示与编辑；
• 上传图像/视频
• ……

加粗的是我认为在一个新鲜事系统里最重要部分。在系统设计面试中，要快速选择出功能列表中哪些功能是该系统中最核心功能。

挑选出核心功能，后面一步就是要分析、推断、预测出系统中的用户规模与访问量。如下是 Twitter 月活跃用户统计图表：

img

Twitter 的 MAU 差不多在 300M，MAU（月活） 与 DAU（日活）的数量根据经验值约是两倍关系，可推出 DAU 为 150M 。根据 150M 的 DAU，假设用户每天平均请求的次数为 60 次，可计算出平均每秒并发访问量约为：150M * 60 / 86400 = 100 K/s。而通常每日访问的峰值大约在平均每秒并发访问量的 2~9 倍，因此，访问峰值的合理估计数值在 200 K/s ~ 900 K/s 之间。

大约可推断出如下与系统规模相关数字：

• DAU：150M
• MAU：300M
• 平均每秒并发访问量：300K
• 读 QPS：300K（读一定比写多）
• 写 QPS：5K

当然，以上数字全部都是估计与推断的结果，重要的不是这个推断出来的结果，有时这个推断过程更加重要，言之有理能够给出合理解释即可。系统的性能瓶颈由系统中各个部分的最短板决定。

服务 - Service

将大系统拆分为小服务。

• 第一步 - Replay：重新过一下所有需求，为每个需求添加一或多个服务
• 第二步 - Merge：归并相同的服务

可将新鲜事系统拆为如下服务，每个服务中会包含场景分析中提到的各个功能：

• User Service（用户服务）：
  • 登录
  • 注册
• News Service（新鲜事服务）：
  • 发布/转发新鲜事
  • 新鲜事
  • 时间线
• Friendship Service（好友服务）：
  • 关注好友
  • 取消关注
• Media Service（媒体服务）：
  • 上传图片
  • 上传视频

存储 - Storage

• 第一步 - Select：为每个服务选择合适存储结构
• 第二步 - Schema：细化数据库表结构

选择合适的存储结构：

• SQL 关系型数据库
  • 用户信息
• NoSQL 非关系型数据库
  • 新鲜事内容（推文、微博内容）
  • 社交图谱
• 文件系统
  • 图片/视频

简单的表结构设计实例：

• 针对 User Service（用户服务），用户表可设计：

数据库中存放的密码一般是经hash后的。

• Friendship Service（好友服务）可能包含如下的关系表结构：

from 用户关注了to用户， from_user_id 和 to_user_id 是 User表的外键关联。

• News Service（新鲜事服务）存储新鲜事的表结构：

升级、扩展 - Scale

解决缺陷，处理可能遇到的问题。

如何存取信息流（News Feed）/ 时间线（Timeline）？

当你打开微博：

• 打开首页，看自己关注的用户发布了哪些新内容
• 打开某特定用户的时间轴，浏览该用户发布的内容

聚焦信息流和时间线的数据存储和数据访问，来权衡设计。

Solution A：拉模型（Pull Model）

主动型的模型。当你打开微博，查看自己的新鲜事订阅（其它你所关注的用户发的微博）时，系统会先去取出你所关注的的用户列表，再分别把这些你所关注的的用户的时间线上的微博取出来，最终按时间执行归并排序，返回给你所需要的新鲜事订阅。

当你需要获取新鲜事列表时，系统是去你所关注（Follow）用户的时间线列表，拉取你所需要的新鲜事。

1. 用户打开新鲜事列表，获取所有关注的其他用户
2. 获取这些用户时间轴中的前 100 条新鲜事
3. 将【2】中取到的新鲜事，按时间排序，合并成为一个 100 条的新鲜事列表（K 路归并）

img

复杂度

假设该用户关注了 N 个用户：

100*N次DB读 + N路归并 = 100*N次DB访问 + 100log(N)内存处理

一般内存处理的时间<< DB 访问时间，因此可忽略不计。【拉模型】下，若用户发布了一条新鲜事，会发生啥?

该模型下，用户发表一条新鲜事，只需在用户自己的时间轴中插入一条数据，即执行一次DB写。

伪代码

// 获取新鲜事列表
public List<Feed>  getNewsFeed(request) {
  List<Feed> followings = db.readFollowings(request.user);
  List<Feed> newsFeedList = [];
  
  followings.forEach(f -> {
    List<Feed> feeds = db.getTimeLine(f.to_user, 100);
    newsFeedList.push(feeds);
  });
	return K_sort(newsFeedList);
}

// 发布新鲜事
public String postNews(request, content) {
  db.insertNews(request.user, content);
  return "success";
}

缺陷

当用户想拉取自己订阅的新鲜事list，需执行较多DB操作，用户需等待这一系列 DB 操作执行完成，系统才会将新鲜事list返给客户端显示，对于用户就得等待较长时间。

Solution B：推模型（Push Model）

系统为每一个用户都维护了一个新鲜事列表，当某用户发了一条新鲜事，所有关注该用户的新鲜事列表里都会被插入一条该新鲜事；当一个用户查看自己订阅的新鲜事列表时，仅需从自己的列表中取出前 K 条新鲜事即可。

算法描述

1. 为每个用户建立一个存储他的新鲜事的列表，列表中只包含他所关注的用户发布的新鲜事
2. 当某个用户发布新鲜事后，会将该新鲜事逐个推送至每个关注他的用户的新鲜事列表
3. 当用户需要查看自己订阅的新鲜事列表时，只需按时间顺序，从该新鲜事列表中取出

复杂度分析

当用户在刷新自己订阅的新鲜事列表时，只需1次DB读取。

当用户发一条新鲜事，若该用户被 N 个用户关注，则需执行 N 次 DB 写入。

在用户请求到达服务端后，服务端可先返回给用户“已发送成功”消息，用户无需等待所有数据插入完成，该操作可在系统异步执行，即【Fanout】：

假设现有四个用户之间好友关系如下：

张东升在 2020 年 06 月 20日 8：30 发一条新鲜事：“一起去爬山啊！”，此时新鲜事数据库表数据如下：

img

老陈发了一条新鲜事“今天碰上一个臭小子！”

img

严良发了一条：“我爸爸在哪呢？”：

img

朱朝阳结束了疲惫的一天发了条“终于记完了今天的日记。”：

img

基本伪代码：

// 获取新鲜事列表
function getNewsFeed(request) {
	return db.getNews(request.user);
}

// 发布新鲜事
function postNews(request, content) {
  db.insertNews(request.user, content);
  AsyncTask.asyncExec(request.user, content);
  return "success";
}

AsyncTask.asyncExec = (user, content) => {
	let followings = db.readFollowings(request.user);

 	followings.forEach(f => {
	  db.insertNews(f, content);
  });
}

缺陷

• **浪费DB空间：**同一条新鲜事会在数据表中存储多条，尽管这问题可通过在 fanout 的表中，只记录新鲜事 id 来优化，但是相比较而言，这一方案是更浪费DB存储空间
• **新鲜事更新可能会不及时：**如一个明星有 1M 粉丝，整个 Fanout 的过程可能要持续相当一段时间，有些粉丝可能已经收到这个明星发布的新鲜事，但是有的粉丝可能半小时后才收到，影响用户吃瓜的体验！

推 or 拉？

img

两个方案各领风骚。

但实际系统设计更多选择【拉模型】，如：

• Facebook、Twitter 使用 Pull 模型
• Instagram 使用的是 Push + Pull 模型

只使用推模型的例子较少，毕竟我们注重用户体验。实际情况中，若系统流量不大，使用 Push最经济/省力。系统设计面试，方案比较分析与回答存在误区：

• **不要不坚定想法，在几个方案间摇摆：**比如面试官对你的 Pull 模型提了质疑，指出缺陷，你就摇摆到 Push 模型，这是错误的回答方式
• **要展现出 tradeoff 能力：**要针对当前系统设计方案的缺陷做权衡

如何优化？

即【扩展 - Scale】部分，解决设计缺陷。

解决 Pull 模型的缺陷

Pull 模型系统瓶颈（bottleneck），该模型最慢部分在于用户请求新鲜事列表时，且这一过程需消耗用户等待时间。

可在访问DB前加个缓存层，若缓存命中，直接将数据返给用户，大大缩减用户等待时间。

那缓存存啥？

每个用户的时间线（Timeline）

相当于把之前 N 次（N 为关注的好友的个数） DB 请求替换成 N 次缓存访问，可以提速。但缓存不能存储海量数据，因此要做出tradeoff，如每个用户只缓存最新 1000 条或最新 100 条新鲜事，还可将明星、热点用户（用友大量关注者的用户）的缓存长期保存在缓存系统，不轻易让缓存失效

每个用户的新鲜事列表（News Feed）

拉取新鲜事列表时，就仅需一次 Cache 访问：

• 无缓存新鲜事列表的用户，归并 N 个关注好友的最新 100 条新鲜事，取出前 100 条放入缓存
• 已做缓存的用户，归并 N 个用户在某个时间之后的所有新鲜事，加入缓存

该方案中，也可针对不同用户做优化，如针对经常使用系统、经常频繁刷新新鲜事的用户做优化，将他们的缓存长期存放，对一些长期不使用的僵尸用户，将他们的缓存清掉。

由于系统的突然爆发式的访问，造成缓存失效，如何处理？

解决 Push 模型缺陷

浪费DB存储空间，但这不算问题，毕竟“Disk is cheap.”。

由于 Fanout 时间可能较长，导致用户有可能在自己所关注的用户发布新鲜事一段时间后，才能够在自己的新鲜事列表里刷到该条消息。可采用一定方案提升用户体验，在 Fanout 时，先对粉丝按规则排序，如按用户活跃度（按最新登录系统时间排序），针对活跃度越高用户，优先进行推送。

另外，针对某些明星用户或者说热点用户（关注他们的用户数量远远大于他们自己所关注用户的数目），整个 Fanout 的时间可能会很长。解决这一个问题有一个很粗暴的方案，就是增加机器的数量，采用分布式 Fanout 的方案。

Push 模型 + Pull 模型的方案

将 Push 方案 和 Pull 方案结合优化。

针对普通用户采用 Push

针对明星这类热点用户，在系统里进行标记。

对于明星用户发布新鲜事，不将新鲜事 Push 到关注了这一明星的列表。当用户需获取自己的新鲜事列表时，到自己所关注的明星用户的时间线上取并合并到自己的 News Feed 列表。

热点用户迅速涨粉/掉粉（摇摆问题）

将明星用户标记，对非明星用户使用“Push”的方案，对明星用户采用“Pull”方案。这会带来什么问题呢？

如系统定义被关注数量有 1M 以上用户为明星用户，此时有一个用户被关注数量为 1M，同时存在大量用户在点击对该用户的关注/取关，这一用户在系统中就会被频繁被标记为“明星”/“非明星”用户，在“Pull”和“Push”模型之中来回切换，导致有用户收不到该“明星用户”发布的新鲜事。这一问题称为“摇摆问题”。

img

最简单的：不对动态的对明星用户进行标记。即用户的关注、取关行为不会立刻影响到该用户会不会被标记为“明星用户”，这一标记过程可异步使用一个线程，定期做。

还有一种解决思路，使用一个缓冲地带，如给用户加入一个“伪明星”状态，针对这一状态的用户单独处理。

僵尸粉

系统中长期不活跃的用户，但是他们也有许多关注的用户，也有少量粉丝。

这种用户有时会给系统带来一些不必要负载，影响整个系统性能。

可单独针对这一类用户处理。比如，我们在系统中对这些长期不活跃的用户进行标记，系统如果使用的是 Push 模型的话，在 Fanout 的过程中，将该类用户设置优先级，放到该过程最后执行。

关注（Follow）与取关（Unfollow）

若采用 Push 模型：

• 当一个用户 A 去 Follow 了用户 B 之后：将用户 B 的 Timeline 异步合并到 A 的 New Feed
• 当一个用户 A 去 Unfollow 了用户 B 之后：将用户 B 的 Timeline 异步从 A 的 New Feed 中删除

异步原因是这过程可能较慢，采用异步可迅速给到用户反馈，让用户觉得“已”关注或取关完成。随之问题是，用户在刷新自己的 News Feed 时发现，可能还会收到自己已经取关的用户的新鲜事。但终究该用户的 Timeline 中是会把自己已经取关的用户的新鲜事删掉。

明星出轨

惊群效应、缓存、缓存雪崩、缓存重建。《Scaling Memcache at Facebook》。

查询共同好友？

常规思路

没有一个系统会让你展现出来你所有的好友与你之间的共同好友，一般只要展示出来你和另一用户之间共同好友的 Top10 或 Top20，所以可简化系统设计。

若每次都去请求好友的好友list进行遍历，复杂度是 O(N * max(N,M)) ：

• N，该用户的好友数
• M，他好友的好友数量

响应时间较慢，但其实可以提升响应速度而牺牲一点精确度（对用户体验牺牲也不 大），因为基于我们的需求，只需 TOP10即可 ，最终结果差一两名影响不大。

针对这一方案，也有对应优化策略：

• 每个用户额外使用一个表，记录与自己共同好友较多的 Top10 用户列表， 每次用户请求 Top10 时直接返回
• 当新加一个好友时，异步使用上述算法，求两个用户之间的共同好友，并且使用共同好友 Top10 表里面的最少共同好友的记录去比较，看是否需要更新结果。 同时，异步更新这两个好友的共同好友列表，因为有可能由于这次操作他们直接多了一个共同好友

还有个暴力方法，但也科学：

如对 QQ 来说，有好友上限的，假设为5000。针对系统来说，就算把一个用户的所有好友的 id 存放到缓存（比如 Redis）也就 80 KB左右，若计算交集，即便不使用 HashMap ，计算量的数量级大概在 10^7，系统计算反应时间也是ms级，其实直接使用缓存系统 + 暴力也可行。因为其实查询共同好友这一功能并不是一个非常常用的功能，通常也不会出现缓存雪崩或者缓存失效。

朋友圈的可见/不可见

总结

• 问清需求再设计
• 不做关键词大师
• 不试图设计一个最牛的系统，要设计一个够用的系统
• 先设计MVP，再逐步优化
• 系统设计无标准答案，和面试官一起探讨分析的过程比结果更重要