一致性

简述

一致性，是指对每个节点一个数据的更新，整个集群都知道更新，并且是一致的。假设一个具有N个节点的分布式系统，当其满足以下条件时，我们说这个系统满足一致性：

• 全认同: 所有N个节点都认同一个结果
• 值合法: 该结果必须由N个节点中的过半节点提出
• 可结束: 决议过程在一定时间内结束，不会无休止地进行下去

面临着的问题

1. 消息传递异步无序: 现实网络不是一个可靠的信道，存在消息延时、丢失，节点间消息传递做不到同步有序
2. 节点宕机: 节点持续宕机，不会恢复
3. 节点宕机恢复: 节点宕机一段时间后恢复，在分布式系统中最常见
4. 网络分化: 网络链路出现问题，将N个节点隔离成多个部分
5. 拜占庭将军问题: 节点或宕机或逻辑失败，甚至不按套路出牌抛出干扰决议的信息

如下形象demo：

周五 我：晚上下班吃鸡 周六凌晨 xc：好的                             // 消息延迟 我：WC --------------------------------- 我：晚上下班吃鸡 xc：No (两小时后) xc：No problem！                     // 宕机节点恢复 我：WC --------------------------------- 我：晚上下班吃鸡 ...                                 // 节点宕机  --------------------------------- 我：晚上下班吃鸡 cx:好，我们去大保健！                 // 拜占庭将军 我：WC 

前面 已经讨论过，在分布式环境下，有很多不确定性因素，故障随时都回发生，也讲了CAP理论，BASE理论。我们希望达到在分布式环境下能搭建一个高可用的，且数据高一致性的服务，目标是这样，但CAP理论告诉我们要达到这样的理想环境是不可能的。这三者最多完全满足2个。

在这个前提下，P（分区容错性）是必然要满足的，因为毕竟是分布式，不能把所有的应用全放到一个服务器里面，这样服务器是吃不消的，而且也存在单点故障问题。
所以，只能从一致性和可用性中找平衡。

怎么个平衡法？在这种环境下出现了BASE理论：
即使无法做到强一致性，但分布式系统可以根据自己的业务特点，采用适当的方式来使系统达到最终的一致性；
BASE由Basically Avaliable 基本可用、Soft state 软状态、Eventually consistent 最终一致性组成，一句话概括就是：平时系统要求是基本可用，除开成功失败，运行有可容忍的延迟状态，但是，无论如何经过一段时间的延迟后系统最终必须达成数据是一致的。

其实可能发现不管是CAP理论，还是BASE理论，他们都是理论，这些理论是需要算法来实现的，今天讲的2PC、3PC、Paxos算法，ZAB算法就是干这事情。

所以今天要讲的这些的前提一定是分布式，解决的问题全部都是在分布式环境下，怎么让系统尽可能的高可用，而且数据能最终能达到一致。

2PC

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

阶段1

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

阶段2

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

实例

下面我们通过一个例子来说明两阶段提交协议的工作过程：
A组织B、C和D三个人去爬山：如果所有人都同意去爬山，那么活动将举行；如果有一人不同意去爬山，那么活动将取消。用 2PC 算法解决该问题的过程如下：

首先A将成为该活动的协调者，B、C和D将成为该活动的参与者。

阶段1：

1. A发邮件给B、C和D，提出下周三去爬山，问是否同意。那么此时A需要等待B、C和D的邮件。
2. B、C和D分别查看自己的日程安排表。B、C发现自己在当日没有活动安排，则发邮件告诉A它们同意下周三去爬山。由于某种原因， D白天没有查看邮 件。那么此时A、B和C均需要等待。到晚上的时候，D发现了A的邮件，然后查看日程安排，发现周三当天已经有别的安排，那么D回复A说活动取消吧。

阶段2：

1. 此时A收到了所有活动参与者的邮件，并且A发现D下周三不能去爬山。那么A将发邮件通知B、C和D，下周三爬山活动取消。
2. 此时B、C回复A太可惜了，D回复A不好意思。至此该事务终止。

