MapReduce
简介
MapReduce 是一个编程模型，也是一个处理和生成 超大数据集的算法模型的相关实现。
用户首先创建一个Map 函数处理一个基于key/value pair 的数据集合，输出中间的基于key/value pair 的 数据集合；然后再创建一个Reduce 函数，用来合并 所有的具有相同中间key 值的中间value 值。 MapReduce 架构的程序能够在大量的普通配置的计 算机上实现并行化处理。
Hadoop VS.Google
技术架构
数据结构化管理组件：Hbase→BigTable。 并行计算模型：MapReduce→MapReduce。 分布式文件系统：HDFS→GFS。 Hadoop缺少分布式锁服务Chubby。
Hadoop云计算应用
HBase MapReduce HDFS
分布式存储和计算系统
By 薛长俊 2010-12-28
Google的三驾马车
GFS
MapReduce
BigTable
返 回
GFS
简介
组件失效不再被认为是意外，而是被看做正常的现 象。常量监视器，错误侦测，容错以及自动恢复系 统集成在系统中。 文件非常巨大。 大部分文件的修改，不是覆盖原有数据，而是在文 件尾追加新数据。 应用程序和文件系统API的协同设计。
GFS
容错和诊断
高可用性。 快速恢复。不管主服务器和块服务器是如何关闭的，它们 被设计为可以在数秒钟内恢复它们的状态并启动。 块复制。每个块被复制到不同机架上的不同的块服务器上。 主节点复制。为了可靠性主服务器状态要被复制。它的操 作日志和检查点都要复制到多台机器上。 数据完整性。每个块服务器利用校验和来检查存储的数据 是否损坏。块被分为64KB的大小，每个有一个对应的32位 的校验和。 诊断工具。广泛而详尽的分析日志。
MapReduce
一般算法
MapReduce
编程模型
MapReduce
一个例子
举例：计算一个大的文档集合中每个单词出现的次数： map(String key, String value): // key: document name // value: document contents for each word w in value: EmitIntermediate(w, "1"); reduce(String key, Iterator values): // key: a word // values: a list of counts int result = 0; for each v in values: result += ParseInt(v); Emit(AsString(result));
数据模型
行 表中的行关键字可以是任意的字符串。对同一个行关 键字的读或者写操作都是原子的。Bigtable通过行关键字 的字典顺序来组织数据。 列族 关键字组成的集合叫做“列族” 。访问控制、磁盘和 内存的使用统计都是在列族层面进行的。 时间戳 在Bigtable中，表的每一个数据项都可以包含同一份 数据的不同版本，不同版本的数据通过时间戳来索引。
HDFS关键运行机制
读文件流程
客户端联系NameNode,得到所有数据块信息，以及数据块对 应的所有数据服务器的位置信息。 尝试从某个数据块对应的一组数据服务器中选出一个，进行 连接（选取算法未加入相对位置的考虑）。 数据被一个包一个包发送回客户端，等到整个数据块的数据 都被读取完了，就会断开此链接，尝试连接下一个数据块对 应的数据服务器，整个流程，依次如此反复，直到所有想读 的都读取完了为止。
GFS
设计预期
这个系统由许多廉价易损的普通组件组成。 这个系统保存一定数量的大文件。 负载中主要包含两种读操作：大规模的流式读取和 小规模随机读取。 负载中还包括许多大规模的顺序的写操作，追加数 据到文件尾部。 系统必须高效的实现良好定义的多客户端并行追加 到一个文件的语意。 高度可用的带宽比低延迟更加重要。
Google云计算应用
BigTable MapReduce Chubby GFS
Hadoop VS.Google
HDFS与GFS比较
中心服务器模式的差异。 GFS：多台物理服务器，选择一台对外服务，损坏时可选择 另外一台提供服务。 HDFS：单一中心服务器模式，存在单点故障。 原因：Hadoop缺少分布式锁服务。 安全模式的差异。 HDFS具备安全模式。获知数据块副本状态，若副本不足， 则拷贝副本至安全数目（如3个） GFS不具备安全模式。副本损坏处理：API读取副本失败时， Master负责发起拷贝任务。 HDFS具备空间回收机制。 文件删除时，仅删除目录结构 实际数据的删除在等待一段时间后实施 优点：便于恢复文件
MapReduce
备用任务
木桶效应 在运算过程中，如果有一台机器花了很长的时间才完 成最后几个Map 或Reduce 任务，会导致MapReduce 操 作总的执行时间超过预期。 流程优化 当一个MapReduce 操作接近完成的时候，master 调 度备用任务进程来执行剩下的、处于处理中状态的任务。 无论是最初的执行进程、还是备用任务进程完成了任务， 我们都把这个任务标记成为已经完成。
GFS
系统交互
GFS
创建、重新复制、负载均衡
当主服务器创建一个块，会选择哪里放置初始的空副本。 新的副本放置在低于平均硬盘使用率的块服务器。 限制每一个块服务器上"近期"创建操作的数量。 把块分布在机架之间。
一旦块的可用副本数少于用户指定的值，主服务器会重新 复制它。
主服务器周期性地对副本进行负载均衡：它检查当前的副 本分布情况，然后移动副本以得到更好的硬盘剩余空间以 及负载的均衡。
BigTable
Tablet的位置
使用一个三层的、类似Ｂ+树的结构存储Tablet的位置信息。
BigTable
Tablet服务
Hadoop
Hadoop项目简介
HDFS体系结构及关键运行机制
Hadoop VS.Google（分布式文件系统）
返 回
Hadoop项目简介
Apache的解决方案
GFS-->HDFS MapReduce-->Hadoop BigTable-->HBase

