关于java:一致性协议2PC3PCPaxos

一致性协定

2PC

2PC 即二阶段提交，是计算机网络尤其是在数据库畛域内，为了使基于分布式系统架构下的所有节点在进行事务处理过程中可能放弃原子性和一致性而设计的一种算法。
协定阐明：二阶段提交协定是将事务的提交过程分成两个阶段来进行解决。
阶段一：提交事务申请
投票阶段
阶段二：执行事务提交

执行阶段

优缺点

长处：原理简略，实现不便
毛病：同步阻塞、单点问题、脑裂、太过激进

同步阻塞

在二阶段提交的执行过程中，所有参加该事务操作的逻辑都处于阻塞状态

单点问题

协调者的角色在整个二阶段提交协定中起到了十分重要的作用，是单点的。

数据不统一

在二阶段提交协定的阶段二，即执行事务提交的时候，commit 申请并未发送到所有的参与者。

太过激进

如果在协调者批示参与者进行事务提交询问的过程中，参与者呈现故障而导致协调者始终无奈获取到所有参与者的响应信息的换，这时协调者只能依附本身的超时机制来判断是否须要中断事务，这样的策略显得比拟激进。换句话说，二阶段提交协定没有波及较为欠缺的容错机制，任意一个节点的失败都会导致整个事务的失败。

3PC

三阶段提交是 2PC 的改进版，将二阶段提交协定的“提交事务申请”过程一分为二，造成了由 CanCommit,PreCommit 和 doCommit 三个阶段组成的事务处理协定。

阶段一：CanCommit

1. 事务询问
2. 各参与者向协调者反馈事务询问的响应

阶段二：PreCommit，两种状况
执行事务预提交：协调者从所有的参与者取得的反馈都是 yes 响应，那么就会执行事务预提交。

1. 发送预提交申请
2. 事务预提交
3. 各参与者向协调者反馈事务执行的响应

中断事务：如果任何一个参与者向协调者反馈了 No 响应，或者在期待超时之后，协调者尚无奈接管到所有参与者的反馈响应，那么就会中断事务

1. 发送中断请求
2. 中断事务

阶段三：doCommit，两种状况

执行提交：

1. 发送提交申请
2. 事务提交
3. 反馈事务提交后果
4. 实现事务

中断事务

1. 发送中断请求
2. 事务回滚
3. 反馈事务回滚后果
4. 中断事务

须要留神，一旦进入阶段三，可能会存在以下两种故障。

• 协调者呈现问题
• 协调者和参与者之间的网络呈现故障

无论呈现那种状况，最终都会导致参与者无奈及时承受到来自协调者的 doCommit 或者 abort 申请，针对这样的异常情况，参与者都会在期待超时之后，持续进行事务提交。

优缺点

长处：相较于 2PC，3PC 最大的有点就是升高了参与者的阻塞范畴，并且可能在单点故障后持续达成统一。
毛病：容易呈现数据不一致性

Paxos

分布式一致性协定是一种基于消息传递且具备高度容错个性的一致性算法，是目前公认的解决分布式一致性问题最无效的算法之一。
Paxos 算法须要解决的问题就是如何在一个可能产生上述异样的分布式系统中，疾速且正确地在集群外部对某个数据的值达成一致性，并且保障不管产生以上任何异样，都不会毁坏整个零碎的一致性。

问题形容

假如有一组能够提出提案的过程汇合，那么对于一个一致性算法来说须要保障以下几点：

• 在这些被提出的提案中，只有一个会被选定
• 如果没有填被提出，那么就不会有被选定的提案
• 当一个提案被选定后，过程应该能够获取被选定的提案信息

对于一致性来说，安全性需要如下：

• 只有被提出的提案能力被选定
• 只能有一个值被选定
• 如果某个过程认为某个提案被选定了，那么这个提案必须是真的被选定的那个

从整体来说，Paxos 算法的指标就是要保障最终有一个提案会被选定，当提案被选定后，过程最终也能获取到被选定的提案。

