zookeeper源码学习

上周在同事的唆使下，我抽空把zookeeper的实现研究了下，把分享帖给大家：


1. paxos算法介绍
如何达成一致性是分布式系统上的一个经典问题，而paxos就是用来解决这个问题的。
对于该算法的介绍，可以先读一下此文：
http://zh.wikipedia.org/wiki/Paxos%E7%AE%97%E6%B3%95
说白了，就是针对于一个提案，只要半数以上成员达成一致，那么提案就被通过了。若是有部分成员记性差，忘记了上次的提案，只要仍旧有半数以上的成员还记得，就可以把之前的一致告诉他。

在经典的paxos算法中，有如下几个成员：
1. proposers：提议发起者
2. acceptors：提案处理者
3. learners：提案学习者（只能学习被通过的提案）

提案的处理分成2个阶段：
1. prepare 阶段：
proposer 选择一个提案编号 n 并将 prepare 请求发送给 acceptors 中的一个多数派；
acceptor 收到 prepare 消息后，如果提案的编号大于它已经回复的所有 prepare 消息，则 acceptor 将自己上次接受的提案回复给 proposer，并承诺不再回复小于 n 的提案；
2. 批准阶段：
当一个 proposor 收到了多数 acceptors 对 prepare 的回复后，就进入批准阶段。它要向回复 prepare 请求的 acceptors 发送 accept 请求，包括编号 n 和之前已经accept正在处理中的提案。
在不违背自己向其他 proposer 的承诺的前提下，acceptor 收到 accept 请求后即接受这个请求。
这个过程在任何时候中断都可以保证正确性。例如如果一个 proposer 发现已经有其他 proposers 提出了编号更高的提案，则有必要中断这个过程。因此为了优化，在上述 prepare 过程中，如果一个 acceptor 发现存在一个更高编号的提案，则需要通知 proposer，提醒其中断这次提案。

流程图如下：



2．Zookeeper介绍

Zookeeper是paxos算法的实现，它的默认实现（FastLeaderElection）对经典paxos的2个阶段处理进行了改进，改为了一个阶段。

处理流程图如下：




这里需要对几个角色做下解释：
1. proposer：提案发起者
2. Leader：一致达成之后的领导者，当有人忘记之前提案的时候，可以和它进行同步。
3. Follower:可以发起投票的参与者。
4. Observer：只能接受数据，但不能发起投票。

接下来，我们看下zookeeper的启动流程：


启动流程：
QuorumPeerMain->initializeAndRun
                            |_NIOServerCnxn.Factory
                            |_quorumPeer
                                      |_start
                                          |_zkDb.loadDataBase()
                                          |_cnxnFactory.start()->doIO
                                          |_startLeaderElection->createElectionAlgorithm->listener.start
                                          |_super.start

Zookeeper有2种工作模式，standalone模式和集群模式，当配置的server小于等于1台则为单机模式，这里我们讲的是集群模式。

quorumPeer为集群中每台机器还未确定角色的名称。
启动步骤为：
1. 从本地加载数据。
2. 启动cnxnFactory用于监听客户端和follower的请求。
3. startLeaderElection启动选举算法，默认为FastLeaderElection
4. 启动选举结果监听器，用于达成一致性。
5. quorumPeer线程主循环启动，在选举成功后，进入自己的角色。还未投票前为LOOKING
成功后为：LEADING，OBSERVING，或FOLLOWING

假如为leading，则初始化leader,过程为：
Leader.lead()->LearnerCnxAcceptor->LearnerHandler

LearnerHandler这个线程处理所有Learner（包括Follower和Observer）的交互逻辑。从Learner发来的消息有以下几种：
1.ACK消息。这是Follower对PROPOSAL消息的响应。Leader收到这个消息后，判断对应的PROPOSAL如果有过半的voter通过，则发送commit请求到CommitProcessor线程的CommittedRequest队列，并且发送Commit消息给所有Follower，发送INFORM消息给所有Observer（告诉这个Proposal通过了）。
2. REQUEST消息。这是Follower转发来的写请求，或者同步请求。转交给PrepRequestProcessor线程处理（放入其submittedRequests队列）
3. PING消息。Learner的心跳消息
4. REVALIDATE消息。用来延长session有效时间

另外，LeaderZooKeeperServer也会在lead函数中被初始化，并setupRequestProcessors
这样，所有进入leader的请求都会走流程：
PrepRequestProcessor->ProposalRequestProcessor->CommitProcessor->ToBeAppliedRequestProcessor->FinalRequestProcessor

假如是读请求，那么PrepRequestProcessor会直接响应用户。
假如是写请求，那么PrepRequestProcessor会向Follower发送PROPOSAL请求。
然后，把request放入到CommitProcessor的queuedRequests，当committedRequests中收到LearnerHandler接受到Follower对PROPOSAL消息的响应消息后。则CommitProcessor处理该request,并进入后续流程。

大致过程如上所述，如有疑问，有空一起交流下。

评论

1 楼 leibnitz 2015-03-21  

有几点要请教下;
a.在二阶段里有这样一句:

引用

例如如果一个 proposer 发现已经有其他 proposers 提出了编号更高的提案，则有必要中断这个过程

为什么要打断呢,打断不是造成混乱吗?
b.图1中的response 由learner返回觉得不对,而图2中的才是正确的.
c.2中说是改为一阶段,其实本质是还是2个阶段,只是leader封装了吧.

sincerely