从PhxPaxos中再看Paxos协议

超、凢脫俗 2022-07-14 00:10 225阅读 0赞

**从PhxPaxos中再看Paxos协议**

本文就是通过Phxpaxos中所附带的简单例子，摸索了解Phxpaxos中对Paxos算法的实现，算是验证一下前面对Paxos算法的学习吧。当然之前也说过，Phxpaxos同Lamport老爷爷的原版Multi-Paxos相比已经修改了很多，毕竟老爷爷的文章比较的偏理论化，所以理论上不修改的Multi-Paxos是不可能满足线上分布式系统的可用性和可靠性需求的，具体对于遇到的修改再行另表吧。

# 一、预备操作 #

默认情况下Phxpaxos的存储模块使用的是glog，但不知道怎么回事，在我MacOS下VMware Fusion虚拟机Ubuntu-1604的环境下，严格按照[《编译安装手册》][Link 1]还是会报无法创建log文件的错误，不知道是不是因为目录使用NFS挂载的原因，此处也不详究了。其实Phxpaxos的实现中，很多地方都有详细的且分好等级的日志信息，查看代码发现只要设置了pLogFunc函数指针，就可以在所有log记录之前执行这个hook函数，于是乎可以在sample中设置这个option，那么整个系统的运行路径和运行状态也就一览无余了。

