Google关于大数据处理的论文简述
Google关于大数据处理的论文简述7
2013年4月
目录
一、简述 (3)
二、Google经典三篇大数据论文介绍 (3)
2.1、GFS (3)
2.2、MapReduce (5)
2.3、BigTable一个分布式的结构化数据存储系统 (6)
三、Google新大数据论文介绍 (6)
3.1、Caffeine：处理个体修改 (7)
3.2、Pregel：可扩展的图计算 (8)
3.3、Dremel：在线可视化 (8)
四、总结 (12)
一、简述
Google在2003年开始陆续公布了关于GFS、MapReduce和BigTable三篇技术论文，这也成为后来云计算发展的重要基石，为数据领域工作者开启了大数据算法之门。然而Google的大数据脚步显然不止于此，其后公布了Percolator、Pregel、Dremel、Spanner等多篇论文。没有止步的不仅是Google，很多公司也跟随其脚步开发了很多优秀的产品，虽然其中不乏模仿。主流的大数据基本都是MapReduce的衍生，然而把目光聚焦到实时上就会发现：MapReuce 的局限性已经渐渐浮现。下面将讨论一下自大数据开始，Google公布的大数据相关技术，以及这些技术的现状。
从2010年之后Google在后Hadoop时代的新“三驾马车”——Caffeine、Pregel、Dremel再一次影响着全球大数据技术的发展潮流。但这还远远不够，目前Google内部使用的大数据软件Dremel使大数据处理起来更加智能。
二、Google经典三篇大数据论文介绍
Google在2003年到2006年公布了关于GFS、MapReduce和BigTable 三篇技术论文。
三篇论文主要阐述：
2.1、GFS
公布时间：2003年。
GFS阐述了Google File System的设计原理，GFS是一个面向大规模数据密集型应用的、可伸缩的分布式文件系统。GFS虽然运行在廉价的普遍硬件设备上，但是它依然了提供灾难冗余的能力，为大量客户机提供了高性能的服务。
虽然GFS的设计目标与许多传统的分布式文件系统有很多相同之处，但是，我们设计还是以我们对自己的应用的负载情况和技术环境的分析为基础的，不管现在还是将来，GFS和早期的分布式文件系统的设想都有明显的不同。所
以我们重新审视了传统文件系统在设计上的折衷选择，衍生出了完全不同的设计思路。
GFS完全满足了我们对存储的需求。GFS作为存储平台已经被广泛的部署在Google内部，存储我们的服务产生和处理的数据，同时还用于那些需要大规模数据集的研究和开发工作。目前为止，最大的一个集群利用数千台机器的数千个硬盘，提供了数百TB的存储空间，同时为数百个客户机服务。
为了满足Google迅速增长的数据处理需求，我们设计并实现了Google文件系统(Google File System –GFS)。GFS 与传统的分布式文件系统有着很多相同的设计目标，比如，性能、可伸缩性、可靠性以及可用性。但是，我们的设计还基于我们对我们自己的应用的负载情况和技术环境的观察的影响，不管现在还是将来，GFS 和早期文件系统的假设都有明显的不同。所以我们重新审视了传统文件系统在设计上的折衷选择，衍生出了完全不同的设计思路。
首先，组件失效被认为是常态事件，而不是意外事件。GFS 包括几百甚至几千台普通的廉价设备组装的存储机器，同时被相当数量的客户机访问。GFS 组件的数量和质量导致在事实上，任何给定时间内都有可能发生某些组件无法工作，某些组件无法从它们目前的失效状态中恢复。我们遇到过各种各样的问题，比如应用程序bug 、操作系统的bug 、人为失误，甚至还有硬盘、内存、连接器、网络以及电源失效等造成的问题。所以，持续的监控、错误侦测、灾难冗余以及自动恢复的机制必须集成在GFS 中。
其次，以通常的标准衡量，我们的文件非常巨大。数GB的文件非常普遍。每个文件通常都包含许多应用程序对象，比如web文档。当我们经常需要处理快速增长的、并且由数亿个对象构成的、数以TB的数据集时，采用管理数亿个KB大小的小文件的方式是非常不明智的，尽管有些文件系统支持这样的管理方式。因此，设计的假设条件和参数，比如I/O 操作和Block的尺寸都需要重新考虑。
第三，绝大部分文件的修改是采用在文件尾部追加数据，而不是覆盖原有数据的方式。对文件的随机写入操作在实际中几乎不存在。一旦写完之后，对文件的操作就只有读，而且通常是按顺序读。大量的数据符合这些特性，比如：数据分析程序扫描的超大的数据集；正在运行的应用程序生成的连续的数据流；存档的数据；由一台机器生成、另外一台机器处理的中间数据，这些中间数据的处理可能是同时进行的、也可能是后续才处理的。对于这种针对海量文件的访问模
式，客户端对数据块缓存是没有意义的，数据的追加操作是性能优化和原子性保证的主要考量因素。
第四，应用程序和文件系统API的协同设计提高了整个系统的灵活性。比如，我们放松了对GFS 一致性模型的要求，这样就减轻了文件系统对应用程序的苛刻要求，大大简化了GFS 的设计。我们引入了原子性的记录追加操作，从而保证多个客户端能够同时进行追加操作，不需要额外的同步操作来保证数据的一致性。本文后面还有对这些问题的细节的详细讨论。
Google已经针对不同的应用部署了多套GFS 集群。最大的一个集群拥有超过1000个存储节点，超过300TB的硬盘空间，被不同机器上的数百个客户端连续不断的频繁访问。
2.2、MapReduce
公布时间：2004年。
MapReduce是一个编程模型，也是一个处理和生成超大数据集的算法模型的相关实现。用户首先创建一个Map函数处理一个基于key/value pair 的数据集合，输出中间的基于key/value pair 的数据集合；然后再创建一个Reduce 函数用来合并所有的具有相同中间key 值的中间value 值。现实世界中有很多满足上述处理模型的例子，本论文将详细描述这个模型。
MapReduce架构的程序能够在大量的普通配置的计算机上实现并行化处理。这个系统在运行时只关心：如何分割输入数据，在大量计算机组成的集群上的调度，集群中计算机的错误处理，管理集群中计算机之间必要的通信。采用MapReduce架构可以使那些没有并行计算和分布式处理系统开发经验的程序员有效利用分布式系统的丰富资源。
我们的MapReduce实现运行在规模可以灵活调整的由普通机器组成的集群上：一个典型的MapReduce计算往往由几千台机器组成、处理以TB计算的数据。程序员发现这个系统非常好用：已经实现了数以百计的MapReduce程序，在Google的集群上，每天都有1000多个MapReduce程序在执行。
2.3、BigTable一个分布式的结构化数据存储系统
公布时间：2006年。
Bigtable是一个分布式的结构化数据存储系统，它被设计用来处理海量数据：通常是分布在数千台普通服务器上的PB级的数据。Google的很多项目使用Bigtable存储数据，包括Web索引、Google Earth、Google Finance 。这些应用对Bigtable提出的要求差异非常大，无论是在数据量上（从URL 到网页到卫星图像）还是在响应速度上（从后端的批量处理到实时数据服务）。尽管应用需求差异很大，但是，针对Google的这些产品，Bigtable还是成功的提供了一个灵活的、高性能的解决方案。本论文描述了Bigtable提供的简单的数据模型，利用这个模型，用户可以动态的控制数据的分布和格式。
老三篇即使我们常用的Hadoop系统的设计理论基石。虽然Google没有公布这三个产品的源码，但是根据google发布了这三个产品的详细设计论文。而且，Yahoo资助的Hadoop也有按照这三篇论文的开源Java实现:Hadoop对应Mapreduce, Hadoop Distributed File System (HDFS)对应Google fs,Hbase对应Bigtable。不过在性能上Hadoop比Google要差很多
三、Google新大数据论文介绍
Hadoop来源自Google在2003年底和2004年发表的两篇研究论文。第一篇介绍了Google File System，它是一个可扩展的分布式文件系统，用于大型的、分布式的、对大量数据进行访问的应用。它运行于廉价的普通电脑服务器上，但可以提供容错功能并且可以给大量的用户提供总体性能较高的服务；另一篇介绍的是MapReduce，这是是一种编程模型，用于大规模数据集（大于1TB）的并行运算，能够极大地方便编程人员在不会分布式并行编程的情况下,将自己的程序运行在分布式系统上。八年之后，Hadoop在网络上得到了广泛的使用，应用领域涉及数据分析到各种这样的数值计算任务。但Google却研发出了更好的技术。
2009年，网络巨头Google开始用新的技术取代Google File System和MapReduce。相应替代的理论基础来自以下三篇论文为主导:Caffeine、Pregel、
Dremel。
3.1、Caffeine：处理个体修改
公布时间：2010年。
Google并没有止步于MapReduce。事实上，随着Internet的指数增长，从零开始重算所有搜索索引变得不切实际。取而代之，Google开发了一个更有价值的系统，同样支持分布式计算系统。Google Caffeine是google全球数据中心网络上的新的搜索基础设施——是基于分布式数据处理系统Percolator的。Percolator引入了事务，而一些NoSQL数据库仍然在强调得到高扩展性的同时你必须牺牲（或者不再需要）事务处理。它是一个增量处理平台——一种可以持续更新Google公司的核心搜索索引而不需要从头开始处理所有数据的方法。
在本质上Caffeine丢弃MapReduce转而将索引放置在由Google开发的分布式数据库BigTable上。作为Google继GFS和MapReduce两项创新后的又一项创新，其在设计用来针对海量数据处理情形下的管理结构型数据方面具有巨大的优势。这种海量数据可以定义为在云计算平台中数千台普通服务器上PB级的数据。
在本论文中，Google展示了其网络搜索是如何保持着与时俱进。Percolator 建立于已存类似Bigtable的技术，但是加入了事务以及行和表上的锁和表变化的通知。这些通知之后会被用于触发不同阶段的计算。通过这样的方式，个体的更新就可以“渗透”整个数据库。这种方法会让人联想到类似Storm（或者是Yahoo 的S4）的流处理框架（SPF），然而Percolator内在是以数据作为基础。SPF 使用的一般是消息传递而不是数据共享，这样的话更容易推测出究竟是发生了什么。然而问题也随之产生：除非你手动的在某个终端上储存，否则你将无法访问计算的结果。
Caffeine大大提升了google搜索速度。在原有的系统中，Google公司每天爬数以亿万计的文档，把它们和现有文档的集合一起经过约100次MapReduce 工序进行处理。由于系统是顺序的，每个文档都要花2到3天来索引才能出现在google的在线搜索结果中。
Percolator提供对现有的PB级索引数据的随机访问，让google可以更新索引而不需要重新处理所有数据，通过这种方式减少了这个延迟。“随机访问让
我们可以处理单个文档，而不是像MapReduce那样需要对整个数据仓库进行扫描。”论文中说道。该系统运行于海量计算机上，通过被称作ACID兼容数据库事务的方式，并行的对索引进行大量修改。
3.2、Pregel：可扩展的图计算
公布时间：2010年。
最终Google还需要挖掘图数据，比如在线社交网络的社交图谱；所以他们开发了Pregel，并在2010年公布其论文。
Pregel是一个用于分布式图计算的计算框架主要用于图遍历(BFS)、最短路径(SSSP)、PageRank计算等等。共享内存的运行库有很多但是对于google 来说一台机器早已经放不下需要计算的数据了所以需要分布式的这样一个计算环境。没有Pregel之前用MapReduce来做,但是效率很低;也可以用已有的并行图算法库Parallel BGL或者CGMgraph来做,但是这两者又没有容错。
Pregel内在的计算模型比MapReduce复杂的多：基本上每个节点都拥有一个工作者线程，并且对众多工作者线程进行迭代并行。在每一个所谓的“superstep”中，每一个工作者线程都可以从节点的“收件夹”中读取消息和把消息发送给其它节点，设置和读取节点相关值以及边界，或者投票停止。线程会一直运行，直到所有的节点都被投票停止。此外，还拥有Aggregator和Combiner做全局统计。
论文陈述了许多算法的实现，比如Google的PageRank、最短路径、二分图匹配等。对比MapReduce或SPF，Pregel需要更多实现的再思考。
3.3、Dremel：在线可视化
公布时间：2010年。
面对海量数据的分析处理，MapReduce的优势不需多言，其劣势在于时效性较差不满足交互式查询的需求，比如3秒内完成对万亿数据的一次查询等，Dremel应此需求而生，与MapReduce成为有效互补。
Dremel是一个为结构化数据设计，并拥有类SQL语言的交互式数据库。然而取代SQL数据库使用字段填补的表格，Dremel中使用的是类JSON格式数据（更准确的说，使用Google Protocol buffer格式，这将加强对允许字段的限制）。内部，数据被使用特殊格式储存，可以让数据扫描工作来的更高效。查询被送往服务器，而优秀的格式可以最大性能的输出结果。
这篇论文描述了一个叫做Dremel的系统，它支持在普通PC组成的共享集群上对超大规模的数据集合执行交互式查询。不像传统的数据库，它能够操作原位嵌套数据。原位意味着在适当的位置访问数据的能力，比如，在一个分布式文件系统（比如GFS或者其他存储层（比如Bigtable）。查询这些数据一般需要一系列的MapReduce任务，而Dremel可以同时执行很多，而且执行时间比MapReduce小得多。Dremel不是为了成为MapReduce的替代品，而是经常与它协同使用来分析MapReduce管道的输出或者创建大规模计算的原型系统。
Dremel自从2006就投入生产了并且在Google有几千用户。多种多样Dremel的实例被部署在公司里，排列着成千上万个节点。使用此系统的例子包括：
●分析网络文档
●追踪Android市场应用程序的安装数据
●Google产品的崩溃报告分析
●Google Books的OCR结果
●垃圾邮件分析
●Google Maps里地图部件调试
●托管Bigtable实例中的Tablet迁移
●Google分布式构建系统中的测试结果分析
●成百上千的硬盘的磁盘IO统计信息
●Google数据中心上运行的任务的资源监控
●Google代码库的符号和依赖关系分析
Dremel基于互联网搜索和并行DBMS的概念。首先，它的架构借鉴了用在分布式搜索引擎中的服务树概念。就像一个web搜索请求一样，查询请求被推入此树、在每个步骤被重写。通过聚合从下层树节点中收到的回复，不断装配查询的最终结果。其次，Dremel提供了一个高级、类SQL的语言来表达ad-hoc 查询。与Pig和Hive不同，它使用自己技术执行查询，而不是翻译为MapReduce 任务。
最后也是最重要的，Dremel使用了一个column-striped的存储结构，使得它能够从二级存储中读取较少数据并且通过更廉价的压缩减少CPU消耗。列存储曾被采用来分析关系型数据，但是据我们了解还没有推广到嵌套数据模型上。我们所展现的列状存储格式在Google已经有很多数据处理工具支持，包括MapReduce、Sawzall、以及Flume Java。
关于Dremel的效率：
论文中描述如下：Dremel每个月扫描千之五次方条记录。我们采样了某个月的查询记录，统计出耗时分布曲线。如图15所示，大部分查询低于10秒，在交互型查询的耗时容忍范围内。一些查询会在共享集群上执行接近于100 billion条记录每秒的全量扫描，在专用机器上这个值还要更高。通过对上述实验数据进行观察，我们可以得到如下结论：
●我们可以在磁盘常驻的数据集合上对万亿级记录执行基于扫描的查询，
并达到交互式速度。
●在几千个节点范围内，列数量和服务器数量的可伸缩性、可扩展性是接
近线性的。
●MapReduce也可以从列状存储中得益，就像一个DBMS。
●记录装配和解析是昂贵的。软件层（在查询处理层之上）最好被优化，
能够直接消费面向列的数据
●MapReduce和查询处理可以互为补充；一个层的输出能作为另一个的
输入。
●在一个多用户环境，规模较大的系统能得益于高性价比的可伸缩能力，
而且本质上改善用户体验。
●如果能接受细微的精度损失，查询速度可以更快。
●互联网级别的海量数据集合可以做到很快速的扫描，但想要花费更少的
时间则很困难。
●Dremel的代码库包含少于100K行的C++ Java和Python 代码
hadoop和Dremel对比：
Dremel是个数据分析工具，经专门设计用于完成大规模查询结构化数据集（如日志和事件文件）。它支持类SQL语法，区别在于它是只读的。不支持修改或者建立功能，也没有表索引。数据被列式存储，这样有助于提升查询的速度。Google的BigQuery就是Dremel通过RESTful API的一种实现。
Hadoop（MapReduce的一种开源实现）集合了“Hive”数据仓库软件，同样允许使用SQL语句对大量的数据集进行数据分析。Hive本质上是把查询转换成MapReduce运算。对比使用ColumIO格式，Hive则是使用表索引的思想去优化查询。
Hadoop更多的则是用于批处理，这就意味着数据是运行在你已经拥有的数据集上。有数据流入时，流引擎会进行处理。“流”和“实时”通常被互换使用，这也是导致Dremel和Drill混淆的原因，通常都会把它们归类成延时。
值得注意的是Google只是打算将Dremel作为MapReduce的一种补充，而不是替换。通过论文也可以得知，Dremel被频繁的用于分析MapReduce的结果或者是作为大规模计算的测试。Dremel可以做那些通常需要一系列MapReduce才可以完成的查询，但是花费的时间只是使用MapReduce的一小部分。如前所述，Dremel从速度上完全超越MapReduce。
Google Dremel 和Apache Drill对比:
Apache Drill更像是Google Drill的开原版本。OpenDremel，另一个创建Dremel开源版本的项目。当然还有一些其他支持大数据快速查询的项目，比如：Apache CouchDB和Cloudant的演变版本BigCouch。
除了Drill外，还有其他一些大数据分析工具和技术
1. Storm ——Backtype开发并被Twitter开源。
2. Apache S4 ——Yahoo！开源。
而流引擎就是这些实时大数据处理系统（比如Storm和S4）与Dremel的最大区别，当然Dremel是专门针对查询设计。
四、总结
目前国内提起大数据就不能不说Hadoop，而Hadoop的火爆要得益于Google在2003年底和2004年公布的两篇研究论文，其中一份描述了GFS （Google File System），GFS是一个可扩展的大型数据密集型应用的分布式文件系统，该文件系统可在廉价的硬件上运行，并具有可靠的容错能力，该文件系统可为用户提供极高的计算性能，而同时具备最小的硬件投资和运营成本。另外一篇则描述了MapReduce，MapReduce是一种处理大型及超大型数据集并生成相关执行的编程模型。其主要思想是从函数式编程语言里借来的，同时也包含了从矢量编程语言里借来的特性。基于MapReduce编写的程序是在成千上万的普通PC机上被并行分布式自动执行的。8年后，Hadoop已经被广泛使用在网络上，并涉及数据分析和各类数学运算任务。但Google却提出更好的技术。在2009年，网络巨头开始使用新的技术取代GFS和MapReduce。这些技术代表未来的趋势。
自Hadoop兴起以来，Google已经发布了三篇研究论文，主要阐述了基础设施如何支持庞大网络操作。其中一份详细描述了Caffeine，Caffeine主要为Google网络搜索引擎提供支持。
在Google采用Caffeine之前，Google使用MapReduce和分布式文件系统（如GFS）来构建搜索索引（从已知的Web页面索引中）。在2010年，Google 搜索引擎发生了重大变革。Google将其搜索迁移到新的软件平台，他们称之为“Caffeine”。Caffeine是Google出自自身的设计，Caffeine使Google能够更迅速的添加新的链接（包括新闻报道以及博客文章等）到自身大规模的网站索引系统中，相比于以往的系统，新系统可提供“50%新生”的搜索结果。
另一篇介绍了Pregel，Pregel主要绘制大量网上信息之间关系的“图形数
据库”。而最吸引人的一篇论文要属被称之为Dremel的工具。全球很多技术都落后于Google，而Google自身的技术也正在影响全球。在Google思路以及论文的启发下，同样涌现出一些开源项目，比如：Apache Drill、Apache Giraph、斯坦福GPS等等。Google近年来每篇论文都有着深远的影响，同时大数据领域内有很多人必然在翘首以盼Google的下一篇论文。