用zookeeper来构建的一种一致性副本协议

我曾经在研究生期间负责开发过一个对可用性有要求的服务。为了保障该服务的可用性，我基于zookeeper设计了一个副本复制的解决方法，以确保当单个服务节点出现故障后，其他的备用服务节点能够被选为主用服务节点，并对外提供服务，以保障整个系统不受单点故障的影响。与此同时，还能保障系统的数据一致性。本文介绍的内容就是这种解决方案的总结和抽象。

在一个分布式系统中，多个有状态的服务节点协同工作，完成某项系统功能。对于服务节点来说，保障其无故障运行，或者当其出现故障时，能够快速恢复，是一件很有挑战的事情。同时，带有状态的服务节点在快速恢复时，还需要恢复到故障出现前的服务状态，更加地加大了系统设计的难度。

1. CAP定理

由Eric Brewer在2000年提出的CAP定理[1]，提出了在一个服务中，无法同时满足数据一致性，服务可用性和分区容错性。分区容错性不仅仅包含网络分区，还应该包括宕机等异常情形。由于在分布式系统中，分区容错性是必须被满足的，因此分布式系统只能在数据一致性和服务可用性中做出选择。

可用性指的是在足够长的时间内，一个服务可用的时间。因此为了提高可用性，需要提高系统的可靠性，也就是系统连续无故障运行的时间，和需要减少系统在出现故障后的恢复时间。系统的可靠性与系统本身的实现与部署有关，不在本文讨论的范围。本文的设计，主要关注的是系统故障后的恢复时间。

对于数据一致性，保障的是后续操作对于先前操作的可见性。如果后续的读取，无法读到先前写入的数据，会使得基于此系统的开发变得困难。

2. 多副本容灾

为了能够达成故障恢复的目标，传统的做法是基于主用服务器与备用服务器之间做同步或者异步数据复制，也就是primary-secondary协议[2]。当主用服务故障后，可以快速切换到备用服务。如果使用同步的数据复制，可以保障数据一致性，但是没办法保障系统可用性。因为无论主用服务还是备用服务出现了故障，都会导致服务不可用。因为必须将宕机服务重新启动后才能恢复服务，从而导致系统故障恢复时间变长。如果使用异步的数据复制，如果主用服务节点出现故障，可以很快切换到备用正常工作，从而缩短了故障恢复时间，因而提高了系统的可用性。但是有可能会出现数据不一致的情况，例如，用户在之前写入的数据，在后续的读取中无法被读到。

基于paxos[3]协议和raft[4]协议的系统是多副本容灾中最常用的解决方案。因为paxos协议或者raft协议能够保障数据一致性，并同时最大限度地保障系统可用性，只有当副本节点出现一半或以上的宕机情况时，才会影响可用性。否则，系统都能够在短时间内恢复回来，并拥有一致性的数据副本。但是由于在系统中嵌入地正确实现无论是paxos协议，还是简化的raft协议，都是相当有挑战的事情。为了简化上述系统的实现，我们可以借助像zookeeper[5]等高可用的分布式协调服务，来帮助我们完成选主，和节点状态监听等工作。从而在此基础上，完成日志复制等工作，进而大大地简化这个系统的实现。因此在这个系统设计中，我会使用zookeeper来完成选主和节点监听等工作。

3. 设计考虑

无论是在paxos还是raft中，系统保障的是CAP中的数据一致性和分区容错性，也就是CP。因为只要出现一半或者以上数量的副本节点宕机的情况，就会影响系统的可用性，因此paxos协议或者raft协议都不能保障完美可用性。本文设计的系统依然是保证了CAP中的数据一致性和分区容错性，但是为了简化实现，并没有采用paxos或者raft的方案。而是借鉴了了primary-secondary协议的做法，在主用节点和备用节点之间做同步日志复制。但同时引入了zookeeper来监听节点的存活状态，从而缩短了系统恢复可用的时间，提高了可用性。

因为本文设计的系统保障了数据一致性，牺牲了系统的部分性能和可用性。但是这种选择是值得的，保障了数据一致性的系统，可以屏蔽数据不一致给业务层带来的烦恼，从而降低业务开发的工作难度。

1. 复制状态机

