【转】经典论文翻译导读之《Large-scale Incremental Processing Using Distributed Transactions a

【译者导读】

Percolator号称其取代MapReduce之后，Google的索引更新速度提升了100倍。它究竟是如何实现 “100” 这个刺眼的数字？当今的并行计算世界真的有如此大的提升空间吗？当我们满心欢喜以为又有新的算法、新的并行计算架构可以学习时，她却又为何跟你聊起了分布式事务？这篇文章将为您揭晓。

摘要

在搜索引擎系统中，文档被抓取后需要更新web索引，新的文档会持续到达，这就意味着包含大量已存在索引的存储库需要不断变化。现实中有很多这样的数据处理任务，都是因为一些很小的、独立的变化导致一个大型仓库的转变。这种类型的任务的性能往往受制于已存在设施的容量。数据库能够很好的处理这种任务，但是它不会用在如此大规模的数据上：Google的索引系统存储了十几个PB的数据，并且每天在几千台机器上处理数十亿次更新。MapReduce（后文简称MR）和其他批处理系统是为了大型批处理任务的效率而量身定制的，并不适合单独的处理小的更新。
所以我们创建了Percolator，一个在大型数据集合上增量处理更新的系统，并且已经部署上线用于构建Google的web搜索索引。通过将基于批处理的索引系统替换为Percolator，我们每天处理文档的数量相同，而搜索结果的年龄却减少了50%（比如本篇文章在今天中午12点发布，在Google上能在下午一点被搜索到，那年龄就是1个小时）。

1. 介绍

在web索引系统中，系统开始会抓取互联网上的每一个页面，处理它们，同时在索引上维护一系列的不变量。比如，如果在多个URL下抓取到了相同的内容，只需要将PageRank最高的URL添加到索引中。每个外部链接也会被反向处理，让其锚文本附加到链接指向的页面上（链接中的锚文本往往能比较准确的评估其指向页面的内容）。链接反向处理还要考虑复制品（意指内容相同的多个页面）：在必要的情况下指向一个复制品的链接应该被指向最高PageRank的页面（这样能增强最高PageRank的页面的评估）。
上述任务能够被表达为一系列的MR操作：一个用于页面聚类分析，一个用于链接反向处理，等等。在MR任务中维护不变量很简单，因为它是组织型计算（计算是按照一定逻辑和安排执行的，该并行的地方并行，该有序的地方有序），限制了计算的并行；所有文档都是按照步骤依次完成一个个阶段的处理。比如，当索引系统正附加锚文本到当前最高PageRank的URL时，我们不需要担心它的PageRank会并发改变：之前的MR步骤已经完成了PageRank的计算，确定了它的PageRank。

现在考虑一下，在只重新抓取了一小部分文档时如何处理。对于MR来说，仅仅对新抓取的页面执行作业是不够的，比如新来页面和已存在的老页面之间可能会有链接关系。MR必须在整个库之上再次运行，也就是说，既包括新页面也包括所有老页面。如果提供足够的计算资源，加上MR的可扩展性，这个途径确实是可行的，而且事实上，在Percolator问世前，Google的索引制造一直都是按这种方式。然而，对整个库再处理的做法丢弃了之前的工作成果，延迟随着整个库的增长而成比例增长，而不是这一次更新的量。

【译者注】MR之所以不能有效重复利用上一次的工作成果，其中一个原因是索引制造的计算不是“mergable computation”。mergable用数学公式表达就是：在mergable函数y=f(x)中，对于x中任意的子集x1和x2，此公式可以表示为 y=l(m(x1),n(x2))。也就是说x中的数据无论怎么切分，都可以逐一基于上一次的结果进行计算。

译者找到另一篇incoop的论文，它用MR的视角来诠释了传统的MR为何不适合增量计算：

?

?

?

如图所示，假设First run中Reduce的结果为A，在第二次计算时(2)出现了，要为它执行增量计算，能不能直接将(2)的值与A进行计算得到新的结果？答案是不一定。假如这个MR仅仅是对1到23各个数据进行求和，那就可以直接将A+(2)得到新的值（这就是mergable computation）。假如不是mergable（比如是将1、2、3、5的和与6到23的和相除），不仅1、2、3、5要重新计算，6到23都需要重新计算（因为MR仅仅保存了最终Reduce结果，丢失了中间计算结果）。这就是为何Google要重复的执行全量的MR。对于此问题，译者曾发邮件给作者Daniel Peng，他的回复是：

There are partial results of the index computation that are needed in the next incremental step.? In the mapreduce case, it is not easy to save and retrieve these partial results.? In percolator, it’s easy to store these partial results and retrieve them for the next time they are needed.

邮件中可以看到两个关键性词语。第一个是“partial results”，它强调了在索引计算中需要的不仅是上一轮的最终结果，更需要局部的、中间的计算结果，从某种意义上可以简单的理解为计算是unmergable的；第二个是“not easy to save and retrieve”，这个突出了MR的软肋，如图中那么多中间结果，哪些需要保存、如何保存、如何检索等等，这些都是MR没有考虑过的事情。与其花费很大精力去弥补此软肋，还不如有的放矢，针对新的场景重新设计一套架构，这就是Percolator选择的方案（但是在另一篇incoop的论文中，incoop的作者将MR优化改造成了能保存、检索中间结果的增量型计算架构，同样解决了问题，孰优孰劣，这里就不过多讨论了）。

索引系统理论上可以将数据存储在一个DBMS，就可以轻易实现只为单独的文档执行更新，而且可以使用事务来维护不变量。然而，当今的DBMS不能处理数量如此庞大的数据：Google的索引系统使用几千台机器存储了10PB的数据。像BigTable这样的分布式存储系统可以扩展到我们需要的容量，但是在面对高并发更新时不能很好的帮助开发者维护不变量。

理想的处理系统是为增量处理优化定制的；它应该允许我们维护一个非常大型的文档库，并且当每一个新文档被抓取时高效率的更新。它可以高并发的处理很多小的更新，而且要为并发更新维护不变量。

论文下面的部分描述了这样一个特殊的增量处理系统：Percolator。Percolator提供在PB级别存储库中随机访问的能力。随机访问允许我们单独的处理文档，避免全局的扫描(未优化的MR往往需要全局扫描)。为了达到高吞吐量，它允许大量机器上的很多线程并发的对存储库执行更新，所以Percolator为开发者提供了遵循ACID的事务机制；我们目前是通过快照隔离语义来实现。

为了解决并发问题，增量系统的开发者需要持续跟踪增量计算的状态。Percolator提供观察者来帮助实现此任务：每当一个用户指定的列发生变化时系统将调用的一段代码逻辑。Percolator应用的结构其实就是一系列的观察者；每个观察者完成一个任务并通过对table进行写操作，为“下游”的观察者创建更多的工作。一个外部的处理会将初始数据写入table，以触发链路中的第一个观察者。

Percolator为增量处理量身定制，而且并不希望代替已存在的大多数数据处理任务的解决方案。如果结果不能被分解为小而多更新（比如文件排序），最好用MR。另外，一致性很强的场景下才需要使用Percolator：否则Bigtable就足够了。最后计算也要非常庞大：计算很小不需要用到MR或Bigtable的情况下，DBMS就足够了。