数据库中的2PC

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

对一条数据的修改操作首先写undo日志，记录的数据原来的样子，接下来执行事务修改操作，把数据写到redo日志里面，万一捅娄子，事务失败了，可从undo里面回复数据。

不只是数据库，在很多企业里面，比如华为等提交数据库修改都回要求这样，你要新增一个字段，首先要把修改数据库的字段SQL提交给DBA（redo），这不够，还需要把删除你提交字段，把数据还原成你修改之前的语句也一并提交者叫（undo）

数据库通过undo与redo能保证数据的强一致性，要解决分布式事务的前提就是当个节点是支持事务的。

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

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

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

优缺点

在异步环境并且没有节点宕机的模型下，2PC可以满足全认同、值合法、可结束，是解决一致性问题的一种协议。从协调者接收到一次事务请求、发起提议到事务完成，经过2PC协议后增加了2次RTT(propose+commit)，带来的时延增加相对较少。
优点：

优点：原理简单，实现方便

缺点：

缺点：同步阻塞，单点问题，数据不一致，容错性不好

1. 同步阻塞

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

2. 单点问题

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

3. 数据不一致

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

4. 容错性不好

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

3PC

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

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

第一阶段canCommit

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

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

第二阶段PreCommit

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

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

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

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

第三阶段doCommit

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

执行提交

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

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

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

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

优缺点

与2PC区别：

第二阶段才写undo和redo事务日志
第三阶段协调者出现异常或网络超时参与者也会commit

优点：

改善同步阻塞
改善单点故障

缺点：

同步阻塞
单点故障
数据不一致
容错机制不完善

Paxos算法

这算法的提出者莱斯利·兰伯特在前面几篇论文中都不是以严谨的数学公式进行的。其实这个paxos算法也分成两阶段。首先这个图有2个角色，提议者与接收者。

第一阶段

提议者对接收者吼了一嗓子，我有个事情要告诉你们，当然这里接受者不只一个(一半要奇数个)，它也是个分布式集相当于星期一开早会，可耻的领导吼了句：“要开会了啊，我要公布一个编号为001的提案，收到请回复”。这个时候领导就会等着，等员工回复1“好的”，如果回复的数目超过一半，就会进行下一步。如果由于某些原因（接收者死机，网络问题，本身业务问题），导致通过的协议未超过一半，

这个时候的领导又会再吼一嗓子，当然气势没那凶残：“好了，怕了你们了，我要公布一个新的编号为002的提案，收到请回复1”【其实和上学时候老师讲课很像，老师经常问听懂了吗？听懂的回1，没懂的回2，只有回复1的占了大多数，才能讲下个知识点】

第二阶段

接下来到第二阶段，领导苦口婆心的把你们叫来开会了，今天编号002提案的内容是：“由于项目紧张，今天加班到12点，同意的请举手”这个时候如果绝大多少的接收者都同意，那么好，议案就这么决定了，如果员工反对或者直接夺门而去，那么领导又只能从第一个阶段开始：“大哥，大姐们，我有个新的提案003，快回会议室吧。。”

paxos的核心就是少数服从多数。

苦逼的领导（单点问题）：有这一帮凶残的下属，这领导要不可能被气死，要不也会辞职，这是单点问题。
凶神恶煞的下属（一致性问题）：如果员工一直都拒绝，故意和领导抬杆，最终要产生一个一致性的解决方案是不可能的。

所以paxos协议肯定不会只有一个提议者，作为下属的员工也不会那么强势

协议要求：如果接收者没有收到过提案编号，他必须接受第一个提案编号
如果接收者没有收到过其他协议，他必须接受第一个协议。
一旦一个提议被大家同意，那么之后的人再次提议，也是无效的，结果必须跟先前被大家接受的一致。

形象解说

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

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

