2.1 Google的计算框架

要说起Hadoop，我们必然要提到Google。Google是最早提出云计算概念的公司，也是大数据时代的先行者之一。Google旗下的Google搜索、Google地图、gmail邮箱、Picasa图像存储和YouTube视频（被Google收购的视频网站领袖）分享等诸多基于互联网的产品服务都是建立在海量数据之上，由Google的大数据计算框架所支撑。

面对大数据，Google采用了分布式存储和并行计算方法，构建了GFS文件系统、MapReduce计算模型和BigTable非关系型数据库组成的基础平台，用来支撑自家的产品和服务。

GFS、MapReduce、BigTable可以称为Google（早期）基础平台的三个支柱。

2.1.1 Google公司的三篇论文

我们来看图2-1。

从图2-1中我们看到：

（1）从Google文件系统衍生出了Hadoop HDFS；

（2）从Google的MapReduce框架衍生出了Hadoop MapReduce；

（3）从Google的BigTable衍生出了Apache HBase。

而HDFS、MapReduce框架和HBase恰恰是Hadoop的三个核心组件。

对于有钻研精神的同学，我们建议可以去读读Google的三篇研究文章。这三篇文章是Google的GFS、MapReduce和BigTable系统的基础，而且最终成就了Hadoop。

（1）http://research.google.com/archive/gfs.html，关于GFS的论文：The Google File System, Google文件系统。

（2）http://research.google.com/archive/MapReduce.html，关于MapReduce框架的论文：MapReduce: Simplified Data Processing on Large Clusters, MapReduce：在大规模集群上的简单化数据处理。

（3）http://research.google.com/archive/bigtable.html，关于BigTable的论文：BigTable: A Distributed Storage System for Structured Data, BigTable：结构化数据的分布式存储系统。

虽然Google公司没有公开这三个系统的源代码，但是通过这三篇论文，我们基本能够知道所有的执行细节。

而Doug Cutting正是从这三篇论文出发，搭建了最初的Hadoop系统。

2.1.2 GFS文件系统

谷歌的创始人Larry Page在斯坦福大学时设计和实现了称为BigFiles的文件系统，用于存储下载的网页。在Google公司成立之后，面对服务器数量的不断增多和数据量不断增长的情况，谷歌工程师在BigFiles成果上研制出了GFS（Google File System）文件系统，其结构如图2-2所示。该文件系统解决了大数据在廉价硬件上的分布式存储问题，和早期计算机系统的文件系统相比，有不少新颖之处。

GFS文件系统认为组件失效不再是意外，而是一种系统必须接受的正常现象。Google为了降低成本没有采用超级计算机或者高性能的计算机，而是把所有产品和服务建立在大量廉价服务器甚至由普通PC组成的集群之上，由集群代替超级计算机提供存储和计算能力。由于Google构成集群的单台服务器性能一般，可靠性差且经常出问题，Google工程师以此为基础假设，在系统的整体处理能力和容错性上精心设计，使GFS文件系统具有数据冗余和容错机制，可以自动应对单台服务器宕机和数据丢失风险。

其次，GFS文件系统是专为大文件存储而设计的，对大文件读写操作的参数和通道进行了优化。存储在GFS上的数据文件通常都很大，一般在100MB以上，几个GB甚至几十GB的文件也很常见，GFS把大文件分块存储，文件块（File Chunk）固定大小为64MB，这也和由大量小文件组成的传统文件系统环境非常不同。

GFS作的假设是：

（1）对大文件最频繁的两项操作是顺序读取和在文件末尾追加新数据；

（2）数据一旦写入改写的需求极少；

（3）文件随机写的操作几乎不存在；

（4）如果需要执行随机写的操作，整个大文件需要重新生成。

GFS由单一主服务器（Master）和众多存储服务器（Chunk Server）组成，主服务器上存储的是文件的名字空间等元数据，而存储服务器存放具体数据。所有的数据都有多份冗余，以文件块（chunk）的形式在多台存储器上存放。

2.1.3 MapReduce的模型和框架

