fast-paxos算法与zookeeper-leader选举源代码分析

fastpaxos算法与Zookeeperleader选举源代码分析雷明[e-mail]1、paxos算法1.1、分布式一致性问题在分布式系统中，有多个节点（服务器），这些节点可以为客户（客户端）提供某种服务。这至少带来两个好处：一方面可以提供性能，另一方面可以提供容错，当部分服务器挂掉之后，不影响整个服务。但是问题又来了：如果多个服务器节点修改同一个变量，后果会怎么样？1.2、paxos算法paxos算法是一个基于消息传递的一致性算法，在1990年由Lamport提出，最近被广泛的应用于分布式计算中。Google的Chubby，Apache的Zookeeper都是基于该理论实现。Paxos被认为是到目前为止唯一正确的分布式一致性算法，其他的算法都是Paxos的改进或者简化。1.3、fastpaxos算法问题提出：在分布式系统中，需要选举出一个leader节点，只有该节点可以做出决策。问题：怎么在n个节点中选择一个作为leader？方法一：指定某一个节点作为leader，问题：这个leader挂了怎么办？方法二：给每个节点指定一个唯一的id，比较所有节点的id，id最大的为leader，问题：怎么知道活着的id中，哪个是最大的？要解决的问题：1、什么时候发起选举？2、选举过程中，后加入的节点怎么办？3、一个节点挂掉后重启，要发起选举，怎么办？选举轮数的新旧：每个节点的数据的新旧（选举结果）有多个节点都活着，在同一轮选举中，选择哪个节点作为leader？2、zookeeper的选举算法2.1、概述Zookeeper集群中，只有一个节点是leader节点，其他节点都是follower节点（实际上还有observer节点，不参与选举的投票，在这里我们先忽略，下同）。所有的更新操作，必须经过leader节点，leader节点和follower节点之间保持着数据同步和心跳。客户端使用zookeeper时，可能会连到follower身份的server上，也可能会连到leader身份的server上。三类角色的分工如下：Leader：处理写请求，单点Follower：处理客户端请求，参与投票Observer：不参与leader选举的投票，只处理客户端请求在一个zookeeper集群里，有多少个server是固定的，每个节点有一个唯一的id，标识它自己，另外，每个server还有用于选举的IP和port，这些都在配置文件中。一个具体的例子如下：server.1=192.168.0.11:2888:3888server.2=192.168.0.12:2888:3888server.2=192.168.0.13:2888:3888这里有3个server，其id分别为1、2、3。2888为节点和leader交换信息的端口，3888为选举的端口。这个节点的id，在投票时，用户标识参加竞选的节点的身份。问题：这个leader节点是怎么确定的？答案：zookeeper系统自己选举出来的，所有的server节点（observer除外），都参与这个选举。这样做的好处是：当现在的leader挂掉了之后，系统可以重新选举一个节点做leader。Zookeeper的选举算法能保证：只要超过半数的节点还活着，就一定能选举出唯一个一个节点作为leader。2.1.1、节点的状态Zookeeper中的节点有以下三种状态（忽略observer节点）：LOOKING：初始化状态，处于选举过程中，leader还没有选出LEADING：leader已经选出，本节点是leaderFOLLOWING：leader已经选出，本节点是follower2.1.2、选举发生的时机当任何一个节点进入looking状态时，选举开始，进入looking状态有如下原因：1、节点刚启动，使自己进入选举状态2、发现leader节点挂掉了Zookeeper中的leader怎么知道follower还活着？follower怎么知道leader还活着？leader会定时向follower发ping消息；follower会定时向leader发ping消息。当发现无法ping通leader时，就会将自己的状态改为LOOKING，并发起新的一轮选举。处于选举模式时，zookeeper的服务不可用。2.1.3、一个节点成为leader的条件一个节点要成为leader，必须得到至少n/2+1（即半数以上节点）的投票，实际上，在实现时，还可以考虑其他规则，比如节点权重。为什么要保证至少n/2+1的节点同意？因为这样能保证本节点得到多数派的支持。因为每一个节点，只能支持一个节点成为leader，因此，只要一个节点获得至少n/2+1的选票，就一定会比其他任何节点得到的选票多。这个规则意味着，如果超过半数以上的节点挂掉，zookeeper是选举不出leader节点的，因此，zookeeper集群最多允许n/2的节点故障。2.1.4、要解决的问题选举算法的目标是确保一定要选出一个唯一的leader节点。这有两层含义：1、一定要选出一个节点作为leader2、这个leader一定要唯一为此，要解决如下问题：1、在一次选举中，节点应该把票投给谁？规则：每个节点有一个唯一的id，在选举中，节点总是把票投给id最大的那个节点，这样，id大的节点更有可能成为leader，天生就是做领导的料。2、在一次选举的过程中，有些节点由于没有启动而没参加（有些人去国外了，没有赶上这次大选，当他回国后，进入looking状态，要发起选举，怎么办？），后来这个节点启动了，此时要求选举，怎么解决？3、运行过程中，leader节点挂掉了，怎么办？此时其他节点会发现leader挂了，会发起新一轮选举，最后选出新的leader。2.1.5、尝试的解决方案1、直接指定一个节点做leader，例如，永远都让id最大节点当leader，这个想法最简单。问题：这个节点挂了怎么办？这会出现单点问题。2、每次选举中，让活着的节点中，id最大的节点当leader。问题：1、其他节点怎么知道活着的节点中，谁的id最的？2.2、源代码分析zookeeper的leader选举源代码在：src\java\main\org\apache\zookeeper\server\quorum目录下。zookeeper实现了3种选举算法，在这里我们只介绍默认的FastLeaderElection算法，其源代码在FastLeaderElection.java中。2.2.1、选举算法的流程选举开始时，每个节点为自己生成一张投票，推荐自己成为leader，并把投票发送给其他节点，这相当于paxos算法中的proposer角色。接下来，节点启动一个接收线程接收其他节点发送过来的投票，并对选票进行处理，这相当于paxos中的acceptor角色。简单的说，节点之间通过这种消息发送（投票），最终选举出leader。当收到其他节点的选票之后，会和自己的投票比较，如果比自己的投票好（比如推荐的leader的id更大，选举轮数更新），则更新自己的选票，接下来把收到的选票放在选票列表里（该列表存储了所有节点的投票，是一个key-value结构，key为节点的id，value为该节点的投票）。并再次把自己的投票发送给其他节点。接下来节点会统计选票列表中每个节点获得的票数，如果有一个节点i获得超过半数的选票，则认为该节点是leader。如果本节点就是i，则将自身的状态置为leading，表明自己是leader；否则将自己的状态置为following，表明自己是follower。通过若干轮的消息交换，最终，会有一个节点获得超过一半的选票而成为leader。这种方法的精髓在于，每个节点在不需要获得所有节点的信息（投票结果）的前提下，达成一致意见，选出leader。2.2.2、主要数据结构NotificationNotification是一个节点从其他节点收到的投票信息，一个节点投票发生变化时会向其他节点发送通知，这分为以下几种情况：1、本节点刚加入到选举过程中2、本节点收到了另外一个节点的消息，这个节点后更大的zxid或者zxid相等但是节点id更大，也就是说，节点更新了自己的投票，变成投这个节点。staticpublicclassNotification{longleader;//发送者推荐的leader的节点idlongzxid;//发送者推荐的leader的zxidlongepoch;//发送者的选举轮数QuorumPeer.ServerStatestate;//发送者的状态InetSocketAddressaddr;//发送者的ip地址}ToSendToSend用于在本节点的投票发生变化时，向其他节点发送消息。staticpublicclassToSend{inttype;longleader;longzxid;longepoch;QuorumPeer.ServerStatestate;longtag;InetSocketAddressaddr;}2.2.3、发送队列和接收队列发送线程用于向其他节点发送本节点的投票信息，接受线程用于从其他节点接受投票信息。LinkedBlockingQueueToSendsendqueue;LinkedBlockingQueueNotificationrecvqueue;第一个队列是发送选票的队列，用于向其他节点发送本节点的选票消息；第二个队列是接收队列，用于接收其他节点发来的选票消息。2.2.4、收票箱HashMapLong,Voterecvset=newHashMapLong,Vote();这个用于存储本节点收到的来自其他节点的选票。HashMapLong,Voteoutofelection=newHashMapLong,Vote();这个用于存储本节点从其他following、leading状态的节点收到的选票，用于对leader进行检查确认。2.2.5、重要的函数totalOrderPredicate函数totalOrderPredicate用于比较两张选票的大小，具体代码如下：protectedbooleantotalOrderPredicate(longnewId,longnewZxid,longnewEpoch,longcurId,longcurZxid,longcurEpoch){if(self.getQuorumVerifier().getWeight(newId)==0){returnfalse;}return((newEpochcurEpoch)||(newEpoch==curEpoch&&newZxidcurZxid)||(newZxid==curZxid&&newIdcurId));}比较的规则为：1、首先比较epoch，即逻辑时钟，这个大的，选票就大。2、接着比较zxid，事务号，这个大的，选票就大。3、最后比较节点的id，id大的，选票就大。updateProposal函数updateProposal更新本地节点的选票，具体代码如下：synchronizedvoidupdateProposal(longleader,longzxid,longepoch){proposedLeader=leader;proposedZxid=zxid;proposedEpoch=epoch;}更新的内容包括：本节点推荐的leader的id，推荐的leader所持有的zxid值，推荐的leader所持有的epoch值。一般的，在更新本节点的选票之后，会调用sendNotifications向其他节点广播本节点的选票。sendNotifications函数sendNotifications用于向其他节点发送自己的投票信息，实际上是把投票放到sendqueue，发送队列中，本节点的选票变化时（收到来自其他节点更好的选票，或者选举初始时），会调用此函数：privatevoidsendNotificatio