zookeeper（MIT-6_824课程学习记录）

zookeeper是一个在实际生产环境相当成功的系统，集成到了各种服务中，例如dubbo在使用zookeeper做服务发现，有的系统将zookeeper作为配置中心等等。zookeeper所以一定存在些值得我们学习的东西。以下便是我们能初步从zookeeper中获得的一些思考：

相对于Raft，Raft仅仅是一个库，需要自己写应用程序与Raft库进行交互。是否有一些独立、通用的系统来快速帮助我们构建分布式系统？所以第一个问题，对于通用的服务，API应该是怎么样的？zookeeper就是这样的通用的协调服务（General-Purpose Coordination Service）
对于多副本复制系统来说，多副本系统通常需要3台、5台、7台或者更多的服务器来满足容错，问题是我投入了N台服务器是否能够得到N倍的性能？

多副本系统的性能问题

先说第二点，性能问题，当我们增加服务器的CPU数量、CPU性能和提升其他硬件设施是否能让我的多副本系统变得更快？这是肯定的，因为能让副本的复制过程会变快。但是当添加过多的服务器的时候leader将会是一个瓶颈，leader接受每一个请求，然后将这些请求复制到其他副本服务器上，当增加副本服务器的数量的时候对于leader来说会增加负载。对于添加进来的副本服务器也仅仅是完成了leader交给它们复制请求的动作，实际上并没有做什么事情，所有的压力都在leader身上。所以我们可以论证当有了更多服务器以后会使得系统变慢。下图演示了多副本系统进行日志复制的过程。

在实际生产系统中可能读请求远远大于写请求，我们最简单的想法是能否可以利用空闲的副本服务器？所有的写请求只往leader发，而读请求可以往任意的副本发，这样我们确实很高兴，因为leader的读压力被完全分配到了各个副本服务器上。但是随之而来的问题是：如果我们将客户端的读请求发往随机的副本服务器能达到我们的预期吗？

类似于raft的多副本系统，副本服务器肯定存储着和leader的log的一份拷贝。例如服务器上层是一个key-value数据库，当通过leader写入了一个X的值，那们应该也可以在副本服务器中寻找到一个x的值，所以读请求是可以从副本服务器获取到预期结果的。但是存在的问题是副本中的数据可能不是最新的（up-to-date)。

很多原因可能造成副本没有最新的数据。1. 类似于raft的系统，如果leader的写请求没有发往某个副本请求就已经达到了过半的目标，那么该副本需要等待一段时间后才会被复制到副本中，期间肯定就不是最新的数据；2. 网络丢包导致数据并未被发送到某副本中，除此之外还有很多问题导致这种结果。最坏的情况是副本和leader出现了网络分区，这种情况副本与leader的Log会相差变大，等到网络分区结束后才会慢慢跟上leader的log。

所以从上面的分析来看，数据的实时性就是一个最大的问题。虽然从性能角度来看很美好，但是如果我们要做的是一个线性一致的系统，那么就不能将读请求发往副本。线性一致是要求不能读取到就的数据，必须读到的是读请求之前的最新一个写的结果。

但是我们从zookeeper的论文中看到，zookeeper可以随服务器的增加而提升性能，所以zookeeper肯定做了一些修改使得读请求可以发往其他副本。所以zookeeper如何确保读请求是安全的是一个让人好奇的问题。

一致性保证

在zookeeper中的做法是放弃线性一致性。zookeeper放弃了读的线性一致，不保证返回最新的结果。Zookeeper这里声明，自己最开始就不支持线性一致性，来解决这里的技术问题。如果不提供这个能力，那么（为读请求返回旧数据）就不是一个bug。这实际上是一种经典的解决性能和强一致之间矛盾的方法，也就是不提供强一致。

zookeeper有着自己的一致性保证（guarantee），来帮助应用开发人员来理解其工作原理。

第一个是写线性一致，所有的写请求都会按照线性顺序写入，这点和raft是相同的

第二点是任何一个客户端的请求，都会按照客户端指定的顺序来执行，论文里称之为FIFO（First In First Out）客户端序列

FIFO对写请求处理

对于FIFO队列是这样理解的，对于特定客户端来说，加入有A写请求，B写请求，C写请求，那么在这个特定的客户端上写请求的顺序就会按照A,B,C的顺序发送到服务器加入到所有客户端的写请求中，但是最终的执行结果对于这个客户端而言就是这个客户端的发送顺序，但是在总的写请求顺序中可能不是相邻的。所以，对于写请求，最终会以客户端确定的顺序执行；

FIFI对读请求处理

