阅读论文 Frangipani，参考 FAQ，note。

概述

Frangipani 是一个分布式文件系统，由 Petal 分布式存储服务和多个 Frangipani 服务器组成，Frangipani 服务器共享 Petal 提供的单个虚拟磁盘抽象，同时使用分布式锁保证缓存一致性。

实现

预写日志

每个 Frangipani 服务器都会使用预写日志记录系统元数据的变化（不记录文件数据），只有当日志持久化到 Petal 之后，才能修改系统的元数据。日志首先会按顺序存放在服务器内存的循环缓冲区中，然后定期刷新到 Petal。使用日志记录元数据的变化，可以避免服务器故障时元数据的部分更新导致文件系统结构被破坏（产生不一致），从而可以避免运行 fsck 一致性检查程序，实现快速恢复。

日志由若干大小为 512 字节的日志块组成，每个日志块都有一个单调递增的序列号。论文表示序列号作用是在故障恢复时检测日志的末尾，即使磁盘乱序写入数据。元数据由若干大小为 512 字节的元数据块组成，每个元数据块都有一个单调递增的版本号。日志块也会包含其所修改元数据块的版本号，只有日志块中的版本号大于元数据块的版本号时，才能应用日志。从而可以避免服务器故障恢复时，旧日志覆盖新版本的元数据，以及重复应用已经应用的日志。512 字节的日志块和元数据块实际上对应一个扇区，扇区的读写保证是原子的。

PS：论文提到元数据块被释放然后重用于文件数据导致版本号消失的问题，然后说明限制释放的元数据块仅被新的元数据块重用可以解决该问题。此处所说的元数据块应该是指扇区，所有才会释放和重用，也就是说版本号实际上是和元数据块所在的扇区绑定，而和元数据是什么无关。而且，之所以版本号消失会有问题，是因为日志块记录的是所修改元数据块的扇区位置。这种设计有点奇怪，日志块以及版本号不和修改的元数据关联，而是和扇区关联。

分布式锁

锁服务使用 Paxos 进行容错，为文件系统提供读写锁。当锁服务检测到冲突的锁请求时，会要求当前锁的持有者释放或降级锁，以消除冲突。读写锁允许 Frangipani 服务器从磁盘获取数据并将其缓存。在释放读写锁前，服务器会使缓存无效，从而保证缓存一致性。在释放或降级写锁前，服务器必须将脏数据写入磁盘（包括文件数据）。磁盘被划分为若干逻辑段，每个段都有一个锁，每个日志、文件、目录和符号链接都是一个段。每个文件使用一个锁，适合很少并发写的工作负载，其他负载可能需要使用更细粒度的锁。

锁具有粘性，也就是说 Frangipani 服务器获取锁之后不会主动释放，除非锁服务要求其释放。当挂载 Frangipani 文件系统时，Frangipani 服务器会调用 clerk 模块，该模块会连接到锁服务，获取租约并且在本地打开一个锁表。当文件系统被卸载时，clerk 会关闭锁表。clerk 和锁服务使用异步消息进行通信，有四种消息类型：request、grant、revoke 和 release。

故障处理

当 Frangipani 服务器的租约由于没有续约而过期时，锁服务会认为该服务器故障，此时需要一种机制来释放故障服务器持有的锁。锁服务会在另一个 Frangipani 服务器上启动恢复进程，新服务器会获取租约和故障服务器日志的锁，然后按顺序应用未执行的日志，最后释放（release）所有锁以及释放（free）日志。如果是由于网络分区故障而没有续约，租约过期的 Frangipani 服务器会主动丢弃其所有锁和缓存数据。如果缓存中存在脏数据，则服务器会向用户程序报告错误，将问题交给用户处理。

如果租约在服务器向 Petal 发送写入请求之后到达之前过期，则会产生问题，因为此时锁可能已经被授予故障恢复服务器。论文提到可以为每个写入请求添加过期时间戳，如果请求到达 Petal 的时间戳大于请求中的时间戳，则拒绝该请求。或者将锁服务和 Petal 集成，服务器为写入请求添加租约标识符，然后 Petal 可以判断租约是否过期。

