MIT-6.824 (4)

MIT-6.824 分布式系统学习笔记（4）

参考资料：

• chaozh/MIT-6.824: Basic Sources for MIT 6.824 Distributed Systems Class (github.com)
• MIT6.824 (gitbook.io)
• 2020 MIT 6.824 分布式系统_bilibili

Lecture 08 ZooKeeper

线性一致

• 线性一致是特定的操作历史记录的特性。当观察到一系列不同时间的客户端请求和这些请求的响应（服务器应当能够通知请求完成，否则很难判断线性一致），需要判断这样的历史记录是不是线性的——线性一致的历史记录必须与请求的实际时间匹配，后来的请求都必须在先来的请求之后
• 如果能构建一个序列，同时满足：
  • 序列中的请求的顺序与实际时间匹配
  • 每个读请求看到的，都是序列中前一个写请求写入的值
  • 此时请求历史记录是线性的
• 可以合理的认为强一致与线性一致是一样的
• 对于整个请求历史记录，只存在一个序列，不同的客户端不能看见不同的序列，存储在系统中的数据演进过程必须相同
• 对于系统执行写请求，只能有一个顺序，所有客户端读到的数据的顺序，必须与系统执行写请求的顺序一致
• 线性一致系统，或者强一致系统不可能提供旧的数据——对于读请求，线性一致系统只能返回最近一次完成的写请求写入的值
• 服务器必须要有能力能够过滤出重复的请求——服务器根据请求的唯一号，或者其他的客户端信息来保存一个表，从而知道之前收到过这个请求并执行过——如果客户端有重传，并且要从客户端的角度来定义线性一致，则必须考虑此问题

ZooKeeper

• Raft实际是一个库（在大的多副本系统中使用Raft库），但不是一个可以直接交互的独立服务，要设计相应的应用程序来与Raft库交互
• ZooKeeper是一个独立、通用的服务，可以包装成一个任何人可以使用的独立服务，减轻构建分布式应用的难度——Zookeeper这类软件被认为是一个通用的协调服务
• 作为一个多副本系统，Zookeeper是一个容错的，通用的协调服务（General-Purpose Coordination Service）——通过多副本实现容错
• 性能分析：（下面将会把Zookeeper看成一个类似于Raft的多副本系统，但Zookeeper实际运行在Zab之上）
  • 大量的客户端和一个Leader，Leader有两层：上面一层是和客户端交互的ZooKeeper，下面是与Raft类似的管理多副本的Zab
  • Zab维护Log（存放一系列客户端发送的操作）。每个副本服务器都有自己的Log，会将新的请求加到Log
  • 客户端发送一个请求，Zab层会将请求的拷贝发送给其他的副本，其他副本将请求追加给Log
  • 当加入更多的服务器时，Leader是一个性能瓶颈
  • 最简单的提高性能的方法是，所有的写请求通过Leader下发——实际生活中大量的负载是读请求，因此可以将写请求发给Leader，将读请求发给任意一个副本
    • 问题是，如果直接将客户端的请求发送给副本，不一定能得到正确结果
    • ZooKeeper是一个类似于Raft的系统，如果客户端将请求发送给一个随机的副本，副本中肯定有一份Log的拷贝，但是没有理由相信除了Leader以外的任何一个副本的数据是最新（up to date）的，因为副本可能不在Leader所在的过半服务器中
    • 尽管在性能上可以有很大提升，但不能将读请求发送给副本——线性一致的要求下，不能用副本来服务客户端
• 但是，ZooKeeper的读性能仍然随着服务器数量的增加而显著的增加
• ZooKeeper并不要求返回最新的写入数据。ZooKeeper不提供线性一致的读，不为读请求提供最新的数据——不提供强一致性
• ZooKeeper允许客户端将读请求发送给任意副本，并由副本根据自己的状态响应读请求

一致保证