对于FIFO中的写请求来说可能会更复杂一点。我们应该这么考虑FIFO客户端序列，客户端会以某种顺序读某个数据，之后读第二个数据，之后是第三个数据，对于那个副本上的Log来说，每一个读请求必然要在Log的某个特定的点执行，或者说每个读请求都可以在Log一个特定的点观察到对应的状态。后续的读请求，必须要在不早于当前读请求对应的Log点执行。也就是一个客户端发起了两个读请求，如果第一个读请求在Log中的一个位置执行，那么第二个读请求只允许在第一个读请求对应的位置或者更后的位置执行。

这里的实现原理是zookeeper的每一条log都会被leader打上一个唯一的zxid。任何时候一个副本回复一个客户端的读请求，首先这个读请求是在Log的某个特定点执行的，其次回复里面会带上zxid。客户端会记住最高的zxid，当客户端发出一个请求到一个相同或者不同的副本时，它会在它的请求中带上这个最高的zxid。这样，其他的副本就知道，应该至少在Log中这个点或者之后执行这个读请求。

那如果副本没有这个最新的zxid的日志，那么副本有可能会等待或者拒绝这个请求，让客户端去找其他副本。

FIFO对混杂请求处理

更进一步，FIFO客户端请求序列是对一个客户端的所有读请求，写请求生效。我现在给Leader发了一个写请求，而Leader还没有处理完它或者commit它。之后我发送了一个读请求给某个副本。这个读请求需要暂缓一下，以确保FIFO客户端请求序列。读请求需要暂缓，直到这个副本发现之前的写请求已经执行了。这是FIFO客户端请求序列的必然结果，（对于某个特定的客户端）读写请求是线性一致的。

通过上面的描述可以看出zookeeper其实是一个最终一致系统。但是在zookeeper中也提供了一种方法来帮助达到最终一致

sync原语

Zookeeper有一个操作类型是sync，它本质上就是一个写请求。假设客户端A发起了一个写请求，而客户端B想知道最新的写入值，此时客户端B可以通过调用sync操作等待log更新，再发起一个读请求就能够读取到最新的值。可以这样去解释，如果我发送了一个sync请求之后，又发送了一个读请求。Zookeeper首先执行sync操作将sync对应的日志写到各个副本当中，由于客户端的FIFO特性，Zookeeper必须要向我返回至少是我发送的sync请求对应的状态。

对于上面的例子来讲，sync是很耗费资源的，这个操作将简单读操作转变为了耗时的写操作。除非必要否则不建议使用。

zookeeper的API

zookeeper的API从某种程度上来说是一个文件系统。有根目录，根目录下是各个应用程序自己的子目录。这样设计的原因也很容易理解，因为zookeeper期望为很多不相干应用程序服务，所以需要用一个命名系统（namespace）来区分不同的应用程序之间的数据。但是zookeeper的API也不是一个完全的文件系统，没有cd，mount这些动作，如果你要访问某个节点数据，只能是用全路径限定名来直接访问，例如访问/app1/p_1。

在zookeeper中目录和节点都称为znodes，共有两类节点

Regular节点：客户端创建后将会一直存在，除非删除了这个节点

Ephemeral节点：客户端可以创建临时的节点，这种节点的特性是要么客户端主动移除，要么是当客户端与zookeeper的通讯会话断开后会自动移除。

zookeeper在创建节点的时候还允许提供**sequential** 标记，则提供的节点名称作为前缀，在节点后面添加一个自增后缀。举个例子，如果在/app1/下创建节点p并且没有其他p节点，那么将会创建/app/p_1,如果再创建一个p节点将会是/app/p_2。至于zookeeper的自增值从多少开始我并不明确，只是举例说明这种节点的特殊性。

zookeeper的客户端API定义如下：

**create(path, data, flags):**创建一个路径名为path的znode，在其中存储数据[]，并返回新znode的名称。Flags允许客户端选择znode的类型:Regular，Ephemeral，并设置sequential标志;

delete(path, version): 如果指定的目录，如果版本匹配的话；

exists(path, watch): 如果path存在那么将返回true。如果watch设置为true，那么zookeeper会在path的信息变化时通知客户端；

getData(path, watch): 返回指定路径下的数据和元数据信息，例如版本号。与exist不同的是，如果path不存在是不会设置watch的；

setData(path, data, version): 写data到path对应的znode下，如果提交的版本号与znode的版本号一致的话。

getChildren(path, watch): 返回path下的所有子节点

sync(path): 让客户端等待zookeeper的副本复制完成，当前的path无效，用于后续扩展

zookeeper的API都有同步和异步的接口，异步不会阻塞调用线程。

zookeeper的API使用

配置中心应用

现在假设一种场景，假设有另外一个分布式系统现在选举出了一个新的leader，而这个新的leader再上线之后需要完成后多配置的变更，并且在变更完成后通知相关的进程。对此有两个重要的要求：

在新的leader上线开始变更配置时，其他进程不应该使用新leader的配置
如果新的leader在完成配置更新之前挂掉了，其他进程不能够使用部分更新的配置

