Frangipani 分布式文件系统

来自 https://thekkath.sharepoint.com/Documents/frangipani.pdf

Frangipani 是一个可扩展的分布式文件系统，管理多台服务器上的磁盘作为一个共享存储池。

功能：

• 所有用户看同一份件都是一致的
• 无需变更配置就可以轻松添加服务器至集群
• 系统管理员无需停机就可以备份整个文件系统
• 可以设置备份保持在线，允许用户访问不小心删除的文件
• 无需手动干预文件系统能够容忍并从机器、网络、磁盘故障中恢复

两层结构：

• 底层：Petal 分布式存储服务，为客户端提供虚拟磁盘

  和物理存储一样，Petal 虚拟磁盘以可读写的块提供存储

  与物理存储不同，虚拟磁盘提供 2^64 字节地址空间，而物理存储只按需分配

  通过数据复制实现高可用

  提供高效的快照以支持一致的备份

• 上层：Frangipani 文件系统，使用分布式锁确保一致性

• 运行在共享的 Petal 虚拟磁盘上
• 添加服务器扩容文件系统层
• 自动从故障恢复和使用存活的服务器来继续操作实现错误容忍
• 通过分散文件系统负载提供比集中式网络文件服务器更好的负载均衡能力
• Petal 和锁服务也是分布式的，实现可扩展性、容错和负载均衡

2. 系统架构

2.1 组件

用户程序通过标准操作系统调用接口访问 Frangipani。修改文件内容是在本地内核缓冲区进行的，在下一次 fsync 或 sync 系统调用前不能保证落盘；但是元数据的变化会被记录下来并可以选择在系统调用前落盘。

Frangipani 文件系统模块在操作系统内核中运行，它将自己注册进内核的文件系统开关。使用本地的 Petal 设备驱动读写 Petal 虚拟磁盘。所有文件服务器在共享的 Petal 磁盘上读写相同的文件系统数据结构，但是每台服务器保留它自己的重做日志（redo log）。日志保存在 Petal 中，当某台 Frangipani 服务器崩溃，另一台会读取日志并执行恢复。服务器之间没必要直接相互通信，它们只和 Petal 还有 锁服务通信。

Petal 设备驱动隐藏了其分布式的性质，使得 Petal 看上去就像普通的本地磁盘。驱动负责连接 Petal 服务器和故障切换。

锁服务为客户端提供了读写锁，Frangipani 使用锁来协调对虚拟磁盘的访问并保持多服务器的缓存一致。

2.2 CS 架构

如图 2，每台部署了用户程序的机器也会部署 Frangipani 文件服务器模块。这种配置带来了安全问题。任意 Frangipani 机器都能读写 Petal 虚拟磁盘的块，所以 Frangipani 必须只允许在可被信任的操作系统上；同样 Petal 和锁服务也要运行在可被信任的操作系统上；这三种组件两两认证。最后为了确保文件数据的私密性，应答防止用户窃听 Petal 和 Frangipani 机器之间的网络。

Frangipani 文件系统可通过图 3 所示的配置暴露给外部不被信任的机器，将服务器和客户端分开。只有被信任的 Frangipani 服务器才能与 Petal 和锁服务通信。

客户端使用操作系统支持的文件访问协议与 Frangipani 服务器通信，例如 DCE/DFS、NFS 或 SMB，当然支持一致访问的协议最佳（DCE/DFS）。理想化地，协议也应该支持故障切换。上面提到的协议不支持故障切换，但 VIP 能在这应用。

除了安全问题，因为 Frangipani 运行在内核中，不能快速移植到不同的操作系统甚至不同的 Unix 版本，来自不支持的操作系统的客户端远程访问来使用 Frangipani。

2.3 讨论

Frangipani 的设计有三个潜在问题：