• ZooKeeper的一致性保证（帮助理解应用程序运行时会发生什么）：
  • 写请求线性一致：一次只执行一个写请求，并且符合写请求的实际时间；ZooKeeper不是一个严格的读写系统
  • 任何一个客户端的请求，都会按照客户端指定的顺序来执行，称之为FIFO（First In First Out）客户端序列
    • 一个特定的客户端发送了一个写请求之后是一个读请求或者任意请求，所有的写请求会以这个客户端发送的相对顺序，加入到所有客户端的写请求中（满足保证1），因此
    • 所以如果一个客户端先完成写操作1，再完成写操作2，最后是写操作3，最终整体的写请求序列中，写请求1、2、3也会顺序出现——这是服务端要考虑的问题
    • 为了让Leader按客户端的顺序执行写请求，客户端会对写请求打上序号，表明执行顺序
    • 对于读请求，客户端会发送多个读请求，每个读请求都可以在Log的一个点观察到对应的状态。后续的读请求必须要在不早于当前读请求对应的Log点执行，即一个客户端发起两个读请求，第一个读请求在Log的index1执行，第二个读请求只允许在index1及更后执行
      • 即使客户端第二个读请求可能切换到一个新副本，客户端在新副本的读请求，必须在第一个读请求的index或者之后的点执行
      • 每个Log条目都会被Leader打上zxid标签，是Log对应的条目号。一个副本回复读请求时，回复会带上zxid，对应的是Log中执行点的前一条Log条目号。客户端记住最高的zxid，发出一个请求到一个相同或者不同的副本时，会在请求中附加最高的zxid
      • 如果副本发现zxid不符（副本log长度不够），要么副本阻塞对于客户端的响应，要么副本拒绝客户端的读请求，让其切换询问对象或延迟再问。如果副本连上Leader，它会更新最新的Log，就可以响应读请求了
    • FIFO客户端请求序列对一个客户端的所有读写请求生效。如果发送写请求给Leader，Leader没有处理完时又发送一个读请求给某个副本，读请求需要暂缓——对于某个特定的客户端，读写请求是线性一致的——当客户端发送一个读请求说，上一次发送的写请求对应zxid是多少，副本必须等到自己看到对应zxid的写请求再执行读请求

同步操作（sync）

• 有一个弥补（非严格线性一致）的方法：sync
• sync是ZooKeeper的一个操作类型，本质上是一个写请求。假设客户端知道服务端写了些数据，想读出ZooKeeper中最新的数据，此时可以发送一个sync请求（效果相当于一个写请求），出现在所有副本的Log中
• 接着，发送读请求时客户端告诉副本，在看到该客户端上一次的sync请求前，不要返回读请求——此时符合FIFO客户端请求序列，因为读请求必须至少要看到同一个客户端前一个写请求对应的状态
• 这是一个代价很高的操作：将一个廉价的读操作转换成了一个耗费Leader时间的sync操作

就绪文件（Ready file/znode）

• file对应的是论文里的znode，ZooKeeper以文件目录的形式管理数据，因此每一个数据点可以认为是一个file
• 假设一个分布式系统，有一个Master节点，Master节点在Zookeeper维护一个配置，这个配置对应一些file（znode）。配置描述了有关分布式系统的一些信息，如worker的IP地址。Master更新配置，同时大量的客户端需要读取相应的配置，并且需要在配置更新时被通知——要求有原子效果的更新，此时客户端才能读出完整更新的配置，而非更新一半的配置——这是使用Zookeeper管理配置文件的一个经典场景
• 论文2.3节表明：
  • 对于写请求：
    • 假设发出一系列写请求来更新配置，分布式系统中的Master会以该顺序执行写请求
    • 此时需要一些Ready file（以Ready为名字的file）。如果Ready file存在，则允许读相应配置，否则说明配置正在更新
    • 如果Master要更新配置，首先要删除Ready file，然后更新各个保存了配置的ZooKeeper file（znode）。当所有组成配置的file更新完成，Master再次创建Ready file
    • 为了确保写的顺序，Master为这些请求打上tag，ZooKeeper Leader要按照顺序将写请求append到多副本的Log，副本按照顺序执行请求，也会删除自己的Ready file，最后再次创建自己的Ready file
  • 对于读请求：
    • 假设有worker节点要读取当前配置，并且Ready file存在
    • 需要读取配置的客户端，首先通过调用exist来判断Ready file是否存在，存在则读取组成配置的第一个file。但是之后在读第二个file时，Master可能正在更新配置，客户端读到的是一个由旧配置的一部分和新配置的一部分共同组成的配置——这是一个严重的不一致问题
    • ZooKeeper的API中，客户端调用时不仅会查询Ready file是否存在，还会建立针对这个Ready file的watch，如果Ready file有变更，例如被删除了，或者之前不存在然后被创建，副本会给客户端发送一个通知——上例中，Ready file被删除，副本会给客户端发送一个通知——因此副本确保Ready file有变化时，在合适时机返回一个通知，并且副本会先发通知，再处理触发了watch的请求（例如删除Ready file）
    • 因此，当客户端读取配置读了一半，如果收到Ready file删除的通知，可以放弃本次读，重新读