在本文介绍的系统中，需要把服务节点抽象成一个状态机[6]。每个节点包含一组状态，一个转换函数和一个输出函数。客户发往服务节点的请求都可以抽象为一个操作日志，作为转换函数和输出函数的输入。多个相同初始状态的状态机，输入相同的操作日志序列，最终能够得到相同的状态，并且输出相同的结果。因此，系统只需要在多个副本节点中同步复制操作日志流，即可实现系统的状态复制。

2. 选主实现

在多个复制状态机，也即服务节点中，需要选举出一个主用服务节点，来对外提供读写服务。为了简化实现，本系统使用了zookeeper中的分布式锁服务来实现选主功能。多个服务节点在启动后都会向zookeeper中的同一目录下，去请求创建同一个临时锁文件。只有第一个服务节点能够创建成功，接着成为主用服务节点。其他服务节点成为备用服务节点，并去监听临时锁文件的状态。当主用服务节点发生故障，导致主用服务节点与zookeeper的租约到期，临时锁文件会被zookeeper删除，然后会通知其他的备用服务节点。备用服务节点接着可以再次请求创建临时锁文件，进而成为新的主用服务节点。

3. 节点存活状态监听

每一个节点都会在zookeeper上创建一个临时文件，并协商最大租约时间。当节点出现故障，租约到期后，临时文件会被删除，并向所有节点广播该节点的故障信息。当一个故障的节点恢复后，会重新到zookeeper上去创建临时文件，zookeeper会向其他节点广播该节点重新上线的消息。以上机制可以确保每一个节点都拥有了当前所有节点的存活状态。

4. 日志复制

主用服务节点在接受客户的操作日志流时，需要把日志流复制到备用服务节点上。每条日志都带有唯一自增序号。

对于每一条操作日志，主用服务节点会将操作日志顺序写入磁盘，确保操作日志的持久化，同时将操作日志发往所有的备用服务节点。所有的备用服务节点在接受到操作日志后，同样要把操作日志顺序写入磁盘，然后向主用服务节点返回确认。主用服务节点只要等到当前操作日志已经被写入本机磁盘，以及已经接收到除自己之外，所有的存活的备用节点的确认消息，就可以认为当前操作日志同步完成，可以去处理下一条操作日志。

在处理返回客户端当前操作日志处理完成，并去处理下一条日志之前，需要在zookeeper上记录当前最新确认成功提交的日志序号。在zookeeper上记录最新commit的日志序号，zookeeper会将最新commit的序号广播给所有节点，节点上就可以提交给状态机了，主用节点上还要返回客户端。最新commit日志序号，记录在zookeeper上，还可以用于以供后续节点宕机恢复以及新节点加入时使用。新恢复或启动的节点，只需到zookeeper上查询最新commit的日志序号，就可以向其他节点请求自己所缺失的日志了。

5. 故障恢复

当节点出现故障时，主要分这两种类型。

首先是主用节点出现故障。此时，新的主用节点会被选出来。由于主用节点和备用节点之间采用了同步的日志复制方式，所以备用节点可以快速地成为主用，而不用去其他节点上拉取未同步的日志。

接着，如果是备用节点出现故障。此时，主用节点的日志流同步复制操作会出现阻塞。当备用节点与zookeeper的租约到期后，备用节点故障的消息会被zookeeper广播到主用节点上。此时，主用节点的日志流同步工作可以继续下去。

当一个节点从故障中恢复回来，或者加入一个新节点。此时，该节点状态会落后于其他节点，该节点会向zookeeper获取最新确认成功提交的日志序号，然后向其他节点拉取缺失的操作日志。在该节点完成日志同步之前，无法应答其他节点和客户端的任何请求。

因此，该系统中，出现机器宕机和机器恢复时，都会导致系统短暂的不可用，无法处理操作日志，从而无法应答客户端的写入请求。但是，仍然能够应答客户端的读取请求。

6. 日志提交

日志在复制到所有的存活节点上后，最后需要确认提交状态。在很多一致性复制算法中，会将日志复制和提交的流程分离开。首先主用节点发起日志复制，复制成功后，再发起日志提交流程。当收到提交请求后，状态机就可以执行日志了。在本文设计的系统中，当完成日志复制后，主用节点会将提交日志id更新到zookeeper，通过zookeeper来广播其他节点操作日志的提交消息。通过zookeeper来分发和记录最新提交日志的id，虽然在系统性能上会有部分损耗，但是却能极大的简化系统的实现。

