0%

论文研读之Zab协议

Posted on In

Zab是ZooKeeper中使用的用来保证可用性和一致性的协议. 论文为: A simple totally ordered broadcast protocol

写请求都通过一个leader服务器来执行, 这样就可以将非幂等(non-idempotent)的请求转化为幂等(idempotent) 的请求. 读请求可以在客户端直接连接的服务器执行, 但是返回的数据可能陈旧的或无效的, 当然, 可以通过参数指 明采用同步读以从leader读取最新数据.

ZooKeeper对广播协议的要求:

  • Reliabl delivery: If a message, m, is delivered by one server, then it will be eventually delivered by all correct servers.

  • Total order: If a message a is delivered before message b by one server, then every server that delivers a and b delivers a before b.

  • Causal order: If a message a causally precedes message b and both messages are delivered, then a must be ordered before b.

  • Prefix property: If m is the last message delivered for a leader L, any message proposed before m by L must also be delivered.

Two types of Causal Relationships

  • If two messages, a and b, are sent by the same server and a is proposed before b, we say that a causally precedes b;

  • Zab assumes a single leader server at a time that can commit proposals. If a leader changes, any previously proposed messages causally precedes messages proposed by the new leader.

Zab中没有特别说明如何实现leader选举, 主要包含两部分内容:

  • recovery: 当服务刚刚启动或leader fail后, 就进入recovery mode.
  • broadcast: 当产生新的leader, 并且leader已与大多数服务器同步, 即可开 始broadcast.

Recovery

当服务刚开始或发生leader failure之后, Zab就进入recovery mode, 直至产生新的leader, 并且 leader和大多数follower的状态已同步. 而完成这两个步骤之后, leader就可以广播消息.

选举新的leader时, 需要保证发生fail之前的消息不能被遗忘, 因此规定选举新选举的leader必须具有最 高的proposal number. 这样还可以避免新的leader向follower同步proposal.

另一种情况是上一轮被丢弃的消息由于延迟, 在选举出新的leader后出现, 必须保证能够正确丢弃这些 proposal. 解决办法是为proposal赋予一个 zxid, 假设为64bit, 高32bit作为 epoch, 低32bit作为计数器. 每次选举出一个leader, 就产生一个新的 epoch number, 并重置计数器为0. 所有的proposal都会附带当前leader产生的epoch number和计数器. 这样, 即可通过epoch number识 别proposal是否是陈旧的.

Broadcast

使用简化版本的两步提交(2-phase commit, 2PC), 由leader向follower发出proposal, follower 收到proposal时, 将其记录到磁盘, 但并不commit, 并向leader返回ack. 当leader收到大多数 follower的ack时, 即可commit该proposal, 并向follower发送COMMIT消息, 表明可以commit该 proposal.

broadcast使用的是FIFO信道(FIFO channel), 基于TCP即可实现, 这样就能保证消息的有序性.

leader会为每个proposal消息附带一个zxid, 详情见上文recovery.