袋鼠云技术团队 关注
手机版

分布式一致性算法之Paxos原理剖析

  1. 云栖社区>
  2. 袋鼠云技术团队>
  3. 博客>
  4. 正文

分布式一致性算法之Paxos原理剖析

dream2751027 2016-05-17 18:25:09 浏览3621 评论0

摘要: 清楚zk背后leader一致性选举paxos(帕克索斯)原理

概述

Zookeeper集群中,只有一个节点是leader节点,其它节点都是follower节点(实际上还有observer节点,不参与选举投票,在这里我们先忽略,下同)。所有更新操作,必须经过leader节点,leader节点和follower节点之间保持着数据同步和心跳。

30495ac8bfbd0e8a0064cc8b916a6fa0d699d607

客户端使用zookeeper时,可能会连到follower身份的server上,也可能会连到leader身份的server上。

三类角色分工如下:

Leader:处理写请求,单点

Follower:处理客户端请求,参与投票

Observer:不参与leader选举投票,只处理客户端请求

在一个zookeeper集群里,有多少个server是固定的,每个节点有一个唯一id,标识它自己,另外,每个server还有用于选举的IP和port,这些都在配置文件中。一个具体的例子如下:

server.1= server1的IP地址:2888:3888

server.2= server2的IP地址:2888:3888

server.2= server3的IP地址:2888:3888

这里有3server,其id分别为1232888为节点和leader交换信息的端口,3888为选举端口。这个节点的id,在投票时,用户标识参加竞选的节点的身份。

问题:这个leader节点是怎么确定的?

答案:zookeeper系统自己选举出来的,所有server节点(observer除外),都参与这个选举。这样做的好处是:当现在leader挂掉了之后,系统可以重新选举一个节点做leader。

Zookeeper的选举算法能保证:只要超过半数节点还活着,就一定能选举出唯一个一个节点作为leader。

选举发生时机

   当任何一个节点进入looking状态时,选举开始,进入looking状态有如下原因:

   1、节点刚启动,使自己进入选举状态

   2、发现leader节点挂掉了

   Zookeeper中的leader怎么知道follower还活着?follower怎么知道leader还活着?leader会定时向follower发ping消息;follower会定时向leader发ping消息。当发现无法ping通leader时,就会将自己的状态改为LOOKING,并发起新一轮选举。处于选举模式时,zookeeper服务不可用。

一个节点成为leader条件

    一个节点要成为leader,必须得到至少n/2+1(即半数以上节点)投票,实际上,在实现时,还可以考虑其它规则,比如节点权重。

    为什么要保证至少n/2+1的节点同意?因为这样能保证本节点得到多数派的支持。因为每一个节点,只能支持一个节点成为leader,因此,只要一个节点获得至少n/2+1选票,就一定会比其它任何节点得到的选票多。

    这个规则意味着,如果超过半数以上的节点挂掉,zookeeper是选举不出leader节点的,因此,zookeeper集群最多允许n/2节点故障。

要解决的问题

    选举算法目标是确保一定要选出一个唯一的leader节点。这有两层含义:

    1、一定要选出一个节点作为leader

    2、这个leader一定要唯一

    为此,要解决如下问题:

    1、在一次选举中,节点应该把票投给谁?

    规则:每个节点有一个唯一id,在选举中,节点总是把票投给id最大的那个节点,这样,id大的节点更有可能成为leader,天生就是做领导的料。

    2、在一次选举过程中,有些节点由于没有启动而没参加(有些人去国外了,没有赶上这次大选,当他回国后,进入looking状态,要发起选举,怎么办?),后来这个节点启动了,此时要求选举,怎么解决?

    3、运行过程中,leader节点挂掉了,怎么办?

    此时其它节点会发现leader挂了,会发起新一轮选举,最后选出新leader。

尝试解决方案

    1、直接指定一个节点做leader,例如,永远都让id最大节点当leader,这个想法最简单。问题:这个节点挂了怎么办?这会出现单点问题。

    2、每次选举中,让活着节点中,id最大节点当leader。问题:1、其它节点怎么知道活着节点中,谁id最大?

