Google于2010年4月将一个新的增量索引架构Percolator部署到了websearch index上,并命名为Caffeine(咖啡因)。自己最近发现网上写的日志什么会很快的被Google索引到,而百度则要慢得多,因此特意去找了这篇paper的原文来仔细拜读了下。

Google的Percolator增量索引更新是针对在一个大的数据源中只有少部分被更新需要重新索引而设计的,并没有取代之前的Map/Reduce方式,即原来的索引更新是当增量的数据到达一定规模时,对repository进行MR重新建立索引并加入全局索引。而采用了新的Percolator系统后,每天处理和之前相同规模的文档,平均的生命周期缩短了50%(即从网页被爬取下来到处理,索引完成可以被搜索引擎搜索到的时间间隔)。

Percolator的架构图:

Percolator由Worker, Bigtable, GFS三部分组成,Percolator提供了一系列的observer关联在worker上,这些observer定义需要观察的data table中的columns,当该columns发生变化时,对应的observer会作为一个function call被worker process调用,Percolator的应用程序就是由一系列的observers组成的,每个observer。



Percolator是基于bigtable的操作进行封装的,大部分API也都采用了Bigtable的模式,简单的说就是通过给bigtable中的cell进行加锁来进行数据的更新和读写,在说明之前先看原文中Percolator操作table数据更新的实例,Table中有两个记录分别记录Bob和Joe的账户余额,现在需要将Bob账户中的9$转给Joe。

  1. 初始状态, bob有$10, Joe有$2,  5,6可以表示timestamp序列,bal:write中的data@5表示数据在第5时刻存放。                  initial
  2. 事务开始,Percolator的事务采用的两段式提交,在第一段Per-write阶段,首先给Bob的bal:lock写操作进行加锁,锁的标志是primary。同时写入更新后的数字。
  3. 接着事务锁定Joe的数据行,并写入更新后的数据。此时的锁是一个辅助锁,在lock列写入的记录指向此次事务更新的primary锁,每一个事务都只有一个primary lock,其他lock的都指向primary,这样是用于操作crash时的清理操作。                        
  4. 现在到达第二阶段Commit,是在write列写上数据的位置,类似指针。首先将bob的primary lock用一个在write列的写操作替换掉,即8: data@7,指向新数据。
  5. 最后通过给Joe的write列写入新的记录指向数据的timestamp 7并移除掉non-primary lock,完成整个事务操作。                                                          

整个过程是两段式提交,第一阶段 ,对于所有的记录加锁并更新数值,只不过每个事务有一个primary lock,剩下的lock都记录指向primary lock的指针,这样当操作在过程中crash掉以后,可以根据primary lock是否已经被commit来决定是进行roll forward还是roll back,即如果primary lock不存在,说明前面的事务已经将记录已经提交,其他的非primary记录就roll forward,否则就全部roll back并清理锁。

下面看看文章中的代码是如何进行操作的,首先系统需要oracle server来分发timestamp,并且要保证分发的timestamp是严格递增的。

事务的定义:

Write被封装为一个row,col,value的结构体,函数操作此结构。在事务初始化时候首先请求事务开始的时间戳start_ts_。写操作只是简单的将值写入vector即可。

读操作:

读操作首先检查从时间戳区间[0,start_ts_]上的锁,如果锁存在(pending lock),说明有并发的事务操作。或者可能之前事务失败导致锁依然存在需要clean。clean的操作就是根据查找该lock对应事务的primary lock来判断是进行roll forward/roll back。

没有冲突的锁的话就直接查找write列上从[0,start_ts_]的的数据,如果存在就是最后一次data的timestamp,然后到data列读取对应的data值。

预提交:

写操作首先检查是否在write列比start_ts_更新的timestamp数据,如果有就出现写写冲突,返回失败;或者发现任意时刻的lock,则有可能是另外的事务准备释放lock,但已经在start_ts_之前进行了commit,因此也返回失败。

否则就进行数据的更新,以及锁标志的写入,并指明是primary lock的位置。

事务提交:

