一致性算法-doola

2PC

2PC(tow phase commit)两阶段提交。它本身是一致强一致性算法，所谓的两个阶段是指：第一阶段：准备阶段(投票阶段) 第二阶段：提交阶段(执行阶段)。我们将提议的节点称为协调者(coordinator)，其他参与决议节点称为参与者(participants, 或cohorts)。

在阶段1中，协调者发起一个提议，分别问询各参与者是否接受

在阶段2中，协调者根据参与者的反馈，提交或中止事务，如果参与者全部同意则提交，只要有一个参与者不同意就中止

在innodb存储引擎，对数据库的修改都会写到undo和redo中，不只是数据库，很多需要事务支持的都会用到这个思路。

首先把整个分布式事务分两节点，首先第一阶段叫准备节点，事务的请求都发送给一个个的资源，这里的资源可以是数据库，也可以是其他支持事务的框架，他们会分别执行自己的事务，写日志到undo与redo，但是不提交事务。

当事务管理器收到了所以资源的反馈，事务都执行没报错后，事务管理器再发送commit指令让资源把事务提交，一旦发现任何一个资源在准备阶段没有执行成功，事务管理器会发送rollback，让所有的资源都回滚。这就是2pc，非常非常简单。

说他是强一致性的是他需要保证任何一个资源都成功，整个分布式事务才成功。

优点：原理简单，实现方便｜｜｜缺点：同步阻塞，单点问题，数据不一致，容错性不好

在二阶段提交的过程中，所有的节点都在等待其他节点的响应，无法进行其他操作。这种同步阻塞极大的限制了分布式系统的性能。

协调者在整个二阶段提交过程中很重要，如果协调者在提交阶段出现问题，那么整个流程将无法运转。更重要的是，其他参与者将会处于一直锁定事务资源的状态中，而无法继续完成事务操作。

假设当协调者向所有的参与者发送commit请求之后，发生了局部网络异常，或者是协调者在尚未发送完所有 commit请求之前自身发生了崩溃，导致最终只有部分参与者收到了commit请求。这将导致严重的数据不一致问题。

二阶段提交协议没有设计较为完善的容错机制，任意一个节点是失败都会导致整个事务的失败。

3PC

三阶段提交（Three-phase commit），是二阶段提交（2PC）的改进版本。与两阶段提交不同的是，三阶段提交有两个改动点。

引入超时机制。同时在协调者和参与者中都引入超时机制。在第一阶段和第二阶段中插入一个准备阶段。保证了在最后提交阶段之前各参与节点的状态是一致的。也就是说，除了引入超时机制之外，3PC把2PC的准备阶段再次一分为二，这样三阶段提交就有CanCommit、PreCommit、DoCommit三个阶段。

第一阶段canCommit

3PC的CanCommit阶段其实和2PC的准备阶段很像。协调者向参与者发送commit请求，参与者如果可以提交就返回Yes响应，否则返回No响应。

1.事务询问协调者向参与者发送CanCommit请求。询问是否可以执行事务提交操作。然后开始等待参与者的响应。2. 响应反馈参与者接到CanCommit请求之后，正常情况下，如果其自身认为可以顺利执行事务，则返回Yes响应，并进入预备状态。否则反馈No

第二阶段PreCommit

协调者根据参与者的反应情况来决定是否可以记性事务的PreCommit操作。根据响应情况，有以下两种可能。假如协调者从所有的参与者获得的反馈都是Yes响应，那么就会执行事务的预执行。

发送预提交请求协调者向参与者发送PreCommit请求，并进入Prepared阶段。事务预提交参与者接收到PreCommit请求后，会执行事务操作，并将undo和redo信息记录到事务日志中。响应反馈如果参与者成功的执行了事务操作，则返回ACK响应，同时开始等待最终指令。

假如有任何一个参与者向协调者发送了No响应，或者等待超时之后，协调者都没有接到参与者的响应，那么就执行事务的中断。

发送中断请求协调者向所有参与者发送abort请求。中断事务参与者收到来自协调者的abort请求之后（或超时之后，仍未收到协调者的请求），执行事务的中断。

第三阶段doCommit

该阶段进行真正的事务提交，也可以分为以下两种情况。

执行提交

