paxos分布式一致性协议

Paxos究竟在解决什么问题？

Paxos如何在分布式存储系统中应用？

Paxos算法的核心思想是什么？第一阶段做什么？第二阶段做什么？

Paxos用来确定一个不可变变量的取值，取值可以是一个二进制的数据，有点确定经不能改变，并且可以被获取到（不可变性，可读取性）。

在分布式存储系统中应用Paxos，数据本身可变，采用多副本进行存储（网络延迟，故障都有可能导致副本不一致）。多个副本的更新操作序列【op1，欧派，……，opn】是相同的，不变的（每个副本第一步干什么，第二步干什么都是不变的）。用Paxos一次来确定不可变变量的Opi的取值（即第i个操作是什么）。每确定完Opi之后，让各个数据副本执行Opi，以次类推。Google的Ghubby，Megastor和Spannner都采用了Paxos来对数据副本的 更新序列达成一致。

Paxos如何确定一个不可变变量的取值

设置一个系统，来存储名称为var的变量。系统内部由多个Acceptor组成，负责存储 和管理var变量。外部有多个proposer机器任务并发调用API，向系统提交不同的var取值。var的取值可以是任意二进制数据。系统对外的API库接口：propose（var,V）=><ok,f>or<error>(如果当前请求调用成功，则f=V,否则f就等于其他proposer提交的值)。系统需要确保var的取值满足一致性，如果var的取值没有确定，则var的取值为null。一旦var的取值被确定，则不能被变更。并且可以一直获取这个值。系统需要满足容错特性，可以容忍任意proposer机器出现故障，可以容忍少数Acceptor故障（半数一下）。为了简单理解，暂时不考虑网络分化和Acceptor故障会丢失var的信息。

确定一个不可变变量的难点

管理多个Proposer的并发执行

先考虑由单个Acceptor组成。通过类似互斥锁机制，来管理并发的proposer运行。Proposer首先向acceptor申请acceptor的互斥访问权，然后才能请求Acceptor接收自己的取值。Acceptor给proposer发放互斥访问权，谁申请到互斥访问权，就接收谁提交的取值。一旦Acceptor接收了某个Proposer的取值，则认为var取值被确定，其他Propose不在改变。

确定一个不可变变量取值----方案1

基于互斥访问权的Acceptor的实现

Acceptor保存变量var和一个互斥锁lock。Acceptor：：prepare（）这个函数用来加互斥锁，给予var的互斥访问权，并返回var当前的取值f。Acceptor：：release（）这个函数用来解互斥锁，回收var的互斥访问权。Acceptor：：accept（var,V）如果已经加锁，并且var没有取值，则设置var为V。并且释放锁。

propose（var,V）的两阶段实现

第一阶段：通过Acceptor：：prepare获取互斥访问权和当前var的取值。如果不能，返回<error>(锁被人占用)。

第二阶段：根据当前var的取值f，选择执行。如果f==null，则通过Acceptor：：accept（var,V）提交数据V。如果f！=null，则通过Acceptor：：release（）释放访问权。release函数返回<ok,f>。

确定一个不可变变量取值----方案1续

通过Acceptor互斥访问权让Proposer序列运行，可以简单的实现var取值的一致性。但Proposer在释放访问权之前发生故障，会导致系统陷入死锁。不能容忍任意Proposer机器故障。为了解决这个问题看方案2

确定一个不可变变量取值----方案2

引入抢占式访问权，acceptor可以让某个proposer获取到的访问权失效，不再接收他的访问。之后，可以将访问权发给其他proposer，让其他proposer访问acceptor

Proposer向Acceptor申请访问权时指定编号epoch（越大的epoch越新），获取到访问权之后，才能向acceptor提交取值。

Acceptor采用喜新厌旧的原则。一旦受到更大的新epoch的申请，马上让旧的访问权失效，不在接收他们提交的取值。然后给新的epoch发放访问权，只接收新的epoch提交的取值。

新epoch可以抢占旧epoch，让旧epoch的访问权失效。旧epoch的proposer将无法运行，新epoch的proposer将开始运行。

为了确保一致性，不同的epoch的proposer之间采用的“后者认同前者”的原则。在肯定旧epoch无法生成确定取值时，新的epoch会提交自己的value，不会冲突。一旦就epoch形成确定性取值，新的epoch肯定可以获得此取值，并且会认同此取值，不会破坏。

确定一个不可变变量取值----方案2续

基于 抢占式访问权的Acceptor的实现

Acceptor保持的状态，当前var的取值<acceped_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,如果不相等说明已经有其他proposer已经获取了访问权，所以此次提交就失效了。如果相等，则设置var的取值<accepted_epoch,accepted_value>=<prepared_epoch,v>

Propose(var,V)的两阶段实现

第一阶段：获取epoch轮次的访问权和当前var的取值。（原理）

简单选取当前时间戳为epoch，通过Acceptor：：prepare（epoch），获取epoch轮次访问权和当前var的取值。如果不能获取（说明有相同的或者更大的epoch获取了访问权），返回<error>。（实现）

第二阶段：采用“后者认同前者”的原则执行。在肯定旧epoch无法生成确定性取值时，新的epoch才会提交自己的value，不会冲突。一旦旧epoch行程确定性取值，新的epoch肯定可以获取到此值，并且会认同此值，不会冲突。（原理）

如果var的取值为空，则肯定旧epoch无法生成确定性取值，则通过Acceptor：：accept（var,epoch,V）提交数据V。成功后返回<ok,V>，如果accept失败，返回<error>(被新epoch抢占或者acceptor故障)。如果var取值存在，则此取值肯定是确定性取值，此时认同它不在改变，直接返回<ok,accepted_value>（实现）

确定一个不可变变量取值----方案2续

基于抢占式访问权的核心思想，让Proposer将按照epoch递增的顺序抢占式一次运行，后者认同前者。

可以避免proposer机器故障带来的死锁问题，并且扔可以保证var取值的一致性。

仍需要引入多acceptor，单机模块的Acceptor是故障导致整个系统宕机，无法提供服务。

确定一个不可变变量取值----Paxos

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

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

Propose（var,V）第二阶段：采用“后者认同前者”的原则执行。在肯定旧epoch无法生成确定性取值时，新的epoch会提交自己的值。不会冲突。一旦旧epoch行成确定性取值，新的epoch可定可以获得此取值，并且不会认同此取值，不会破坏。

如果获取的var取值都为空，则旧epoch无法行成确定性取值。此时努力使<epoch,V>成为确定性取值。

1.向epoch对应的所有accecptor提交取值<epoch,V>。

2.如果收到半数以上成功，则返回<ok,V>

3.否则返回<error>（被新epoch抢占或者accecptor故障）

 

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