<table style="margin:0px; padding:0px; border:none; outline:0px; font-style:inherit; font-family:inherit; font-size:16px; vertical-align:middle; border-collapse:collapse; border-spacing:0px; width:auto; max-width:65em; empty-cells:show"> 
 <tbody style="margin:0px; padding:0px; border:0px; outline:0px; font-style:inherit; font-family:inherit; vertical-align:baseline"> 
  <tr style="margin:0px; padding:0px; border:0px; outline:0px; font-style:inherit; font-family:inherit; vertical-align:baseline; height:35px"> 
   <td style="margin:0px; padding:0px; border:none; outline:0px; font-style:inherit; font-family:inherit; font-size:16px; vertical-align:middle; height:35px; white-space:nowrap"> <pre style="margin-top:0px; margin-bottom:0px; padding:0px 1em 0px 0px; border:none; outline:0px; font-style:inherit; font-family:Menlo,Consolas,&quot;Source Code Pro&quot;,Inconsolata,Monaco,monospace,&quot;Microsoft YaHei&quot;,&quot;Hiragino Sans GB&quot;,&quot;WenQuanYi Micro Hei&quot;; font-size:0.85rem; vertical-align:baseline; background:none; overflow:auto; color:rgb(211,211,211); line-height:1.3rem; text-align:right">
       
        
     <div style="margin:0px; padding:0px; border:0px; outline:0px; font-style:inherit; font-family:inherit; font-size:13.6px; vertical-align:baseline; line-height:1.3rem">
      
         
        1
       
        
     </div>
       
        
     <div style="margin:0px; padding:0px; border:0px; outline:0px; font-style:inherit; font-family:inherit; font-size:13.6px; vertical-align:baseline; line-height:1.3rem">
      
         
        2
       
        
     </div>
       
        
     <div style="margin:0px; padding:0px; border:0px; outline:0px; font-style:inherit; font-family:inherit; font-size:13.6px; vertical-align:baseline; line-height:1.3rem">
      
         
        3
       
        
     </div>
       
        
     <div style="margin:0px; padding:0px; border:0px; outline:0px; font-style:inherit; font-family:inherit; font-size:13.6px; vertical-align:baseline; line-height:1.3rem">
      
         
        4
       
        
     </div>
       
        
     <div style="margin:0px; padding:0px; border:0px; outline:0px; font-style:inherit; font-family:inherit; font-size:13.6px; vertical-align:baseline; line-height:1.3rem">
      
         
        5
       
        
     </div>
       
        
     <div style="margin:0px; padding:0px; border:0px; outline:0px; font-style:inherit; font-family:inherit; font-size:13.6px; vertical-align:baseline; line-height:1.3rem">
      
         
        6
       
        
     </div>
       
        
     <div style="margin:0px; padding:0px; border:0px; outline:0px; font-style:inherit; font-family:inherit; font-size:13.6px; vertical-align:baseline; line-height:1.3rem">
      
         
        7
       
        
     </div></pre> </td> 
   <td style="margin:0px; padding:0px; border:none; outline:0px; font-style:inherit; font-family:inherit; font-size:16px; vertical-align:middle; height:35px"> <pre style="margin-top:0px; margin-bottom:0px; padding:0px; border:none; outline:0px; font-style:inherit; font-family:Menlo,Consolas,&quot;Source Code Pro&quot;,Inconsolata,Monaco,monospace,&quot;Microsoft YaHei&quot;,&quot;Hiragino Sans GB&quot;,&quot;WenQuanYi Micro Hei&quot;; font-size:1em; vertical-align:baseline; background:none; overflow:auto; color:rgb(77,77,76); line-height:1.3rem">
       
        
     <div style="margin:0px; padding:0px; border:0px; outline:0px; font-style:inherit; font-family:inherit; vertical-align:baseline; line-height:1.3rem">
        
         
      <span style="margin:0px; padding:0px; border:0px; outline:0px; font-style:inherit; font-family:inherit; vertical-align:baseline">#<span style="margin:0px; padding:0px; border:0px; outline:0px; font-style:inherit; font-family:inherit; vertical-align:baseline">include</span> <span style="margin:0px; padding:0px; border:0px; outline:0px; font-style:inherit; font-family:inherit; vertical-align:baseline">&lt;stdarg.h&gt;</span></span>
       
        
     </div>
       
        
     <div style="margin:0px; padding:0px; border:0px; outline:0px; font-style:inherit; font-family:inherit; vertical-align:baseline; line-height:1.3rem">
        
         
      <span style="margin:0px; padding:0px; border:0px; outline:0px; font-style:inherit; font-family:inherit; vertical-align:baseline; color:rgb(66,113,174)"><span style="margin:0px; padding:0px; border:0px; outline:0px; font-style:inherit; font-family:inherit; vertical-align:baseline; color:rgb(137,89,168)">void</span> <span style="margin:0px; padding:0px; border:0px; outline:0px; font-style:inherit; font-family:inherit; vertical-align:baseline; color:rgb(142,144,140)">custLog</span><span style="margin:0px; padding:0px; border:0px; outline:0px; font-style:inherit; font-family:inherit; vertical-align:baseline; color:rgb(245,135,31)">(<span style="margin:0px; padding:0px; border:0px; outline:0px; font-style:inherit; font-family:inherit; vertical-align:baseline; color:rgb(137,89,168)">const</span> <span style="margin:0px; padding:0px; border:0px; outline:0px; font-style:inherit; font-family:inherit; vertical-align:baseline; color:rgb(137,89,168)">int</span> iLogLevel, <span style="margin:0px; padding:0px; border:0px; outline:0px; font-style:inherit; font-family:inherit; vertical-align:baseline; color:rgb(137,89,168)">const</span> <span style="margin:0px; padding:0px; border:0px; outline:0px; font-style:inherit; font-family:inherit; vertical-align:baseline; color:rgb(137,89,168)">char</span> * pcFormat, va_list args)</span> </span>{
       
        
     </div>
       
        
     <div style="margin:0px; padding:0px; border:0px; outline:0px; font-style:inherit; font-family:inherit; vertical-align:baseline; line-height:1.3rem">    
        
         
      <span style="margin:0px; padding:0px; border:0px; outline:0px; font-style:inherit; font-family:inherit; vertical-align:baseline; color:rgb(137,89,168)">char</span> sBuf[
        
         
      <span style="margin:0px; padding:0px; border:0px; outline:0px; font-style:inherit; font-family:inherit; vertical-align:baseline; color:rgb(245,135,31)">1024</span>] = {
        
         
      <span style="margin:0px; padding:0px; border:0px; outline:0px; font-style:inherit; font-family:inherit; vertical-align:baseline; color:rgb(245,135,31)">0</span>};
       
        
     </div>
       
        
     <div style="margin:0px; padding:0px; border:0px; outline:0px; font-style:inherit; font-family:inherit; vertical-align:baseline; line-height:1.3rem">
      
         
            vsnprintf(sBuf, 
        
         
      <span style="margin:0px; padding:0px; border:0px; outline:0px; font-style:inherit; font-family:inherit; vertical-align:baseline; color:rgb(137,89,168)">sizeof</span>(sBuf), pcFormat, args);
       
        
     </div>
       
        
     <div style="margin:0px; padding:0px; border:0px; outline:0px; font-style:inherit; font-family:inherit; vertical-align:baseline; line-height:1.3rem">    
        
         
      <span style="margin:0px; padding:0px; border:0px; outline:0px; font-style:inherit; font-family:inherit; vertical-align:baseline; color:rgb(245,135,31)">std</span>::
        
         
      <span style="margin:0px; padding:0px; border:0px; outline:0px; font-style:inherit; font-family:inherit; vertical-align:baseline; color:rgb(245,135,31)">cerr</span> &lt;&lt; sBuf &lt;&lt; 
        
         
      <span style="margin:0px; padding:0px; border:0px; outline:0px; font-style:inherit; font-family:inherit; vertical-align:baseline; color:rgb(245,135,31)">std</span>::
        
         
      <span style="margin:0px; padding:0px; border:0px; outline:0px; font-style:inherit; font-family:inherit; vertical-align:baseline; color:rgb(245,135,31)">endl</span>;
       
        
     </div>
       
        
     <div style="margin:0px; padding:0px; border:0px; outline:0px; font-style:inherit; font-family:inherit; vertical-align:baseline; line-height:1.3rem">
      
         
        }
       
        
     </div>
       
        
     <div style="margin:0px; padding:0px; border:0px; outline:0px; font-style:inherit; font-family:inherit; vertical-align:baseline; line-height:1.3rem">
      
         
        oOptions.pLogFunc = custLog;
       
        
     </div></pre> </td> 
  </tr> 
 </tbody> 
