云计算解密：技术原理及应用实践

作者根据多年从事云计算学术研究和项目实施经历，从分布式计算的角度出发，深入浅出地对云计算的基本概念、云计算的核心实现技术及作者所在研究小组关于云计算的学术研究成果进行阐述。
本书分为三大部分：第一部分为理论篇，主要介绍分布式计算及云计算理论方面的知识；第二部分为技术篇，重点介绍云数据中心的节能技术及作业调度策略，并深入剖析MapReduce框架存在的性能问题及其优化方法；第三部分为实践篇，以PageRank算法和DNA序列拼接算法的实现为例，讲述如何使用云计算解决实际问题，并以图计算框架Hama为例，阐述对开源云计算项目的性能进行评价的方法。附录中介绍了如何搭建云计算研发环境。

2007/05－2008 /04，美国中佛罗里达大学，电子工程与计算机学院，访问学者 2003/07至今，北京交通大学，计算机与信息技术学院，副教授 2002/05－2003/06，丹麦科技大学，访问学者 2000/05－2002/04，法国国家信息与自动化研究院，博士后

目录
理 论 篇
第1章 绪论 3
1．1 计算模式演化 3
1．1．1 集中式计算模式 3
1．1．2 桌面计算模式 4
1．1．3 分布式计算模式 4
1．2 分布式计算 4
1．2．1 分布式计算概述 5
1．2．2 分布式计算结构 6
1．2．3 典型分布式计算技术 7
1．3 云计算 12
1．3．1 云计算的产生背景 12
1．3．2 云计算概述 13
1．3．3 云计算与网格计算 19
1．4 云计算的关键技术 21
1．4．1 虚拟化 21
1．4．2 资源管理与调度 21
1．4．3 文件系统 22
1．4．4 数据存储 22
1．4．5 云安全 22
1．4．6 编程模式 23
1．4．7 能耗管理 23
1．5 典型云计算平台 23
1．5．1 Google云计算平台 23
1．5．2 Amazon云计算 25
1．5．3 IBM的蓝云平台 26
1．5．4 Microsoft云计算 27
1．5．5 开源云计算平台 29
参考文献 32
第2章 并行计算编程模型 35
2．1 并行编程模型概述 35
2．1．1 共享存储编程模型 36
2．1．2 消息传递模型 37
2．1．3 分布并行编程模型 38
2．2 并行编程模型MapReduce 38
2．2．1 MapReduce概述 38
2．2．2 MapReduce编程模型 40
2．2．3 MapReduce的主要设计思想 43
2．2．4 MapReduce执行流程 44
2．2．5 MapReduce的核心技术 46
2．2．6 MapReduce技术研究 47
2．3 集群上的MapReduce实现――Hadoop 48
2．3．1 Hadoop项目简介 48
2．3．2 Hadoop与Google 53
2．3．3 MapReduce运行机制 54
2．3．4 MapReduce执行流程 60
2．3．5 MapReduce的核心技术 62
2．3．6 Hadoop YARN简介 63
2．3．7 典型案例剖析 65
2．3．8 MapReduce新旧API比较 73
2．4 MapReduce模型的其他实现 73
2．4．1 多核上的MapReduce实现 74
2．4．2 GPU上的MapReduce实现 75
参考文献 76
第3章 分布式文件系统 78
3．1 概述 78
3．1．1 什么是分布式文件系统 78
3．1．2 分布式文件系统的发展历史 79
3．1．3 分布式文件系统的体系结构 82
3．1．4 分布式文件系统的关键技术 83
3．2 GFS文件系统 84
3．2．1 GFS的设计原则 84
3．2．2 GFS体系结构 87
3．2．3 GFS工作流程 88
3．3 HDFS分布式文件系统 90
3．3．1 HDFS的设计目标 90
3．3．2 HDFS体系结构 91
3．3．3 HDFS故障处理 94
3．3．4 副本管理 94
3．3．5 HDFS工作流程 98
3．3．6 HDFS与GFS 101
3．3．7 HDFS联盟介绍 102
3．4 分布式锁服务Chubby 103
3．4．1 一致性问题 103
3．4．2 Paxos算法简介 104
3．4．3 Chubby概述 109
3．4．4 Chubby架构 110
3．5 分布式应用协调器Zookeeper 112
3．5．1 Zookeeper概述 112
3．5．2 Zookeeper的数据结构 113
3．5．3 Zookeeper架构 114
3．5．4 Zookeeper的工作原理 116
3．5．5 Zookeeper应用场景 118
3．6 云存储 119
3．6．1 概述 119
3．6．2 云存储的分类 119
3．6．3 云存储的结构模型 120
3．6．4 典型云存储系统 121
参考文献 122
第4章 分布式数据存储系统 124
4．1 概述 124
4．2 NoSQL数据库简介 125
4．2．1 NoSQL的起源与发展 125
4．2．2 NoSQL概述 126
4．2．3 NoSQL系统架构 127
4．2．4 NoSQL的数据模型 128
4．2．5 NoSQL的理论基础 131
4．2．6 NoSQL数据库体系结构 134
4．2．7 NoSQL与SQL的比较 135
4．3 面向列存储系统BigTable 136
4．3．1 概述 136
4．3．2 数据模型 137
4．3．3 系统架构 138
4．4 面向列存储系统HBase 143
4．4．1 HBase概述 143
4．4．2 HBase的数据模型 143
4．4．3 HBase架构及实现 146
4．4．4 HBase与BigTable的比较 151
参考文献 152

