Real-time Search in Twitter (1)

Twitter搜索相关的一组数据:
360 millions tweets per Day
Indexing latency < 10s
    2.2 Billion queries per day
50 ms Average Query Response Time

Twitter搜索的核心需求就是实时性。在这种级别数据流的情况下,将索引放到内存中基本就是唯一的解决方案了。

image

基本架构实在是没有什么特殊之处。几乎所有的网站都是这么干的。用户的数据写到MySQL中,然后搜索引擎周期性的从数据库中“拉”数据并更新索引。

Twitter搜索的目前版本改版自Lucene。后续可以看到,它对Lucene的一些底层设计做了针对性的修改,很值得品味。

Inverted Index

Lucene(特别是3.*版本)默认的实现中有两个特别的设计:Delta encoding 和 Vint

image

这两个设计本来的目的都是为了压缩数据,减少index的尺寸。实际中,也确实能够有效的降低index的size。

但对于Twitter来说,这两处设计都有问题:

Delta encoding会导致索引只能够从old数据开始向new数据方向读取,因为后面数据的值必须通过前一个数据的值 + delta值计算得到;

Each posting depends on previous one; decoding only possible in old-to-new direction

Vint的设计,使得int不再是原生的java type,没办法原子性的写入;

a VInt-encoded posting can not be written as a primitive Java type; therefore it can not be written atomically

为了解决这两个问题,看看Twitter是怎么改的:

image

前面的两个设计它都抛弃了。取而代之的是用一个完整的int值来同时保存docID和position信息。这里有个很讨巧的地方,是Tweet只有140个字符,所以8位的position就够用了……前面的24位保存docID,最大的ID就只能是2^24,所以一个Segment最多存储2^24这么多tweet(2^24大概是Twitter半个小时的量);

这样的设计解决了前面的2个问题:
首先,int值是可以做原子操作的;
其次,索引读取的方向可以从new向old读取了;

image

我个人认为这个设计还是很漂亮的。

— Continue. —

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

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

  1. Pingback引用通告: Real-time Search in Twitter (2) | 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