MIT6824笔记六 线性一致与Zookeeper

这节课主要介绍了线性一致的概念与Zookeeper论文。

线性一致描述的是系统的行为，正确的行为是客户端发送了一个写请求并且收到服务端答复后，这个写请求能被之后的读请求看到。每个读请求看到的都是最新的写请求所作的更改。

Zookeeper论文是我接触到的最抽象的一篇论文。首先它的功能就很抽象：分布式协调内核。它提供的两个保证：线性写和FIFO客户端请求也费时间理解。最后则是它的API调用以及具体实现。

读这篇论文的原因我想一是Zookeeper的广泛使用，证明了其实用性；二是其“线性一致”的设计，契合课程。收获就是其API的设计、Watch模式。

参考文章：【MIT 6.824】学习笔记 6: ZooKeeper - 知乎

线性一致

（1）例子

example history 1:
  |-Wx1-| |-Wx2-|
    |---Rx2---|
      |-Rx1-|
is this history linearizable?

满足以下两个要求：

• 线性后的序列要与实际请求时间相匹配（一个请求的结束时间在另一个请求的开启时间之前，那么线性序列也必须遵守）
• 每个读请求看到都是序列中前一个写请求的值

（2）线性一致

线性一致更多描述的是关于系统行为的定义，我们只能通过一系列请求以及返回值来推测一个系统是否是线性一致的。

在一个线性一致的系统中，读请求不允许返回旧的数据。也就是说，如果我发起了一个写请求，然后再读，如果读到的不是上次写的值，那这个系统就不是线性一致的。

ZooKeeper

参考了个人笔记：https://zhuanlan.zhihu.com/p/363396366

介绍Zookeeper

Zookeeper是一个通用的分布式协调服务（General-Purpose Coordination Service），通过提供协调内核/客户端API的形式，让开发者自己实现诸多原语/功能，包括统一命名、配置管理、成员管理、分布式锁、双重屏障等。

Zookeeper基于Zab（类似Raft的基于领导者的原子广播协议）实现了多副本容错机制，但不同于Raft，Zookper的所有副本都能接受读请求。这得益于Zookeeper的两个设计：线性写和FIFO客户端请求。

Zookeeper为客户端提供了一组数据节点（称之为Znode），Znode根据分层名称空间进行组织，记法上类似于Unix的文件系统。客户端通过Zookeeper提供的API能对数据节点进行创建、删除、读取、写入、获取目录下所有文件等操作。Zookeeper还实现了一种Watch机制，通过此机制，客户端能够监听某个Znode的变化（更新、删除），Zookeeper会在Znode发生变化时向客户端发送一条通知消息。

Zookeeper API

Zookeeper的API某种程度上来说像是一个文件系统。它有一个层级化的目录结构，有一个根目录（root），之后每个应用程序有自己的子目录。文件和目录都被称为znodes。

`CREATE(PATH，DATA，FLAG)`。入参分别是文件的全路径名PATH，数据DATA，和表明znode类型的FLAG。这里有意思的是，CREATE的语义是排他的。

`DELETE(PATH，VERSION)`。入参分别是文件的全路径名PATH，和版本号VERSION。有一件事情我之前没有提到，每一个znode都有一个表示当前版本号的version，当znode有更新时，version也会随之增加

`EXIST(PATH，WATCH)`。入参分别是文件的全路径名PATH，和一个有趣的额外参数WATCH。通过指定watch，你可以监听对应文件的变化。

`GETDATA(PATH，WATCH)`。入参分别是文件的全路径名PATH，和WATCH标志位。这里的watch监听的是文件的内容的变化。

`SETDATA(PATH，DATA，VERSION)`。入参分别是文件的全路径名PATH，数据DATA，和版本号VERSION。如果你传入了version，那么Zookeeper当且仅当文件的版本号与传入的version一致时，才会更新文件。

`LIST(PATH)`。入参是目录的路径名，返回的是路径下的所有文件。

Znode有两种基本类型：Regular和Ephemeral。创建的api还包括一个sequential flag。Znode还关联了时间戳、版本信息。

更新方法都带有一个版本号参数，只有版本号与Znode的版本号一致时，更新操作才能成功。

配置管理

如何利用Zookeeper实现动态配置管理？非常简单。

配置管理器将配置写在一个Znode中，其他进程读这个Znode，同时设置Watch标志位。如果Znode中的配置改变了，那么其他进程将会收到通知，并且会再次读取最新配置。

集合点

Rendezvous我理解为进程同步。客户端创建Znode，然后将Zode的full path作为参数传递给master process和worker process。如果master process先创建完成，那么它就将它的信息（addresses and ports）写入到Znode中；如果是worker process先创建完成，它照样读取Znode并设置Watch标志位，后续mater改变Znode后，worker就能读取信息。

组成员管理

利用一个Znode 表示组。当组成员创建时，只需创建一个对应的Znode的Child Znode。如果需要唯一的对应，可设置Sequentail标志位。如果需要获取一个Group的信息，只需要简单调用list api查看Znode的所有Child。如果一个进程要监视组信息的变化，为每一个组成员设置Watch标志位即可。

ephemeral node有一个好处是能代表会话的状态，当进程失败或结束时，ephemeral node会自动移除。

分布式锁

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

总的来说，先是通过CREATE创建锁文件，或许可以直接成功。如果失败了，我们需要等待持有锁的客户端释放锁。通过Zookeeper的watch机制，我们会在锁文件删除的时候得到一个watch通知。收到通知之后，我们回到最开始，尝试重新创建锁文件，如果运气足够好，那么这次是能创建成功的。

Herd Effect