技 术 篇
第5章 云数据中心节能技术 157
5．1 数据中心概述 157
5．1．1 数据中心发展历史 157
5．1．2 数据中心网络结构 158
5．1．3 云数据中心 160
5．2 云数据中心节能技术 161
5．2．1 硬件设施 162
5．2．2 系统架构 162
5．2．3 软件方式 163
5．2．4 数据中心的能耗模型 166
5．3 网络感知节能调度算法DENS 167
5．3．1 DENS算法原理 167
5．3．2 DENS算法实现 168
5．3．3 改进的DENS算法 169
5．4 基于超图的存储优化节能算法 172
5．4．1 问题提出 172
5．4．2 CS方法 172
5．4．3 基于超图的副本存储优化节能算法 174
5．4．4 作业静态分配算法 176
5．4．5 动态副本迁移算法的相关分析 176
5．4．6 异构集群能效分析 177
5．4．7 覆盖集发现算法CS-k 178
5．4．8 基于超图的副本节能算法描述 178
5．4．9 实验结果及分析 182
参考文献 186
第6章 Hadoop集群的作业调度 189
6．1 集群与作业调度 189
6．1．1 集群简介 189
6．1．2 作业调度系统 192
6．1．3 经典作业调度算法 193
6．1．4 PBS作业管理系统 196
6．1．5 云环境下的作业调度 197
6．2 Hadoop的作业调度算法 200
6．2．1 Hadoop作业调度概述 200
6．2．2 批处理调度器FIFO 203
6．2．3 公平调度器 204
6．2．4 计算能力调度器 205
6．2．5 其他调度算法 207

6．3 基于伯格模型的公平调度算法 209
6．3．1 公平性概念 209
6．3．2 伯格模型概述 209
6．3．3 云计算中资源分配的伯格模型 210
6．3．4 基于伯格模型的作业调度模型 211
6．3．5 基于伯格模型的作业调度算法 217
参考文献 223
第7章 MapReduce性能优化 225
7．1 概述 225
7．1．1 MapReduce性能调优 225
7．1．2 MapReduce的性能优化研究 227
7．2 MapReduce性能模型 231
7．2．1 影响性能指标的因素 231
7．2．2 基于I/O成本的性能模型 232
7．3 Crunch概述 241
7．3．1 Crunch简介 241
7．3．2 设计思路 242
7．3．3 框架结构 245
7．3．4 工作原理 246
7．4 Crunch优化 248
7．4．1 问题的提出 248
7．4．2 Profiling 249
7．4．3 基于代价的划分 252
7．4．4 Reduce优化 253
7．4．5 数据抽样 255
7．5 实验与结果分析 255
7．5．1 实验设置 256
7．5．2 基于MapReduce的协同过滤推荐算法 256
7．5．3 验证算法正确性 259
7．5．4 验证算法有效性 260
参考文献 262
实 践 篇
第8章 云环境下的图算法PageRank 267
8．1 图计算概述 267
8．2 Web挖掘 268
8．2．1 Web挖掘概述 268
8．2．2 Web图结构分析 270
8．3 浅析PageRank算法 274
8．3．1 PageRank算法简介 274
8．3．2 PageRank算法分析 276
8．3．3 使用MapReduce思想计算PageRank值 276
8．4 基于MapReduce的PageRank算法 278
8．4．1 PageRank算法的MapReduce实现 278
8．4．2 利用矩阵分块思想的并行PageRank算法 281
8．4．3 PageRank算法实现的改进 284
8．4．4 实验及结果分析 288
8．5 基于BSP模型的PageRank算法 291
8．5．1 BSP模型 291
8．5．2 图计算框架Pregel 293
8．5．3 PageRank的Pregel实现 305
8．5．4 Pregel存在的问题 306
参考文献 306
第9章 图计算框架Hama 309
9．1 Hama简介 309
9．2 Hama核心技术 310
9．2．1 Hama层次结构 310
9．2．2 Hama体系结构 311
9．2．3 Hama代码组织 313
9．2．4 Hama常用API 315
9．2．5 基于YARN的Hama程序执行流程 317
9．3 蒙特卡罗算法的实现 318
9．3．1 用蒙特卡罗算法求圆周率 318
9．3．2 基于Hadoop的蒙特卡罗算法 319
9．3．3 基于Hama的蒙特卡罗算法 321
9．4 Hadoop与Hama的性能比较 323
9．4．1 优势区间 323
9．4．2 可用区间 325
9．4．3 劣势区间 326
9．4．4 综合分析 328
参考文献 328
第10章 基于MapReduce的DNA序列拼接 329
10．1 概述 329
10．1．1 生物信息学现状 329
10．1．2 序列拼接研究 330
10．2 测序技术 331
10．2．1 第一代DNA测序技术 331
10．2．2 第二代DNA测序技术 332
10．2．3 第三代DNA测序技术 332

10．3 序列拼接技术 332
10．3．1 序列拼接问题 333
10．3．2 序列拼接技术 333
10．4 repeat问题 337
10．4．1 聚类法 337
10．4．2 ARACHNE法 338
10．4．3 路径相容性法 338
10．5 基于MapReduce的欧拉超路并行算法 339
10．5．1 算法的选择 340
10．5．2 欧拉超路算法拼接流程 340
10．5．3 欧拉超路算法各步骤的并行化 342
10．5．4 并行欧拉超路算法性能分析 346
参考文献 350
附录A 云计算仿真器CloudSim 353
A．1 CloudSim简介 353
A．2 CloudSim体系结构 354
A．3 CloudSim核心类介绍 356
A．4 CloudSim开发环境搭建 357
A．5 仿真步骤 361
A．6 样例程序分析 363
参考文献 368
附录B Hama开发环境的搭建 369
B．1 所需软件 369
B．2 Hadoop和Hama的安装 369
B．3 搭建Hama编程环境 377
附录C 分布式Hadoop平台搭建 379
C．1 Hadoop系统的安装方式 379
C．2 硬件和软件需求 379
C．3 搭建步骤 380
C．4 运行示例程序 382