设计新鲜事（News Feed）系统

谁借莪１个温暖的怀抱￠ 2024-04-07 16:04 18阅读 0赞

#### 新鲜事系统是啥？ ####

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

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

### 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（用户服务），用户表可设计：
    
    ![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_SmF2YUVkZ2U_size_16_color_FFFFFF_t_70_g_se_x_16][]
    
    数据库中存放的密码一般是经hash后的。
 *  Friendship Service（好友服务）可能包含如下的关系表结构：
    
    ![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_SmF2YUVkZ2U_size_17_color_FFFFFF_t_70_g_se_x_16][]

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

*  News Service（新鲜事服务）存储新鲜事的表结构：
    
    ![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_SmF2YUVkZ2U_size_19_color_FFFFFF_t_70_g_se_x_16][]

#### 升级、扩展 - Scale ####

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

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

当你打开微博：

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

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

###### Solution A：拉模型（Pull Model） ######

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

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

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

![img][img 1]

**复杂度**

假设该用户关注了 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】：

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_SmF2YUVkZ2U_size_20_color_FFFFFF_t_70_g_se_x_16 1][]

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

![watermark_type_d3F5LXplbmhlaQ_shadow_50_text_SmF2YUVkZ2U_size_20_color_FFFFFF_t_70_g_se_x_16 2][]

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

![img][img 2]

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

![img][img 3]

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

![img][img 4]

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

![img][img 5]

**基本伪代码：**

// 获取新鲜事列表
    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][img 6]

两个方案各领风骚。

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

*  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][img 7]

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

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

### 僵尸粉 ###

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

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

可单独针对这一类用户处理。比如，我们在系统中对这些长期不活跃的用户进行标记，系统如果使用的是 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》][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，再逐步优化
 *  系统设计无标准答案，和面试官一起探讨分析的过程比结果更重要

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_SmF2YUVkZ2U_size_20_color_FFFFFF_t_70_g_se_x_16]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/3b20e45aeb5d486298813825da9e0327.png
[img]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/4be8b16284ca4dab8fc6be16a2555100.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_SmF2YUVkZ2U_size_16_color_FFFFFF_t_70_g_se_x_16]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/0025ad55f5024f1aa4725cff952a3c98.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_SmF2YUVkZ2U_size_17_color_FFFFFF_t_70_g_se_x_16]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/5fa516f0083442a1a3c880e5ab161dfd.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_SmF2YUVkZ2U_size_19_color_FFFFFF_t_70_g_se_x_16]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/5505929554aa4130a0f7496ab47cb047.png
[img 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/64f87f68452541418dc0d7ecad78861f.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_SmF2YUVkZ2U_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/63023584fc824dea8fb52cc033155072.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_SmF2YUVkZ2U_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/61b0f67b70054226b487cf784887cd67.png
[img 2]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/b58fa1c0790046c39c70bc2272c8b0a9.png
[img 3]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/fdbfdfbb9b9f4b339cd04de01464548b.png
[img 4]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/af2a000f13be44059c11b5db767db9f8.png
[img 5]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/1afa51c914494095943f55c03e8fec27.png
[img 6]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/75c17ac2b5544488b6d2cecd992b7c93.png
[img 7]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/07/d5dfc86a7dc44f3dbf8279d569c631bb.png
[Scaling Memcache at Facebook]: https://www.usenix.org/system/files/conference/nsdi13/nsdi13-final170_update.pdf