2.1.2 一致性算法
一致性算法[3]有很多，本节只简单介绍2PC、3PC、Paxos、Raft、ZAB这几种。生产系统里常用的软件大都实现并改进了这些一致性算法。
[3] 李海翔. 分布式数据库原理､架构与实践[M]. 北京：机械工业出版社，2021：3-55.
1．2PC
2PC（two phase commit，两阶段提交）是使分布式系统的所有工作实例，在事务提交时保持一致性而设计的一种算法。很多分布式数据库都是使用2PC作为提交协议算法的，比如Greenplum、Google Spanner。提交的受众有两个角色：参与者和协调者。
第一阶段，协调者记录本地日志信息，发送询问给各个参与者，然后等待；参与者回复自己是否可以提交，如果可以提交，参与者也记录本地日志。
第二阶段，如果协调者收到所有参与者的确认信息，则记录本地提交日志，然后给各个参与者发送提交信息，参与者收到后记录本地提交日志，返回确认信息给协调者；如果协调者收到任何一个参与者的中止信息，则会记录本地中止日志，然后给各个参与者发送中止信息，参与者收到后记录本地中止日志，然后发送确认信息给协调者。
2PC算法的优点是原理简单、清晰，实现方便。缺点也很明显：协调者有单点故障；第二阶段不能保证强一致性，数据会不一致；参与者需要相互等候，同步阻塞。两阶段提交协议是本书的重点，在后续的源码分析章节里有详细的状态机描述和代码分析内容，读者可以学习到一个工业级软件Greenplum是如何改进和实现2PC的，以及各种异常情况的处理方法。
2．3PC
3PC算法基于2PC算法改造和升级而来。它引入了超时机制，并将2PC算法的第一阶段分成了两个阶段，所以一共有3个阶段：准备阶段、预提交阶段、提交阶段。参与者收到预提交请求后不做实际动作，进入预提交阶段，收到提交请求或者超时以后才完成实际操作，进入提交阶段。3PC算法的优点很明显，即在出现协调者单点故障的时候参与者也能自己进行提交。当然，如果这时候出现了网络分区，数据还是会不一致。
3．Paxos
Paxos[4]是一个强一致性算法，也是一个多数派算法。集群里面出现分歧的时候，每个节点都可以提出修改该条数据的提案，提案能否通过取决于是否有超过半数的节点同意该提案。按照Paxos算法策略，集群的节点有以下多种角色。
[4] Gray J, Lamport L. Consensus on transaction commit [J]. ACM Transactions on Database Systems, 2006, 31(1): 133-160.
● 客户端（client）：向分布式数据库发起请求的节点。
● 提案者（proposer）：向集群里面其他节点发起提案的节点。
● 接收者（acceptor/voter）：接收某个提案者的提案的节点。
● 学习者（learner）：提案通过后，进行数据复制的节点。
● 领导者（leader）：提案通过后，被选为领导者的节点。Paxos算法确保只有一个领导者。
Paxos算法在具体实施的时候又分为很多种，如Basic Paxos、Multi-Paxos、Cheap Paxos、Fast Paxos、Byzantine Paxos，还有一些是几种算法的综合变体。
4．Raft
Raft[5]也是一个强一致性算法，通过选举的方式选出领导者，然后进行日志处理。所以主要有两个阶段，第一阶段是领导者选举，第二阶段是日志复制。按照这样的逻辑，节点也有多种角色。
[5] Ongaro D, Ousterhout J. In search of an understandable consensus algorithm [J]. USENIX Annual Technical Conference, 2014: 305-319.
● 客户端（client）：向分布式数据库发起请求的节点。
● 候选人（candidate）：在领导者被选出来以前，各个节点都是候选人。
● 领导者（leader）：在选举结束以后，被选为领导者的候选人。只有领导者才能进行日志复制工作。它从客户端接收请求，在本地做完日志复制以后，再将日志发散到各个跟随者节点上。
● 跟随者（follower）：跟随者在接收到来自领导者的日志信息后，进行本机的日志复制。
Raft算法还有一个安全（safty）机制，保证了选举和日志复制过程中遇到异常也不会破坏强一致性。Raft算法的选举策略和Paxos算法的类似，利用多数原则来确定完成投票。
5．Zab
Zab是Zookeeper Atomic Broadcast（Zookeeper原子广播）的缩写，是在ZooKeeper产品里面使用的算法。Zookeeper有跟随者和领导者两个角色，跟随者向领导者发起事务提交请求，领导者接收事务提交请求，用Zab算法将数据广播到各个节点上。Zookeeper的数据按照一个树形结构存储。这时候Zab算法也要保证事务提交的顺序正确和异常处理正确等。
提示 本节简单介绍了几种一致性算法。2PC算法和3PC算法要求所有节点提交成功，而Paxos算法、Raft算法等只需要一半以上的节点提交成功，在算法策略上有本质差异。