二次学习（横生枝节篇）一、初探Hadoop（1）
最近买了不少书，打算从头开始二次学习。这次学习将比较深入，包括一些硬件知识、系统软件知识、网络、编程语言、以及一些流行的编程模型，也许以后还会想到更多。刚开始的时候，一定找不到比较有效的线索，但走过一段以后，也许会有点眉目。好在这是一次长途旅行（也许是下半辈子），慢慢来。
在开始这次旅行之前，因为一些特殊的原因，要先学习几个节外生枝的内容。这些内容不是计划的一部分，至少不是刚开始要进行的。但是没有办法，今天就从Hadoop开始了。
对于Hadoop，网上有各种说法，有说它是一个实现了MapReduce计算模型的开源分布式并行编程框架，有说它是并行运算编程工具和分布式文件系统，还有说它是支持数据密集型分布应用的java框架。这些说法都从一些侧面（跟踪Hadoop的发展轨迹）描述了Hadoop的功能。但是，最权威的说法，还是要看Hadoop的官方声明。
事实上，Hadoop就是为了可靠的、可伸缩的、分布式的计算而提供的一系列开源软件。这些软件组合在一起，相互之间有各种形式的依赖。它提供的不仅仅是一个分布式的文件系统，也不仅仅是一个并行编程的框架。它正在并且将要提供一系列支持可靠的、可伸缩的、分布式计算的软件，包括数据库和数据仓库的基础设施。
Hadoop由一系列子项目组成。Hadoop Common是支持其他子项目的公用工具（原先叫Hadoop Core，后来从中分离出MapReduce和HDFS两个子项目，而保留了公共工具的部分），MapReduce是一个软件框架（顾名思义，它的基本计算模型是基于Map/Reduce），它支持大的数据集在一个计算机集群上的分布式处理，HDFS是一个分布式的文件系统，它提供对应用数据的高吞吐访问，Avro是一个数据序列化系统，它提供了与脚本语言的动态集成功能，chukwa是一个数据集合系统，它管理大的分布式系统，HBase是一个可升级的、分布式的数据库，可以支持对大表的结构化数据存储，Hive是一个数据仓库的基础设施，它提供数据汇总和即席查询，Pig是一个分析大数据集的平台，ZooKeeper是一个集中服务，用来管理配置信息，命名等。
看上去，Hadoop项目包含的内容不少。为了了解它，我们还是得简化思路。从本质上看，Hadoop的核心就是Map/Reduce计算模型的java实现，其他的都是衍生出来的应用，包括分布式文件系统（我还不确定，但姑且这么认为好了），分布式数据库等。
基于这个想法，我们不妨把目光集中在MapReduce计算模型上面。
据Michael Stonebraker（PostgreSQL的最初伯克利领导）说，作为一种技术，MapReduce的思想很早就已经提出了。
事实上，MapReduce使用的技术已经有20年了。把大数据集切分成小的分区在“Application of Hash to Data Base Machine and Its Architecture” 里作为一种新的join算法的基础就已经提出，在“Multiprocessor Hash-Based Join Algorithms”，Gerber展现了Kitsuregawa的技术如何被扩展，在shared-nothing的集群上结合分区表，分区执行，hash拆分来并行执行join。DeWitt表明这些技术可以被采用来并行执行无论有无group 语句的合并。DeWitt和Gray描述了一些并行数据库系统，以及它们如何处理查询。Shatdal和Naughton则探索了并行执行合并的替代策略。
上面的资料我都没有看过，在这里不做评论。我们先来看看MapReduce计算模型到底是什么。
MapReduce的计算模型很简单，输入和输出分别是一组键值对（Key/Value）。程序员需要指定两个函数，
1、map (k1, v1) -> list(k2, v2)
处理输入的键值对，产生中间键值对。
2、reduce (k2, list(2)) -> list(v3)
为某个键合并所有的中间值，产生一组合并后的输出值。这样说，也许还不够清晰，我们来看一张图。
假设，我们输入的是一系列文档（每一篇文档都对应到上图中input行上的一个矩形块），目标是来统计这些文档中每个单词出现的次数。我们以两篇文档为例。“hello hadoop goodbye hadoop”，“hello world bye world”。事实上，这两篇文档通常是经过split之后形成的，我们后面会谈到这一点。
经过map函数之后，这两篇文档产生了中间结果，就是上图中intermediate行。中间结果如下：
| k1：v | K2：v | k3：v |
k2：v |
| hello：1 | hadoop：1 | goodbye：1 | hadoop：1 |
| k1：v | k4：v | k5：1 | k4：1 |
| hello：1 | world：1 | bye：1 | world：1 |
接着，我们按照key来group，得到group后的结果是：
| k1：v，v，v | k2：v，v，v | k3：v，v，v | k4：v，v，v | k5：v，v，v |
| hello：1，1 | hadoop：1，1 | goodbye：1 | world：1，1 | bye：1 |
接下来，就是执行reduce函数了，在Jeffrey Dean and Sanjay Ghemawat的论文中，reduce函数就是对结果值进行简单的加法操作。所以，得到的结果是：
| hello：2 | hadoop：2 | goodbye：1 | world：2 | bye：1 |
有人也许会说，这个模型有什么用？答案是，有用。当我们把input行的矩形块打乱次序后，得到的结果和上面的演示结果是一样的。因为这个特性，我们可以把这个计算模型推到分布式计算环境中了。看下图：
我们把每个task分配到一台计算机，就可以解决并行计算了。实际上，这里还有一些概念。一次计算请求通常被称为一个job，每个job又由一系列的task组成。
作为一种计算模型，MapReduce有一些适用的场合（约束），也有一些自己的计算特点，针对MapReduce还有一些争议。这些留待下次写。