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

By | 2020年8月30日

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]。 该系统是一组进程image-20200819180140425

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

发表评论

电子邮件地址不会被公开。 必填项已用*标注