问题

Q：日志序列号的作用有点奇怪，为什么磁盘要乱序写入数据？

Q：日志只会记录元数据，那么有可能只执行元数据更改，而丢失文件数据？

A：该语义符合标准的本地 Unix 文件系统，崩溃之前的写入可能会丢失。应用程序可以使用 fsync 系统调用，强制将数据立即刷新到磁盘。

总结

预写日志存储在 Petal 提供的共享虚拟磁盘上，使得任何服务器都可以使用故障服务器的日志进行恢复。多个日志使得恢复过程变得复杂，需要使用版本号机制避免异常。分布式锁保证服务器之间的缓存一致性。Frangipani 服务器运行在用户侧，负责和共享磁盘通信，该设计要求用户是可信的。该系统使用粗粒度的锁定，一个文件对应一个锁，所以不适用于经常并发写入相同文件的负载。论文的性能测试我没有太多时间看，总结时也忽略了一些我认为不是很重要的细节。

阅读论文 Chain Replication，参考 note。

概述

链式复制是一种容错复制方式，可以保证高性能、高可用和强一致性（可线性化）。客户端的请求都以原子的方式执行，查询请求直接发送到 tail，更新请求发送到 head，然后沿着链传递到 tail。在没有故障的情况下，可线性化保证源于以下两点：只有 tail 会响应客户端的请求，以及更新操作只会在 head 计算一次，从而可以避免冗余计算和非确定性操作带来的一致性问题。

实现

基本概念

对象由 \(objID\) 唯一标识，\(Hist_{objID}\) 表示该对象上已执行的请求，\(Pending_{objID}\) 表示该对象上待执行的请求。对于链式复制来说，客户端视图中的 \(Hist_{objID}\) 被定义为 tail 存储的 \(Hist_{objID}\)，\(Pending_{objID}\) 被定义为任何服务器接收到的、没有被 tail 执行的客户端请求。注意，这两个状态都是对象的客户端视图，而不是实际存储在服务器中的数据。此外，论文只是为方便论证才将对象状态描述为 \(Hist_{objID}\)，实际的状态应该是对象的当前值。

故障检测和恢复

链式复制使用额外的服务来检测故障，重新配置链，通知客户端链头和链尾对应的服务器。论文称该服务为 master，使用复制进行容错，使用 Paxos 维持多个 master 副本之间的一致性。可以将其视为类似 ZooKeeper 的协调服务。虽然论文没有提及，不过检测故障通常是使用定时心跳。

链头故障

master 直接将 head 的下一个节点作为新的 head，然后通知客户端。所有旧 head 接收而未转发给后继的请求最终都会超时，然后客户端会重试。该过程相当于执行 T2 转移。

链尾故障

master 直接将 tail 的上一个节点作为新的 tail，然后通知客户端。因为更新是从前往后传播的，所以上一个节点的视图至少和旧 tail 的视图一样新，不会影响一致性。该过程相当于执行 T3 转移。

中间故障

master 会修改故障节点的前驱和后继的指针，从而将故障节点从链中删除。但是，如果前驱转发更新请求到故障节点，而故障节点没有将其转发至后继，那么前驱需要一种机制识别这部分请求，然后重新将其转发至后继。

每个服务器维护一个更新请求的已转发列表 \(Sent\)，当服务器将请求转发到后继时，会将该请求添加到列表中。当更新请求 \(r\) 转发到尾节点，并被尾节点处理时，尾节点会向前驱发送确认信息 \(ack( r)\)。收到 \(ack( r)\) 的服务器会将 \(r\) 从 \(Sent\) 列表中删除，同时将 \(ack( r)\) 转发到前驱。

当中间节点 \(S\) 故障，master 向后继 \(S^{+}\) 发送其新的前驱 \(S^{-}\)，\(S^{+}\) 会响应 master 确认消息，其中包含 \(S^{+}\) 收到的最后一个更新请求的序列号。然后 master 向前驱 \(S^{-}\) 发送其新的后继 \(S^{+}\) 和序列号，\(S^{-}\) 会将在 \(Sent_{S^{-}}\) 中且在序列号之后的请求转发到 \(S+\)，这部分请求就是故障节点 \(S\) 未转发至 \(S^{+}\) 的请求。该机制的关键在于保留已发送请求的列表，\(ack\) 的作用只是回收空间。

