本文的内容源至–知行学社V. http://www.tudou.com/programs/view/e8zM8dAL6hM/

Paxos 的理解困境

  • Paxos究竟在解决什么问题？
  • Paxos如何在分布式存储系统中应用？
  • Paxos算法的核心思想是什么 第一阶段在做什么 第二阶段在做什么

Paxos 用来确定一个不可变量的取值

  • 取值可以是任何二进制数据
  • 一旦确定将不再更改，并且可以被获取到(不可变性、可读性)

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

  • 数据本身可变，采用多副本进行存储
  • 多副本的更行操作序列[Op1,Op2,…,Opn]是相同的，不变的
  • 用Paxos依次来确定不可变量Opi的取值（即第i个操作是神什么）
  • 每次确定完Opi之后，让各个数据副本执行Opi，依次类推。

Google的Chubby、Megastore 和Spanner都采用了Paxos来对数据副本的根性序列达成一致

Paxos 希望解决的一直性问题

设计一个系统，来存储名称为var的变量 - 系统内部由多个Acceptor组成，负责存储和管理var变量。 - 外部有多个proposer机器任意并发调用API，想系统提交不同的var取值，var的取值可以是任意二进制数据 - 系统对外的API库接口为：propose(var,V)=> <ok,f> or <error>

系统需要保证var的取值满足一致性

  • 如果var的取值没有确定，则var的取值为null
  • 一旦var的取值被确定，则不可以被更改。并且可以一直获取到这个值

系统需要满足容错特性

  • 可以容忍任意propose机器出现故障
  • 可以容忍少数Accptor故障（半数一下）

暂时不考虑 网络分化 和 acceptor故障丢去var的信息。

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

  • 管理多个Proposer的并发执行
  • 保证var变量的不可变性
  • 容忍任意Proposer机器故障
  • 容忍半数以下Acceptor机器故障

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

  • 先考虑系统由单个Acceptor组成。通过类似互斥锁机制，来管理并发的proposer运行。
  • Proposer首先向Acceptor申请Acceptor的互斥访问权，然后才能请求Acceptor接受自己的取值。
  • Acceptor给Proposer发放互斥访问权，谁申请到互斥访问权，就接收到谁提交的取值。
  • 让Proposer按照获取互斥访问权的顺序依次访问Acceptor
  • 一旦Acceptor接受了某个Proposer的取值，则认为var取值被确定，其他Proposer不再更改

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

  • Acceptor保存变量var和一个互斥锁lock
  • Acceptor::pareprare(): 加互斥锁，给予var的互斥访问权，并返回var当前的取值f
  • Acceptor::release(): 解互斥锁，收回var的互斥访问权
  • Acceptor::accept(var,V): 如果已经加锁，并且var没有取值，则设置var为V。并且释放锁

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

  • 第一阶段：通过Acceptor::prepare获取互斥访问权和当前var的取值，如果不能返回（锁被别人占用）
  • 第二阶段：根据当前var的取值f，选择执行 如果f为null，则通过Acceptor::accept（var,V）提交数据V 如果f不为空，则通过Acceptor::release()释放访问权，返回

通过Acceptor互斥访问权让Proposer序列运行，可以简单的实现var取值的一致性

Proposer在释放互斥访问权之前发生故障，会导致系统陷入死锁,所以方案一不能容忍任意Proposer机器故障

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

引入抢占式访问权 - Acceptor可以让某个Proposer获取到的访问权失败，不再接收它的访问，之后，可以将访问权发给其他Proposer，让其他Proposer访问Acceptor - Proposer向Acceptor申请访问权时指定编号epoch（越大的epoch越新），获取到访问权之后，才能向Acceptor提交取值。 - Acceptor采用喜新还旧的原则 一旦收到更大的新epoch的申请，马上让旧epoch的访问权失败，不再接受他们提交的取值。 然后给新epoch发放访问权，只接收新epoch提交的取值 - 新epoch可以抢占旧epoch，让旧epoch的访问权失败，旧epoch的Proposer将无法运行，新epoch的Proposer将开始运行 - 为了保持一致性，不同epoch的Proposer之间采用“后者认同前者”的原则 1、在肯定旧epoch无法生成确定性取值时，新的epoch会提交自己的value，不会冲突 2、旦旧epoch形成确定性取值，新的epoch可定可以获取到此值，并且会认同此取值，不会破坏

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

  • Acceptor保存的状态 当前var的取值<accepted_epoch, accepted_value> 最新发放访问权的epoch(lasted_prepared_epoch)
  • Acceptor::preprare(epoch): 只接收比lasted_prepared_epoch更大的epoch，并给予访问权，记录lasted_prepares_epoch=epoch
  • Acceptor::accept(var ,prepared_epoch, V ): 验证lasted_prepared_epoch == prepared_epoch ,并设置var的取值<accepted_epoch,accepted_value> = <prepared_epoch,v>.

