Real-time Search in Twitter (2)

上一篇中谈到了,Twitter是如何优化posting list。它没有使用Delta encoding和Vint,使得一个int结构就能够完整的保存一个docId和position信息,且实现了索引能够从new向old的方向进行遍历。

这篇完整的说清楚整个Inverted Index的结构。

Inverted Index

image  图(1)

图(1)是一个逻辑上的倒排索引的结构。它包括一个Term Directory,其中的每个term有对应有一个posting list,保存了该term所出现过的document Id和所在的position。

早期的Lucene,对于每个term有一个数据结构,如下图:

image

但这样的问题是,会产生大量的long-live object,导致GC变慢。于是,Lucene使用parallel posting arrays替代了这个数据结构,如下图:

image

对于每个term,有一个hash table能够查到term id,然后,在对应的array中,用过term id作为下表,可以查到该term的frequency,以及posting list的指针。于是,整个倒排索引就变成了:

image 图(2)

这么修改的好处就是“avoid having very many long-living PostingList objects”(Lucene-2329)

再说说posting list storage。整个storage由4个int[] pools构成,每个pool由一个个32k的int[]块组成:

image

每个pool会被切成一个个的slice,区别在于slices的size是不同的(大部分内存池都是这样的做法,也没什么太新鲜的)

image

对于一个term的posting list,它首先在最小的slice pool上回分配一个slice,当这个slice被占满后,就到上一级的pool中分配一个新的slice,依次类推。所以在前三个pool中,一个term的posting list最多只有一个slice,如下图:

image

最终,倒排索引变成了图(3)的形式:

image 图(3)

这样的设计同样是为了
1. 减少java object的数量,避免过慢的GC。”The number of java objects should be independent of the number of lists or number of items in the lists”;
2. 实现索引从new到old数据的遍历(上图中的红线);

图(1) –> 图(2) –> 图(3),整个过程中一些设计上的tricky还是很有意思的。

— Continue. —

Advertisements
相册 | 此条目发表在Analyzing Big Data with Twitter, Lucene分类目录,贴了, , 标签。将固定链接加入收藏夹。

One Response to Real-time Search in Twitter (2)

  1. Pingback引用通告: Real-time Search in Twitter (3) | Great Power Law

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s