在Google，Percolator的主要应用是实时构建web搜索索引。索引系统使用Percolator之后，我们能在文件被抓取时就单独的处理它。这几乎减少了100倍的平均文档处理延迟，而且搜索结果中文档的平均年龄也降低了50%（除了索引构建耗时，搜索结果的年龄还包含文档从改变到被抓取之间的时间）。此系统也被用来将页面渲染为图片：Percolator跟踪web页面和它们依赖的资源之间的关系，所以当任何依赖的资源改变时页面也能够被再处理。

2. 设计

Percolator为执行大规模增量处理提供了两个主要抽象：在随机访问库和观察者模式之上的ACID事务机制、增量计算过程的组织方法。

Percolator系统中集群的每台机器包含三个执行文件：一个Percolator的worker，一个Bigtable的tablet服务器，和一个GFS的chunkserver（每台机器都同时扮演三种角色，而不是严格划分三个layer各自负责一种角色）。所有的观察者都在Percolator的worker中，worker扫描Bigtable中发生改变的列（“通知”）并且就像本地方法调用一样调用对应的观察者的处理逻辑。观察者通过发送读写RPC请求到Bigtable的tablet服务器来执行事务（可能发送到任意一台机器的tablet服务器），后者接着发送读写RPC请求到GFS的chunkserver。系统也依赖两个小服务：时间戳oracle服务（原文为timestamp oracle，下文中所有“时间戳oracle”、“oracle”都是指此服务，译者注）和轻量锁服务。时间戳oracle提供了严格的递增时间戳：快照隔离协议需要依赖此属性。Worker需要使用轻量锁服务来更加高效的搜索“脏”通知（“脏”原文dirty，意指某个数据发生了改变，等待后续处理，后续“脏”都为此含义，译者注）。
从开发者视角，一个Percolator库包含少量的table。每个table是“cell”的集合（某一行的某一列就是一个cell）。每个cell包含一个值，某类cell为支持快照隔离，会包含按时间戳索引的一系列的值。

有两个前提影响着Percolator设计，一是必须运行在大规模数据上，二是并不要求非常低的延迟。不严格的延迟要求让我们采用了一个懒惰的途径来清理故障机器上被事务遗留下的锁。这个途径虽懒惰但实现很简单，不过它可能会导致事务延缓提交几十秒钟。这个延缓在DBMS运行OLTP任务时是无法接受的，但是在增量处理系统创建web索引时可以忍受。另外，Percolator的事务管理缺乏一个中央总控：尤其是它缺少一个全局死锁检测器。这增加了事务冲突时的延迟，但是却可以帮助系统伸缩至几千台机器。

2.1 Bigtable概览

Percolator建立在Bigtable分布式存储系统之上。Bigtable对用户呈现了一个多维度排序的map：map的keys是指（行、列、时间戳）元组。Bigtable为每个行提供查询和更新操作，而且Bigtable的行事务能够支持单行的原子“读-修改-写”操作。Bigtable处理PB级别数据，能够可靠地运行在大数量的（不可靠）机器上。

一个运行中的Bigtable包含一批tablet服务器，每个负责服务多个tablet（key空间内连续的域）。一个master负责协调控制各tablet服务器的操作，比如指示它们装载或卸载tablet。一个tablet在Google SSTable上被存储为一系列只读的文件。SSTable被存储在GFS；Bigtable依靠GFS来保护数据以防磁盘故障。Bigtable允许用户控制table的执行特征，比如将一批列分配为一个locality group。locality group中的列被存储在独立隔离的SSTable集合中，在其他列不需要被扫描时可以有效降低扫描成本。

基于Bigtable来构建Percolator，也就大概确定了Percolator的架构样式。Percolator充分利用了Bigtable的接口：数据被组织到Bigtable行和列中，Percolator会将元数据存储在旁边特殊的列中（见图5）。Percolator的API和Bigtable的API也很相似：Percolator中大量API就是在特定的计算中封装了对Bigtable的操作。实现Percolator的挑战就是提供Bigtable没有的功能：多行事务和观察者框架。

?

?

【译者预读】下面作者将介绍Percolator最核心的事务机制和通知机制，然而附图较少，陈述性的语言太多，尤其是事务部分的文字非常晦涩，还要结合源代码仔细阅读，不太适合读者快速的接收信息。所以译者附上译者YY环节，无论是否准确，相信能帮助读者快速的接收信息，了解其大概全貌，继而再结合原文探究其细节。

下面附YY图一张：

?

?

?

图中描述了在一台Percolator的机器上有两个部分：Percolator Worker和Bigtable（GFS对大家来说是透明的、封装的，暂不考虑）。Bigtable的职责无需多说，就是结构化存储，需要注意的是Percolator对它的使用。对任何一种data（比如PageRank值），Percolator为它分配一张表，表中C:data列存储的才是真实的data，其他的列全是为了服务于某种机制而附加上去的“元数据列”。C:data、C:write、C:lock是和数据读写有关的列，用于事务机制；而C:notify和C:ack_xxx只用于通知机制。各列中，

notify列仅仅是一个hint值（可能是个bool值），表示是否需要触发通知。

ack列是一个简单的时间戳值，表示最近执行通知的观察者的开始时间。

data列是KV结构，key是时间戳，value是真实数据，包含多个entry。

write列包含的是写记录，也是KV结构，key是时间戳，value是各个时间戳下曾经写入的值。

lock列也是KV结构，key是时间戳，value是锁的内容。

另一方面，Percolator Worker由两部分组成，一是用于扫描的线程池，二是开发者编写的观察者（observer）。下面按照图中序号大致描述一下Percolator中的流程：

step 1： 由于某逻辑（此逻辑可以是Percolator之外的第一个往Percolator写入数据的初始化输入，也可以是中间过程里某个观察者逻辑往表中写入了数据，对应step 6），需要往Bigtable的C:data列中写入新的数据，而且可能是多个逻辑并发的写，此时可能会遇到“写/写冲突”，需要巧妙的利用write列和lock列，并利用它们KV结构中的时间戳帮助实现快照隔离，以实现ACID事务（细节可参考原文的事务章节）。写入成功的事务会将新的写记录提交到write列；并设置notify列（如图中“Changed！”），通知此值已经发生了变化。

step 2：worker中各个扫描线程通过巧妙的分工（分工之巧妙、如何避免公交车凝结效应等，请看原文通知章节），尽可能高效的对特殊的notify列进行扫描（notify列是Bigtable中特殊的locality group，提升效率）。

step 3：扫描线程发现了step 1设置的notify列（如图中“Changed！”），需要通知相关的观察者来执行后续逻辑，但是为了避免非预期的并发问题导致多个线程同时扫描到此行，导致启动重复的观察者事务，这里扫描线程需要判断ack列，得知此行最近被观察者在哪个时间点做了处理，通过对write列和ack列中时间戳的分析，扫描线程可以“猜测”是不是可以启动观察者。若可以启动，则将新启动的观察者的开始时间戳写入ack列（由Bigtable行事务保护），以便下次扫描。即使在极小的概率下两个线程同时“猜测”可以启动，也会在写入ack列时发生冲突而避免重复。

step 4：各观察者会在Percolator Worker中注册自己感兴趣的列。扫描线程找到此次通知对应的观察者，启动并开始执行一个新事务。事务中观察者执行自己的计算逻辑，并可能需要从其他table中查询必需的数据（对应step5，此过程可能涉及事务中的读/写冲突，读事务会查看write列和lock列来判断是否冲突，冲突时读事务会等待，直到写事务结束，细节请参考原文和图6源码）。在计算结束后，输出的结果需要写入另一个table（对应step6，此时会遇到和step1类似的写/写冲突）。提交成功的写操作将触发step1，依次循环直至不再写入任何列或没有任何观察者需要被触发。