当一个新的节点加入复制组，或者一个之前故障的节点恢复后，提交日志都需要恢复到和zookeeper上的commit日志序号一样的位置，才能正常对外提供服务。因此，在新加入节点，或者节点恢复时，会导致系统暂时不可用，不可用的时间长短与节点日志恢复的时间有关。

当日志完成提交后，状态机就可以执行操作日志了，这里的状态机与具体的应用有关，不属于本文要讨论的范围。

1. 总体架构设计

该系统的总体架构中，需要有zookeeper集群，作为分布式协调服务，还有多个节点。其中有一个主节点，与多个备用节点。主用节点向备用节点同步日志。

架构图如下：

2. 系统接口

系统向用户暴露日志提交接口，并提供同步或者异步的提交确认。

接口名称	参数	返回值	说明
SubmitLogSync	log 操作日志, timeout 超时时间	state 提交状态	操作日志同步提交的接口，成功提交操作日志后返回成功。可以存在三种返回状态：成功，失败，和超时
SubmitLogAsync	log 操作日志, timeout 超时时间, callback((state) -> {}) 回调函数	无	操作日志异步提交的接口，成功提交操作日志后，调用回调函数，返回成功。回调函数中同样可能存在三种状态：成功，失败和超时

通过向用户暴露日志提交接口，用户可以通过客户端，向系统提交操作日志，系统在完成日志在多节点的复制后，会提交给状态机来执行。

3. 与Zookeeper交互的模块设计

Zookeeper在本文设计的系统中主要负责三个功能，选主，节点存活状态监听和记录最新一次成功提交的日志序号。

• Zookeeper上目录结构设计

因此在zookeeper上的目录结构如下所示：

文件和目录位置	作用	属性	监听节点	说明
/lock	用于选主，文件中保存主用的位置	临时文件	所有备用节点	创建这个文件的节点成为主用节点
/nodes/[ip:port]	记录每个节点的存活状态	临时文件	无	[ip:port]为节点接受请求的位置
/logid	记录最新一次成功提交的日志序号	普通文件	所有节点	每次更新都会广播给所有节点
/nodes	用于广播节点的实时存活状态	普通文件	所有节点	所有节点需要关注这个目录下节点的状态变化

• 节点存活状态监听

在每个节点启动后，都会去zookeeper的/nodes目录下面，创建一个临时文件，文件名称为本节点的地址，并在zookeeper上注册监听/nodes目录下面子节点的变化。

当有节点出现故障后，与zookeeper的心跳中断，租约到期。之后zookeeper会删除该故障节点创建的临时文件，并通知其他复制组节点，关于/nodes目录下的子节点变化。其他节点就可以实时知道当前所有节点的存活情况。

在节点注册完自身状态后，还需要去创建/lock的临时文件，如果创建成功，则成为主用节点。如果文件已存在，说明已经存在其他主用，则只需要监听/lock文件状态，并成为备用节点。当主用出现故障后，与zookeeper的租约也会到期，文件也会被删除，并通知备用节点。备用节点接收到/lock文件被删除的通知后，可以再次去创建/lock文件。

• 记录提交日志序号

在完成每一条日志的复制后，主节点会去zookeeper上更新最新的成功提交日志序号。Zookeeper会把日志序号变化的事件，广播给所有节点。

4. RPC设计

整个系统的实现，需要每一个节点上都实现以下功能的RPC。

• 处理主节点发送的日志

主节点会将客户端发送过来的操作日志，发往其他的备用节点。备用节点在接收到操作日志后，会将日志写入磁盘，并返回确认消息。

方法名	参数1	参数2	返回值
HandleOpLog	logId	log	ack
处理主节点发送的日志	接收到的日志的id号	接收到的日志	返回确认

• 处理日志拉取请求

在新节点，或者先前出现故障的节点恢复后，需要向其他节点拉取日志，同步到与其他节点一致的日志状态，然后才能正常对外服务。所以，这里同样提供了一个日志拉取的RPC调用。

