IT新技术课题报告
C i
Google大数据技术
专业名称：软件工程
姓名：王六平
2019年9月11日
2019年一9月
2019年9月日
11 目录
一、 简述 ................................................... 4 二、 Google经典三篇大数据论文介绍 ........................... 5
2.1、 GFS ..................................................................................... 5 2.2、 MapReduce ......................................................................... 6 2.3、 BigTable —个分布式的结构化数据存储系统 ........... 7 三、 Google新大数据论文介绍 ................................ 8
1
、 \\ j
f'
_ / ［亠*
3.1、 Caffeine :处理个体修改 ............................ 8 3.2、 Pregel :可扩展的图计算 ............................. 9 3.3、 Dremel :在线可视化 .............................. 11 四、Google大数据的应用 .................................... 14
2019年一9月
一、大数据时代的来临 1. 大数据的概念：
按照维基百科上的定义，所谓“大数据” （big data ）在当今的互联网业指 的是这样一种现象：一个网络公司日常运营所生成和积累用户网络行为的数据 “增长如此之快，以至于难以使用现有的数据库管理工具来驾驭”。这些数据量 是如此之大，已经不是以我们所熟知的多少 G和多少T为单位来衡量，而是以P （1000个T）, E （—百万个T）或Z（ 10亿个T）为计量单位，所以称之为大数 据。
大数据泛指巨量的数据集，因可从中挖掘出有价值的信息而受到重视。
《华
尔街日报》将大数据时代、智能化生产和无线网络革命称为引领未来繁荣的三大
\\ 1
$
I 一-^
技术变革。麦肯锡公司的报告指出数据是一种生产资料，大数据是下一个创新、 竞争、生产力提高的前沿。世界经济论坛的报告认定大数据为新财富，价值堪比 石油。因此，发达国家纷纷将开发利用大数据作为夺取新一轮竞争制高点的重要 抓手。
2. 大数据的发展
I f
Ji'1 ..
I
互联网特别是移动2互联网的发展，加快了信息化向社会经济各方面、大众 日常生活的渗透。有资料显示，1998年全球网民平均每月使用流量是 1MB（兆字 节），2000 年是 10MB 2003 年是 100MB 2008 年是 1GB（ 1GB等于 1024MB， 2014年将是10GB全网流量累计达到1E（即10亿GB或 1000PB的时间在2001
I /
年是一年，在2004年是一个月，在 2007年是一周，而2013年仅需一天，即一 天产生的信息量可刻满1.88亿张DVD光盘。我国网民数居世界之首，每天产生 的数据量也位于世界前列。淘宝网站每天有超过数千万笔交易， 单日数据产生量 超过50TB （仃B等于1000GB，存储量40PB （1PB等于1000TB。百度公司目 前数据总量接近1000PB存储网页数量接近1万亿页，每天大约要处理60亿次 搜索请求，几十PB数据。一个8Mbp（兆比特每秒）的摄像头一小时能产生3.6GB 数据，一个城市若安装几十万个交通和安防摄像头，
每月产生的数据量将达几十
2019年一9月
PB医院也是数据产生集中的地方。现在，一个病人的CT影像数据量达几十GB 而全国每年门诊人数以数十亿计， 并且他们的信息需要长时间保存。 总之，大数 据存在于各行各业，一个大数据时代正在到来。
信息爆炸不自今日起，但近年来人们更加感受到大数据的来势迅猛。 一方面， 网民数量不断增加，另一方面，以物联网和家电为代表的联网设备数量增长更快。 2007年全球有5亿个设备联网，人均0.1个；2013年全球将有500亿个设备联 网，人均70个。随着宽带化的发展，人均网络接入带宽和流量也迅速提升。全 球新产生数据年增40%即信息总量每两年就可以翻番，这一趋势还将持续。目 前，单一数据集容量超过几十TB甚至数PB已不罕见，其规模大到无法在容许的 时间内用常规软件工具对其内容进行抓取、管理和处理。
数据规模越大，处理的难度也越大，但对其进行挖掘可能得到的价值更大， 这就是大数据热的原因。
3. 大数据的特征：
r
大数据（Big Data）是指“无法用现有的软件工具提取、存储、搜索、共享、 分析和处理的海量的、复杂的数据集合”。业界通常用四个V来概括大数据的特 征。
数据体量巨大（Volume）。至U目前为止，人类生产的所有印刷材料的数据量 是200PB （1PB=210TB，而历史上全人类说过的所有的话的数据量大约
5EB
（1EB=210PB。当前，典型个人计算机硬盘的容量为 TB量级，而一些大企业的 数据量已经接近EB量级。
数据类型繁多（Variety）。这种类型的多样性也让数据被分为结构化数据和 非结构化数据。相对于以往便于存储的以文本为主的结构化数据，
非结构化数据
越来越多，包括网络日志、音频、视频、图片、地理位置信息等，这些多类型的 数据对数据的处理能力提出了更高要求。
价值密度低（Value）。价值密度的高低与数据总量的大小成反比。以视频 为例，一部1小时的视频，在连续不间断的监控中，有用数据可能仅有一两秒。 2019
年一9月
如何通过强大的机器算法更迅速地完成数据的价值“提纯”，成为目前大数据背 景下亟待解决的难题。
处理速度快(Velocity )。这是大数据区分于传统数据挖掘的最显着特征。根 据IDC的“数字宇宙”报告，预计到 2020年，全球数据使用量将达到 35.2ZB (1ZB=210EB。在如此海量的数据面前，处理数据的效率就是企业的生命
二、Google经典三篇大数据论文介绍
Google 在 2003 年到 2006 年公布了关于 GFS Map Reduce® BigTable 三 篇技术论文。
2.1、GFS
公布时间：2003年。
GFS阐述了 Google File System的设计原理，GFS是一个面向大规模数据密 集型应用的、可伸缩的分布式文件系统。GFS虽然运行在廉价的普遍硬件设备上， 但是它依然了提供灾难冗余的能力，为大量客户机提供了高性能的服务。
虽然GFS的设计目标与许多传统的分布式文件系统有很多相同之处， 但是， 我们设计还是以我们对自己的应用的负载情况和技术环境的分析为基础的，
不管
现在还是将来，GFS和早期的分布式文件系统的设想都有明显的不同。所以我们 重新审视了传统文件系统在设计上的折衷选择，衍生出了完全不同的设计思路。
GFS完全满足了我们对存储的需求。GFS作为存储平台已经被广泛的部署 在Google内部，存储我们的服务产生和处理的数据，同时还用于那些需要大规 模数据集的研究和开发工作。
目前为止，最大的一个集群利用数千台机器的数
千个硬盘，提供了数百TB的存储空间，同时为数百个客户机服务。
为了满足Google迅速增长的数据处理需求，我们设计并实现了 Google文件 系统(Google File System - GFS。GFS与传统的分布式文件系统有着很多相同 的设计目标，比如，性能、可伸缩性、可靠性以及可用性。但是，我们的设计还 基于我们对我们自己的应用的负载情况和技术环境的观察的影响，
不管现在还是
2019年一9月
将来，GFS和早期文件系统的假设都有明显的不同。 所以我们重新审视了传统文 件系统在设计上的折衷选择，衍生出了完全不同的设计思路
首先，组件失效被认为是常态事件，而不是意外事件。 GFS包括几百甚至 几千台普通的廉价设备组装的存储机器， 同时被相当数量的客户机访问。GFS组 件的数量和质量导致在事实上，任何给定时间内都有可能发生某些组件无法工 作，某些组件无法从它们目前的失效状态中恢复。我们遇到过各种各样的问题， 比如应用程序bug、操作系统的bug、人为失误，甚至还有硬盘、内存、连接 器、网络以及电源失效等造成的问题。所以，持续的监控、错误侦测、灾难冗余 以及自动恢复的机制必须集成在 GFS中。
其次，以通常的标准衡量，我们的文件非常巨大。数
GB的文件非常普遍。
每个文件通常都包含许多应用程序对象， 比如web文档。当我们经常需要处理快 速增长的、并且由数亿个对象构成的、数以 TB的数据集时，采用管理数亿个 KB 大小的小文件的方式是非常不明智的，尽管有些文件系统支持这样的管理方式。 因此，设计的假设条件和参数，比如I/O操作和Block的尺寸都需要重新考虑。
第三，绝大部分文件的修改是采用在文件尾部追加数据，而不是覆盖原有 数据的方式。对文件的随机写入操作在实际中几乎不存在。
一旦写完之后，对文
件的操作就只有读，而且通常是按顺序读。大量的数据符合这些特性，比如：数 据分析程序扫描的超大的数据集；正在运行的应用程序生成的连续的数据流；存 档的数据；由一台机器生成、另外一台机器处理的中间数据， 这些中间数据的处 理可能是同时进行的、也可能是后续才处理的。对于这种针对海量文件的访问模 式，客户端对数据块缓存是没有意义的，数据的追加操作是性能优化和原子性保 证的主要考量因素。
第四，应用程序和文件系统API的协同设计提高了整个系统的灵活性。比如, 我们放松了对GFS 一致性模型的要求，这样就减轻了文件系统对应用程序的苛 刻要求，大大简化了 GFS的设计。我们引入了原子性的记录追加操作，从而保 证多个客户端能够同时进行追加操作，不需要额外的同步操作来保证数据的一致 性。本文后面还有对这些问题的细节的详细讨论。
2019年一9月
Google已经针对不同的应用部署了多套 GFS集群。最大的一个集群拥有超 过1000个存储节点，超过300TB的硬盘空间，被不同机器上的数百个客户端连 续不断的频繁访问。 2.2、MapReduce
公布时间：2004年。
MapReduce是一个编程模型，也是一个处理和生成超大数据集的算法模型的 相关实现。用户首先创建一个 Map函数处理一个基于key/value pair的数据集 合，输出中间的基于key/value pair
的数据集合；然后再创建一个 Reduce函
数用来合并所有的具有相同中间key值的中间value值。现实世界中有很多满 足上述处理模型的例子，本论文将详细描述这个模型。
Map Reduce架构的程序能够在大量的普通配置的计算机上实现并行化处 理。这个系统在运行时只关心：如何分割输入数据，在大量计算机组成的集群上 的调度，集群中计算机的错误处理，管理集群中计算机之间必要的通信。采用
MapReduce架构可以使那些没有并行计算和分布式处理系统开发经验的程序员 有效利用分布式系统的丰富资源。
我们的MapReduce实现运行在规模可以灵活调整的由普通机器组成的集群 上: 一个典型的MapReduce^算往往由几千台机器组成、处理以TB计算的数据。 程序员发现这个系统非常好用：已经实现了数以百计的
MapReduce序，在
Google的集群上，每天都有1000多个Map Reduces序在执行。 2.3 BigTable 一个分布式的结构化数据存储系统
公布时间：2006年。
Bigtable是一个分布式的结构化数据存储系统，它被设计用来处理海量数 据：通常是分布在数千台普通服务器上的 PB级的数据。Google的很多项目使用 Bigtable 存储数据，包括 Web索引、Google Earth、Google Finance 。这些 应用对Bigtable提出的要求差异非常大，无论是在数据量上（从
URL到网页到
卫星图像）还是在响应速度上（从后端的批量处理到实时数据服务）。尽管应用
2019年一9月
需求差异很大，但是，针对 Google的这些产品，Bigtable还是成功的提供了一 个灵活的、高性能的解决方案。本论文描述了 Bigtable提供的简单的数据模型， 利用这个模型，用户可以动态的控制数据的分布和格式。
老三篇即使我们常用的Hadoop系统的设计理论基石。虽然Google没有公布 这三个产品的源码，但是根据google发布了这三个产品的详细设计论文。
而且,
Yahoo资助的Hadoop也有按照这三篇论文的开源 Java实现:Hadoop对应 Map reduce, Hadoop Distributed File System (HDFS) 对应 Google fs,Hbase 对应Bigtable。不过在性能上 Hadoop比Google要差很多
三、Google新大数据论文介绍
「i z? '/
Hadoop来源自Google在2003年底和2004年发表的两篇研究论文。 第一篇 介绍了 Google File System，它是一个可扩展的分布式文件系统，用于大型的、 分布式的、对大量数据进行访问的应用。它运行于廉价的普通电脑服务器上， 可以提供容错功能并且可以给大量的用户提供总体性能较高的服务； 的是MapReduce这是是一种编程模型，用于大规模数据集(大于 运算，能够极大地方便编程人员在不会分布式并行编程的情况下
但
另一篇介绍 仃B)的并行
，将自己的程序
运行在分布式系统上。八年之后，Hadoop在网络上得到了广泛的使用，应用领 域涉及数据分析到各种这样的数值计算任务。 但Google却研发出了更好的技术。
2009年，网络巨头 Google开始用新的技术取代 Google File System 和 MapReduce相应替代的理论基础来自以下三篇论文为主导 :Caffeine、Pregel、 Dremelo
3.1、Caffeine :处理个体修改
公布时间：2010年。
Google并没有止步于 Map Reduce事实上，随着In ternet 的指数增长，从 零
2019年一9月
开始重算所有搜索索引变得不切实际。取而代之， Google开发了一个更有价
值的系统，同样支持分布式计算系统。Google Caffeine是google全球数据中 心网络上的新的搜索基础设施 --------- 是基于分布式数据处理系统
Percolator的。
Percolator引入了事务，而一些NoSQ数据库仍然在强调得到高扩展性的同时 你必须牺牲（或者不再需要）事务处理。它是一个增量处理平台一一一种可以持 续更新Google公司的核心搜索索引而不需要从头开始处理所有数据的方法。
在本质上Caffeine丢弃MapReduce专而将索引放置在由Google开发的分布 式数据库BigTable上。作为Google继GFS和Map Reduce两项创新后的又一项创 新，其在设计用来针对海量数据处理情形下的管理结构型数据方面具有巨大的优 势。这种海量数据可以定义为在云计算平台中数千台普通服务器上
PB级的数据。
在本论文中，Google展示了其网络搜索是如何保持着与时俱进。Percolator 建立于已存类似Bigtable的技术，但是加入了事务以及行和表上的锁和表变化 的通知。这些通知之后会被用于触发不同阶段的计算。通过这样的方式，个体的 更新就可以“渗透”整个数据库。这种方法会让人联想到类似 Storm（或者是Yahoo 的S4）的流处理框架（SPF，然而Percolator内在是以数据作为基础。SPF 使用的一般是消息传递而不是数据共享，这样的话更容易推测出究竟是发生了什 么。然而问题也随之产生：除非你手动的在某个终端上储存，否则你将无法访问 计算的结果。
Caffeine大大提升了 google搜索速度。在原有的系统中，Google公司每天 爬数以亿万计的文档，把它们和现有文档的集合一起经过约 100次MapReduce 工序进行处理。由于系统是顺序的，每个文档都要花2到3天来索引才能出现在 google的在线搜索结果中。
Percolator提供对现有的PB级索引数据的随机访问，让 google可以更新 索引而不需要重新处理所有数据， 通过这种方式减少了这个延迟。“随机访问让 我们可以处理单个文档，而不是像 MapReduce那样需要对整个数据仓库进行扫 描。”论文中说道。该系统运行于海量计算机上，通过被称作 事务的方式，并行的对索引进行大量修改。
ACID兼容数据库
2019年一9月
3.2、 Pregel :可扩展的图计算
公布时间：2010年。
最终Google还需要挖掘图数据，比如在线社交网络的社交图谱；所以他们 开发了 Pregel，并在2010年公布其论文。
Pregel是一个川「分和弍图说薛的计算柜架 匸扱叩」：图迓川（BFS）、最短 路径（SSSP）、PageRank计身斗— 艾曰射川勺运刁片仃很移 但是応」- google IX矿=台机器早已经放不下需耍计算的数据了 讲以需耍分彳忒的这样一吓- 计算环境。没有Pregel乙市」川MapReduce来做,但是效率很低；也可以用已有 的并行图算法库Parallel BGL或者CGMgraph来做，但是这两者又没有容错。
Pregel内在的计算模型比MapReduce复杂的多：基本上每个节点都拥有一 个工作者线程，并且对众多工作者线程进行迭代并行。在每一个所谓的
“ superstep ”中，每一个工作者线程都可以从节点的“收件夹”中读取消息和 把消息发送给其它节点，设置和读取节点相关值以及边界，或者投票停止。线程 会一直运行，直到所有的节点都被投票停止。此外，还拥有 Combi ner做全局统计。
论文陈述了许多算法的实现，比如 Google的PageRank最短路径、二分图 匹配等。对比Map Reduce或 SPF Pregel需要更多实现的再思考。
■_
] |
f
1
Aggregator和
3.3、 Dremel :在线可视化
公布时间：2010年。
面对海量数据的分析处理， Map Reduce的优势不需多言，其劣势在于时效 性较差不满足交互式查询的需求，比如 3秒内完成对万亿数据的一次查询等， Dremel应此需求而生，与Map Reduce成为有效互补。
Dremel是一个为结构化数据设计，并拥有类 SQL语言的交互式数据库。然 而取代SQL数据库使用字段填补的表格，Dremel中使用的是类JSOh格式数据（更 准
2019年一9月
确的说，使用Google?Protocol buffer格式，这将加强对允许字段的限制）。 内部，数据被使用特殊格式储存，可以让数据扫描工作来的更高效。 查询被送往 服务器，而优秀的格式可以最大性能的输出结果。
这篇论文描述了一个叫做Dremel的系统，它支持在普通PC组成的共享集群 上对超大规模的数据集合执行交互式查询。
不像传统的数据库，它能够操作原位
嵌套数据。原位意味着在适当的位置访问数据的能力， 比如，在一个分布式文件 系统（比如GFS或者其他存储层（比如Bigtable ）。查询这些数据一般需要一 系列的Map Reduce壬务，而Dremel可以同时执行很多，而且执行时间比
Map Reduce小得多。Dremel不是为了成为 Map Reduce的替代品，而是经常与它协 同使用来分析MapReduce管道的输出或者创建大规模计算的原型系统。
Dremel自从2006就投入生产了并且在 Google有几千用户。多种多样Dremel 的实例被部署在公司里，排列着成千上万个节点。使用此系统的例子包括：
分析网络文档
追踪An droid市场应用程序的安装数据 Google产品的崩溃报告分析 Google Books 的 OCF结果 垃圾邮件分析
Google Maps里地图部件调试 托管Bigtable实例中的Tablet迁移 Google分布式构建系统中的测试结果分析 成百上千的硬盘的磁盘IO统计信息 Google数据中心上运行的任务的资源监控 Google代码库的符号和依赖关系分析
Dremel基于互联网搜索和并行DBMS勺概念。首先，它的架构借鉴了用在分 布
2019年一9月
式搜索引擎中的服务树概念。就像一个web搜索请求一样，查询请求被推入此 树、在每个步骤被重写。通过聚合从下层树节点中收到的回复， 不断装配查询的 最终结果。其次，Dremel提供了一个高级、类SQL的语言来表达ad-hoc查询。 与Pig和Hive不同，它使用自己技术执行查询，而不是翻译为Map Reduce任务。
最后也是最重要的，Dremel使用了一个column-striped 的存储结构，使得 它能够从二级存储中读取较少数据并且通过更廉价的压缩减少
CPU消耗。列存储
曾被采用来分析关系型数据，但是据我们了解还没有推广到嵌套数据模型上。我 们所展现的列状存储格式在Google已经有很多数据处理工具支持，包括 MapReduce Sawzall、以及 Flume Java。
四、Google大数据的应用
保护野生老虎
谷歌强调的第一个例子是使用谷歌地图的数据来保护野生老虎。 借助谷歌地 图海量的卫星图像和地理数据库资源，以及强大的处理分析能力，米尼苏达大学 的科学家完成了他们在重点地区恢复老虎的栖息地的研究。
这个研究团队测量了过去14年里，全世界76个老虎栖息地面积缩小的数据。他 们发现，老虎栖息地的退化速度远远高于森林面积的退化速度。 只有在尼泊尔和 印度这样拥有老虎栖息地保护区的国家， 老虎的数量得到了增长。这两个国家老 虎的数量分别增长了 61唏口 31%
这个研究中最让人惊奇的是，大部分的研究都通过使用卫星图片信息完成的，
I. 1
这
些信息全部通过谷歌地球免费获得的。 比如，你可以在谷歌地球中输入全球的任 何一个位置，然后你就可以通过地球资源卫星图片，看到该地点是如何随着时间 的迁移而变化的。 “天窗计划”
谷歌另一个有意思的研究项目是“天窗计划”。 “天窗计划”可以预估在房顶安 装太阳能设备后可以节省的开支。谷歌地球的图像库里拥有全年的日照情况和天 气变化数据，“天窗计划”可以计算安装太阳能板的屋顶空间，判断使用太阳能 带来的价值和可以节省的能源费用，并将用户与太阳能电池板提供商连接起来。 这是我们对不断扩大的数据库的又一创新使用：
帮助我们对重大项目作出更明智
2019年一9月
的决定。在这个案例中，能源消耗就是这个重要项目。目前，全美41个州的4300 多万户居民可以使用“天窗计划”。用户提供一个指标，它就可以来可以测算出 可能节省的开支，以及并网发电后可能带来的收益。通过测算你的房子或地区进 行独特定制，最终推动太阳能在更大范围的使用。 治理空气污染
第三个例子由Google Earth Outreach 和环境守护基金（the Environmental Defense Fund）牵头完成。他们测量了铺设在道路下的天然气管道的甲烷泄露情 况。
谷歌通过适配谷歌街景（Google Streetview） 汽车来完成这一任务。这些汽车携 带甲烷分析器，在街道行驶并绘制道路地图。这意味着这些汽车在为
Google地
图获取街景图片内容的同时，他们也在以半秒钟为时间单位，测量所在街道甲烷 的浓度。使用这些数据，研究小组可以标记哪里存在甲烷的泄露以及泄露的程度。 “我们发现泄露的程度从平均一英里一个泄露点位 （波士顿）到两百英里一个
（印
第安纳波利斯）不等。通过分些这些数据，研究小组得出了很多实用的信息。比 如，在管线建设中，使用塑料管道的效果会比使用铸铁管道更好。“ 链接：
• Google File System 中文版 • Google MapReduce 中文版 • Google BigTable 中文版
• Big Data bey ond MapReduce: Google's Big Data papers?
（编译/仲浩 审校/王旭东）
2019年一9月
因篇幅问题不能全部显示，请点此查看更多更全内容