分布式系统与一致性

"√ 全面覆盖文件、存储、消息、数据库、协调服务、一致性实现原理、算法的分布式架构设计宝典。 √ 十余年经验资深架构专家讲述分布式技术核心一致性理论，更精心组织、剖析业界前沿系统案例。 √ 饿了么KV数据库开发负责人现身实战解密“高并发、可扩展分布式系统设计”带来的一一致性难题。 √ 面向大型分布式系统构建，深入剖析重要的一致性特性，将晦涩理论融入实际案例使其浅显易读。"

一致性是非常重要的分布式技术。众所周知，分布式系统有很多特性，如可用性、可靠性等，这些特性多多少少会与一致性产生关系，受到一致性的影响。要全面研究、掌握分布式技术，一致性是绕不开的一个话题，也是最难解决的一个问题。本书主要介绍GFS、HDFS、BigTable、MongoDB、RabbitMQ、ZooKeeper、Spanner、CockroachDB系统与一致性有关的实现细节，以及非常重要的Paxos、Raft、Zab分布式算法；本书还介绍了事务一致性与隔离级别、顺序一致性、线性一致性与强一致性相关内容，以及架构设计中的权衡等。从分布式技术的角度来说，本书讲解了分布式领域比较高阶的内容，但是从分布式一致性的角度来说，本书仍然是一致性的入门书。

陈东明: 饿了么北京技术中心架构组负责人,负责饿了么的产品线架构设计以及基础架构研发工作,主导开发eleme key-value数据库。曾任百度架构师负责百度即时通讯产品的架构设计。具有丰富的大规模系统构建和基础架构的硏发经验,善于复杂业务需求下的大并发、分布式系统设计和持续优化。