有三种参加角色，咱们用 Proposer，Acceptor 和 Learner 来示意

假如不同参与者之间能够通过收发音讯来进行通信，那么：

• 每个参与者以任意的速度执行，可能会因为出错而进行，也可能会重启。同时，即便一个提案被选定后，所有的参与者也都有可能失败或重启，因而除非那些失败或重启的参与者能够记录某些信息，否则将无奈确定最终的值。
• 音讯在传输过程中可能会呈现不可预知的提早，也可能会反复或失落，然而音讯不会损坏，即音讯内容不会被篡改

推到过程

P1：一个 Acceptor 必须批准它收到的第一个提案。


因为以上两种状况，在 P1 的根底上，再加上一个提案
被选定须要由半数以上的 Acceptor 批准的需要暗示着一个 Acceptor 必须可能批准不止一个提案。

咱们应用一个全局的编号来惟一标识每一个被 Acceptor 批准的提案，当一个具备某 Value 值的提案被半数以上的 Acceptor 批准后，咱们就认为该 Value 被选定了，此时咱们也认为该提案被选定了。

P2：如果编号为 M0、Value 值为 V0 的提案被选定了，那么所有比编号 M0 更高的，且被选定的提案，其 Value 值必须也是 V0.
一个提案要被选定，其首先必须被至多一个 Acceptor 批准，因而咱们能够通过满足如下条件来满足 P2。
P2a：如果编号为 M0、Value 值为 V0 的提案被选定了，那么所有比编号 M0 更高的，且被 Acceptor 批准的提案，其 Value 值必须也是 V0。

P2b：如果一个提案【M0,V0】被选定后，那么之后任何 Proposer 产生的编号更高的提案，其 Value 值都为 V0。
因为一个提案必须在被 Proposer 提出后能力被 Acceptor 批准，因而 P2b 蕴含了 P2a，进而蕴含了 P2。
论证 P2b 成立。

P2c：对于任意的 Mn 和 Vn，如果提案【Mn，Vn】被提出，那么必定存在一个由半数以上的 Acceptor 组成的汇合 S，满足一下两个条件中的任意一个。

• S 中不存在任何批准过编号小于 Mn 的提案，其中编号最大的那个提案其 Value 值是 Vn。

Proposer 生成天
Proposer 抉择一个新的提案编号 Mn，而后向某个 Acceptor 汇合的成员发送申请，要求该汇合中的 Acceptor 做出如下回应。

• 向 Proposer 承诺，保障不再批准任何编号小于 Mn 的提案
• 如果 Acceptor 曾经批准过任何提案，那么其就向 Proposer 反馈以后该 Acceptor 曾经批准的编号小于 Mn 但为最大编号的哪个提案的值。

Acceptor 批准提案

• Prepare 申请：Acceptor 能够在任何时候响应一个 Prepare 申请
• Accept 申请：在不违反 Accept 现有承诺的前提下，能够任意响应 Accept 申请。

算法优化

尽可能地武略 Prepare 申请

算法陈说

阶段一

1. Proposer 抉择一个提案编号 Mn，而后向 Acceptor 的某个超过半数的子集成员发送编号为 Mn 的 Prepare 申请。
2. 如果一个 Acceptor 收到一个编号为 Mn 的 Prepare 申请，且编号 Mn 大于该 Acceptor 曾经响应的所有 Prepare 申请的编号，那么它就会将它曾经批准过的最大编号的提案作为响应反馈给 Propser，同时该 Acceptor 会承诺不会在批准任何编号小于 Mn 的提案。

阶段二

1. 如果 Proposer 收到来自半数以上的 Acceptor 对于其收回的编号 Mn 的 Prepare 申请的响应，那么它就会发送一个针对 [Mn，Vn] 提案的 Accept 申请给 Acceptor。
2. 如果 Acceptor 收到这个针对 [Mn，Vn] 提案的 Accept 申请，只有该 Acceptor 尚未对编号大于 Mn 的 Prepare 申请做出响应，它就能够通过这个提案。