发送提交请求协调接收到参与者发送的ACK响应，那么他将从预提交状态进入到提交状态。并向所有参与者发送doCommit请求。事务提交参与者接收到doCommit请求之后，执行正式的事务提交。并在完成事务提交之后释放所有事务资源。响应反馈事务提交完之后，向协调者发送Ack响应。完成事务协调者接收到所有参与者的ack响应之后，完成事务。

中断事务协调者没有接收到参与者发送的ACK响应（可能是接受者发送的不是ACK响应，也可能响应超时），那么就会执行中断事务。

发送中断请求协调者向所有参与者发送abort请求事务回滚参与者接收到abort请求之后，利用其在阶段二记录的undo信息来执行事务的回滚操作，并在完成回滚之后释放所有的事务资源。反馈结果参与者完成事务回滚之后，向协调者发送ACK消息中断事务协调者接收到参与者反馈的ACK消息之后，执行事务的中断。

所有数据库的分布式事务一般都是二阶段提交，而这三阶段的思想更多的被借鉴扩散成其他的算法。

Paxos

Paxos算法解决的问题是在一个可能发生消息延迟、丢失、重复的分布式系统中如何就某个值达成一致，保证不论发生以上任何异常，都不会破坏决议的一致性。这个“值”可能是一个数据的某，也可能是一条LOG等；根据不同的应用环境这个“值”也不同。

一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个一致性算法以保证每个节点看到的指令一致。

在Basic Paxos 算法中，存在提议者（Proposer），接受者（Acceptor），**学习者（Learner）**三种角色，它们的关系如下：

提议者（Proposer）：提议一个值，用于投票表决，可以将上图客户端 1 和客户端 2 看作提议者。实际上，提议者更多是集群内的节点，这里为了演示的方便，将客户端 1 和 2 看作提议者，不影响 Paxos 算法的实质

接受者（Acceptor）：对每个提议的值进行投票，并存储接受的值，例如，上图集群内的节点 A、B、C

学习者（Learner）：被告知投票的结果，接受达成共识的值，不参与投票的过程，存储接受数据

需要指出的是，一个节点，既可以是提议者，也可以是接受者。

https://blog.csdn.net/weixin_63566550/article/details/134655955

RAFT

https://cloud.tencent.com/developer/article/2168468

RAFT vs Paxos

Raft协议比paxos的优点是容易理解，容易实现。它强化了leader的地位，把整个协议可以清楚的分割成两个部分，并利用日志的连续性做了一些简化：
（1）Leader在时。由Leader向Follower同步日志
（2）Leader挂掉了，选一个新Leader，Leader选举算法。

但是本质上来说，它容易的地方在于流程清晰，描述更清晰，关键之处都给出了伪代码级别的描述，可以直接用于实现，而paxos最初的描述是针对非常理论的一致性问题，真正能应用于工程实现的mulit-paxos，Lamport老爷爷就提了个大概，之后也有人尝试对multi-paxos做出更为完整详细的描述，但是每个人描述的都不大一样。

Zookeeper的ZAB，Viewstamped Replication（VR），raft，multi-paxos，这些都可以被称之为Leader-based一致性协议。不同的是，multi-paxos leader是作为对经典paxos的优化而提出，通过选择一个proposer作为leader降低多个proposer引起冲突的频率，合并阶段一从而将一次决议的平均消息代价缩小到最优的两次，实际上就算有多个leader存在，算法还是安全的，只是退化为经典的paxos算法。而经典的paxos，从一个提案被提出到被接受分为两个阶段，第一个阶段去询问值，第二阶段根据询问的结果提出值。这两个阶段是无法分割的，两个阶段的每个细节都是精心设计的，相互关联，共同保障了协议的一致性。而VR,ZAB,Raft这些强调合法leader的唯一性协议，它们直接从leader的角度描述协议的流程，也从leader的角度出发论证正确性。但是实际上它们使用了和Paxos完全一样的原理来保证协议的安全性，当同时存在多个节点同时尝试成为leader或者不知一个节点认为自己时leader时，本质上它们和经典Paxos中多个proposer并存的情形没什么不同。