1. 有时日志会发生两次，一次 Frangipani 日志，Petal 内部又一次。
2. Frangipani 在放置数据时不使用磁盘位置信息，因为 Petal 虚拟了磁盘。
3. Frangipani 锁整个文件和目录而不是独立的块。

3. 磁盘布局

Petal 虚拟磁盘有 2^64 字节地址空间，只有在写入时才把物理磁盘空间提交给虚拟地址。

1. 第一块区域存储共享的配置参数，有 1TB 虚拟空间，但目前只用了几 KB
2. 第二块区域存储每台 Frangipani 的日志，预留了 1TB，分成 256 份日志。
3. 第三块区域用于分配位图，描述剩下区域中那些块是空闲的。每台 Frangipani 服务器锁定一部分位图供其使用。
4. 第四块区域存放 inode：每个文件都有一个 inode 来存储元数据（时间戳和数据位置指针）。每个 inode 512 字节，1TB 空间能存放 2^31 个 inode。
5. 第五块区域存放小数据块，每个 4KB（2^12 字节）。文件的首 64 KB 会被存储在小数据块中（16 个）；其余部分被存储在一个大数据块中。
6. Petal 地址空间的剩余部分存储大数据块，为每个大块预留 1TB 空间。

使用 4KB 块的磁盘布局策略可能有碎片化的问题；而且每 inode 512B 也有点浪费空间，但收获了简洁的设计，算是对物理磁盘空间成本的合理权衡。

当前方案限制了 Frangipani 少于 2^24 个大文件（大于 64 KB 的文件），基本上也没啥文件能大于 1TB。但也可以设置大数据块的大小，Frangipani 的设计是弹性的。

4. 日志与恢复

Frangipani 采用 WAL 日志来简化故障恢复并提升性能，只记录元数据而非用户数据，存储在 Petal 的日志区域。当更新文件元数据时，Frangipani 创建一条相关记录并缓存在内存中，定期写入 Petal。只有在日志记录落盘后才会修改实际的元数据。

日志大小限制在 128 KB，为每份日志分配一个环形缓冲区，当日志填满后，回收最旧（已被写入 Petal）的 25% 日志空间腾出地方给新日志。

如果某台 Frangipani 服务器崩溃，系统会探测到故障并运行恢复程序。恢复进程找到日志的起始和结尾，按序检查每条记录，进行未完成的更新。处理完日志后，恢复进程会释放锁。只要底层的 Petal 仍可用，Frangipani 能够容忍无数服务器故障。

为了确保恢复时能够找到日志的结尾，日志每 512 字节块附带一个单调递增的序号。

1. Frangipani 的锁协议确保不同服务器对相同数据的更新请求是串行化的。
2. Frangipani 确保恢复只适用于服务器持锁以来的更新，并且它仍会持锁；而且恢复不会重复已完成的更新。
3. 只有元数据块为版本号预留空间，用户数据更新不会被记录。
4. Frangipani 确保任意时间只有一个恢复进程重放特定服务器的日志。

Frangipani 的日志并不向其用户提供高级的语义保证（只记录元数据而非用户数据），而是为了提高元数据更新的性能和加速故障恢复。类似 Unix，用户可以调用 fsync 来获得更好的一致性语义。

5. 同步与缓存一致性

多台 Frangipani 服务器都在修改共享的数据结构，需要同步来保证一致性，还要足够的并发来提升性能。Frangipani 采用读写锁实现必要的同步。

• 读锁允许服务器读盘并缓存。如果某台服务器被要求释放读锁，必须在弃锁前失效其缓存。
• 写锁允许服务器读写盘并缓存。持写锁时缓存可以与磁盘上的数据不同。当服务器被要求释放写锁/降级到读锁时，必须在弃锁前将脏数据写盘。
  • 如果降级锁可以保留缓存
  • 如果释放锁必须失效缓存

选择将脏数据刷至磁盘而非直接将其发送给请求方，是为了简单性：

