并行与分布式数据服务：事务模型、处理语言、一致性与体系结构

随着物联网、云计算、大数据与人工智能等技术的蓬勃发展，计算服务逐渐从计算密集型向数据密集型（Data Intensive）转变。高性能、高通量的数据服务关键技术成为智慧城市、智能制造、智慧农业等国家重大需求解决方案的核心基础。并行与分布式数据处理的概念启发于上世纪80年代，源自讨论在内存及二级存储极为有限的条件下如何跨越“内存墙”，完成计算任务的优化技术。而今，互联网与私有网络数据指数级增长、数据服务的事务性需求复杂多变、跨地域数据同步需求动态不统一、如何应对当前及未来大数据服务及其上的人工智能计算对并行与分布式数据服务提出了新的问题与挑战。本书从并行与分布式数据服务的基础理论、事务模型、数据处理语言等基础内容，并进一步讨论分布式数据一致性模型及全观性的数据处理架构方面的先进及实用的研究及系统软件相关知识，，对分布式数据服务的其他研究也进行了概述，并对其未来发展方向进行展望。本书可以作为计算机、数据科学与大数据技术、人工智能等相关专业的高年级本科生与研究生在数据库理论及分布式系统等课程上的辅助教材，也可以为物联网、云计算、大数据与人工智能等领域的科研人员及从业者提供创新研究与技术应用的参考。

徐子晨：
教授、博士生导师。2016年6月毕业于美国俄亥俄州立大学获博士学位。现为南昌大学数学与计算机学院副院长，高层次引进人才，学科方向带头人，江西省“双千计划”首批入选者。在南昌大学任职期间教授本科生及研究生系统类课程二十余门。
主要从事包括数据密集计算，智能计算，高能效计算及分布式数据存储等数据库系统软件相关方面的教研工作。以第一作者发表数据库、分布式系统体系结构等方向高水平期刊、会议文章50余篇。服务于IEEE/ACM TKDE/TC/TPDS/TCC等旗舰期刊，担任过IEEE ICDE，INFOCOM，BigData，IWQoS，ICDCS等国际旗舰会议的程序委员会副主席及委员等相关工作。是计算机数据库系统研究者。

柳杰：
国内互联网大厂分布式缓存服务高级工程师，前滴滴出行高级软件开发工程师，曾参与并主导了滴滴出行底层键值存储系统分布式资源编排系统的重构方案设计，并负责开发实现，在分布式系统架构领域有深入研究。是开源项目eraft（https://eraft.cn/）主要代码贡献者，该项目被收录于斯坦福大学Raft协议官方库，亦是本书的实践主体。

娄俊升：
2021级南昌大学软件工程硕士，研究方向为分布式系统一致性算法优化。曾参与多个国家级、省级项目研发，从中学习与总结了许多分布式系统领域相关的理论和实践经验，对分布式一致性算法性能优化有深入研究。

适读人群 ：本书可以可以为物联网、云计算、大数据与人工智能等领域的科研人员及从业者提供创新研究与技术应用的相关理论、方法与技术支撑，也可作为计算机科学与技术、数据科学与大数据
?本书主要围绕分布式数据服务进行阐述，对分布式数据服务相关系统、算法以及体系结构进行了全面的解读。

?本书加入了大量的实践实训环节，引导读者从零到一构建一种强一致性协议并实现其运行框架。

?本书中的硬核技术是互联网大厂亟需的分布式基础架构开发技术，为相关从业人员提供了全面而系统的学习资源。

写作是一件痛苦的事情，这不仅仅是自己思考的模态转换，更是对自身学术认知的重新梳理。大概在12年前，我还是一个学生，在某次学术会议上遇到了Leslie Lamport博士。那时他已经70岁高龄，脸上沟壑纵横，但眼神仍然犀利，对探讨的话题反馈依旧敏锐。当时是我第一次听到Paxos Island的故事，并从此进入了分布式一致性协议优化的“深渊巨口”。时间如白驹过隙，十多年过去了，我们在分布式一致性协议上做了各种工作，有些是对数学模型的探讨，有些是对具体实现的优化，还有一些是人生哲学上的引申。我们想留下这些心得体会，并分享给更多人。
本书主要围绕Raft和Paxos两个协议进行阐述。与其他相关图书不同的是，书中加入了大量的实践实训环节，引导读者从零到一构建一种强一致性协议并实现其运行框架。这种技术是硬核的，是很多互联网企业急需的，是值得学习的。这与我们成书的起源相关。2017年，我回国开始创办泛在数据处理与优化实验室，开始只有几个本科生跟着我做一些超出他们学习范围的工作。其中就有本书的另一作者——柳杰。年轻人对未知知识是如此渴望，但是对复杂数学模型又是如此畏惧。在共同协作下，我们复现了Raft（Paxos协议的一种变形）、Paxos，甚至提出了更加泛化、更简单好用的eRaft一致性协议及其实现，并且eRaft被收录于斯坦福大学的一致性协议公开库中。整体工作共用了大概5年时间。在此基础上，我们可以对分布式数据库，特别是分布式数据库函数级服务，实现更好更宽泛的支持。希望本书可以帮助更多学生，实现复杂的一致性协议，同时对学生学习分布式系统、分布式数据库等高阶知识起到帮助作用。
较早的时候，机械工业出版社的编辑找到我，希望我写一本关于数据库先进技术的书。我答应了，决定把这本书写出来。在编写本书的过程中，崔傲、谭国龙、姜文静、向紫芊、肖欣雨等同学帮忙搜集资料，黄嘉诚、刘必勇、吴伟正等同学帮忙构建系统，吴伟正、曾焘、舒磊明、许可、李江波、李冰雁、孙珍龄等同学帮忙完成协调、编纂、校对、验证代码等一系列烦琐的工作。在成书的过程中，得到了中国人民大学杜小勇老师，上海交通大学过敏意老师、陈全老师、李超老师、陈海波老师、王肇国老师，中国科学技术大学李诚老师，国防科技大学董德尊老师，北京理工大学王国仁老师、袁野老师，北京航空航天大学马帅老师等各位师长的建议和指导，在此一并感谢。
表文云，“丽文幽质，唯道可度，欢同陨世，大道不称”。共勉之。

