Paxos 算法是一种多数派决议,是解决分布式系统中数据一致性最有效的一种算法(Google Chubby的作者Mike Burow 说过这个世界上只有一种一致性算法那就是Paxos,其他的算法都是残次品)
Paxos 中主要有三个角色
Proposer : 提交者(议案提交者) Acceptor:接收者(议案接收者),Learber :学习者
要满足Paxos算法需要满足以下四个前提:
1 如果Acceptor 没有议案必须接收第一个议案
2 每个议案都必须有一个议案编号,并且议案编号只能增长,不能重复,随着时间议案编号会递增
3 如果Acceptor已经接收的议案如果大于新接收的议案那么拒绝。
4 一个Acceptor会接收到提交的议案和批准的议案
Paxos 算法主要分为两阶段:
1 Prepare 阶段(决议提交)
a) Proposer 提出议案,并且将议案编号K,并且把这个议案编号K发给Acceptor
b) Acceptor判断手里有没有议案,如果没有任何议案Acceptor必须接收
c) 如果Acceptor已经有议案,议案编号大于发过来的议案编号拒绝发过来的议案编号。
d) 如果Acceptor已经有议案,议案编号小于新发过来的议案议案编号,Acceptor需要检查之前是否有批准的议案,如果没有则用接受该议案。如果之前有批准的议案,则将批准的议案编号和议案内容回复给Proposer.
Accept 阶段
a) Proposer 收到过半Acceptor发过来的回复时且没有附带任何批准过的议案编号和议案内容,那么Proposer继续提交批准(Accept)请求,这时会将议案编号和议案内容一起提交。
b)Proposer 收到过半Acceptor发过来的回复,且有附带议案编号和议案内容,那么Proposer找到所有回复中超过半数的那个作为提交配准请求发送给Acceptors
c) Proposer 没有收到过半Acceptor发过来的回复,则修改议案编号,并将议案编号重新发给Acceptors
d) Acceptor 收到Proposer发过来的提交请求,如果议案编号小于手里持有的议案编号直接不回应或reject,反之接受新的议案编号和议案内容回复给Proposer
e)经过一段时间Proposer对比接收到的Accept回复,如果超过半数,则结束流程(表示议案已经被批准),通知Learner学习议案.如果未超过半数,则修改议案编号,重新接入Prepare阶段。