</table>

Phxpaxos的代码虽然是多，但是当除掉存储模块、网络模块、CheckPoint模块、Benchmark和单元测试等部分代码后，核心代码其实也是十分有限的，而且和Paxos算法相关的部分都单独放在algorithm目录中了，查看这个文件夹中的文件名，赫然醒目的acceptor、proposer、learner、instance，就让我们估计道知道他们是什么角色履行的职责了。

# 二、附带phxelection选主例程解析 #

Phxpaxos附带的两个sample详细构建过程都在[《README》][README]中描述清楚了，本来是想phxelection和phxecho两个例子都一起跟踪的，但是后面看着看着发现，phxelection流程走完基本就定型了，phxecho和前者的差异主要就是传递了自定义的StateMachine，所以在Paxos算法Chosen Value之后，会额外的执行客户提供的状态机转移函数Execute()，这其实和phxelection在原理上没有本质的差异，因为后者算是对于选主的特殊情况，预先定义了MasterStateMachine状态机而已。

### 2.1 Phxpaxos中的Master Node ###

在Phxpaxos的设计中弱化了Multi-Paxos中提到的Leader角色，而是使用了Master的概念，在后面PhxSQL项目的文档中也强调了：Master是唯一具有外部写权限的Node，所以可以保证这个Node的数据肯定是最新的副本，Client的所有写请求和强一致性的读请求都需要直接或者由其他Node代理转发到这个Master Node上面，而对数据一致性要求不高的普通读请求，其读请求才可以在非Master Node上面执行。  
　　由此可见，在稳定的情况下Master Node起到了单点协调者的作用。但是当系统新启动，或者在Master Node挂掉的时候，就需要有一个选主的操作。[《Paxos理论介绍(3): Master选举》][Paxos_3_ Master]已经将选主的原理详细说明了。概而言之，就是在没有Master的时候，大家都可以认为自己是Master并发出TryBeMaster请求，这就等于大家实现一个Basic-Paxos的流程，根据Paxos的算法原理可以保证，最后只有唯一一个节点的提案被Chosen，这时候被Chosen提案的Proposer就被选为Master Node。在系统运行的过程中，各个节点会事先约定一个租赁周期，在这个周期到达之前Master Node可以提起续约的请求，其他节点当发现约定的检查周期到达之后并且Master租赁有效期间之前还能够请求到Master Node，就表示Master Node续约成功，此时就不再发起TryBeMaster的请求。这样在稳定的情况下Master Node可以一直稳定的运行下去，而当Master Node异常或者普通Node和Master Node通信失常情况下的处理方式，会在后文中作进一步的解释。