徐子晨
2023年4月20日

序
前言
第一部分　分布式系统基础与理论
第1章　分布式系统基础2
1.1　概述2
1.2　分布式设计目标4
1.2.1　一致性4
1.2.2　可用性6
1.2.3　分区容错性8
1.2.4　可扩展性9
1.3　数据模型10
1.3.1　关系模型10
1.3.2　文档模型12
1.3.3　图状数据模型14
1.4　数据存储15
1.4.1　数据库内部的数据结构17
1.4.2　列式存储20
1.5　数据冗余与副本25
1.6　本章小结27
第2章　分布式数据处理语言29
2.1　SQL29
2.1.1　SQL基础30
2.1.2　SQL的查询语句33
2.1.3　SQL表的连接42
2.1.4　SQL的其他语句48
2.2　NoSQL52
2.2.1　键值数据库处理语言53
2.2.2　文档数据库处理语言56
2.2.3　列族数据库处理语言61
2.2.4　图数据库处理语言65
2.3　本章小结72
第3章　分布式查询过程73
3.1　分布式连接问题74
3.1.1　直接连接算法77
3.1.2　半连接算法78
3.1.3　布隆连接算法80
3.2　多关系连接83
3.2.1　分布式查询优化的目标83
3.2.2　分布式查询优化的基本方法84
3.2.3　局部处理优化85
3.2.4　基于直接连接的多连接查询优化87
3.2.5　基于半连接的多连接查询优化90
3.3　关系连接算法91
3.3.1　嵌套循环连接算法92
3.3.2　哈希连接算法93
3.3.3　排序归并连接算法95
3.4　本章小结97
第4章　分布式环境下的事务处理99
4.1　深入理解事务100
4.1.1　本地事务100
4.1.2　全局事务111
4.1.3　分布式事务112
4.2　原子提交协议和分布式事务
解决方案113
4.2.1　2PC协议113
4.2.2　3PC协议118
4.2.3　Best Efforts 1 PC事务120
4.2.4　TCC事务121
4.2.5　SAGA事务123
4.3　并发控制协议125
4.3.1　悲观并发控制协议126
4.3.2　乐观并发控制协议134
4.3.3　多版本并发控制协议136
4.4　本章小结138
第5章　分布式数据服务一致性139
5.1　数据同步方法139
5.1.1　主从复制139
5.1.2　多主复制141
5.1.3　无主复制143
5.2　分布式数据一致性级别144
5.2.1　线性一致性145
5.2.2　顺序一致性和PRAM一致性147
5.2.3　因果一致性149
5.2.4　最终一致性和弱一致性152
5.3　分布式数据一致性/共识算法154
5.3.1　ViewStamped Replication算法157
5.3.2　Paxos算法161
5.3.3　Practical Byzantine Fault Tolerance算法167
5.3.4　Raft算法171
5.4　本章小结177
第二部分　分布式系统经典案例学习与实战
第6章　分布式系统案例分析——GFS180
6.1　GFS的设计目标180
6.2　GFS的master节点181
6.3　GFS读文件182
6.4　GFS写文件182
6.5　GFS的一致性183
6.6　本章小结185
第7章　面向分布式系统设计的Go语言基础知识186
7.1　Go 语言的优势186
7.2　切片189
7.2.1　Go语言中的数组189
7.2.2　切片的声明190
7.2.3　切片的追加190
7.2.4　切片的截取192
7.2.5　修改切片元素193
7.3　Goroutine和通道194
7.3.1　Goroutine简介195
7.3.2　Goroutine 的使用196
7.3.3　通道简介200
7.3.4　通道实现同步202
7.4　调度器203
7.4.1　调度器的设计决策203
7.4.2　Go语言调度器模型204
7.5　本章小结213
第8章　构建强一致性算法库214
8.1　核心数据结构设计214
8.2　协程模型215
8.3　RPC定义217
8.3.1　日志条目：Entry217
8.3.2　投票请求：Request-Vote217
8.3.3　追加日志：Append-Entries218
8.4　Leader 选举实现分析219
8.5　日志复制实现分析224
8.6　Raft快照实现分析228
8.7　本章小结230
第9章　基于强一致性算法库构建分布式键值存储系统231
9.1　eraftkv架构及运行流程231
9.2　eraftkv环境配置232
9.3　让系统运行起来233
9.4　对外接口定义234
9.5　服务端核心实现分析235
9.6　本章小结239
第10章强一致性算法Raft的优化设计与实现：Multi-Raft240
10.1　设计思考240
10.2　配置服务器实现分析241
10.3　分片服务器实现分析242
10.4　客户端实现分析246
10.5　本章小结248
参考文献249