Google实时索引系统原理和实现

Google实时索引系统原理和实现

1、实时索引原理
人们对实时搜索的要求越来越高，恨不得搜索引擎的索引能够和互联网的整个资源都同步起来。稍微懂一些的搜索技术的人们，就知道实时搜索的挑战还是挺大的。本文主要探讨Google在资源已经抓取后，在索引环节如何做到实时的问题。
如果索引量非常小，每隔一段短时间，就全部重建一次索引，用户感觉到的延时就很短，并会觉得这就是实时索引。可惜，这个前提在现在海量信息的环境下，是不成立的。实时索引技术难点，很自然能够想到关键就在于如何设计增量索引结构。
传 统的解决方案是将索引分为很多层，其中一些会以较快的速度（如分钟级/小时级/天级）更新，而主要内容层则会更长时间（如天级）才更新一次。索引节点本身 是更新了，但少量网页变化和增加对应的其他网页属性变化却不能完整地体现到全网的资源上，而这些对检索时效性又是至关重要的。因此，传统解决方案是差强人 意的（不能单独地处理一些小的更新）。
Google的以前的索引系统也是这种传统机制，并使用MapReduce方式实现。在计算资源足够的情况下，MapReduce的可扩展性使得这种方式也是可行的。
实 时索引理想的模型应该是把数据处理系统优化成增量性的处理。也就是说系统允许我们维护一个海量的网页索引库，当有新的网页被抓取下来的时候能够有效地去更 新索引库。鉴于该系统要并发的处理很多小的变更，这个理想模型就需要提供这样一种机制，尽管有新的变更，但要保持原来已经处理过的索引。
Google 新的索引系统Caffeine（咖啡因）是一个很好的实时搜索的解决方案。Google构建了一个Percolator（过滤器）系统，这个系统可以增量 式的处理一个大数据集的更新，并通过部署这个系统创建Google网页搜索索引。使用这个增量型的过滤器系统替代原来的批处理索引系统，每天处理相同数量 的文档，能在搜索结果中将文档平均年龄减少50%。该系统还可以把网页渲染成图片的形式。Percolator还可以追踪网页和它以来的源头之间的关系， 所以一个网页依赖的任何一个源改变的时候，这个网页就会被重新处理。
Google的这个增量处理模型中过滤器Percolator使用户可以随机 访问海量索引文档库，允许我们可以单独的处理某个文档，而不需要MapReduce去扫描整个索引库。为了实现高吞吐率，很多分布在不同服务器上的线程需 要并发的更新索引库，所以Percolator通过“快照隔离”实现了一种符合ACID的跨行跨表的事务处理机制，使得程序员可以更容易的获得索引库的状 态。除了需要获知并发状态，增量系统的程序员需要追踪计算过程中所处的状态。为了实现这一目标，Percolator提供了一系列观察者 （observers）：当用户指定的某列发生改变的时候，这些观察者会被系统触发。Percolator应用程序就是由一列的观察者串成链组成的。每一 个观察者完成一个任务然后创建更多的任务给它下线的观察者（观察者链式关系）。一个外部的操作将会通过往表里写初始数据这一动作触发观察者链中的第一个环 节。
当然，Percolator是专门针对增量性数据处理的，而不是取代已经存在的海量数据处理方案。对于不能被分割的计算，MapReduce 已经提供的更好的支持。其次，这个增量计算应该有很强的数据一致性要求，否则采用Bigtable就足够了。最后，Percolator更适合于在高一致 性及在数据量和CPU等方面有很高要求的计算任务，如果是过小的计算在DBMS中就好了，不适合MapReduce或者Bigtable。

2、Percolator设计
Percolator为了实现大规模数据的增量处理抽象出了两种基本的操作：一个是随机访问索引库时的ACID事务处理。另一个是观察者，一种组织增量计算的方式。

Percolator详细的架构图如下：

一 个Percolator系统由3个组件构成：一个Percolator worker，一个Bigtable tablet 服务器，和一个GFS chunkserver。这些组件运行在cluster中的每个机器上。所有的观察者都链接到Percolator worker上，这个worker会扫描bigtable里改变的列并且在这个worker处理中以函数调用的方式来触发相应的观察者 （notifications）。观察者通过发送读写RPCs到bigtable tablet servers，bigtable tablet servers又会转而发送读写RPCs到GFS chunkservers。这个系统还依赖于两个小的服务：时间戳发生器（timestmp oracle）和轻量级的锁服务。时间戳发生器提供了一个严格的方式增加时间戳，这是正确使用快照隔离协议所需要的属性。轻量级的锁服务可以更高效的搜索 最新的变更发出的通知（notifications）。
 从一个程序员的角度来看，一个Percolator索引库是由一些表构成的，这些表是很多由行和列索引的小单元构成。每个小单元的值都是由一个无结构的字节流组成。（在内部，为了支持快照隔离，我们把每个小单元都展示为通过时间戳索引过的值）
Percolator 的设计需要满足运行在海量索引库之上这个需求，对于极低的处理时延这个需求就比较宽松了。比如说，这种宽限的时延需求使得我们可以用一种懒（lazy）的 方式去清除事务处理失败的机器所留下来的锁。这种延迟处理的方式比较容易去实现，也因此在事务提交时造成了数十秒的延迟。这种延迟在DBMS处理OLTP 任务的时候是不可接受的。但是在增量系统里构建网页索引这个应用中是可以接受的。Percolator没有提供用于事务管理的中心服务器。也没有全局的死 锁检测器。这一点又增加了冲突事务的处理时延，但是却使得Percolator可以扩展到成千上万的机器中。（懒处理的方式和缺乏全局死锁检测的方式，确 实增大了事务处理时延，但是这点时间起MapReduce重新构建索引库的时间实在不算什么，如果真有全局检测机制，那对系统的扩大将是个很大的难题）
Percolator是基于Bigtable的操作进行封装的，大部分API也都采用了Bigtable的模式，简单的说就是通过给Bigtable中的cell进行加锁来进行数据的更新和读写。

3、参考文章
《》 ，Daniel Peng,  Frank Dabek, 原论文
《》在osdi上的PPT, Google Docs