恢复冗余

发生故障的服务器会从链中删除，需要恢复冗余以保证容错。理论上，可以将新服务器添加到链中的任意位置。实践中，添加到链尾比较简单。master 会要求当前链尾 \(T\) 转发对象已执行的请求队列 \(Hist_{objID}^{T}\) 到新的链尾 \(T^{+}\)，在转发完成之前，依然是当前链尾 \(T\) 执行查询请求和前驱传来的更新请求，以及响应客户端。该过程中执行的更新请求同时会被添加到 \(Sent_{T}\)，该操作与 \(Sent_{T}\) 的定义不一致，之后会处理。当 \(Hist_{objID}^{T}=Hist_{objID}^{T^{+}}\oplus Sent_{T}\) 成立时，也就是转发开始时的 \(Hist_{objID}^{T}\) 都转发到 \(T^{+}\) 时，\(T^{+}\) 可以成为链尾。

过程如下：如果 master 收到上述不变式成立的通知，master 会通知 \(T\) 其不是链尾，之后 \(T\) 会将收到的查询请求转发到 \(T^{+}\)。然后 \(Sent_{T}\) 中的更新请求也会被转发到 \(T^{+}\)，转发完成之后，就符合 \(Sent_{T}\) 的定义，\(T\) 会通知 master 将 \(T^{+}\) 作为新的链尾。然后，master 会通知客户端新的链尾。PS：注意，此时 \(Sent^{T}\) 中的请求已经响应客户端。

对比主从复制

链式复制可以视为特殊的主从复制，头节点和尾节点共同充当主节点，其他节点作为从节点。相比传统的主从复制（指的是强一致性的主从复制）：

• 链式复制的查询，由链尾的服务器处理，不会被链中其他服务器的活动延迟。而主从复制的查询，主节点需要等待之前的更新被从节点确认，才能执行查询。PS：个人理解，指的应该是多客户端之间的更新和查询，单客户端是同步的，只有接收到上一个请求的响应才会发送下一个请求，否则链式复制是无法保证客户端的 FIFO 执行顺序。
• 链式复制串行传播更新，主从复制并行传播更新，所以链式复制的更新延迟更高，而且和链的长度成正比。

测试

根据论文中的模拟实验可以发现，链式复制比主从复制具有更高的读取性能，但是强一致性保证使得读写性能不能随着机器的数量线性扩展，不像 ZooKeeper。比较令人惊讶的是，在更新请求至少占总请求数的 15% 时，弱一致性保证的读取方案反而会降低系统的总吞吐量，因为在头节点的查询和更新会产生竞争。主从复制的吞吐量不会受复制因子的影响，而链式复制的更新是串行传播的，似乎吞吐量会随着链的长度增加而减少。但是，只要有足够多的更新请求，那么通过一个预热时间启动流水线，吞吐量可以恢复正常水平。

问题

Q：更新请求不是幂等的，如果响应丢失，客户端重试更新请求怎么办？

A：目前讨论的系统：GFS 的 primary chunkserver 重试会导致重复追加，我猜客户端重试大致也是如此；VM-FT 请求是否幂等取决于虚拟机中的应用程序；Raft 要求请求包含唯一标识，在状态机层去重；尽管 ZooKeeper 的事务是幂等的，但是请求不是幂等的，没有讨论如何处理；链式复制论文提到可以在重试之前，进行查询判断更新是否已经执行。总的来说，是否要求幂等是根据系统的实际使用场景而定的，课程中也提到，ZooKeeper 和链式复制也可以使用和 Raft 类似的方法去重，从而实现幂等。

Q：更新请求的延迟和链的长度成正比，那么超时时间会更长，如果请求丢失似乎需要更多等待？

