商品参数

内容简介

本书主要讲解分布式系统常用的基础知识、算法和案例，经笔者对文献海洋中晦涩艰深的原理和算法进行提炼，辅以图示和代码，并结合实际经验进行分析总结而成。通过阅读本书，读者可以快速、轻松地掌握分布式系统的基本原理，以及Paxos或Raft共识算法，并通过典型的案例学习如何设计大型分布式系统。本书首先介绍什么是分布式系统、分布式系统带来的挑战，以及如何对分布式系统进行建模，这部分内容偏向概念性介绍。接着介绍了分布式数据的基础知识，包括数据分区技术、数据复制技术、CAP定理、一致性模型和隔离级别，尝试厘清一些十分容易混淆的术语，比如一致性、线性一致性、#终一致性和一致性算法等。本书还介绍了分布式系统的核心算法——Paxos和Raft算法，不仅补充了大量图示进行讲解，还从零实现了一个Paxos算法。此外，本书分析了常见的分布式事务，并讨论了分布式系统中的时间问题，整理了一些实际发生的编程陷阱。#后结合一些对工业界产生重大影响的论文或开源系统，学习前人在设计大型分布式系统时的思路、取舍和创新

目录

第1章　认识分布式系统 1

1.1　什么是分布式系统 1

1.2　为什么需要分布式系统 2

1.3　分布式系统的示例 3

1.3.1　搜索引擎 3

1.3.2　加密货币 5

1.4　分布式系统的挑战 5

1.4.1　网络延迟问题 6

1.4.2　部分失效问题 7

1.4.3　时钟问题 7

1.5　每个程序员都应该知道的数字 8

1.6　本章小结 9

第2章　分布式系统模型 10

2.1　两将军问题 10

2.2　拜占庭将军问题 12

2.3　系统模型 14

2.3.1　网络链路模型 14

2.3.2　节点故障类型 16

2.3.3　按时间划分系统模型 16

2.4　消息传递语义 17

2.5　本章小结 18

第3章　分布式数据基础 19

3.1　分区 20

3.1.1　水ping分区算法 21

3.1.2　分区的挑战 28

3.2  复制 28

3.2.1  单主复制 29

3.2.2  多主复制 32

3.2.3  无主复制 34

3.3　CAP定理 38

3.3.1　PACELC定理 42

3.3.2　BASE 44

3.4　一致性模型 44

3.4.1　线性一致性 47

3.4.2　实现线性一致性 52

3.4.3　线性一致性的代价 53

3.4.4  顺序一致性 54

3.4.5　因果一致性 55

3.4.6　#终一致性 56

3.4.7　以客户端为中心的一致性模型 56

3.5  隔离级别 58

3.6　一致性和隔离级别的对比 63

3.7　本章小结 64

第4章　分布式共识 66

4.1　分布式共识简介 66

4.1.1　什么是分布式共识 67

4.1.2　为什么要达成共识 68

4.2　异步系统中的共识 70

4.2.1　FLP不可能定理 71

4.2.2　故障屏蔽 72

4.2.3　使用故障检测器 72

4.2.4　使用随机性算法 73

4.3　同步系统中的共识 74

4.4　Paxos 74

4.4.1　基本概念 76

4.4.2　问题描述 77

4.4.3　Paxos算法实现流程 78

4.4.4　案例 81

4.4.5　活锁 83

4.5  实验：使用Go语言实现Paxos共识算法 83

4.5.1　定义相关结构体 83

4.5.2　定义消息结构体 85

4.5.3　算法实现流程 87

4.5.4　学习提案 91

4.5.5　实现单元 94

4.6  Multi-Paxos 97

4.6.1  确定日志索引 98

4.6.2　选举 100

4.6.3　减少请求 100

4.6.4　副本的完整性 101

4.6.5　客户端请求 103

4.6.6　配置变更 103

4.6.7　完整实现 105

4.6.8　Paxos练习题 108

4.7　其他Paxos变体 112

4.7.1  Disk Paxos 113

4.7.2　Cheap Paxos 113

4.7.3　Fast Paxos 114

4.7.4　Mencius 115

4.7.5　EPaxos 116

4.7.6　Flexible Paxos 120

4.7.7　WPaxos 120

4.7.8　CASPaxos 121

4.7.9　其他 122

4.8  Raft算法 122

4.8.1　系统模型 123

4.8.2　基本概念 124

4.8.3　选举 125

4.8.4　日志复制 129

4.8.5　更替 134

4.8.6  选举限制举例 137

4.8.7　延迟提交之前任期的日志条目 139

4.8.8　清理不一致的日志 142

4.8.9　处理旧 143

4.8.10　客户端协议 144

4.8.11　实现线性一致性 144

4.8.12　配置变更 146

4.8.13　配置变更存在的Bug 149

4.8.14　极端情况下的活性问题 151

4.8.15　日志压缩 154

4.8.16　基于内存的状态机的快照 155

4.8.17　基于磁盘的状态机的快照 158

4.8.18　性能优化 159

4.8.19　Raft练习题 162

4.9　Paxos vs Raft 167

4.10　拜占庭容错和PBFT算法 169

4.11　本章小结 174

第5章　分布式事务 176

5.1　什么是分布式事务 176

5.2　原子提交 180

5.2.1　两阶段提交 181

5.2.2　三阶段提交 184

5.2.3　Paxos提交算法 187

5.2.4　基于Quorum的提交协议 190

5.2.5　Saga事务 192

5.3　并发控制 194

5.3.1　两阶段锁 195

5.3.2　乐观并发控制 198

5.3.3　多版本并发控制 201

5.4　Percolator 211

5.5　本章小结 215

第6章　时间和事件顺序 218

6.1　物理时钟 219

6.2　时钟同步 221

6.3　逻辑时钟 224

6.4　向量时钟 231

6.5　分布式快照 234

6.6　本章小结 237

第7章　案例研究 239

7.1　分布式文件系统 239

7.1.1　GFS的目标 240

7.1.2　架构 241

7.1.3　读取文件 242

7.1.4　写入文件 243

7.1.5　一致性模型 244

7.1.6　其他 246

7.2　分布式协调服务 248

7.2.1　ZooKeeper架构 248

7.2.2　数据模型 251

7.2.3　ZooKeeper实现 251

7.2.4　客户端API 253

7.2.5　其他 254

7.3　分布式表格存储Bigtable 255

7.3.1　数据模型 255

7.3.2　架构 257

7.3.3　SSTable和LSM Tree 260

7.3.4　其他优化 262

7.4　分布式键值存储Dynamo 263

7.4.1　架构 264

7.4.2　请求协调 265

7.4.3　成员管理和故障检测 266

7.5　分布式N0SQL数据库Cassandra 267

7.5.1　数据模型 268

7.5.2　架构 269

7.5.3　协调请求 270

7.5.4　一致性级别 271

7.5.5　轻量级事务 271

7.5.6　二级索引 272

7.5.7　批处理 273

7.6　分布式数据库Spanner 275

7.6.1　数据模型 276

7.6.2　架构 276

7.6.3　TrueTime 277

7.6.4　读写事务 280

7.6.5　只读事务 282

7.6.6　快照读和模式变更事务 283

7.7　分布式批处理 284

7.7.1　MapReduce 285

7.7.2　Spark 289

7.8　分布式流处理Flink 292

7.8.1　计算模型 293

7.8.2　系统架构 295

7.8.3　时间处理 297

7.8.4　分布式快照 300

7.8.5　端到端的一次语义 302

7.9　本章小结 303

^_^:ab5084fd1014da0440831a3988556ed6