例如：公司商定年会举办的地点，每个人都可以提出建议。在现实环境中我们可以在一个会议室共同讨论或在微信群中讨论（基于内存共享方式）；但在基于消息传递的分布式环境中每个人只能通过手机短信与其它人通过。如何在这种会延迟、丢失的环境中确定一个年会举办地点；

Paxos算法是这样解决这个问题：

1、每个人都可以提出建议、同意建议、接受建议
2、少数服从多数。只要建议被多数人同意即可确定该建议。
于是确定以下讨论方式：
1、只有被提出来的建议才能被大家同意。
2、最终只能确定一个建议
3、如果某个人认为大家同意了某 个建议，那么这个建议必须真的是被大家同意的

算法推论：
情况一：如果只有一个人提出建议怎么办？
如果只有一个建议被提出来那么大家必须赞同这个建议，因为如果不同意这个建议就无法确定一个年会举办地点。
P1:每一个人必须同意他收到的第一个建议， 基于这样的结论会出现以下问题：

张三给王五发短信说：我建议去上海举办年会！
王五给李四发短信说：我建议去广州举办年会！
李四给张三发短信说：我建议去北京举办年会！

根据P1：每个人必须同意他收到的第一个建议，那么张三、李四、王五最终获得的信息是不一致的。
所以再次规定：一个提议必须被大多数人同意才能生效。
那么说明一个人可以同时同意多个建议，如果一个人可以同时同意多个建议最终可能出现拜占庭将军问题导致最终结果不一致。（例如：张三同意到北京举办也同意到广州举办，那么李四将获得2票一票自己的，一票张三的。他会认为自己获得多数人支持所以就确定最终是到北京举办，同理王五也会同时获得2票，也认为大家最终决定到广州举办）。 所以要避免出现这种问题，某个人只能同意的多个提议中的内容相同（公司举办的地址）就不会出现这种问题。

最终协商结果是有2票是到同一个地方，这样就可以确认最终举办地！
那么就会引出 这样的一个结论：一旦同意某个建议，那么之后同意的建议中提议公司举办年会的地址必须一致。
问题出来了：如何确定什么是之前，什么 是之后
所以必须为提议分配一个编号，在提议之间建立一个全序关系。

情况二：
当张三、李四、王五三个人确定最终到郑州举办年会后。赵六、孙七2人由于手机没电，没收到通知，当他们2人开机后赵六给孙七发短信提议到海南举办，这个提议是孙七开机后第一次收到的提议，根据P1原则，他必须同意他接收到的第一个提议，所以孙七同意到海南举行年会。但这样就会导致孙七与张三、李四、王五他们确定的举办地点不一致。

为了避免出现以上问题。对P2进行具体说明：
P2a:一旦一个提议被大家同意，那么之后的人再次同意的提议中的公司举办年会的地址必须一致。
也就是说，孙七在开机后同意的第一个提议必须是“到郑州举办”才不会出现信息不一致的现象。但孙七开机后必须得接受第一个提议（P1原则），并且无法干涉提议中的内容（公司举办年会的地址）。所以最好的办法通过某种方式让赵六的提议中的内容与张三、李四同意的地址相同（到郑州举行）。这样孙七同意的第一个提议就是“到郑州举办”

我们再次对P2a进行修改：
P2b:一旦一个提议被大家同意，那么之后的人再次提议，提议中的公司举办年会的地址必须跟之前其它人解决的地址一致。

如何让刚开机的赵六提议的内容必须与张三、李四、王五讨论出来的一致（到郑州举行）？

我们继续对P2b进行强化修改：
P2C:如果有一个编号为N的提议具有V(提议的内容)，那么存在一个多数派，要么他们中所有人都没有同意编号小于N的任何提议，要么他们已经同意的所有编号小于N的提案中编号最大的那个提案具有V。

要满足P2C的要求，提议人在提议之前，首先要和多数人通信并获得他们进行的最后一次同意的提议。之后根据反馈的信息决定这次提议的内容，形成提议开始投票！

重点

所以整个投票决议分两个阶段：

1. 准备阶段