Q：如果链头 \(S\) 和 master 发生网络分区故障，那么 \(S^{+}\) 会成为新链头，而此时 \(S^{+}\) 依然会收到旧链头 \(S\) 的转发。节点必然需要一种机制判断是否应该忽略请求，这可以通过简单的判断请求的来源是否是其前驱来实现。

Q：客户端在连接到服务器时，以及链头或链尾被改变时，master 需要通知客户端，如果客户端很多会有什么问题？

总结

课程提到，复制状态机有两种主要的实现方式，一种是使用共识算法复制所有操作，另一种是使用配置服务 + 主从复制，配置服务中的共识算法仅复制元数据，其他操作不需要使用共识算法复制。链式复制使用的是第二种方式，它需要利用额外的配置服务进行故障恢复，同时避免脑裂。链式复制概念简单，只有中间故障和恢复冗余稍微复杂一点。和共识算法不同，只要有一个服务器故障，就可能会导致读请求或写请求的短暂中断。论文在模拟实验中提到多链和对象放置策略，我认为论文的描述很模糊，所以没介绍。

阅读论文 ZooKeeper，参考 FAQ，note，官方文档，另一个课程的 note。

概述

ZooKeeper 是一个协调服务，用于协调分布式应用程序。它没有实现特定的协调原语（例如：配置、选举、锁），而是提供 API 供应用程序开发者使用，让开发者根据实际需要实现协调原语。ZooKeeper API 具有无等待特性，提供事件驱动机制。ZooKeeper 使用流水线（pipeline）架构处理请求，流水线自动支持客户端请求的 FIFO 执行顺序，从而允许客户端异步发送请求。ZooKeeper 没有实现可线性化一致性模型，它仅保证写操作的异步可线性化，以及读操作的写后读和单调读一致性（术语取自 DDIA），适合读多写少的工作负载。

会话

客户端在连接到服务器时建立一个会话（session），同时获得一个会话 ID。只要会话 ID 有效，应用程序就可以通过客户端调用 ZooKeeper API。客户端会定期向服务器发送心跳，如果服务器在超时时间内没有收到心跳，则服务器会结束会话。如果客户端当前连接的服务器故障，则客户端在会话 ID 过期之前自动尝试连接到另一台服务器。

PS：创建会话类似写操作，需要经过多数服务器同意，会话的状态也会使用日志持久化，它是一个全局会话。这也可以解释，为什么客户端可以使用同一个会话 ID 透明地切换到另一台服务器。由于开销较大，ZooKeeper 在之后的版本添加了本地会话功能，本地会话只能执行全局会话操作的子集，状态只在本地服务器维护。

数据模型和监视

ZooKeeper 以类似文件系统的树形结构在内存中存储协调数据（应用程序元数据），树中的数据节点被称为 znode，由路径名唯一标识。不同的应用程序在各自的子树中组织数据，存储在节点中的数据以原子的方式被读写。节点会维护一个统计结构，包含版本号、时间戳和事务 ID（zxid）等元数据。节点分为常规（Regular）和临时（Ephemeral）两种类型，客户端可以显示创建和删除节点。特别的，临时节点如果没有被显示删除，则在创建它们的会话终止时被自动删除，以及临时节点不能有子节点。

创建节点时，客户端可以设置顺序（sequential）标志，从而将一个计数值附加到该节点的路径末尾，同一父节点的子节点的计数值根据创建顺序单调递增。客户端可以为节点设置一次性监视（watch）标志，该标志在客户端连接的服务器本地维护。当监视触发时，服务器会向客户端发送一个监视事件，同时取消监视。有两种监视类型，监视数据和监视子节点。有四种监视事件，创建、删除、数据变化、子节点变化（不包含子节点的数据变化）。监视和会话相关，当会话结束时，监视也会被取消。ZooKeeper 保证设置监视的客户端在看到变化之前，会收到服务器的通知。会话事件也会触发监视，以便客户端知道监视事件可能延迟。

原语示例

客户端可以使用 ZooKeeper API 实现更强的原语，示例如下。更多示例（双重屏障、2PC、选举）可以查看官方文档。