对于zookeeper来说可以在应用程序路径中添加一个ready znode 。当这个ready znode 存在的时候就可以读取配置，如果不存在就不能读取。新leader上线后先删除掉ready znode 然后将配置写入，写入配置完成后再创建ready znode 。这些操作都是写请求。所以zookeeper能够对这些操作是能够保证线性一致的

接下来我们考虑读请求，假设此时有部分进行需要读取配置，那么这些进程将会先检查ready znode 是否存在，如果存在则读取配置，否则不读取。如果此时的ready znode 已经被删除并且重建，说明新leader已经完成了配置变更，那么进程来读配置的时候将会读到最新的配置。因为zookeeper的log是从zookeeper自身的leader复制到其他副本，而其他应用进程是与zookeeper的副本直接通讯的，当其他进程读取副本中的ready znode 也就说明ready znode 写请求也被复制到了副本中，所以此时读取是没有问题的。所以，尽管Zookeeper不是完全的线性一致，但是由于写请求是线性一致的，并且读请求是随着时间在Log中单调向前的，我们还是可以得到合理的结果。

再考虑一种场景，如果进程在读取副本是ready znode 是存在的，但是其他分布式应用的leader就将ready znode 删除了，并且在leader写入数据1时读取出了副本的数据f1，在leader更新完成后读取到了更新后的数据f2，这种情况下将会是一半的旧数据一半的新数据，这是不可接受的。

而Zookeeper可以保证，如果客户端向某个副本watch了某个ready znode，之后又发送了一些读请求，当这个副本执行了一些会触发watch通知的请求，那么Zookeeper可以确保副本将watch对应的通知，先发给客户端，再处理触发watch通知请求（也就是删除ready znode的请求）。

这意味着，客户端在完成读所有的配置之前，如果对配置有了新的更改，zookeeper可以保证客户端在收到删除ready znode的通知之前，看到的都是配置更新前的数据（也就是，客户端读取配置读了一半，如果收到了ready znode删除的通知，就可以放弃这次读，再重试读了）。

以上的内容也说明尽管zookeeper不是完全线性一致，但是还是能满足部分应用的场景需求，保证数据的安全性。

计数器应用

假设在zookeeper中的一个znode存储一个计数，现在客户端并发对数据进行更改，如果没有任何处理会怎么样？可以想象的是zookeeper对读请求是非线性一致的，运行读到旧的值，假设每个副本上的旧值都是10，现在有两个客户端要对数据进行并发修改，都将旧值加一后写入zookeeper，最后的结果是11而不是12。所以直接使用zookeeper来进行操作也是会有问题的，那zookeeper是如何解决这个问题的呢？

WHILE TRUE:
    X, V = GETDATA("F")
    IF SETDATA("f", X + 1, V + 1):
        BREAK

具体的处理流程如下：

首先你需要一个循环，循环开始时读取要修改的值，返回值本身和对应的版本号。
然后将值+1，版本号加一后设置，如果设置成功则退出循环，否则会带循环开始重新执行。

设置失败的情况很容易理解，假如客户端A和B同时获取到了F的值为10，版本号为1，不管A或B谁先执行成功，F的版本号都会变成2，另外一个执行写操作时会因为版本号不一致而失败。虽然本次操作失败了，但是在下次操作中可能成功最后完成操作，从全局来看这个操作最终一定会成功。

这个例子，其实就是大家常说的mini-transaction。之所以称之为mini-transaction，是因为这里并不是一个完整的数据库事务（transaction）。一个真正的数据库可以使用完整的通用的事务，你可以指定事务的开始，然后执行任意的数据读写，之后结束事务。数据库可以聪明的将所有的操作作为一个原子事务提交。一个真实的事务可能会非常复杂，而zookeeper支持这种非常简单的事务，使得我们可以对于一份数据实现原子操作。这对于计数器或者其他的一些简单功能足够了。所以，这里的事务并不通用，但是的确也提供了原子性，所以它被称为mini-transaction。

上述的这个mini-transaction 的实现方式我们也可以叫做CAS(compare and swap)，也类似于乐观锁。但是这种行为在大量并发争抢的情况下并不会有太好的表现，因为本身执行这个操作就是乐观的认为只有当前客户端在执行这个操作，适用于少写的情况。

简单锁

在zookeeper中获取锁可以这样处理

WHILE TRUE:
    IF CREATE("f", data, ephemeral=TRUE): RETURN
    IF EXIST("f", watch=TRUE):
        WAIT

创建节点f时还指定了节点是ephemeral的。具体执行流程是：

如果锁文件创建成功了，表明我们获得了锁，直接RETURN
如果船舰锁失败则开始对f进行watch，然后进入等待。
当f的状态更改（指删除）后将会唤醒客户端重新获取锁。

解锁的话直接删除节点f即可。

