本文是对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
)