<从PAXOS到ZOOKEEPER分布式一致性原理与实践>读书笔记-paxos算法
本文属于分布式系统学习笔记系列,上一篇笔记梳理了2阶段、3阶段提交。本文来梳理paxos算法。背景:本书第二章里面作者详细介绍了paxos算法的由来,这里从2.2.3开始。Paxos算法实现的是分布式系统多个结点之上数据的一致性,这个算法有如下特性1.基于消息传递,允许消息传输的丢失,重复,乱序,但是不允许消息被攥改2.在结点数少于半数失效的情况下仍然能正常的工
本文属于分布式系统学习笔记系列,上一篇笔记梳理了2阶段、3阶段提交。本文来梳理paxos算法。
背景:
本书第二章里面作者详细介绍了paxos算法的由来,这里从2.2.3开始。
Paxos算法实现的是分布式系统多个结点之上数据的一致性,这个算法有如下特性
1.基于消息传递,允许消息传输的丢失,重复,乱序,但是不允许消息被攥改
2.在结点数少于半数失效的情况下仍然能正常的工作,结点失效可以在任何时候发生而不影响算法正常执行。
paxos算法
算法中的参与者主要分为三个角色,同时每个参与者又可兼领多个角色:
⑴proposer 提出提案,提案信息包括提案编号和提议的value;
⑵acceptor 收到提案后可以接受(accept)提案;
⑶learner 只能"学习"被批准的提案;
问题描述,一致性算法需要保证:
- 决议(value)只有在被proposers提出后才能被批准(未经批准的决议称为"提案(proposal)");
- 在一次Paxos算法的执行实例中,只批准(chosen)一个value;
- learners只能获得被批准(chosen)的value;
接下来作者介绍了提案的选定及推导过程。
Proposer生成提案:
- 向Proposer承诺,保证不再批准任何编号小于Mn的提案。
- 如果acceptor 已经审批任何提案,那么其就向Proposer反馈当前acceptor 已经批准的编号小于Mn但为最大编号的那个提案的值。
Acceptor批准提案:
- Prepare请求:acceptor 可以在任何时候响应一个prepare请求。
- Accept请求:在不违背accept现有承诺情况下,可以响应任何accept请求。
通过选取主Proposer保证算法活性
这样一来,只要leader和过半的Acceptor能够正常的进行网络通信,那么但凡leader提出一个编号更高的提案,该提案终将会被批准,流程就能保证活性。此时的paxos算法在本质上就退变为两阶段提交协议。但在异常情况下,系统可能会出现多Leader的情况,但这并不会破坏算法对一致性的保证,此时多个Leader都可以提出自己的提案,优化的算法就退化成了原始的paxos算法。
原书本章内容到此结束,补充下优化后的相关知识。
**********************************************************************
一个Leader的工作流程主要有分为三个阶段:
(1).学习阶段 向其它的参与者学习自己不知道的数据(决议);
(2).同步阶段 让绝大多数参与者保持数据(决议)的一致性;
(3).服务阶段 为客户端服务,提议案;
paxos算法理论上学习到此结束了,实际应用结合网上 的例子“ 使用Basic-Paxos协议的日志同步与恢复”去学习。更多推荐
所有评论(0)