Google的索引更新速度提升了100倍

经典论文翻译导读之《Large-scaleIncrementalProcessingUsingDistributedTransactionsandNotifications》英文原文：googleusercontent，编译：ImportNew-储晓颖【译者导读】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之所以不能有效重复利用上一次的工作成果，其中一个原因是索引制造的计算不是“mergablecomputation”。mergable用数学公式表达就是：在mergable函数y=f(x)中，对于x中任意的子集x1和x2，此公式可以表示为y=l(m(x1),n(x2))。也就是说x中的数据无论怎么切分，都可以逐一基于上一次的结果进行计算。译者找到另一篇incoop的论文，它用MR的视角来诠释了传统的MR为何不适合增量计算：如图所示，假设Firstrun中Reduce的结果为A，在第二次计算时(2)出现了，要为它执行增量计算，能不能直接将(2)的值与A进行计算得到新的结果？答案是不一定。假如这个MR仅仅是对1到23各个数据进行求和，那就可以直接将A+(2)得到新的值（这就是mergablecomputation）。假如不是mergable（比如是将1、2、3、5的和与6到23的和相除），不仅1、2、3、5要重新计算，6到23都需要重新计算（因为MR仅仅保存了最终Reduce结果，丢失了中间计算结果）。这就是为何Google要重复的执行全量的MR。对于此问题，译者曾发邮件给作者DanielPeng，他的回复是：Therearepartialresultsoftheindexcomputationthatareneededinthenextincrementalstep.Inthemapreducecase,itisnoteasytosaveandretrievethesepartialresults.Inpercolator,it’seasytostorethesepartialresultsandretrievethemforthenexttimetheyareneeded.邮件中可以看到两个关键性词语。第一个是“partialresults”，它强调了在索引计算中需要的不仅是上一轮的最终结果，更需要局部的、中间的计算结果，从某种意义上可以简单的理解为计算是unmergable的；第二个是“noteasytosaveandretrieve”，这个突出了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服务（原文为timestamporacle，下文中所有“时间戳oracle”、“oracle”都是指此服务，译者注）和轻量锁服务。时间戳oracle提供了严格的递增时间戳：快照隔离协议需要依赖此属性。Worker需要使用轻量锁服务来更加高效的搜索“脏”通知（“脏”原文dirty，意指某个数据发生了改变，等待后续处理，后续“脏”都为此含义，译者注）。从开发者视角，一个Percolator库包含少量的table。每个table是“cell”的集合（某一行的某一列就是一个cell）。每个cell包含一个值，某类cell为支持快照隔离，会包含按时间戳索引的一系列的值。有两个前提影响着Percolator设计，一是必须运行在大规模数据上，二是并不要求非常低的延迟。不严格的延迟要求让我们采用了一个懒惰的途径来清理故障机器上被事务遗留下的锁。这个途径虽懒惰但实现很简单，不过它可能会导致事务延缓提交几十秒钟。这个延缓在DBMS运行OLTP任务时是无法接受的，但是在增量处理系统创建web索引时可以忍受。另外，Percolator的事务管理缺乏一个中央总控：尤其是它缺少一个全局死锁检测器。这增加了事务冲突时的延迟，但是却可以帮助系统伸缩至几千台机器。2.1Bigtable概览Percolator建立在Bigtable分布式存储系统之上。Bigtable对用户呈现了一个多维度排序的map：map的keys是指（行、列、时间戳）元组。Bigtable为每个行提供查询和更新操作，而且Bigtable的行事务能够支持单行的原子“读-修改-写”操作。Bigtable处理PB级别数据，能够可靠地运行在大数量的（不可靠）机器上。一个运行中的Bigtable包含一批tablet服务器，每个负责服务多个tablet（key空间内连续的域）。一个master负责协调控制各tablet服务器的操作，比如指示它们装载或卸载tablet。一个tablet在GoogleSSTable上被存储为一系列只读的文件。SSTable被存储在GFS；Bigtable依靠GFS来保护数据以防磁盘故障。Bigtable允许用户控制table的执行特征，比如将一批列分配为一个localitygroup。localitygroup中的列被存储在独立隔离的SSTable集合中，在其他列不需要被扫描时可以有效降低扫描成本。基于Bigtable来构建Percolator，也就大概确定了Percolator的架构样式。Percolator充分利用了Bigtable的接口：数据被组织到Bigtable行和列中，P