ZooKeeper API

• ZooKeeper实现了mini-transaction

• ZooKeeper的特点：

  • ZooKeeper基于（类似于）Raft框架
  • 读请求可以由任何副本响应，可能返回旧数据
  • ZooKeeper确保一次只处理一个写请求，所有副本看到一致的写请求顺序——一致的写请求顺序保证状态一致
  • 一个客户端发出的所有读写请求会按照客户端发出的顺序执行
  • 对于一个客户端的连续请求，后来的请求看到较于前一个请求相同、或更晚的状态

• ZooKeeper的目标：

  • 可以实现VMware FT所需要的Test-and-Set服务
    • Test-and-Set服务用于主备切换
    • Zookeeper能够提供工具来实现一个容错的、完全满足VMware FT要求的Test-and-Set服务
  • 可以用ZooKeeper发布其他服务器使用的配置信息，如向Worker节点发布当前Master的IP地址
  • 选举Master
    • 替换故障的Master
    • 如果新Master需要保持最新状态，例如GFS的Master需要存储“一个特定的Chunk的Primary节点在哪”，此时GFS的Master节点可以存储该信息于ZooKeeper，旧Master崩溃后新Master可以直接从ZooKeeper读取旧Master的状态
  • 对于一个类似于MapReduce的系统
    • Worker节点可以通过在ZooKeeper中创建小文件来注册自己
    • Master节点可以向ZooKeeper写入具体的工作，Worker节点从ZooKeeper一个个的取出工作，执行，完成后再删除工作

• ZooKeeper的API像一个文件系统（但不是一个实际的文件系统，不能mount文件、运行ls和cat这样的命令）

  • 有一个层级化的目录结构、一个根目录（root）
  • 每个应用程序有自己的子目录：应用程序1的文件保存在APP1目录下，应用程序2的文件保存在APP2目录下
  • ZooKeeper可能要被许多完全不相关的服务共享使用，因此需要一个命名系统区分不同服务的信息（后三节会介绍几个例子）
  • 通过RPC向ZooKeeper请求数据时，可以直接指定/APP2/X
  • 文件和目录都被称为znodes。ZooKeeper有3种类型的znode
    • Regular znodes：一旦创建就永久存在，除非主动删除
    • Ephemeral znodes：
      • ZooKeeper认为创建它的客户端挂了，会删除该类znodes
      • 此类znodes与客户端会话绑定，因此客户端需要发送心跳给ZooKeeper
    • Sequential znodes：
      • 当想要以特定的名字创建一个文件，ZooKeeper实际上创建的文件名是指定的文件名+一个数字
      • 当多个客户端同时创建Sequential文件时，ZooKeeper确保数字不重合，同时也确保数字总是递增的

• ZooKeeper以RPC的方式暴露以下API

  • CREATE(PATH，DATA，FLAG)：
    • 入参：文件的全路径名PATH，数据DATA，表明znode类型的FLAG
    • 如果返回为yes，说明文件之前不存在；如果返回为no或错误，说明文件之前已经存在
    • 如果有多个客户端同时创建同一个文件，实际成功创建文件（获得了锁）的客户端可以通过返回值得知自己获得锁
  • DELETE(PATH，VERSION)：
    • 入参：文件的全路径名PATH，版本号VERSION
    • 每一个znode都有表示当前版本号的version，znode有更新时version也会增加
    • delete和一些update操作，可以增加version参数，表明当且仅当znode当前版本号与version参数相同，才执行操作
    • 当多个客户端同时要做相同的操作时，参数version会很有用
  • EXIST(PATH，WATCH)：
    • 入参：文件的全路径名PATH，参数WATCH
    • 指定watch可以监听对应文件的变化
    • 不论文件是否存在都可以设置watch为true，此时如果文件有任何变更（创建，删除，修改等）都会通知到客户端
    • 判断文件是否存在和watch文件的变化，在ZooKeeper内是原子操作
      ——当调用exist并传入watch为true时，不可能判断和建立watch通道之间，插入创建文件操作
  • GETDATA(PATH，WATCH)：
    • 入参：文件的全路径名PATH，WATCH标志位
    • watch监听的是文件内容的变化
  • SETDATA(PATH，DATA，VERSION)
    • 入参：文件的全路径名PATH，数据DATA，版本号VERSION
    • 若传入version，当且仅当文件版本号与version一致时才更新文件
  • LIST(PATH)：
    • 入参：目录的路径名
    • 返回路径下的所有文件