以上是译者YY的大致流程，希望可以帮助读者参考以窥全貌，继而结合原文、源代码细化阅读。事务部分的源码其实非常值得精度，只是原文的事务章节陈述性语句太多而且晦涩难懂、逻辑跳跃。强烈建议读者阅读图6甚至更多的源码，以了解一个巧妙的分布式事务方案。译者也提供了比较通俗的总结环节来帮助读者理解。

?

2.2 事务

Percolator利用ACID快照隔离语义提供了跨行、跨表事务。Percolator的用户可使用必要的语言(当前是C++)编写它们的事务代码，然后加上对Percolator API的调用。图2表现了一段简化的基于内容hash的文档聚类分析程序。在这个例子中，如果Commit()返回false，事务冲突了（可能两个有内容hash相同的URL被同时处理）需要在回退后被重新尝试。对Get()和Commit()的调用是阻塞式的；通过在一个线程池里同时运行很多事务来增强并行。

尽管不利用强事务的优势也可能做到数据增量处理，但事务使得用户能更方便的推导出系统状态，避免将难以发现的错误带到长期使用的存储库中。比如，在一个事务型的web索引系统中，开发者能保证一个原始文档的内容hash值永远和索引复制表中的值保持一致。而没有事务，一个不合时的冲击可能造成永久的不一致问题。事务也让构建最新、一致的索引表更简单。注意我们说的事务指的是跨行事务，而不是Bigtable提供的单行事务。

Percolator使用Bigtable中的时间戳维度，对每个数据项都存储多版本，以实现快照隔离。在一个事务中，按照某个时间戳读取出来的某个版本的数据就是一个隔离的快照，然后再用一个较迟的时间戳写入新的数据。快照隔离可以有效的解决“写-写”冲突：如果事务A和B并行运行，往某个cell执行写操作，大部分情况下都能正常提交。任何时间戳都代表了一个一致的快照，读取一个cell仅需要用给出的时间戳执行一个Bigtable查询；获取锁不是必要的。图3说明了快照隔离下事务之间的关系。

传统PDBMS为了实现分布式事务，可以集成基于磁盘访问管理的锁机制：PDBMS中每个节点都会间接访问磁盘上的数据，控制磁盘访问的锁机制就可以控制生杀大权，拒绝那些违反锁要求的访问请求。而Percolator是基于Bigtable的，它不会亲自控制对存储介质的访问，所以在实现分布式事务上，与传统的PDBMS相比，Percolator面对的是一系列不同的挑战。

相比之下，Percolator中的任何节点都可以发出请求，直接修改Bigtable中的状态：没有太好的办法来拦截并分配锁。所以，Percolator一定要明确的维护锁。锁必须持久化以防机器故障；如果一个锁在两阶段提交之间消失，系统可能错误的提交两个会冲突的事务。锁服务一定要高吞吐量，因为几千台机器将会并行的请求锁。锁服务应该也是低延迟的；每个Get()操作都需要申请“读取锁”，我们倾向于最小化延迟。给出这些需求，锁服务器需要冗余备份（以防异常故障）、分布式和负载均衡（以解决负载），并需要持久化存储。Bigtable作为存储介质，可以满足所有我们的需求，所以Percolator将锁和数据存储在同一行，用特殊的内存列，访问某行数据时Percolator将在一个Bigtable行事务中对同行的锁执行读取和修改。

我们现在考虑事务协议的更多细节。图6展现了Percolator事务的伪代码，图4展现了在执行事务期间Percolator数据和元数据的布局。图5中描述了系统如何使用这些不同的元数据列。事务构造器向oracle请求一个开始的时间戳（第六行），它决定了Get()将会看到的一致性快照。Set()操作将被缓冲（第七行），直到Commit()被调用。提交被缓冲的Set操作的基本途径是两阶段提交，被客户端协调控制。不同机器上基于Bigtable行事务执行各自的操作，并相互影响，最终实现整体的分布式事务。

【译者注】十分抱歉此段截图狭长导致格式不畅，而且此章内容十分晦涩，需要结合图和文字一起阅读，所以建议读者打开原文PDF中的图解（尤其是图6的源码）和下文对照阅读。并建议阅读本章结束的【译者总结】的补充内容。

在Commit的第一阶段(“预写”，prewrite)，我们尝试锁住所有被写的cell。（为了处理客户端失败的情况，我们指派一个任意锁为“primary”；后续会讨论此机制）事务在每个被写的cell上读取元数据来检查冲突。有两种冲突场景：如果事务在它的开始时间戳之后看见另一个写记录，它会取消（32行）；这是“写-写”冲突，也就是快照隔离机制所重点保护的情况。如果事务在任意时间戳看见另一个锁，它也取消（34行）：如果看到的锁在我们的开始时间戳之前，可能提交的事务已经提交了却因为某种原因推迟了锁的释放，但是这种情况可能性不大，保险起见所以取消。如果没有冲突，我们将锁和数据写到各自cell的开始时间戳下（36-38行）

如果没有cell发生冲突，事务可以提交并执行到第二阶段。在第二阶段的开始，客户端从oracle获取提交时间戳（48行）。然后，在每个cell（从“primary”开始），客户端释放它的锁，替换锁为一个写记录以让其他读事务知晓。读过程中看到写记录就可以确定它所在时间戳下的新数据已经完成了提交，并可以用它的时间戳作为“指针”找到提交的真实数据。一旦“primary”的写记录可见了（58行），其他读事务就会知晓新数据已写入，所以事务必须提交。

一个Get()操作第一步是在时间戳范围 [0,开始时间戳] 内检查有没有锁，这个范围是在此次事务快照所有可见的时间戳（12行）。如果看到一个锁，表示另一个事务在并发的写这个cell，所以读事务必须等待直到此锁释放。如果没有锁出现,Get()操作在时间戳范围内读取最近的写记录（19行）然后返回它的时间戳对应的数据项（22行）。

由于客户端随时可能故障，导致了事务处理的复杂度（Bigtable可保证tablet服务器故障不影响系统）。如果一个客户端在一个事务被提交时发生故障，锁将被遗弃。Percolator必须清理这些锁，否则他们将导致将来的事务被非预期的挂起。Percolator用一个懒惰的途径来实现清理：当一个事务A遭遇一个被事务B遗弃的锁，A可以确定B遭遇故障，并清除它的锁。然而希望A很准确的判断出B失败是十分困难的；可能发生这样的情况，A准备清理B的事务，而事实上B并未故障还在尝试提交事务，我们必须想办法避免。现在就要详细介绍一下上面已经提到过的“primary”概念。Percolator在每个事务中会对任意的提交或者清理操作指定一个cell作为同步点。这个cell的锁被称之为“primary锁”。A和B在哪个锁是primary上达成一致（primary锁的位置被写入所有cell的锁中）。执行一个清理或提交操作都需要修改primary锁；这个修改操作会在一个Bigtable行事务之下执行，所以只有一个操作可以成功。特别的，在B提交之前，它必须检查它依然拥有primary锁，提交时会将它替换为一个写记录。在A删除B的锁之前，A也必须检查primary锁来保证B没有提交；如果primary锁依然存在它就能安全的删除B的锁。

