新鲜事系统设计
Twitter, 朋友圈
新鲜事系统的核心因素?
关注与被关注, 每个人看到的新鲜事都是不同的.
Pull Model
算法: 在用户查看 New Feed 时, 获取每个好友的前 100 条 Tweets, 合并出前 100 条 News Feed. (K 路归并算法)
复杂度分析: 假如有 N 个关注的对象, 则为 N 次DB Reads 的时间 + K 路归并的时间 (可忽略, 因为访问磁盘速度远远慢于运算速度)
Pull 模型有什么缺陷
Pull 模型每次用户刷新, 都需要现算, 需要一定的时间, 体验不好.
Push Model
算法:
-
为每一个用户建立一个 List 存储他的 News Feed 信息.
-
每一个用户发送一个 Tweet 之后, 将该推文推送到每个用户的 News Feed List 中. (Fanout)
-
用户需要查看 News Feed 时, 只需要从该 News Feed List 中读取最新的 100 条即可.
复杂度分析:
-
News Feed: 1 次 DB read
-
Post a tweet: N 个粉丝, 需要 N 次 DB writes. 但是好处是可以用异步任务在后台执行, 无需用户等待.
可以异步在后台执行, 无序用户等待
| News Feed Table | |
|---|---|
| id | primary key |
| owner_id (接收 News 的用户) | foreign key |
| tweet_id | foreign key |
| created_at | timestamp |
东邪发了一条帖子: 好想念超风
西毒发了一条帖子: 好想念嫂子
郭靖发了一条帖子: 不知道华筝怎么样了
黄蓉发了一条帖子: 男人都不是好东西
| id | owner_id | tweet_id | created_at |
|---|---|---|---|
| 1 | 东邪 | 好想念超风 | No1 |
| 2 | 西毒 | 好想念超风 | No1 |
| 3 | 西毒 | 好想念嫂子 | No2 |
| 4 | 郭靖 | 不知道华筝怎么样了 | No3 |
| 5 | 东邪 | 不知道华筝怎么样了 | No3 |
| 6 | 西毒 | 不知道华筝怎么样了 | No3 |
| 7 | 黄蓉 | 不知道华筝怎么样了 | No3 |
| 8 | 黄蓉 | 男人都不是好东西 | No4 |
| 9 | 郭靖 | 男人都不是好东西 | No4 |
| 10 | 东邪 | 男人都不是好东西 | No4 |
黄蓉登录后, 可以看到的帖子通过一句 SQL 查询就可以拿到:
select * from news_feed_table where owner_id = 黄蓉 order by created_at desc limit 20;
如上的 SQL 语句怎么建立索引呢?
应该建立一个复合索引, 先按照 owner_id 排序, 再按照 created_at desc 来排序. 不能单独建立 owner_id 的索引或者单独建立 created_at desc 的索引, 因为查询的时候都是复合条件的, 单个索引没有用. 怎么查的决定怎么建立的索引.
Push Model 有什么缺陷
有些大V有很多粉丝, 那么发送一条 Tweet 在数据库中创建的记录就会非常巨大, 开销非常大.
怎么选呢
先看看热门 Social APP 的模型
-
Facebook: Pull
-
Instagram: Pull + Push
-
Twitter: Pull
-
朋友圈: Push
Facebook, Instagram, Twitter 的 News Feed 都需要进行实时的运算, 而不是单单使用时间来进行排序, 所以需要 Pull 模型来实时进行运算. 而朋友圈只按照时间展示动态, 所以在发布动态的时候就可以仅仅按照时间插入到 News Feed List 中, 可以使用 Push 模型.
误区
-
不坚定想法, 摇摆不定
-
不能表现出 Tradeoff 能力
-
无法解决特定的问题
Scale 扩展
1 解决 Pull 的缺陷
最慢的部分发生在用户读请求时(需要消耗用户等待时间)
-
在 DB 访问之前加入 Cache
-
Cache 每个用户发过的帖子
-
N 个 DB 请求 --> N 次 Cache 请求 (N是关注的好友个数)
-
Trade off? Cache 用户发布的所有帖子? Cache 用户发布最近 1000 条帖子?
-
-
Cache 每个用户的 News Feed (可能刷的过于频繁, 关注的人没有在这段时间发布帖子)
-
没有 Cache News Feed 的用户: 归并 N 个用户最近的 100 条结果, 取出结果的前 100 条.
-
有 Cache News Feed 的用户: 归并 N 个用户在某个时间戳 (上次 Cache News Feed 的时间) 之后的 Tweets.
-
2 解决 Push 的缺陷
Push 的机制就是写扩散
-
浪费更多的存储空间 Disk
-
与 Pull 模型将 News Feed 存储在内存中相比很便宜
-
Disk is cheap
-
-
不活跃用户
- 粉丝排序
-
粉丝数目 followers >> 关注数目: 大V粉丝及其多, 他们发布的一条帖子会 fanout 出几千万的记录.
面试时错误的回答方案: 既然 Push 不行, 那我们就切换成 Pull 吧. 这样肯定不可以, 因为前面可能已经构建完毕, 才发现这个问题, 如果草率切换, 以前的工作全部白费.
前期用户少, 可以使用 push 模型, 节省 pull 模型可能的内存开销. 后期用户多了, 可以进行重构, 重构为 pull 模型.
3 Push + Pull 优化方案
-
普通的用户仍然 Push
-
将大V标记为明星用户, 不 Push 到用户的 News Feed 中.
-
当用户需要时, 来明星用户的 Timeline 中获取, 并整合进入 News Feed 中.
4 总结
系统面试不只是期望你答出来最优的解决方法, 而是从你的分析当中判断你对系统的理解和知识的储备.
-
什么时候用 Push?
-
资源少 (用 Disk 即可)
-
实时性要求不高
-
代码简洁
-
用户少, 明星用户少
-
-
什么时候用 Pull?
-
资源充足 (Cache 多)
-
实时性要求较高
-
用户发帖多
-
用户多, 有明星用户
-