基于zookeeper的写线性一致和对watch的保证，zookeeper实现锁的逻辑是没有问题的。但是这种锁不是一个好的设计。这种锁会产生惊群效应（Herd Effect）（实际上不知道翻译成羊群效应还是惊群效应，好像两种翻译都对）。

所谓的惊群效应，对于计数器的例子来说，就是当有1000个客户端同时需要增加计数器时，我们的复杂度是 O(n^2) ，这是处理完1000个客户端的请求所需要的总时间。对于这一节的锁来说，也存在惊群效应，如果有1000个客户端同时要获得锁文件，为1000个客户端分发锁所需要的时间也是O(n^2)。因为每一次锁文件的释放，所有剩下的客户端都会收到WATCH的通知，并且回到循环的开始，再次尝试创建锁文件。

没有惊群效应的简单锁

在Zookeeper论文的结尾，讨论了如何使用Zookeeper解决非扩展锁的问题，从而避免羊群效应。

**Lock**
1 n = create(l + “/lock-”, EPHEMERAL|SEQUENTIAL)
2 C = getChildren(l, false)
3 if n is lowest znode in C, exit
4 p = znode in C ordered just before n
5 if exists(p, true) wait for watch event
6 goto 2
Unlock
1 delete(n)

处理逻辑如下：

在节点l下创建一个临时顺序节点n
进入循环，获取所有的节点l下的子节点
判断当前创建的节点n是不是节点l下的子节点中序号最小的，如果是则退出。
计算出节点l下的所有子节点中的在n节点之前的节点p
检测p节点是否存在并设置对节点p的watch然后等待。
如果当等待结束则回到第2步重新获取。

举个例子说明这个操作，假如现在节点l下有lock-0 也就是说锁现在被创建lock-0 的客户端A持有，那么现在当前客户端B在l下再创建一个节点lock-1 ,并watch节点lock-0 是否存在,然后客户端C此时也要获取锁，也会创建一个节点叫做lock-2 ,并watch节点lock-1 。其实本质上就是让获取锁这个事情处于一个等待队列。正常情况下lock-0 删除后会通知客户端B，而不会通知客户端C，因为客户端C没有watch节点lock-0 ,所以客户端C感知不到锁的释放。再看一种情况是假如客户端A没有释放锁，客户端B突然挂了，那么此时客户端C将会得到通知，但是当前节点l下还有比lock-2 更小的节点lock-0 ，所以客户端C还是会等待直到感知到锁的释放。

解决惊群效应的最好办法就是排队等待。后面会附加资料说明linux下的accpet惊群、epoll惊群如何解决，算是拓展资料。

读写锁

zookeeper的论文中也提到了读写锁如何实现和处理，也就是再上面的锁的基础上将读锁和写锁分开，剩余的处理过程都一致。

**Write Lock**
1 n = create(l + “/write-”, EPHEMERAL|SEQUENTIAL)
2 C = getChildren(l, false)
3 if n is lowest znode in C, exit
4 p = znode in C ordered just before n
5 if exists(p, true) wait for event
6 goto 2
Read Lock
1 n = create(l + “/read-”, EPHEMERAL|SEQUENTIAL)
2 C = getChildren(l, false)
3 if no write znodes lower than n in C, exit
4 p = write znode in C ordered just before n
5 if exists(p, true) wait for event
6 goto 3

其他应用

在zookeeper中还有其他的应用，例如如何利用zookeeper进行群组关系维护，双屏障等均不做展开。

关于MIT6.824学习zookeeper的总结

对于分布式多副本系统，例如raft，简单增加机器的数量并不一定能够提升性能，反而会加大系统负载，拖慢整个系统。有时可以在允许范围内牺牲掉严格的线性一致变成最终一致来提升性能，zookeeper就是这样的例子。
zookeeper是写线性一致但是读非线性一致，但是对应指定客户端来说进入FIFO队列的请求是线性一致的。严格意义上来说zookeeper是最终一致，也学习了zookeeper如何通过sync原语来实现线性一致。
zookeeper的API设计上给与了较多的启发，有看到其他人说etcd的API设计更加好用，这个后续可以再看下。
学习到了什么是惊群效应（Herd Effect）以及其解决方案—排队

总体来说本论文的重点相较于raft更多的启发是如何权衡一致性和性能。线性一致虽然能保证数据的安全性，但是性能较差。在允许范围内放弃线性一致也是一种解决性能低的办法。

参考资料

https://www.zhihu.com/column/c_1273718607160393728 MIT6.824 课程翻译
https://www.infoq.cn/article/kkylzqazdomqdkwxgxgv infoQ如何解决niginx惊群
https://www.zhihu.com/question/22756773 知乎关于惊群效应的解读
https://iswade.github.io/translate/zookeeper/#24 zookeeper论文翻译

附件

{% asset_link zookeeper.pdf %}
{% asset_link zab.pdf %}