zookeeper 内部工作原理(翻译版本)

 zookeeper 内部工作原理
1、原子广播
zookeeper的核心就是消息处理原子性，能够保持所有的server同步

2、保证，属性和一些定义
zookeeper 能够保证消息处理原子性的特性包括：
1）可靠的消息传递
如果一个消息m， 某个server接收了，那么基本上所有server肯定也都接收到了该消息
2）顺序接收
如果message a 先于message b 被某个server接收，那么所有server接收a 都会先于b。
a 和b 同时传递消息的话，反正要么a在前，要么b在前，就是不会出现并行或混乱冲突的情况。
3）因果关系
如果message a 先于b ，b又先于c，那么a肯定先于c的(这里的关系主要指某个server接收是这个顺序，其他server也肯定是这个顺序)

zookeeper 消息系统必须设计的高效、可靠，实现和维护都很简单。

由于我们需要大量使用消息，所以我们需要zookeeper平均每秒能够处理成千上万的请求

尽管我们使用k+1个正常运行的server收发消息。但是我们还是必须能够恢复比方断电导致所有server停止工作的的情况(相对单个server出问题的情况)

如果我们时间紧迫而且开发人员少，那么我们需要一个容易实现的协议能够快速实现。

最后，zookeeper能够完全满足以上的需求
zookeeper的协议假设我们能够在点对点的server中构造FIFO消息通道。一般相类似的服务总是假设消息会丢失或者消息会重复，我们会假设FIFO通道是可靠的，由于我们使用tcp连接，基于tcp连接的以下特点:
4）顺序消息传递
message m 总是会在所有之前的消息之后传递。由此，如果消息m丢失了，那么m之后的消息也都会丢失
5)FIFO 管道关闭过后，就接收不到消息了
如果FIFO消息管道关闭了，就不可能从该管道中接收消息。
FLP证明一致性不可能实现在分布环境中如果发生了错误。为了在出错的时候实现一致性，我们使用timeout机制来实现。
但是我们使用timeout机制是为了证明server的存活，而不是证明server的正确性。这样，当timeout机制
停止工作(计时发生故障)，消息系统会挂起，但是依然能够保证一致性正常工作
6）数据包
通过FIFO通道发送的一系列字节流
7）提议
一个协议单元，提议通过zookeeper"同意团"(同意该提议的一组server)交换数据包表决通过。大多数提议包含消息。但是有个特别的就是新leader选举协议就是不带消息的。
8）消息
字节流会自动的广播到其他zookeeper server。提议和同意提议在传递的时候都会附带消息的。
就如以上提到的，zookeepr 保证所有消息的顺序一样，也保证所有提议的顺序。zookeeper 使用zookeeper事务id（zxid）保证提议的顺序。
所有的提议都会被加上一个zxid当这个提议被发起，这样通过zxid就能反映提议的顺序。提议被发送到所有的zookeeper server，
然后其中一个server如果认可该提议的话，这个server就会提交这个提议。若果提议包含一条消息，这个消息也会一起被提交当提交提议的时候。
认可该协议意味着持久化存储这个提议。成为"同意团"要求任何一个"同意团"必须有至少一个server。
我们通过要求每个"同意团"至少包含所有server数量的一半以上，即，至少一半以上的server同意该提议，该提议才有效。

zxid包含两个部分：纪元(每新选举一个leader，开启一个纪元，就像古代皇帝更替)部分和计数部分。zxid用一个64bit的数字实现。高32为表示纪元，低32为表示计数。
因为zxid的两部分都是用数字表示的(epoch,count).epoch（纪元）表示leader的改变。每次产生一个新的leader。就有一个数字特定的表示这个新的leader。
我们使用一个简单的算法给每个提议指定一个唯一的zxid：leader为每个新的提议将对应的zxid +1.leader 选举过程保证每个leader的epoch是特定的。这样每个leader对应的所有提议
和其他leader的提议肯定不同。这样就保证了提议的唯一性。

zookeeper消息系统由两部分组成：
leader激活：
这个阶段需要选举一个leader然后建立正确的系统状态，然后准备好接受提议
消息传递:
这个阶段leader接受提议，而且协调提议的正确传递。
zookeeper是一个整体的协议。我们并不关心单个提议，而是关注所有的提议流。严格的顺序特性保证了执行的高效和协议的简化。
leader选举体现了整体性。只有当"同意团"都同意这个server成为leader的时候这个server才有效，而且状态和leader都同步了，他们有相同的状态。
这个状态包含所有的提议都必须是已经提交的且生效的。这就是选举新leader的提议。

