目录 - 博文视点

目录
第0章当谈论大数据时我们在谈什么
第1章数据分片与路由
第2章数据复制与一致性
第3章大数据常用的算法与数据结构
第4章集群资源管理与调度
第5章分布式协调系统
第6章分布式通信
第7章数据通道
第8章分布式文件系统
第9章内存KV数据库
第10章列式数据库
第11章大规模批处理系统
第12章流式计算
第13章交互式数据分析
第14章图数据库：架构与算法
第15章机器学习：范型与架构
第16章机器学习：分布式算法
第17章增量计算

图书类别

数据处理与大数据

第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

图书分类

高可靠系统构建指南：服务稳定性建设与技术债务治理

特色专题

帮助

目录

目录

图书类别