1、提议人选择一个编号N，并将准备信息发送给多数人。
2、如果收信人收到准备消息后，如果提议的编号大于它已经回复的所有准备信息。那么收信人将自己上次接受的提议内容回复给提议人，并承诺不再回复小于N的提议。

2. 同意阶段

1、当一个提议人收到多数人反馈的信息后，就进入同意阶段。它要向反馈给它信息的人再次发送一个请同意该提议的请求。包含编号N和根据P2C决定的提议内容（如果回复中没有反馈他们已经接受过的提议内容，则可以自由决定提议内容）
2、在不违背向其它人承诺的前提下，收到该提议请求后立即同意该请求。

假设：只有User1、User2、User3 三个人决定1+1等于几！

提案阶段

1. User1 提案编号为 1 并发送给User2和User3。

因User2 和User3 根据P2c它们并没有接受过小于编号为1的提案。所以它们可以接受该提议，并反馈给User1 不再接受小于编号1的提案。这时User1收到多数人的回复，将进入第2阶段。（如果收到的回复并不能形成多数人，那么将再次进入阶段1）

2. User2 提案编号为2 ；并发送给User1和User3。

因User1第一次收到提案，并且根据P2C它并没有同意过小于编号为2的提议，所以它可以接受该提议。User3由于接受过User1编号为1的提案，但User2的提案编号 2 > 1 所以User3也可以同意User2的提议，并反馈不再接受小于2的提议。User2也收到多数人的回复，将进行第2阶段。

3. User3提案编号为3 ；并发送给user1 和user2 .

因user1收到user3编号为3的提案 > user2编号为2的提案，所以接受user3的提案。
因user2收到User3编号为3的提案 > user1 编号为1的提案，所以接受user3的提案。
至此user3也收到多数人回复，将进行第2阶段。

同意阶段

1. user1 发送编号为1的提议，提议内容为：1+1=1；并发送给user2和User3 。

由于user2已经声明不再接受小于3的提案，所以拒绝user1的提案。
由于User3已经声明不再接受小于2的提案，所以同样拒绝User1的提案。
User1提议被多数人拒绝，再次`进入阶段1**.

2. user2 发送编号为2的提议，提议内容为：1+1=2；并发送给User1和User3

由于User1已经声明不再接受小于3的提案，所以拒绝user2的提议。
由于User3已经声明不再接受小于2的提案，该提案编号=2所以user3同意User2的提议。
但User2并没有获得多数人的同意，所以同样进行阶段1.

3. User3 发送编号为3的提议，提议内容为：1+1=3；并发送给User1和User2;

由于 user1 声明不再接受小于3的提案，所以同意User3的提议。
由于 user2 声明不再接受小于3的提案，所以同意User3的提议。

至此最终User3可以获得多数人的同意。

ZAB

很多人会误以为ZAB协议是Paxos的一种特殊实现，事实上他们是两种不同的协议。ZAB和Paxos最大的不同是，ZAB主要是为分布式主备系统设计的，而Paxos的实现是一致性状态机(state machine replication)

尽管ZAB不是Paxos的实现，但是ZAB也参考了一些Paxos的一些设计思想，比如：

1. leader向follows提出提案(proposal)
2. leader 需要在达到法定数量(半数以上)的follows确认之后才会进行commit
3. 每一个proposal都有一个纪元(epoch)号，类似于Paxos中的选票(ballot)

ZAB特性

1. 一致性保证

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

2. 全局有序(Total order)

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

3. 因果有序(Causal order) –

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

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

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)模式

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

恢复(recovery)模式

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

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

当 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选举机制

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

脑裂

ZAB为解决脑裂问题，要求集群内的节点数量为2N+1, 当网络分裂后，始终有一个集群的节点数量过半数，而另一个节点数量小于N+1, 因为选主需要过半数节点同意，所以任何情况下集群中都不可能出现大于一个leader的情况。

参考

2PC跟3PC通俗说
Paxos形象说知乎
李凯讲Paxos
不错的Paxos讲解
小灰浅谈