[转]系统设计丨如何设计Twitter

随笔,算法 2018-11-12

原文链接:http://blog.bittiger.io/post156/

*本文来自于BitTiger冯沁原老师的硅谷之路系列视频之如何设计Twitter,欢迎大家回看视频:https://www.bittiger.io/classpage/tAkRctFLtgNuCj5ev

今天来聊一聊如何设计Twitter,这是第一篇章。

1-768x324.png

如何设计Twitter是个经典的面试问题,我们要想一想Twitter的本质是什么,它其实是feed流。那什么是feed流呢?有很多list,这些List的集合就是你最终展现的结果,把一些list集合到一块去就是feed流。这个概念跟Kafka其实是非常相似的,Kafka是按照时间排序把很多log流聚合到一块。除了Twitter,还有很多现在火爆的应用主要功能都涉及到了feed流,比如Facebook、微博、微信朋友圈、Google Reader、今日头条。

2-768x405.png

进一步来看,我们举个具体的例子,比如说在Twitter中,我们有三个feed list,这里需要强调,因为在不同公司不同项目叫法不太一致,我们讲的feed是指单独的list,而list的集合叫timeline,所以timeline是feed的聚合,而每个单独的feed就是一个list。比如说上图中第一列是关于Nelson自己的list,第二列是关于Tim自己的list,第三列是QCon的list,每个人自己的feed可以放一起。

3-768x388.png

如果聚到一块就叫timeline。这里这个概念非常重要,大家要记住,每个单独的列表是自己的list,例如朋友圈有自己发的内容,你妈妈发的内容,你爸爸发的内容,那三个聚集到一块,成为你观看所有好友list的朋友圈就是timeline。对这个概念的理解有助于做后面的部分。

4-768x428.png

在Twitter里除了每个人自己的list外,第二重要的概念是每个人都有自己的好友关系,为什么说重要呢?只有有了这个好友关系和关注关系,才能够把你关注的所有人的信息聚集到一起,得到最终的结果social graph。这个关系图可以是单向或双向的,但为了简单起见,我们会把它看成单向,因为单向也可以表示双向。

根据我们的系统设计SNAKE(Scenario, Necessary, Application, Kilobit, Evolve)原则,首先需要了解场景,根据上面的介绍,我们对场景已经有了基本的认识。

第二个是限制条件,对于Twitter有什么限制性条件呢?大家可以猜猜Twitter实时的限制是多少?在Twitter里我们往往最关注读和写。Twitter的读,得到自己Timeline的请求是QPS=300k,这是很大的值,意味着每秒30万个人在读自己的list;那它的写是多少呢?只有5k,也就是说它的写远远少于读。这很正常,大多数情况读的人比较多,而写的人比较少。

5-768x256.png

在Twitter里另外一个重要功能是通知功能,比如Lady Gaga有几千万的关注者,她发了一条通知,会希望在之后的几十秒内能让所有关注者都收到这条通知,这时候就需要通知每个关注者。

Twitter希望做到什么能力呢?做到每秒一百万条通知,这是一个非常厉害的数字。那我们根据这个数字可以计算在Twitter里并发用户有多少个,答案是1500万个。那每天可以推送多少消息呢?用每秒发的数量乘以1天时间就行,得到答案大概每天4亿tweets,这是很大的数量,有这个数量以后我们可以计算每天的硬盘需求量,内存需求量。

在Twitter设计时,如果想把消息通知所有人,一共有两种模式:一种是自己拿广播通知所有人,这叫“推”模式;一种是有人主动来找你要,这叫“拉”模式。

首先讲最基本的“推”模式。

在任何一个模式里面,我们仍最关心两件事,读和写。首先什么是写呢?如果一个用户写了一条推文“Hello,I’m Fannec”,首先会调用Twitter自己对外写的API,这样才能写到后面执行所有的流程,写API要做的事情是通知大家推送出去消息,需要广播给所有关注的好友把消息发送他们。具体发送给谁呢?就需要Fanout广播系统读出我的好友关系,接着用O(n)的复杂度。因为每个人都需要写,比如一万个人关注我,就需要发一万份消息给大家,所以需要在每个人 的List后面加一个消息,“Fannec发送一条新消息”。这就是写。

1-5-768x824.png

写完以后怎么读呢?如果写是O(n),读就简单了,为什么呢?只需要把自己的Timeline读出来就可以展现最终结果。所以当你写的时候是O(n),读的时候是O(1)。比如另外一个人上线以后,直接从Timeline Service里得到他的Timeline,最终结果就出来了。

2-4-768x781.png

这个模式有什么缺点吗?

最大缺点就是Lady Gaga模式,什么意思呢?Lady Gaga有将近5000万的关注用户,当Lady Gaga发一条消息时,需要读出5000万个关注者,然后写出5000万份,那在这一瞬间就只能写Lady Gaga的,别人的没法写。所以当关注者太多时根本来不及写,或者说当写这个的时候别人都没办法写,难道每次Lady Gaga发消息别人都要延迟一分钟吗?肯定不能。那最好的方法怎么做呢?其实最好的方法就是只通知在线用户,因为在线用户需要立刻观看,不在线用户可以慢一些,所以可以用这种方法来优化。在线的关注者可能只有500万,这样5秒钟就通知完了。这是一个很好的方法,但广播模式最大的问题仍然是当一个人有很多关注者就会变得很慢。