Paxos和raft都是一旦一个entries（raft协议叫日志，paxos叫提案，叫法而已）得到多数派的赞成，这个entries就会定下来，不丢失，值不更改，最终所有节点都会赞成它。Paxos中称为提案被决定，Raft,ZAB,VR称为日志被提交，这只是说法问题**。一个日志一旦被提交(或者决定），就不会丢失，也不可能更改，这一点这4个协议都是一致的**。Multi-paxos和Raft都用一个数字来标识leader的合法性，multi-paxos中叫proposer-id，Raft叫term，意义是一样的，multi-paxos proposer-id最大的Leader提出的决议才是有效的，raft协议中term最大的leader才是合法的。实际上raft协议在leader选举阶段，由于老leader可能也还存活，也会存在不只一个leader的情形，只是不存在term一样的两个leader，因为选举算法要求leader得到同一个term的多数派的同意，同时赞同的成员会承诺不接受term更小的任何消息。这样可以根据term大小来区分谁是合法的leader。Multi-paxos的区分leader的合法性策略其实是一样的，谁的proproser-id大谁合法，而proposer-id是唯一的。**因此它们其实在同一个时刻，都只会存在一个合法的leader。**同时raft协议的Leader选举算法，新选举出的Leader已经拥有全部的可以被提交的日志，而multi-paxos择不需要保证这一点，这也意味multi-paxos需要额外的流程从其它节点获取已经被提交的日志。因此raft协议日志可以简单的只从leader流向follower在raft协议中，而multi-paxos则需要额外的流程补全已提交的日志。需要注意的是日志可以被提交和日志已经被提交是两个概念，它们的区别就像是我前方有块石头和我得知我前方有块石头。但是实际上，Raft和multi-Paxos一旦日志可以被提交，就能会保证不丢失，multi-paxos天然保证了这一点，这也是为什么新leader对于尚未被确认已经提交的日志需要重新执行经典paxos的阶段一，来补全可能缺失的已经被提交的日志，Raft协议通过强制新Leader首先提交一个本term的no-op 日志，配合前面提到的Leader选举算法所保证的性质，确保了这一点。一条日志一旦被多数派的节点写入本地日志文件中，就可以被提交，但是leader只有得知这一点后，才会真正commit这条日志，此时日志才是已经被提交的。

Raft协议强调日志的连续性，multi-paxos则允许日志有空洞。日志的连续性蕴含了这样一条性质：如果两个不同节点上相同序号的日志，只要term相同，那么这两条日志必然相同，且这和这之前的日志必然也相同的，这使得leader想follower同步日志时，比对日志非常的快速和方便；同时Raft协议中日志的commit（提交）也是连续的，一条日志被提交，代表这条日志之前所有的日志都已被提交，一条日志可以被提交，代表之前所有的日志都可以被提交。日志的连续性使得Raft协议中，知道一个节点的日志情况非常简单，只需要获取它最后一条日志的序号和term。可以举个列子，A,B,C三台机器，C是Leader，term是3，A告诉C它们最后一个日志的序列号都是4，term都是3，那么C就知道A肯定有序列号为1,2,3,4的日志，而且和C中的序列号为1,2,3,4的日志一样，这是raft协议日志的连续性所强调的，好了那么Leader知道日志1，2，3，4已经被多数派（A,C)拥有了，可以提交了。同时，这也保证raft协议在leader选举的时候，一个多数派里必然存在一个节点拥有全部的已提交的日志，这是由于最后一条被commit的日志，至少被多数派记录，而由于日志的连续性，拥有最后一条commit的日志也就意味着拥有全部的commit日志，即至少有一个多数派拥有所有已commit的日志。并且只需要从一个多数集中选择最后出最后一条日志term最大且序号最大的节点作为leader，新leader必定是拥有全部已commit的日志(关于这一点的论证，可以通过反证法思考一下，多数集中节点A拥有最后一条已commit的日志，但是B没有，而B当选leader。根据选主的法则只能有两种可能(1)当选而A最后一条日志的term小于B；(2)A最后一条日志的term等于B，但是A的日志少于B。1,2可能嘛？）而对于multi-paxos来说，日志是有空洞的，每个日志需要单独被确认是否可以commit，也可以单独commit。因此当新leader产生后，它只好重新对每个未提交的日志进行确认，已确定它们是否可以被commit，甚至于新leader可能缺失可以被提交的日志，需要通过Paxos阶段一向其它节点学习到缺失的可以被提交的日志，当然这都可以通过向一个多数派询问完成（这个流程存在着很大的优化空间，例如可以将这个流程合并到leader选举阶段，可以将所有日志的确认和学习合并到一轮消息中，减少消息数目等）。但是无论是Raft还是multi-paxos，新leader对于那些未提交的日志，都需要重新提交，不能随意覆写，因为两者都无法判定这些未提交的日志是否已经被之前的leader提交了。所以本质上，两者是一样的。一个日志被多数派拥有，那么它就可以被提交，但是Leader需要通过某种方式得知这一点，同时为了已经被提交的日志不被新leader覆写，新leader需要拥有所有已经被提交的日志（或者说可以被提交，因为有时候并没有办法得知一条可以被提交的日志是否已经被提交，例如当只有老leader提交了该日志，并返回客户端成功，然而老leader挂了），之后才能正常工作，并且需要重新提交所有未commit的日志**。两者的区别在于Leader确认提交和获取所有可以被提交日志的方式上，而方式上的区别又是由于是日志是否连续造成的，Raft协议利用日志连续性，简化了这个过程**。

在Raft和multi-paxos协议确保安全性的原理上，更进一步的说，所有的凡是满足集群中存活的节点数还能构成一个多数派，一致性就能满足的算法，raft协议，paxos，zab，viewstamp都是利用了同一个性质：两个多数派集合之间存在一个公共成员。对于一致性协议来说，一旦一个变量的值被确定，那么这个变量的值应该是唯一的，不再更改的。Raft,paoxos等协议，对于一个变量v来说，一个由节点n1提出的值a只有被一个多数集q1认可并记录后，才会正式令v=a，如果另一个节点n2想要修改变量v的值为b，也需要一个多数集q2的认可，而q1和q2必然至少有一个共同的成员p,节点p已经记录了v=a。**因此只需要通过增加一些约束，让p能够告诉节点n2这个事实：v=a，使得n2放弃自己的提议，或者让节点p拒绝节点n2想要赋予v的值为b这个行为，都可以确保变量v的一致性不被破坏。**这个思想对于这个四个协议来说都是一样的，4个协议都使用一个唯一的整数作为标识符来标明leader的合法性，paxos叫做proposer-id，ZAB叫epoch，VR叫view，raft叫term。把leader看做是想要赋予变量v某个值的节点n1,n2，上面提到的情形中，如果n2是目前的合法leader，那么n2需要知道v=a这个事实，对于raft来说就是选择n2是已经记录了v=a的节点，对于multi-paxos来说，就是重新确认下v的值。如果n1是目前的合法leader，n2是老的leader，p就会根据leader的标识符拒绝掉n2的提案，n2的提案会由于得不到一个多数派的接受而失效。最直接的从理论上阐明这个原理的是经典的paxos算法，关于这个原理更具体的阐述可以看看我在如何浅显易懂地解说 Paxos 的算法？下的回答。所以确实在一定程度上可以视raft,ZAB,VR都是paxos算法的一种改进，一种简化，一种优化，一种具象化。Lamport老人家还是叼叼叼。。。。。。。不过值得一提的是，ZAB和raft作者确实是受了paxos很多启发，VR是几乎同时独立于paxos提出的。

Raft容易实现在于它的描述是非常规范的，包括了所有的实现细节。如上面的人说的有如伪代码。而paxos的描述侧重于理论，工程实现按照谷歌chubby论文中的说话，大家从paxos出现，写着写着，处理了n多实际中的细节之后，已经变成另外一个算法了，这时候正确性已经无法得到理论的保证。所以它的实现非常难，因为一致性协议实非常精妙的。小细节上没考虑好，整个协议的一致性就崩溃了，**而发现并更正细节上的错误在没有详尽的现成的参考的情况下是困难的，这需要对协议很深的理解。**而且在Raft协议的博士论文CONSENSUS: BRIDGING THEORY AND PRACTICE，两位作者手把手事无巨细的教你如何用raft协议构建一个复制状态机。我表示智商正常的大学生，都能看懂。我相信在未来一致性现在被提起来，肯定不是现在这样，大部分人觉得好难啊，实现更难。。。。应该会成为一种常用技术。

https://www.zhihu.com/question/36648084/answer/82332860

ZAB

ZAB特性

一致性保证

可靠提交(Reliable delivery) -如果一个事务 A 被一个server提交(committed)了，那么它最终一定会被所有的server提交

全局有序(Total order)

假设有A、B两个事务，有一台server先执行A再执行B，那么可以保证所有server上A始终都被在B之前执行

因果有序(Causal order) -

如果发送者在事务A提交之后再发送B,那么B必将在A之后执行

只要大多数（法定数量）节点启动，系统就行正常运行
当节点下线后重启，它必须保证能恢复到当前正在执行的事务

ZAB的具体实现

ZooKeeper由client、server两部分构成
client可以在任何一个server节点上进行读操作
client可以在任何一个server节点上发起写请求，非leader节点会把此次写请求转发到leader节点上。由leader节点执行
ZooKeeper使用改编的两阶段提交协议来保证server节点的事务一致性

ZXID

ZooKeeper会为每一个事务生成一个唯一且递增长度为64位的ZXID,ZXID由两部分组成：低32位表示计数器(counter)和高32位的纪元号(epoch)。epoch为当前leader在成为leader的时候生成的，且保证会比前一个leader的epoch大

实际上当新的leader选举成功后，会拿到当前集群中最大的一个ZXID(因为数据最新)，并去除这个ZXID的epoch,并将此epoch进行加1操作，作为自己的epoch。

历史队列(history queue)

每一个follower节点都会有一个先进先出（FIFO)的队列用来存放收到的事务请求，保证执行事务的顺序