如果一个客户端在第二阶段提交时崩溃，一个事务将错过提交点（它已经写过至少一个写记录），而且出现未解决的锁。我们必须对这种事务执行roll-forward。当其他事务遭遇了这个因为故障而被遗弃的锁时，它可以通过检查primary锁来区分这两种情况：如果primary锁已被替换为一个写记录，写入此锁的事务则必须提交，此锁必须被roll forward；否则它应该被回滚（因为我们总是先提交primary，所以如果primary没有提交我们能肯定回滚是安全的）。执行roll forward时，执行清理的事务也是将搁浅的锁替换为一个写记录。

清理操作在primary锁上是同步的，所以清理活跃客户端持有的锁是安全的；然而回滚会强迫事务取消，这会严重影响性能。所以，一个事务将不会清理一个锁除非它猜测这个锁属于一个僵死的worker。Percolator使用简单的机制来确定另一个事务的活跃度。运行中的worker会写一个token到Chubby锁服务来指示他们属于本系统，token会被其他worker视为一个代表活跃度的信号（当处理退出时token会被自动删除）。有些worker是活跃的，但不在运行中，为了处理这种情况，我们附加的写入一个wall time到锁中；一个锁的wall time如果太老，即使token有效也会被清理。有些操作运行很长时间才会提交，针对这种情况，在整个提交过程中worker会周期的更新wall time。

【译者总结】译者感觉上面这段介绍事务的原文过于松散，内容不足，所以根据自己的理解，这里稍作补充，不能保证准确性，只是希望能供读者参考。

译者认为，事务章节希望介绍4方面的内容：1，Percolator事务希望实现什么场景的ACID；2，机器正常时，一个事务在各种各样的场景下如何反应，来保证大家的ACID；3，机器故障时，如何为受影响的事务善后，仍然保证ACID；4，如何适应分布式环境

1，Percolator事务希望实现什么场景的ACID

首先，理解一下Bigtable的事务。Bigtable能提供单行事务，简单说就是用事务更新一个row时，能保证各个列的更新能同时生效、或同时失败。但是需要注意的是，Percolator在使用Bigtable的单行事务更新一个row时，不是为了更新多个真实的data。比如一个文档，它有PageRank值，内容hash值等多个属性，Percolator会不会把它们作为列放在同一个表里，然后用单行事务去同时更新？答案是不会。Percolator会为PageRank、内容Hash每个属性单独创建一张表，对外界来说就好像它们每个人都占据了一张表，但是只用到了一个列。之所以这么做，是因为对PageRank、内容Hash等每个data，Percolator都要附带的配送一系列的元数据（lock、write等），出于就近原则也是为了避免麻烦，这些元数据就直接作为“伴随”列，放在真实数据列的旁边。（真实的结构可能更复杂，但是在本篇论文中没有提到，可以先这么简单理解，即使有偏差也不会有太大影响）。所以Percolator依赖Bigtable的单行事务，主要是为了能原子的修改真实的数据和它的伴随元数据。

接下来Percolator要做什么呢？为什么要有那么多伴随元数据呢？

对于Percolator来说，原子的更新一个（甚至是多个）文档的PageRank值和内容Hash值，是无法避免的。按照上述存储方式，这些值都是分布在各自的表中、不同的row上，所以Percolator要提供的，就是跨表的、跨行的事务。这个事务通过有效的利用元数据，在各种可能遇到的场景中“随机应变”，来保证自己和其他事务的ACID。比如它要原子更新3个PageRank值和2个内容Hash值，这5个值分布在2张表的5个row的cell上，一个事务的核心思路就是：首先对5个cell执行更新（Set()操作，但不会立刻生效，而只是将Set操作记录在内存中）；然后抢到这5个cell的“锁”，抢不到就退出，当什么都没发生过；抢到了，就将5个Set操作一个个的提交（由于5个锁都抢到了，所以可以放心大胆的一个个提交，期间不会有其他事务来捣乱）；5个都提交，本事务圆满结束，将锁一个个释放掉，不耽误其他的事务。过程其实非常简单，但是其中的细节处理却十分繁琐，需要各种缜密复杂的逻辑。比如一个个的提交5个cell时，怎么保证它们5个同时对外可见（需要“写记录”的“昭告”，“锁”的阻挠，还需要Get()的配合）？抢锁的细节到底如何？任何一个阶段机器突然重启，怎么善后？下面我们对机器正常时的各种场景、机器故障时的异常场景进行分析，来回答这些问题。

2，机器正常时，一个事务在各种各样的场景下如何反应？

假如当前事务是T，T整个生命包含3个步骤：

