Twitter时间线和搜索功能架构简介

语言: CN / TW / HK

我们知道在Twitter中的时间线和搜索是两个很主要的功能,那么它背后的架构是怎样的呢?Twitter的架构师Raffi Krikorian在QCon 2012上有一个讲座提到了背后的实现,虽然时间较早,但当时的QPS也已经很大了,所以其实现的架构哪怕在今天仍然值得我们去学习。本文就从笔者理解的角度来聊聊Twitter是如何实现这两个功能的。

概述

首先我们知道Twitter最重要的功能就是你可以发布一些Twitter的消息,然后一些follow你的人可以及时看到你发布的消息。当然你也可以看到所有你follow的人发布的消息,我们把这个你可以看到所有follow人的消息的这个页面称之为时间线页面,它如下所示:

通常来说,它就是显示所有你follow的人发布的消息,并按照一个时间顺序来进行排序,当然现实中可能还会插入一些你没有follow人的发布的消息,或者一些推广之类的,这些特殊的内容不在本文讨论的范围之内。

Pull vs. Push

从技术的角度来讲,我们可以使用两种技术,一种是pull的技术,比如说这里我们时间线页面就可以使用pull的技术,我们会调用相应的API来获取我们需要显示的Twitter消息,再比如我们想要搜索一些twitter消息,它也是使用的pull的技术。另外一种是push技术,这个技术主要用在消息的通知,比如你follow的人发布了一个新的twitter,就可以通过push技术来通知你,这样你就可以及时得到消息。如下图所示。本文我们主要讨论时间线和查找的实现,所以会着重讨论pull技术的实现。

Capacity

理解了讨论的问题之后,我们来看看在2012年的时候Twitter的体量是怎样的?当时大概全球有1.5亿的用户量,时间线的QPS大概是300K,也就是30万/s的调用。Twitter当时的写的体量大概是4000/s这个级别,相比读的QPS要小很多,当然这个也是可以理解的。

很显然,这样的QPS之下我们不可能每次都去查询数据库,比如select数据库得到一条记录等等(不要笑,Twitter早期真的尝试过这种实现的,结果当然不work)。

Twitter的发布

在了解大概的capacity之后,我们从Twitter的写来看,就是当一条Twitter发布的时候它是怎么写的。它的主要架构如下所示:

当用户发布一条Twitter的时候,当然它会经过load balance,前端的server等,然后调用写的API,然后会经过一个称之为Fanout的组件,最终会写入到Redis的cluster中。

那么Fanout是干什么呢?它会通过Social Graph Service查询得到有哪些人是follow你的,有了这个信息之后,它就会遍历所有这些人的时间线(Redis上),然后把你新写的这条Twitter插入到他们的时间线上。

当然Redis本身也是有replica的,当时Twitter使用的是在不同数据中心上进行3个备份,基本可以做到高可靠性。所以在把消息插入到时间线的之后,还需要在各个replica之间进行replay。

在Redis中使用的其实是native list的结构进行存储数据的,它的数据结果如下所示:

主要包括一个Tweet ID,然后发布的用户User ID还有4bytes是用于存储一些别的内部使用的数据,比如retweet等等,不需要特别注意。

随着时间的推移,你在Redis上的时间线其实保存的内容就如下所示了,当你要显示时间线的时候,就可以直接查询得到结果了。

几个事情需要注意:

  1. 这里有一个大小限制,也就是每个Redis只保存800条记录,所以那时候你浏览800条记录之后,可能就没有更多了。这里其实就是一个trade off,在大小和用户场景之间的一个取舍,通常来讲800条已经蛮多了。有了这个限制之后我们就可以把所有的时间线数据都保存在Redis上,访问的速度就会很快。
  2. 另外一个优化就是假如你不是一个active user (30天没有登录),那么你的时间线数据不会保存在Redis上。

当然我们在发布Twitter的时候,肯定还是会把Twitter的数据写到的disk的,但是只会保存在发布者那边,不会在follow这边把任何数据写到disk。就像假如我们在Redis上没有数据的情况下,可以通过一个Gather的服务从所有的follow那边保存的数据库中读取相关的twitter ID,然后combine起来组成新的时间线,并保存到Redis上。

时间线的读取

相关的时间线的读取就很简单了,只要从Redis上找到你时间线所在的Redis,然后读取相关的时间线数据就可以了,如下图所示:

通过Timeline Service,找到保存数据的Redis,其实因为有replica的存在,其实会有三个可以读的备份,你可以选择速度最快的那个repica来进行读取,并最终组成时间线页面。

所以我们可以看到这个总得设计是在写的时候比较花时间,因为要把所有的follow的时间线都插入数据,但是在读的时候则很快,只要找到相关的数据,直接返回就可以了。

