Zookeeper 提出了什么问题

1. 能够将 coordination 作为一种通用服务去提供吗，可以的话，API 应该是怎么样的，其他分布式程序应该怎么去使用它？
2. 我们有 N 个 replica server，能从这个 N 个 server 中获得 N 倍性能吗？

将 Zookeer 视为基于 Raft 的 service

只不过 ZooKeeper 使用的是 zab 协议，为 ZooKeeper 专门设计的一种支持崩溃恢复的一致性协议

当我们添加更多的 server 时候，replication arrangement 是否变得更快

replica 越多，写入的速度就越慢
leader 必须将每次写入发送给越来越多的 server

可以让 follower 提供只读服务，这样 leader 压力就小很多

可能会产生 log 与 leader 不一致的情况，导致 client 读取的数据不对，甚至是产生 “倒退现象”，client 先从 up-to-date replica 读，再从 logging replica 读。这个就不可能是 Linearizability
Raft 和 Lab3 不会出现这种情况，因为 follower 不提供只读服务

Zookeeper 怎么处理这个

在性能和强一致性之间保持平衡，不提供强一致性，允许从 replica 读取数据（写只能是写 leader），但是在其他方面则是保证了顺序。

Ordering guarantees (Section 2.3)

Linearizable writes

1. client 发送写入命令到 leader
2. leader 选择一个顺序，编号为 zxid
3. 将该命令发送给 replica，所以 replica 按照 zxid 顺序去执行。
4. 即使是并发写操作，也会保证按照某个顺序去一一执行。

FIFO client order

client 指定 write 和 read 操作的执行顺序

• write：按照 client 指定的 write order，section2.3 ready file
• read：
  • 每次读都在写入顺序中的某一个点开始执行
  • client 连续读操作，每次读的顺序保证是非递减，这一次读不会读到前面的内容
  • 如果执行读操作的时候，replica 挂掉了，client 需要将它的读请求发送给另外一个 replica，这时候依旧会保证 FIFO client order（非递减）。
  • 工作原理是每个 log entry 都有一个 zxid，当一个 replica 响应 client 的读请求时会携带上一个 log entry 的 zxid（这里的上一个相对于是下一个读请求），client 会记住最新数据的 zxid，每次请求会携带上 zxid。
  • 如果另外一个 replica 也没有最新 zxid 对应的下一个 log，replica 可能会延迟对读请求回复直到 leader 同步了 log 或者是拒绝这个请求，或者是其他。
• 将 write 发送给 leader，但是 leader 还没有同步给 replica，这时候 read replica 会被 delay（因为指定了命令的执行顺序）或者 sync ()
• 只是保证了一个 client 的 FIFO order（同一个 clien 的 Linearizability），即同一个 client 的命令可以保证下一次读到的是上一次的写。但是对于不同的 client 来讲，client2 不一定能准确读到刚刚 client1 写的数据

尽管 Zookeeper 不是 Linearizability，但是在别的方面还是有用的

• sync () 能够让后续不同的 client 看到之前 client 写入的值。只有该数据在整个系统中处于写状态，不允许其他 client 读到。想要读取最新数据，需要 sync 再读。缺点是增加了 leader 的处理时间，不这样做的话就不是 linearizable
• 场景 1 ready file：master 在 Zookeeper 中维护了一个配置文件（描述了分布系统的东西，比如 worker ip，master 信息等），里面有一堆文件（可以实现原子更新效果），master 会去更新配置文件，在更新的过程中 worker 不能查看配置，只能看到完全更新后的配置。
  • 正常的操作序列，虽然不是完全 linearizable（只有写），但是读只能往前读，所以达了类似 linearizable 的效果，提高了性能：
• 可能会出现的问题：
  
  读 f1 的时候，执行了写操作，导致读到的 f2 不是原来应该读的
  Zookeeper 使用 watch 事件去解决，当调用 exists 的时候，除了判断 file 是否存在，还在这个文件上面设置了 watch 事件（replicate 会创建 watch table，文件修改之前查看 watch table)，当这个文件被修改时候 replica 会在一个相对正确的时间点通知 client，即会在读操作执行之前。
  
  当 replicate crash 时候，对应的 watch table 也会没有，client 切换到新的 replicate 读的时候就不会有对应的 watch table。但是 client 会在合适的时间收到 replica 崩溃的通知。

• 当 leader failed 时候 leader 必须保存 client 的 write order（？
• replicate 需要保障 client 的读取顺序按照 zxid 顺序
• client 必须跟踪它已读取的最高 zxid

提高性能的技巧

• client 可以让 leader 发送异步写入，不必等待
• leader 可以批处理请求以减少磁盘和网络开销

Coordination as a service 是怎么样的（Zookeeper 有什么用）

VMware-FT’s test-and-set server

