讨论一下Facebook的news feed设计题

虽然是道老生常谈的题，但是有些疑问，拿过来和大家讨论一下。
我认为schema可以分为User, Friend, Feed这几个table, 对于怎么sharding有些疑惑。User/Friend可以通过亲密程度以及地理位置来做clustering, 从而实现shard, 那么feed如何shard比较好呢？
求大家指点！多谢了先~:)

本文被提升为今日话题：凡是在置顶有效期内参与讨论，提供言之有物、切中主题的高质量回复，最低奖励20大米，干货越多奖励越多。

看到好回答，请加分、请顶上去。对认真码字、热心分享的同学表示感谢，今后大家也会看到更多精彩分享。
说明：给别人加分不会扣除你的积分。

戳这里查看以往的全站置顶：
https://www.1point3acres.com/bbs/forum.php?mod=guide&view=digest

14417335 发表于 2019-3-6 10:26
我不知道什么假设是合法的。但是为了让讨论继续下去。

能否暂时假设一个数字，QPS为1，000，000；我们 ...

latency在这里确实不是那么重要，早点晚点没太大关系。可以仅当用户在浏览newsfeed的时候才去poll，server端接收到request时生成news并返回，可以用cache或者其他空闲时间预先生成部分结果来加快。应该不需要15分钟那么久，虽然不用太实时，我觉得也要做到分钟以下级别的。

BridgeHUHX 发表于 2019-3-6 23:10
latency在这里确实不是那么重要，早点晚点没太大关系。可以仅当用户在浏览newsfeed的时候才去poll，serve ...

facebook有删帖的麻烦吗？除了FB公司外，如果原作者自己删除呢？如果删帖后，已经fan out write过了，还需要cache里删除。
好友的好友的好友发帖了，我是否应该收到。这样就需要每个用户维护一个k半径的圈子。
提高latency和降低latency好像只对cache的个数产生影响。如果要保证1分钟内写入所有的应该被通知的用户的feed里，而cache的写入能力是给定的，比如250,000/sec，那么就要求对用户数进行sharding。
对于网红的fan out write是不是也要考虑进去，这样才能计算给定用户数，普通用户发帖量，网红的发帖量，到底需要多少shard。

14417335 发表于 2019-3-6 23:46
facebook有删帖的麻烦吗？除了FB公司外，如果原作者自己删除呢？如果删帖后，已经fan out write过了，还 ...

如果cache的写入能力是给定的，而且要保证latency，那么就要求对用户数进行sharding，这个说的非常好

首先一个问题是你怎么做fan out的。
你是fan out on read 还是 fan out on write?

假设你是 fan out on write, 也就是你发了一个帖子，写到你所有好友的feed里面去，那么我认为feed 按照读的时候的用户来sharding比较合适，因为用户读帖子，他能看到的帖子都分到了同一台机器上，效率很高。 如果按照写的用户来sharding，你有n个好友，你要去n台机器上读，似乎不太合适。

如果你是 fan out on read, 在读的时候，才去看看你好友有谁，然后去fetch他们发的feed， 这样你还是跟着写的用户来sharding也行。

lnkdrefer 发表于 2018-3-2 07:17
首先一个问题是你怎么做fan out的。
你是fan out on read 还是 fan out on write?

多谢，你这个如何做fan out的point提得很好，也是一个关于trade off的考点。Facebook的newsfeed是用fan out on read来实现的，所以就只能跟着写的用户来sharding了。读时n路归并避免不了，不过可以用cache去优化。

提两个问题暖暖贴，

1. 写的时候应该同步还是异步？
2. 如果feed存储在cache里方便优化，而且我们假设cache是分布式的，还有必要写到除了cache以外的其它地方去吗？

这个题的需求是什么，要达到什么样的目标？对throughput和latency有什么要求？

BridgeHUHX 发表于 2019-3-6 04:07
这个题的需求是什么，要达到什么样的目标？对throughput和latency有什么要求？

我不知道什么假设是合法的。但是为了让讨论继续下去。

能否暂时假设一个数字，QPS为1，000，000；我们的系统应该是可以linearly scalable的。希望如果这个数字变大我们无非就是加server而已。

latency 我感觉在我想象中的用户界面里不是太过重要。用户登陆后甚至不一定马上显示出来。用户follow的其它人的帖子出来后，到达这位用户的屏幕上甚至不需要太及时。15分钟如何？

看了上面很多回答都是从system的角度出发的，我当时被问这题从ML设计的角度，比如最先想到goal是为了点击率，然后讨论如何假设用户点击的概率。
再延伸到不同类型的内容（文字，图片，视频），分别有不同的方法提取feature。。。

看你们说的latency等等我完全不懂。。。

攒大米。。。。

顺便问一句大家对FB立面的 “@”at人的功能的设计有什么好的想法，比如@的人的排序算法，和如何存储这个@人的排序的结果以供下次使用？
我的想法是user table立面存好友是用array存这个人的所有好友，然后array是用LRU的思想按照使用频率来排序然后存储。