前半部分是priwrite调用,给primary以及non-primary写data和lock

如果没有表中某单元存在冲突,事务进入第二段提交。

从timestamp server取得当前timestamp,然后从53~57行进行primary lock的提交,首先确认lock列的锁是否写成功并还存在,然后进行在write列写入record并指向start_ts_的timestamp,即数据更新的timestamp,并擦去lock列的记录。write列保存的是一个timestamp以使得client可以在data列可以找到真实数据。

对primary进行commit完成后,对non-primary的记录进行write record和lock的earse。

事务完成。

失效的检测:

虽然根据primary lock的状态,client可以选择对事务进行roll forward/roll back并使得数据一致。但rollback操作会造成性能的损失,因此应该避免过多的rollback,事务只有确认了一个lock属于一个dead/stuck worker的情况下才clean lock。worker的存活状态采用Chubby锁服务,各个worker定期的写token通知Chubby Server来确定自己依然在工作状态,其他client可以根据token的存在来确定lock所属的worker是否dead。并且为了仍然存活却阻塞不工作的worker,同样也会在lock中写入时间,一个lock如果包含的时间是很久以前的也会被clean,因此在一个commit操作较长的操作中,worker需要周期性的更新lock中的时间信息。

Notifications:

之前说到Percolator的应用程序是由一系列的Observer组成的,而每一个Observer可能会定义自己关心的table cell,当该cell中的内容更改后,Percolator会自动调用这些Observer。Notifications机制类似于数据库中的trigger,每一个Observer完成操作后可能会创建新任务给下游的Observer,从而执行完整个应用。

为了辨认那些被修改了的table cell(dirty cell),Percolator维持了一个特殊的”notify” Bigtable列,该列包含了每一个”diry cell”的entry,当 一个事务修改了一个被观测的cell,同时也会设置对应的notify cell,而当对应的observer执行完成后,notify cell也将会被移除。

为了使得dirty cell的扫描更加高效,Percolator将notify column本地存储在一个单独的Bigtable中,并且采用多线程对整个column进行扫描,这里每一个线程随机选择表中的一个key开始进行扫描,为了避免两个线程扫描到同一区域,当每一个worker在扫描之前会从一个轻量级锁服务中取得锁避免冲突。另外一个随机扫描的问题就是如果一个线程扫描位置在另外一个线程之后,则会导致clump together问题,论文中很形象的用了公交车来比喻这个现象,即如果前面的公交车因为路况,车站等待上车人数过多而导致速度很慢,速度很慢又会导致下一个车站上车人数变多,使得问题更加慢,因此后面的车最后会赶上前面的车。为了避免此问题使得并行效率降低,当一个扫描线程发现它扫描到另外一个线程正在扫描的row时,就随机选择table中的另外一个位置开始扫描。

最后通过Google的测试,通过每小时更新的个数占整个repository的比重有如下对比,当更新频度不是很高的时候,Percolator的文档延迟速度远远低于Map/Reduce。

大家有兴趣的可以在自己的blog上写一篇文章,试验下看最新的这篇文章何时能被Google索引到,同时看看百度的差距时间,当然这个时间会由于你网页的PR值,更新频率的不同,Crawler会抓取间隔不同。主要大家可以对比下两个搜索引擎索引到的时间差,我自己由于更新不频繁,Google现在貌似一天,百度貌似还要慢两天左右。

参考:

《Large-scale Incremental Processing Using Distributed Transactions and Notifications》 ,Daniel Peng,  Frank Dabek, 原论文

Percolator-Slide , 在osdi上的PPT, Google Docs,你懂得

转载请注明来源:Leoncom-《Google Percolator增量索引系统》
,
Trackback

3 comments untill now

  1. 不错!
    刚接触Percolator,多交流!

  2. 写得很不错。赞一个。

  3. Working late is often the product of your laziness and unproductiveness during the day, which results in you needing to work your
    ass off late at night just to reach your deadline.
    Use this advice to help you decide what to change in your marketing campaign.

    Article Source: to understand more about Online business.

Add your comment now