从Paxos到Zookeeper笔记2——第2章：一致性协议
第2章：一致性协议
根据CAP理论，在P必须被满足的情况下，需要在C和A之间进行权衡。因此产生了一系列的一致性协议。
最著名的一致性理论就是二阶段提交协议、三阶段提交协议和Paxos算法。
本章介绍二阶段和三阶段协议的优缺点，并重点介绍Paxos算法。
2.1 2PC与3PC
每个节点知道自己的事务是否成功，但无法获取其他节点的结果。
为了让一个事务能够跨节点执行，则需要一个“协调者”来统一调度分布式节点的执行逻辑。
协调者通过调度参与的节点，来保证事务的运行，因此衍生出了二阶段提交和三阶段提交两种协议。
2.1.1 2PC
2PC指的是二阶段提交。
目前绝大部分关系型数据库采用二阶段提交协议来完成分布式事务处理的，利用该协议能够非常方便地完成所有分布式事务参与者的协调，统一决定事务的提交或回滚。
协议说明
阶段一：提交事务请求：
协调者询问各个参与者是否能够执行事务，所以又称“投票阶段”
（1）事务询问：
协调者询问参与者是否能够执行事务，然后等待参与者的响应
（2）执行事务：
各参与者节点执行事务操作，将Undo和Redo信息记录事务中
（3）参与者向协调者反馈
若执行成功则反馈yes，若失败则反馈no。
阶段二：执行事务提交
根据参与者的反馈情况，来决定是否要执行事务。
如果所有的参与者都反馈yes，那么就开始执行事务，（1）协调者发送提交请求（2）参与者开始执行事务 （3）反馈提交的结果 （4）完成事务
如果有任何一个反馈no，则中断事务，（1）发送回滚请求 （2）事务回滚 （3）反馈事务回滚结果 （4）中断事务
2PC的优缺点
优点：原理简单、实现方便
缺点：
同步阻塞（参与者必须等待其他参与者反馈完才可以执行）
单点问题（一旦协调者出现问题，将会很严重）
脑裂（有一部分收到了commit请求，另一部分没有收到，导致整个系统出现不一致的情况）
太过保守（任何一个节点失败都会导致事务的失败）
2.1.2 3PC
基于二阶段存在的同步阻塞、单点问题、脑裂、太过保守的问题，提出了改进的三阶段协议
三阶段将二阶段提出的“提交事务请求”一分为二，形成了CanCommit、PreCommit和doCommit三阶段的事务处理协议。
阶段一：CanCommit
（1）事务询问：
协调者向参与者询问是否能够执行事务
（2）协调者接收反馈
参与者会根据情况回答yes还是no
阶段二：PreCommit
根据参与者的反馈，会得到两种结果。如果都是yes，则执行事务预提交，否则执行中断事务
事务预提交
（1）协调者发送预提交请求
（2）事务预提交
（3）参与者向协调者反馈事务执行的响应
中断事务
（1）发送中断请求
（2）中断事务
阶段三：doCommit
在预提交成功之后，才会进行真正的提交，否则中断事务
执行提交
（1）协调者发送提交请求给参与者
（2）协调者正式提交事务
（3）参与者反馈事务提交的结果
（4）完成事务
中断事务
（1）发送中断请求
（2）事务回滚
（3）反馈事务回滚结果
（4）中断事务
3PC的优缺点
（1）优点：降低参与者的阻塞范围，并能够在单点故障后达成一致
（2）缺点：如果在预提交之后，出现网络阻塞，那么参与者依然会进行事务的提交，出现数据不一致的情况。
2.2 Paxos算法
一种基于消息传递且高度容错特性的一致性算法，是目前解决分布式一致性最有效的算法之一。
Paxos解决的问题
如果在一个可能异常的分布式系统中，快速且正确地让数据内部达成一致。
2.2.1 追本溯源
1982年，Lamport等人提出了一种计算机容错理论，并设想了以下场景
拜占庭帝国有很多军队，不同军队的将军之间必须指定一个统一的行动计划（进攻还是撤退），
但是，将军都是分开的，只能靠通讯员进行通信。然而，通讯员也可能有叛徒，会任意篡改消息。
在有叛徒的情况下，这在分布式系统中完成一致性几乎是不可能的。
因此在一致性算法中，假设信道是可靠的，没有叛徒。
1990年，Lamport又提出了一个理论解决了一致性的问题，同样他也假设了一个场景来解决一致性问题
古希腊有一个叫Paxos的小岛，岛上通过议会的形式通过法令，议会中的*通过信使进行消息传递。
*和信使都是兼职的，他们随时都会离开议会，也可能重复传递消息，也可能一去不复返。
因此，议会协议要保证这种情况下法令仍然可以正确的产生。
2.2.2 Paxos理论的诞生
由于Lamport使用了故事的方式进行算法的描述，导致当时的委员会没人能够读懂这个算法，委员会要求他用严谨的数学证明他的算法，但是Lamport拒绝了。
1996年，其他人帮助Lamport用数学的形式化术语定义并证明了Paxos算法。
2001年，Lamport用通俗易懂的方式讲诉了原文。
2.2.3 Paxos算法详解
作者用2001年通俗易懂的版本来解释一致性算法的合理性。
问题描述
假设有一组可以提案的进程（*）集合，那么一致性算法需要保证以下几点
（1）这些被提出的提案、只有一个会被选定
（2）如果没有提案提出，那么就不会有被选定的提案
（3）当提案被选定后，进程可以获取被选定提案的信息
对于一致性来说，安全性（Safety）需求如下：
（1）只有被提出的提案才能被选定
（2）只能有一个值被选定
（3）某个进程认为改提案被选定，那么这个提案一定被选定
在Paxos一致性算法中，有三种参与角色，分别用Proposer(*)、Acceptor（接收者）和Learner（信使）来表示。
一个进程不止一种角色，不同参与者之间通过收发消息来通信，那么（1）进程直接可能会各种问题 （2）信息可能会丢失，但是不会被篡改
提案的选定
如果只有一个Acceptor，那么接收提案很简单，但是一旦出现问题，将是不可挽回的。
如果有多个Acceptor，那么Proposer向多个Acceptor发送提案，每个Acceptor都会批准该提案、如果足够多的Acceptor批准该提案，那么该提案就被选定了。
足够多的定义是什么？规定一个包含绝大部分Acceptor的子集，并且一个Acceptor只能批准一个提案，就能保证只有一个提案被选定了。
推导过程
如果：一个Acceptor必须批准它收到的第一个提案。
由此会产生如下问题
（1）如果有5个Proposer提出了5个提案刚好被5个Acceptor批准
（2）如果2个提案发给5个Acceptor，但有一个Acceptor出现异常，4个提案刚好各被2个Acceptor批准。
所以Paxos没有采用一个Acceptor的方法
所以：一个Acceptor能够批准不止一个提案
当某一个提案已经被半数以上的Acceptor批准了，那么就直接选定该提案。
通过引入一个全局唯一编号（从小到大），编号越大的提案越有可能被接收 。此时提案被变成了[编号，Value],即[编号，具体的提案内容]
但是如果[编号，Value] 的提案被选中，那么后续提案中已经被选中的Value（具体的提案内容）必须是一样的。
p2: 如果[M0,V0]的提案被选定了，那么所有编号比M0更高的，且被选中的提案，其Value值也必须是V0
要满足p2,则需要同时满足p2a和p2b
p2a:如果[M0,V0]被选定了，那么所有编号比M0更高的，且被Acceptor批准的提案，其Value值也必须是V0
p2b:如果[M0,V0]被选定了，那么之后任何Proposor产生的编号更高的提案，其Value值都为V0
proposal如何满足p2b
proposer在产生一个编号为Mn的提案时，必须知道当前比M0小，且最大，且被Acceptor接收的编号数。
并且proposer要求所有的Acceptor都不要再批准编号小于M0的提案。
当proposer发送请求前，需要Acceptor做出如下回应（prepare请求）
（1）Acceptor需要承诺，不再批准编号小于M0的提案
（2）Acceptor返回编号比M0小，且最大的编号数，当前Acceptor通过的编号最大的Value（Vn，提案的具体内容）
如果Proposer接收到半数以上Acceptor的prepare响应结果后，就可以发送accept请求
（1）他就可以产生编号为M0，Value值为Vn的提案
Acceptor如何满足p2a
Acceptor可能会收到Proposer的两种请求，分别是prepare请求和accept请求。
prepare请求：Acceptor可以在任何时候响应一个prepare请求
accept请求：在不违背Accept现有承诺下，可以响应任意accept请求。承诺为：如果一个Acceptor没有响应过编号大于M0的prepare请求。
算法陈诉
阶段一：
（1）Proposer提出一个编号为M0的提案，且向Acceptor超过半数的子集发送Prepare请求
（2）如果Acceptor接收到的M0大于任何已经批准过的编号，就将比当前M0小，且最大的编号的Value（具体提案）给Proposer。同时承诺不再批准小于M0的提案
阶段二：
（1）如果Proposer收到半数以上的Acceptor对于其发出的编号Vn和做出的承诺（prepare请求的响应），就把当前的[M0，V0]作为提案发送给Acceptor
（2）Acceptor收到这个提案后，只要acceptor没有接收比当前编号大的提案，就通过这个提案（通过accept请求）
提案的获取
当选定提案后，如何让Learner获取提案，作者提出了三种方案
方案一：
最简单的做法，一旦该提案被超过半数的Acceptor接收，就立刻通知Learner
缺点：费时间，如果有n个Acceptor和m个Learner，那么通信就需要m*n次
方案二：
当选定提案后，将结果通知给一个主Learner，再由主Learner通知其他Learner。
确定：主Learner一旦出现故障，将是不可挽回的
方案三：
针对方案二，进行了改进。因为一个Leaner不可靠，就可以通知给多个主Learner
当选定提案后，将结果通知给一个主Learner集合
通俗理解
proposer（*）是一群趋炎附势的人，当proposer收到一群acceptor的反馈后，知道某个提案最有可能被acceptor接收（编号最大的），然后proposer发送的提案都是这个提案。
acceptor是一群没有感情的接受机器，它只通过编号大且已经被当前acceptor同意的提案。
当提案通过过半后，acceptor就将结果告诉给Learner