深入理解分布式系统
2023-02-21 20:48:34 26 举报AI智能生成
分布式系统概览
作者其他创作
大纲/内容
第1章 认识分布式系统
1.1 什么是分布式系统
完全可以认为，目前绝大部分系统都是分布式的
定义
分布式系统是一个其组件分布在不同的、连网的计算机上，组件之间通过传递消息进行通信和协调，共同完成一个任务的系统
特点
多进程
不共享操作系统
不共享时钟
1.2 为什么需要分布式系统
高性能
可扩展性
高可用性
必要性
1.3 分布式系统的示例
对于不同的任务，可能又有不同的架构，这就导致分布式系统可能有上百种架构
1.3.1 搜索引擎
分布式基础设施
一个全球化、巨大的多数据中心
一个分布式文件系统：GFS
一个高性能、可扩展、用于存储大规模结构化数据的存储系统：Bigtable
一个分布式锁服务：Chubby
一个并行和分布式计算的编程模型：MapReduce
2012年，分布式数据库Spanner
1.3.2 加密货币
1.4 分布式系统的挑战
分布式系统是指一台你根本不知道其存在的计算机发生了故障，会导致你自己的计算机无法使用
谬误
网络是可靠的
延迟为零
带宽是无限的
网络是安全的
拓扑结构不会改变
单一管理员
传输成本为零
网络是同构的
部分失效问题
时钟问题
1.4.1 网络延迟问题
分布式系统中的消息传递可能出现问题
消息丢失了
我们可能认为请求丢失了，但实际上消息只是延迟到达
网络可能会重传信息，导致收到重复的消息
消息延迟可能会让我们认为某个服务已经因故障下线，但实际上并没有
消息可能以不同的顺序到达，或者不同的结点上消息到达的顺序不同
1.4.2 部分失效问题
系统的某些部分可能会以某种不可预知的方式宕机，这被称为部分失效
难点在于部分失效时不确定的
1.4.3 时钟问题
我们很难确定在涉及多台机器时事件发生的顺序
解决方案
TrueTime API
逻辑时钟
确定时间顺序
分布式系统的状态机
1.5 每个程序员都应该知道的数字
其实就是整个系统的各个部件所消耗的时间
1.6 本章小结
更多情况是，我们需要在几个相互竞争的问题之间进行权衡，克服这些问题，对系统涉及进行取舍
第2章 分布式系统模型
不可能逐一分析上百种架构，需要抽象出一些通用的系统模型
2.1 两将军问题
该问题被证明无解
但我们熟悉的传输控制协议（TCP）的“三次握手”就是两将军问题的一个工程解
在一个分布式系统中，一个节点没有办法确认另一个节点的状态，一个节点想要知道某个节点的状态的唯一方法是通过发送信息进行交流来尽量得知
2.2 拜占庭将军问题
将军中可能出现叛徒
我们要做的是让忠诚的将领们达成共识
拜占庭故障类型描述的就是系统中某些成员计算机不仅会发生故障和出现错误，甚至会故意篡改、破坏和控制系统的系统模型
2.3 系统模型
分布式系统，节点和网络都可能出现各种各样的故障。我们的系统模型就是根据不同种类的故障抽象出来的
在设计一个分布式系统的时候，我们必须清楚会发生哪种故障，然后寻找对应的解。不同的系统模型有着不同的算法和架构
按网络、节点故障和时间三种类型划分系统模型
2.3.1 网络链路模型
网络分区
由于网络设备故障，导致网络分裂为多个独立的组
1.可靠链路
不会丢失信息，也不会凭空捏造信息，但它可能对信息进行重新排序
特点
可靠传输
没有重复
不会无中生有
2.公平损失链路
消息可能会丢失、重复和重新排序，但消息最终总会到达
特点
公平损失
有限重复
不会无中生有
3.任意链路
允许任意的网络链路执行任何操作，可能有恶意软件修改网络数据包和流量
三种网络模型可以相互转换
公平损失链路通过不断重传丢失的消息，知道接收者收到，并让接收者过滤重复的消息，把公平损失链路变成一条可靠链路（假设网络分区只持续有限时间）
使用加密技术可以将任意链路变成公平损失链路（假设攻击人不会阻断通信链路）
2.3.2 节点故障类型
节点故障可能会导致消息永久丢失
崩溃-停止
指一个节点工作停止后永远不会恢复
意味着算法不能依赖于节点恢复
崩溃-恢复
允许节点重新启动并继续执行剩余的步骤
一般通过持久化存储必要的状态信息来容忍这种故障类型
拜占庭故障
故障的节点可能不只会宕机，还可能以任意方式偏离算法，甚至恶意破坏系统
部署在私有化安全的环境的内部应用一般采用简单和方便的崩溃-停止和崩溃-恢复策略，而加密货币和航空系统都需要实现拜占庭容错
2.3.3 按时间划分系统模型
适用于异步系统的算法同样适用于同步系统，反之却不成立
不同于编程中的同步/异步
同步系统模型
一个消息的响应时间在一个有限且已知的时间范围内
异步系统模型
一个消息的响应时间是无限的，无法知道一条消息什么时候会到达
在部分同步系统模型中，我们假设系统在大部分时间都是同步的，都偶尔会因为故障转变为异步系统
2.4 消息传递语义
重复传递消息产生副作用
解决办法：幂等操作
幂等操作是指多次操作产生相等的结果，且不会有任何其他影响
幂等操作会对系统进行严格的约束，代价是昂贵的，可以通过给给每条消息一个唯一的标识符的方式使接收者避免执行已经执行过的操作
最多一次
消息最多传递一次，消息可能丢失，但不会重复
至少一次
系统保证每条消息至少会发送一次，消息不会丢失，但在有故障的情况下可能导致消息重复发送
精确一次
消息只会被精确传递一次，这种语义是人们实际想要的，有且仅有一次，消息不丢失不重复
2.5 本章小结
本书默认的分布式系统模型是可靠链路、崩溃-停止或崩溃-恢复和部分同步系统
系统模型是涉及系统架构的基础，如果一开始就对系统做了错误的假设，那么剩下的工作都是徒劳的
第3章 分布式数据基础
数据一致性、强一致性、弱一致性、最终一致性
3.1 分区
实现可扩展性的主要方式之一就是对数据进行分区
分区增加了数据的可管理性、可用性和可扩展性
垂直分区 VS 水平分区
水平分区常称为分片
3.1.1 水平分区算法
1.范围分区
用来分区的关键字也叫分区键
2.哈希分区
3.一致性哈希
在分布式存储系统中用来缓解哈希分区增加或删除节点时引起的大规模数据移动问题
一致性哈希算法将整个哈希值组织成一个抽象的圆环，称为哈希环。数据存储在按照顺时针方向遇到的第一个节点上
虚拟节点
不是真实的物理服务器，是实际节点在哈希环中的副本，一个物理节点不再值对应哈希环上一个点，而是对应多个节点
直观的看，虚拟节点越多，数据分布就越均匀
3.1.2 分区的挑战
对于某些特定的操作存在低效的弊端
另一个挑战是实现事务
3.2 复制
增强数据的可用性和安全性，减少往返时间，增加吞吐量
保持一致性不太容易
3.2.1 单主复制
同步复制
异步复制
半同步复制
3.2.2 多主复制
数据冲突
对某些请求的正确顺序产生分歧，导致多个节点上的数据不一致
解决冲突的办法
由客户端解决冲突
最后写入胜利
因果关系跟踪
无冲突复制数据类型CRDT
复杂性远超过它的好处，很少在单个数据中心使用，一般用于多个数据中心的存储系统，避免写请求跨越数据中心
3.2.3 无主复制
基本思想
客户端不仅向一个节点发送写请求，而是将请求发送到多个节点，在某些情况下甚至会发送给所有节点
无主复制有着不同的协调请求方式，一种是客户端直接将写操作发送到多个副本，而另一种是在节点中选出一个协调节点，客户端将请求发送到协调节点，再由协调节点代表客户端将写操作转发到多个副本，经过多个副本确认后再由协调节点响应客户端。与基于领导者的复制不同，无主复制不强制写操作的顺序
数据修复
读修复
客户端向旧数据所在的节点发送最新的值
反熵过程
从存储最新的数据的节点中将数据复制到错误的节点，不保证写操作的顺序，只保证最后结果一样
Merkle Tree 哈希树 - 减少传输数据量
基于Quorum的数据冗余机制
Quorum（法定人数）机制是分布式系统中用来保证数据冗余和最终一致性的一种算法
基于Quorum机制的最小读写副本数可以作为系统在读写性能方面的可调节参数
W+R>N
从R个节点中读取的数据必然包含写成功的节点的数据
W>N/2
保证数据的串行化修改，两个不同的写请求不能同时成功修改一份数据
3.3 CAP定理
设计分布式系统或者设计任何系统架构，主要是为了解决一个或一些特定的需求，而需求是驱动软件开发最基本的动力
CAP（布鲁尔定理）是一个分布式系统特性的高度抽象，总结了各个特性之间的冲突
在一个异步网络环境中，对于一个分布式读写存储系统来说，只能满足以下三项中的两项，而不可能满足全部三项
一致性
客户端访问所有节点，返回的都是同一份最新的数据（线性一致性）
可用性
每次请求都能获取非错误的响应，但不保证获取的数据是最新数据
分区容错性
节点之间由于网络分区而导致消息丢失的情况下，系统仍能继续正常运行
网络分区故障是必然发生的
开发者通常将他们的分布式系统分为两类
CP
AP
延迟和网络分区密切相关，系统需要在网络延迟时做出权衡
3.3.1 PACELC定理
CAP定理的一个扩展定理
CAP定理忽略分布式系统中的延迟影响是一个重大疏忽，因为延迟在系统运行过程中时刻存在，而网络分区不会一直存在
在分布式系统存在网络分区（P）的情况下，必须在可用性（A）和一致性（C）之间做出选择；否则（Else，E）系统在没有网络分区且在正常运行的情况下，必须在延迟（L）和一致性（C）之间做出选择
存在分区
PA
PC
不存在分区
EL
EC
3.3.2 BASE
基本可用、软状态和最终一致性
https://zhuanlan.zhihu.com/p/351582220
最终一致性：当客户端更新某个数据时，可能因为网络分区或延迟，导致数据没有及时同步到所有副本，系统中存在新旧数据。此时系统仍然允许继续读写数据，但在最终某个时刻，系统保证这个更新操作一定会同步到所有副本
3.4一致性模型
CAP、ACID和Paxos或Raft“分布式一致性算法”（错误）
Paxos或Raft（分布式共识算法）
ACID
ACID的一致性属于数据库领域的概念，主要是指数据的一致性没有被破坏，这种一致性要求不仅指常见的数据库完整性约束（例如主键、外键、触发器、check等约束），有时还需要由用户（应用程序）来保证
这类一致性不属于本书一致性的讨论范畴
本文要谈论的一致性模型和复制有着密切关系
复制
带来了高可用性和高性能
但也带来了多个副本如何保持数据一致这个问题
冯·诺依曼体系结构的计算模型
读操作应该返回最近的写操作所写入的结果
关键问题在于“最近”的含义是比较模糊的，到底何时、何种情况才能读到最近的写操作的结果
需要一种模型，来帮助开发者预测系统中读写操作的结果
一致性模型就是指，在并发模型中，系统和开发者之间的一种约定，如果开发者遵循某些规则，那么开发者执行读操作或写操作的结果是可预测的
“可预测”保证了程序逻辑的确定性
一致性模型本质上定义了写操作的顺序和可见性，即并发写操作执行的顺序是怎样的，写操作的结果何时能够被憋得进程看见
实际上数据一致性问题并非分布式系统独有，早在关于多处理器和并行计算的研究中已经提出许多一致性模型，包括我们需要重点掌握的线性一致性也是这一时期提出的。但有的定义已不能很好地适用于分布式系统，本章的目的就是以分布式系统的视角研究数据一致性问题
著名的分布式一致性验证框架Jepsen对一致性模型的分类
根据可用性分为三类
不可用
满足这类一致性模型的系统发生网络分区时，为了保证数据一致性和正确性，系统会不可用
包括
线性一致性
顺序一致性
基本可用
满足这类一致性模型的系统可以忍受一部分节点发生故障，还未出现故障的节点仍然可用，但前提是客户端不能将请求发送到不可用的副本节点
包括
因果一致性
PRAM一致性
读你所写一致性
高可用
满足这类一致性模型的系统可用性是最高i的，即使网络发生严重分区，在没有发生故障的节点上，仍然保证可用
包括
读后写一致性
单调读一致性
单调写一致性
3.4.1 线性一致性
CAP理论中的一致性指的就是线性一致性
最强的一致性模型，通常用Linearizability可线性化直接代替Linearizable Consistency
强一致性、严格一致性、原子一致性、立即一致性或外部一致性
线性一致性最开始是关于并发对象行为正确性的一个模型，原始论文中的并发对象主要是讨论单台计算机上的共享变量
非严格定义
分布式系统的所有操作看起来都是原子的，整个分布式系统看起来好像只有一个节点
在单台计算机进行并发编程时，我们仍然需要一些同步原语才能实现线性一致性
原因是，当我们在现代多核CPU上运行多线程程序时，由于CPU访问缓存速度比内存快得多，所有每个CPU核都有自己的缓存，这其实也构成了一个多副本的情况
严格定义
给定一个执行历史，执行历史根据并发操作可以扩展为多个顺序历史，只要从中找到一个合法的顺序历史，那么该执行历史就是线性一致性的
并发情况
顺序关系
一个操作明显在另一个操作之前发送
并发关系
两个操作之间有重叠
一个操作包含另一个操作
约束
将执行历史转变成顺序历史的过程中，如果两个操作是顺序关系，那么它们的先后关系必须保持相同；如果两个操作是并发关系，则它们可以按任何顺序排列
总的来说，线性一致性主要有两个约束条件
1.顺序记录中的任何一次读必须读到最近一次写入的数据
2.顺序记录要跟全局时钟下的顺序一致
不能重排顺序关系的操作
要知道操作之间的先后关系
3.4.2 实现线性一致性
大部分操作系统都提供了原子比较-交换（CAS）操作，原子写操作不考虑当前寄存器的值，但比较-交换操作是先判断寄存器x的当前值，如果寄存器x的当前值等于v，则原子地将x设置为v1，如果寄存器x的当前值不等于v，则保持寄存器的值不变。该操作有效避免了ABA问题
分布式系统还可以通过共识算法实现线性一致性，但是，并不是说实现了共识算法就等于实现了线性一致性
3.4.3 线性一致性的代价
分布式系统中的线性一致性最困难的是需要一个全局时钟，这样才能知道每个节点事件发生的事件和全局顺序，但分布式系统中准确的全局时钟是非常难以实现的
默认情况下，现代CPU在访问内存时不保证线性一致性，这是因为同步指令开销大、速度慢，并且涉及跨节点CPU缓存失效问题
3.4.4 顺序一致性
Lamport早于线性一致性提出
约束
同一个客户端（进程）的操作在排序后保持先后顺序不变，但不同客户端（或进程）之间的先后顺序是可以任意改变的
顺序一致性和线性一致性的主要区别在于没有全局时间的限制，顺序一致性不要求不同客户端之间的操作的顺序一致，只关注局部的顺序
与线性一致性一样，现代CPU在默认情况下也不保证顺序一致性，因为顺序一致性严格限制了程序的执行顺序。现代编译器和CPU通常都会优化指令的执行顺序，以提高程序性能，实际执行的指令顺序和程序写的指令顺序可能是不一致的
3.4.5 因果一致性
不依赖全局操作的顺序，要求必须以相同的顺序看到因果相关的操作，而没有因果关系的并发操作可以被不同的进程以不同的顺序观察到
使用了逻辑时钟来维持因果顺序
因果一致性的关键是体现了“发生于……之前”关系
因果关系在逻辑时钟下的使用
3.4.6 最终一致性
在最终的状态下，只要不再执行写操作，读操作将返回相同的、最新的结果
3.4.7 以客户端为中心的一致性模型
上面四种一致性模型归为一类，以数据为中心的一致性模型
旨在为数据存储系统提供一个系统级别的全局一致性视图
从客户端的角度来观察分布式系统，不再从系统的角度考虑每个副本的数据是否一致，而是考虑客户端的读写请求的结果，从而推断出系统的一致性
总结
以数据为中心的一致性模型常常考虑多个客户端时的系统状态，而以客户端为中心的一致性模型聚焦于单个客户端观察到的系统状态
类别
单调读一致性模型
客户端不会读到旧的值
单调写一致性模型
同一个客户端的写操作在所有副本上都以同样的顺序执行，即保证客户端的写操作是串行的
读你所写一致性模型
单个客户端
当写操作完成后，在同一副本或其他副本上的读操作必须能读到写入的值
读后写一致性模型
会话因果一致性
看起来跟因果一致性非常相似，只不过是以单个客户端为视角
同一个客户端对于数据项x，如果先读到了写操作w1的结果是v，那么之后的写操作w2保证基于v或比v更新的值
PRAM一致性（FIFO一致性）
流水线随机访问存储器一致性
由单调读、单调写和读你所写三个一致性模型组成
一致性要求
同一个客户端的多个写操作，将被所有的副本按照相同的执行顺序观察到，但不同客户端发出的写操作可以以不同的执行顺序被观察到
3.5 隔离级别
隔离性属于事务ACID四个属性之一
隔离级别定义了并行系统中事务的结果何时、以何种方式对其他并发事务可见
串行化
可重复读
快照隔离
读已提交
读未提交
隔离性是一种容易跟一致性混淆的概念，尤其是隔离级别跟一致性模型有着类似的层级结构
异常情况
脏写
一个事务覆盖了另一个仍在运行中、尚未提交的事务写入的值
问题
会破坏数据的完整性约束，使系统无法正确回滚事务
脏读
事务读到了另一个尚未提交的事务写入的值
问题
事务可能会根据读到的值做出决定，但是相关的事务可能会在随后回滚，这样做出的决定共和系统中存储的值是矛盾的
不可重复读
一个事务中查询一个值两次，但两次查询返回的值不同
不可重复读与脏读差别
脏读是由于其他事务回滚导致的
不可重复读读到的是其他事务已经提交的数据
问题
如果第一次读取的值用于一些条件判断，而第二次读的值用来更新某个值，那么会得到意料之外的结果
幻读
一个事务进行条件查询时，另一个事务在中间插入或删除了匹配该条件的数据；幻读就是读到的数据项变多了或变少了
更新丢失
当两个事务读取同一个值，然后都试图将其更新为新的不同的值时，就会发生更新丢失
读偏斜
读到了数据一致性被破坏的数据（一致性约束通常是业务逻辑层面的）（ACID）
写偏斜
两个并发事务都读到了相同的数据集，但随后各自修改了不相干的数据集，导致数据的一致性约束被破坏
进行系统设计时，根据不同应用程序以不同方式操作数据来考虑哪些异常是可以允许的，哪些是要避免的
不同的隔离级别可以防止不同的异常
P63
3.6 一致性和隔离级别的对比
一致性和隔离级别对任何数据系统（无论是不是分布式的）来说都是非常重要的概念
相同点
本质上都是用来描述系统能够容忍哪些行为，不能容忍哪些异常行为，更严格的一致性模型或隔离级别意味着更少的异常行为，但可以降低系统性能和可用性为代价
区别
一致性模型适用于单个对象，比如单个数据项或单个变量的读写，该数据可能存在多个副本
隔离级别通常涉及多个操作对象，比如在并发事务中修改多个数据
最严格一致性模型和隔离级别
线性一致性和串行化
线性一致性提供了实时保证，而串行化没有
这意味着线性一致性保证操作在客户端调用和客户端收到响应之间的某个时刻生效，而串行化只保证多个并发事务的效果，以及它们以穿行顺序运行，至于串行的顺序是否与实时的顺序一样，它没有保证
严格串行化
一个数据存储系统可以同时保证线性一致性和串行化
保证了多个事务执行的结果等同于它们的串行执行结果，同时执行顺序与实时排序一致
像单机单线程程序一样
3.7 本章小结
通过分区提高可扩展性，通过复制提高可用性和性能
CAP定理和分布式数据系统相关的设计思想
一致性模型和隔离级别
很难自圆其说（中庸之道，取舍）
数据进行分区，分散存储导致故障频发，数据副本实现自动容错，同时带来数据一致性问题，进而导致低性能
第4章 分布式共识
4.1 分布式共识简介
起源于NASA
4.1.1 什么是分布式共识（协商）
“共识”不等于“一致性”
共识侧重于研究分布式系统中的节点达成共识的过程和算法，一致性则侧重于研究副本最终的稳定状态
另外，一致性一般不会考虑拜占庭容错问题
在分布式系统中，共识就是在一个可能出现任意故障的分布式系统中的多个节点（进程）对某个值达成共识；共识问题的有趣之处在于其充满了关于故障的讨论
数学语言描述
一个分布式系统包含n个进程，记为{0，1，2，……，n-1}，每个进程都有一个初始值，进程之间互相通信，设计一种共识算法使得尽管出现故障，但进程之间仍能协商出某个不可撤销的最终决定值，且每次执行都满足以下三个性质：
终止性：所有正确的进程最终都会认同某一个值
协定性：所有正确的进程认同的值都是同一个值
完整性，也叫作有效性：如果正确的进程都提议同一个值v，那么任何正确进程的最终决定值一定是v
存在较弱的完整性
4.1.2 为什么要达成共识
状态机复制
状态机的确定性是实现容错和一致性的理想特性
状态机必须具备确定性：多个相同状态机的副本，从同样的“初始”状态开始，经历相同的输入序列后，会达到相同的状态，并输出相同的结果
实现状态机复制常常需要一个多副本日志系统：如果日志的内容和顺序都相同，多个进程从同一状态开始，并且从相同的位置以相同的顺序读取日志内容，那么这些进程将生成相同的输出，并且结束在相同的状态；共识算法常用来实现多副本日志
可以解决
互斥
选主
原子提交
4.2 异步系统中的共识
分布式系统可以分为同步系统、异步系统和部分同步系统，异步与同步相比是一种更通用的系统模型
4.2.1 FLP不可能定理
在一个完全异步系统中，即使只有一个节点出现了故障，也不存在一个算法使系统达成共识
在一个异步系统中，进程可以在任意时间返回响应，我们没有办法分辨一个进程是速度很慢还是已经崩溃
安全性、活性、容错性
FLP不可能定理提供的思路 — 不在尝试寻找完全异步系统中具备安全性、活性和容错性的解法，要么牺牲共识算法的一个属性，要么放宽对异步网络的假设
三种绕过FLP不可能定理（将异步系统转换为同步系统）
故障屏蔽
使用故障检测器
使用随机性算法
4.2.2 故障屏蔽
故障屏蔽假设故障的进程最终会恢复，并找到一种重新加入分布式系统的方式
如果没有收到来自某个进程的消息，就一直等待，直到收到预期的消息
4.2.3 使用故障检测器
超时故障检测器
完美
完全性
精确性
最终弱故障检测器
最终弱完全性
最终弱精确性
4.2.4 使用随机性算法
随机性算法使得“敌人”不能有效地阻碍系统达成共识，即实现拜占庭容错
随机性算法都无法严格满足安全性
随机算法的输出不仅取决于外部输入，还取决于执行过程中的随机概率
和传统选出领导节点在协作的模式不同，像区块链这类应用的共识是基于哪个节点最快计算出难题来达成的。区块链中的每一个新区块都由本轮最快计算出数学难题的节点添加，整个分布式网络持续不断地建设这条有时间戳的区块链，而承载了最多计算量的区块链正是达成了共识的主链（即累计计算难度最大）
4.3 同步系统中的共识
有理论支撑：在同步系统中，有不超过f个进程发生故障（其他节点始终是正常的），且错误进程数量f小于总进程数N，那么经过f+1轮消息传递后即可达成共识
4.4 Paxos
实际上，Paxos算法包含了一系列的共识算法，它有着许许多多的变种，它们都被归为Paxos族共识算法
关于Paxos的论文是在帮助SRC研究院解决问题中的到实现
确保分布式系统中的全局操作在部分节点失效的情况下依然能够正确完成
1989、1998、2001
4.4.1 基本概念
各个节点需要通过消息传递不断提出提案，最终整个系统接受同一个提案，进入一个一致的状态，即对某个提案达成共识
角色
客户端
提议者
接受者
学习者
4.4.2 问题描述
要实现一个不需要后台进程修复数据，同时能够容忍故障的系统，那么每个节点该如何决定是否接受某次写请求的值呢
前提：有多个接收者
1.每个节点只接受第一次收到的值
存在没有出现多数派的情况，没有提案被批准，算法无法终止
2.允许一个节点接受多个不同的值
违反安全性
一旦一个值被批准了，未来的提案就必须提议相同的提案值
设计一个两阶段协议，将已经批准的值告知后续的请求，让后续的提案也使用相同的值
3.接收者已经接受一个值之后就不会再接受别的值（需要知道提案的先后顺序）
4.4.3 Paxos算法实现流程
Basic Paxos
只决议出一个共识的值，之后都继续使用这个提案值
两个阶段
第一阶段
a.发送RPC请求
提议者收到来自客户端的请求后，选择一个最新的提案编号n，向超过半数的接收者广播Prepare消息，请求接受者对提案编号进行投票
注意，这里的请求RPC不包含提案值，只需要发送提案编号
b.响应RPC请求
接受者收到Prepare请求信息后进行判断
如果Prepare消息中的提案编号n大于之前接受的所有提案编号，则返回Promise消息进行响应，并承诺不会再接受任何编号小于n的提案。特别地，如果接收者之前接受了某个提案，那么Promise()相应还应将前一次提案的编号和对应的值一起发送给提议者
否则忽略该请求，但常常会回复一个拒绝相应
接受者持久化存储已经接受的最大提案编号、已接受的提案编号和已接受的提案值
第二阶段
a.发送RPC请求
当提议者接收到超过半数的接受者的Promise()响应后，提议者向多数派的接受者发起Accept(n，value)请求，这次要带上提案编号和提案值
关于提案值的选择
如果之前接受者的Promise()响应有返回已接受的值accept_VALUE，那么使用提案编号最大的已接受值作为提案值
如果没有返回accept_VALUE，那么提议者可以自由决定提案值。符合我们之前说的，Basic Paxos只决议出单一的提案值，并且之后都使用该值继续运行算法
b.响应RPC请求
接受者收到Accept（）请求后，在这期间如果接受者没有另外承诺提案编号比n更大的提案，则接受该提案，更新承诺的提案编号，保存已接受的提案
可见，接受提案和批准提案是不同的，接受提案是接受者单独决定的，而批准提案需要满足超过半数接受者接受提案
4.4.4 案例
情况1
提案已被批准
情况2
提案被接受，提议者可见
只要有一个接受者在Promise()响应中返回了提案值，就要用它来替换提案值
情况3
提案被接受，提议者不可见
在接受者还没完全批准小提案编号的那段时间，系统可以对大的提案编号进行批准
4.4.5 活锁
FLP不可能定理对Paxos算法依然生效
一个接着一个的新的提案，使得大家都没法发送第二阶段的Accept请求消息，形成活锁
解决活锁问题
引入随机超时，某个提议者发现提案没有被成功接受，则等待一个随机超时时间，让出机会，减少一直互相抢占的可能性
4.5 实验：使用Go语言实现Paxos共识算法
4.6 Multi-Paxos
Paxos算法就是用来实现状态机复制的
Basic Paxos决议出一个提案值，而Multi-Paxos决议出多个提案值
Multi-Paxos的目标就是高效地实现状态机日志复制
一个Paxos实例用来决议出一个值，多个Paxos实例是可以并行运行的
对每一条日志记录单独运行一次Paxos算法来决议出其中的值，重复运行Paxos算法即可创建一个日志的多份副本，从而实现状态机复制
如果每一条日志都通过一个Paxos实例来达成共识，那么每次都要至少两轮通信，这会产生大量的网络开销；所以需要对Basic Paxos做一些优化，以提升性能；这种经过一些列优化后的Paxos被称为Multi-Paxos；
4.6.1 确定日志索引
调整
1.添加一个关于日志索引的index参数到Basic Paxos的第一阶段和第二阶段，用来表示某一论Paxos正在决策哪一个日志条目
服务器上的每个日志条目可能存在三种状态
已经保存并已知被批准的日志条目
已经保存但不知道有没有被批准的日志条目
空的记录
我们需要解决的是，每个提案在最优情况下仍然需要两轮RPC通信的问题
针对提案冲突和消息轮次过多这两个问题，通过下面两个方式进行优化
1.领导者选举
从多个提议者中选择一个领导者，任意时刻只有领导者一个节点来提交提案，这样可以避免提案冲突。另外，如果领导者发生故障，则可以从提议者中重新选择一个领导者，所以不存在单点故障问题
2.减少第一阶段的请求
有了领导者之后，由于提案都是从领导者这里提出的，实际上可以从发起端保证提案编号是单调递增的，因此只需要对整个日志发送一次第一阶段的请求，后续就可以直接通过第二阶段来发送提案值，使得日志被批准
4.6.2 领导者选举
领导者选举是分布式系统中一个非常有用的算法，不仅可以服务于共识算法
Lamport
让服务器id最大的节点成为领导者
非常简单的策略，这种方式下系统中同时有两个领导者的概率是较小的；即使系统中有两个领导，Multi-Paxos也能正常工作，只是就回到了算法最初的多个提议者的状态
明显问题
如果恰好server_id最大的服务器的日志落后于其他节点，那么Paxos要先重复发送多次第一阶段消息以补齐领导者的日志，才能真正开始处理当前的客户端请求
4.6.3 减少请求
Paxos算法的第一阶段的两个主要作用
1.屏蔽过期的提案
Paxos需要保证接受者接受的提案编号是最新的，但由于每个日志条目的Paxos实例是相互独立的，所以每次请求只能怕屏蔽一个日志条目的提案，对于后面位置的日志信息不得而知
2.用已经接受的提案值来代替原本的提案值
当多个提议者并发进行提案的时候，要确保新提案的提案值与已接受的提案值相同
实际上，Multi-Paxos依然是需要第一阶段的，只不过Multi-Paxos需要在实现上面两个功能的同时，尽量减少第一阶段的请求次数
4.6.4 副本的完整性
我们需要每台机器的日志都是完整的，知道哪些日志是被批准的，这样状态机才能安全执行日志，达到一样的状态。要做到这一点，我们需要增加一些参数和逻辑来实现日志副本的完整性
优化
1.领导者在收到超过半数接受者的恢复后，同时在后台继续对未回复的接受者进行充实，尝试将提案值复制给所有的接受者（不能确保完全复制）
2.为了追踪哪些日志记录是被批准的，我们增加以下两个变量（接受者就知道哪些日志被批准了）
变量acceptedProposal是一个数组，acceptedPropposal[i]代表第i条目的提案编号
如果第i条日志中的命令被批准，则acceptedProposal[i]等于无穷大
每个节点都维护一个firstUnChosenIndex变量，表示第一个没有被批准的日志位置即第一个acceptedProposal[i]不等于无穷大的节点
发送第二阶段的Accept消息的时候带上变量firstUnChosenIndex，如果第i条日志满足i小于firstUnChosenIndex且提案编号相等，则认为第i条日志是被批准的日志，接受者会将acceptedProposal[i]设置为无穷大
3.在接受者的日志条目中仍然可能有一些前任领导留下的提案，前一任领导者还没有完成日志的复制或者批准就宕机了，换了一个领导者节点，这时候就需要接受者将其firatUnChosenInedx作为Accept请求的响应返回给领导者；领导者收到请求后，判断如果Acceptor.firatUnChosenIndex < Leader.firstUnChosenIndex，则在后台（异步）发送一个Success（index，v）RPC消息。接受者收到Success消息后，会更新被批准的日志记录。
通过上述3个优化就可以确保所有的接受者最终都能够知道被批准的日志记录
现在日志已被完全复制了
4.6.5 客户端请求
客户端请求的顺序决定了状态机执行命令的顺序
客户端第一次请求不知道谁是领导者
一条日志被批准并且被领导者的状态机执行之后，才能返回响应给客户端
异常
状态机批准一条命令，返回消息之前宕机，客户端认为请求失败，重试导致状态机执行两次
解决
客户端为每个请求都附加一个唯一id
4.6.6 配置变更
节点的id、节点网络地址、节点数量变更
尤其是系统中节点数量的改变会影响多数派数量的判断，我们必须保证不会出现两个重叠的多数派
解决
使用日志来管理配置变更，即将当前的系统配置当作一条日志记录存储起来，并与提案相关的日志记录一起复制和同步
Multi-Paxos增加了一个系统参数变量，表示新的配置在多少条记录之后才生效，用来平滑过渡配置变更，以及控制什么时候真正应用新的配置
a这个值是在系统启动的时候就指定的参数
这个参数和系统并发性能相关，该参数的大小会限制系统可以同时批准的日志条数
4.6.7 完整实现
基本概念
- 提案编号n，等于轮次和服务器server_id的组合
- T，超时时间，用于领导者选举算法
- a，并发限制因子，用于配置变更
1. 选举算法
1. 每个节点每隔T（ms）向其他服务器发送心跳消息
2. 如果一个节点在2T（ms）时间内没有收到比自己服务器id更大的心跳消息，那么它自己就转为领导者
2. 节点存储的状态信息
提议者（领导者）
需要持久化存储的状态
maxRound：提议者已知的最大提案轮次，用来生成最新的提案编号
需要存储的易失性状态
nextIndex：客户端请求要写的下一个日志索引
prepared：布尔值，用来表示是否可以不发送第一阶段消息
如果prepared值为True，即超过半数的Acceptor恢复了noMoreAccepted，则领导者不将不再需要发起第一阶段请求
初始值为False
接受者
需要持久化存储的状态
lastLogIndex：记录已经接受的最大的日志索引
minProposal：记录已经接受提案中的最小提案编号，初始值为0
状态机日志
acceptedProposal[i]:第i条日志最后接受的提案编号。初始化时为0；如果提案被批准，则acceptedPropoal[i]等于无穷大
acceptedValue[i]：第i条日志最后接受的提案值，初始化时为null
firstUnChosenIndex：i>0且acceptedProposal[i]<无穷大的最小日治所原因
3. 算法流程
略
4.7 其他Paxos变体
针对特定需求对Basic Paxos算法进行优化
其实有的变体的价值并不是作为一个完整的共识算法来实现的，而是提供一种优化的思路，这种思路可以用来优化Paxos或Raft等共识算法
4.7.1 Disk Paxos
2002 Lamport
和Basic Paxos一样分为两个阶段
不同
Basic Paxos通过消息传递进行进程间通信
Disk Paxos认为所有进程都由一个专属的磁盘块，可以将信息写入块中
Disk Paxos 适用于像SAN这样的存储网络
4.7.2 Cheap Paxos
优点
减少接受者的数量，以实现更好的性价比，也就是便宜
Basic Paxos需要2f+1个接受者来容忍f个节点故障，即正常运行的接受者也不能小于f+1个
Cheap Paxos认为发生故障只是小概率事件，它只需要f+1个接受者，以及f个廉价的辅助接收者
辅助接受者在正常执行期间保持空闲，只有出现故障才会替补上去工作，从而再次保证有f+1个接受者正常决议投票
4.7.3 Fast Paxos
Basic Paxos 从客户端将请求发出，到学习者收到已批准的提案需要3轮消息，而Fast Paxos只需要2轮
要求系统由3f+1个接受者组成
还需要客户端将请求发送到多个节点，而不是只发送到领导者
差别
Multi-Paxos中，领导者可以选择提案值，然后发送一条包含提案值的Accept消息
Fast Paxos，如果领导者没有想要提议的提案值，那么客户端可以直接发送Accept消息到接受者，接受者像Basic Paxos那样检查提案编号，如果检查通过，则向领导者和学习者广播已接收的提案值，使整个系统的日志一模一样
缺点
如果并发冲突很多，那么通信轮次也会变多
3+1
Fast Paxos 实际上耦合了客户端，算法扩展性变差
所需节点数目比Basic Paxos多很多
4.7.4 Mencius
试图解决Multi-Paxos单一领导者带来的性能瓶颈问题，同时能够在广域网（WAN）环境下良好工作
Mencius使用MultiLeader的解决方案，让节点轮流充当领导者
Mencius将所有接受者和领导者组成一个逻辑环，并预先分配好槽位（Slot），每个槽位都代表一个Paxos实例
4.7.5 EPaxos
无领导者的Paxos变体
目标
优化广域网的提交延迟
在所有节点实现负载均衡，从而实现高吞吐量，解决单一领导者的性能瓶颈问题
在节点变慢或故障时，能够优雅降级
EPaxos的消息数量与节点数量成线性关系，并且在普通情况下只需要一次往返时间RTT就能提交命令，在最坏的情况下也只需要经过两次往返时间
快速路径
慢速路径
想法
共识算法的本质就是确保状态机复制以相同的顺序执行相同的命令
Multi-Paxos是由领导者来决定顺序的
EPaxos没有领导者，于是维护命令的关系和序列号，通过依赖关系和序列号来保证所有副本最后提交的命令顺序是一样的
任意一个节点从客户端收到命令C后，接收该请求的节点称为命令领导者，命令领导者向2f个节点发送预接受消息
预接受消息
1.命令C
2.依赖关系deps，包含所有可能与当前命令存在依赖关系或冲突关系，但是未提交的命令列表
3.序列号seq，序列号用来打破循环依赖，seq的值被设为大于任何deps中的序列号值
时间戳排序队列
故意延迟某些消息的处理，以改进命令一致性的速度
4.7.6 Flexible Paxos
也称为FPaxos
讨论了Paxos中Quorum的组成
提出一种减少Multi-Paxos第二阶段消息数量和等待时间的方法
Flexible Paxos证明，Paxos算法只需要两个阶段的Quorum存在交集即可，并不一定需要Quorum是多数派节点
Q1+Q2>N
要求选举阶段Q1需要更多的投票，这样在第二阶段Q2就只需要更少的节点确认
4.7.7 WPaxos
针对广域网环境设计的多领导者（MultiLeader）Paxos变体
增加第一阶段Quorum的数量来减少第二阶段Quorum的数量
4.7.8 CASPaxos
新型无领导者的Paxos变体，避免了Multi-Paxos的单领导者可用性问题，CASPaxos创新性的地方在于其去掉了日志，从复制状态而不是入职日志的角度来实现状态机复制
分布式寄存器
除了没有日志和领导者，CASPaxos甚至没有心跳
4.7.9 其他
Vertical Paxos（垂直Paxos）主要能提出一种高效、可用的配置变更方案
Raft算法也是以Paxos协议族的一个变体
4.8 Raft算法
2013 也是用来保证日志完全相同地复制到多台服务器上，以实现状态机复制的算法
4.8.1 系统模型
Raft所运行的系统模型
服务器可能宕机、停止运行，过段时间再恢复，但不存在拜占庭故障，即节点的行为是非恶意的，不会篡改数据
消息可能丢失、延迟、乱序或重复；可能有网络分区，并在一段时间之后恢复
分析部分
1.领导者选举
2.算法正常运行
3.领导者变更时的安全性和一致性
最棘手、最关键，描述新选举出来的领导者要做的日志清理工作
4.处理旧领导者
5.客户端交互
6.配置变更
7.日志压缩
8.实现线性一致性
9.性能优化
4.8.2 基本概念
Raft算法中的服务器在任意时间只能处于以下三种状态之一
领导者
跟随者
候选者
任期就是一个逻辑时间
每台服务器需要维护一个currentTerm变量，表示服务器当前已知的最新任期号
变量currentTerm必须持久化存储，以便在服务器宕机重启时能够知道最新任期
任期对于Raft算法来说非常重要，任期能够帮助Raft识别过期的信息
4.8.3 领导者选举
Raft算法启动的第一步
领导者保持权威，必须向集群中的其他节点周期性地发送心跳包
空的AppendEntries消息
特性
安全性
一个任期内只会有一个领导者被选举出来
1.每个节点在同一任期内之只能投一次票，它将投给第一个满足条件的RequestVote请求，然后拒绝其他候选者的请求
1.投票变量votedFor，需要持久化，以便节点宕机重启后恢复投票信息，否则节点重启后votedFor信息丢失，会导致一个节点投票给不同的候选者
2.只有获得超过半数节点的选票才能成为领导者，两个不同的候选者无法在同一任期内都获得超过半数节点的选票
活性
确保系统最终能选出一个领导者
存在活锁问题，节点随机选择超时时间
4.8.4 日志复制
日志条目
索引：索引表示该日志条目在整个日志中的位置
任期号：日志条目首次被领导者创建时的任期
命令：应用于状态机的命令
通过索引和任期号唯一标识一条日志记录
与Paxos算法不同的地方
Paxos算法允许日志不连续地提交，但Raft算法的日志必须连续地提交，不允许出现日志空洞
一致性检查
保证日志较高的一致性
每个ApendEntries消息请求包含新日志条目之前一个日志条目的索引和日期
4.8.5 领导者更替
新领导上任时，对于冲突的日志无须采取任何特殊处理
我要想要保证的是
在机器恢复云习性之前，我们必须保证系统正常运行
随着时间的推移，让所有跟随者的日志最终都与其匹配
一旦状态机应用了一条日志中的一条命令，就必须确保其他状态机在同样索引的位置不会执行不同的命令，否则就违反了状态机复制的一致性
无论未来领导者如何变化，已提交的日志都必须保留在这些领导者的日志中
更改选举程序
如果节点的日志中没有正确提交的日志，则需要避免使其成为领导者
稍微修改提交日志的逻辑（延迟提交）
前面的定义是一个日志条目在多数派节点中存储即是已提交的日志
但是在某些时候，假如领导者刚复制到多数派就宕机了，则后续领导者必须延迟提交日志记录，直到我们知道这条记录是安全的
所谓安全的，就是后续领导者也会有这条日志
Raft算法通过比较日志，在选举期间，选择最有可能包含所有已提交日志的节点作为领导者。所谓最有可能，就是找出日志最新并且最完整的节点来作为领导者
判断任期号和索引
任期号优先级更大
4.8.6 选举限制举例
延迟提交的原因
日志仅仅是复制到多数派，Raft算法也并不能立即认为日志可以提交到并应用到状态机
之后某个节点可能覆盖这些日志，重新执行某些命令，这是违反状态机安全性的
4.8.7 延迟提交之前任期的日志条目
新的选举仍然不安全，继续修改提交规则
要求领导者想要提交一条日志（提交约束）
1.日志必须存储在超过半数的节点上
2.领导者必须看到超过半数的节点上还存储着至少一条自己任期内的日志
领导者只能提交自己任期的日志，从而间接提交之前任期的日志
结合新的选举规则和延迟提交规则，我们可以保证Raft的安全性
仍然有一点瑕疵
no-op空日志
只有索引和任期信息，命令信息为空，这类日志不会改变状态机的状态和输出，只是用来保持领导者的权威，驱动算法运行
no-op空日志可以使领导快速提交之前任期未提交的日志
4.8.8 清理不一致的日志
两种不一致的日志
缺失的日志
多出来的日志
领导者为跟随者保存变量nextIndex[]
用来表示要发送给跟随者的下一个日志条目的索引
对于跟随者i来说，领导者上的nextIndex[i]的初始值为1+领导者最后一条日志的索引
还可以通过nextIndex[]来修复日志
4.8.9 处理旧领导者
网络分区导致产生两个领导者
使用任期机制
每个RPC请求都包含发送方的任期
如果接收方发现发送方的任期陈旧，那么无论哪个过程，该RPC请求都会被拒绝。接收方将已知的最新任期回传给发送方，发送方知道自己任期过期后，转变到跟随者状态并更新其任期
如果接收方发现自己的任期陈旧，那么接收方将自己转为跟随者，更新自己的任期，然后正常地处理RPC请求
4.8.10 客户端协议
Raft算法要求必须由领导者来处理客户端请求
领导者将命令写入本地并复制、提交和执行到状态机之后，才会做出响应
解决一个命令被重复执行两次的风险
每个请求都附加上一个唯一id
每个命令只会被执行一次，这是实现线性一致性的关键要素
4.8.11 实现线性一致性
线性一致性要求读操作必须返回最近一次提交的写操作的结果
实现方式
将读请求当作写请求进行处理
可以通过在领导者增加一个变量readIndex来优化一致性读的实现
实际上还是保证领导者在当前任期提交过日志，确保领导者是真正的领导者
比上个策略更有效率，避免了对每个读请求都要写入磁盘和复制日志的开销
流程略
4.8.12 配置变更
两阶段协议
Raft算法通过联合共识来完成两阶段协议，即让新、旧两种配置都获得多数派选票
4.8.13 配置变更存在的Bug
4.8.14 极端情况下的活性问题
4.8.15 日志压缩
不进行压缩日志，会导致可用性问题
状态机只关注最终的状态，一旦一个日志条目被提交并应用于状态机，那么用于到达最终状态的中间状态和命令就不再需要了
日志压缩后得到快照
不同的系统有不同的日志压缩方式
共同点
1.不将压缩任务集中在领导者上，每个服务器独立地压缩其已提交的日志；对于日志量非常小的状态机，基于领导者的日志压缩也许才会更好
2.保存最后一条被丢弃的日志条目的索引和任期，用于日志一致性的检查
3.一旦丢弃了前面部分的日志，领导者就要承担两个新的责任
服务器重启需要将最新的快照加载到状态机后再接收日志
需要向较慢的跟随者发送一致的状态快照
4.8.16 基于内存的状态机的快照
状态机的数据集小于10GB的时候选择基于内存的状态机是合理的
需要存储的状态
最后一个日志条目的索引和任期分别记为lastIncludedIndex和lastIncludedTerm，另外还要存储该索引处的最新配置
1.如何再正常运行期间生成快照
序列化和写快照等操作都要与常规操作并发进行，避免服务不可用
写时复制技术
2.何时生成快照
引入快照大小和日志大小的比值
一旦日志大小超过之前的快照的大小乘以扩展因子，服务器就生成快照
扩展因子的设置需要权衡空间和带宽利用率
轮到领导者生成快照的时候，领导者先要“下台”，让其他服务器选出另一个领导者接替其工作
3.实现快照时需要关注的问题
1.保存和加载快照
2.传输快照
3.消除不安全的日志访问和丢弃日志条目
4.通过写时复制并发地生成快照
5.决定何时生成快照
4.8.17 基于磁盘的状态机的快照
对于日志大小达到几十或上百GB的状态机，需要使用磁盘作为主要存储系统
Log Cleaning 或 LSM Tree
以增量的方式清理日志并生成快照
优点
负载是均衡的
写入磁盘效率更高
传递快照更为简单
Log Cleaning
LSM Tree
4.8.18 性能优化
1.批处理和流水线
领导者可以在向跟随者并行复制日志的同时写入自己的磁盘
批处理
领导者的多次请求汇聚成一批发送给跟随者
汇集一批日志再写入磁盘
流水线
当领导者给跟随者发送了一批日志消息之后，它可以直接更新nextIndex，并且立刻发送后续的日志，不需要等待跟随者的返回
AppendEntries RPC对于日志一致性的检查保证了流水线的安全性
2.目击者节点
廉价的接受者
只参与选举的服务器，通常不参与日志复制，即不存储日志，而且根本没有状态机
节省成本，发生故障时，存储日志
3.Quorum大小优化
在选举不常发生的场景下，增加领导者选举Quorum的数量，可以降低复制时跟随者的确认信息
但是容错性降低
Q1+Q2>N
4.MultiRaft
适合大的Raft集群
解决的是心跳包过多的问题
百度的braft
4.9 Paxos vs Raft
Paxos（主要Multi-Paxos）和Raft其实非常相似
从所有节点中选出一个领导者，它接受所有的写操作，并将日志发送给跟随者
多数派复制了日志后，该日志提交，所有成员最终将该日志中的命令应用于它们的状态机
如果领导者失败了，则多数派会选出一个新的领导者
两者都满足状态机安全性和领导完整性
状态机安全性
如果一个节点上的状态机应用了某个索引上的日志，那么其他节点永远不会在同一个索引应用一个不同的日志
领导完整性
如果一个命令C在任期t和索引i处被领导者提交，那么任期大于t的任何领导者在索引i处存储同样的命令C
不同
表现形式
表现形式更为友好，更好的可理解性，对于实际构建系统的开发者来说是实用的
简单性
Paxos的复杂性
1.Raft按顺序提交日志，而Paxos允许日志不按顺序提交，但需要一个额外的协议来填补可能因此而出现的日志空洞
2.Raft中的所有日志的副本都有相同的索引、任期和命令，而Paxos中这些任期可能有所不同
高效的领导者选举算法
不会选出日志落后的节点
4.10 拜占庭容错和PBFT算法
在一个有f个拜占庭故障节点的系统中，至少有3f+1个节点才能够达成拜占庭共识
虽然在同步系统下对于拜占庭将军问题的确存在解，但是代价很高，需要n的f次幂的信息交换量
PBFT 一种实用的拜占庭容错算法，使用同步假设保证活性来绕过FLP不可能定理
容错数量
N>=3f+1
信息交换量
n方
PBFT（许可链）
依然要实现状态机复制，为了实现拜占庭容错，PBFT在增加一轮或多轮投票以获得多数派共识
其实也是Paxos算法的一类变体，也被称作Byzantine Paxos算法
PBFT算法非常依赖主节点，万一主节点正好是叛徒呢
为了避免主节点正好是叛徒，故意给不同的请求附加相同的序列号，或者故意附加不连续的序列号，这就需要更换主节点以更换视图，来保证PBFT算法的正确性
一般通过超时检测来触发视图切换，如果节点发现一个请求超时，那么为了防止无限等待请求（可能此时有节点故意破坏），节点会触发视图切换，并将视图切换消息广播给所有节点
4.11 本章小结
微信 - phxpaxos
阿里巴巴 - OceanBase
Basic Paxos流程是比较容易理解的，但Multi-Paxos却非常棘手
Raft算法的优点在于其有效的领导者选举算法
术语
状态机复制（SMR）
日志
已提交的日志条目
已批准的日志条目
领导者
多数派
提案编号
任期
第5章 分布式事务
分布式系统和数据是密不可分的；事务和存储系统也是密不可分的
5.1 什么是分布式事务
ACID的一致性和CAP定理中的一致性是不一样的
ACID中的C属于数据库事务领域的概念
指的是数据的完整性
CAP定理中的C指的是线性一致性
传统数据库的事务
一系列的数据库操作，工程师希望这些操作作为一个整体，不会因为失败而被分割，不必担心“这个操作完成”但“那个操作失败”了
不希望被其他事务看到多个操作的中间状态，而是作为一个整体一起完成
隔离级别：串行化
并行执行的一系列事务与按照某种串行的顺序来执行这些事务得到的结果是相同的
理解为单机事务的两种变体
1.同一份数据需要多个副本上更新，一个分布式事务需要更新所有的副本，如果有的节点提交了事务，有的节点回滚了事务，那么这样的结果对用户来说是无法接受的
2.数据进行了分区，银行账户为例，用户A的账户存储在节点N1，用户B的账户存储在节点N2，将用户A的钱转到用户B的账户中，这样的事务跨越了多个节点，还要同时保证整体数据一致和事务的ACID属性
重要
实现
无论是分布式系统还是单机系统，事务一致性（数据库层面的数据完整性）和持久性的实现并没有太大的差别
一致性是需要应用程序和数据库一起控制的属性，分布式事务通常不讨论ACID中的一致性
在向客户端返回响应之前，确保将数据存储在非易失性存储设备中即可，即可实现持久性
分布式事务原子性
原子提交
分布式系统发生部分失效，事务照样需要具备回滚能力
分布式事务隔离性
并发控制
主要是通过隔离其他尝试使用相同数据的并发事务以实现隔离性，并发控制经常涉及锁和多版本并发控制
5.2 原子提交
提交问题
单机事务的原子性实现
原子写
常见的机械磁盘可以保证512字节的原子写，即便遭遇突然断电意外情况，一般的机械磁盘也可以保证当前512字节的成功写入
更通用情况是，使用日志或WAL技术
先将操作的元数据写入一个单独的日志文件，同时还有表示操作是否完成的标记
基于硬盘原子写和日志文件来实现事务原子性的方法，在文件系统和数据库中广泛使用
原子提交协议（原子提交算法）
特性
协定性
所有进程都决议出同一个值，相当于所有进程要么一起提交事务，要么一起中止事务，不存在两个进程一个提交事务另一个中止事务的情况
有效性
如果所有进程都决定提交事务并且没有任何故障发生，那么最终整个系统将提交事务；只要有一个进程决定中止事务，系统最终将中止事务
终止性
弱中止条件
如果没有任何故障发生，那么所有进程最终都会做出决议（提交或中止事务）
强中止条件（非阻塞条件）
没有发生故障的进程最终会做出决议
原子提交协议实际上解决了分布式共识问题的一个子类
对事务的提交或终止达成共识
5.2.1 两阶段提交
两个角色
协调者
参与者
两个阶段
准备阶段（投票阶段）
1.协调者向所有参与者并行发送准备消息，询问参与者是否可以提交事务，并等待参与者响应
2.参与者检查执行事务所需条件和资源（如权限验证、上锁等），一切都准备好后参与者执行事务的所有操作，并记录操作日志
3.参与者响应协调者发起的请求。如果参与者发现事务的所有操作都执行成功，则返回一条“是”消息；如果参与者发现所需条件和资源检查失败，或者事务操作执行失败，则返回一条“否”信息
提交阶段
协调者收到所有参与者上一阶段的响应
如果所有参与者都回复“是”
1.协调者向所有参与者发送提交消息，指示参与者提交本次事务，等待参与者响应
2.参与者收到提交消息后，正式提交事务。完成事务提交操作后，清理占用的资源，例如释放锁，并记录操作日志
3.参与者中止事务后响应协调者，协调者收到所有参与者消息后，确认事务完成
只要有一个参与者回复“否”
1.协调者向所有参与者发送中止信息，指示参与者中止本次事务，等待参与者响应
2.参与者接收到中止信息后，利用其第一阶段记录的日志回滚所执行的事务操作，并清理占用的资源
3.中止后参与者响应协调者，协调者收到所有参与者消息后，确认事务中止
两阶段提交类似于投票，投票方（参与则）有一票否决权，只有全票通过，事务才能提交；否则事务中止
两阶段提交协议需要一定的容错性来预防各种问题
协调者可以设置一个超时等待时间
两阶段提交是一种阻塞提交算法，只满足弱终止条件
如果协调者发生故障，其他没有发生故障的参与者无法决定事务走向
同步阻塞问题、单点故障问题、数据不一致问题以及提交阶段不确定问题
Parallel Commits
将第一阶段最终的节点和结果写到全局事务日志中，这样在问题发生的时候就有办法通过查询其他节点的结果来处理异常情况
需要和共识算法一起工作
5.2.2 三阶段提交
解决两阶段提交协调者单点失效问题（阻塞性）
在两阶段提交的第一阶段和第二阶段之间插入一个预提交阶段
预提交阶段，协调者将第一阶段的投票结果发送给所有参与者，这样，如果在提交阶段协调者和收到消息的参与者发生了故障，则可以从剩下的参与这种选出一个来充当协调者，新的协调者可以根据预提交阶段的信息，判断是应该执行提交还是中止事务，继续安全地推进事务
流程
准备阶段（投票阶段）
1.协调者向所有参与者并行发送准备消息，询问参与者是否准备好执行事务，并等待参与者响应
2.参与者判断是否具备执行事务的条件。具体如何判断，不同的业务有着不同的计算方式。注意，如前所述，三阶段提交的第一阶段只确认是否具备基本的执行条件，并不会实际执行事务操作
3.参与者相应协调者发起的请求。如果参与者确认事务能够执行并提交，则返回一条“是”消息；如果参与者认为事务无法顺利完成，则返回一条“否”消息
预提交阶段
如果协调者收到上一阶段的响应都是“是”
1.协调者向所有参与者发送预提交信息，询问参与者是否可以执行并提交事务，并等待参与者响应
2.参与者收到预提交信息后，检查执行事务的必要条件和资源，条件满后执行事务的所有操作，并记录操作日志
3.参与者响应协调者发起的请求。如果参与者发现事务的所有操作都执行成功，则返回一条“是”消息；如果参与者发现所需条件和资源检查失败，或者事务操作执行失败，则返回一条“否”信息
如果准备阶段的响应中有一个参与者回复了“否”，或者等到超时都没有响应，那么协调者会向所有参与者发送中止信息，等待所有参与者中止事务并回复后，直接中止这次事务
提交阶段
协调者收到所有参与者预提交阶段的响应，如果所有参与者都回复“是”
1.协调者向所有参与者发送提交信息，指示参与者提交本次事务，等待参与者响应
2.参与者收到提交信息后，正式提交事务。完成事务提交操作后，清理占用的资源，例如释放锁等，并记录操作日志
3.完成后参与者响应协调者，协调者收到所有参与者的消息后，确认事务完成
如果预提交阶段的响应中只要有一个参与者回复了“否”，或者超时没有回复协调者，那么
1.协调者向所有参与者发送中止信息，指示参与者中止本次事务，等待参与者响应
2.参与者收到中止消息后，利用其预提交阶段记录的日志回滚事务操作，并清理占用的资源
3.参与者中止事务后响应协调者，协调者收到所有参与者消息后，确认事务中止
三阶段提交增加的可用性是以正确性为代价的
网络分区导致三阶段提交出错
出现数据不一致的状态
三阶段提交协议满足了强终止性，但是受网络分区影响并且通信代价较高，出于这个原因，两阶段提交仍然是实现事务原子性的第一选择
5.2.3 Paxos提交算法
使用Paxos算法来复制第一阶段的信息，实现一个多副本状态机，这样就不会做出相互冲突的决议
同时，Paxos算法也可以通过实现选主来选出新的协调者
备协调者方案
存在问题，如果同步数据产生延迟，甚至可能一个协调者发出中止事务的消息，而另一个协调者发出提交事务的消息
三种角色
资源管理者
资源管理者从客户端接收事务请求，或者有些系统资源管理者也作为客户端
总之，资源管理者发起事务，并创建Paxos提案，然后尝试和接收者运行Paxos算法来决议提交或中止事务
领导者
领导者用来协调整个Paxos提交算法，由选举能力，不存在单点故障的问题
接受者
接收者与资源管理者一起组成Paxos实例
流程
1. 开始于某个资源管理者，发送BeginCommit消息给领导者，请求提交事务
2. 领导者收到消息后，向所有资源管理者发送Prepare消息
3. 资源管理者收到Prepare消息后，如果一切准备就绪，决定参与本次事务的提交，就向所有接收者发送带有提案编号且值为Prepared的消息；反之，如果资源管理者认为条件不满足，要终止本次事务，就向所有接收者发送带有提案编号且值为Aborted的消息；这个阶段的消息统称为Phase 2a消息
4. 接受者收到Phase 2a消息后，如果接受者没有收到任何比消息中的提案编号更大的消息，则接收者接受该消息，并向领导者回复一条带有该提案编号和值的Phase 2b消息。如果接受者收到比提案编号更大的消息，那么忽略这条消息
5. 对于每一组Paxos实例，领导者统计其收到的接受者的响应信息。如果领导者收到f+1个值一样的消息，就认为该Paxos实例的多数派达成，那么根据Paxos算法，就认为这个资源管理者选定了这个值
6. 当每一组Paxos实例都选定完毕后，领导者进行最终确认。如果最终每个资源管理者选定的值都为Prepared，则代表所有资源管理者达成共识，一致认为该事务可以提交。领导者向所有资源管理器发送提交消息，资源管理器收到消息后提交事务
7. 如果领导者发现最终所有资源管理者的值中有一个是Aborted，则代表该资源管理者认为应该终止该事务。领导者向所有资源管理器发送中止消息，资源管理器收到消息后中止事务
优化
节点数目多
将资源管理者和接收者放在一台机器
消息传递
接受者一次发送多个Phase2b消息
接收者直接将投票信息发送给资源管理者
减少消息延迟
消息数量增加
Paxos提交算法是一种基于复制的容错性算法，Paxos实际上在两阶段提交的基础上引入了多个协调者（接受者），所以其有点事，只要多数派（f+1个）接受者正常运行，就不会阻塞事务运行，但该算法将Paxos算法和两阶段提交紧密耦合在一起，在工程上实现颇具难度
5.2.4 基于Quorum的提交协议
1982
解决三阶段提交的正确性问题
保证事务的原子性
Quorum本质是一种投票算法，核心思想
执行某种操作之前，必须先获得足够的票数
Quorum机制在数据冗余和原子提交中的应用是相似的
三个子协议
提交协议
在事务开始时使用
中止协议
当出现网络分区时使用
合并协议
当系统从网络分区中恢复过来的时候使用
和三阶段提交都是由Dale Skeen发明
缺点和三阶段类似
系统管理员可以动态调整Vc和Va的值，使得该协议在网络分区的情况下选择提交事务或中止事务的倾向性有着很大的弹性
5.2.5 Saga事务
长活事务LLT
一个批处理程序，用来计算大数据集相关的报告
保险公司的理赔，包含各个阶段，中间可能还需要人工输入数据
可能并不需要真正完全地隔离
Saga事务本质上由一连串的子事务T1、T2、Tn组成，可以与其他事务交替执行
Saga事务在分布式系统中的优点
既满足业务需求，又保持系统松耦合架构
一些没有提供事务的存储系统可以使用Saga事务的方式由业务方实现分布式事务
分布式系统的Saga事务只能作为一种折中的选择，并不能提供完整的事务特性
5.3 并发控制
并发控制是一种隔离并发事务以保证数据正确性的机制
三类
悲观并发控制
使用数据前加锁，为了正确性牺牲性能，主要用来实现串行化的隔离级别
乐观并发控制
乐观的认为并发事务是小概率事件，失败中止重试
多版本并发控制
主要用来实现快照隔离级别
5.3.1 两阶段锁
两阶段锁与前面提到的两阶段提交是完全不同的协议，前者是并发控制协议，后者属于原子提交协议
悲观并发控制
使用锁机制
锁的类型
读锁
共享锁
写锁
排他锁
两阶段锁
是根据获得锁和释放锁，将一个事务分为扩张阶段和收缩阶段
扩张阶段，事务不断上锁，但不允许释放任何锁；收缩阶段，事务陆续释放锁，但没有新的加锁动作
严格两阶段锁
除了满足两阶段锁，还要求事务必须在提交之后方可释放它持有的所有排他锁
强严格两阶段锁
要求事务只有在结束之后才能释放事务的所有锁
死锁
死锁避免
死锁预防
基于时间戳
等待-死亡
伤害-等待
无等待算法
谨慎等待
死锁检测
5.3.2 乐观并发控制
重点
放在事务提交时冲突检查上，而不是直接锁住数据不允许访问
基于检查的并发控制
为每个事务涉及的数据创建一个私有的副本，所有的更新操作都在私有副本上执行，再通过检查原来的数据是否有冲突来决定是否能够提交事务
读取阶段
校验阶段
写入阶段
基于时间戳的并发控制
通过为每个事务和每个数据项分配时间戳来实现算法
读时间戳
写时间戳
缺点
可能产生不可恢复的操作
一大难点
如何保证精确的时间源
5.3.3 多版本并发控制
1. 多版本两阶段锁
2. 多版本乐观并发控制
3. 多版本时间戳排序
4. 版本存储和垃圾回收
版本存储
仅追加存储
时间旅行存储
增量存储
垃圾回收策略
元组级别垃圾回收
事务级别垃圾回收
小结
串行化的快照隔离
通过追踪事务之间的读写操作，按照时间戳生成一个图，如果检测到图中存在环，则违背了串行化，需要中止其中一个事务来实现串行化
5.4 Percolator
除了Bigtable，Percolator还依赖一个单点授时、但时间源的授时服务，简称TSO
算法流程没看
5.5 本章小结
原子性
两阶段提交
三阶段提交
Paxos提交
基于Quorum的提交
Saga事务
隔离性
悲观并发控制
乐观并发控制
多版本并发控制
原子提交算法和并发控制必须结合起来，以保证分布式事务的完整特性
第6章 时间和事件顺序
开发者在设计软件时，默认状态和流程的演进是随着时间流动方向进行的
分布式系统实现并发控制，想要实现多版本并发控制就需要一个全局的授时服务
在分布式系统中，我们需要重新审视时间这个概念
6.1 物理时钟
机械钟
石英钟
原子钟
GPS时钟
6.2 时钟同步
NTP是一个时钟同步的网络协议
客户端/服务器架构，由于网络延迟和CPU处理速度会有很大的变化，为了精确同步时钟，NTP客户端必须计算其时间偏移量和来回通信延迟
一次NTP客户端与NTP服务端的通信即可同步客户端时间
NTP把NTP客户端应该设置的时间称为时间偏移
具体算法会使用统计学的方法，然后调整时钟频率以逐渐减少时间偏移，达到纠正时钟的目的
若NTP将本地时间向后调整，程序可能会产生异常
很多语言或操作系统提供单调时钟来解决
单调时钟不仅可以用来计算事件经过的时间，还可以用来判断两个事件发生的先后关系
只能在单机系统中使用，在分布式系统中有着很大的局限性
6.3 逻辑时钟
即使存在原子钟或GPS时钟等精准时钟，网络延迟误差还是让我们难以确认分布式系统中的时间顺序
逻辑时钟并不能得到完整的时间顺序，这是逻辑时钟和物理时钟最大的不同
全序关系
指全部元素可比较的关系，即集合中的任何两个元素是可以相互比较并确认大小的
偏序关系
指部分元素可以比较，只是部分元素有序，并不是全部元素都可以比较
将偏序关系扩展成全序关系
Lamport的方案是在逻辑时钟上附加进程编号，同时定义进程的全序关系，默认情况下使用逻辑时钟排序，逻辑时钟相同的情况下按照进程的全序关系进行排序
进程的全序关系
其实就是对比两个进程的优先级，由架构师任意定义
逻辑时钟的全序关系其实在偏序关系的基础上，通过定义一个任意的优先级，最终得到全序关系
不容忽视的是，这种全局关系的推断是比较随意的，并不一定符合实际情况。同样的逻辑时钟，进程的优先级选择不同，会得到不同的全序关系
分布式互斥问题
中心化的进程来统一分配资源是不可行的
中心分配资源没有按消息发生顺序授予资源
根源在网络
通过逻辑时钟来实现一种去中心化的算法
状态机复制能够解决分布式互斥问题
逻辑时钟可以帮助我们在分布式系统中实现多进程状态同步，需要所有进程都互相进行通信
Raft
任期在Raft中扮演了逻辑时钟
虽然不同的节点可能会处于不同任期，但最终服务器会检测到过期的信息，如过期的领导者
每个节点上的任期编号就是逻辑时钟，任期单调递增，通过心跳来交换当前的任期
如果一个节点发现自己的当前任期比另一个节点的小，那么就更新自己的任期为最新值
如果一个节点的请求来自一个任期过期的节点，那么请求将被拒绝
最重要的思想是
如何构建分布式系统的状态机
6.4 向量时钟
是在逻辑时钟的基础上改进而来的
主要思想
让每个进程都能够知道系统中其他所有进程的时钟，这样就无须额外执行进程的优先级
依旧只能得出分布式系统中的事件的偏序关系，不过向量时钟包含了其他节点的信息，通常用于数据冲突检测
更新
收到信息的时候，除了要更新自己的逻辑时钟，还要更新自己本地记录的所有节点的向量时钟
逻辑时钟只关注自己，而向量时钟需要关注整个系统
happened before
对于所有的下标k，都由Ca，k<=Cb，k
在[0,N]中至少存在一个l，使得Ca，l<Cb，l
版本向量
6.5 分布式快照
如何记录一个由多节点组成的分布式系统的快照
难点
分布式快照想要捕捉整个系统的全局状态，但是又不能让系统停止工作
对系统进行建模，将整个系统定义为一个有向图
算法不仅要记录一个节点的状态，还要记录这个节点的管道中的消息，这样就得到一个局部快照
而全局快照就是将所有节点的局部快照合并起来
通过传播一个额外的、不包含任何改变进程状态信息的maker消息来记录每个进程的快照
6.6 本章小结
逻辑时钟其实是用来实现分布式状态机的
向量时钟主要用来检测数据冲突的算法
无论是逻辑时间还是向量时钟，都需要两个节点相互通信才能够更新时钟
存在这种场景：虽然两个节点没有相互通信，但系统却要迫切地知道两个节点上的事件的先后顺序
分布式数据库系统
需要一个全局的物理时钟，也叫做全局授时服务
总之
逻辑时钟的重点是分布式状态机，如果你的分布式系统真的需要一个全局授时服务，那么还是需要选择TSO、基于物理时钟的算法或者混合逻辑时钟
第7章 案例研究
7.1 分布式文件系统
2003
分布式存储（包括文件系统）是构建分布式系统的关键，许多分布式应用都构建在分布式存储之上
并发性能、容错、复制和一致性
7.1.1 GFS的目标
设计目标
大型
高性能
全局
容错
面向大文件
重点操作
read
write
record append
7.1.2 架构
一个GFS集群包括一个Master节点和多个ChunkServer节点，并且若干客户端会与之交互
组件
Chunk
Master节点
客户端
ChunkServer节点
为了容错，Master和ChunkServer都被设计成在几秒内就能恢复状态和重启，另外Chunk会被复制成多个副本存储在多台机器上
7.1.3 读取文件
1. 客户端将要读取的文件名和偏移量（Offset）转换为GFS的文件名和对应的Chunk索引（Chunk Index），向Master发起请求
2. Master在内存中的元数据查询对应Chunk所在的Chunk Handle 和 Chunk 副本位置（Chunk Loaction）返回给客户端
3. 客户端将Master返回给它的位置信息缓存起来，用文件名+Chunk Index作为关键字（注意：客户端之缓存元数据，不缓存Chunk数据）
4. 客户端会选择网络上最近的ChunkServer通信（在Google的数据中心中，IP地址是连续的，所以可以通过IP地址的差异判断网络位置的远近），发送Chunk Handle 和 Chunk字节范围（byte range）请求所需的数据
超过64MB的数据（一个Chunk），会将一个读请求拆分成两个读请求再发送到Master节点
7.1.4 写入文件
租约机制避免Master成为性能瓶颈
客户端的数据首先写入LRU缓存中（不直接写入硬盘）
7.1.5 一致性模型
只有数据修改操作才可以影响分布式系统的一致性，GFS中有三种修改操作
修改元数据
写数据
追加数据（Record Append，记录追加）
一致和已定义
GFS并不是强一致性的，如何处理上述的不一致或未定义的异常情况，取决于应用程序
7.1.6 其他
1. Chunk的大小为什么是64MB
2. 快照
GFS将快照生成的责任交给每个ChunkServer，节省了网络带宽
3. 数据完整性
小结
0 条评论
下一页
