深入理解Basic Paxos协议

Paxos作用

Paxos用来在多个节点间确定并只确定一个不可变变量的取值。(一旦确定后就不可以更改)

基本概念

  • 系统内部由多个Acceptor组成,也就是参与决议的一方,用于存储和管理变量。
  • 系统外部有多个提议者Proposer可以任意并发调用API,向系统提交不同的提议。
  • Proposer发起的每项提议分别用一个ID标识,提议可表示为(ID, value)。
  • ID是一个比较大小的值,比如可以用当前时间戳。
  • 访问权:Paxos的第一阶段要使用新生成的ID去获取访问权,第二阶段使用这个代表访问权的ID以及对应的值去提议。

规定

  • acceptor可以接受(accept)不止一项提议,当多数(quorum) acceptor接受一项提议时该提议被确定(chosen)。(提议是否确定只有proposer知道,也就是通过第一阶段的返回值来了解,acceptor是不知道自己接受的提议确定了没有的)
  • 如果一项值为v的提议被确定,那么后续只确定值为v的提议。(也就是只有ID可以改)
  • 如果一项值为v的提议被确定,那么proposer后续只发起值为v的提议。
  • 对于提议(n,v),acceptor的多数派S中,如果存在acceptor最近一次(即ID值最大)接受的提议的值为v’,那么要求v = v’;否则v可为任意值。(也就是如果acceptor中已经有接受提议的,那选择其中ID最大的提议值作为本次提议的value;如果都没有接受提议,那就按照自己原本的提议)

流程

paxos流程

我们将整个流程分为2个阶段,第一阶段,由proposer使用提议ID向acceptor申请访问权。第二阶段,由proposer使用提议ID和对应的值向acceptor提议。

第一阶段

  1. proposer生成一个新的提议ID(比如可以用当前时间戳),并向所有的acceptor申请访问权,也就是调用prepare(ID)。
  2. acceptor内部保存了maxId(当前颁发的最大的访问权ID),和已经接受的取值(cID,cVal),这3个值都初始化为null(注意maxId和cId不同,cID是当前已经接受的取值cVal对应的ID,由第二阶段修改;而maxId是最大访问权ID,由第一阶段修改)。在acceptor收到提议ID后,有2种情况:
    • maxId为空。也就是这是第一次被申请访问权,那直接保存提议ID到maxId,并返回(ok,null,null)
    • maxId不为空。比较ID和maxId,如果ID>maxId,则更新maxId,并返回(ok,cID,cVal),其中cVal可能有值也可能为null;如果ID<=maxId,返回(error)。
  3. proposer需要获取半数以上访问权,也就是半数返回ok的,进入第二阶段。否则生成新的提议ID,重新执行第一阶段。

第二阶段

  1. proposer向**获取到访问权的**acceptor进行提议,也就是调用propose(ID,v)。这里的ID也就是上一步获取到的访问权ID(由于能够进入第二阶段,说明ID已经被半数以上acceptor所接受),关于v的取值,分3种情况:
    1. 第一阶段acceptor返回的cVal列表中,存在某个非空cVal,出现次数超过半数以上,说明该cVal已经是确定性取值,则直接返回(ok,cVal),不再进行提议。
    2. 如果存在非空cVal,但不存在次数超过半数以上的,则选择maxId最大的一个对应的val,作为v。
    3. 如果都是空的cVal,则用自己原本准备提交的value作为v。
  2. acceptor收到提议后,首先判断ID是否与保存的maxId相等,如果不是,则返回(error);如果是,则更新cID=ID,cVal=v。
  3. proposer如果收到半数以上成功,则返回(ok,v),否则返回(error)(被新ID抢占或者acceptor故障)。

思考

  1. 如何保证已经形成确定性取值后不会被破坏。
    • 如果某个值已经形成确定性取值v,则它在acceptor中超过半数。新的proposer发起提议的时候,在第一阶段获取访问权的时候,如果存活的acceptor超过半数(这是paxos的基本要求,少于半数存活则无法形成确定性取值),则其中必定包含至少一个返回v的acceptor,并且该v对应的id也是存活的acceptor中最大的。此时按照paxos的规则,应该使用这个v作为新的提议进行提交。最终在acceptor中,该确定性取值v的个数只会增加不会减少,所以不会被破坏。
  2. 是否可能出现第二阶段中ID>maxId的情况。
    • 不可能。proposer只向获取到访问权的acceptor发起提议,也就是用于提议的ID肯定在acceptor中申请过,所以会ID<=maxId。

存在的问题

就是活锁了。

活锁:当多个相互协作的线程都对彼此进行响应从而修改各自的状态,并使得任何一个线程都无法继续执行时,就发生了活锁。

活锁这个词听起来不好理解,其实就是相对走来的2个人,你为了避开对面的人,走到左边了,他为了避开你,也换个位置走到左边了,这样两个人在左边又是面对面。为了避开,2人又换到右边,如此反复。与死锁不同,活锁是有可能自行解开的。

paxos中,存在活锁的情况。当proposer1在第一阶段获取到访问权1时,proposer2接下去执行了第一阶段,获取到访问权2。此时proposer1再执行第二阶段时,访问权由于已经变成2了,所以proposer1的访问权失效,proposer1需要重新执行第一阶段,获取访问权3。这时proposer2执行第二阶段,由于访问权变成3了,执行失败。如此反复,谁也提交不了提议。这就形成了活锁。但可以发现的是,只要时间稍稍错开,没那么刚好,活锁就解开了。

相关文章

相关标签/搜索