第0 章 当谈论大数据时我们在谈什么 1
0.1 大数据是什么2
0.2 大数据之翼:技术范型转换.4
0.3 大数据商业炼金术6
0.4 “大数据”在路上.7
第1 章 数据分片与路由 9
1.1 抽象模型.10
1.2 哈希分片(HashPartition) 11
1.2.1 RoundRobin11
1.2.2 虚拟桶(VirtualBuckets) 12
1.2.3 一致性哈希(ConsistentHashing) .13
1.3 范围分片(RangePartition) 18
参考文献19
第2 章 数据复制与一致性20
2.1 基本原则与设计理念21
2.1.1 原教旨CAP 主义21
2.1.2 CAP 重装上阵(CAPReloaded).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-PhraseCommit,2PC)33
2.4.2 向量时钟(VectorClock) 38
2.4.3 RWN 协议.40
2.4.4 Paxos 协议.42
2.4.5 Raft 协议.45
参考文献49
第3 章 大数据常用的算法与数据结构51
3.1 布隆过滤器(BloomFilter) 51
3.1.1 基本原理.52
3.1.2 误判率及相关计算52
3.1.3 改进:计数BloomFilter53
3.1.4 应用54
3.2SkipList55
3.3 LSM 树58
3.4 Merkle 哈希树(MerkleHash 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.2Snappy67
3.6 Cuckoo 哈希(CuckooHashing) 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 数据局部性(DataLocality) 75
4.2.3 抢占式调度与非抢占式调度.75
4.2.4 资源分配粒度(AllocationGranularity) .76
4.2.5 饿死(Starvation)与死锁(Dead Lock)问题.76
4.2.6 资源隔离方法77
4.3 资源管理与调度系统范型.77
4.3.1 集中式调度器(MonolithicScheduler).78
4.3.2 两级调度器(Two-LevelScheduler) .79
4.3.3 状态共享调度器(Shared-StateScheduler) 79
4.4 资源调度策略.81
4.4.1 FIFO 调度策略81
4.4.2 公平调度器(FairScheduler)81
4.4.3 能力调度器(CapacityScheduler) 82
4.4.4 延迟调度策略(DelayScheduling)82
4.4.5 主资源公平调度策略(DominantResource Fair Scheduling).82
4.5 Mesos.84
4.6YARN87
参考文献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 ZooKeeper96
5.2.1 体系结构.96
5.2.2 数据模型(DataModel) .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 ProtocolBuffer 与Thrift .108
6.1.2Avro.109
6.2 消息队列.110
6.2.1 常见的消息队列系统110
6.2.2 Kafka.111
6.3 应用层多播通信(Application-LevelMulti-Broadcast)114
6.3.1 概述.114
6.3.2 Gossip 协议.115
参考文献118
第7 章 数据通道.120
7.1 Log 数据收集.120
7.1.1Chukwa121
7.1.2Scribe122
7.2 数据总线123
7.2.1Databus125
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 Colossus137
8.2 HDFS138
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 纠删码(ErasureCode).158
8.5.1 Reed-Solomon 编码.159
8.5.2 LRC 编码.164
8.5.3 HDFS-RAID 架构.166
参考文献.166
第9 章 内存KV 数据库.168
9.1 RAMCloud169
9.1.1 RAMCloud 整体架构169
9.1.2 数据副本管理与数据恢复170
9.2Redis172
9.3 MemBase.173
参考文献175