Percolator与分布式事务思考（一）

Percolator严格说来是google一个处理增量网页索引的系统，可以认为其内部mapreduce系统的一个增量版本，同时提供了强一致更新不同机器中索引信息的机制。论文原文可以在http://research.google.com/pubs/pub36726.html 这个链接中找到。

这篇论文我做了下翻译，这里主要tips下我比较关注的如何保证更新不同机器上数据时的ACID。

Percolator被构建出来纯粹是为了增量数据的处理,它并不打算取代现有的对多数数据处理的方案.那些不能被分解为一些小的更新的计算(比如一个文件的排序)更适合用MapReduce来处理.同时,除非计算需要强一致性,否则,BigTable就足够了.最后,那些需要某些维度跨度非常大的计算(全数据长度,CPU密集型变更,等等)或者一些不适合用MapReduce或者BigTable来计算的小规模计算用传统的DBMS解决即可.

Percolator为大规模增量数据处理提供了2个主要的抽象:为随机访问数据仓库的操作提供ACID事务和观察者,一个构建增量计算的途径。



一个Percolator系统由3个二进制包组成，他们跑在集群中的每个机器中;一个Percolator worker,一个BigTable的tablet服务器，还有一个GFS的chunkserver.所有观察者关联到percolator的worker上，观察者们通过发送读写RPC请求到Bigtable tablet服务器，然后（由tablet服务器）发送读写PRC请求到GFS chunkservers来实现事务。系统同时依赖2个小的服务：时间戳预报服务和轻量级锁服务。时间戳预报服务提供精准的递增时间戳：这是快照隔离协议正确执行的必要属性。Workers使用轻量锁服务让对脏通知的搜索(the search for notifications)更加高效.

需求直接影响了Percolator的设计，这些需求包括需要运行在大规模并且不需要异常严格的延迟的环境中。宽松的延迟需求可以让系统做诸如以下的事情，系统可以在事务运行失败的机器上延迟地清空锁。这种延迟，可以简单到让事务提交延迟几十秒。这种延迟是DBMS运行OLTP任务是所不能容忍的，但是在一个用于建立web页面索引的增量处理系统中是能够容忍的（译者：网页索引更新延迟几十秒已经算实时的范畴了，相对于传统1天或者几天通过mapreduce来全量构建索引好得多）。Percolator没有事务管理的中心节点；特别是，它缺乏一个全局的死锁检测器。这个增大了冲突事务的延迟但是却使系统能够扩展到成千上万台机器。

Percolator建立在BigTable上。BigTable提供了一个多维度并且排序的map给用户：keys是（row,column,timestamp）元组。BigTable 提供了在每一行上进行查找和更新的操作，并且BigTable行事务允许在独立的行上进行原子的read-modify-write操作。

构建在BigTable上的这个决定已经定义了Percolator整体形状。Percolator维持了BigTable接口的风格：数据被组织成了BigTable的rows和columns，并且Percolator的metadata(元数据)单独的存放在特殊columns中.Percolator的API酷似BigTable的API：Percolator library大部分由存在于Percolator计算框架内的BigTable操作组成。实现Percolator即需要提供BigTable所没有的特性：多行事务和观察者框架。




Percolator提供了跨行，跨表事务，这些事务具有ACID 快照隔离语义。Percolator用户使用一种语言（现在是C++）写事务代码并且在他们的代码中混合调用Percolator的API. 上图Figure 2 显示了一个通过一个文本内容hash得到的简单集群文档的版本。在这个例子中，如果Commit()返回false,这个事务就冲突了（在这种情况下，得到2个URL下相同内容hash后将同时被处理）并且必须在一个回退后重试。调用Get()和Commit() 被阻塞；并行处理是通过一个线程池中同时运行许多事务达成。

Percolator存储着每一个数据的多个版本，使用了BigTable的时间戳维度。多版本被用来实现快照隔离，这种机制让每一个事务从某一个时间戳的稳定数据快照中读取数据。写出现在一个不同的，更后面的时间戳中。快照隔离保护了 写-写 冲突：如果事务A和B并发执行，并且写同一个cell（译者：实际上可以理解为数据库行），那么最多有一个会commit.快照隔离不提供串行化；特别是，事务运行在一个向写倾斜的快照隔离上(写多读少)。一个串行化协议的快照隔离主要优势在于更加高效的读。因为任何时间戳代表一个一致的快照，读取一个cell只需要进行一个给定时间戳的BigTable查询即可；获取锁是不必要的。上图Figure3 演示了在快照隔离下的事务之间的关系。

因为Percolator被构建成了一个客户端代码包去访问BigTable,而不是控制对存储本身的访问(Server模式)，Percolator面临着一系列与传统PRDBMSs所不同的挑战来实现分布式事务。其他并行数据库将锁集成到系统组件以管理对磁盘的访问。

相比之下，在Percolator中的任何节点能够让请求直接修改BigTable的状态；因为没有一个环节阻止这种行为或者进行锁分配。这样，Percolator必须明确的维持锁。锁必须在面对机器失效时也要持久；如果一个锁在两个阶段的commit之间丢失，那么系统可能错误地提交2个事务并且这两个事务可能是冲突的（译者：这里我理解为更新顺序出现问题，也就是两个事务的数据交叉覆盖）。锁服务需要提供高吞吐量；成千上万台机器将会同时请求锁。锁服务需要低延迟；每个Get()操作除了读取数据之外还需要读取锁。有了这些需求后，这个锁服务器需要复制(在硬件失败中存活)，分布式并且是负载均衡的(处理load),并且写到持久数据存储中。BigTable本身满足所有我们提出的需求，所以Percolator把它的锁存储在BigTable的一个特别的内存columns中，这个BigTable同时存储数据，当访问一行数据时同时更新BigTable行事务锁。