方法名	参数1	参数2	返回值
PullLog	startId	endId	logs
处理日志拉取请求	拉取的起始日志id	拉取的最后日志id	返回日志

1. 节点上线

当节点上线后，首先在zookeeper的/nodes目录中创建一个临时文件。然后尝试在zookeeper上创建/lock临时文件，如果创建成功，则成为主用节点，否则，成为备用节点。

接下来，执行状态恢复的流程。读取zookeeper上/logid文件内的最新提交的日志序号，并读取本节点的最新提交的日志序号。比较两个日志序号，如果本节点已提交日志落后于其他节点，则调用PullLog的RPC，完成日志拉取并恢复。在日志恢复完成之前，无法响应客户端和其他节点的RPC请求。

完成日志恢复后，可以正常响应客户端和其他节点的RPC请求。

处理流程如下：

2. 主节点处理操作日志

当主节点接受到客户端的操作日志，首先写入磁盘，然后将日志通过HandleOpLog的RPC，发往备用节点，等待备用节点RPC都返回确认后，则认为该日志复制成功，修改zookeeper上/logid文件内容为该日志序号。如果发往某个备用节点的HandleOpLog的RPC调用失败，则不断重试，直到成功，或者该备用节点被zookeeper检测到出现故障。

处理流程如下：

3. 备用节点处理操作日志

当备用节点通过PRC HandleOpLog接收到主节点发送过来的操作日志后，首先需要写入磁盘，等待日志持久化成功后，再返回成功确认。

4. 状态机执行

当主用节点更新/logid 中的最新提交日志序号后，zookeeper会将日志序号广播给所有的节点，然后节点就可以推进状态机的执行日志。

5. 选主实现

在本系统中，选主是依赖于zookeeper来实现的，通过多个节点抢占创建zookeeper上的/lock文件。当主节点出现故障后，/lock文件会被zookeeper删除，然后广播通知其他备用节点。接收到通知的节点，可以再次抢占创建/lock文件。

1. 日志批量操作

在主节点接受到客户端的操作日志的时候，先不急着写入磁盘和发往备用节点。可以缓存一段时间的操作日志，然后再一起写入磁盘和发往备用节点，这样可以提高系统的吞吐量。但是主节点由于需要缓存日志，所以系统的响应延迟会增长。所以系统要根据业务场景来选择缓存时间。

2. 日志流水线操作

主节点不需要等到之前的操作日志都成功写入磁盘和复制到备用节点上后，才能发起新操作日志的复制操作。而是可以并行发起多条日志的写入磁盘和复制到备用节点的操作，从而某条日志的复制阻塞，不会影响到后面日志的复制操作。不过，主用节点在zookeeper上更新已提交日志序号的操作，日志序号必须是增长的。而且，状态机执行操作日志也是顺序执行。

3. 日志拉取

如果刚加入的节点，日志落后其他节点太多，可以通过生成snapshot文件，新节点拉取snapshot，来加快日志和状态的恢复。

4. 数据读取

由于在这个系统中，各个节点的状态是强一致的，所以数据读取可以在系统的任意一个节点上执行，从而降低主节点的系统负荷。所以本文介绍的是一个单写多读的系统，通过增长节点个数，可以优化数据读取性能，不过会导致写入变慢，因为日志同步的代价会加大。

如果业务中对读取到的数据不要求强一致，允许一定的延时，可以考虑加入异步复制的弱一致节点。弱一致节点不参与主节点的选举和同步的日志复制，只会异步的向普通节点拉取日志，并对外提供弱一致性读的功能。

1. 与客户端交互

客户端在向主节点提交操作日志后，主节点需要向客户端返回确认。返回确认的时间应该是在将日志序号更新到zookeeper的/logid中后，因为此时就可以确认日志已提交。

如果系统由于异常，比如网络中断，机器宕机等，导致客户端超时未得到日志提交结果。此时，进入未知状态，客户端需要先向系统读取日志提交情况，根据情况来决定是否重新执行日志提交。

2. 与paxos和raft的比较

