豆博客

Paxos算法

/ 算法 / 位置： Home » 算法 »

介绍

There is only one consensus protocol, and that’s “Paxos” — all other approaches are just broken versions of Paxos

—— Mike Burrows

角色

  1. proposal(提议者),发起提案
  2. acceptor(接受者),决策提案
  3. learner(学习者),当提案被通过,会被学习者学习,学习者不参与提案的发起和抉择

[!IMPORTANT]

一个agent允许扮演多个角色

提案

一次提案通过多轮决策最终决定一个唯一值.

每个提案均会有instance_id,下面用i代替

每个agent均会带有

  • promised_rnd: 已承诺决策ID,下面用prnd代替
  • accepted_rnd: 已接受决策ID,下面用arnd代替
  • accepted_v: 已接受决策值,下面用av代替

传递的rnd不仅会有round_id,还会携带proposal的唯一标识

实现

理想情况

假设现有4个节点(agent),其中A为proposal,BCD为Acceptor

  1. proposal A向BCD发送信息: i=1,rnd=(1,A)
  2. 收到多数派返回结果: i=1,prnd=(1,A),arnd=0,av=nil
  3. A发现prnd和自己的rnd相同,因此开始Phase2,发送: i=1,rnd=(1,A),v="G"
  4. 接收到多数派节点返回信息: i=1,arnd=1,av="G",prnd=1

理想情况下提案结束.

无冲突情况

并发写冲突

  1. X向多数派BC发送: i=1,rnd=(1,X)
  2. X收到多数派返回: i=1,prnd=(1,X),arnd=0,av=nil
  3. Y向多数派CD发送: i=1,rnd=(1,Y)

  4. Y收到多数派返回:

    C: i=1,prnd=(1,X),arnd=0,av=nil

    D: i=1,prnd=(1,Y),arnd=0,av=nil

  5. Y查询多数派返回的prnd != rnd,rnd+1继续发送请求 i=1,rnd=(2,Y) 给BC
  6. Y收到多数派返回: i=1,prnd=(2,Y),arnd=0,av=nil

  7. X此时进行Phase2发送请求: i=1,rnd=(1,X),v="G"

    B节点返回: i=1,prnd=(1,X),arnd=1,av="G" B节点更新成功

    C节点判断prnd!=rnd返回: i=1,prnd=(2,Y),arnd=0,av=nil C节点更新失败

  8. Y进行Phase2发送请求: i=1,rnd=(2,Y),v="J"
  9. Y收到多数派返回: i=1,prnd=(2,Y),arnd=2,av="J"
  10. 此时X重新进行Phase1,由于上面被拒绝,这次rnd增加为3,发送请求: i=1,rnd=(3,X)

  11. X收到多数派返回:

    B: i=1,prnd=(3,X),arnd=1,av="G"

    C: i=1,prnd=(3,X),arnd=2,av="J"

  12. X发现多数派响应中,有两个接受的值,av="G" av="J"因此,这次不能写入自己的值,而是进行修复.

    由于C节点的arnd最新,考虑到paxos算法的约定: 只接收rnd大于自己的请求,如果av="G"已经被多数派确认,那么av="J"一定不会被写入. 所以将av="J"确定为要修复值

  13. X向BC节点进行Phase2请求: i=1,rnd=(3,X),v="J"
  14. X接收到多数派响应: i=1,prnd=(3,X),arnd=3,av="J"

提案结束最终值J被确定

冲突情况p1

冲突情况p2

极端情况--rnd无限提升

  1. X向BC发送i=1,rnd=1
  2. X收到多数派成功返回
  3. Y向CD发送i=1,rnd=1失败(这里没画出来),提升rnd后发送i=1,rnd=2
  4. Y收到多数派成功返回
  5. X向BC发送i=1,rnd=1,v="X",B节点成功,C节点失败
  6. X提升rnd,向BC发送i=1,rnd=3,收到成功响应
  7. Y向CD发送i=1,rnd=2,v="Y",D节点成功,C节点失败
  8. Y提升rnd .....
  9. 无限重试...

rnd无限提升

rnd无限提升2

Muti-Paxos

将多个提案的Phase1合并到一个请求中发送

Fast-Paxos

逻辑

  1. 一步到位直接发送Phase2请求,其中rnd=0,这样可以保证冲突时安全退回,因为classic-paxos的rnd一定>=1
  2. 如果Fast-Paxos冲突,退化到Classic-Paxos处理

为什么增加多数派数量

引用xp大佬的图

fast-paxos

除X,Y外,中间五个节点从左到右命名为ABCDE

  1. X使用rnd=0占用了ABC.因为rnd同为0,Y只占据了DE.
  2. Y退化至classic-paxos.此时CDE的arnd都为0,Y无法判断哪个值被多数派接受,如果选择CDE则最终值为y0,但实际x0为多数派接受.

此时应当修改多数派从n/2+1改为n*(3/4)+1,这样接受X的多数派数量为4个,Y不论如何去选都至少有两个节点av为x0,通过至少两个节点有相同的值Y可以确定被接受的值.

Reference

[]: https://blog.openacid.com/algo/paxos "可靠分布式系统-paxos的直观解释"
[]: https://www.doubao.com/ "豆包"
[]: https://github.com/Trekkiii/paxos_raft_protocol "paxos_raft_protocol"

paxos算法

我来吐槽

*