2010—2011学年上学期读书笔记
从暑假入学开始，开始接触或者更深刻的认识云计算、MapReduce、Hadoop、Xen虚拟机、物联网等概念及相应机理的学习和研究，我本人有自己的一个学习习惯，学任何东西前先要查查这个词是什么意思或者起源在那，否者就会心里不舒服，所以我的学习也是从概念开始的：
云计算（cloud computing）是一种基于因特网的超级计算模式，在远程的数据中心里，成千上万台电脑和服务器连接成一片电脑云。因此，云计算甚至可以让你体验每秒10万亿次的运算能力，拥有这么强大的计算能力可以模拟核爆炸、预测气候变化和市场发展趋势。用户通过电脑、笔记本、手机等方式接入数据中心，按自己的需求进行运算。
侠义的云：指IT基础设施的交付和使用模式，指通过网络以按需、易扩展的方式获得所需的资源(硬件、平台、软件)。提供资源的网络被称“云”。“云”中的资源在使用者看来是可以无限扩展的，并且可以随时获取，按需使用，随时扩展，按使用付费。这种特性经常被称为像水电一样使用IT基础设施。
广义的云：指服务的交付和使用模式，指通过网络以按需、易扩展的方式获得所需的服务。这种服务可以是IT和软件、互联网相关的，也可以是任意其他的服务。
云计算的原理：云计算(Cloud Computing)是分布式处理(Distributed Computing)、并行处理(Parallel Computing)和网格计算(Grid Computing)的发展，或者说是这些计算机科学概念的商业实现。
云计算的基本原理是，通过使计算分布在大量的分布式计算机上，而非本地计算机或远程服务器中，企业数据中心的运行将更与互联网相似。这使得企业能够将资源切换到需要的应用上，根据需求访问计算机和存储系统。这可是一种革命性的举措，打个比方，这就好比是从古老的单台发电机模式转向了电厂集中供电的模式。它意味着计算能力也可以作为一种商品进行流通，就像煤气、水电一样，取用方便，费用低廉。最大的不同在于，它是通过互联网进行传输的。云计算的蓝图已经呼之欲出：在未来，只需要一台笔记本或者一个手机，就可以通过网络服务来实现我们需要的一切，甚至包括超级计算这样的任务。从这个角度而言，最终用户才是云计算的真正拥有者。云计算的应用包含这样的一种思想，把力量联合起来，给其中的每一个成员使用。
这里网格计算的定义是：网格计算通过利用大量异构计算机的未用资源（CPU周期和磁盘存储），将其作为嵌入在分布式电信基础设施中的一个虚拟的计算机集群，为解决大规模的计算问题提供了一个模型。网格计算的焦点放在支持跨管理域计算的能力，这使它与传统的计算机集群或传统的分布式计算相区别。
MapReduce的定义：MapReduce是一种编程模型，用于大规模数据集（大于1TB）的并行运算。概念“Map（映射）”和“Reduce（化简）”，和他们的主要思想，都是从函数式编程语言里借来的，还有从矢量编程语言里借来的特性。他极大地方便了编程人员在不会分布式并行编程的情况下,将自己的程序运行在分布式系统上。 当前的软件实现是指定一个Map（映射）函数，用来把一组键值对映射成一组新的键值对，指定并发的Reduce（化简）函数，用来保证所有映射的键值对中的每一个共享相同的键组。
Hadoop的定义：Hadoop是Apache软件基金会所研发的开放源码并行运算编程工具和分布式文件系统，与MapReduce和Google档案系统的概念类似。
一个分布式系统基础架构，由Apache基金会开发。用户可以在不了解分布式底层细节的情况下，开发分布式程序。充分利用集群的威力高速运算和存储。Hadoop实现了一个分布式文件系统（Hadoop Distributed File System），简称HDFS。HDFS有着高容错性的特点，并且设计用来部署在低廉的（low-cost）硬件上。而且它提供高传输率（high throughput）来访问应用程序的数据，适合那些有着超大数据集（large data set）的应用程序。HDFS放宽了（relax）POSIX的要求（requirements）这样可以流的形式访问（streaming access）文件系统中的数据。
物联网的定义：上世纪末的时候提出了物联网的概念。英文名称是“The Internet of things”，从此看出，物联网就是“物-物相连的互联网”。这里有两层意思：第一，物联网的核心和基础依然是互联网，是在互联网基础上的扩展和延伸的更大的网络；第二，其用户端延伸和扩展到了物品和物品之间的信息交换和通讯。物联网的严格定义是：通过射频识别（RFID）、红外感应器、全球定位系统、激光扫描器等信息传感设备，按约定的协议，把任何物品与互联网连接起来，进行信息交
1
换和通讯，以实现智能化识别、定位、跟踪、监控和管理的一种网络。
（一）了解了基本概念之后，我精读了陶老师推荐的几篇论文：
第一篇，MapReduce：Simplified Data Processing on Large Cluster，这篇文章主要有8个部分构成：简介、编程模式、实现、改良、功能、感受实验结果、相关工作、结论。
MapReduce是由Google公司发明，近些年新兴的分布式计算模型。作为Google公司的核心技术，MapReduce在处理T级别以上巨量数据的业务上有着明显的优势。本文从分布式计算的历史背景开始，论述了MapReduce的灵感源泉及基本原理。
Google公司的MapReduce实现是该公司的保密技术，而来自开源社区 Apache的Hadoop项目则是此思想的java克隆版本。最近，Stanford大学提出的Phoenix项目将MapReduce应用于共享存储结构的硬件平台上，取得了一定的成果。本文重点论述，此三者在实现上的关键技术区别。
MapReduce基本原理介绍：在过去的数年里，Google的许多员工已经实现了数以百计的为专门目的而写的计算，用来处理大量的原始数据。比如爬虫文档、Web请求日志等等。为了计算各种类型的派生数据，比如倒排索引，Web文档的图结构的各种表示，每个主机上爬行的页面数量的概要，每天被请求数量最多的集合，等等。很多这样的计算在概念上很容易理解。然而，输入的数据量很大，并且只有计算被分布在成百上千的机器上才能在可以接受的时间内完成。怎样并行计算，分发数据，处理错误，所有这些问题综合在一起，使得原本很简洁的计算，因为要大量的复杂的代码来处理这些问题，而变得让人难以处理。作为对这个复杂性的回应，Google公司的Jeffery Dean设计一个新的抽象模型，使我们只要执行的简单计算，而隐藏并行化、容错、数据分布、负载均衡的那些杂乱细节则放在一个库里，不必关心它们。此类抽象模型的灵感来自Lisp和许多函数语言的map和reduce的原始表示。事实上许多计算都包含这样的操作：在我们输入数据的逻辑记录上应用map操作，来计算出一个中间key/value对集；在所有具有相同key的value上应用reduce操作，来适当地合并派生的数据。功能模型的使用，再结合用户指定的map和reduce操作，让我们可以非常容易地实现容错。这个工作的主要贡献是通过简单有力的接口来实现自动的并行化和大规模分布式计算，结合这个接口的实现在大量普通的PC机上实现高性能计算。
计算利用一个输入key/value对集，来产生一个输出key/value对集。MapReduce库的用户用两个函数表达这个计算：map和reduce。用户自定义的马屁函数，接受一个输入对，然后产生一个中间key/value对集。MapReduce库把所有具有相同key I的中间valuce聚合在一起，然后把它们传递给reduce函数。用户自定义的reduce函数，接受一个中间key I和相关的一个value集。它合并这些value，形成一个比较小的value集。一般的，每次reduce调用只产生0或1个输出value。通过一个迭代器把中间value提供给用户自定义的reduce函数。这样可以使我们根据内存来控制value列表的大小。
实例：计算单词数wordcount。 考虑这个问题：计算在一个大的文档集合中每个词出现的次数。用户将写出和下面类似的伪代码：
map(String key, String value): //key: 文档的名字 //value：文档的内容
For each word w in value :
Emit Intermediate(w, “1”) ;
Reduce(String key, Iterator values) : //key: 一个词
//values: 一个计数列表 Int result=0;
For each v in values: Emit(AsString(resut));
2
Map函数产生每个词和这个词的出现次数（在这个简单的例子里就是1）。Reduce函数把产生的每一个特定的词的计数加在一起。另外，用户用输入输出文件的名字和可选的调节参数来填充一个mapreduce规范对象。用户然后调用MapReduce函数，并把规范对象传递给它。用户的代码和MapReduce库链接在一起。
类型；
即使前面的伪代码写成了字符串输入和输出的term格式，但是概念上用户写的map和reduce函数有关联的类型：
Map（k1，v1）→list（k2，v2） Reduce（k2，list（v2））→list（v2）
例如输入的key，value和输出的key，value的域不同。此外，中间key，value和输出key，values的域相同。我们的C++实现传递字符串和用户自定义的函数交互，并把它留给用户的代码，来在字符串和适当的类型间进行转换。
其他的一些实例，如分布式的Grep、计算URL访问频率、倒转网络链接图、每个主机的术语向量、倒排索引、分布式排序等一些让人感兴趣的简单程序，可以容易的用MapReduce计算来表示。
MapReduce的实现：
这里主要介绍下Google的MapReduce实现。
我们的环境是:
1.Linux操作系统,双处理器,2-4GB内存的机器.
2.普通的网络硬件,每个机器的带宽或者是百兆或者千兆,但是平均小于全部带宽的一半. 3.因为一个机群包含成百上千的机器,所有机器会经常出现问题.
4.存储用直接连到每个机器上的廉价IDE硬盘.一个从内部文件系统发展起来的分布式文件系统被用来管理存储在这些磁盘上的数据.文件系统用复制的方式在不可靠的硬件上来保证可靠性和有效性.
5.用户提交工作给调度系统.每个工作包含一个任务集,每个工作被调度者映射到机群中一个可用的机器集上.
执行预览
通过自动分割输入数据成一个有M个split的集,map调用被分布到多台机器上.输入的split能够在不同的机器上被并行处理.通过用分割函数分割中间key,来形成R个片(例如，hash(key) mod R),reduce调用被分布到多台机器上.分割数量(R)和分割函数由用户来指定.
图1显示了我们实现的MapReduce操作的全部流程.当用户的程序调用MapReduce的函数的时候,将发生下面的一系列动作(下面的数字和图1中的数字标签相对应)：
3