小记
Google Chubby的作者Mike Burrows说过，there is only one consensus protocol, and that’s “Paxos” – all other approaches are just broken versions of Paxos. 意即世上只有一种一致性算法，那就是Paxos，所有其他一致性算法都是Paxos算法的不完整版。这也是本博客的主题。
Paxos 究竟在解决什么问题
Paxos用来确定一个不可变变量的取值
- 取值可以是任意二进制数据
- 一旦确定将不再更改，并且可以被获取到（不可变性、可读性）
在分布式存储系统中应用Paxos
- 数据本身可变，采用多副本进行存储
- 多个副本的更新操作序列【op1,op2,op3,…..,opn]是相同的、不变的
- 用Paxos依次来确定不可变变量opi的取值（即第i个操作是什么）
- 没确定完opi之后，让各个副本执行opi，依次类推
- Google的Chubby、 Megastore和Spanner都采用了Paxos来对数据副本的更新序列达成一致
Paxos 算法的核心思想是什么
第一阶段在做什么？
第二阶段在做什么？
这是两个很重要的问题，先针对这个问题进行详细阐述
具体实现发展
1.首先是基于互斥访问权的单Acceptor
互斥锁
- 一阶段：获取锁
- 二阶段：var有值f,则释放锁Acceptor:release然后返回<ok,f>,否则会努力使Acceptor:accept<var,v>
2.基于前者提出抢占式访问权
采用发放访问权的策略，接受访问权epoch新的，修改能接受的epoch的新旧底线，也就是拒绝比epoch旧的Proposer的访问权，就是Acceptor采用喜新厌旧的原则。为了保持一致性，不同的epoch的Proposer之间采用后者认同前者的原则（如果旧的epoch无法生成确定性取值时，新的epoch会提交自己的value，不会冲突；如果就的epoch形成确定性取值，新的epoch肯定可以获取此值并且认同此取值，不会破坏）
一阶段：获取epoch轮次访问权和当前var的取值
简单选取当前的时间戳为epoch，通过Acceptor::prepare(epoch)，获取epoch轮次的访问权和当前var的取值
如果不能获取，返回二阶段：采用后者认同前者的原则进行
如果var的取值为空，则肯定旧epoch无法生成确定性取值，则通过Acceptor::accept(var,epoch,V)提交数据V。成功后返回<ok,V>
如果accept失败，返回(被新epoch抢占或者Acceptor故障)
如果var取值存在，则此取值肯定是确定性取值，此时认同它不再更改，直接返回<ok,aaccepted_epoch,aaccepted_value>
3.Paxos 基于方案2 引入多Acceptor
1.Acceptor的实现保持不变，仍然采用“喜新厌旧”的原则运行
2.Paxos采用“少数服从多数”的思路
3.一旦某epoch的取值f被半数以上acceptor接受，则认为此var取值被确实为f，不再更改
一阶段：选定epoch，获取epoch访问权和对应的var取值
获取半数以上acceptor的访问权和对应的一组var取值
二阶段：采用后者认同前者的原则进行
1.在肯定旧epoch无法生成确定性取值时，新的epoch会提交自己的取值，不会冲突。
2.一旦旧epoch形成确定性取值，新的epoch肯定可以获取到此值，并且会认同此取值，不会破坏
如果获取的var取值都为空，则旧epoch无法形成确定性取值。此时努力使<epoch,V>成为确定性取值
- epoch对应的所有acceptor提交取值<epoch,V>
- 如果收到半数以上成功，则返回<ok,V>
- 否则，则返回
(被新epoch抢占或者acceptor故障)
如果var的取值存在，认同最大aaccepted_epoch对应的取值f，努力使<epoch,V>成为确定性取值- 如果f出现半数以上，则说明f已经确定性取值，直接返回<ok,f>
- 否则，向epoch对应的所有acceptor提交取值<epoch,f>
Paxos 解决半数一下故障问题以及会出现的活锁问题
Paxos 可以解决半数以下故障问题，但会引发活锁问题：
旧一轮的epoch总是被新一轮的epoch所抢占
解决办法：
选举Leader/Master节点，然后统一也只能由Leader发送，具体的讲解参考如下链接：https://zhuanlan.zhihu.com/p/20417442,里面提到multi-paxos。