[翻译] ZooKeeper Internals

[toc]

原文链接: https://zookeeper.apache.org/doc/current/zookeeperInternals.html

Introduction

这篇文档包含 ZooKeeper 的内部工作机制的相关信息. 目前为止, 讨论了以下几个 topic:

Atomic Broadcast

ZooKeeper 的核心是一个原子消息系统, 它可以使所有的 server 保持同步.

Guarantees, Properties, and Definitions

ZooKeeper 使用的消息系统可以提供如下保证:

可靠的投递(Reliable delivery):

如果一条消息 m 投递到了某个 server, 它最终会被投递到所有的 server.

全局有序(Total order):
如果在一台 server 上消息 a 在是早于 b 投递的, 拿在所有的服务器上 a 都会早于 b 投递. 如果 a 和 b 都是已被投递的 message, 那有可能 a 早于 b 投递也有可能 b 早于 a 投递.

因果有序(Causal order):
如果消息 b 的 sender 在收到了 a 之后发送了消息 b, 那么 a 一定早于 b.如果同一个 sender 先发送 b 再发送 c, 那么 c 一定晚于 b.

ZooKeeper 的消息系统同样需要高效, 可靠, 易于实现和维护. 我们会大量地使用消息, 所以我们需要系统能够处理每秒上千次的请求. 尽管我们需要至少 k+1 个正确的 server 才能发送新消息, 但我们必须能够从失败中恢复, 比如说断电. 当我们在实现系统时, 我们的时间和人力都很少, 所以我们需要一个工程师可以理解并且好实现的协议. 我们最终发现我们的协议满足所有的目标.

我们的协议假设我们能在 server 之间构建点对点的 FIFO channel. 尽管类似的服务通常会假设消息传递会丢失或者重新排序, 考虑到我们使用 TCP 进行通信, 我们对于 FIFO channel 的假设还是很实用的. 我们明确依赖了 TCP 的这些特性:

顺序投递(Ordered delivery):
数据是和它被发送的一样的顺序被投递的, 消息 m 直到 m 之前的消息都投递成功了 (delivered) 才会发送. (它造成的结果是, 如果消息 m 丢失则 m 后面的消息都会丢失.)

关闭后不会再有消息(No message after close):
一旦 FIFO chanel 关闭, 不会再从它这里收到新消息.

FLP 证明了如果在一个全异步的分布式系统中发生了故障, 是无法达成共识的. 为了确保再出现故障时我们能够达成共识, 我们会使用超时机制.(译者注: 可以达到部分同步) 然而, 我们依赖时间是为了保持存活(liveness), 而不是正确性(correctness). 所以如果如果超时机制出现了问题(比如说时钟出现了故障), 消息系统可能会挂起(hang), 但是不会违反它的保证.

FLP 是一篇论文, 也是准备翻译的, 挺久前挖的坑, 还没填. (我 在 丢 人

在描述 ZooKeeper 消息传递协议时,我们将讨论数据包(packets), 提案(proposals)和消息(messages):

数据包(Packet)
是通过 FIFO channel 传递的一段 bytes 序列

提案(Proposal)
是 agreement 的最小单位. proposal 通过 ZooKeeper server 的一个 Quorum 之间传递 Packet 来达成一致的. 大部分的的提案都会包含一个消息(Message), 但是 NEW_LEADER 提案是一个不含消息(Message)的例子.

消息(Message)
是一串 bytes, 会被自动地广播到所有的 ZooKeeper server. Message 会被放入到 Proposal 中, 并在投递前达成一致.

如上所述, ZooKeeper 能够保证 Message 的整体顺序, 也能保证 Proposal 的整体顺序. ZooKeeper 使用 ZooKeeper 事务 id(zxid) 来暴露整体的顺序. 所有的 Proposal 在提出时会被打上 zxid, 并能够明确地反应整体顺序. Proposal 将发送到所有的 ZooKeeper 服务器, 并在收到 Quorum 后的 ACK 后提交(commit).如果 Proposal 包含一个 Message, 消息将会在提交时被投递 (delivered). ACK 代表 server 已经将 Proposal 记录到持久化存储中了. 任何两个 Quorum 都必须至少有一个共同的服务器. 我们通过要求所有的 Quorum 都必须至少数量为$(n/2 + 1)$(n 为 ZooKeeper server 的数量) 来保证这一点.

zxid 由两部分构成: epoch 和一个 counter. 在我们的实现中 zxid 是一个 64 位的数字. 我们使用高 32 位存储 epoch, 低 32 位存储 counter. 因为 zxid 由两部分构成, 所以 zxid 即可以表示为一个数字, 也是可以表示一个整数对: (epoch, count). epoch 用来表示集群 leader 的变化. 每次一个新的 leader 被选举出来, 都会产生一个新的 epoch 数字. 我们有一个简单的算法来位每个 proposal 分配唯一的 zxid: leader 只需要增加 zxid 就可以保证每个 proposal 的 zxid 唯一性. Leadership activation 能够保证在每个特定的 epoch 中, 都指有一个 Leader, 所以我们简单的算法能够保证每个 proposal 能够有一个唯一的 id.

ZooKeeper 的通信包括两个阶段:

  • Leader 激活(Leader activation): 在这个阶段, leader 建立起系统的状态, 并准备好开始发起 Proposal.
  • 活动消息投递(Active messaging): 在这个阶段, leader 接受消息来发出 Proposal, 并协调消息投递.

ZooKeeper 是一个整体的协议. 我们不会注重于某个 proposal, 而是从整体上看 proposal 的 stream. 我们严格的顺序性可以使我们高效的做这件事, 而且很大的简化协议. Leadership activation 体现了这个整体的概念. 一个 Leader 只有被一个 quorum 的 follower(leader 也算是一个 follower, 你可以给你自己投票) 同步时才会激活, 他们都有相同的状态. 这个状态包括所有 leader 认为已经被提交(committed)的 proposal 和所有 follow 这个 leader 的 proposal, 即 NEW_LEADER proposal. (你可能在想, leader 认为提交过的 proposal 就是所有的真正被提交的 proposal 了吗? 回答是是的. 接下来我们将把原因说清楚.)

Leader Activation

Leader activation 包括 leader 选举(FastLeaderElection). ZooKeeper 并不关心选举的具体方法, 只要能够满足下面都可以:

  • leader 已经观察到了所有 followers 中最高的 zxid
  • 一个 Quorum 已经 follow 了 leader, 并已经 commit. (A quorum of servers have committed to following the leader.)

在两个需求中, 只有第一个 follower 中最高的 zxid, 是为了正确性而必须达到的. 第二个需求, Quorum 的 followers, 只需要高概率即可. 我们将会重新确认第二个需求, 所以如果在选举过程中发生了错误而且 quorum 丢失了, 我们会通过放弃这次 leader activation 并进行另一次选举来进行恢复.

Active Messaging

Summary

Comparisons

Consistency Guarantees

Quorums

Logging

Developer Guidelines