- 前言
- CAP原理 & BASE理论
- 一致性模型
- 共识算法(Consensus Algorithms)/ 分布式一致性算法
- Paxos
- Basic Paxos
- Multi Paxos
- Raft 算法
- Paxos VS Raft总结
- ZAB 协议 ( Zookeeper Atomic Broadcast)
Consistency(一致性)、 Availability(可用性)、Partition tolerance(分区容错性)
- 要想数据高可用,就得写多份数据
- 写多分数据就会导致数据一致性问题
- 数据一致性问题会引起性能问题
一致性模型没有最好的算法:人们对性能的追求是无休止。不同的共识算法在不同场景下性能会各有优劣
-
弱一致性
-
最终一致性(一段时间达到一致性,存在中间的不一致状态)
-
强一致
解决的问题:让整个集群的节点对某个值的变更达成一致
- 名词解释:
提案值:对值的操作
提案编号:全局唯一且单调递增
提案 = 提案值 + 提案编号 - 3个角色
Proposer 提案者,
Acceptor 接收者、批准者,
Learner 学习者、记录者
Paxos算法中这三个角色是分开的,但是现实工程一个进程可能同时充当多种角色
Basic Paxos与Multi Paxos
Basic Paxos-
核心思想
- 每个节点都能改数据,作为Proposer发起提案
- 由其他节点作为Acceptor 审批提案(只同意 提案编号 是最新的提案),超过半数同意 Prepare和Accepter就最终达成了共识
- 达成一致后,通知其他Learner节点统一
-
缺点
只能单值达成共识。
多值修改 发到多个节点 产生多个Proposer,提案编号相互否定,容易导致活锁
改进了Basic Paxos
- 核心思想
- 用Basic Paxos算法 选举出一个Leader Proposer,后续的议案都由它来发起
- 每个值都单独运行一个Basic Paxos算法实例,多值共识时有多个Basic Paxos算法互不影响
- 缺点
- Multi-Paxos 因为网络问题而脑裂,出现多 Leaders,退化成Basic Paxos
- Multi Paxos每个节点都可以成为leader 并发添加日志,没有顺序性要求,所以日志可能存在空洞现象;
(leader日志不一定是最新最全的,有日志空洞,leader节点会异步的查询其他节点来填补自身日志空洞)
由于Paxos的难于理解,更难以实现。为此,来自Stanford的学者设计了新的分布式协议Raft,Raft的可理解性和落地性更为简单方便
Raft本质上属于Multi Paxos的进一步优化
-
名词解释
任期Term:节点选举成功变为Leader后 有自己的任期Term
TermId:任期id,全局唯一且单调递增
日志:Leader收到请求的命令操作,保存为日志 -
三种状态
Leader:负责 Client 交互 和 log 复制,系统中同一时刻最多存在一个
Follower(Acceptor):被动响应请求,从不主动发起请求
Candidate:由Follower 向Leader转换的中间状态 -
一致性 流程
- 选举一个Leader,仅允许日志最多的节点当选为leader
- 由Leader操作数据,并将操作保存为日志
- Leader把日志同步给Follower
-
Leader选举 流程
- 没有leader时。follower会发起选举,变成candidate竞选leader
- 每个节点有1票,candidate的票投给自己,超过半数票的candidate变成leader
最新、最全日志的节点才能够当选Leader - Leader节点 遇到其他任期Term比自己高的Leader则退回为follower
-
日志限制:
- 只有leader能操作日志
- 日志必须要串行连续添加
- leader只能日志追加日志,不能覆盖日志
- Basic Paxos算法没有leader proposer角色,是一个纯粹的去中心化的分布式算法,
但是它存在若干不足(只能单值共识 & 活锁 & 网络开销大)。 - 所以才有了以leader proposer为核心的Multi Paxos算法(由一个去中心化的算法变为leader-based的算法)。
- Raft算法相当于Multi Paxos的进一步优化,主要通过增加两个限制
- 日志添加次序性
- 选主限制(仅允许日志最多的节点当选为leader)
原子广播协议:保证了发给各副本的消息顺序相同
Zookeeper 把其作为数据一致性的算法。ZAB 是在 Paxos 算法基础上进行扩展而来的
-
三种状态
Looking:系统刚启动时 或者 Leader 崩溃后正处于选举状态
Following:Follower与 Leader处于数据同步状态
Leading:当前集群中有一个 Leader 为主进程 -
核心思想:
- 保证任意时刻只有一个节点是Leader,Leader处理所有事务请求
- 由Leader发起去更新所有副本 Follower,更新时用的是 两段提交协议,只要多数节点 prepare 成功,就通知他们commit。
- 各个follower 要按当初 leader 让他们 prepare 的顺序来 apply 事务



