Paxos分布式一致性算法学习心得

Paxos算法学习心得

• 背景感悟
• Paxos 算法学习心得
• • 三种角色定义:
  • 有如下几种主要动作
  • 数据字段描述
  • • Proposer中的字段:
    • Acceptor中的字段:
  • Paxos流程
  • • • 算法流程图
      • 算法描述
• 结束

背景感悟

关于分布式一致性算法之前断断续续看了很长时间,一直没搞懂，最近想把这个问题弄明白，看了一下Paxos 算法，白天上班在公交车上边看边思考，发现效率很低，下班回家，已经深夜，睡不着，索性搜集了几篇文章，想把这个问题给弄明白，感觉晚上的效率还挺好，有所感悟，乘热乎，写一下心得，关于paxos 算法，网上有很多文章，质量有好有坏，但个人感觉这篇文章写的很好，现在贴出来分享一下，后面也写一下自己对于 Paxos 算法的理解，以及自己对于 Paxos 算法的疑问和从看过这篇文章之后得出的解答，下面是我看过的文章的链接，有兴趣的可以看一下:

https://blog.csdn.net/wolf_love666/article/details/92832811

Paxos 算法学习心得

三种角色定义:

三种角色分别是

1. Proposer:

   提出proposal(提案)

2. Acceptor

   决策提案，从众多提案中，根据协议，选出一个提案(更准确的说是accept一个proposal)

3. Learner

   不对提案做出决策，只学习已经被accept的提案

有如下几种主要动作

1. prepare(npNo) 请求:

   由Proposer发出的提案申请,被Acceptor处理，其中npNo(new proposal No 的缩写)是发出propose的一个全局自增性编号，Proposer每次申请一个proposal都要生成一个全局增长的npNo;

2. resp-prepare(pok,respNo,respV) 响应:( WARING: resp-prepare 的名字是我自己取得，在其他文章里你不会看到这个名字，只是方便解释下面算法的过程取得名字)

   由 Acceptor 处理 prepare(npNo) 请求，根据具体情况对 Proposer 的响应,其中 pok 表示是否响应成功，只有在 pok 是 True 的情况下，后面的两个值才有效, respN 可能为prepare(npNo) 中的 npNo 有可能不是，respV 有可能为空，有可能非空;

3. accept(npNo,paV) 请求:

   由 Proposer 向 Acceptor 发出的请求，其中npNo是prepare(npNo)中的npNo, paV(proposal accept value的缩写) 可能是 resp-prepare(respNo,respV) 中的 respV, 有可能是发出 accept(npNo,paV) 请求的 Proposer 想要提议的值；

4. resp-accept(aok)响应:

   由 Acceptor 对 accept(npNo,paV) 请求，根据情况所作出的响应,aok为True表示响应成功；

数据字段描述

数据字段表示Proposer和Acceptor所持有的数据字段，是算法不可缺少的部分

Proposer中的字段:

1. maxRespNo:

   Proposer对于每个prepare(npNo)的响应resp-prepare(pok,respNo,respV),如果其中的pok为成功的话且respNo大于maxRespNo,则将maxRespNo置为respNo;

2. maxRespV:

   Proposer对于每个prepare(npNo)的响应resp-prepare(pok,respNo,respV),如果其中的pok为成功的话且respNo大于maxRespNo,则将maxRespV置为respV;

3. acceptV:

   Proposer的提案被接受的值

Acceptor中的字段:

1. maxRespPrepareNo:

   每个Acceptor在接受prepare(npNo)请求时，如果该prepare(npNo)请求中 npNo 大于maxRespPrepareNo，那么将maxRespPrepareNo设置为该 npNo;

2. maxAcceptNo:

   每个 Acceptor 在接受accept(npNo,paV) 请求时，如果npNo大于maxRespNo,那么maxAcceptNo就设置为 npNo;

3. maxAcceptV:

   每个 Acceptor 在接受accept(npNo,paV) 请求时，如果npNo大于maxRespNo,那么maxAcceptV就设置为 paV;

Paxos流程

算法流程图

算法描述

如上图1所示，Paxos算法分为两个阶段，prepare阶段和accept阶段，

1. prepare阶段:

Proposer生成一个全局性的编号npNo，并发送prepare(npNo) 请求给过半的Accptor,

对于每个Accptor,要做的事情如下：

1).    如果没有响应过任何prepare(npNo)即maxPrepareRespNo为null ，那么它直接返回一个响应resp-prepare(pok=成功,respNo=null,respV=null) ，并且将自己的maxPrepareRespNo置为npNo;
    
    2).    如果有响应过prepare请求即maxPrepareRespNo不为空且如果npNo小于maxPrepareRespNo，则返回相应resp-prepare(pok=失败,respNo=null,respV=null)，或者不响应;
    
    3).    如果有响应过prepare请求即maxPrepareRespNo不为空且如果npNo大于maxPrepareRespNo，则返回一个响应resp-prepare(pok=成功,respNo=maxAcceptNo,respV=maxAcceptV)
           

对于每个Proposer,要做的事情如下:

1).    如果接受的prepare(pok=成功)响应数小于等于Acceptor总数的一半，那么该Proposer需要重新生成一个npNo=全局npNo+1,并重新发prepare请求给过半的Acceptor即重走preapre阶段;
    
    2).    如果接受的prepare(pok=成功)响应数大于Acceptor总数的一半，那么该Proposer就从这些prepare响应resp-prepare(pok,respNo,respV)中找到最大的respNo，并将maxRespNo置为该respNo,同时将maxRespV置为响应的respV，那么这个maxRespV就将作为第二阶段的提案值，如果respNo均为空，那么maxRespV，那么该acceptor自己的提案值作为第二阶段的提案值;
           

1. accept阶段:

Proposer根据prepare阶段决定的提案值 作为accept(npNo,paV)请求中的paV发送给过半的Acceptor(这里的过半Acceptor集合和parepare阶段中的集合可以不相等)，对于每个Acceptor和Proposer要做的事如下:

对于么个Acceptor,要做的事情如下:

1).    如果maxRespPrepareNo大于accept(npNo,paV)中的npNo,则返回resp-accept(aok=失败);
    2).    如果maxRespPrepareNo不大于accept(npNo,paV)中的npNo,则接受该提案，并将maxAcceptNo置为npNo,maxAcceptV置为paV,并返回一个resp-accept(aok=成功);
           

对于每个Proposer,要做的事情如下:

1).    如果接受的accept(aok=成功)响应数小于等于Acceptor总数的一半，那么本次提案失败，重新生成一个npNo=全局npNo+1,并重新走prepare流程；
    2).    如果接受的accept(aok=成功)响应数大于Acceptor总数的一半,那么本次的提案被接受，结束流程；
           

经过上面的流程，最终每个Proposer的acceptV和每个Acceptor的maxAcceptV的值会走向一致；

结束

至此，Paxos算法的描述就结束了，之后就是对于Paxos的疑问了，如下：

1. 为什么上面描述的Paxos算法能解决一致性问题，它的原理是什么，如何证明？
2. 为什么算法中有许多“过半”的描述，它意义在哪里？
3. Paxos算法为什么有两个阶段？
4. Paxos算法的活锁是怎么产生的？

还有其他问题暂时还没想到，今天时间有限，以后补上，也会补上这这些问题的解答！