1. Frangipani 服务器之间不通信，只和 Petal 还有锁服务通信。
2. 确保当某台服务器崩溃，只需要处理那台服务器使用的日志。

将磁盘上的数据结构划分至带锁的逻辑段，确保单个磁盘扇区持有不超过一个可共享的数据结构，旨在保持合理的锁数量，避免对锁的争夺，这样锁服务就不会成为系统的瓶颈。

每个日志都是一个可锁段，位图区也一样，这样在分配新文件时就不会出现竞争。最终每个文件、路径、软链接都是一个段；锁保护它指向的 inode 和文件数据。这种单文件的锁粒度很适合难得并发写的工作负载。

缓存一致性协议与 Echo、Andrew 文件系统、DCE/DFS 和 Sprite 中用于客户端文件缓存的有点类似。

6. 锁服务

Frangipani 只需要锁服务的一小部分通用功能：

• 锁服务提供读写锁。
• 锁服务使用租约处理客户端故障，客户端获取的全部锁都与租约关联，到期后要续租。

Frangipani 项目中先后使用了三种不同的锁实现：

1. 初版实现了单台集中式服务器，所有锁状态保存在内存里。对 Frangipani 来说也够了，因为服务器的日志有足够的状态信息，即使锁服务崩了，也能恢复；但是锁服务故障会导致 Frangipani 不可用。
2. 第二版实现将锁状态存在 Petal 虚拟磁盘上。如果主锁服务挂了，备机从 Petal 读取当前状态并接管。这种方案虽然提升了可用性但性能很差。
3. 最终版的锁服务实现是完全分布式的。

当 Frangipani 文件系统被挂载，Frangipani 服务器会打开一张锁表，锁服务会给 Frangipani clerk 组件一个租约；当文件系统被卸载，clerk 会关掉锁表。出于性能考虑 clerk 和锁服务之间异步通信而非同步的 RPC。

和 Petal 一样，锁服务使用心跳包探测服务器活性；采用 qorum 容忍网络分区。

一小部分全局状态信息（锁服务器列表、正被使用的锁列表等）使用 Paxos 算法在所有锁服务器间复制并持久化，复用了 Petal 的 Paxos 实现。之所以要达成共识，是因为要：

• 在锁服务器之间重新分配锁
• 锁服务器崩溃后恢复锁状态
• 服务 Frangipani 服务器的恢复

当 Frangipani 服务器崩溃，它持有的锁不会被释放。这台服务器的日志必须被处理，任何待执行的更新必须被写至 Petal。当一台 Frangipani 服务器的租约过期，锁服务将要求另一台 Frangipani 服务器进行恢复，然后释放属于崩溃的 Frangipani 服务器的锁。

所以总体上 Frangipani 系统也容忍网络分区。具体来说只要大多数 Petal 服务器没问题，Petal 就可以继续提供服务，但如果大多数的那个分区没有副本，Petal 虚拟磁盘的部分内容将无法访问。锁服务也一样，只要大多数没问题，就能够继续提供服务。

• 如果某台 Frangipani 服务器因为网络分区无法访问锁服务，就无法续租：锁服务会宣布它的死亡，并从其在 Petal 上的日志中启动恢复。
• 如果某台 Frangipani 服务器因为网络分区无法访问 Petal 虚拟磁盘：Frangipani 将禁止用户访问受影响的文件系统，直到分区消失并重新挂载文件系统。

Frangipani 服务器租约到期还有个小风险，如果服务器并没有挂掉只是因为网络问题与锁服务失联，即使租约到期了它还是有可能尝试访问 Petal。Frangipani 服务器会检查它的租约是否有效，但是 Petal 在收到写请求时不会做任何检查。两种解决方案：

1. 给每个 Petal 写请求带上过期时间戳，设置成租约到期时间；让 Petal 忽略掉任何小于当前时间的请求。
2. Petal 写请求带上租约的 ID，Petal 拒绝任何携带着过期租约标识符的写请求。

7. 添加/删除节点

