paxos算法

一、概述：

确定一个不可变变量的取值：
　　基于互斥访问权的Acceptor的实现：
　　　　1、Acceptor保存变量var和一个互斥锁
　　　　2、Acceptor::prepare()
　　　　　　互斥加锁，给予var的互斥访问权，并返回var当前的取值f
　　　　3、Acceptor::release()
　　　　　　解开互斥锁，收回var的互斥访问权
　　　　4、Acceptor::accept(var, V):
　　　　　　如果已加锁，并且var没有取值，则设置var为V。并且释放锁；

　　propose(var, V)的两阶段实现：
　　　　1、第一阶段，通过Acceptor::prepare获取互斥访问权和当前var的取值；如果不能，返回 <error>(锁被别人占用)
　　　　2、第二阶段，根据当前var的取值f，选择执行：
　　　　　　a、如果f为NULL，则通过Acceptor::accept(var, V)提交数据V，
　　　　　　b、如果f不为空，则通过Acceptor::release()释放访问权，返回<ok, f>
　　通过Acceptor互斥访问权让Proposer序列运行，可以简单的实现var取值的一致性；

不足之处:

　　　Proposer在释放互斥访问权之前发生故障，会导致系统陷入死锁, Proposer在释放互斥访问权之前发生故障，会导致系统陷入死锁。

引入抢占式访问权：
　　　　1、acceptor可以让某个proposer获取到的访问权失效，不在接收它的访问；
　　　　2、之后，可以将访问权发放给其他proposer，让其他的proposer访问acceptor
　　Proposer向acceptor申请访问权时指定编号epoch（越大的epoch越新），获取到访问权之后，才能向acceptor提交取值；

Acceptor采用"喜新厌旧"的方式：
　　一旦接收到更大的epoch的申请，马上让旧的epoch的访问权失效，不再接收他们提交的取值；然后给新epoch发放访问权，只接收新epoch提交的取值；
　　新epoch可以抢占旧epoch，让旧epoch的访问权失效。旧epoch的proposer将无法运行，新epoch的
　　proposer将开始运行。
　　　　为了保持一致性，不能epoch的proposer之间采用"后者认同前者"的原则；在肯定旧epoch无法生成确定性取值时，新的epoch会提交自己的value，不会冲突；一旦旧epoch形成确定性取值，新的epoch肯定会获取到取值，并且会认同此取值，不会破坏；

基于抢占式访问权的Acceptor的实现：
　　Acceptor保存的状态；
　　　　当前var的取值<accepted_epoch, accepted_value>
　　　　最新发放访问权的epoch(latest_prepared_epoch)
　　Acceptor::prepare(epoch):
　　　　只接收比latest_prepared_epoch更大的epoch，并给予访问权，记录latest_prepared_epoch = epoch; 返回当前var的取值；
　　Acceptor::accept(var, prepared_epoch, V):
　　　　验证latest_prepared_epoch == prepared_epoch，
　　　　　　如果latest_prepared_epoch大于prepared_epoch的话，说明该访问权失效了；
　　　　　　设置var的取值<accepted_epoch, accepted_value> = <prepared_epoch, v>

　　propose(var, V)的两个阶段：
　　　　第一阶段：获取epoch轮次的访问权和当前var的取值：
　　　　　　a、当前选取当前时间戳为epoch，通过Acceptor::prepare(epoch),获取epoch轮次的访问权和当前var的取值；
　　　　　　b、如果不能获取，返回<error>
　　　　第二阶段：采用"后者认同前者"的原则执行：
　　　　　　如果var的取值为空，则肯定旧epoch无法生成确定性取值，则通过Acceptor::accept(var, epoch, V)，提交数据V，成功后返回<ok, V>
　　　　　　如果accept失败，返回<error> （被新epoch抢占或者acceptor故障）
　　　　　　如果var的取值存在，则此取值肯定为确定性取值，此时认同它不再更改，直接返回<ok, accepted_value>

基于抢占式访问权的核心思想：
　　让proposer将按照epoch递增的顺序抢占式依次运行，后者认同前者；可以避免proposer集群故障带来的死锁问题，并且扔可以保证var取值的一致性；仍需要引入多acceptor:单机模块Acceptor是故障导致整个系统宕机，无法提交服务；

　　Paxos在方案2的基础上引入多Acceptor。
　　　　Acceptor的实现保持不变，仍采用“喜新厌旧”的原则运行；　　
　　　　Paxos采用“少数服从多数"的思路；
　　　　　　一旦某epoch的取值f被半数以上acceptor接受。则认为此var取值被确定为f，不再更改；

　　　　　　Propose(var, V)第一阶段：选定epoch，获取epoch访问权和相应的var取值；
　　　获取半数以上acceptor的访问权和对应的一组var取值；

　　Propose(var, V)第二阶段：采用”后者认同前者“的原则执行：
　　　　如果获取的var取值为空，则旧epoch无法形成确定性取值，此时努力使<epoch, V>成为确定性取值；
　　　　a、向epoch对应的所有acceptor提交取值<epoch, V>
　　　　b、如果收到半数以上成功，则返回<ok, V>
　　　　c、否则，返回<error>(被新epoch抢占或者acceptor故障)

　　如果获取的var取值不为空，认同最大accepted_epoch对应的取值f，努力使<epoch, f>成为确定性取值；
　　如果f出现半数以上，则说明f已经是确定性取值，直接返回<ok, f> 否则，向epoch对应的所有acceptor提交取值<epoch, f>