### 2.2 phxelection选主的实现流程 ###

Phxpaxos中的两个项目默认是使用的三个节点来实验的，根据Paxos中Majority的需求，其节点数至少是三个，而且尽可能的是奇数数目。每一个运行的进程对外被抽象成Node节点，在内部使用带序列号的Instance作为执行单元，且每个Instance内部都含有完整的Acceptor、Proposer、Leader的角色，而且同一个Instance中的三个角色是存在于同一个进程中的，相互之间的结果是立即可见的。

### 2.2.1 Node初始化操作 ###

Phxelection历程启动很简单，当代码创建PhxElection对象oElection后，直接调用其成员函数PhxElection::RunPaxos()启动。在这个成员函数中，可以设置相关参数oOptions(注意这个选项很大，而且后续会深入透传到整个Phxpaxos内部)，这个sample中，最主要的是要打开选主开关bIsUseMaster，然后调用Node::RunNode()，也只在这个函数中才进行PNode实体的创建和初始化工作，并将得到对象的地址保存返回给poNode指针，这样用户程序也可以操作Node(而非PNode)规定的其他可用接口来访问或操作底层对象了。  
　　PNode对象的创建采用典型的两段式构造，当然下面很多对象都是两段式构造，主要工作在PNode::Init()中实现，这个初始化涉及的内容比较的多，几乎贯穿了整个系统的启动过程：  
　　(1). InitLogStorage: 好像底层是基于啥LevelDB搞的吧，先不管它了；  
　　(2). InitNetWork: 默认的网络配置是根据命令行参数解析到的节点网络信息IP:Port，对于UDP协议创建接收套接字和一个发送套接字，对于TCP则是通常的bind-listen服务端初始化。TCP类型的初始化工作，还包括使用epoll\_create创建异步事件侦听，同时创建封装了pipe匿名管道的Notify对象用于对接收到的消息进行传递，并设置管道NONBLOCK且将管道的读端添加EPOLLIN事件侦听；设置成员变量poNetWork；  
　　(3). MasterList: 由于我们只用到一个Group，所以只创建一个MasterDamon对象，可见默认的Master Lease是10s，可以通过SetLeaseTime自由自定义设置这个租赁周期但是必须大于1s；同时还要创建一个MasterStateMachine对象，首先尝试从之前保存的数据加载历史信息，如果读取失败进行默认初始化，同时设置version的值为(uint64\_t)-1；  
　　(4). Group: 和上面一样也只有一个，主要把上面已经初始化的信息保存到这个容器里面；这个里面，让我们最感兴趣的是创建了一个Instance类型的m\_oInstance对象，大概看了一下Instance类的声明就让人感到十分兴奋，因为大部分的消息回调OnRecieveXXX都在这个类的声明里面，同时还包含了Acceptor、Proposer、Learner成员，表明我们离Paxos已经是很接近了；  
　　(5). ProposeBatch: 批量提交，算是Phxpaxos相比Multi-Paxos的一个新操作，待到我后面研究到这个深度的时候再深入；  
　　(6). InitStateMachine: 参数只有一个——Options，一个超大巨形体参数，但是在这个sample中我们并没有创建StateMachine，所以这里的AddStateMachine啥也没做，当然对于另外一个Phxecho需要使用用户定义的StateMachine，此处就会进行添加；然后当我们开启了选主的功能后，各个Node都会启动运行RunMaster()，这个操作会创建一个线程运行MasterDamon::run()，这个线程就是Master Node选取和维护的主要实现部分，此处跳过，后面会单独展开详述；  
　　(7). Group Init: 将启动时候添加的所有Node列表信息添加到SystemVSM中，同时添加GetSystemVSM()、GetMasterSM()两个StateMachine。其实看到这里，让人感觉到StateMachine实际等价于某个带状态的函数，当所谓的StateMachine发生转移的时候，实际就是其对应的函数被执行。然后执行Instance::Init()，由于Instance的初始化有较多操作，且是跟Paxos密切相关的，下面单独展开介绍。