选举算法流程

    选举开始时,每个节点为自己生成一张投票,推荐自己成为leader,并把投票发送给其它节点,这相当于paxos算法中的proposer角色。接下来,节点启动一个接收线程接收其它节点发送过来的投票,并对选票进行处理,这相当于paxos中的acceptor角色。简单说,节点之间通过这种消息发送(投票),最终选举出leader。

    当收到其他它节点的选票之后,会和自己的投票比较,如果比自己的投票好(比如推荐的leader的id更大,选举轮数更新),则更新自己的选票,接下来把收到的选票放在选票列表里(该列表存储了所有节点的投票,是一个key-value结构,key为节点的id,value为该节点的投票)。并再次把自己的投票发送给其它节点。

    接下来节点会统计选票列表中每个节点获得的票数,如果有一个节点获得超过半数的选票,则认为该节点是leader。如果本节点就是,则将自身的状态置为leading,表明自己是leader;否则将自己的状态置为following,表明自己是follower。

    通过若干轮的消息交换,最终,会有一个节点获得超过一半的选票而成为leader。这种方法的精髓在于,每个节点在不需要获得所有节点的信息(投票结果)的前提下,达成一致意见,选出leader。

算法中涉及的重要变量

logicalclock

volatile long logicalclock;

    表示选举轮数,在lookForLeader开始的时候会加1,,另外,在收到其他节点的投票信息时,如果其它节点的electionEpoch比本值大,本值会被赋成electionEpoch。也就是说,每次节点启动时,该值为0?这个值只在节点存活的时候有意义?即节点重启后,该值为0

ProposedLeader

    long proposedLeader;

    该值为本节点推荐的leader的id,初始时为自己,后面会更新,这个值不会从文件中读,也就是说,重启后会自动使用本节点id。getInitId源代码如下:

    public long getId() {

       return myid;

    }

ProposedZxid

    long proposedZxid;

    本节点建议的zxid,在starter函数中,被初始化为-1;在updateProposal函数中,会更新该变量的值。

    updateProposal(getInitId(), getInitLastLoggedZxid(), getPeerEpoch());

        private long getInitLastLoggedZxid(){

        if(self.getLearnerType() == LearnerType.PARTICIPANT)

            return self.getLastLoggedZxid();

        else return Long.MIN_VALUE;

 }

 public long getLastLoggedZxid() {

     if (!zkDb.isInitialized()) {

           loadDataBase();

     }

     return zkDb.getDataTreeLastProcessedZxid();

     }

ProposedEpoch

    long proposedEpoch;

    表示本节点推荐的选举轮数,在updateProposal函数更新选票时,会更新该值。节点启动初始化时候,第一次调用updateProposal,会把proposedEpoch的值赋为getPeerEpoch,而该函数又会调用getCurrentEpoch,getCurrentEpoch的代码如下:

    public long getCurrentEpoch() throws IOException {

             if (currentEpoch == -1) {

                  currentEpoch = readLongFromFile(CURRENT_EPOCH_FILENAME);

             }

             return currentEpoch;

    }

    这表明,该值会从日志文件中读出来。也就是说,节点重启后,会使用上次活着的时候的值。

     为什么有了zxid还需要epochzxid是用来表示数据的新旧,而epoch是用来表示选举的轮数。

运行实例

    假设zookeeper集群中有3个节点,其ID分别为123。整个集群开始运行时,每个节点zxid都为1
  • 节点123启动后,都进入looking状态,开始leader选举。每个节点的proposedLeader即推荐的leader都是自己;logicalclock值都为1;建议的proposedZxid值都为1;建议的proposedEpoch值都为1;投票列表为每个节点投自己的一票(1->1,2->2,3->3)。节点1首先向23发送自己的投票消息:
4678b76427137d3a3a5a95acba1359c1e9848e88

  • 节点2、3收到节点1的投票消息,首先查看1的状态,发现1处于looking状态。接下来,判断1发来的electionEpoch和本地逻辑时钟logicalclock的大小,发现两者相等(都为1)。接着判断leader、zxid、peerEpoch和本地proposedLeader、proposedZxid、proposedEpoch的大小,节点2发现节点1推荐的leader的id比自己小(1<2),节点3也发现节点1推荐的leader的id比自己的小(1<3),因此不用更新自己的投票。接下来,节点2、3把节点1的投票放入自己的投票列表中,这样,节点2收到的投票的列表为:

         1->1

         2->2

         节点3的为:

         1->1

         3->3

     节点2、3再判断此次投票是否可以结束,发现不能结束。如下图所示:

ca5076372c0195bfb7574d99085101479cebd307

  • 节点2向节点13发送自己的投票信息,节点3由于发送线程的故障原因,投票信息一直没有出去:

8f59244a0a92773ff24657e9fea4adc1ac2bd4fa

      在2发出的投票信息中,选择的leader是它自己。

  • 节点13收到节点2的投票消息。节点1比较自己的logcalclock和节点2发来的electionEpoch的大小,二者相等,接下来比较leaderzxidpeerEpoch和本地proposedLeaderproposedZxidproposedEpoch的大小,发现节点2推荐的leaderid2)比自己的proposedLeader1)大,于是更新自己的选票,将proposedLeader改为2。然后,节点12的选票(2->2)放入自己收到的投票箱中,接着判断投票是否可以结束(调用函数termPredicate),由于节点2被超过半数的节点选择(12),因此选举可以结束,由于自己不是leader,节点1将自己的状态改为following
  • 节点3比较自己的logcalclock和节点2发来的electionEpoch的大小,二者相等,接下来比较leaderzxidpeerEpoch和本地proposedLeaderproposedZxidproposedEpoch的大小,发现节点2推荐的leaderid2)比自己的proposedLeader3)小,不用更新自己的选票。然后,节点32的选票(2->2)放入自己收到的投票箱中,接着判断投票是否可以结束(调用函数termPredicate),由于没有节点获得超过半数的选票,因此选举继续。6b080a7834b6d567555dc4b36e00c7e8908b7609
  • 节点1收到节点2的选票,更新选票后,再向节点13发送自己的投票信息:此时,节点1选的leader已经变为2,而且节点1的状态已经变成followingff09a8b387f8f76b502fa3ae293a73e279869d16
  • 节点2在收到节点1的选票信息后,判断节点1的状态,发现为following,这表明,节点1已经认为leader选出来了,并且是2。节点2首先更新自己的收票箱,将1的投票改为2,接着,判断选举是否结束,发现确实可以结束,节点2就更新自己的状态,由于发现自己是被半数以上人推荐的leader,因此把自己的状态改为leading同样,节点3在收到节点1的投票信息后,判断节点1的状态,发现为following,这表明,节点1已经认为leader选出来了,并且是2。节点3首先更新自己的收票箱,将1的投票改为2,接着,判断选举是否结束,发现确实可以结束,节点3就更新自己的状态,由于发现自己不是被半数以上人推荐的leader,因此把自己的状态改为following至此,选举结束,选出来的leader213都为follower7adaeb1876c3604fdd081310a95ea1b9a2077fb9


用云栖社区APP,舒服~

【云栖快讯】新手小白必看!编程语言系列讲座火爆进行中,与行业资深专家一起学习Python、C++、JavaScript、Java!从入门到进阶  详情请点击

网友评论

dream2751027
文章7篇 | 关注2
关注
充分利用阿里云现有资源管理和服务体系,引入中间件成熟的整套分布式计算框架,以应用为中心,帮助... 查看详情
一种稳定、可靠、容量和服务能力可弹性伸缩的分布式关系型数据库服务。 查看详情
快速、完全托管的TB/PB级数据仓库解决方案,向用户提供了完善的数据导入方案以及多种经典的分... 查看详情
为您提供简单高效、处理能力可弹性伸缩的计算服务,帮助您快速构建更稳定、安全的应用,提升运维效... 查看详情
阿里云飞天战略营全新发布

阿里云飞天战略营全新发布