Proposer(var , V)的两个阶段实现

  • 第一阶段：获取epoch 轮次的访问权和当前var的取值 简单选取当前世界戳为epoch，通Acceptor::prepare(epoch)，获取epoch轮次的访问权和当前var的取值如果不能获取，返回<error>
  • 第二阶段：采用“后者认同前者”的原则选定取值，进行提交。 1、如果var的取值为空，则可定当前没有确定性取值，则通过Acceptor::accept(var, epoch , V)提交数据V，成功后返回<ok,V>;如果Acceptor失败，返回<error>(被epoch抢占或者Acceptor故障) 2.如果var取值存在，则此值肯定是确定性取值，此时认同它不再更改，直接返回<ok, epoch_old , accepted_value>

总结

基于抢占式访问权的核心思想： 让Proposer将按照epoch递增的顺讯抢占式的依次运行，后者认同前者。可以避免proposer机器故障带来的死锁问题，并且可以var取值的一致性。但是还得引入多Acceptor单机模块Acceptor是故障导致整个系统down机 ，无法提供服务

  • 关于方案1 如何控制proposer的并发运行？ 让Propose按照epoch递增的顺序抢占式的依次运行，后者会认同前者.(*注*：即使这样做了其实也不能够确保，因为在分布式中，获取的时钟值可能是一样的，如果真出现这种情况，Acceptor应该收回发出去的锁，让Propose重新发起申请，知道时钟是时钟是不一样的;还有就是抢占会发生洪水式的抢占失败，因为前者被后者抢占了，如果后者还没有执行第二阶段，那么前者也有重新抢占的可能，这样反复抢占（简称活锁），那就坑爹了)

为何可以保证一致性？ var值只能被改动一次

为什么会有死锁问题？ 如果获取到的锁的Propose还有执行第二阶段，然后down机了，那么就会出现死锁的情况，但是如果使用抢占式的话还是可以避免到死锁的问题(如果让锁具有时效性，这样也是避免死锁的一种方案). - 关于方案2 如何解决方案1的死锁问题？ 在什么情况下，Proposer可以将var的取值确定为自己提供的取值？

确定一个不可变量的取值—方案2序

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

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

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

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

  • Paxos在方案2的基础上引入多Acceptor Acceptor的实现保持不变，仍采用“喜新厌旧”的原则运行。
  • Paxos采用“少数服从多数”的思路

  • 一旦某epoch的取值f被半数acceptor接受，则认为此var取值被确定为f ,不在改变。

  • Propose(var, v)第一阶段：选定某个epoch,获取epoch访问权和对应的var取值 获取半数以上Acceptor的访问权和对应的一组var取值

  • Propose(var,v)第二阶段：采用“后者认同前者”的原则运行 1、肯定旧epoch无法生成稳定性取值时，新的epoch会提交自己的取值，不会冲突。 2、一旦旧epoch形成确定性取值，新的epoch肯定可以获取到此取值，并且会认同取值，不会破坏。 3、如果获取的var取值为空，则旧epoch无法形成确定性取值。此时努力使<epoch, v>成为确定性取值。

    • 向epoch对应的所有acceptor提交取值<epoch, v>.
    • 如果收到半数以上成功, 则返回<ok, v>
    • 否则，则返回<error>(被新epoch抢占或者acceptor故障) 4、如果var的取值存在，认同最大acceptor_epoch对应的取值f,努力使<epoch, f>成为确定性取值。

抢占式访问权机制的运行过程

图一 图二（#1表示P1获取了访问权） 图3(现在是P2抢占获得了访问权，而P1保存着过期的访问权，此时Acceptor里面的lasted_prepared_epoch 比P1的大) 图4（P2成功设置了V2） 图5（P1的访问权已经失效了，所以Acceptor(#1,V1)失败） 图6（P3prepare(#3)成功，但是会返回，因为var已经被设置了，起到了一致性作用，所以不会在更改var的值）

Paxos算法的核心思想

  • 在抢占访问权的基础上引入多Acceptor
  • 保证一个epoch,只有一个propose运行，proposer按照epoch递增的顺序依次执行
  • 新epoch的proposer采用“后者认同前者”的思想运行 1、在肯旧epoch无法生成确定性取值时，新的epoch会提交自己的取值，不会冲突。 2、一旦旧epoch形成确定性取值，新的epoch肯定可以获取到此取值，并且认同此取值，不会破坏
  • paxos算法可以满足容错要求 1、半数一下acceptor出现故障时，存活的acceptor仍然可以生成var的确定性取值。 2、一旦var取值被确定，即使出现半数以下acceptor故障，此取值可以被获取，并且将不再被更改。
  • paxos算法的Liveness问题 新轮次的抢占会让旧轮次停止运行，如果每一轮次在第二阶成功之前都被新一轮抢占，则导致活锁，怎么解决呢？？？

可以参考raft选举的实现，可以使用随机时间戳来避免活锁，就说每个Propse每轮次的间隔时间是在某个时间段里的某个值，根据raft算法的验证，这种方案接近100%解决这种问题（忘记多少了，有兴趣的朋友，可以到raft的官网去查）。