Real-Time Search In Twitter

Posted by CodingCat on March 27, 2015

这是一篇发表在ICDE 2012上的文章,讲的是twitter如何构建他们的实时搜索引擎[1]。在twitter这样的以文本为主的数据存储空间中进行搜索,很常见的场景就是用户给出一个关键字,搜索引擎根据内容的相关程度返回和这个关键字有关(可以是exactly包含这个关键字,也可以是包含相关联的关键字) 的tweets. 这种业务通常就是用所谓的inverted index 来做,那么这篇文章的中所描述的业务场景和传统的引擎有什么不同呢?

##Tweet编码##

最大的不同在于实时。既然是和的概念有关,所以对于返回结果的排序,更关注的是实效性而不是在传统索引中采用例如相关因子等参数。所以这篇文章关注的最多的就是如何基于时间对tweets进行排序。

一个简单的方法是,给某个tweets一个全局的ID,按照ID来排序,越大的ID表示越新;然后在遍历结果的时候我们按照逆向遍历。这是不可行的!:

  1. 大多数的索引为了节约存储空间不会去存储一个tweet的具体ID,而是去存储相邻tweet之间的压缩过的gap[2]; 对这种结构的逆向遍历是不能反映tweets在时序上的关系的.

  2. 如果你直接按id由大到小存储tweet,又会带来内存管理上的压力;长期下来,你每次都必须在每一个entry的头部插入新的item, 然后移动已经存在的item,或者你必须采用很好的算法去预估内存分配空间 (i.e. initCapacity); 如果你用链表去做,从cache局部性的角度来说又不是一个很好的方法

所以这个系统的设计精妙之处之一就在于把每一个tweets转化成了一个32-bits长度的整数;每一个整数的前24 bits用来表示tweet的id (虽然文章没有明确说24比特的id带来的问题,而只是讲系统容量的问题,但是我估计当超过这个范围,id会从0开始复用), 后8位去代表这个term在tweet中的位置。

因此Inverted Index就成了关键字索引一个整数数组,这样的一个存储结构虽然没有用各种压缩技术去节约空间,但是本质上带来了如下的好处

  1. 能够很方便的进行反向搜索,而不要针对特定的压缩方式来进行解压缩

  2. 从任何一个位置都可以进行反向搜索,因此可以支持更丰富的查询表达式,例如对某时间段的查询

  3. cache friendly (利用了数组的连续空间)

这个编码方式从本质上来说还是一个空间换时间的做法

##内存管理##

###Slice-Based 内存分配###

既然提到了数组,一个很直接的问题就是数组有多长? 在inverted index中,data skew的问题直接拒绝了我们用一个统一数组长度去分配内存空间的可能性: 你用文档中的关键字去索引文档,总会有一些词是很多文档都包含的,而一些词则仅仅属于一小部分文档, 所以如果你采用一个统一的长度,设置的过长自然浪费内存空间,如果过小,这就和LinkedList差不多了,你得用一个类似wrapper的数据结构把分配的小数组们串到一起,不是cache friendly的。

作者采用的方法其实和很多系统类似了,基于slice内存空间分配

服务器的内存空间被划分为4内存池(pool, pool 1 - pool 4), 每一个内存池中最多包含2^15个元素,当一个内存池满的情况下会分配另一个内存池。(4种!不是4个!)

每一个池又被进一步划分为slice, 4种池所对应的slice大小是不一样的,分别对应2^1, 2^4, 2^7, 2^11 个元素。每一个新遇到的关键字,首先在pool 1中申请一个大小为2个元素空间的slice,这两个被填满的时候在pool 2中申请一个16个元素空间的slice,一直到pool 4, 如果在pool 4申请的第一个slice被用掉,将继续申请在pool 4中的slice。

Slice Based Memory Allocation

具体可以看上图中,在不同pool中的不同slice是怎么串接到一起的

###利写与利读内存结构的转化###

在以上的分配算法的基础上,early bird其实在pool之上还有一层内存抽象,segment, 也就是说,多个pool组成了一个segment 并且在任意时刻,最多只有一个segment是可写的。那些从可写转化为只读的segment可以通过丢弃多分配的内存空间以及压缩技术进一步减少Memory Footprint.

##并发支持##

在上一个section中,early bird已经做到了所谓memory efficient, 那作为一个线上系统下一步就是如何支持并发的访问。

Early Bird在实现上支持了single writer, multiple readers.

首先我们定义一个tweet何时才叫被索引了: 当一个tweet中所有的关键字以及tweet本身都被成功添加到都被索引之后,我们就说这个tweet已经被索引了。后续一个动作就是去update一个代表一个服务器中一共有多少个tweet的变量,maxDoc.

现在我们再来看并发支持到底要解决什么问题(准确一些说是,在正确性方面要解决什么问题):

  1. 对于每一个关键字所索引的tweet的list (如上文所述,其实是串在一起的数组),他在各个线程之间必须维持一致的状态。比如这个list的尾指针必须是线程间一致的,否则添加tweet的时候一定会出错的;

  2. 不同的关键字所有的list所共享的状态,必须是线程间一致的; 例如当一个请求到达时,必须能在所有已经完成索引的所有tweets的范围内进行筛选

这两点都涉及到线程同步问题,简单的互斥锁固然可行,却牺牲了太多的性能;early bird采用了利用volatiile变量做memory barrier (内存屏障)的做法,i.e. 那个maxDoc是一个volatile变量,内存屏障的意思就是,在所有发生在update maxDoc之前的内存操作,和之后的操作之间竖起一道屏障;这道屏障起到的作用就是发生在update maxDoc之前的操作所产生的结果,对于之后的操作都是可见的.

回到上述的两个问题以及一个tweet何时才叫被索引的定义上,既然update maxDoc是索引一个tweet的最后一步,他自然的就是一个内存屏障;进一步,如果我们在刚开始查询一个tweet的时候就去读一下这个maxDoc, 那么writer thread已经完成的操作一定会被这个查询操作所看见 (注意,我们只有一个writer thread),从而保证了问题1, 2的解决。

这个利用volatile做memory barrier的做法和Akka 解决内存可见性的问题其实是一样的,我在写这篇总结的时候发现原文的分析思路和我当初分析Akka内存可见性实现的思路很相似,具体可以参看我上几个月的一篇博客(从Akka 内存可见性的实现看JVM Volatile机制)

[1] http://www.umiacs.umd.edu/~jimmylin/publications/Busch_etal_ICDE2012.pdf

[2] http://dl.acm.org/citation.cfm?id=1526764&dl=ACM&coll=DL&CFID=656394834&CFTOKEN=29851676