第1部分  开 篇 第1章 分布式系统的核心特性：一致性 2 1.1 拆分是解决大规模应用的本质 2 1.2 分布式技术是大规模应用的最后一个考验 4 1.3 一致性是这个考验的核心 6 第2部分  系统案例 第2章 Google的文件系统 8 2.1 GFS的外部接口和架构 8 2.1.1 GFS的外部接口 8 2.1.2 GFS的架构 9 2.2 GFS的写流程细节 11 2.2.1 名字空间管理和锁保护 11 2.2.2 租约 11 2.2.3 变更及变更次序 11 2.3 GFS的原子性 13 2.3.1 write和record append的区别 13 2.3.2 GFS中原子性的含义 14 2.3.3 GFS中多副本之间不具有原子性 15 2.4 GFS的松弛一致性 15 2.4.1 元数据的一致性 15 2.4.2 文件数据的一致性 15 2.4.3 适应GFS的松弛一致性 16 2.4.4 GFS的设计哲学 17 参考文献 18 第3章 开源的文件系统HDFS 19 3.1 HDFS的外部接口和架构 19 3.1.1 HDFS的外部接口 19 3.1.2 HDFS的架构 20 3.2 HDFS的写流程细节 21 3.2.1 打开文件 22 3.2.2 pipeline写入 22 3.2.3 上报block状态 24 3.2.4 关闭文件 24 3.2.5 DN定期上报信息 24 3.3 HDFS的错误处理 25 3.3.1 DN的错误 25 3.3.2 NN的错误 26 3.3.3 客户端的错误 26 参考文献 29 第4章 Google的BigTable系统 30 4.1 BigTable的外部接口和架构 30 4.1.1 表 30 4.1.2 数据 31 4.1.3 原子性 32 4.1.4 时间戳 32 4.1.5 BigTable的数据模型 33 4.1.6 BigTable的架构 34 4.2 BigTable的实现 35 4.2.1 tablet location 35 4.2.2 tablet的指派 36 4.2.3 加载tablet 36 4.2.4 tablet的读/写操作 37 4.2.5 合并 38 参考文献 38 第5章 文档数据库MongoDB 39 5.1 MongoDB的外部接口和架构 39 5.1.1 MongoDB的基本概念 39 5.1.2 MongoDB的架构 39 5.2 MongoDB的standalone模式 40 5.2.1 MongoDB的写入过程 40 5.2.2 无确认导致的丢失更新异常 40 5.2.3 未持久化导致的丢失更新异常 41 5.3 MongoDB的replica set模式 42 5.3.1 MongoDB的复制过程 43 5.3.2 无副本确认导致的丢失更新异常 44 5.3.3 不正确选主导致的丢失更新异常 45 5.3.4 脑裂导致的丢失更新异常 47 5.3.5 缺失任期信息导致的丢失更新异常 48 5.3.6 脏读异常 51 5.3.7 陈旧读异常 52 第6章 消息系统RabbitMQ 54 6.1 RabbitMQ简述 54 6.1.1 关于broker 54 6.1.2 RabbitMQ的接口 55 6.1.3 镜像队列 55 6.2 RabbitMQ的基本实现 55 6.2.1 镜像复制 55 6.2.2 镜像加入队列 56 6.2.3 镜像同步过程 56 6.3 master切换及RabbitMQ的异常处理 57 6.3.1 意外宕机后的master切换 57 6.3.2 主动运维后的master切换 57 6.3.3 意外宕机与主动运维的默认行为差异 58 6.3.4 网络分区后的master切换 58 6.4 确认机制 59 第7章 协调服务ZooKeeper 60 7.1 协调服务的应用场景 60 7.2 ZooKeeper简述 61 7.2.1 ZooKeeper的数据模型 61 7.2.2 ZooKeeper的外部接口 62 7.2.3 ZooKeeper的架构 63 7.3 ZooKeeper的实现细节 65 7.3.1 客户端异步处理 65 7.3.2 请求处理器 65 7.3.3 原子广播 67 参考文献 68 第8章 Google的Spanner数据库 69 8.1 Spanner的数据模型 69 8.1.1 带模式的半关系型表 69 8.1.2 通用事务 71 8.2 Spanner的架构 72 8.3 Spanner的实现 73 8.3.1 tablet与存储 73 8.3.2 复制 73 8.3.3 TrueTime 74 8.3.4 事务 75 8.3.5 目录 80 8.3.6 Paxos的作用 80 8.4 TrueTime的作用 81 8.4.1 Spanner的外部一致性 81 8.4.2 TrueTime生成事务时间戳 82 8.4.3 TrueTime管理leader租约 83 8.4.4 TrueTime作用的总结 85 参考文献 85 第9章 分布式数据库CockroachDB 86 9.1 CockroachDB的接口和数据模型 86 9.2 CockroachDB的架构 87 9.3 元数据存储的实现 88 9.4 多副本存储的实现 90 9.5 事务的实现 92 9.5.1 单个事务的执行 92 9.5.2 多个事务串行执行 94 9.5.3 事务的并发执行 96 参考文献 106 第3部分  分布式算法 第10章 共识算法Paxos 108 10.1 Paxos的历史 108 10.2 Consensus vs Paxos 110 10.3 Basic Paxos算法 111 10.3.1 共识问题 111 10.3.2 算法简述 113 10.3.3 选择值过程 115 10.4 Multi Paxos 算法 132 10.4.1 多个实例 132 10.4.2 独立实例运行的完整Paxos算法 132 10.4.3 只运行一次prepare消息的完整Paxos算法 137 10.5 复制状态机 144 10.6 Paxos算法与复制状态机 146 10.6.1 Paxos算法实现复制状态机 146 10.6.2 空洞处理 147 10.7 原子广播 148 10.7.1 原子广播协议 148 10.7.2 原子广播的模型 148 10.7.3 原子广播的特性 149 10.8 Paxos算法与原子广播 149 10.8.1 Paxos consensus实例与原子广播 149 10.8.2 Paxos的角色与原子广播 150 参考文献 151 第11章 复制日志算法Raft 152 11.1 Raft是复制日志的算法 152 11.2 Raft算法的组成 153 11.3 复制过程 153 11.4 选举过程 154 11.4.1 选举的基本条件 154 11.4.2 任期 155 11.4.3 完整的选举过程 156 11.5 异常处理 157 11.5.1 不一致异常 157 11.5.2 一致性检查 160 11.5.3 不提交旧的leader的entry 160 参考文献 162 第12章 原子广播算法Zab 163 12.1 Zab算法简述 163 12.1.1 设计的Zab算法与ZooKeeper中实现的Zab算法 163 12.1.2 Zab算法的阶段 164 12.2 各版本Zab算法的共有部分 164 12.2.1 Zab算法的基本概念 164 12.2.2 Zab算法的broadcast阶段 166 12.2.3 Zab算法的消息通道 169 12.2.4 Zab算法的broadcast阶段的特性 170 12.2.5 已提交的提议 170 12.2.6 故障处理 170 12.3 设计的Zab算法 172 12.3.1 Phase0：election阶段 173 12.3.2 Phase1：discovery阶段 174 12.3.3 Phase2：synchronization阶段 174 12.3.4 Phase3：broadcast阶段 175 12.3.5 设计的Zab算法的问题 176 12.3.6 设计的Zab算法处理leader故障 176 12.4 Zab Pre 1.0算法 177 12.4.1 leader election阶段 177 12.4.2 recovery阶段 177 12.4.3 Zab Pre 1.0算法处理leader宕机故障 178 12.4.4 Zab Pre 1.0算法的缺陷 179 12.5 Zab 1.0算法 179 12.5.1 Phase0：leader election阶段 180 12.5.2 Phase1：discovery阶段 180 12.5.3 Phase2：synchronization阶段 181 12.5.4 Zab 1.0算法处理leader宕机故障 181 参考文献 182 第4部分  一 致 性 第13章 事务一致性与隔离级别 184 13.1 ANSI的隔离级别 185 13.1.1 ANSI的隔离级别定义 185 13.1.2 对一致性的破坏 186 13.1.3 脏写 188 13.1.4 锁机制 188 13.2 SI和SSI隔离级别 190 13.2.1 MVCC 190 13.2.2 SI隔离级别 190 13.2.3 SSI隔离级别 192 参考文献 192 第14章 顺序一致性 193 14.1 顺序一致性的正式定义 193 14.1.1 顺序一致性应用的范围 193 14.1.2 顺序一致性的定义 194 14.1.3 核心概念的解释 195 14.1.4 定义解析 198 14.1.5 在分布式系统中的定义 200 14.1.6 举例说明 200 14.2 理解顺序一致性 202 14.2.1 顺序排序 202 14.2.2 程序顺序 202 14.2.3 顺序一致性是严苛的 203 14.3 顺序一致性的其他描述 204 14.3.1 第一种描述：全局视角一致 204 14.3.2 第二种描述：允许重排序 205 14.4 顺序一致性的作用 206 14.4.1 并发条件 206 14.4.2 原子性 207 参考文献 209 第15章 线性一致性与强一致性 210 15.1 什么是线性一致性 210 15.1.1 预备概念 211 15.1.2 定义 213 15.2 判断系统是否满足线性一致性 213 15.3 对线性一致性的理解与强一致性 216 15.3.1 线性一致性的其他描述 216 15.3.2 线性一致性与顺序一致性的比较 217 15.3.3 强一致性 218 15.4 ZooKeeper的一致性分析 219 15.4.1 ZooKeeper是顺序一致性的 219 15.4.2 ZooKeeper的一致性的作用 221 15.4.3 ZooKeeper的一致性的描述 222 参考文献 223 第16章 架构设计中的权衡 225 16.1 什么是CAP定理 225 16.1.1 CAP历史：从原则到定理 225 16.1.2 CAP的定义 226 16.1.3 CAP定理下的三种系统 226 16.1.4 深入理解CAP定理中的P和A 227 16.2 关于CAP定理的错误理解 228 16.2.1 不是三选二，不能不选P 228 16.2.2 不是三分法 229 16.2.3 不该轻易放弃任何一个属性 230 16.3 CAP中的权衡 230 16.3.1 弱CAP原则 230 16.3.2 CAP推动NoSQL 231 16.3.3 分布式系统中的可用性和一致性 231 16.4 进一步权衡：HAT和PACELC 231 16.4.1 HAT 232 16.4.2 权衡 234 16.4.3 PACELC 234 参考文献 235