leader 激活
leader激活包括leader选举。当前zookeeper中有两个leader选举算法：leader选举算法和快速leader选举算法(快速认证选举法是通过UDP通讯，而且允许各个server使用一组简单的认证方式避免ip欺骗)。zookeeper消息并不关心使用哪一种具体选举法。只要选举结果满足以下要求就好：
leader的zxid必须是所有议员中最高的
"同意团"同意后提交的提议必须和leader的一致。
这两个要求只有第一个，leader的zxid必须保持最高的需要适当正确算法。第二个要求，只需要大部分议员同意该提议即可。zookeeper会复查第二个条件。如果在leader选举过程中发生错误，或者一部分server丢失了，zookeeper会放弃当前选举，重新开始新一轮的选举过程。

选举完成后，就有一个server成为leader,然后等待其他server连上该leader。其他所有的server都会连上leader。然后leader会同步所有的server，将它们缺失的提议记录都发送给他们。如果某个server的提议记录缺失太多了，leader会发送一个完整的存储记录快照给它。

有一个特别的情形必须特别处理，某个server接受了新的提议，但是它没有连上server。由于提议都是有顺序的。可能该server保持的zxid比server还要高。这种情就是要么该server在选举过程中被选举为leader。要么就是连上leader过后，该server所保持的这个比leader zxid还高的提议会被所有议员否决，直接丢弃。

当新的leader被选举出来后，会建立新的zxid，标示新的纪元(epoch),用来接受新的提议。新的纪元结构总是(e+1,0)，在新的纪元下，新的提议总是从0开始计数。在leader和某个server同步过后，leader首先会给server发送一个NEW_LEADER的提议。一旦NEW_LEADER的提议被提交(其实leader已经选举出来了，这个过程应该只是跑一遍表决过程，然后能够正式的记录下来。)，leader才能正式被激活然后开始接受一些其他的提议。

听起来很复杂但是其实在leader激活过程只有一下的几步操作：
A 议员在和leader同步过后，会确认收到一个NEW_LEADER的提议。
A 议员只会收到一个使用特定的zxid表示NEW_LEADER的提议从一个server那里。
A 议员会确认提交这个NEW_LEADER提议当大部分议员都确认提交了(系统中的每个提议其实么个议员(server)都是不会拒绝一个新提议的。)。
这个新leader必须在NEW_LEADER提议被提交通过过后才能接受其他新的提议。
如果leader选举(激活)过程意外结束了，因为NEW_LEADER提议还没有被提提交通过，所以这个leader没有任何选票，不会出任何问题的。当意外发生了，当前leader和其他的议员都会因为连不上而timeout的，然后会重新开始新的选举。

激活消息
leader激活是最繁琐的。一旦一个leader被确定了，它就开始接受提议。只要这个leader还在，就不会产生其他的leader，因为其他leader没有任何选票选举成为leader。如果一个新的leader产生，那么旧的leader肯定联系不上了。新leader会清理旧leaer的所有烂摊子。（其实就是开启新的纪元，还未提交的提议会被新的leader代为处理了。(此时现在这个leader还未正式加冕呢)）

zookeeper的消息处理方式和经典的双向提交确认很像

 
所有的联系通道都是FIFO.所以所有处理都是有顺序的。所以肯定有一下的操作限制：
leader发送提议给所有server是挨个发送的。因此，每个server接收到请求也是依序接收到的。因为FIFO的特性决定了server必须是依序收到的。
server顺序的处理收到的消息，这就意味着每个消息都必须被顺序的确认而且leader也是顺序的收到确认的消息，由于FIFO的特性，如果消息$m$被写入了持久化存储，那么在$m$之前被提议的消息也都被写入了持久化存储中。
一旦大部分投票同意这个提议，leader会发布一个COMMIT消息给所有server。由于消息已经被一个一个的确认了，COMMIT 消息会一个一个的发送给server，每个server也会都接收到。
COMMIT消息会被server顺序的处理，每个server会在该提议提交的时候一起传递消息。
总结
现在你明白，zookeeper怎么工作了吧?特别的，新leader怎么确认某些提议是确实被投票通过的呢？首先，所有的提议有一个唯一的zxid,这样，不同于其他协议，我们不必担心两个不同的提议会有同一个zxid;所有的议员收到而且记录提议是有顺序的；协议按顺序的提交，同一时间只会有一个有效的leader，所有的server也只是连接这一个leader.新leader记录下了前一个leader期间的所有提议，所以它总是持有最高的zxid的提议，这些提议都是被表决通过的；在前一个leader期间任何没有提交的的协议在新leader变得生效正式工作之前，都要首先被提交的。
比较
这个是不是很像multi-paxos算法呢?multi-paxos算法要求某种算法假设只有一个leader，我们不能依赖这种假设。相反我们使用leader激活过程去替换leader或者旧的leader确认它还是有效的。