配置管理

ZooKeeper 可用于分布式应用程序的配置管理，可以将配置存储在 znode 中。客户端从 znode 读取配置，同时设置监视标志。如果配置被更新，则客户端会收到通知，然后再次从该 znode 读取配置和设置监视标志。

群组成员

客户端可以创建一个 znode 表示一个群组，当进程以该群组的成员身份启动时，它会在该 znode 下创建一个临时子 znode。如果每个进程有一个唯一的名称，则将该标识作为子 znode 的名称，否则可以使用顺序标志，使其获得唯一的名称。进程可以将其元数据存储在该子 znode 中，例如地址和端口。如果进程终止，则临时节点会被自动删除。可以通过在 znode 上设置监视标志，从而监视群组成员的变化。

简单锁

可以将一个指定路径的 znode 作为锁，客户端可以创建临时 znode 来获取锁，其他客户端通过判断 znode 是否存在来判断是否能够获取锁，同时设置监视标志。当临时 znode 被显示或自动删除，则表示锁被释放。此时，等待锁的客户端将收到通知。但是该实现存在羊群效应（herd effect）：在锁被释放时，许多客户端会争抢同一个锁。

无羊群效应的简单锁

直觉上来说，将获取锁的请求按照 FIFO 的顺序排队处理，那么就可以避免羊群效应。可以使用顺序标志在指定父 znode 下创建临时子 znode，客户端通过判断其创建的临时 znode 是否是序号最小的，来判断它是否已获取锁。当客户端需要释放锁时，只需删除其创建的临时 znode。个人认为，有无羊群效应的简单锁，有点像是 notify_all 和 notify_one 的区别。

特别的，在代码实现时有一个陷阱，ZooKeeper 没有提供监视来通知当前 znode 的序号是否最小。在创建 znode 之后， 我们首先需要获取子 znode 列表，判断当前是否是最小的。如果不是，则可以在前一个节点上设置监视。但是，该监视触发并不意味着当前客户端已获取锁，因为有可能只是前一个客户端提前结束会话，此时仍存在更小的序号。

读写锁

实现细节

ZooKeeper 使用复制提供容错，使用原子广播协议（ZAB）保证多个副本之间的一致性。客户端仅连接到一个服务器发送请求，写请求会被转发给领导者，读请求读取本地数据库而不需要通过领导者。本地处理读请求使得读取性能可以随着服务器的数量增加而增加，而不会受限于单个领导者。复制数据库是一个内存数据库，当日志持久化到磁盘时，才会将日志应用到内存数据库，同时会定期为数据库生成快照。PS：类似 Raft，内存数据库实际上就是一个状态机。

ZooKeeper 使用 ZAB 保证写操作的可线性化，同时保证异步请求按照客户端 FIFO 的顺序执行，从而实现写操作的异步可线性化（A-linearizability）。当领导者收到写请求时，如果请求包含的版本号和目标 znode 的未来版本号匹配，就会将请求转换为事务。之所以要和未来版本号匹配，是因为可能存在尚未应用到数据库的事务。如果事务未提交（复制到大多数），则无法应用到数据库。ZooKeeper 保证事务是幂等的，〈transactionType, path, value, new-version〉。

ZooKeeper 使用的是模糊快照（fuzzy snapshot），因为允许在创建快照的过程中更改状态机，而且也不像 Raft 使用写时复制，所以快照不对应某个时刻的状态，故称为模糊快照。不过，由于事务的幂等性，重放相同的日志也没有关系。从日志的角度看，模糊快照并不对应一个连续的日志范围，可能是断断续续的。

客户端向服务器发送读写请求和心跳消息，得到的响应中会包含服务器的 zxid。如果客户端连接到新服务器，会检查客户端的 zxid 和新服务器的 zxid，确保新服务器满足客户端的单调读一致性。如果新服务器的视图更旧，客户端可以连接另一台服务器。

问题

Q：无等待（wait-free）是什么意思？

