今天我们来聊一聊如何设计Twitter。


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


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


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


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

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

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


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

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

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

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

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


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


这个模式有什么缺点吗？

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


换成“拉”模式怎么样？

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


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

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

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

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


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

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

面试时，选择推还是选择拉呢？

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

第一：理解场景。比如像微信的后台架构，对于微信而言，群聊是“拉”模式好还是“推”模式好呢？必然是“推”模式好，为什么呢？因为群聊里最多是500人，所以说推的成本比较低，而“拉”模式会很复杂。而对于Twitter可以根据具体情况分析选择。
第二：延迟、计算、存储量之间做平衡。根据自己服务器的情况及当前的场景和未来的预估去做决定。
第三：O(n)不可行。在分布式系统中如果做算法，O(n)已经很低，但很多时候做分布式O(n)往往是不可行的。为什么呢？可能O(n)里面的每一个1都已经是很复杂的操作，比如每个1需要10毫秒，n是1万，那就是好几秒时间。所以当在分布式系统里，就算看到O(n)也不能掉以轻心，应该想O(n)前面的那个常量是多少，才能评估出最准确的结果。
最后：一条路走到黑。大家会问大多数系统是“推拉结合”的吗？其实没有，大多数系统选择了只一条路走到天黑，为什么呢？因为实现两个系统的复杂度反而更高，还不如针对某一个做优化。所以大家可以看到在Facebook里面，其实对所有人用的都是“拉”模式，而Instagram对所有人用的是“推”模式，也运行很好。大家不用很纠结，两种模式都可以做的很好，只要针对它做很好的优化。这是一个经验，大家不要执着于方法的混合，往往一种单独方法就很好。

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

读写二兄弟，
推拉两姐妹，
选对一个人，
相爱到天黑。

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

来源：顶级程序员