### 2.2.2 Instance初始化操作 ###

在Instance初始化的过程中，主要是对Paxos中的几个角色的初始化，其角色大多都是继承自Thread类，所以意味着各自以线程的方式独立运行。我们主要关心的角色有：  
　　(1). Learner  
　　最终映射成LearnerSender::run()线程，做的事情就是：等待条件变量m\_bIsComfirmed被设置，然后调用SendLearnedValue(m\_llBeginInstanceID, m\_iSendToNodeID);从llBeginInstanceID开始一直发送到当前的m\_llInstanceID。对在每一个instance发送的过程中，都需要从log中查取这个instance的相关信息(比如提案节点、提案号、Chosen Value等)后打包发送，具体的信息请参看Learner::SendLearnValue()中的打包过程，然后可以选择之前在Node初始化中网络部分的TCP还是UDP方式发送，具体任务交由网络模块负责了。  
　　Learner会等待记录ACK信息，当前被确认的ID保存在m\_llAckInstanceID变量中，确认超时后错误返回，错误时候记录当前已经发送的llSendInstanceID变量不被更新。  
　　(2). Acceptor  
　　初始化较为的简单，因为我们没有历史记录，所以加载数据发现为空，就将m\_llInstanceID设置为0就可以了；  
　　(3). CheckpointMgr  
　　这个暂时也不展开说了。作为一个状态机如果要重新加载状态，最直观的就是从最开始零状态一直进行历史记录回放，但是这种方式效率低，而且随着状态机的运行记录所有的历史信息也是不现实的，所以为了增加效能实现的CheckPoint功能就是将历史记录某个时间点的状态做完整快照，加载状态可以从那个CheckPoint开始重放到当前日志记录的状态(这个过程叫做CatchUp)，具体的信息可以查看[《状态机Checkpoint详解》][Checkpoint]。  
　　本sample都是从头开始的，这些东西基本都是0状态的。  
　　(4). IOLoop  
　　这也是开辟一个线程，主要是在一个消息队列m\_oMessageQueue中不断的完成取出消息和处理消息(主要就是通过一个带互斥锁、条件变量封装的std::deque，腾讯说好的无锁队列呢？)的工作，正常情况下会取出消息，然后发配到OnReceive(\*psMessage)处理，而OnReceive的处理流程会对数据包拆包检查，然后根据消息类型分别发配给Learner、Acceptor、Proposer对应角色去处理，消息的类型定义在了comm\\commdef.h的enum PaxosMsgType中，看上去Proposer和Acceptor比较明确，而Learner处理的消息比较多啊。  
　　通过把这个OnReceive的处理大概逛了一下，基本就是标准的Paxos协议的内容了，比如Proposer接收到Acceptor的表决信息后，会先调用m\_oMsgCounter.AddReceive()，然后检查m\_oMsgCounter.IsPassedOnThisRound()看看是不是已经满足超过半数决议了，如果是就进行接下来的例程Accept()或者向Learner广播消息ProposerSendSuccess()，而如果投票失败(否决票过多或者超时)则等待几十毫秒后重新发起Prepare请求。  
　　上面提及的只是消费消息，消息的生产者在哪里呢？之前说道PNode在初始化网络层的时候有过TCP和UDP两种通信方式，TCP通过使用event异步事件，而UDP在一个线程中不断的接收消息，这些渠道接收到的信息，最后都会放到这个队列中去的。  
　　此外Instance还保留了一个m\_oRetryQueue重试队列，用于处理Paxos相关消息，具体什么原理暂时不详。  
　　上面的这些线程的循环，都在m\_bIsEnd=true的时候会退出来，在IOLoop::Stop()会设置这个变量，检索后在Instance对象被析构的时候会调用之。