Frangipani 设计旨在简化服务器的添加和删除任务。

• 添加节点：新服务器只需知道使用哪个 Petal 虚拟磁盘以及如何发现锁服务。新服务器向锁服务申请租约，确定使用哪块日志空间，并上线。管理员无需动其他服务器。
• 删除节点：服务器最好在停止前 flush 所有脏数据并释放它的锁，但也并非严格需要如此。同样管理员也无需碰其他服务器。

8. 备份

基于 Petal 的快照功能：Petal 允许客户端在任意时间点创建虚拟磁盘的副本。快照看上去和普通的虚拟磁盘没啥区别，除了没法修改它。该实现使用了写时复制（copy-on-write）技术来提升效率。快照包含所有日志，把它复制到一个新的虚拟磁盘并对每一份日志运行恢复。

Frangipani 基于该方案做了一点小改进：通过让备份程序强制所有 Frangipani 服务器进入一个新的屏障状态，使用一个由锁服务提供的全局锁。Frangipani 服务器要执行任何修改操作就以共享模式获取该锁；而备份进程则以独占模式请求该锁。当某台 Frangipani 服务器收到请求释放该锁，它会阻塞所有修改数据的文件系统调用，清理缓存中的脏数据并释放锁。当所有服务器都进入屏障状态，备份程序能够获得独占锁；然后它打一个 Petal 快照并释放该锁。此时服务器在共享模式下重新持锁，正常的操作就恢复了。

通过以上方案，新的快照无需恢复就可以作为 Frangipani 卷被挂载。但是新卷必须以只读模式被挂载，因为 Petal 快照是只读的。

总结

• Frangipani 文件系统为用户提供了对一组文件一致、共享的访问。
• 随着用户的增长，可以扩展更多的存储空间，获得更好的性能和负载均衡。
• 即使组件出现故障，仍高可用。
• 几乎无需人工管理。

使用 Petal 作为底层有这些好处：

• Petal 实现了数据复制的高可用性，Frangipani 就无需这样做了。
• 一个 Petal 虚拟磁盘可被所有的 Frangipani 服务器统一访问，因此任意服务器都可以提供任何文件。
• 任何机器都可以运行恢复。
• Petal 大而松散的地址空间能够简化 Frangipani 的磁盘数据结构。

在最初的性能测试中 Frangipani 已经可以与生产上的 DIGITAL Unix 文件系统相媲美，而且还可以通过进一步调整来提升性能。

令人印象深刻的是，一台 Frangipani 服务器在更新共享文件系统的过程中崩溃了，有可能恢复。我们通常认为一个线程在持有互斥锁时崩溃是无法恢复的。每台 Frangipani 服务器都有自己的日志存储在公共的地方，以便任何人从其中恢复这个想法很聪明。

Frangipani 与 GFS 的不同：

架构上最大的不同在于 GFS 绝大部分文件系统逻辑都在服务器程序中，而 Frangipani 将逻辑分布至运行 Frangipani 的服务器上。也就是说 Frangipani 没有 GFS 那样文件服务器的概念。Frangipani 将文件系统逻辑放在服务器上，为了让它们完全在本地缓存中执行文件系统操作。Frangipani 大多数的活动是服务器读写单个用户缓存的文件。Frangipani 有很多机制来确保服务器的缓存一致。这样一来一个服务器上的写可以马上被另一个服务器上的读看到，复杂操作都是原子的（如创建文件），即使其他服务器尝试查看相关文件或路径。

相反 GFS 根本没有缓存，因为它专注于顺序读写巨型文件，这对缓存来说太大了。所以 GFS 没有缓存一致性协议。文件系统的逻辑在服务器程序中，GFS 客户端相对简单；服务器程序才需要锁和担心故障恢复。

Frangipani 看上去就像一个真正的文件系统；GFS 不以文件系统出现因为应用程序不得不通过 GFS 的库来使用它。