3-6-768x918.png

换成“拉”模式怎么样?

依然从读和写两方面看,如何写决定了如何读。那如何写呢?首先写条消息,然后发到writeAPI,这回变聪明了,这条消息只写到自己的list中,如果是Fannnec就写到Fannec List里面,如果是Lady Gaga就写到Lady Gaga的List里。所以写的时候只写一条,因为只写自己,不写其他人,是O(1)的复杂度。

4-5-768x804.png

写的时候容易,但读的时候呢?比如另外一个人需要读,他一定要去看自己关注的所有人,然后才能从Feed List里找到所有人的消息,把所有人的消息聚集到一起,所以读的时候会变得很慢,写是O(1)但读的时候是O(n)。

5-2-768x825.png

这就是上文所说的balance,需要做一个选择。当读取时如果关注了很多人,跟“推”模式相反,Lady Gaga是如果一个人被关注太多会成为瓶颈,“拉”模式是如果一个人关注很多人会成为问题,比如黑客帝国架构师的问题,黑客帝国架构师关注了世界上所有人,当他想知道世界发生什么事情的时候,难道要把十亿人的行为全部放到一起去吗?根本来不及看,架构师就会把系统弄崩溃。

“推、拉”模式都有缺点怎么办?

第一个想法肯定是“推拉结合”,这很简单,对于那些关注者比较少的就推过去,对于那些关注者比较多的就拉过来。所以最终结果是当有一个人想要得到消息时, 他的一部分关注者,那些关注者少的人会通过“推”模式发出来,而关注者比较多的人,如Lady Gaga,贝克汉姆之类还要“拉”一下,这两种方式可以混合得到最终结果,所以“推拉结合”的方式往往能够比较好的解决问题。

6-2-768x653.png

“推拉结合”难道没有问题吗?

问题是关注者的阈值怎么设。设置10万还是20万更合适?即使设置10万的定值还会有一个问题,叫做摇摆者问题,如果一个人的关注者在10万左右来回摇摆,是不是会出问题呢?有人可能会说Twitter怎么可能会把自己的关注数减少呢?不可能的。但有一种情况很可能会出现剧烈的摇摆,就是清理僵尸粉,比如新浪微博会有一段时间看到僵尸粉太多了,清理一下吧,结果发现系统中一半以上的ID都有僵尸粉,一清理,很多人的关注者从10万直接变成了几千,很多人会在推拉间从“拉”模式变成了“推”模式,这种情况就会产生巨大的摇摆,系统会在短时间出现问题。那怎么办呢?是否有别的办法?其实任何一个系统,针对一个绝对阈值设置不同的行为往往会出现问题,因为会发生摇摆,所以我们需要设置一个范围阈值。什么意思呢?如果关注数少于10万的话就开始推,如果关注数大于9万就开始拉。也就是设立一个阈值,当用户从10万往下降的时候并不会影响到自己的摇摆,它摇摆的过程被限制住了。所以通过设置一个范围的情况,能够极大的减少抖动,当然也不是绝对解决问题。但可以想一想设立一个缓冲区也是同样意义,比如两个国家打仗,无法完全分出胜负怎么办?就会在中间设置几个缓冲区,谁也别占,这样能够取得一定的平衡。

7-3-768x725.png

面试时,选择推还是选择拉呢?

我们有一些选择标准可以帮助判断。

第一:理解场景。比如像微信的后台架构,对于微信而言,群聊是“拉”模式好还是“推”模式好呢?必然是“推”模式好,为什么呢?因为群聊里最多是500人,所以说推的成本比较低,而“拉”模式会很复杂。而对于Twitter可以根据具体情况分析选择。

第二:延迟、计算、存储量之间做平衡。根据自己服务器的情况及当前的场景和未来的预估去做决定。

第三:O(n)不可行。在分布式系统中如果做算法,O(n)已经很低,但很多时候做分布式O(n)往往是不可行的。为什么呢?可能O(n)里面的每一个1都已经是很复杂的操作,比如每个1需要10毫秒,n是1万,那就是好几秒时间。所以当在分布式系统里,就算看到O(n)也不能掉以轻心,应该想O(n)前面的那个常量是多少,才能评估出最准确的结果。

最后:一条路走到黑。大家会问大多数系统是“推拉结合”的吗?其实没有,大多数系统选择了只一条路走到天黑,为什么呢?因为实现两个系统的复杂度反而更高,还不如针对某一个做优化。所以大家可以看到在Facebook里面,其实对所有人用的都是“拉”模式,而Instagram对所有人用的是“推”模式,也运行很好。大家不用很纠结,两种模式都可以做的很好,只要针对它做很好的优化。这是一个经验,大家不要执着于方法的混合,往往一种单独方法就很好。

第一篇章到这里就结束了,在这里做一个小总结:

读写二兄弟,

推拉两姐妹,

选对一个人,

相爱到天黑。

下次深入探究如何在分布式的环境下把Twitter的架构做的更好。

推荐一些相关文章给大家:

赏个馒头吧