现实中,这个读取的API的速度大概在400ms左右,然后加入UI的rendering时间(没有cache的情况下)大概在2s左右,整个用户体验还是可以接收的。

当然你可能会问,这里从Redis得到的其实只是Twitter ID,是不是还要得到Twitter的内容啊,是的,在从Redis中得到Twitter ID后,你可以通过这个Twitter ID的数组得到相应的Twitter的内容,这个是别的服务负责的,他们也有一套自己的cache等策略来保证效率,本文就不做详细介绍了。

Twitter的Search

我们在前面也提到其实Twitter也是可以做查找的,那么查找这块是怎么做的呢?我们也还是从Twitter的发布来说起,它的总体的架构如下:

同样的写API,除了会往时间线那么进行插入数据,它还会向Ingester这边插入数据,这里的比较纯粹,不需要做额外的查询,就是一条记录进行一次处理就可以。Ingester其实就是做Tokenize等操作,然后Earlybird其实就是一个修改版本的lucene (保存在RAM)。和Fanout那边不同的是,一条Twitter你可能会保存在很多不同的Redis中(取决于有多少人follow你),而这里每条Twitter记录只需要保存在一个Earlybird中就可以了,当然也会做replica来distribute load的压力。

而对于Blender的读也就是查询来说就比较麻烦了,你需要搜索所有的index,看有没有你想要查询的数据,然后再进行merge,rank,最后再返回查询结果。

时间线和搜索设计的背后思想

我们可以看到时间线和搜索设计它背后的trade off是不同的,如下图所示:

对于时间线来说,写是一个o(n)的操作,我们要在所有的follow的时间线中都插入我发布的twitter。而读则是一个o(1)的数据,可以直接访问相应的Redis,快速得到数据。

而对于搜索来说则相反,写是一个O(1)的操作,做好tokenize,index,直接写入就可以了。但是读也就是查询的时候则是一个O(n)的操作,需要访问很多Earlybird,查找到相关的数据,merge, rank再返回。

这就是典型的根据使用场景来进行不同设计的例子。

Hot user处理

我们再回头看看上面的时间线架构,你会发现一个常见的问题,即Fanout很容易成为瓶颈,尤其是对一些名人而言,比如说Lady gaga,有3100万的人follow她(查了一下今天有83.9M的人follow,没有量级上的增长,哈哈),假如她发送一条Twitter,你需要修改3100万人的时间线,这个时间的消耗其实就蛮大了,而且也大大增加了Fanout的处理压力。

这个Fanout的延时的问题并不在于你在Lady gaga发送了一个Twitter之后多久你可以看到这个Twitter,比如说你在1分钟之后看到Lady gaga发送的twitter和你在30s之后就看到在现实中并没有什么特别大的问题。真正存在的问题是在于twitter的错序。

比如说你和小明互相follow了,然后你们两个都follow了Lady gaga,现在Lady gaga发送了一个Twitter,小明在Lady gaga发送之后10s就看到了这个twitter,因为Lady gaga有很多follow,所以你正好排在Fanout的比较后面。在小明看到这个Twitter之后,它感觉很有趣,就转发并评论了。这个时候你follow小明,而小明的follow列表人很少,所以你很快就看到这个转发和评论,而在之后Lada gaga发送的twitter才fanout到你,所以你会看到小明的转发评论竟然会在Lady gaga发送的前面,这种情况就会真正影响用户的体验了。

其实一个简单的解决方法就是在时间线上按照TwitterID来做一个排序,只要保证TwitterID是全局有序的就可以了。这样一来就可以轻松解决这个问题。网上有很多TwitterID全局有序的实现文章大家可以自行搜索查询。

但是这些hot user还是会大量使用fanout的资源,我们有没有什么好的办法来解决这个问题呢?Twitter做了一个新的尝试,就是把时间线和查询结合起来:

我们前面讲了,其实整个系统中有时间线和查询两套体系,那么对于这些hot user我们能否使用查询体系呢?

我们来看下面这个例子,假如raffi发布了一条Twitter: “Hello, world”,在Fanout这边其实就是插入一条记录,而在query那边其实就是有两个term hello和world,假如我们能标注它是raffi发送的twitter,那么我们就可以通过查询raffi发送的twitter来得到Hello world这条twitter了。

是不是茅塞顿开,所以对于这些hot user,比如lady gaga来说,我们不需要进行Fanout,对于那些Lady gaga的follower来说,在build他们的时间线的时候,先通过正常的时间线Redis得到一个列表,然后在通过查询Lady gaga发布的twitter来得到她的twitter信息,最终再把两者组合起来,就可以build一个完整的时间线了。

总结

本文就详细介绍了2012年时Twitter是如何实现时间线和查询两个功能的,主要介绍了整体的架构设计和一些trade off的考虑。

Post Views: 3