可靠提交由ZAB的事务一致性协议保证
全局有序由TCP协议保证
因果有序由follower的历史队列(history queue)保证

ZAB工作模式

ZAB 协议是为分布式协调服务 ZooKeeper 专门设计的一种支持崩溃恢复的原子广播协议。在 ZooKeeper 中，主要依赖 ZAB 协议来实现分布式数据一致性。ZAB协议两种模式：消息广播和崩溃恢复。

广播(broadcast)模式

leader从客户端收到一个写请求
leader生成一个新的事务并为这个事务生成一个唯一的ZXID，
leader将这个事务发送给所有的follows节点，将带有 zxid 的消息作为一个提案(proposal)分发给所有 follower。
follower节点将收到的事务请求加入到历史队列(history queue)中，当 follower 接收到 proposal，先将 proposal 写到硬盘，写硬盘成功后再向 leader 回一个 ACK。
当leader收到大多数follower（超过法定数量）的ack消息，leader会发送commit请求
当follower收到commit请求时，会判断该事务的ZXID是不是比历史队列中的任何事务的ZXID都小，如果是则提交，如果不是则等待比它更小的事务的commit(保证顺序性)

恢复(recovery)模式

恢复模式大致可以分为四个阶段 选举、发现、同步、广播。

当leader崩溃后，集群进入选举阶段，开始选举出潜在的新leader(一般为集群中拥有最大ZXID的节点)
进入发现阶段，follower与潜在的新leader进行沟通，如果发现超过法定人数的follower同意，则潜在的新leader将epoch加1，进入新的纪元。新的leader产生
集群间进行数据同步，保证集群中各个节点的事务一致
集群恢复到广播模式，开始接受客户端的写请求

当 leader在commit之后但在发出commit消息之前宕机，即只有老leader自己commit了，而其它follower都没有收到commit消息新的leader也必须保证这个proposal被提交.(新的leader会重新发送该proprosal的commit消息)

当 leader产生某个proprosal之后但在发出消息之前宕机，即只有老leader自己有这个proproal，当老的leader重启后(此时左右follower),新的leader必须保证老的leader必须丢弃这个proprosal.(新的leader会通知上线后的老leader截断其epoch对应的最后一个commit的位置)

ZK选举机制

每个Server会发出一个投票,第一次都是投自己。投票信息：（myid，ZXID）
收集来自各个服务器的投票
处理投票并重新投票，处理逻辑：优先比较ZXID,然后比较myid
统计投票，只要超过半数的机器接收到同样的投票信息，就可以确定leader
改变服务器状态