### 2.2.3 MasterDamon主线程工作 ###

根据上面说到的选主原理，这个线程的工作内容也十分简单，实质的工作内容就是TryBeMaster()：首先在Master Node稳定正常的情况下自身会自动续约，那么在m\_llAbsExpireTime之前就会返回m\_iMasterNodeID和版本号，否则返回nullnode；当Node发现返回nullnode的时候，无论是Master Node的原因还是自己和其通信的原因，都会发起一个包含llMasterVersion信息的Proposer请求，那么：  
　　(1). 系统刚开始的时候，所有的Node都认为自己是Master Node，然后发起Propose()请求，经过Basic-Paxos的正常流程，会最终有一个Node被Chosen，由于大家都在同一个Instance中，被Chosen Value所对应同一进程中的Learner已经知道Chosen Value了(多线程共享变量)，然后就会发送ProposerSendSuccess()广播给所有的Learner，大家接收到之后通过OnProposerSendSuccess()进行学习，并设置m\_bIsLearned=true状态；Learner的后续执行流程检查到这个状态后，就会执行状态机MasterStateMachine状态转移Execute()即LearnMaster()，设置所有节点的m\_iMasterNodeID为被Chosen Value的节点。系统启动Master Node新选取成功时候，m\_llAbsExpireTime的值为0，而后面续约的时候更新为提起Propose时刻+Master租赁时长-100ms长度，自此选主成功。  
　　(2). 所有节点都会在Lease Timer之前发起(但不一定会实质执行)TryBeMaster()，为了减少异常情况下通过Basic-Paxos新选取Master时候可能的“活锁”冲突，大家发起Prepare的时间点会有个微小的elf差异，当发现Master Node在超时时间之前仍然有效的时候，非Master节点都直接返回而不执行BeMaster()，Master节点会发起一个续约的正常Propose请求，最终状态机转移的时候更新时间等信息，然后所有节点学习重新调整即可；  
　　(3). 当Master Node本身挂掉的时候，大家都会发起Propose请求，那么此时就退化成初始状态多个Node采用Basic-Paxos的方法选主的情况了；  
　　(4). 当某个非Master Node因为通信或者其他的原因，错误的发起了BeMaster()的时候，wiki也说了这里是个“乐观锁”的解决方案：这个节点将自己观测到的最大version打包到Propose参数里面去，后续通过正常的Paxos流程会被Chosen，待到最后执行状态转移LearnMaster()的时候，会解包对参数进行校验，发现请求的version版本和当前最新版本不符，那么放弃这次状态机的实质切换操作而直接返回了。我们乐观的预估，此时改节点和系统的通信正常了，在真正的MasterNode下次续约的时候，改节点将会正确学习到Master Node的信息并正常工作。

转载于:  https://taozj.org/2016/11/%E5%88%86%E5%B8%83%E5%BC%8F%E7%B3%BB%E7%BB%9F%E5%85%A5%E9%97%A8%E7%AC%94%E8%AE%B0%EF%BC%88%E4%B8%89%EF%BC%89%EF%BC%9A%E4%BB%8EPhxPaxos%E4%B8%AD%E5%86%8D%E7%9C%8BPaxos%E5%8D%8F%E8%AE%AE/

[Link 1]: https://github.com/tencent-wechat/phxpaxos/wiki/%E4%B8%AD%E6%96%87%E8%AF%A6%E7%BB%86%E7%BC%96%E8%AF%91%E6%89%8B%E5%86%8C
[README]: https://github.com/tencent-wechat/phxpaxos/blob/master/README.zh_CN.md
[Paxos_3_ Master]: https://zhuanlan.zhihu.com/p/21540239
[Checkpoint]: https://github.com/tencent-wechat/phxpaxos/wiki/%E7%8A%B6%E6%80%81%E6%9C%BACheckpoint%E8%AF%A6%E8%A7%A3