如果有1000个客户端同时要获得锁文件，为1000个客户端分发锁所需要的时间也是N方。因为每一次锁文件的释放，所有剩下的客户端都会收到WATCH的通知，并且回到循环的开始，再次尝试创建锁文件。

为了获得锁，要通知一大群的线程，也就是惊群，最会只有一个线程能获得锁。

CREATE("f", data, sequential=TRUE, ephemeral=TRUE)
WHILE TRUE:
    LIST("f*")
    IF NO LOWER #FILE: RETURN
    IF EXIST(NEXT LOWER #FILE, watch=TRUE):
        WAIT

代码第4行，如果现存的Sequential文件的序列号都不小于我们在代码第1行得到的序列号，那么表明我们在并发竞争中赢了，我们获得了锁。所以当我们的Sequential文件对应的序列号在所有序列号中最小时，我们获得了锁，直接RETURN。序列号代表了不同客户端创建Sequential文件的顺序。在这种锁方案中，会使用这个顺序来向客户端分发锁。当存在更低序列号的Sequential文件时，我们要做的是等待拥有更低序列号的客户端释放锁。在这个方案中，释放锁的方式是删除文件。所以接下来，我们需要做的是等待序列号更低的锁文件删除，之后我们才能获得锁。

所以，在代码的第5行，我们调用EXIST，并设置WATCH，等待比自己序列号更小的下一个锁文件删除。如果等到了，我们回到循环的最开始。但是这次，我们不会再创建锁文件，代码从LIST开始执行。这是获得锁的过程，释放就是删除创建的锁文件。

学生提问：为什么这种锁不会受羊群效应（Herd Effect）的影响？

Robert教授：假设我们有1000个客户端在等待获取锁，每个客户端都会在代码的第6行等待锁释放。但是每个客户端等待的锁文件都不一样，比如序列号为500的锁只会被序列号为501的客户端等待，而序列号500的客户端只会等待序列号499的锁文件。

每个客户端只会等待一个锁文件，当一个锁文件被释放，只有下一个序列号对应的客户端才会收到通知，也只有这一个客户端会回到循环的开始，也就是代码的第3行，之后这个客户端会获得锁。所以，不管有多少个客户端在等待锁，每一次锁释放再被其他客户端获取的代价是一个常数。而在非扩展锁中，锁释放时，每个等待的客户端都会被通知到，之后，每个等待的客户端都会发送CREATE请求给Zookeeper，所以每一次锁释放再被其他客户端获取的代价与客户端数量成正比。

双重屏障

// todo

计数器

第一个很简单的例子是计数器，假设我们在Zookeeper中有一个文件，我们想要在那个文件存储一个统计数字，例如，统计客户端的请求次数，当收到了一个来自客户端的请求时，我们需要增加存储的数字。

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

这个例子，其实就是大家常说的mini-transaction。这里之所以是事务的，是因为一旦我们操作成功了，我们对计数器达成了_读-更改-写_的原子操作。

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

Zookeeper的保证

Zookeeper基于Raft框架，是容错的，在发生网络分区的时候，也能有正确的行为。Zookeeper有一些性能增强，使得读请求可以在任何副本被处理，因此，可能会返回旧数据。

为什么Zookeeper在允许多副本读的情况下还能保证正确的行为？

这得益于ZooKeeper 两个基本的一致性保证：线性写和先进先出(FIFO)的客户端请求。

写请求是线性一致的

All requests that update the state of ZooKeeper are serializable and respect precedence.

Leader 保证写操作的顺序，并且该顺序在所有 Follower 上保持一致。

客户端可以并发的发送写请求，然后Zookeeper表现的就像以某种顺序，一次只执行一个写请求，并且也符合写请求的实际时间。所以如果一个写请求在另一个写请求开始前就结束了，那么Zookeeper实际上也会先执行第一个写请求，再执行第二个写请求。

所有更改Zookeeper状态的请求都是线性的，那么这就保证了主从状态一致性。

先进先出的客户端请求

All requests from a given client are executed in the order that they were sent by the client.

每个客户端可以为其操指定一个顺序，ZooKeeper 会按照客户端指定的顺序来执行。即zookeeper为每个单独的客户端提供了线性一致性。

这里的线性一致性只对于单个客户端的请求。比如说，客户端先发了一个写请求，然后再发读请求到落后的副本，那么这个读请求得看到它自己之前的写更新。

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

ZooKeeper 通过 zxid 来实现，zxid 是最后一个事务的标记，当客户端发出一个请求到一个相同或者不同的副本时，会在请求带上 zxid 标记，副本通过检查客户端的 zxid 和自己的 zxid，保证读到的是更新的 zxid 的数据(没有具体说怎么处理，是阻塞等待还是拒绝请求)

更进一步，如果同一个客户端发送一个写请求<X, 17>，然后立即去某个副本服务器读 X，这里会暂缓一下读请求，直到这个副本发现写请求的 zxid 已经执行了，即客户端将会读到 <X, 17>，不会读到过期的数据。

同步操作 sync

尽管有了Zookeeper的两个保证，但这还不是线性一致性。Zookeeper提供了另外一种弥补线性一致的方法：sync。

To handle this scenario more efficiently ZooKeeper provides the sync request: when followed by a read, constitutes a slow read. sync causes a server to apply all pending write requests before processing the read without the overhead of a full write. This primitive is similar in idea to the flush primitive of ISIS。

可以简单认为sync操作等于原子的写+读。这样客户端的读操作一定能看到最新的写入操作。因为FIFO的客户端请求使得它看到了自己的写请求，而写请求又是线性的，于是之前的写请求一定也被看见。

Zookeeper的实现

//todo