当我们有大量数据需要处理的时候，对某一个单独的服务器进行性能的提升其方式毕竟是有限的，除了添加内存和提升CPU的主频之外没有太多良策。于是大家就想到了并行计算，通过增加新的服务器的方式让整体的服务器处理速度加快。

在互联网时代数据量的不断增长迫使越来越多的程序采用并行计算来处理问题，然而开发并行计算程序难度不小。一些传统应用，如网页爬取、Web请求的日志分析等，要实现其并行算法，必须解决数据分发、错误处理、负载均衡等一系列问题，相关的代码不仅异常复杂而且难以维护。

Google的研究人员发现，大量并行计算应用可以由Map（映射）和Reduce（简化）两个过程组成的程序模型描述，只要开发人员完成Map和Reduce两个过程，其余程序可以标准化处理。于是Google的工程师在GFS基础上实现了称为MapReduce的计算框架，封装了并行计算的复杂性，使普通的开发人员也能较容易地写出并行计算程序。

简而言之，MapReduce就是一种编程模型，用于大规模数据集（大于1TB）的并行运算，能够极大地方便不会分布式并行编程的编程人员，将自己的程序运行在分布式系统上。

MapReduce程序模型和计算框架在谷歌内部应用非常广泛，Google利用MapReduce实现了分布排序、分布Grep、Web连接图反转、Web访问日志分析、反向索引构建、文档聚类、机器学习、基于统计的机器翻译等众多程序和功能，MapReduce还成为Google的索引更新方式。实践证明，MapReduce框架的效率和功能都是不错的。

2.1.4 BigTable数据库

大数据对传统关系型数据库（Relational DataBase Management System, RDBMS）造成了很大的冲击，关系型数据库并发能力无法处理每秒上万次的读写请求，而且关系型数据库在存储了上亿条记录时，查询效率非常低。最重要的一点是关系型数据库很难横向扩展，当数据量大时无法通过简单添加服务器的方法提高其性能和负载能力，而且在对数据库进行升级扩展时又必须停机和进行数据迁移。

Google设计和实现了一个名为BigTable的数据库，这是一个专门为管理大规模结构化数据而设计的分布式存储数据库。BigTable放宽了数据事务要求，因为Google的大多数Web应用程序并不要求严格的数据库事务，对读一致性要求很低，一些场合甚至对写一致性要求也不高。很多Web应用程序设计时采用单表主键查询及简单条件分页查询，避免了多表关联查询，所以BigTable弱化了SQL功能，有利于存储和性能的提升。

在BigTable产品研发出来之后，Google公司把BigTable部署在上千台服务器上，可以可靠地处理PB级数据，支撑包括谷歌地图（Google Earth）、谷歌分析（Google Analytics）、谷歌金融（Google Finance）等60多个应用。受BigTable启发，Cassandra和HBase等各个非关系型数据库延续着BigTable设计思路迅速发展起来。

BigTable的表（Table）在本质上是一个key-value（键-值）对映射，由行键、列键、时间戳三维定位一条字符记录值。其中行是表的第一级索引，列是表的第二级索引，时间戳是第三级，每行拥有的列不受限制，可以每一行都不相同。如果多个列是属于同一族类的，可以用一个列族来表示这些列，表达方式为Family:Qualifier，每个列族都有同样的Family值。可以用这样的公式表示BigTable表中的数据：

        (row:string, column:string, time:int64)→string

图2-3是Google论文中的一个示例，描述一张网页在BigTable中是如何存储的。

图中www.cnn.com是表的行键，以URL逆向排列然后按字母顺序存储，即最后一段com出现在最前面，而第一段www出现在最后，所以www.cnn.com对应的存储是com.cn.www。contents是一个列键，对应的是网页内容；而anchor是一个列族，包含了cnnsi.com和my.look.ca两个反向链接的列键。contents列下存放t3、t5、t6三个时间点的页面内容，cnnsi.com和my.look.ca列下只存放一份链接值，因为链接值并不因为时间而变化。

在Jeffrey Dean提出MapReduce计算理念之后，MapReduce的想法被技术圈子的很多人认可。但是，Google并没有公开太多关于MapReduce实现的细节。