导图社区 从Paxos到Zookeeper（2）
- 199
- 8
- 3
- 举报
从Paxos到Zookeeper（2）
《从Paxos到Zookeeper》第二章-个人学习笔记分享。希望对其他人有帮助
编辑于2019-10-14 15:20:29
- 相似推荐
- 大纲
从Paxos到Zookeeper（2）
一致性协议
2PC与3PC
概述
每一个分布式节点明确的知道自己执行的事务结果是成功还是失败，但无法知道其他节点的执行结果，因此为了保持事务的ACID特性，需要引入一个“协调者”（Coordinator）来调度所有的分布式节点称为“参与者”（Participant）。基于这种思想衍生出了二阶提交与三阶提交两种协议。
二阶提交（Two-Phase Commit，2PC）
概述
为了使基于分布式架构下的所有节点在进行事务处理过程中保持原子性与一致性而设计的一种算法
执行流程
阶段一：提交事务请求
1. 事务询问
协调者向所有的参与者发送事务内容，询问是否可以执行事务提交操作，并开始等待各个参与者响应
2. 执行事务
各参与者节点执行事务操作，并将undo与redo信息写入事务日志中
3. 各参与者向协调者反馈事务询问的响应
如果参与者成功执行了事务，就返回YES，如果不成功，就返回NO。
该阶段相当于各个参与者对协调者发送的事务内容进行是否可以执行的投票
阶段二：执行事务提交
根据参与者的响应，正常情况下有两种情况
执行事务提交（响应都为YES）
1. 发送提交请求
协调者向所有参与者节点发出Commit请求
2. 事务提交
参与者接收到Commit请求后，会正式执行事务提交操作，并在完成后释放事务执行期间占用的资源
3. 反馈事务提交结果
参与者完成事务提交以后，向协调者发送Ack消息
4. 完成事务
收到所有参与者节点的Ack消息后，完成事务
中断事务（响应有NO，或有超时）
1. 发送回滚请求
协调者向所有参与者节点发出Rollback请求
2. 事务回滚
参与者接收到Rollback请求后，会根据undo信息执行事务回滚操作，并在完成后释放事务执行期间占用的资源
3. 反馈事务回滚结果
参与者完成事务回滚以后，向协调者发送Ack消息
4. 中断事务
收到所有参与者节点的Ack消息后，完成事务中断
优点
原理简单
实现方便
缺点
同步阻塞
在二段提交过程中，所有参与该事务操作的逻辑都处于阻塞状态，也就是各个参与者在等待其他参与者响应的过程中都无法执行其他操作
单点问题
协调者的角色在整个二段提交协议中起到了非常重要的作用，如果协调者出现问题，参与者将锁定事务资源无法继续完成事务操作。
数据不一致
在阶段二过程中，有可能因为网络等原因出现只有部分参与者收到了Commit请求，从而出现各个节点数据不一致的问题
太过保守
没有容错机制，任何一个节点的失败都会导致整个事务的中断
三阶提交（Three-Phase Commit，3PC）
概述
2PC的改进版本，将2PC二阶段提交的过程一分为二，形成了CanCommit，PreCommit，DoCommit三个阶段组成的事务协议
执行流程
阶段一：CanCommit
1. 事务询问
协调者向所有的参与者发送一个包含事务内容的canCommit请求，询问是否可以执行事务提交操作，并开始等待各个参与者响应
2. 各参与者向协调者反馈事务询问的响应
如果参与者认为可以顺利执行事务，就反馈YES，并进入预备状态，否则反馈NO
该阶段相当于各个参与者对协调者发送的事务内容进行是否可以执行的投票
阶段二：PreCommit
根据参与者的响应，正常情况下有两种情况
执行事务预提交（响应都为YES）
1. 发送预提交请求
协调者向所有参与者节点发出preCommit请求，并进入prepared阶段
2. 预事务提交
参与者接收到PreCommit请求后，会执行事务，并将undo与redo信息写入事务日志中
3. 反馈事务提交结果
参与者完成事务提交以后，向协调者发送Ack消息，等待最终的指令：提交（Commit）或终止（abort）
中断事务（响应有NO，或有超时）
1. 发送回滚请求
协调者向所有参与者节点发出abort请求
2. 中断事务
收到所有参与者节点的Ack消息后，或者等待协调者响应超时，都会中断事务
阶段三：DoCommit
根据参与者的响应，正常情况下有两种情况
执行提交（响应都为YES）
1. 发送提交请求
协调者向所有参与者节点发出doCommit请求
2. 事务提交
参与者接收到doCommit请求后，会正式执行事务，并在完成后释放事务执行期间占用的资源
3. 反馈事务提交结果
参与者完成事务提交以后，向协调者发送Ack消息
4. 完成事务
收到所有参与者节点的Ack消息后，完成事务
中断事务（二阶段预提交后，参与者响应有NO，或有超时）
1. 发送回滚请求
协调者向所有参与者节点发出abort请求
2. 事务回滚
参与者接收到abort请求后，会根据undo信息执行事务回滚操作，并在完成后释放事务执行期间占用的资源
3. 反馈事务回滚结果
参与者完成事务回滚以后，向协调者发送Ack消息
4. 中断事务
收到所有参与者节点的Ack消息后，或者等待协调者响应超时，都会中断事务
可能会出现的问题
协调者出现故障
协调者与参与者之间的网络出现故障
解决方案
一旦参与者接收不到协调者的请求超时以后，都会进行事务提交
优点
降低了二阶段提交的阻塞范围
缺点
参与者收到preCommit消息后，一旦无法与协调者通信，将在超时后提交事务，在这种情况下，可能会出现数据的不一致性
Paxos算法
概述
一种基于消息传递具有高度容错特性的一致性算法，是目前公认的解决分布式一致性问题最有效的算法之一
Paxos场景
古希腊有一种Paxos小岛，岛上采用一会的形式通过法令，议会中议员通过信使进行消息传递，议员与信使都是兼职的，他们随时都有可能会离开议会，并且信使有可能传递重复的信息，也有可能一去不复返，因此议会要保证在这种情况下法令仍然能够正确的产生，并且不会起冲突。
问题描述
假设有一组可以提出提案的进程集合
对于一个一致性算法要保证一下几点
在这些提案中，只有一个被选定
如果没有提案被提出，就不会有选定的提案
当提案被选定以后，进程应该可以获取被选定的提案信息
对于一致性来说，安全性需求如下
只有被提出的提案才能被选定
只有一个提案被选定
如果某个进程认为某个提案被选定了，那么这个提案必须是真的被选定的那个
该一致性算法中，有三种参与角色
Proposer（提议者）
Acceptor（决策者）
Learner（最终决策学习者）
一个参与者可能扮演多个角色，假设不同的参与者之间可以通过收发消息来进行通信
每个参与者以任意的速度执行，可能会因为出错而停止，也可能会重启
消息在传输过程中可能会出现不可预知的延迟，也有可能会重复或者丢失，但消息不会被损坏，即消息内容不能被篡改
提案的选定
一个Acceptor
最简单的选定方式是只有一个Acceptor，Proposer发送给该Acceptor提案以后，Acceptor直接选择第一个提案为被选定的提案。但这种做法一旦Acceptor出问题，整个系统将无法正常工作。
多个Acceptor
Proposer向多个Acceptor集合发送提案，每个Acceptor都可能会批准（Accept）该提案，当足够多个Acceptor批准这个提案的时候，我们就认为该提案被选定了。
什么是足够多？
1. 足够多的集合是整个集合的子集
2. 这个集合大到包含Acceptor大多数成员
3. 每个Acceptor最多只能批准一个提案
推导过程
概述
在没有失败和消息丢失的情况下，如果我们希望即使只有一个提案被提出，仍然可以选出一个提案，这就暗示了如下约束
约束
P1 ： 一个Acceptor必须批准他收到的第一个提案
问题
如果多个提案被不同的Proposer同时提出，这可能会导致虽然每个Acceptor都批准了他收到的第一个提案，但是没有一个提案是多个人批准的。也就是没有多数的Acceptor集合
规定
一个提案被选定需要被半数以上的Acceptor接受
解决
这个规定就暗示了在P1的基础上，一个Acceptor能够批准不止一个提案。我们使用全局的编号来唯一的标识每一个Acceptor批准的提案，当一个具有某value的提案被半数以上的Acceptor批准以后，我们就认为该value被选定。注意，提案和value不是一个概念，提案是由一个编号与value组成的结构体，因此我们用【编号，Value】来表示一个提案。
提案编号
给每个提案加上一个提案编号，表示提案被提出的顺序，不同的编号可以有相同的内容
Value
提案的内容
问题
虽然允许多个提案被选定，但必须保证所有被选定的提案都具有相同的value值。否则又会出现不一致
约束
P2：如果编号为M,Value为V的提案（即【M，V】）被选定了，那么所有比M编号更高的，且被选定的提案，其Value值必须也是V。
P2需求
因为提案编号是全序的，P2就保证了只有一个Value值被选定这一关键安全性属性。同时，一个提案被选定，其首先必须被至少一个Acceptor批准，因此我们可以通过满足如下条件来满足P2
约束
P2a：如果编号为M,Value为V的提案（即【M，V】）被选定了，那么所有比编号M更高的，且Acceptor批准的提案，Value值必须也是V。
问题
假设总的有5个Acceptor。Proposer2提出[M1,V1]的提案，Acceptor2~5（半数以上）均接受了该提案，于是对于Acceptor2~5和Proposer2来讲，它们都认为V1被选定。Acceptor1刚刚从宕机状态恢复过来（之前Acceptor1没有收到过任何提案），此时Proposer1向Acceptor1发送了[M2,V2]的提案（V2≠V1且M2>M1），对于Acceptor1来讲，这是它收到的第一个提案。根据P1（一个Acceptor必须接受它收到的第一个提案。）,Acceptor1必须接受该提案！同时Acceptor1认为V2被选定。这就出现了两个问题
1. Acceptor1认为V2被选定，Acceptor2~5和Proposer2认为V1被选定。出现了不一致。
2. V1被选定了，但是编号更高的被Acceptor1接受的提案[M2,V2]的value为V2，且V2≠V1。这就跟P2a（如果某个value为v的提案被选定了，那么每个编号更高的被Acceptor接受的提案的value必须也是v）矛盾了。
约束
P2b：如果一个提案【M，V】被选定后，那么之后任何Proposer产生的编号更高的提案，其Value的值都为V。
问题
由P2b可推出P2a，进而推出P2。如何确保在某个Value为V的提案被选定后，Proposer提出的编号更高的提案的Value都是V呢？
约束
P2c：对于任意的N和V，如果提案[N, V]被提出，那么存在一个半数以上的Acceptor组成的集合S，满足以下两个条件中的任意一个
1. S中每个Acceptor都没有批准过编号小于N的提案
2. S中Acceptor接受过的最大编号的提案的value为V
Proposer生成提案
概述
在P2C的条件下如何进行提案的生成。对于一个Proposer来说，获取那些已经通过的提案远比预测未来可能会通过的提案来的简单。因此Proposer在产生一个编号为M的提案时，必须要知道当前某一个将要或已经被半数以上Acceptor批准的编号小于M但未最大的编号的提案。并且，Proposer会要求所有Acceptor都不要批准任何编号小于M的提案。
也就是Proposer生成提案之前，应该先去『学习』已经被选定或者可能被选定的value，然后以该value作为自己提出的提案的value。如果没有value被选定，Proposer才可以自己决定value的值。这样才能达成一致。这个学习的阶段是通过一个『Prepare请求』实现的
提案生成算法
1. Proposer选择一个新的提案编号N，然后向某个Acceptor集合（半数以上）发送请求，要求该集合中的每个Acceptor做出如下响应（response），我们将该请求称为编号为N的Prepare请求
向Proposer承诺保证不再接受任何编号小于N的提案
如果Acceptor已经接受过提案，那么就向Proposer响应已经接受过的编号小于N的最大编号的提案
2. 如果Proposer收到了半数以上的Acceptor的响应，那么它就可以生成编号为N，Value为V的提案[N,V]。这里的V是所有的响应中编号最大的提案的Value。如果所有的响应中都没有提案，那 么此时V就可以由Proposer自己选择
生成提案后，Proposer将该提案发送给半数以上的Acceptor集合，并期望这些Acceptor能接受该提案。我们称该请求为Accept请求。（注意：此时接受Accept请求的Acceptor集合不一定是之前响应Prepare请求的Acceptor集合）
Acceptor批准提案
概述
Acceptor可以忽略任何请求（包括Prepare请求和Accept请求）而不用担心破坏算法的安全性。因此，我们这里要讨论的是什么时候Acceptor可以响应一个请求
约束
P1a：一个Acceptor只要尚未响应过任何编号大于N的Prepare请求，那么他就可以接受这个编号为N的提案。
算法优化
假设一个Acceptor收到了一个编号为N的Prepare请求，但此时该Acceptor已经对编号大于N的Prepare请求做出了响应，因此它肯定不会再批准任何新的编号为N的提案，那么很显然，Acceptor就没必要对这个Prepare请求作出响应，于是Acceptor可以选择忽略这样的Prepare请求。同时，Acceptor也可以忽略掉那些它已经批准过的提案的Prepare请求
算法陈述
阶段一
1. Proposer选择一个提案编号M，然后向Acceptor的某个超过半数的子集成员发送编号为M的Prepare请求。
2. 如果一个Acceptor收到一个编号为M的Prepare请求，且编号M大于该Acceptor已经响应的所有Prepare请求的编号，那么它就会把已经批准过的最大的编号的提案作为相应反馈给Proposer，同时该Acceptor会承诺不会在批准任何编号小于M的提案。
阶段二
1. 如果Proposer收到来自半数以上的Acceptor对于其发出的编号为M的Prepare请求的响应，那么它就会发送一个针对【M，V】提案的Accepte请求给Acceptor。 注意：V的值就是收到的响应中编号最大的提案的值，如果响应中不包含任何提案，那么他就是任意值
2. 如果Acceptor收到的这个针对【M，V】的提案的Accept请求，只要该Acceptor尚未对编号大于M的Prepare请求作出响应，他就可以通过这个提案。
提案的获取
方案一
一旦Acceptor批准了一个提案，就将该提案发送给所有的Learner
方案二
让所有的Acceptor将它们对提案的批准情况，统一发送给一个Learner，再由它通知其他的Learner
方案三
方案二的主节点存在单点问题，可以将主Leaner的范围扩大，即Acceptor可以将批准信息发送给一个特定的Learner集合，该集合中每个Learner都可以在一个提案被选定后通知其他Leaner
通过选取主Proposer保证算法的活性