本文是对Apache官方在Zookeeper的wiki里对zk的核心算法 - Zab算法与另外一个广为人知的Paxos算法的区别描述文章的意译. 如果有任何异常,可以直接联系我更改. 阅读本文需要对Zookeeper和Paxos有基本的认识. 引用里是我自己添加的注释.
Zab是不是Paxos算法的一个特殊实现?
Zab是一个与Paxos不同的算法,尽管说他们有一些相同的关键点,比如:
一个向
followers提出事务提案的leader提交一个提案(proposal)之前,
leader需要等待过半(quorum)的followers的确定(acknowledgements)提案包含一个
epoch数字, 和Paxos里的ballot数字一样
PS: 就是一个版本号的意思
Zab和Paxos算法最主要的区别是设计目标不同, Zab是主要设计为一个主备系统(primary-backup systems),像Zookeeper这种. 而Paxos则是为了一个一致性状态机 (state machine replication)
主备系统和状态机系统的区别
状态机是一个处理一系列请求的软件组件,对每一个处理请求,它修改内部状态然后产生一个响应.一个状态机在这种情况下是确定的: 给定两台接收到相同顺序请求的机器, 它总是产生相同的内部状态和相同的响应.
一个状态机系统是一个Client-Server系统, 它确保每一台机器(replicas. 意译)已相同顺序的顺序执行客户端请求,即使请求是被客户端并发提交和服务器(replicas. 意译)乱序接收. 机器之间通过共识算法来确保执行客户端请求的执行顺序, 比如Paxos算法. 客户端并发,交替提交的请求可能被以任意顺序执行. 如果一个Leader挂掉,新选举出来的Leader可以对之前未提交的提案做任意的重排序
可以参考下
Zab算法在运行期间的Leader选举
在一个像Zookeeper之类的主备系统, 备机接收leader发出的”增量更新”, (原文:)
replicas agree on the application order of incremental (delta) state updates, which are generated by a primary replica and sent to its followers
不像客户端请求, 状态更新必须与产生的顺序严格一致(也就是与这个leader或者说master上的严格一致), 与leader的初始状态开始. 如果一个leader挂掉, 新选举出来的leader不能重排序之前未提交的提案, 或者说从一个不同的初始状态开始.
总的来说, 在主备系统的共识(agreement)要求严格的顺序性保证, 而状态机系统则相对没有这么严的要求.
共识算法的意义
Paxos算法在把Primary作为leader的时候可以作为一个”主备”算法, 但是它的关键问题是, 如果一个primary并发的提交多个状态更新并且还失败了, 那么新的primary可能会对这些重排序. 在DSN 2011 Paper有个例子. 在这个例子中, 一个replica本来应该仅仅在提交A后提交B, 但是使用Paxos, 新的primary可能在C后提交B, 也就到达了一个和之前primary不同的一个错误状态.
当然这个问题可以通过串行化提交提案,但是这个对性能的影响过大不予考虑.
而Zab不需要这些,Zab的replica可以在没有错误的情况下并发的同意多个状态更新. 这是通过在恢复阶段增加至少一个同步操作来达到的(相较于Paxos), 以及使用一个不同的机器标识 (zxid)