大数据日知录：架构与算法
作者：张俊林 著
出版时间：2014年版
丛编项： 大数据丛书
内容简介
大数据是当前最为流行的热点概念之一，其已由技术名词衍生到对很多行业产生颠覆性影响的社会现象，作为最明确的技术发展趋势之一，基于大数据的各种新型产品必将会对每个人的日常生活产生日益重要的影响。本书从架构与算法角度全面梳理了大数据存储与处理的相关技术。大数据技术具有涉及的知识点异常众多且正处于快速演进发展过程中等特点，其技术点包括底层的硬件体系结构、相关的基础理论、大规模数据存储系统、分布式架构设计、各种不同应用场景下的差异化系统设计思路、机器学习与数据挖掘并行算法以及层出不穷的新架构、新系统等。本书对众多纷繁芜杂的相关技术文献和系统进行了择优汰劣并系统性地对相关知识分门别类地进行整理和介绍，将大数据相关技术分为大数据基础理论、大数据系统体系结构、大数据存储，以及包含批处理、流式计算、交互式数据分析、图数据库、并行机器学习的架构与算法以及增量计算等技术分支在内的大数据处理等几个大的方向。通过这种体系化的知识梳理与讲解，相信对于读者整体系统地了解、吸收和掌握相关的优秀技术有极大的帮助与促进作用。
目录
第0章 当谈论大数据时我们在谈什么 1
0．1 大数据是什么 2
0．2 大数据之翼：技术范型转换 4
0．3 大数据商业炼金术 6
0．4 “大数据”在路上 7
第1章 数据分片与路由 9
1．1 抽象模型 10
1．2 哈希分片（Hash Partition） 11
1．2．1 Round Robin 11
1．2．2 虚拟桶（Virtual Buckets） 12
1．2．3 一致性哈希（Consistent Hashing） 13
1．3 范围分片（Range Partition） 18
参考文献 19
第2章 数据复制与一致性 20
2．1 基本原则与设计理念 21
2．1．1 原教旨CAP主义 21
2．1．2 CAP重装上阵（CAP Reloaded） 23
2．1．3 ACID原则 24
2．1．4 BASE原则 24
2．1．5 CAP/ACID/BASE三者的关系 25
2．1．6 幂等性（Idempotent） 26
2．2 一致性模型分类 26
2．2．1 强一致性 27
2．2．2 最终一致性 28
2．2．3 因果一致性 28
2．2．4 “读你所写”一致性 29
2．2．5 会话一致性 29
2．2．6 单调读一致性 30
2．2．7 单调写一致性 30
2．3 副本更新策略 30
2．3．1 同时更新 30
2．3．2 主从式更新 31
2．3．3 任意节点更新 32
2．4 一致性协议 32
2．4．1 两阶段提交协议（Two-Phrase Commit，2PC） 33
2．4．2 向量时钟（Vector Clock） 38
2．4．3 RWN协议 40
2．4．4 Paxos协议 42
2．4．5 Raft协议 45
参考文献 49
第3章 大数据常用的算法与数据结构 51
3．1 布隆过滤器（Bloom Filter） 51
3．1．1 基本原理 52
3．1．2 误判率及相关计算 52
3．1．3 改进：计数Bloom Filter 53
3．1．4 应用 54
3．2 SkipList 55
3．3 LSM树 58
3．4 Merkle哈希树（Merkle Hash Tree） 62
3．4．1 Merkle树基本原理 62
3．4．2 Dynamo中的应用 63
3．4．3 比特币中的应用 63
3．5 Snappy与LZSS算法 65
3．5．1 LZSS算法 65
3．5．2 Snappy 67
3．6 Cuckoo 哈希（Cuckoo Hashing） 67
3．6．1 基本原理 68
3．6．2 应用：SILT存储系统 68
参考文献 70
第4章 集群资源管理与调度 71
4．1 资源管理抽象模型 72
4．1．1 概念模型 72
4．1．2 通用架构 73
4．2 调度系统设计的基本问题 74
4．2．1 资源异质性与工作负载异质性 74
4．2．2 数据局部性（Data Locality） 75
4．2．3 抢占式VS．非抢占式调度 75
4．2．4 资源分配粒度（Allocation Granularity） 76
4．2．5 饿死（Starvation）与死锁（Dead Lock）问题 76
4．2．6 资源隔离方法 77
4．3 资源管理与调度系统范型 77
4．3．1 集中式调度器（Monolithic Scheduler） 78
4．3．2 两级调度器（Two-Level Scheduler） 79
4．3．3 状态共享调度器（Shared-State Scheduler） 79
4．4 资源调度策略 81
4．4．1 FIFO调度策略 81
4．4．2 公平调度器（Fair Scheduler） 81
4．4．3 能力调度器（Capacity Scheduler） 82
4．4．4 延迟调度策略（Delay Scheduling） 82
4．4．5 主资源公平调度策略（Dominant Resource Fair Scheduling） 82
4．5 Mesos 84
4．6 YARN 87
参考文献 90
第5章 分布式协调系统 91
5．1 Chubby锁服务 92
5．1．1 系统架构 93
5．1．2 数据模型 94
5．1．3 会话与KeepAlive机制 95
5．1．4 客户端缓存 95
5．2 ZooKeeper 96
5．2．1 体系结构 96
5．2．2 数据模型（Data Model） 97
5．2．3 API 98
5．2．4 ZooKeeper的典型应用场景 98
5．2．5 ZooKeeper的实际应用 103
参考文献 104
第6章 分布式通信 106
6．1 序列化与远程过程调用框架 107
6．1．1 Protocol Buffer与Thrift 108
6．1．2 Avro 109
6．2 消息队列 110
6．2．1 常见的消息队列系统 110
6．2．2 Kafka 111
6．3 应用层多播通信（Application-Level Multi-Broadcast） 114
6．3．1 概述 114
6．3．2 Gossip协议 115
参考文献 118
第7章 数据通道 120
7．1 Log数据收集 120
7．1．1 Chukwa 121
7．1．2 Scribe 122
7．2 数据总线 123
7．2．1 Databus 125
7．2．2 Wormhole 127
7．3 数据导入/导出 128
参考文献 129
第8章 分布式文件系统 131
8．1 Google文件系统（GFS） 132
8．1．1 GFS设计原则 132
8．1．2 GFS整体架构 133
8．1．3 GFS主控服务器 134
8．1．4 系统交互行为 136
8．1．5 Colossus 137
8．2 HDFS 138
8．2．1 HDFS整体架构 139
8．2．2 HA方案 140
8．2．3 NameNode 联盟 143
8．3 HayStack存储系统 145
8．3．1 HayStack整体架构 146
8．3．2 目录服务 147
8．3．3 HayStack缓存 148
8．3．4 HayStack存储系统的实现 148
8．4 文件存储布局 150
8．4．1 行式存储 151
8．4．2 列式存储 151
8．4．3 混合式存储 156
8．5 纠删码（Erasure Code） 158
8．5．1 Reed-Solomon算法 159
8．5．2 LRC编码 164
8．5．3 HDFS-RAID架构 166
参考文献 166
第9章 内存KV数据库 168
9．1 RAMCloud 169
9．1．1 RAMCloud整体架构 169
9．1．2 数据副本管理与数据恢复 170
9．2 Redis 172
9．3 MemBase 173
参考文献 175
第10章 列式数据库 176
10．1 BigTable 177
10．1．1 BigTable的数据模型 177
10．1．2 BigTable的整体结构 178
10．1．3 BigTable的管理数据 179
10．1．4 主控服务器（Master Server） 181
10．1．5 子表服务器（Tablet Server） 182
10．2 PNUTS存储系统 186
10．2．1 PNUTS的整体架构 186
10．2．2 存储单元 187
10．2．3 子表控制器与数据路由器 187
10．2．4 雅虎消息代理 188
10．2．5 数据一致性 189
10．3 Megastore 190
10．3．1 实体群组切分 191
10．3．2 数据模型 192
10．3．3 数据读/写与备份 193
10．4 Spanner 194
10．4．1 SpanServer软件栈 195
10．4．2 数据模型 196
10．4．3 TrueTime 196
参考文献 197
第11章 大规模批处理系统 199
11．1 MapReduce计算模型与架构 200
11．1．1 计算模型 201
11．1．2 系统架构 203
11．1．3 MapReduce计算的特点及不足 206
11．2 MapReduce计算模式 206
11．2．1 求和模式（Summarization Pattern） 207
11．2．2 过滤模式（Filtering Pattern） 208
11．2．3 组织数据模式（Data Organization Pattern） 210
11．2．4 Join模式（Join Pattern） 212
11．3 DAG计算模型 214
11．3．1 DAG计算系统的三层结构 214
11．3．2 Dryad 215
11．3．3 FlumeJava和Tez 217
参考文献 218
第12章 流式计算 219
12．1 流式计算系统架构 222
12．1．1 主从架构 222
12．1．2 P2P架构 223
12．1．3 Samza架构 224
12．2 DAG拓扑结构 224
12．2．1 计算节点 225
12．2．2 数据流 226
12．2．3 拓扑结构 226
12．3 送达保证（Delivery Guarantees） 229
12．3．1 Storm的送达保证机制 230
12．3．2 MillWheel的“恰好送达一次”机制 233
12．4 状态持久化 234
12．4．1 容错的三种模式 234
12．4．2 Storm的状态持久化 236
12．4．3 MillWheel和Samza的状态持久化 237
参考文献 238
第13章 交互式数据分析 240
13．1 Hive系数据仓库 242
13．1．1 Hive 242
13．1．2 StingerInitiative 250
13．2 Shark系数据仓库 251
13．2．1 Shark架构 252
13．2．2 部分DAG执行引擎（PDE） 253
13．2．3 数据共同分片 254
13．3 Dremel系数据仓库 254
13．3．1 Dremel 255
13．3．2 PowerDrill 258
13．3．3 Impala 261
13．3．4 Presto 264
13．4 混合系数据仓库 265
参考文献 269
第14章 图数据库：架构与算法 271
14．1 在线查询类图数据库 272
14．1．1 三层结构 272
14．1．2 TAO图数据库 273
14．2 常见图挖掘问题 277
14．2．1 PageRank计算 278
14．2．2 单源最短路径（Single Source Shortest Path） 278
14．2．3 二部图最大匹配 279
14．3 离线挖掘数据分片 279
14．3．1 切边法（Edge-Cut） 280
14．3．2 切点法（Vertex-Cut） 282
14．4 离线挖掘计算模型 284
14．4．1 以节点为中心的编程模型 284
14．4．2 GAS编程模型 285
14．4．3 同步执行模型 286
14．4．4 异步执行模型 290
14．5 离线挖掘图数据库 292
14．5．1 Pregel 292
14．5．2 Giraph 299
14．5．3 GraphChi 301
14．5．4 PowerGraph 307
参考文献 311
第15章 机器学习：范型与架构 313
15．1 分布式机器学习 314
15．1．1 机器学习简介 314
15．1．2 数据并行VS．模型并行 316
15．2 分布式机器学习范型 317
15．2．1 三种范型 318
15．2．2 MapReduce迭代计算模型 319
15．2．3 BSP计算模型 321
15．2．4 SSP模型 323
15．3 分布式机器学习架构 324
15．3．1 MapReduce系列 325
15．3．2 Spark及MLBase 327
15．3．3 参数服务器（Parameter Server） 332
参考文献 335
第16章 机器学习：分布式算法 337
16．1 计算广告：逻辑回归 338
16．1．1 逻辑回归（Logistic Regression，LR） 338
16．1．2 并行随机梯度下降（Parallel Stochastic Gradient Descent） 341
16．1．3 批学习并行逻辑回归 341
16．2 推荐系统：矩阵分解 344
16．2．1 矩阵分解方法 344
16．2．2 ALS-WR算法 346
16．2．3 并行版ALS-WR算法 347
16．3 搜索引擎：机器学习排序 347
16．3．1 机器学习排序简介 348
16．3．2 LambdaMART 349
16．3．3 分布式LambdaMART 351
16．4 自然语言处理：文档相似性计算 352
16．5 社交挖掘：谱聚类 355
16．5．1 社交挖掘实例 355
16．5．2 谱聚类 356
16．5．3 并行版谱聚类 358
16．6 深度学习：DistBelief 358
16．6．1 深度学习简介 359
16．6．2 DistBelief 360
参考文献 364
第17章 增量计算 366
17．1 增量计算模式 367
17．1．1 两种计算模式 367
17．1．2 Hadoop平台下增量计算的一般模式 368
17．2 Percolator 370
17．2．1 事务支持 371
17．2．2 “观察/通知”体系结构 373
17．3 Kineograph 374
17．3．1 整体架构 375
17．3．2 增量计算机制 375
17．4 DryadInc 376
参考文献 377
附录A 硬件体系结构及常用性能指标 378
附录B 大数据必读文献 380