在本系统中，只要有一台机器出现故障，就会导致系统的不可用，不可用的时间与zookeeper的租约时长有关。但是在paxos中，单台机器的故障不会导致系统的不可用。如果是带有leader的paxos实现，如果leader所在的机器出现故障，新选出的leader需要执行两阶段流程恢复日志状态，恢复时间与新leader恢复日志的时间有关。所以paxos上如果leader所在节点出现故障，才会导致系统不可用，不可用时间与选主和日志恢复时间有关。在raft中，leader会由日志最长的机器担任，所以raft不存在日志恢复流程。所以raft系统同样只受leader故障的影响，不可用时间与选主时间有关。

在有节点加入的时候，本系统同样会出现不可用的情况，不可用时间与日志恢复的时间有关。但在paxos和raft的系统中不会有这种问题。

但是在paxos和raft中，只要出现一半或者一半以上的节点故障，系统将没办法自动恢复，需要人工介入。但是在本系统中只有所有节点出现故障，才会导致系统没法自动恢复。人工介入系统恢复会导致不可用时间延长，从这个角度来说，本文介绍的系统可用性要好于paxos和raft。

3. 适用场景

本文介绍的系统由于日志需要同步复制到所有的节点，因此不适用于部署在网络故障率高，网络延迟高的广域网场景，仅仅适用于数据中心内的局域网部署。

1. 测试环境

测试环境由6台共有云上的主机组成，这几台主机处于同一个数据中心。其中，有三台用于部署zookeeper集群，有三台服务器用于部署本文设计的高可用系统集群。

2. 测试说明

本测试主要集中于当系统中出现节点宕机后，系统可用恢复所要的时间。而对于系统的整体读写性能，以及当新节点加入后的系统可用恢复，都与系统具体实现有关，不在本测试讨论的范围。

集群中有三台服务器，其中有一台主用节点，和两台备用节点。当备用节点故障后，主用节点无法向其复制日志，因此日志提交无法推进，此时系统处于不可用状态。接着当故障的备用节点与zookeeper的租约到期，然后zookeeper通知主用节点，此时主用节点更新存活节点列表，不会向该故障节点复制日志。此时系统故障恢复，进入可用状态。

当主用节点出现故障时，系统同样进入不可用状态。故障的主用节点与zookeeper的租约到期后，zookeeper会通知其他备用节点，主用失效的消息。备用节点首先要抢占创建zookeeper上的/lock文件，接着更新存活节点列表，最后系统的故障才可以恢复，进入可用状态。

主用节点调用HandleOpLog向备用节点复制日志的RPC超时时间设置为1s。

下述测试结果，与具体的程序实现有很大的关系，我根据研究生期间基于此设计开发的程序的测试结果，得出了下面的结果。

3. 测试结果

备用节点宕机恢复测试结果如下：

租约时间/s	系统不可用时间/s
5	6.8
10	12.1
20	22.5

主用节点宕机恢复测试结果如下：

租约时间/s	系统不可用时间/s
5	7.4
10	13.2
20	23.5

这里测试的不可用时间，根据的是主用节点和备用节点的日志数据估算而来，可能存在些误差，待后续再设计合理的测试场景来验证。

本文是通过在高可用实践中的一点思考，从而设计出来的一种在保障数据一致性的条件下，解决系统高可用的设计思路。相比于paxos和raft协议，由于本设计需要依赖于分布式协调服务，因此在性能等方面不占优势。但是本设计依然有其自身的优点，比如实现简单，易于理解，从而能更容易地证明其实现的正确性。

本文提到的一致性副本协议，正在解耦出来，准备成为一个通用的多节点副本拷贝库，目前还在开发中。。。

[1] Brewer, Eric A. "Towards robust distributed systems." PODC. Vol. 7. 2000.
[2] 刘杰. 分布式系统原理介绍
[3] Lamport L. The part-time parliament. ACM Transactions on Computer Systems (TOCS). 1998
[4] Ongaro D, Ousterhout JK. In search of an understandable consensus algorithm. InUSENIX Annual Technical Conference 2014
[5] Hunt P, Konar M, Junqueira FP, Reed B. ZooKeeper: Wait-free Coordination for Internet-scale Systems. InUSENIX annual technical conference 2010
[6] Schneider FB. Implementing fault-tolerant services using the state machine approach: A tutorial. ACM Computing Surveys (CSUR). 1990