一、目录介绍

第0章 当谈论大数据时我们在谈什么
0.1   大数据是什么 2
0.2   大数据之翼：技术范型转换 4
0.3   大数据商业炼金术 6
0.4   “大数据”在路上 7

第1章 数据分片与路由
1.1   抽象模型10
1.2   哈希分片（Hash Partition） 11
1.2.1 Round Robin11
1.2.2 虚拟桶（Virtual Buckets） 12
1.2.3 一致性哈希（Consistent Hashing） 13
1.3   范围分片（Range Partition） 18
      参考文献19
      
第2章 数据复制与一致性
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章 大数据常用的算法与数据结构
3.1   布隆过滤器（Bloom Filter） 51
3.1.1 基本原理52
3.1.2 误判率及相关计算52
3.1.3 改进：计数Bloom Filter53
3.1.4 应用54
3.2   SkipList55
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 Snappy67
3.6   Cuckoo 哈希（Cuckoo Hashing） 67
3.6.1 基本原理68
3.6.2 应用：SILT 存储系统68
      参考文献70
      
第4章 集群资源管理与调度
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 抢占式调度与非抢占式调度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   YARN87
      参考文献90
      
第5章 分布式协调系统
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章 分布式通信
6.1   序列化与远程过程调用框架107
6.1.1 Protocol Buffer 与Thrift 108
6.1.2 Avro109
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章 数据通道
7.1   Log 数据收集120
7.1.1 Chukwa121
7.1.2 Scribe122
7.2   数据总线123
7.2.1 Databus125
7.2.2 Wormhole 127
7.3   数据导入／导出128
      参考文献129
      
第8章 分布式文件系统
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
第10章 列式数据库176
第11章 大规模批处理系统199
第12章 流式计算219
第13章 交互式数据分析240
第14章 图数据库：架构与算法271
第15章 机器学习：范型与架构313
第16章 机器学习：分布式算法337
第17章 增量计算366

附录A  硬件体系结构及常用性能指标378
附录B  大数据必读文献380

��