一个简单完全有序的广播协议
概要
一个简短的对于整个有序广播协议通过zookeeper的总览，叫做ZAB。它非常容易被理解，并且提供了很高的性能，我们展示了协议如何被使用，并且给了协议如何工作的概述。
1 介绍
在雅虎我们已经开发了高新的高可用协调服务叫做Zookeeper，这允许大规模应用程序协调任务，比如领导选举，状态广播和会面等协调任务。服务实现了数据节点的层级空间叫做znode，客户端使用它来实现协调任务。我们发现该服务在性能上是灵活的，它容易的面对生产环境的的web尺度的需求，以及我们在雅虎的关键应用程序。Zookeeper放弃了锁以及实现了无等待的共享数据对象和存储保证以及对这些对象的顺序操作。客户端库利用这些来保证它们的协调任务。一般来说，Zookeeper的一个主要前提是更新的顺序对应用程序来说比其他典型的协调技术（如阻塞）更重要。
Zookeeper中嵌入了一个完全有序的广播协议Zab。在执行客户端保证时，有序的广播是重要的；这也是在每个Zookeeper服务上维护Zookeeper的状态所必须的。这篇论文重点介绍了Zookeeper对于该广播协议的要求以及实现综述。
一个Zookeeper服务通常由三到七个机器构成。我们实现支持更多的机器，但是三到七个提供了足够的性能和弹性。客户端连接到任何一个机器提供服务，并且总是包含了Zookeeper的状态视图。服务器最多可以容忍f个崩溃，需要最少2f+1和服务。
应用程序广泛的使用Zookeeper，并且有数以万计的客户端同事访问它，因此我们需要高吞吐量。我们按照读写比例高于2：1的负载设计了Zookeeper；然而，我们发现Zookeeper的高写入吞吐允许它使用写主导的工作负载。通过每个服务的中Zookeeper的本地状态副本进行读取服务，Zookeeper提高了高的读取吞吐量。因此通过添加服务器，容错性和读取吞吐量都可以扩展。写入吞吐量不能通过添加服务器来扩展；相反，它受到广播协议吞吐量的限制，因此我们需要一个具有高吞吐量的广播协议。
图1展示了Zookeeper服务的逻辑组成。读请求从包含Zookeeper状态的本地数据库中得到服务。写请求被从Zookeeper请求进行幂等的传输，并且生成响应之前进行发送。Zookeeper的写请求本质上是有条件的：一个znode只有在没有任何子节点的情况下才能被删除；可以创建一个znode，并在其后面附加一个名称和序列号；对数据的修改只有在达到预期版本的时候才会应用。即便是非条件请求也会修改元数据，比如版本号，以一种不是幂等的方式。
通过将所有更新发送到一个服务器，这个服务器被称作为leader，我们将非幂等的请求转化为幂等的事务。我们使用术语事务（transaction）在这篇论文中表示幂等的版本。Leader可以执行事务，因为它对被复制的数据库的外来状态有完整的了解，并且可以计算新的状态记录。幂等事务可以是这个新状态的记录。Zookeeper在很多方面利用了幂等事务，它们超出了这篇论文的返回，但是我们事务的幂等特性也允许我们放松我们广播协议在恢复时的有序性要求。
2 需求
我们假设一组进程实现了原子广播协议并使用了它。在Zookeeper中为了保证准确的转化为幂等请求，同时只有一个leader是必要的，因此我们通过协议的视线强制存在一个这样的过程。当我们介绍更多协议的细节时，我们会详细讨论它。
Zookeeper对于广播协议有如下需求。
- 可靠交付：如果消息m，被一个服务进行交付，那么它最终会被交付到所有当前的服务上。
- 全序：如果消息a 在消息b之前被一个服务交付，那么所有的交付消息a和b的服务在a消息b之前
- 随意顺序：如果消息a偶然出现在消息b之前，并且两条消息都被传递，那么a必须在b之前排序。
为了正确性，Zookeeper额外添加了以下需求：前缀特性
- 前缀特性：如果m是传递给leader的最后一条消息，任何在m之前提出的任何信息必须送达。
记住进程可能选举多次，然而，每一次当选都视为不同的领导者，以满足这一前缀属性的需求。
基于三个保证，我们可以维护Zookeeper数据库的正确副本：
- 可靠性和全序保证允许所有副本有相同的状态
- 随机顺序保证允许应用使用zab有状态准确的观察
- leader根据收到的请求对数据库提出更新提议
值得注意的是，Zab考虑了俩种类型的因果关系。
- 如果两个消息 a 和 b 由同一服务器发送，并且 a 在 b 之前被提出，我们说 a 因果上先于 b。
- Zab假设一次只有一个leader服务器可以提交建议。如果leader改变了，任何之前的提交信息都会领先于新leader的消息。
违背因果的例子
为了展示违反第二个维度所造成的问题，考虑如下场景
- Zookeeper客户端c1请求znode /a设置为1，并将其转化为消息，w1它包含了“/a”, “1”, 1，其中元组表示路径，值和znode的结果版本。
- c1然后请求设置/a 为2，他将会被转化为消息，w2它包含了(“/a”, “2”, 2)
- L1提议并且投递w1，但是只能在失败之前向自己发出w2
- 新的leaderL2接任
- 一个客户端C2请求设置/a 为3条件是处于版本1，他会被转换成一个信息，w3他包含了(“/a”, “3”, 2)
- L2广播并且交付w3
在这个场景中客户端成功收到对w1成功的响应，但是对w2是错误的，因为leader故障了。如果最终L1恢复了，重新获得领导权，并且试图为w2提交提案，客户端请求的随机因果顺序将会被违反，复制状态将会不准确。
我们的故障模型是带有状态恢复的崩溃失败。我们不假设同步时钟，但是我们假设服务器感知到的相对时间流逝速度是相同的（我们使用超时来探测失败）。组成Zab的过程具有持久态，因此进程可以在故障之后重启，并且使用持久状态恢复。这意味着进程可以有部分有效的状态，比如缺少最近的事务，更有问题的是，进程可能有违背提交的事务，现在必须跳过这些事务。
我们准备处理f故障，但是我们也要处理相关的可恢复故障，比如停电。为了从故障中恢复，我们要求记录在quorum磁盘的介质上的信息进行传递。（非技术，务实，操作为导向的原因，以防止UPS设备，冗余专用网络设备，和NVRAM等整合到我们的设计中）。
虽然我们不假设拜占庭容错，我们使用摘要检测数据损坏。我们还将额外的元数据添加到协议数据包中，并用它们来进行完整性检查。如果我们检测到数据错误或者完整性检查失败则终止服务进程。
操作环境的独立实现和协议本身的实际问题使得完全拜占庭容忍系统的实现对我们的应用来说不切实际。达到真实的可靠性的独立实现需要的不仅仅是编程资源已经被表明了。到目前为止，我们的大部分生产问题要么是由于影响所有副本的实现错误，要么是Zab协议实现范围之外的问题，但这些问题会影响Zab，比如网络误配置。
Zookeeper使用了在内存中的数据库和存储事务日志，以及定期的在磁盘上进行快照。Zab的事务日志也作为数据库预写事务日志，因此一个事务只会被写入磁盘一次。因为数据库是在内存中的，所系我们使用千兆网卡，瓶颈是磁盘上的写入。为了缓解磁盘I/O的瓶颈我们分批写入事务，这样我们就可以在一次写入磁盘中记录多个事务。这个批处理发生在副本上，而不是在协议级别，因此实现相比于消息打包相比更接近于数据库的组提交。我们选择不使用消息打包来最小化延迟，同时还能获得通过批处理I/O打包到磁盘的好处。
我们带状态的恢复模型意味着当服务器恢复时，它将读入其快照，并且重播所有快照之后交付的事务。因此在恢复期间，原子广播协议不需要保证最多交付一次。我们对幂等事务的使用意味着，只要保持重启顺序，事务的多次交付是可以的。这是一个宽松的全序需求。此外，如果a在b之前被交付，并且在故障后重新交付a，b将也会在a之后重新投递。
我们还有其他的性能需求：
低延迟：Zookeeper被应用程序广泛的使用，我们的用户期望降低响应时间。
突发的高吞吐量：应用使用Zookeeper通常是读为主的工作负载，但偶尔会发生彻底的重新配置，导致写吞吐量出现较大的峰值。
平滑的负载处理：如果一个服务故障，它不是leader服务器，但是仍有正确服务器的法定数量，不应该有服务中断。
3 为什么是另一个协议
可靠性广播协议可以提出不同的语义取决于不同的应用需要。例如，Birman和Joseph提出了俩个原语ABCAST和CBCAST，分别满足总顺序和因果顺序。Zab也提供了随机和总顺序保证。
一个好的协议候选在我们的例子中是paxos。paxos有几个重要的特性，比如保证在一定数量失败下的安全，允许程序崩溃和恢复，并使操作能够在现实假设下的三个通信步骤下提交。我们观察到有几个现实的假设，我们可以让我们简化paxos来得到更高的吞吐量。首先paxos允许消息丢失和重排序消息。通过使用tcp来在服务的键之间进行沟通，我们可以保证消息的投递是以FIFO的顺序，当服务进程有多个未完成的提案信息时，这允许我们满足每个提议者的因果关系。然而，paxos，不直接保证英国关系，因为它必须要FIFO的通道。
提议者是 Paxos 协议中为不同实例提出值的代理人。为了保证进展，必须有一个单一的提议者在提出值，否则提议者可能会在某个实例上永远竞争。这样的主动提议者被称为领导者。当paxos从主的故障中恢复，新的leader需要保证所有部分交付的消息都是完全交付的，然后从老领导留下的实例号继续提出建议。由于多个主可以为给定实例提出一个值，因此出现了俩个问题。第一，提议可能冲突。paxos使用选举来检测和解决冲突的提案。其次，仅仅知道一个给定实例号已提交时不够的，进程还必须能够确定哪些值已经被提交。通过确保对于给定的提案号，只有一个消息提案zab协议避免了这俩个问题。这消除了对于选票的需要并简化了恢复。在paxos中，如果服务认为自己是主，它将会使用高的选票从之前的主那边接管主身份。然而，在Zab中，新的leader可以不能接管主，直到新的法定人数放弃了之前的主。
获得高吞吐量的另一种方式是通过限制每条消息的复杂度，比如Fixed-Sequencer Ring协议。吞吐量不会随着FSR的增长而降低，但是延迟会随着处理数量的增加而增加，这对于我们的环境不方便。当组保持长时间稳定的时候，虚拟同步还可以实现高吞吐量。但是任何故障都会触发服务的重新配置，因此在重新配置过程中会造成短暂的服务中断。此外，这种系统中的故障检测器必须监视所有服务器。这种故障探测器的可靠性对重构的稳定性和速度至关重要。基于leader的协议也依赖于故障探测，但是这样的故障探测只在一个时间监听一个服务，那就是主。我们将在下一节中讨论，我们不使用固定的法定人数或组进行写操作，只要服务不发生故障就保持服务的可用性。
我们协议有一个固定的序列器，根据经典的Defago分类，我们叫做主。这样的主通过主选举算法别选举并且通过其他服务的法定人数进行同步，叫追随者（follower）。因为leader要管理所有追随者的信息，因此根据广播协议，固定序列器分配在组成系统的服务器上不均匀地分配负载。我们采用这种方法是出于以下的原因。
- 客户端可以接受任何服务，服务器在本地提供读取操作，并且维护维护客户端的会话信息。这个从进程的额外负载（进程不是主）让负载更均匀的分布。
- 设计的服务器数量很少。这意味着网络沟通开销不会成为一下固定序列器的瓶颈。
- 没有必要实现更复杂的方法，因为这个简单的方法提供了足够的性能。
例如有一个移动的序列器，增加了实现的复杂性，因为我们需要处理token丢失等问题。此外我们选择放弃基于通信历史的模型，比如基于发送者的，为了避免此类协议二次消息的复杂性。此外目标一致协议也有类似的问题。
使用主需要我们让主从故障中恢复以保证处理。我们使用视图更改的相关技术，录入Keidar和Dolev协议中的技术。与这些协议不一样，我们不使用群通信。如果一个新服务加入或者离开（也许是崩溃），这样就不会导致视图的改变，除非这样的事件对应于leader崩溃。
4 协议
Zab协议包含了俩个模型：恢复和广播。当服务启动或者leader故障后，Zab转变为恢复模式。当leader出现，并且quorum服务器已经与leader同步状态时，恢复模式结束。同步他们的状态包括了保证leader和新的服务有相同的状态。
一旦一个主有了法定人数的同步追随者，他就可以开始广播消息了。就像我们在介绍中提到的，Zookeeper服务自身使用主来处理请求。主是一个服务他通过初始化广播协议来执行广播，除了主以外的任何服务器，它们需要广播信息第一步是转发信息给主。通过使用恢复模式中出现的主作为主来处理写请求和协调广播协议，我们消除了从写请求主到广播协议的主之前转发消息的延迟。
一旦主和法定人数的跟随者同步，它就开始广播消息。如果一个Zab服务上线，另一个leader正在积极的广播信息，服务将会开启恢复模式，发现并与主同步，并且开始参加消息广播。该服务将保持广播模式，直到leader发生故障或不再具有法定人数的追随者。任何法定人数的跟随者都可以让leader和服务保持可用。例如，由三个服务器组成的Zab服务，其中一个是主，俩个其他的服务是跟随者，将会移动到广播模式。如果其中一个跟随者死亡，服务将不会中断，因为leader还是有法定人数。如果一个跟随者恢复另一个死亡，仍然不会有服务中断。
4.1 广播
原子广播服务运行时使用的协议叫做广播模式，类似简单的俩阶段提交：主提出一个请求，收集投票并且最终提交。图2展示了我们协议的信息流。我们能够简化俩阶段提交协议，因为我们没有终止（aborts）；追随者要么接受主的建议要么抛弃主。缺少终止也意味着我们可以在法定数量的服务返回式提交，而不是等待所有服务器响应。这种简化的两阶段承诺本身无法处理领导者的失败，因此我们将会添加恢复模式来处理主的失败。
广播协议使用FIFO（TCP）管道来进行所有的沟通。通过使用FIFO管道，有序性保证变得十分容易；只要消息在接收时被处理，顺序就保持不变。
主广播要传递的消息的提议。在处理消息之前，leader单调递增的唯一id，叫做zxid，因为Zab保留随机顺序，传递的消息也将按照zxid顺序。广播包括将天和附加的消息放入传出队列中，以便通过FIFO的管道发送给每个follower。当follower接收到一个提议时，它会将其写入磁盘，在可能的情况下进行批处理，并在提议出现在磁盘介质上后立即向leader发送确认。当leader接收到来自大部分的确认，leader将会广播COMMIT和在本地交付信息。
注意，如果follower相互广播ack，那么leader不必发送COMMIT。这种修改不仅增加了网络通信量，而且还需要一个完整的通信图，而不是简单的星型拓扑，从启动TCP连接的角度来看，星型拓扑更容易管理。在我们的实现中，维护这样的图并跟踪客户机上的ack也被认为是不可接受的复杂性。
4.2 恢复
这个简单的广播协议工作的很好知道主故障或者失去了法定人数的跟随者。为了保证处理，选举新主的以及将所有的服务恢复到正确状态的恢复手续是必要的。为了leader的选举，我们需要一种高概率成功的算法来保证其有效性。leader选举协议允许不止主知道自己是主，同时法定人数也同意这个决策。如果选举阶段错误，服务器将不会取得进展，它们最终会超时并且重新开始主选举。在我们的实现中，我们有俩中不同的选主实现。最快的只要法定人数的服务是正常的可以在几百毫秒内完成选举。
回收程序的复杂性部分在于，在给定时间内，可能会有大量的提案正在执行。运行中的提案有一个最大数量是可配置选项，它默认是一千。为了使这样的协议能够在领导者失败的情况下工作，我们需要做出两个具体的保证：我们永远不要忘记被传递的信息，我们需要放弃那些被跳过的信息。
在一台机器上被传递的消息，必须被传递到所有机器，即便那个机器故障了。如果主提交了信息并且然后在提交之前故障了，就很容易发生这种情况，如图3所示。因为leader提交了信息，客户端可以在消息中看到事务的结果，因此事务必须被传递到所有其他服务器，以便客户端看到服务的一致性视图。
相反跳过的信息必须保持跳过。如果提案是由领导者提出的，而在其他人看到提案之前，领导者就失败了，那么这种情况很容易发生。例如在图3中没有其他服务器看到提案号3，因此在图4中，当服务1重启时，它需要确保在重新与系统集成时丢弃提案3。如果服务器1成为新的主，并且消息100000001和100000002已经交付，我们将会违反我们的有序性保证。
记住已传递消息的问题可以通过对leader选举协议的简单调整来解决。如果领导者选举协议保证新的领导者在服务器的法定数量中拥有最高的提案数，那么新的leader也会有所有已提交的消息。在提出任何新的消息之前，新的主首先保证所有的信息它们在事务日志中的内容已被通过法定人数的跟随者提议并提交。请注意，将新的leader作为具有最高zxid的服务器进程是对新选出的leader的优化，在这种情况下，不需要从一组追随者中找出哪一个包含最高的zxid并获取丢失的事务。
所有在正常运行的服务，要么是主，要么是追随者。主确保跟随者看到了所有提案，并且交付了所有提交的内容。它通过将任何新连接的跟随者（follower）尚未见过的 PROPOSAL（提案）排队，然后为所有这些提案排队一个 COMMIT（提交），直到最后一个已提交的消息来完成这一任务。在所有这些消息都排队之后，leader将follower添加到广播列表中，以供将来的proposal和ack使用。
跳过已经提出但从未交付的消息也很容易处理。在我们的视线中，zxid是一个64位的数字，较低的32位被用来简单的计数。每个提议都会增加计数器。高的32为是epoch。每当新的主接管它会获得他日志中最高的zxidepoch。增加epoch，并且使用了epoch为的zxid，并将新的计数器设置为0。使用epoch来标记主身份的改变，并且要求法定数量的服务器承认一个服务器是这个epoch的主。我们避免了多个leader发出同一个zxid的可能性。这个模式的一个优点是，我们可以跳过主失败的实例，从而加速和简化恢复流程。如果一个已经关闭的服务器重新启动了一个从未从以前的epoch交付的提案，那么它就不能成为一个新的leader，因为每个可能的服务器quorum都有一个具有来自较新epoch的提案的服务器，因此具有更高的zxid。当这个服务作为跟随者连接时，主检查最后提交的提案，已确定追随者最新提议的epoch并且告诉跟随者阶段其事务日志（即忘记）直到该epoch的最后一个提交的提案。在图4中，当服务1连接到leader，leader告诉他从事务日志中清楚3。
5 最后评论
我们能够快速的实现这个协议，并且在生产环境中被证明是健壮的。最重要的是应对我们高吞吐量和低延迟的目标。在一个非饱和的系统上，延迟以毫秒为单位进行测量，因为服务器数量无关，典型的延迟将对应于数据包传输延迟的4倍。突发的负载也能被优雅的处理，因为在法定人数响应提案是消息就会被提交。慢的节点不会影响突发的吞吐量，因为快的法定人数的服务不包含慢服务，它们可以回复消息。最后，由于leader将在任何仲裁结束后立即提交消息，因此只要存在正确的服务器仲裁，失败的提案follower就不会影响服务的可用性甚至吞吐量。
由于使用了这些协议的有效实现，对于读写比率为2:1或更高的工作负载混合，我们的系统实现达到每秒数万到数十万个操作。该系统目前正在生产中使用，并且被Yahoo！爬虫和雅虎！广告系统。