A：论文 Wait-Free Synchronization 进行了介绍，并发数据对象的无等待实现可以保证，任何进程都能在有限步中完成任何操作，而不论其他进程的执行速度如何。个人认为这个定义有点抽象，无等待还有一个层次结构和共识数。类似的术语还有无锁、无障碍、无阻塞。FAQ 提供了一个简单的解释，为什么 ZooKeeper 是无等待的，因为客户端调用 API 不会被其他客户端阻塞，ZooKeeper 没有使用锁来阻塞调用。

Q：为何流水线自动支持客户端请求的 FIFO 执行顺序？异步请求为何能提高性能？

A：我的理解是 TCP 可以保证客户端请求的 FIFO 到达顺序。流水线将一个处理过程分解为多个组件，能够充分利用系统的资源。但流水线依然是一个顺序的处理过程，一般就是按照到达顺序处理的，所以能够自动支持 FIFO 执行顺序。异步请求能提高性能是流水线的特性，如果同步发送请求，流水线中的很多组件会处于空闲状态。

FAQ 中有问到 ZooKeeper 如何实现异步请求的 FIFO 执行顺序，按照论文的逻辑，这个问题就不对。论文首先说流水线支持 FIFO 执行顺序，然后推出客户端可以发送异步请求。从而我觉得，FAQ 的答案也不对。FAQ 对流水线的解释也有问题，他把流水线解释为批处理。

Q：如何实现读操作的写后读和单调读一致性？

A：写后读一致性可以由客户端的 FIFO 执行顺序保证，而单调读一致性通过检查客户端和服务器的 zxid 保证。

Q：ZooKeeper 如何实现监视（watch）？

A：FAQ 有解释，客户端通常会注册一个回调函数，该函数在监视触发时调用。Go 使用通道（channel）来实现，当监视触发时，服务器会向通道发送一个事件，然后应用程序可以从通道中获取该事件。但是有个疑问，Go 的通道能跨网络传输数据么。

Q：为什么请求不幂等，而事务幂等？

A：假设有一个带顺序标志的创建节点的请求，那么多次发送请求会创建不同的节点。事务是请求的幂等形式，论文中提到形如 〈transactionType, path, value, new-version〉。

Q：ZooKeeper 服务器、客户端和应用程序的关系？

A：个人理解，服务器提供低级原语，客户端使用 API 实现更高级的原语，应用程序使用客户端提供的高级原语。

Q：ZooKeeper 中的 zxid 和版本号有什么关系？

A：ZooKeeper 的每次状态更改（写操作）都会递增 zxid，而版本号则是 znode 的属性。个人认为，zxid 是 ZAB 层面的，版本号是数据库（状态机）层面的。

Q：可线性化和可串行化的区别？

A：可以看下 Linearizability versus Serializability，很清晰。

总结

刚开始看这篇论文，涉及很多没见过的术语，看着比较折磨。如果深入细节的话，会花费很多时间。我确实一开始没有抓住重点，陷入如何在代码层面使用 ZooKeeper，无等待和通用对象是什么意思之类的。但是，如果从更高的层面来看，ZooKeeper 可以理解为 ZAB + 数据库（状态机），就是使用数据树结构提供一个通用的 API。

在查找资料的过程中发现很多不一致的地方，例如：API 文档中描述异步请求会排队等待发送，但按照论文的描述应该不是这样的，不然怎么提高性能；一致性保证中提到单一系统映像，定义首先说保证看到相同的视图，然后又说不会看到旧视图，但这完全不是一个意思；FAQ 中对异步请求如何实现客户端 FIFO 执行顺序的讨论，我认为论文和另一份笔记都证明 FAQ 的错误。

在阅读论文和资料的过程中，经常会看到某个描述，感觉模糊不清，只能凭自己的猜测去理解。实际上确实有很多模糊的地方，没有描述具体的实现方式，但有些问题其实论文中也给出了回答。所以，在读论文的过程中还是要仔细一点，遇到不懂的不要随便猜测，先记下问题，因为很可能是一个错误的猜测，还会干扰之后的理解。总之，论文只是提供一个简要的说明，深入理解还需要实际使用 ZooKeeper，以及阅读源码。