• 要求：一个 replica 无法和其他 replica 通信，则获取 t-a-s lock（test-and-set lock），成为 sole server。必须是唯一的以避免存在两个 primary（如果出现 network partition），必须是 fault-tolerant。
• Zookeeper 提供了工具，可以写出 fault-tolerant test-and-set 服务

Config info

通过 Zookeeper 发布信息给其他服务使用，比如可以将一组 worker 中作为当前 master 的那个 ip 存放在 Zookeeper

Mater elect

在 test-and-set server 中有体现，master 可以把 state 存放在 Zookeeper，如果 master crash，选出一个新的 maser 代替它，新的 master 可以从 Zookeeper 中读取旧 master 的状态。

MapReduce

worker 可以注册到 Zookeeper 中，master 会在里面记录着 worker 的任务，worker 会从 Zookeeper 中将任务一件件拿出来，完成后就会移除掉。

Zookeeper API

• a file-system-like tree of znodes
  
  each znode has a version number
  示例：将一组机器和哪个机器是 primary 的信息存放在 znodes
• znode 的分类：regular、ephemeral、sequential（file name + seqno）

Operations on znodes

flags：znode type

• create (path, data, flags)：互斥的（exclusive），只有第一次创建才能成功
• delete(path, version)：if znode.version = version, then delete
• exists (path, watch)：设置 watch 后，当 path 创建或者删除后会发送一个通知。原子操作，两个 write 之间的 watch 不会有任何操作，znode 完成改变之前不会收到通知
• getData(path, watch)
• setData(path, data, version)：if znode.version = version, then update
• getChildren(path, watch)
• sync()

Zookeeper api 可以很好地实现同步

• exclusive file creation：并发创建只有一个能返回成功
• getData ()/setData (x, version) 支持 mini-transactions
• 当 client fail 的时候，session 会自动执行操作，例如失败时 release lock
• sequential znode file 可用于并发创建的同时又能指定顺序
• watch

znode 中的数字递增

mini-transaction 保障 atomic read-modify-write

while true:
    x, v := getData("f")
    if setData(x + 1, version=v):
      break

Simple Locks (Section 2.4)

acquire():
    while true:
      if create("f", ephemeral=true), success
      if exists("f", watch=true)
        wait for notification
release():
	delete("f")

在 replica exists 执行过程中，lock 文件被释放掉，会发生什么情况。exists 是个只读请求，可能会发生在 replica，与此同时，可能会有别的 client 在执行 delete 操作。exists 会在两个 write 请求之间执行。

在完成执行成功的时间点，replica 会看到 lock 文件依旧存在，replica 会插入 watch 信息到 watch table，然后才执行 delete 操作。所以当 delete 操作执行时，确保 watch 请求会在 replica 的 watch table 中，并且 replica 会给 client 发送通知。
每次释放锁，所有剩下的 client 都会收到 watch 通知，都会返回第一步发送 create 请求，所以时间复杂度基本上还是 N^2。这个就是大量等待 client 引起的 Herd Effect。

Locks without Herd Effect(scalable lock)

1. create a "sequential" file
2. list files
3. if no lower-numbered, lock is acquired!
4. if exists(next-lower-numbered, watch=true)
5.   wait for event...
6. goto 2

• 大量 client 请求的话会按顺序产生很多个文件
• 这些文件代表着获得了锁，如果释放了锁则需要删除文件
• 为什么需要 list files，因为前一个 client 可能会 failed，导致文件被自动删除，这时候就需要关注上一个的上一个的文件是否存在，而不能只是关注上一个文件（相对于 client 创建的文件序号，比如 client 创建了 f500，不能只是关注 f499）是否存在。
• 如何解决 Herd Effect：创建了第 501 个文件的 client 在等待第 500 个文件被释放，创建了第 500 个文件的 client 等待第 499 个文件被释放，每个 client 都在等待文件被释放。当释放锁的时候，一个 client 就会收到通知，第三步就会成立，那么这个 client 就获得了锁。所以一个 client 的开销只有几次 RPC 请求的开销，等待锁也可以是异步等待，在另外一个线程通过某种方式查看 Zookeeper 的状态。其实就相等于锁队列，后一个 client 都在等待着前面的 client 释放。
  • 如果 client 持有锁的时候，但是它中途操作失败，那么锁会立即释放，导致下一个 client 获得锁的时候看到的数据不是正确的数据。所以这些锁和语言带的线程锁相比，它们无法提供相同的原子性保证。
    • 基本上使用这种锁有两种考虑：每个获取到锁的 client 都应该准备好遇到上一个失败这种情况时的操作（比如推断出是在哪个地方出现错误）；要么就是保护的数据不是很重要，比如 MapReduce 中的 worker 失败后，释放锁后下一个 worker 执行时看到任务没有完成，重新执行即可。