《ZooKeeper’s atomic broadcast protocol: Theory and practice》译文

ZooKeeper’s atomic broadcast protocol: Theory and practice

André Medeiros March 20, 2012

Abstract

Apache ZooKeeper是用于云计算的分布式协调服务，可为其他分布式应用程序提供基本的同步和组服务。 核心是原子广播协议，该协议选举一个领导者，同步其他节点，并执行来自领导者更新的广播。 我们研究了该协议的设计，主要介绍了该协议所承诺的性能，并分析了它在Apache中的正式实现。 特别是，详细研究了默认的领导者选举协议。

1 Introduction（简介）

ZooKeeper [8、10、11、12、19]是目前由雅虎和Apache软件基金会维护的云计算应用程序的分布式容错协调服务。 ，它通过封装分布式协调算法并维护简单的数据库，为其他云计算应用程序提供基础服务。 该服务旨在具有高可用性和高可靠性，因此多个客户端进程依靠它进行引导，存储配置数据，运行进程的状态，组成员关系，实现同步原语和管理故障恢复。 它通过复制来实现可用性和可靠性，并被设计为在以读为主的工作负载中具有良好的性能[12]。 ZooKeeper数据库的完全复制是在一组主机上执行的，即由许多主机服务器组成，常规配置为三到五台，其中一台是集群的领导者（即多数）。 只要集群中的主机数目足够，就可以提供服务。 ZooKeeper的关键组件是Zab，它是ZooKeeper原子广播算法，该协议管理副本的原子更新。 它负责在集群中达成共识选举出领导者，同步副本，管理要广播的更新事务，以及从崩溃状态恢复到有效状态。 我们在本报告中对Zab进行了详细的研究。 本报告的概要如下。 下一部分将介绍原子广播协议的背景知识。 在第3节中，我们介绍Zab的设计，在第4节中，我们对其实现进行分析，最后以第5节中结论结束。本报告的主要参考文献为[12，19]

2 Background（背景）

广播算法将消息从一个进程（主进程）传输到网络或广播域中的所有其他进程（包括主进程） 原子广播协议是分布式算法，可以保证正确的广播消息或没有其他影响的情况下中止。 它是广泛应用于分布式计算中的一种组通信方式。 原子广播也可以定义为满足完全有序[3]的可靠广播，即满足以下属性[4]

• 有效性：如果一个正确的进程广播了一条消息，则所有正确的进程最终都会传递该消息。

• 统一协议：如果一个进程传递了一条消息，则所有正确的进程最终都会传递该消息。

• 统一完整性：对于任何消息m，每个进程最多只能发送一次m，并且仅当m的发送者先前已广播了m。

• 统一完全顺序：如果进程p和q都传递消息m和m’，如果p在m’之前传递了m，则q在m之后传递m’

Paxos [14，15]是用于解决分布式共识的传统协议。 它最初不是为原子广播而设计的，但在Défago等人的论文中展示了[4]如何将共识协议用于原子广播。 还有许多其他原子广播协议，ZooKeeper中考虑使用Paxos，但是它不能满足服务所需的某些关键属性。 这些属性在第2.3节中进行了描述。 Zab旨在满足ZooKeeper的要求，同时保持与Paxos的相似之处。 有关Paxos的更多详细信息，请参见[15]。

2.1 Paxos and design decisions for Zab

Zab两个重要需求[12]是处理多个未完成的客户端操作以及有效地从崩溃中恢复。 未完成的事务是已经提出但尚未完成的操作。 对于高性能，ZooKeeper可以处理客户端请求的多个未完成状态更改，并根据FIFO的提交顺序去提交操作，这一点很重要。 此外，系统在领导者崩溃后可以有效恢复也是非常有用的。 原始Paxos协议不支持多个未完成的事务。 Paxos不需要FIFO通道进行通信，因此可以容忍消息丢失和重新排序。 如果两个未完成的事务具有先后顺序依赖性，则Paxos不能具有多个未完成的事务，因为不能保证FIFO顺序。 可以通过将多个事务分批处理到一个提议中，并一次最多允许一个提议来解决此问题，但这会带来性能缺陷。 在Paxos中，从Leader崩溃中恢复时使用事务序列的操作效率不够高[12]。 Zab通过采用事务标识方案对事务进行整体排序来改进此问题。 在该方案下，为了更新新的主进程的应用程序状态，只需要检查每个进程中最高的事务标识符，并仅从接受了具有最高标识符的事务的进程中复制事务。 在Paxos中，序列号不能应用这种方式，因此新的Leader必须对所有先前的序号（在Zab术语中，“已提交事务”）执行Paxos的第一阶段。 ZooKeeper的其他性能要求[19]：

• 低延迟
• 在突发条件下具有良好的吞吐量，处理写工作负载迅速增加的情况，例如大规模系统重新配置期间。
• 平稳的故障处理，以便某些非领导节点崩溃时，该服务可以保持正常运行。

2.2 Crash-recovery system model

ZooKeeper假设崩溃恢复模型为系统模型[12]。 该系统是一组进程， 在本报告中也称为对等体，它们通过消息传递进行通信，每个进程都配备有稳定的存储设备，并且可能多次崩溃和恢复。 > 的quorum是子集Q，Q⊆ /> >并且 >的半数。任何两个quorum都有一个非空的交集。每一个进程都有两个状态, up和down。进程的down状态是从崩溃的时间点到他恢复的时间点; up状态是从恢复的时间点到*。