Ceph Paxos相关代码解析

chenkehao

• 
  Leader选举　　Ceph中的leader选举是一个Paxos Lease过程，与BasicPaxos的目的不同。后者用于解决数据一致性问题，而Paxos Lease是为了选举出一个leader承担monmap的同步任务，并负责在该leader离线之后选出新的leader。Ceph集群中只会有一个monitor作为leader，是当前所有monitor中rank值最小的那个。选举过程会产生leader和quorum成员，即所有支持leader当选的monitor。Quorum是Monitor中的多数派，也就是说它的成员数目必须大于N/2+1，N为Monitor节点数目。
  　　
  　　Paxos Lease过程可以简述如下：
  　　Phase1-a：Proproser参与
  
  
  
  • Proproser向各个Acceptor发送Prepare消息；
    
  • 设置定时器Tp，在r时间后超时，超时后需要重发Prepare消息。
    
  　　Phase1-b：Proposer和Acceptor参与
  
  
  
  • Acceptor收到Prepare消息后，需要检查Prepare消息携带的版本号V，如果版本号比自身已接受的要大，则接受此消息，并向Proposer回复Promise消息，承诺不会接受版本号小于V的Prepare消息；
    
  • Proposer收到Promise消息后，统计批准版本V的Acceptor数量，如果超过半数，则认为此版本为当前最新的（可以提交）。
    
  　　Phase2-a：Proposer参与
  
  
  
  • Proposer重设定时器Tp，向各个Acceptor发送AcceptRequest消息；
    
  　　Phase2-b：Proposer、Acceptor和Learner参与
  
  
  
  • Acceptor收到AcceptRequest消息，向Proposer发送Accepted消息；
    
  • Proposer接受Accepted消息，如果发送者数量超过半数，则认为已经成为Leader。随后向Learner要求版本同步；
    
  • Learner收到版本消息后，重启Tp，准备在定时器触发后重新开始选举过程。
    
  　　
  　　Ceph中的Leader选举可以分为三个步骤：
  
  
  
  • Proposer提出提案，发送propose消息给所有的monitor节点；
    
  • monitor节点收到消息后，接受或拒绝propose；
    
  • Proposer接收ack消息，根据数量统计出支持者数量，如果超过半数则向其他节点发送victory消息，赢得选举。
    
  　　epoch值在leader选举中有非常重要的作用：正常情况下各monitor之间的epoch值相等，当monitor离线后，epoch值保存在数据库中。当它重新上线后，自己的epoch值要比其他monitor小。这样acceptor可以根据对方发过来的epoch值判断PN是不是最新的。还有就是如果epoch值为奇数，说明该monitor处于选举状态。选举完成后，epoch变为偶数并同步到所有quorum成员。
  　　Leader选举主要流程请参见下图：
  
  
  
• 
  Recovery阶段　　当发出OP_COLLECT消息之后，Cpeh集群就进入了Recovery阶段，该阶段的目的是保证所有Monitor之间的monmap版本一致，具体包括最后一个批准(Committed)的提案，最后一个没批准的提案，最后一个接受(Acceppted)的提案。对旧Quorum的所有成员来说，最后一个通过的提案应该都是相同的，但对不属于旧Quorum的成员来说，它的最后一个通过的提案是落后的。
  　　下图从Paxos::collect()开始描述了本阶段各网元的主要活动：
  
  
• 
  Lease阶段　　Lease阶段在Leader发出begin消息后开始。经典Paxos算法分为Prepare和Accept两个阶段。在Prepare阶段，Proposer向所有Acceptor发送Prepare消息，内容为<SNp，Vp>；Acceptor接到此消息后，检查自身回复过的prepare请求的最大值SNa：
  
  
  
  • 如果SNa>SNp，则忽略此请求；
    
  • 否则（此时SNp>SNa）检查上次批准过的accept请求<SNx，Vx>，并回复之；
    
  • 
    如果此前并未接受过请求，则直接回复OK。　　Proposer收到若干Acceptor的回复后，可分为以下几种情况处理：
    
  • 回复Acceptor超过半数，且所有回答都是OK，说明本次欲提交的值之前不存在，可以直接通过accept消息提交；
    
  • 回复Acceptor超过半数，但是携带了此前接受过的V，例如<SN2，V2>，<SN3，V3>。此时Proposer应选择其中编号最大的那个，并将accept消息的内容修改为<SNp，V3>（注意编号不变）；
    
  • 回复Acceptor不超过半数，那递增SNp继续发送prepare消息，若干轮之后Proposer总能提交最新的提案。
    
  　　随后Proposer将开始发送Accept消息。Acceptor接受后分为两种情况处理：
  
  
  
  • 检查回复过的prepare请求的最大编号，如果SNa>SNp，则忽略此消息；
    
  • 否则向Proposer和Learner发送Accepted消息。对于Learner，由于Acceptor之间彼此不知道该轮通过的决议是什么，所以倾向于由Proposer向各个Learner发送<SNp， Vp>完成学习过程。
    
  
  　　对于Ceph而言，总体行为与Paxos算法一致。但是略有差异：Prepare阶段的活动已经在Recovery阶段完成。Peon将自己已接受的最大提案号同步给Leader，这与Paxos中的Promise消息携带着Acceptor已接受的最大提案号是一致的。随后Leader和Peon已接受的最大提案号已经相同，则Leader可以保证自己的提案是未被批准过的，且只有自己才有资格预提交，避免了活锁问题。接下来，Ceph的Lease阶段活动就是Paxos过程中Accept阶段的直接映射。