那么这是不是就是paxos算法呢?激活消息的阶段是不很像paxos算法的阶段2。 实际上，消息激活就像paxos算法的第二个阶段，而且不必处理提议失败的情况。激活消息不会出现在两个算法中出现提议交叉这种情况。如果对于所有的package不维护严格的FIFO顺序，我们的算法就会分崩离析，不可靠的。我们的leader选举阶段也和这两种算法不同的。实际上，使用纪元的方法，就可以跳过未提交的提议而且不必担心一个zxid会有多个提议。

选票
投票特性保证了自动广播和leader选举的系统一致性。默认的，zoopeeker采用多数派投票机制，这就意味着每次提议的投票必须有多个server通过。典型的就是leader选举提案：leader会被确定一旦大部分投票都认可了这个提案。

如果需要从多数投票中提取重要的因素，那么zookeeper只需要保证通过投票保证某个提议的(比方leader选举提议)有效性就是每个投票中必须包含一个有效的server，多数投票保证这个因素。同时，还有其他不同于多数投票的方法，比方，可以对每个投票的server指定权重，这样，某些server的投票就更重要。获得一个有效的决议，我们只需要获得的投票分数大于总投票的分数。

在分层系统中，使用权重加权构造系统的结构被广泛使用。这种情况下，我们一般将所有的server分成几个组，然后给不同的组指定不同的权重。要形成决议，必须从主要的组G中得到足够server的支持，这样大组G中的每个小组g，只要从小组g中获得选票分数大于g总的选票分数总和。有趣的是，这种结构允许更小的投票确定一个提议。比方，如果我们有9个server，分成3组，然后每组指定权重为1 ，这样我们可以在只得到4票分数的情况下确定该提议有效了。具体就是有两组sever中各自有两个server同意。这种情况是有效的，某个小组中的大部分成员同意了，就表示在这个小组同意了。

在zookeeper中，提供了接口，配置zookeeper工作在多数投票，权重加权，或者分组结构的模式下。


原文http://zookeeper.apache.org/doc/trunk/zookeeperInternals.html
paxos算法http://zh.wikipedia.org/wiki/Paxos%E7%AE%97%E6%B3%95


最近在学习zookeeper，内部工作原理比较绕，我想想自己还是翻译一遍，加深理解。第一次翻译，有不对的，还请同行指出来。 后续我会自己写一些demo,写一些自己的理解给大家分享。
国内的大牛们其实也有很多人已经写了很多关于zookeeper的文章，但是大部分都是针对某一面，很多时候给我有些不识庐山真面目的感觉，本人喜欢到官网一遍一遍的看，了解清楚。
我也推荐大家到官网看相关介绍，翻译成中文，总觉得有点怪怪的...,英文不过关啊！

 

评论

2 楼 孤独的心 2013-06-14  

panggezi 写道

怎么大家都踩，我觉得不错啊，不过其实zookeepr并没有使用paxos算法，使用了一种叫zookeeper atomic broadcast protocol的协议，比paxos要简单许多。

我翻译的没有说用了paxos算法吧，但是应该是paxos算法改变的吧。而且这个不算一种算法吧，只是在paxos算法上使用FIFO特性，TCP的特性屏蔽paxos或者muti-paxos算法的缺陷。

1 楼 panggezi 2013-06-14  

怎么大家都踩，我觉得不错啊，不过其实zookeepr并没有使用paxos算法，使用了一种叫zookeeper atomic broadcast protocol的协议，比paxos要简单许多。