使用ZooKeeper实现计数器

• 假设ZooKeeper中有一个文件存储统计数字（如，统计客户端的请求次数）

• （Lab3中，GET不允许返回旧的数据）

• 将代码放在一个循环里，因为不一定能在第一次执行的时候成功。调用GETDATA来获取当前计数器的值，X，V = GETDATA(“f”)，文件名假设为f，返回数值X和版本号V，写入数据SETDATA("f", X + 1, V)，只有当实际真实的版本号等于V的时候，才更新数据（如果没有其他客户端在更新“f”对应的数据，则直接获得结果，否则其他客户端在更改数据的时候会变更版本号，此时获得的版本号就不是最新的）

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

• 此例子即为mini-transaction——一旦操作成功，对计数器达成了“读-更改-写”的原子操作，即“读-更改-写”操作不受其他任何客户端的干扰——并不是一个完整的数据库事务（transaction）。一个真正的数据库可以使用完整的通用的事务，可以指定事务的开始，执行任意的数据读写，之后结束事务，数据库将所有的操作作为一个原子事务提交。ZooKeeper这里的事务并不通用，但也提供了原子性，所以称为mini-transaction

• 该方法可以其他功能，如VMware FT所需要的Test-and-Set服务

使用ZooKeeper实现非扩展锁

• 锁常见的操作是Aquire Lock，伪代码：

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

  • 第2行尝试创建锁文件，锁文件创建成功，表明获得了锁，直接RETURN。如果锁文件创建失败，需要等待锁释放（锁会以删除文件的形式释放）
  • 通过EXIST函数加watch=TRUE监测文件的删除
  • 第4行等待文件删除的watch通知

• 如果两个客户端同时创建锁文件，ZooKeeper Leader以某种顺序一次只执行一个请求。锁文件有可能在调用EXIST之前就释放了（因此EXIST前面要加一个IF），此时又回到循环的最开始，重新尝试获得锁

• 类似的，如果正好在调用EXIST的时候，或者副本在处理EXIST的过程中锁释放，此时EXIST有两种可能：要么在DELETE之前处理，此时副本会认为锁还存在；要么EXIST在DELETE请求之后处理，这时文件不存在，回到循环的最开始

• 本例子和上一个计数器例子，都受羊群效应（Herd Effect）的影响：当有1000个客户端同时增加计数器时，复杂度是$O(n^2)O(n2)$ ，本节的锁同理——每次锁文件的释放，所有剩下的客户端都会收到WATCH通知，会再次尝试创建锁文件，因此CREATE对应的RPC总数与1000的平方成正比

使用ZooKeeper实现可扩展锁

• ZooKeeper可以设计另一个锁，避免羊群效应，使得锁释放时另一个客户端获得锁的复杂度是$O(1)O(1) $——不再使用一个单独的锁文件，而是创建Sequential文件

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

  • 第1行创建Sequential文件，如果是以“f”开头的第27个Sequential文件，实际会创建类似“f27”的文件——获得一个全局唯一序列号（如27），并且后续的序号是递增的

  • 第3行通过LIST列出所有以“f”开头的文件（Sequential文件）

  • 第4行，现存Sequential文件的序列号都不小于第1行得到的序列号，表明获得锁

  • 这个锁方案中，会使用Sequential序列号向客户端分发锁，存在更低序列号的Sequential文件时，要等待响应客户端释放锁（删除文件）

  • 第5行调用EXIST并设置WATCH，等待比自己序列号更小的一个锁文件删除

• ZooKeeper实现的锁没有提供类似于线程锁的原子性保证