• step1（抢到所有的锁！）。对于每个cell，通过执行prewrite来进行抢锁。在prewrite中，会尝试用Bigtable行事务将“真实数据”和“锁”都写入对应的cell，若事务成功，代表抢到此cell的锁。任何一个cell抢锁失败就导致整个T失败，否则进入step2.
• step2（让首要的先走！）。 primary，首要的，是所有cell里随机选出来的一个cell，它本身并不特殊（之所以要选primary是为了处理“机器故障”导致的事务异常，后续会讨论）。一个cell的提交，就是做两件事情，1是填入写记录（write 列），2是删除锁（lock列）。需要注意的是在此step，这两个动作是在一个Bigtable单行事务下提交的，保证原子性（后续会解释原因）
• step3（最后一搏）。首要的cell提交了，step3就是提交剩下的cell，也是做和step2一样的两件事情，但是这里没有用Bigtable单行事务。

  （注意，step1对应“2PC”的阶段一，step2和3对应“2PC”的阶段二，这里细化是为了便于分析某些场景）

  在详细分析之前，先强化对几个概念的理解：

  写记录（write列中kv结构中的一个entry，key是时间戳，value就像一个指向真实data的“指针”）：对写记录最感兴趣的是读事务，也就是Get()操作，它永远是以“写记录”马首是瞻，根据它找到最新的数据，若写记录不提交，即使真实数据在step1就提交了，那也如锦衣夜行，没人知道你产生了新数据，写记录被写入write列才等于昭告天下，本值已准备好被查了。

  锁（lock列中kv结构的一个entry，key是时间戳，value是锁相关的信息）：锁起的就是一个警示作用，表示本事务霸占了这个cell。如果读事务（Get操作）看到一个锁，那说明有其他写事务正在操作此cell，读事务必须等待；如果写事务在step1看到一个锁，那说明别人抢在它前头，已经霸占了这个cell，它只能失败。

  下面以T作为故事的主角，穷举出所有可能与它交手的“反派”，逐一分析T该如何应对：

  对于T来说，它需要提防哪些其他事务呢？如果一个事务修改的cells和T即将修改的cells有交集，那就有可能是T要提防的其他事务，就是即将交手的“反派”

  这些“反派”可以按时窗视角分为（由于step2在无机器故障时和step3无异，可一视同仁，所以这里统称为step23）：

  1. 发生在T之前，当T刚刚开始（拿到开始时间戳）时，它的step23已经结束
  2. 发生在T之前，当T刚刚开始（拿到开始时间戳）时，它的step1已经结束，正在进行step23
  3. 与T差不多时间，当T刚刚开始时它也刚刚开始
  4. 发生在T之后，当T step1提交后它才刚开始
  5. 发生在T之后，当T step23提交后它才刚开始

  其中1、5两种情况可以先排除，因为时窗上无交集，不会相互影响。

  下面简称“反派”为G

  情况2中，G的step1结束，说明已经将lock写入各cell的lock列，按常理，T是肯定会看到锁而取消的。但是又由于step23正在进行中（挨个删除曾经写入的锁），所以十分可能T十分“倒霉”的没有看到任何的锁。没看到锁是小事，真正悲剧的是G还在不断的提交写记录，相当于写入新值，而这些T都蒙在鼓里。所以才要补充对写记录的检查，一旦G瞒着T（瞒着的意思就是把锁删了没让T看到）提交了写记录，写记录的时间戳是G的开始时间戳，其必定早于T的开始时间戳，于是T可以以此为线索，检查各cell锁的同时也检查一下它的写记录。（G必须保证step23中对各cell一定是先提交写记录、后删除锁，才能疏而不漏。个中微妙读者可以画画图领会一下）

  情况3中，那就是狭路相逢，拼的就是Bigtable的单行事务。Bigtable单行事务据译者理解应该基于乐观锁（没有行锁），但是这里为了方便理解，咱们就简单的把它理解为能够霸占某个row的行锁（注意这里的行锁指的是Bigtable事务机制中的概念了，不要和Percolator的锁混淆）——T和G，谁能抢到所有cell的行锁，就能提交step1中的prewrite动作（写入真实data和lock列），谁就继续，否则就取消。但是要注意的是T和G在抢锁时抢的cell顺序是不固定的，各自有自己的顺序，那会不会出现交集里有5个cell，T抢到3个，G抢到2个？不可能，这就像世界杯加时赛金球制胜，只要没抢到一次，那就直接退出。

  情况4，与2相同，只是角色互换。

  上面应该包括了所有可能发生的情况，每种情况都可以保证T的ACID，T要么一路过关斩将直到全部提交成功，要么退出，没有第三种可能。

  ?

  3，机器故障时，如何为受影响的事务善后

  一个事务就3个step，所以机器可能在5个点挂掉

  1. step1开始前
  2. step1期间
  3. step2期间
  4. step3期间
  5. step3之后

  同样的，1、5不用去管。

  刚拿到情况2，就觉得有点难办。你想啊，step1做的事情是提交各个cell的真实值和锁，弄到一半，机器突然挂了，怎么知道提交了哪些？没提交哪些？简直是死无对证，毁尸灭迹——Percolator中没有任何一个组件知道这里死了个事务，更不知道玷污了哪些表的哪些列。

  就在案件没有线索进行不下去时，转机，发生了：每个事务所在的worker都有活跃度检测记录（token、walltime）。通过分析检测记录，我们可以找到机器挂掉时所有涉案的事务。更幸运的是，在信息库中可以找到每个锁对应的事务（原文中有“a transaction will not clean up a lock unless it suspects that a lock belongs to a dead or stuck worker”，所以译者判断Percolator应该有办法suspect出一个锁属于哪个事务）。

  于是我们将涉案事务发出皇榜，昭告百姓。终于，开始出现了一个又一个目击者，也就是Get()操作。它在查询过程中，受到一个可疑锁的阻挠，仔细辨认后确定此锁是被涉案事务所遗弃的！此时我们要做的，就是把这个锁删掉，而且也不用担心其他的遗弃锁。因为对于其他的遗弃锁，如果没人去查询它对应的data，它不会造成什么影响，如果有Get()去查它对应的data，肯定会被它阻挠，最终也会按照同样的方式，被我们删掉。

  在情况2里，弄脏的只有lock列和data列（step1只写这两个列），lock列已经解决了，data列，可以直接不去管它。因为step1没有产生写记录，此事务的真实值不会被任何人查到，迟早被垃圾清理掉。

  对于情况3，在step2发生的唯一事情，就是事务会写入Primary的写记录，同时删除Primary锁（在同一个Bigtable行事务，必定同时发生）。所以Primary锁是否存在，是一个重要标志，如果还存在，说明事务在删除它之前就挂了，绝没有进入情况4，也没有写入Primary写记录。这种情况就相当于情况2，不需要做什么处理（只要像情况2一样等着垃圾锁被清理即可，没有额外的脏数据）。如果不存在，则相当于已经进入情况4，而且Primary写记录也必定已经提交。之前说的清理遗留锁，可以理解为此事务的回滚。而这次不行了，Primary写记录的提交意味着外界已经知道了新值的存在，至少一个。所以这时必须前滚（roll forward）。在情况2中，每个尝试清理的Get()操作，都会先做一个判断，检查Primary锁是否存在。如果锁仍存在，则断定依然属于情况2，可以放心清理；但是如果锁消失了，则必须进入情况4的前滚模式。前滚也很简单，当Get()进入情况4模式后，它通过该锁，找到时间戳，以此时间戳往write列里提交个写记录即可（然后再删除锁）。

  这就是为什么，Percolator一直强调它的分布式事务不是靠中央总控实现的，而是一种懒惰的，等着后来的目击者Get()去一个个的发现和自我修正的客户端协调控制型分布式事务。

  另一个值得注意的地方是，step2提交Primary写记录、删除Primary锁用了Bigtable单行事务，而step3中其他cell提交写记录、删除锁却没有用到单行事务。这是出于什么原因呢？首先Primary那两个操作必须有单行事务保护，只有保证它俩的原子性，Get()才能放心大胆的根据Primary锁存不存在来判断情况2和情况4，这里不用单行事务只会把事情搞复杂。其次，对于其他cell，则不需要单行事务保护，即使写记录先提交了，昭告了新值诞生，但是锁没删除掉，外界依然访问不到，不会导致问题。

  另外从源码上看，最后执行的

  1234for (Write w : secondaries) {??bigtable::Write(w.row, w.col+"write", commit ts, start ts );??bigtable::Erase(w.row, w.col+"lock", commit ts);}

  看上去陆陆续续的把每个cell的值开放出去了（写记录添加了，锁也删了），这样陆续开放，会不会导致中间一个瞬间，可能5个cell有3个被外界查询了新值，另2个被查询了旧值？答案是否定的，另2个没来得及开放出去的锁也没删掉，查询会停住，等待它释放锁。

  即使是刚才讨论的故障发生时（无论发生在step3的那个点上），没有提交完全的（填入写记录和删除锁都提交了才算提交完全），都会触发情况4前滚，继而被查询到新值，不会出现违反ACID的情况。

  4，上述逻辑怎么适应分布式环境？

  其实这里无需补充这一段，读者也可以理解它能适应分布式环境，但为了强调Percolator是分布式事务，可以简单讨论一下。上面已经论证Percolator能巧妙应对跨表、跨行的事务，那假如在更新5个cell的例子中，5个cell分布在5台机器的tablet上，还能应对自如吗？你是不是也很奇怪为何这里没有出现传统分布式事务中的协调者、参与者角色？

  回想一下在机器正常时，我们提到Percolator在各个阶段都对很多cell做了很多update操作，有单个cell的直接更新，也有同row的多个cell用Bigtable单行事务原子更新。我们之前在理解时可能是把它们当做本地的tablet，调用的是Bigtable的本地方法。而事实上对Bigtable的调用（包括无事务的直接更新、有单行事务的更新），根本无所谓它是在同台机器还是在远程机器上，都是向tablet服务器发送一个“指令”，远程机器也就是多了个网络传输的过程而已，没有什么区别。（其实事实上，即使Percolator worker和Bigtable在同台机器，译者估计也是各自独立的进程，进程间的通讯和RPC通讯，无甚区别）

  另外，最重要的，这里采用的是快照隔离机制，也是按“乐观锁”的方向去设计的，它不需要协调者、参与者那么严谨严格的控制。在它的世界里，一台机器上正在执行一个事务，那这个事务就是唯一的控制者，它决定了自己是应该退出还是提交。这样虽不严谨，但是它巧妙的利用了写记录、锁、时间戳版本等机制，再加上Get()等所有操作的配合，也能保证最终的效果是符合ACID的。即使机器故障，也利用懒惰的客户端协调控制解决了问题，不需要中央总控。不严谨体现在很多方面，比如在这个事务执行期间所提交的更新不是同时生效的，每提交一个就生效一个。以A转账给B为例，要修改A、B两个账户的cell（A减钱，B加钱），在step3，RPC调用远程机器提交了第一个cell的写记录（A减钱），然后本机器故障了，此cell的更新已然生效，可以查到新值，对于传统事务这是无法接受的（A钱都扣了，B的钱却没加，不能忍）。但是在Percolator中，它利用自己的细节机制，缜密巧妙的避免了各种问题。即使A账户的cell生效了，但是B账户cell的锁还没释放掉，外界的访问会失败。所以最坏的情况就是看到A的钱扣了，查看B的时候查询失败（理想情况是访问B的时候遇到遗留锁，走情况4前滚逻辑，帮助事务最终完成，B的钱也加掉，皆大欢喜）。

  总结

  Percolator的事务，向大家很好的诠释了什么叫细节决定成败。读者可以思考一下，为什么要在step1就早早的把真实数据写入data列？为什么要在多个cell里随机选一个Primary？为什么step3一定要先提交写记录后删除锁？传统的Get()逻辑都是简单的，在这里为何担此重任？可以说，几乎所有的正常事务逻辑、异常恢复逻辑，都是依靠各种细节相互照顾、相互协调所实现的。

  看分析不如先看代码，图6中精彩的源代码值得每个希望研究事务的同学精读。

  2.3 时间戳

  时间戳oracle是一个用严格的单调增序给外界分配时间戳的服务器（为什么取名oracle、是不是真的用了Oracle DB无从得知，译者注）。因为每个事务都需要调用oracle两次，这个服务必须有很好的可伸缩性。oracle会定期分配出一个时间戳范围，通过将范围中的最大值写入稳定的存储；范围确定后，oracle能在内存中原子递增来快速分配时间戳，查询时也不涉及磁盘I/O。如果oracle重启，将以稳定存储中的上次范围的最大值作为开始值（此值之前可能有已经分配的和未分配的，但是之后的值肯定是未分配的，所以即使故障或重启也不会导致分配重复的时间戳，保证单调递增 ）。为了节省RPC消耗（会增加事务延迟）Percolator的worker会维持一个长连接RPC到oracle，低频率的、批量的获取时间戳。随着oracle负载的增加，worker可通过增加每次批处理返回的量来缓解。批处理有效的增强了时间戳oracle的可伸缩性而不影响其功能。我们oracle中单台机器每秒向外分配接近两百万的时间戳。

  事务协议使用严格增长的时间戳来保证Get()能够返回所有在“开始时间戳”之前已提交的写操作。举个例子，考虑一个事务R在时间戳T(R)执行读取操作，一个写事务W在时间戳T(W)<T(R)执行了提交;如何保证R能看到W提交的写操作？由于T(W)<T(R)，我们知道oracle肯定是在T(R)之前或相同的批处理中给出T(W)；因此，W是在R收到T(R)之前请求了T(W)作为提交时间戳。我们知道R在收到T(R)之前不能执行读取操作，而W在它的提交时间戳T(W)之前必定完成了锁的写入；因此，上面的推理保证了W在R做任何读之前就写入了它所有的锁；R的Get()要么看到已经完全提交的写记录，要么看到锁，在看到锁时R将阻塞直到锁被释放（锁被替换为写记录）。所以在任何情况下，W的写对R的Get()都是可见的。

  2.4 通知

  事务可以让用户改变table，同时维护了不变量，但是用户还需要一个方法来触发和运行事务。在Percolator，用户编写的代码（“观察者”）将因表的变化而触发，我们将所有观察者放入一个可执行文件（Percolator worker），它将伴随每一个tablet服务器运行。每个观察者向Percolator注册一个function和它感兴趣的列，当数据被写到这些列时Percolator会调用此function。

  Percolator应用的结构就是一系列的观察者；每个观察者完成一个任务然后对相应table执行写操作，从而触发“下游”的观察者任务。在我们索引系统中，用一个MR作业运行装载事务，将抓取的文档装载到Percolator，它将触发文档处理器事务执行索引分析（解析、抽取连接等等），文档处理器事务触发更多后续的事务比如聚类分析，最后触发事务将改变的文档聚类数据导出到在线服务系统。

  通知类似于数据库中的触发器或者事件，但是与数据库触发器不同，它们不能被用于维护数据库不变量。比如某个写操作触发了观察者逻辑，写操作和观察者将运行在各自的事务中，所以它们产生的写不是原子的。通知机制是为了帮助组织一个增量的计算，而不是帮助维护数据一致性。

  因此，相比数据库触发器，观察者的行为更易理解。Percolator应用其实包含很少的观察者——Google索引系统有大概10个观察者。每个观察者都是在worker可执行文件的main函数中明确构造的，所以很清楚哪些观察者是活跃的。可能有多个观察者需要观察同一个列，但是我们避免了这个特性，所以可以很清楚的知道当一个特定的列被写后哪个观察者将运行。不过用户需要担心通知的无限循环，Percolator没有为此多做考虑；用户通常是构造一连串依次执行的观察器来避免无限循环。

  我们提供一个保证：对一个被观察列的每次改变，至多一个观察者的事务被提交。反之则不然：一个被观察列的多次写可能只会触发一次观察者事务。我们称这个特性为消息重叠，它可以避免不必要的重复计算。比如，对http://google.com页面来说，周期性的通知其变化就够了，不需要每当一个新链接指向它时就触发一次。

  为了给通知机制提供这些语义，每个被监测列旁边都有一个“acknowledgment”列，供每个观察者使用，它包含最近一次观察者事务的开始时间戳。被监测列被写入时，Percolator启动一个事务来处理通知。事务读取被监测列和它对应的acknowledgment列。如果被监测列发生写操作的时间戳在acknowledgment列的最近时间戳之后，我们就运行观察者逻辑，并设置acknowledgment列为新的开始时间戳。否则，说明已经有观察者被运行了，所以我们不重复运行它。注意如果Percolator偶然对一个特定的通知并发启动了两个事务，它们都会看到脏通知、运行观察者，但是其中一个将取消因为它们会在acknowledgment列上产生写冲突。我们保证对每个通知至多一个观察者可以提交。

  为了实现通知机制，Percolator需要高效找到被观察的脏cell。这个搜索是复杂的因为通知往往是稀疏的：我们表有万亿的cell，但是可能只会有百万个通知。而且，观察者的代码运行在一大批分布式的跨大量机器的客户端进程上，这意味着脏cell搜索也必须是分布式的。

  为确定cell是否脏，Percolator还是老办法，在Bigtable真实数据列旁边维护一个特殊的“notify”列，表示此cell是否为脏。当一个事务对被监测cell执行写操作时，它同时设置对应的notify cell。worker对notify列执行一个分布式扫描来找到脏cell。在观察者被触发并且事务提交成功后，我们会删除对应的notify cell。因为notify列只是一个Bigtable列，不是个Percolator列，它没有事务型属性，只是作为一个暗示，配合acknowledgment列来帮助扫描器确定是否运行观察者。

  为了使扫描高效，Percolator存储notify列为一个独立的Bigtable locality group，所以扫描时仅需读取百万个脏cell，而不是万亿行个cell。每个Percolator的worker指定几个线程负责扫描。对每个线程，worker为其分配table的一部分作为扫描范围，首先挑选一个随机的tablet，然后挑选一个随机的key，然后从那个位置开始扫描。因为每个worker都在扫描table中的一个随机范围，我们担心两个worker会扫描到同一行、并发的运行观察者。虽然由于通知的事务本性，这种行为不会导致数据准确性问题，但这是不高效的。为了避免这样，每个worker在扫描某行之前需要从一个轻量级锁服务中申请锁。这个锁服务只是咨询性质、并不严格，所以不需要持久化，因此非常可伸缩。

  这个随机扫描机制还需要一个附加优化：在最初部署运行时，我们注意到随机的效果不好，扫描线程都趋向于“凝结”到table的少量几个域上，严重影响了扫描的并行效果。这现象通常可以在公交系统中看到，被称为“bus凝结”效应。某一个bus可能因为某种原因导致速度减慢（比如在某个站上车的乘客太多），导致它到达后续车站的时间延后，而每个车站的乘客数量会随时间增长，于是越来越慢。同时，在这个慢bus后面的bus的速度则会提高，因为它在每个站装载的乘客数量减少了。最终的现象就是多辆公交会同时到达后续的车站。我们扫描线程行为与此类似：一个线程由于运行观察者减慢，而它之后的线程快速的跳过已被处理的脏cell，逐渐与领头的线程聚集在一起，但是却没能超过领头的线程因为线程凝结导致tablet服务器繁忙过载。为了解决这个问题，我们做了一个公交系统不能实现的优化：当一个扫描线程发现了它和其他的线程在扫描相同的行，它在table中重新选择一个随机定位继续扫描。这就好比在公交系统中，公交车（扫描线程）为避免凝结而时空穿梭到一个随机的车站（table中的某个位置）。

  最后我们重申，之所以采取非常轻量级、弱事务语义、甚至牺牲了部分一致性的通知机制，是因为在之前的方案中吸取了教训，痛定思痛。现在的机制之轻，主要体现在异步二字上：当改变发生时，并不是立刻以同步方式调用观察者，而仅仅是写入一个弱事务约束的notify列，默默的等待着worker线程扫描到自己才调用观察者，相当于是为后续工作启用了一个异步线程等待被调度。这样的劣势很明显，无论是时效性、一致性都受影响。但是试想在强通知机制下，相似或相同的页面被并发执行聚类分析时，每个事务都同步递归的触发下游工作（比如更新同一个聚类），战线拉得太长，等待时间太长，也就意味着占有锁的事务拖的太长，从而很可能导致大量的冲突，影响性能，甚至恶性循环导致服务器崩溃。不对notify列进行强事务约束，只将其视为一个hint（暗示），意味着会有很多弥补机制来恢复故障导致的一致性问题，所以我们甚至可以在hint写入之后将此notify的cell设置为不可写，以避免不必要的性能损失或写失败。同时，弱通知机制虽然不提倡多个观察者观察同一个列，但是功能上依然是支持的。事实上，当一个观察者事务在某个热点上频繁冲突，将其一拆为二同时接收通知往往能起到缓解效果（相当于将一个大任务拆分成两个小任务，小任务只负责一部分的更新操作，执行也更快，减少冲突的几率）。

  【译者总结】Percolator在通知机制上做足文章是非常值得的。首先，它打造了一个非常可扩展的、友好的编程模型。当新的需求到来时，理想情况下你可以简单的增加一个观察者，而不是在老代码中“截断”、“插入”、“修改”…… 而且，web索引构建系统中的逻辑是一堆高内聚却又相互依赖的单元，如内容Hash计算、PageRank计算、锚文本处理等，它们可以各自分开执行，却也可能依赖彼此的执行结果，所以非常适合这种编程模型。其次，轻量级通知+轻量级事务确实是珠联璧合、相得益彰。采用事务就意味着牺牲了性能，而通知机制让整个系统完全“异步化”，为性能优化创造了很大空间（在普通web应用的同步环境下使用事务往往都是性能杀手，量大时DB就是最大隐患）。而零散的、未知的、高速吞吐的通知又让人十分担心数据一致性问题（在普通web应用下，用户访问某个页面、点击某个按钮，会触发哪些逻辑、导致哪些更新基本上是可控的、已知的；而通知机制将逻辑打散，意味着任何一个cell的更新将触发后面一系列未知的多米诺式的更新，你根本不知道它会影响哪些cell、或者“递归”到第几层，甚至可能导致无限循环），而细致入微、法网恢恢的ACID分布式事务又有效的避免了任何可能的一致性问题。所以它们一起出现、相互合作，也就并不意外了。

  【译者注】译者阅读本文至此，一直有一个很大的疑惑：Percolator声称处理速度比MR提升了100倍，译者期待看到的是一种新的计算模型、计算架构，或者是高效的数据结构+算法的设计、高效的并行计算过程……但是作者却开始大篇幅的介绍起分布式事务（以前的印象中谈到事务都是影响性能的，大规模计算都要努力避免的）、时间戳、通知等知识，眼看核心部分就要结束了，实在让人不解。如果有读者拥有相同的困惑，可阅读文章末尾的译者总结环节。

  2.5 讨论

  相对于MR，Percolator一个不高效的点就是每个work单元发送的RPC数量。MR通常只对GFS执行一个大型的read操作以获取所有需要的数据，而Percolator处理一个文档就需要执行大约50个单独的Bigtable操作。导致RPC太多的其中一个因素发生在commit期间。当写入一个锁时就需要两个Bigtable的RPC：一个为查询冲突锁或写记录，另一个来写入新锁。为减少负载，我们修改了Bigtable的API将两个RPC合并（读者可以联想一下Map中的createIfAbsent）。按这个方法，我们会尽量将可以打包批处理的RPC调用都合并以减少RPC总数。比如将锁操作延缓几秒钟，使它们尽可能的聚集以被批处理。因为锁是并行获取的，所以每个事务仅仅增加了几秒的延迟；这附加的延迟可以用更强的并行来弥补。批处理增大了事务时窗，导致冲突可能性提高，但是通过有效的事务、通知机制，我们的环境中竞争并不强烈，所以不成问题。

  从table读取时我们也利用了批处理：每个读取操作都被延缓，从而有一定几率让相同tablet的读取操作打包成批处理（类似buffer的原理）。这样会延缓每次读取，也可能增加不少的事务延迟。为了解决这个问题，我们采用了预取机制。实验证明从同一行里读取一个数据和读取多个数据所产生的消耗相差不大，因为Bigtable都要从文件系统读取一整个SSTable块并解压缩。Percolator尝试在每次读取某一行的某一列时都做预测，在本事务中，会不会稍后就要读取该行的其他列。预测是根据过去的行为记录而做出的。通过此方法，降低了几乎10倍的read次数。

  在之前的Percolator的实现中，所有API调用都会阻塞，然后通过调高每台机器的线程数量来支持高并发、提升CPU利用率。相比异步、事件驱动等方案，这种thread—per-request的同步模型的代码更易编写。异步方案需要花费大量精力维护上下文状态，导致应用开发更加困难。根据我们的实际经验，thread—per-request的同步模型还是可圈可点的，它的应用代码简单，多核机器CPU利用率也不错，同步调用下的堆栈跟踪也很方便调试，所遭遇的资源竞争也没有想象中那么恐怖。不过它的最大缺点是可伸缩性问题，linux内核、Google的各种基础设施在遭遇很高的线程数时往往导致瓶颈。不过我们有in-house内核开发小组来帮助解决内核问题。

  【译者注】文章后半部分大量篇幅介绍了所做的实验和指标，由于和核心机制关系不大，译者偷懒没有翻译，读者可参考原文。

  【译者总结】看到一篇介绍100倍性能提升的文章，译者脑中第一个想法就是要找到这个“神器”，找到提升100倍的关键设计，它可能是个算法，也可能是个巧妙的数据结构设计，也可能是天才的并行计算架构……但是随着阅读的深入，发现作者对这些都避而不谈，转而大篇幅的介绍分布式事务。在没有搞清楚状况时译者的困惑始终伴随左右。而在通读此文以及相关的其他论文后，才发现提升100倍的神器确实存在，以下就是译者对此神器的理解：

  译者认为，Percolator得到100倍的速度提升并不是取决于它的分布式事务和通知机制多么优秀（确实很优秀），本质上的原因是它改变了索引构建系统的架构类型。比如在淘宝和支付宝，线上支撑双十一大促和秒杀的系统，它要处理很大的数据量；而另一个系统，用于分析某个垂直行业的交易记录得出BI报表（比如服装行业各店铺的各类商品价格走势，以便做出销售策划），也要处理很大的数据量。但是两者的架构类型却有本质上的不同。前者是所谓的增量处理系统，产生一笔交易的input数据很小，但是却要在已存在的茫茫数据中做多次查询（比如在支付阶段要在几亿账户里查询买家账户和卖家账户，判断余额等等），得到额外的input，结合、计算之后产生的输出再插入到茫茫数据中。而后者，所有的输入已经确定，就是某段时间内的交易记录，我们不需要所谓的“已存在库”，更不需要在“已存在库”中查询额外的信息，只需要将交易记录执行广义上两个阶段的处理，第一个阶段(MAP)对原始数据进行解析，得出结构化的、细粒度的满足分析需要的数据，第二个阶段(REDUCE)将有联系的数据汇聚到一起，按照一个公式执行计算，得到结果，保存入库。两种架构类型的称呼很多，比如可以称它们为在线服务系统和离线分析系统（以前对这种规模的批处理基本上都是线下慢慢完成，甚至是T+1、T+n的）。在本篇文章的氛围下，我们还可以称它们为：持续输入的增量计算系统、输入固定的批处理系统。简称增量系统、批处理系统。

  那web索引构建属于哪种系统呢？在以前，那肯定是批处理系统，因为网页已经被爬虫抓取过来了，存在磁盘上了，今天晚上将其制造成索引，明天投入线上使用，供人查询。这样做完全没问题，也许那个时候Google的核心矛盾不是索引更新的有多及时，而是用户输入搜索关键词之后响应有多快、返回的内容有多赞。一个新网页等个两三天才被发现完全没问题，换个邪恶的角度想想，被Google放到搜索结果里那是这个网页的福气，那是价值连城的广告，Google做到公平排序已经很给面子了，干嘛这么待见一个名不见经传的新网页？

  随着时间的推进，响应用户搜索这个环节已经不是核心矛盾，已经做到非常优秀了。Google回过头来，开始不满足于这种T+1的索引更新速度了，它希望本质上提高时效性。这当然是好事，我也希望这篇文章提交后抽根烟回来就能被搜索到。而希望提升时效性，无非就是两个方向，一是继续批处理系统的模式，想办法提升性能，做各种优化；二是做成一个在线服务系统（增量系统）。其实，如果在方向一里一直努力下去，做各种架构权衡、各种纠结取舍，也许到最后就一狠心一咬牙跳到了第二个方向上了。打个不合适的比方，就好像在绘图时，我们把CAP三原色按一定比率调成了暗色调的棕色，很好用，但现在需求变了，希望它亮一点，你可以用美图秀秀加上羽化、柔化、发光等效果，也可能希望微调一下三原色的比例来增强其本质的亮度，也许到最后，调着调着它就脱胎换骨的成了金黄色。很显然，Percolator选择了第二条路。但是这并不能得出“亮色调”优于“暗色调”的结论，它们各有所长、用于不同的场景。

  选择本质上的改革，变成一个在线服务系统，增量处理新来数据，提升了100倍的速度，Percolator，要谢的不是分布式事务和通知，而是系统定位和架构观念上的改变。所以，任何说Percolator的性能是MR的100倍的观点都是狭隘的，根本没有这回事儿。试想一下，如果你重新创办一个搜索引擎公司，你肯定要先用爬虫抓取千千万万的网页来让自己有内容可搜，然后搜索页面和查询系统都准备就绪，就差倒排索引，此时你会用一个在线服务系统去制造吗？你觉得这个时候Percolator能比MR快100倍吗？反过来都有可能吧？想想MR的优势，最大优势就是计算过程是有组织有结构的，是安排好的，既然如此，只要安排得当，那就可以尽量避免锁，也不需要事务（事务是为未知输入、随时到来的并发、故障而准备的）。相反将这么多数据全部喂给Percolator，如果不是它的内部实现非常优化，光是事务冲突就够它崩溃了。这也正是此篇论文浓墨重彩的介绍事务、通知的原因，计算过程从安排好的变成了非预期的、未知的、变化的，它的挑战也就自然的转变成了针对这种难题的事务、一致性、吞吐量等问题。

  所以从MR到Percolator，与其说是架构的变化，还不如说因为Google生态圈里其他点的成长而导致索引制造系统的定位发生了变化，以前教练让他跑马拉松，现在要它练百米。让一个常年练百米的人和一个致力于马拉松的人比速度是不科学的。但是不可否认的是最终的效果，我这篇文章从提交到在Google上出现的时间确实缩短了很多倍。

  说了这么多，只是希望读者阅读这篇论文时，先了解上述事实，然后抱着这样一种态度—— “如何构建一个无限可扩展的、高一致性的、高吞吐量的、可扩展编程模型的 增量计算系统”，来阅读本文，而不要追求究竟是什么神器提升了100倍的速度。在这篇论文里你真正能领略的，是如何构建轻量级的分布式事务、轻量级的通知机制，如何用各种各样的细节优化来弥补它们导致的性能瓶颈。它在细节上的考究真的是令人佩服，整个分布式事务就是一堆缜密的细节交织而成的，另外还有RPC合并、随机分区扫描、避免扫描凝结、locality group、异步轻量级通知、周期性通知、轻量级锁，等等，就连获取时间戳都做成了纯内存的、批量的RPC调用（那个巧妙的预分配范围、最大值持久化的细节让人印象深刻）。勇敢的做出逆天的架构决策，再追求极致的弥补它的缺陷，令人钦佩。

  ?

  英文原文：googleusercontent，编译：ImportNew?-?储晓颖

  ?

  译文链接：?http://www.importnew.com/2896.html