BigTable
组件
Bigtable包括了三个主要的组件：链接到客户程序中 的库、一个Master服务器和多个Tablet服务器。
Master服务器主要负责以下工作：为Tablet服务器分 配Tablets、检测新加入的或者过期失效的Tablet服务 器、对Tablet服务器进行负载均衡、以及对保存在 GFS上的文件进行垃圾收集。除此之外，它还处理对 模式的相关修改操作，例如建立表和列族。
BigTable
简介
分布式的结构化数据存储系统。 被设计用来处理海量数据：通常是分布在数千台普通 服务器上的PB级的数据。 适用性广泛、可扩展、高性能和高可用性。 Google的很多项目使用Bigtable存储数据，包括Web 索引、Google Earth、Google Finance。
空间回收机制
HDFS关键运行机制
写文件流程
客户端缓存 流水线复制 并发写控制 流程： 客户端把数据缓存到本地临时文件夹。 临时文件夹数据超过64M，客户端联系NameNode， NameNode分配DataNode，DataNode依照客户端的位置被排列 成一个有着最近物理距离和最小的序列。 与序列的第一个数据服务器建立Socket连接，发送请求头， 然后等待回应，依次下传，客户端得到回包，流水线建立成功。 正式发送数据，以4K为大小传送。
HDFS体系结构
HDFS的体系结构
NameNodeMaster。 DataNodeChunksever。
HDFS关键运行机制
可靠性保障
一个名字节点和多个数据节点 数据复制（冗余机制） --存放的位置（机架感知策略）
故障检测 --数据节点 心跳包（检测是否宕机） 块报告（安全模式下检测） 数据完整性检测（校验和比较） --名字节点（日志文件，镜像文件）
BigTable
数据模型
稀疏的、分布式的、持久化存储的多维度排序Map。 Map的索引是行关键字、列关键字以及时间戳；Map 中的每个value都是一个未经解析的byte数组。 (row:string, column:string,time:int64)->string 应用示例
BigTable
Google云计算
MapReduce GFS BigTable Chubby
Hadoop项目简介
Apache的解决方案
HDFS为了做到可靠性（reliability）创建了多份数据块 （data blocks）的复制（replicas），并将它们放置在服务 器群的计算节点中（compute nodes），MapReduce就可 以在它们所在的节点上处理这些数据了。
BigTable
API
建立、删除表及列族。 修改集群、表和列族的元数据。 写入或者删除Bigtable中的值。 从每个行中查找值。 遍历表中的一个数据子集。
BigTable
构件
Bigtable建立在其它的几个Google基础构件之上。 使用GFS存储日志文件和数据文件。 依赖集群管理系统来调度任务、管理共享的机器上的 资源、处理机器的故障、以及监视机器的状态。 内部存储数据的文件是Google SSTable格式的。 SSTable是一个持久化的、排序的、不可更改的Map 结构，而Map是一个key-value映射的数据结构，key 和value的值都是任意的Byte串。 BigTable还依赖一个高可用的、序列化的分布式锁服 务组件，叫做Chubby。