• 在一个分布式系统中，可以这样使用Zookeeper实现的锁

  • 每一个获得锁的客户端，需要清理之前锁持有者因为故障残留的数据（确认之前的客户端是否故障了，如果故障，该怎么修复数据），而对于线程锁不需要考虑这个问题
  • 可以用这里的代码实现选举Master

Lecture 09 More Replication, CRAQ

论文CRAQ（Chain Replication with Apportioned Queries）

链复制（Chain Replication）

• CRAQ通过复制实现容错，通过以链复制API请求的方式，提供了和Raft不同的属性
• CRAQ改进了链式复制（Chain Replication）
  • CRAQ采用的方式与Zookeeper相似，通过将读请求分发到任意副本去执行，来提升读请求的吞吐量
  • 在任意副本上执行读请求的前提下，还可以保证线性一致性（Linearizability）
• Chain Replication系统
  • 有多个副本，想确保它们看到相同顺序的写请求（此时副本的状态能保持一致）——Raft的思想一致，但拓扑结构和Raft不同
  • 一些服务器按照链排列，第一个服务器为HEAD，最后一个为TAIL
  • 客户端发送一个写请求时，总是发送给HEAD，HEAD根据写请求更新本地数据，再将写请求通过链向下一个服务器传递，当写请求到达TAIL，TAIL回复客户端表明写请求完成
  • 客户端想要读数据时，将读请求发往TAIL，TAIL直接根据当前状态回复读请求
  • Chain Replication线性一致的，整个系统就像只有TAIL一台服务器一样
  • 除非写请求到达了TAIL，否则一个写请求是不会commit，也不会向客户端回复确认，也不能将数据通过读请求暴露出来

链复制的故障恢复

• Chain Replication出现故障时状态是相对有限的，并且不同的副本之间不会发生各种不同步，因为写请求的传播模式非常规律
  • 要么committed的写请求被所有服务器看到
  • 要么故障服务器之前的服务器都看到写请求，之后的服务器都没看到
• Chain Replication的故障恢复相对更简单
  • HEAD出现故障，下一个节点可以接手成为新的HEAD
    • 对于已经发给第二个节点的写请求，会持续转发直到commit
    • 对于刚发送到HEAD的写请求，HEAD故障时不必做任何事情，或许客户端会重发这个写请求，但是并不是该系统要处理的问题
  • TAIL出现故障，TAIL的前一个节点可以接手成为新的TAIL
  • 中间节点出现故障，将故障节点从链中移除，故障节点的前一个节点或许需要重发最近的一些写请求给它的新后继节点
• Chain Replication与Raft的差别：
  • 对于Raft，如果有一个Leader和一些Follower，Leader需要将数据发送给所有的Follower；Chain Replication中HEAD只需要将写请求发送到一个其他节点。所以Raft Leader的负担会比Chain Replication中HEAD的负担更高，客户端请求变多时Raft Leader成为瓶颈，同等条件下Chain Replication的HEAD的瓶颈来的更晚
  • Raft中读请求同样需要在Raft Leader中处理——Raft Leader看到所有的请求，Chain Replication每一个节点可以看到写请求，但只有TAIL看到读请求
  • Chain Replication故障恢复更简单

链复制的配置管理器

• 问题：HEAD认为第二个节点挂了，第二个节点实际上还活着，它认为HEAD挂了——Chain Replication不能抵御网络分区，也不能抵御脑裂
• 有一个外部权威（External Authority）决定哪个节点是活的，确保所有参与者都认可由哪些节点组成一条链，该外部权威称为Configuration Manager
• Configuration Manager监测节点存活性，一旦认为一个节点挂了，会生成并送出一个新的配置，配置中描述了链的新定义（链中所有的节点，HEAD和TAIL），所有节点会遵从新的配置内容，从而不存在分歧，此时只有一个角色（Configuration Manager）做决定，因此可以解决脑裂
• Configuration Manager通常基于Raft或者Paxos。CRAQ的场景下，会基于ZooKeeper（ZooKeeper本身又是类似Raft的方案）
• 数据中心内的设置通常是，有一个基于Raft或者Paxos的Configuration Manager，通过一系列的配置更新通知，Configuration Manager将数据中心内的服务器分成多个链，Configuration Manager通告给所有参与者整个链的信息
• 此时假如第二个节点挂了，在收到新的配置之前HEAD需要不停尝试重发请求。节点自己不允许决定谁是活的，谁挂了