介绍
这是一篇上世纪九十年代的论文，在当时的环境下，安装新工作站的需求与日俱增，而针对大量工作站的文件系统管理却费时费力。为了保存更多的文件和服务更多的用户，就需要更多的磁盘，并挂载到更多的机器上。某一组文件经常会被手动分配给某些特定的磁盘，当磁盘空间不足，异常或者成为性能热点时，就需要手动移动或者复制文件到其他磁盘上。使用 RAID 技术管理多个磁盘只能解决部分问题；当系统增长到需要多个磁盘阵列和多台服务器时，系统管理问题也随之而来。
Frangipani 是一个可扩展的分布式文件系统，它能统一管理挂载在不同机器上的磁盘，对外来说，这些磁盘构成了一个独立的共享存储池。组成 Frangipani 的机器默认能够被统一管理而且相互间能安全的通信。在 Frangipani 之前已经有了一些分布式文件系统的实现，并且在吞吐和容量上有很好的扩展性。Frangipani 的一个显著特性是它的内部结构非常简单——各台协作的机器共同访问一个通用的存储，并使用锁来保证访问的同步性。这种简单的结构使得只需要少量的机器就能处理系统恢复，重配置和负载均衡。Frangipani 的另一个关键特性是相比于已知的分布式文件系统，它结合了一系列功能使得 Frangipani 更易于使用和管理：
- 所有用户读取到的文件内容都相同。
- 可以轻易的向
Frangipani 添加更多的服务器来增加存储容量和吞吐，而无需修改已有服务器的配置，或者中断其操作。这些服务器可以像积木一样根据需要搭建来构建更大的文件系统。
- 系统管理员添加新用户时无需关心新用户的数据会由哪台服务器管理或者保存在哪个磁盘上。
- 系统管理员可以对整个文件系统进行完整和一致的备份，而无需停止服务。备份可以在线进行，使得用户可以快速访问被意外删除的文件。
- 文件系统可以在无需人工干预的情况下容忍机器、网络、磁盘异常并自行恢复。
Frangipani 构建于 Petal 之上，Petal 是一个易于管理的分布式存储系统，为客户端提供了虚拟磁盘。和物理磁盘一样，Petal 的虚拟磁盘也是以块（block）的方式来读取和写入。和物理磁盘不同的是，一个 Petal 虚拟磁盘提供了264字节的稀疏地址空间，并且只在需要的时候才会分配物理存储。Petal 也支持数据备份来保证高可用。Petal 同时提供了高效的快照功能来支持一致性备份。Frangipani 从下层存储系统继承了扩展性，容错和易于管理的特性，不过将这些特性扩展到文件系统还需要些细致的设计。下一节将会详细描述 Frangipani 的结构以及和 Petal 的关系。
上图展示了 Frangipani 的层级设计。多个可替换的 Frangipani 服务器运行于一个共享的 Petal 虚拟磁盘之上，不同的用户程序可以各自通过连接的 Frangipani 服务器来访问相同的文件，而各 Frangipani 服务器间通过分布式锁服务来保证数据的一致性。通过添加 Frangipani 服务器可以实现对文件系统层的扩展。Frangipani 通过异常服务器的自动恢复和借助依然存活的服务器来提供服务实现了容错。相比于中心化的网络文件服务器，Frangipani 通过将负载分摊到各个正在使用文件的机器上来提供更好的负载均衡。出于扩展性，容错和负载均衡的考虑，Petal 和 Frangipani 用到的锁服务也是分布式的。
Frangipani 服务器默认信任 Petal 服务器和锁服务。Frangipani 的最佳使用场景是在同一个管理域下的工作站集群，虽然它也可以扩展到其他管理域下。因此，Frangipani 可以被看做是一个集群文件系统。
论文的作者在 DIGITAL Unix 4.0 之上实现了 Frangipani。得益于 Frangipani 在 Petal 之上构建的简洁的层级设计，使得在几个月内实现了一个可用的系统。
Frangipani 的目标运行环境的场景是程序开发和工程。测试表明在这样的负载下，Frangipani 有着优秀的性能并且能很好的扩展，而最终的性能上限则受限于网络能力。
系统结构
上图展示了 Frangipani 系统下各机器的一种典型职责分配。最上方的机器运行着用户程序和 Frangipani 的文件服务模块，这些机器无需挂载磁盘。最下方的机器运行着 Petal 和分布式锁服务。
不过在实际场景中，组成 Frangipani 的机器无需严格按照上图中的描述承担职责。Petal 和 Frangipani 文件服务不一定要运行在不同的机器上；每台运行着 Petal 的机器也可以同时运行着 Frangipani 文件服务，特别是当 Petal 的机器负载不高时。分布式锁服务独立于系统中的其他服务，上图中描述了每个 Petal 机器上运行着一个锁服务，不过它们也可以运行在 Frangipani 或者其他可用的机器上。
组件
如前面的图中所示，用户程序通过标准的系统调用接口来访问 Frangipani。运行在不同机器上的应用程序能访问到相同的文件，而且看到的文件内容也是相同的；也就是说，如果在某台机器上修改了某个文件或者文件夹，那么运行在其他机器上的程序也能马上看到这个修改。对于使用 Frangipani 的程序来说，Frangipani 提供的文件操作语义保证和本地 Unix 文件系统提供的文件操作语义保证相同：程序对文件的修改会先暂存在内核的缓冲区中，在下一次的 fsync 或者 sync 系统调用之前，系统不保证对文件的修改会保存到非易失存储上，不过系统会记录对文件元数据的修改并且可选的保证当系统调用返回时，文件的元数据修改已经保存到了非易失存储上。和本地文件系统的文件操作语义有点小小的不同，Frangipani 中文件的最后访问时间是一个近似值，从而避免了每次读取文件时都需要写元数据。
每台机器上的 Frangipani 文件服务模块运行在操作系统内核中。通过内核的 file system switch Frangipani 将自己注册为一个可用的文件系统实现。Frangipani 的文件服务模块使用了内核的缓冲区来缓存最近使用的文件数据。它通过本地的 Petal 设备驱动来实现对 Petal 虚拟磁盘的读写。每个文件服务器使用相同的数据结构来读取和写入文件到共享的 Petal 磁盘上，不过各服务器会在 Petal 磁盘的不同区域上针对进行中的修改维护各自的重做日志。因为 Frangipani 的重做日志保存在 Petal 中，所以当某个 Frangipani 服务器异常时，其他的服务器可以通过 Petal 访问日志并进行数据恢复。各 Frangipani 服务器之间无需通信；它们只会和 Petal 和分布式锁通信。这就简化了服务器的添加，删除和恢复。
Petal 的设备驱动程序掩盖了 Petal 分布式的特性，对操作系统的上层应用来说，Petal 就等同于是一块本地磁盘。驱动程序负责和正确的 Petal 服务器通信，以及如果当前的服务器发生异常，能切换到另一台可用的服务器。类似 Digital Unix 的文件系统都可以运行在 Petal 之上，不过只有 Frangipani 提供了多客户端下访问同一文件的数据一致性特性。
Petal 的各服务器基于本地挂载的物理磁盘并通过协作来向 Frangipani 提供大型，可扩展，容错的虚拟磁盘。Petal 可以容忍一个或多个磁盘或者服务器异常，只要大多数的 Petal 服务器依然存活并且相互之间可以通信，以及每个数据块都至少有一个副本保存在物理存储上并且能够被访问。
Frangipani 用到的锁服务能够为网络中的客户端提供通用的读写锁服务。出于容错和扩展性考虑，它的实现是分布式的。Frangipani 使用锁服务来协调对虚拟磁盘的访问，以及保证各服务器内文件缓存的一致性。
安全和客户端/服务器配置
如 Fugure 2 所示，每台运行着用户程序的机器同时运行着 Frangipani 的文件服务模块。虽然这种配置有利于负载均衡和扩展，不过存在安全隐患。每个 Frangipani 机器都可以对共享的 Petal 虚拟磁盘上的数据块进行任意读写，所以 Frangipani 必须运行在受信任的操作系统上；类似于 NFS 的远程文件访问协议中的身份认证还不足以保证安全性。完整的安全性也要求 Petal 和锁服务运行在受信任的操作系统上，并且 Frangipani、Petal、锁服务这三个组件都需要能够互相认证。最后，为了保证文件数据的私有性，也需要保证没有人能够窃听 Petal 和 Frangipani 机器间的网络通信。
一种解决方案是运行用户程序的机器被设置为不允许运行自定义修改的操作系统，同时这些机器间通过一个私有网络连接并且用户程序没有权限访问。不过这并不是说需要将所有的机器放在同一个机房中并通过私有的物理网络相连；可以借助某些加密技术来实现系统的安全启动，以及某些认证技术和加密链路来保证通信安全性。另外，对于某些应用程序来说，一个不完整的解决方案也是可以接受的；典型的如 NFS 就不能防止网络窃听以及杜绝用户在自己的工作站上运行修改后的操作系统。论文的作者并没有实现所有的安全措施，不过 Frangipani 基本也可以达到 NFS 的安全级别，Petal 服务器只会接受来自已知网络地址的 Frangipani 服务器的请求。
如上图所示，Frangipani 文件系统可以扩展到外部非受信的管理域中。图中区分开了 Frangipani 客户端和服务端。只有受信的 Frangipani 服务端可以和 Petal 以及锁服务通信。这三个组件可以放置在一个受限制的环境中并且通过私有的网络连接。而外部的非受信远程客户端只能和 Frangipani 服务端通信，而不能直接访问 Petal 服务器。
客户端可以和 Frangipani 服务端以任何操作系统支持的文件访问协议通信，例如 DCE/DFS，NFS，SMB，因为对于运行着 Frangipani 服务端的机器来说，Frangipani 就类似于是个本地文件系统。当然，如果访问协议本身支持一致性访问是最好的（例如 DCE/DFS），从而使得 Frangipani 的多服务器间的一致性不会在上一层丢失。理想情况下，客户端的访问协议需要支持故障转移。上述提到的协议并不直接支持故障转移，不过在其他系统中如果某台服务器发生异常，会有另一台服务器接管并复用异常服务器的 IP 地址，因此可以在这里应用同样的手段。
除了安全之外，还有第二个原因要使用上述的客户端/服务端配置。因为 Frangipani 运行在操作系统内核，不能快速的适配不同的操作系统甚至是不同版本的 Unix。所以通过远程客户端的方式就能使得运行不支持的操作系统的客户端也能够使用 Frangipani。
讨论
构建文件系统的分层思想——低层提供存储服务，高层提供命名，文件夹和文件服务，并不是 Frangipani 独有的。最早应用这个思想的是 Universal File Server。不过，Petal 提供的存储功能和早先的系统大有不同，从而引申出不同的上层结构设计。
Frangipani 的设计是基于 Petal 提供的抽象存储服务，作者还未充分考虑为了适配其他的存储服务（例如 NASD）需要对 Frangipani 做出哪些修改。
Petal 提供了高可用的存储服务并且能够通过添加资源来实现对吞吐和容量的扩展。不过，Petal 不提供协同功能或者在多个客户端间共享存储。另外，大部分的应用程序不能直接使用 Petal 的接口因为 Petal 面向的是磁盘而不是文件。Frangipani 在 Petal 之上构建了文件系统层使得在保留和扩展了 Petal 有用的特性的同时对应用程序更加易用。
Frangipani 的一个优势是能够透明的添加服务器，删除服务器以及实现故障恢复。通过将预写日志、锁和提供一致性访问、高可用的存储结合使用，Frangipani 能轻易的实现这个特性。
Frangipani 的另一个特性是能在文件系统运行时生成一致性的备份。这个机制会在后面介绍。
不过 Frangipani 的设计可能在三个方面上存在问题。基于启用了副本的 Petal 虚拟磁盘构建的 Frangipani 有时候会记录重复的日志，一次是 Frangipani 自己写入的日志，这里是 Frangipani 为客户端提供服务；另一次是 Petal记录的日志，这里以 Petal 的视角来说 Frangipani 成为了客户端。第二，Frangipani 无法根据磁盘的位置来选择在哪里保存数据，因为 Petal 提供的是虚拟的磁盘，之所以有这个需求可能是因为类似于 GFS 选择在哪里放置副本一样，如果 Frangipani 能知道具体磁盘的位置，它就能选择一个距离客户端近的磁盘保存文件。最后，Frangipani 会对整个文件或者文件夹加锁而不是对某个数据块加锁。不过作者还没有足够的使用经历来评估这三个问题的影响，不过撇开它们不谈，在作者所处环境下测试出的 Frangipani 的性能还是不错的。
磁盘布局
Frangipani 使用 Petal 提供的巨大、稀疏的磁盘地址空间来简化其数据结构。这个想法是受之前有着巨大内存空间的计算机上的相关工作所启发。因为有着如此巨大的地址空间所以可以将其任意切分。
一个 Petal 虚拟磁盘有264字节的地址空间。Petal 只会在物理磁盘空间写入后才会将其提交到虚拟地址中。Petal 同时提供了 decommit 原语用来释放某个范围内的虚拟地址所关联的物理磁盘空间。
为了使内部的数据结构足够小，Petal 会以较大的数据块来提交（commit）和回收（decommit）虚拟地址，目前的数据块大小是 64 KB。也就是说，对于每个 64 KB 的虚拟地址空间[a∗216,(a+1)∗216)，如果有数据写入且没有被回收，那么同时就需要分配 64 KB 的物理磁盘地址空间。因此 Petal 客户端写入的数据不能太稀疏，否则可能由于碎片化造成物理磁盘空间浪费。下图展示了 Frangipani 如何切分 Petal 的虚拟磁盘空间：
图中的第一个区域用于保存共享的配置参数和其他信息。这个区域的最大大小是 1 T，不过目前实际上只用了几 K。
第二个区域用于保存日志。每个 Frangipani 服务器会在这块区域中选择一部分来保存自己的私有日志。这里总共预留了 1 T 的空间，并切分为256个分区，所以可以保存256份日志。这就限制了一个 Petal 虚拟磁盘最多支持256个 Frangipani 服务器，不过这可以轻易的通过调整分区个数来扩展。
第三个区域用于保存分配位图，从而知道余下的虚拟空间中哪些是可用的。每个 Frangipani 服务器会独占式的锁住这块区域中的某一部分。当某台 Frangipani 服务器的分配位图空间不够时，它会再次找到可用的区域然后加锁使用。整个区域的大小是 3 T。
第四个区域用于保存 inode。每个文件需要一个 inode 来保存元数据，例如访问的时间戳和指向文件数据位置的指针。对于符号链接来说它们的数据直接保存在了 inode 中。每个 inode 的大小为512字节，和磁盘块的大小相同，从而避免了两个服务器同时访问同一个磁盘块上保存的不同 inode 所带来的竞争（也就是 false sharing，FAQ for Frangipani, Thekkath, Mann, Lee, SOSP 1997 中对这个问题有所解释，磁盘数据的读取以块为单位，如果 inode 小于512字节，某个 Frangipani 服务器先读取了磁盘数据块并缓存，此时另一个服务器需要读取和修改同一个磁盘数据块上的 inode，那么为了保证缓存一致性，第一个服务器再次读取 inode 时就需要重新读取磁盘数据块并刷新缓存，造成两个服务器交替的读取修改同一个数据块的内容，缓存也就失去了意义，而本质上两个服务器之间并不应该有竞争。）。整个区域的大小是 1 TB，所以可以保存231个 inode。在位图分配区域中的比特位和 inode 的映射是固定的，也就是说根据位图分配区域中的比特位地址就能推算出对应 inode 的地址，所以每个 Frangipani 为新文件所创建的 inode 地址在第四个区域中的偏移比例和该 inode 对应位图分配区域中的比特位的偏移比例是一致的。不过任何一个 Frangipani 都可能读写或释放某个已经存在的文件的 inode。
第五个区域用于保存小数据块，每个数据块大小为 4 KB（212字节）。一个文件的前 64 KB（16个数据块） 的内容会保存在小数据块中。如果某个文件的大小超过 64 KB，则超过的部分会保存在一个大数据块中。Frangipani 在一个 Fetal 虚拟磁盘上最多可以分配247字节（128 T）的小数据块，共计235块，是 inode 最大数量的16倍。
Petal 虚拟磁盘剩下的地址空间用于保存大数据块。每个大数据块有 1 TB 空间。
选择 4 KB 作为数据块大小会比更小的数据块的策略更容易产生磁盘碎片。同时，一个 inode 512字节在某种程度上也是空间浪费。可以将小文件直接保存在 inode 中来缓解这个问题。虽然存在碎片和空间浪费的问题，不过出于设计简洁性的考虑，作者认为这是一种合理的折中选择。
在当前的设计下，Frangipani 能保存的大文件个数小于224（1600万，大文件需要保存在大数据块中，一个大数据块 1 T，而虚拟空间最大地址264，即224T，又因为不是整个空间都用来保存大文件，所以实际个数小于224），大文件是指大于 64 KB 的文件。另外，Frangipani 能保存文件的最大大小是16个小数据块加上一个大数据块（64 KB 加 1 TB）。如果需要保存更多的文件，可以通过减小大数据块的大小来解决；以及允许一个大文件可以保存在多个大数据块中，这样就可以提高最大能保存文件的大小。如果264字节的地址空间不够，则一个 Frangipani 服务器可以支持扩展为多个 Petal 虚拟磁盘组成的 Frangipani 文件系统。
作者基于之前文件系统的使用经验设定了上述的系统参数。作者认为这种配置已经足够满足需求，不过还是需要时间和实际使用来检验。Frangipani 的设计足够灵活所以可以通过备份和恢复来验证合适的磁盘布局。
日志和恢复
Frangipani 通过元数据的预写重做日志来简化异常恢复和提高性能；不过用户的数据并不会记录到日志中。每个 Frangipani 服务器会将自己的日志保存在 Petal 中。当某个 Frangipani 服务器需要修改某个元数据时，它会首先生成一条日志来描述具体的修改内容并将其添加到内存日志中。这些内存中的日志会周期性的按照修改请求发起的顺序写入到 Petal 中（Frangipani 同时也支持将日志同步的写入到 Petal 中，这会稍微提高容错性不过会增加元数据更新操作的延迟。）。只有当某条日志写入 Petal 之后，系统才会真正修改对应文件的元数据。实际文件的元数据更新会交由一个 Unix 的 update 守护进程来周期性（大概每隔30秒）的更新。
在当前的实现中，Frangipani 写到 Petal 的日志的最大大小为 128 KB。根据 Petal 的空间分配策略，一份日志会拆分到两个不同的物理磁盘上，每个磁盘上的大小为 64 KB。Frangipani 会以环形缓冲（circular buffer）的方式来管理所分配的日志空间。当日志空间满时，Frangipani 会回收25%的最老的日志空间来存放新的日志。一般来说，被回收的日志所对应的元数据修改都应该已经写入到了 Petal 中（通过之前的 sync 操作），因此回收日志时不需要额外的写操作。如果回收日志时发现存在某些待回收的日志所对应的元数据修改还没有写入到 Petal，则需要先执行元数据的写入操作再回收日志。根据日志缓冲区和单条 Frangipani 日志的大小（80-128字节），如果在两个 sync 周期内存在1000-1600个元数据修改操作就能写满整个日志缓冲区。
如果某个 Frangipani 服务器发生异常，系统最终能检测到异常并根据该 Frangipani 服务器的日志进行恢复。Frangipani 服务器异常可以被所访问的客户端发现，或者当锁服务向持有锁的 Frangipani 服务器要求返回锁而没有响应时发现。当异常发生时，负责恢复的守护进程会临时拥有异常的 Frangipani 服务器的日志和锁的所有权。异常恢复进程会先找到异常服务器日志的起始位置和结束位置，然后逐条检查每一条日志，判断哪些日志所对应的元数据更新还没有被执行。当日志处理完成后，异常恢复进程就会释放所持有的锁并清空日志。其他的 Frangipani 服务器就可以在不受异常服务器影响的情况下继续工作，而异常的服务器可以在稍后被重启（对应的日志为空）。只要底层的 Petal 磁盘依然可用，系统就能容忍任意数量的 Frangipani 服务器异常。
为了确保异常恢复进程能找到异常服务器的日志的结束位置（即使磁盘控制器没有按照顺序写数据），系统为每512字节的日志数据块分配了一个递增的序号。只要发现某个数据块的序号小于前一个数据块的序号，那就说明前一个数据块就是日志的结束位置。
Frangipani 确保了日志和异常恢复能正确的处理多条日志。不过这在细节上有几点要注意。
首先，在下一节会介绍到 Frangipani 的锁协议保证了多个服务器对同一个数据的更新请求会被串行执行。某个持有写锁且修改了数据的服务器需要先将修改的数据写回到 Petal 后才能释放锁，所以要么是该服务器在正常情况下数据更新完成后主动释放锁，要么是服务器异常后由异常恢复进程在数据更新完成后释放锁。这说明对于任意的数据块来说，整个系统中最多只可能有一条数据修改的日志还未完成。
第二，Frangipani 确保了异常恢复进程只会处理异常服务器在持有锁之后但还未释放锁期间记录的日志。这是为了确保锁协议保证的更新串行化不会被破坏。Frangipani 使用了更强的条件限制来实现这一保证：异常恢复进程永远不会重新执行一个已经执行完成的数据更新。为了保证这一点，Frangipani 给每512字节的元数据块分配了一个版本号。而类似于文件夹的元数据有可能会跨多个数据块，所以也会有多个版本号。对于每个日志要修改的数据块，日志会记录修改的内容及新的版本号。在异常恢复时，恢复进程会比较当前元数据块最新的版本号和日志中记录的版本号，只有当日志中的版本号大于当前最新的版本号时，恢复进程才会执行重做日志。
由于 Frangipani 记录更新日志时不会记录用户数据，而只有元数据块给版本号预留了空间。这就带来了一个潜在问题。如果某个数据块一开始被用于保存元数据，后来空间被释放，然后又被用来保存用户数据，那么恢复进程就不能正确的跳过依然引用了这个元数据块（现在的用户数据块）的日志，因为原来保存元数据块中的版本号信息已经被用户数据所覆盖，所以恢复进程就无法比较日志中的版本号的大小。Frangipani 通过要求被释放的元数据块只能用于保存新的元数据来避免这个问题。
最后，Frangipani 保证在任一时刻只会有一个异常恢复进程在恢复重做某个异常服务器的日志。Frangipani 通过对日志文件的互斥锁来实现这一保证。
Frangipani 的日志和异常恢复机制假定当出现磁盘写异常时，单个扇区中的内容要么都是旧的，要么都是新的，而不会是两者的混合。如果某个磁盘扇区已损坏并且在读操作时返回 CRC 异常，那么 Petal 内置的副本机制通常能恢复对应的数据。如果某个扇区的副本都损坏了，或者 Frangipani 内部的数据结构由于软件 bug 造成损坏，则需要对元数据进行一致性检查以及需要一个恢复工具（例如 Unix 的 fsck）进行数据恢复。不过论文的作者写论文时还未实现这个工具。
Frangipani 的日志并不是为了给用户提供高层次的执行语义保证。它的目的是为了提高元数据更新的性能以及发生服务器异常时通过避免执行 fsck 这样的恢复工具来加快异常恢复速度。因为 Frangipani 的日志只会记录元数据的更新，不会记录用户数据，所以站在用户的视角来说，当系统发生异常时，文件系统的状态和异常发生前并不能保证一致。论文的作者并不是声明这样的语义是理想的，不过这个行为和标准的本地 Unix 文件系统的行为是一样的。在本地 Unix 文件系统和 Frangipani 中，用户都可以在合适的时间点调用 fsync 来确保更好的数据一致性保证。
Frangipani 所使用的日志技术最早被应用于数据库，并在之后应用到其他某些基于日志的系统中。Frangipani 本身不是个日志结构（log-structured）的文件系统；它不会将所有的数据都保存在日志中，而是将数据按约定维护在磁盘中，通过较少的日志 Frangipani 实现了较好的性能和异常恢复的原子性。和其他基于日志的文件系统不同，但是和例如 Zebra 这样的日志结构文件系统相同，Frangipani 也会保存多份日志。
同步和缓存一致性
由于会有多个 Frangipani 服务器修改 Petal 的共享数据，所以需要一个细致化的同步手段来确保各服务器读取到的数据是一致的，以及当系统负载增加或者添加新的服务器时能通过有效的并发手段来提高性能。Frangipani 使用多读一写的读写锁来实现必要的同步。当锁服务侦测到冲突的锁请求时，它会要求锁的持有者释放锁或者进行锁降级（写锁降级为读锁）来消除冲突。
读锁允许一个 Frangipani 服务器从磁盘中读取相应的数据并缓存。如果该服务器被要求释放锁，则在释放锁前必须先清空缓存。写锁允许一个 Frangipani 服务器读取或者修改数据并将其缓存。只有当某个服务器持有写锁时，它所缓存的数据才有可能和磁盘上保存的数据不同。因此，如果持有写锁的服务器被要求释放写锁或者降级为读锁，则必须先将修改的数据写回到磁盘。如果该服务器降级为了读锁，则依然可以保留缓存，不过如果释放了锁则必须清空缓存。
相比于释放写锁或者降级为读锁时将缓存中的数据写回到磁盘，还可以选择直接将缓存中的数据发送给请求方。不过出于简洁性考虑 Frangipani 并没有这么做。首先，在 Frangipani 的设计中，Frangipani 服务器之间无需通信。它们只会和 Petal 以及锁服务通信。第二，当某台服务器异常时，Frangipani 的设计保证了系统只需要处理异常服务器的日志即可。如果选择将未写入到磁盘中的数据直接发送给请求方，而接收方发生异常时，指向未持久化的数据的日志可能分散在了多台服务器中。这就给系统恢复和日志空间回收都带来了问题。
Frangipani 将磁盘数据结构拆分为了一个个逻辑段，每个逻辑段都对应一把锁。为了避免 false-sharing，Frangipani 确保了一个磁盘扇区不会保存超过1个可共享的数据结构。将磁盘数据结构拆分为可加锁的段是为了将锁的数量控制的足够小，同时又能避免正常情况下的锁竞争，从而使得锁服务不会成为系统的瓶颈。
每个 Frangipani 服务器的日志都是一个可加锁的段，因为这些日志都是私有的。磁盘布局中的位图区域也切分为了一个个段，并且相互之间加了互斥锁，所以分配新文件时不会发生竞争，因为每个服务器都在自己持有的段内分配。还未分配给文件的数据块或者 inode 也同时被位图中的同一把锁保护，只是该位置的空间当前被标记为可用状态。最后，每个文件，文件夹，或者符号链接都是一个段；也就是说，inode 和其指向的数据都被同一把锁保护。这种每个文件一把锁的锁粒度对于作者所在的工作负载来说已经足够了，因为文件几乎很少会被并发的修改。而对于其他的工作负载来说则可能需要更细粒度的锁。
有些操作会要求原子的更新被多把锁保护的磁盘数据结构。Frangipani 通过对锁全局排序以及使用两阶段获取锁来避免死锁。首先，某台服务器先确定需要获取哪些锁。这个过程中会涉及获取或者释放某些锁，例如查找文件夹中的某些文件名。然后，服务器对锁按照 inode 的地址排序然后依次获取锁。同时服务器会检查在第一阶段中读取的对象是否在第二阶段发生了修改，如果发生了修改，那么该服务器会释放所有的锁然后重新执行第一阶段。否则，该服务器就可以开始执行具体的操作，在缓存中修改某些数据并记录一条日志。在缓存中的数据写回到磁盘前，该服务器都会持有相关的锁。
上述描述的缓存一致性协议类似于 Echo、Andrew File System、DCE/DFS 和 Sprite 中的客户端文件缓存协议。这里使用的避免死锁的技术和 Echo 类似。和 Frangipani 一样，Oracle Parallel Server 同样是将缓存中的数据写回到磁盘，而不是直接将缓存中的数据发送给下一个写锁的持有者。
锁服务
Frangipani 只需要一小部分，通用的锁功能，并且不希望锁服务在日常操作中成为性能瓶颈，有很多种实现可以满足这些需求。在 Frangipani 项目中，一共尝试了三种不同的锁服务的实现，其他已有的锁服务也可以提供需要的功能，只是在其之上可能需要编写额外的代码来适配。
锁服务提供了多读一写的读写锁。这里的锁不会用完就马上释放，只要没有其他客户端请求相同的锁，这把锁就会一直被某个客户端持有（这里锁服务的客户端指的是 Frangipani 服务器）。
锁服务通过租约来处理客户端异常。当某个客户端请求锁服务时，它会先获取一个租约。该客户端获取的所有锁都和这个租约绑定。每个租约有一个过期时间，目前是锁创建或者延期后30秒过期。客户端在租约过期前必须先延期，否则锁服务会认为客户端发生了异常。
网络异常会妨碍 Frangipani 服务器延长租约，即使 Frangipani 服务器没有发生异常。当某个 Frangipani 服务器无法延长租约时，它会释放所有的锁并清空缓存。如果缓存中的数据被修改了，那么该服务器会打开某个内部标记使得后续的客户端请求都返回一个错误。相应的文件系统必须取消挂载才能删除这个异常。Frangipani 使用这种粗暴的方式来报告异常从而避免了异常被忽略。
第一版的锁服务实现使用了单节点中心化的服务器，所有的锁状态都保存在了内存中。这种设计对于 Frangipani 来说是足够的，因为 Frangipani 的日志中记录了足够的信息，所以即使锁服务发生异常丢失了所有的状态系统也能够恢复。不过，锁服务异常会导致严重的性能问题。
第二版的锁服务将锁的状态保存在 Petal 中，每个对锁状态的修改都会先写到 Petal 中，然后才会返回给客户端。如果锁服务的主节点异常，那么会由某个备份节点读取 Petal 中的锁状态然后接管异常的主节点并继续提供服务。在这个设计下，异常恢复更加透明，不过日常操作的性能会低于第一种锁实现。作者还未完全实现所有异常的自动恢复就开始了第三种锁服务的实现。
第三版的锁服务是分布式的，并且能很好的支持容错和性能。它由一组相互间协作的锁节点组成，同时每个 Frangipani 服务器内嵌了一个 clerk 模块。
锁服务将锁以表（tables）的形式组织，每个表以 ASCII 字符串的形式命名。每个表中的锁以64位的整型命名。一个 Frangipani 文件系统只使用一个 Petal 虚拟磁盘，虽然多个 Frangipani 文件系统可以挂载到同一个机器上。每个文件系统都绑定了一个关于锁的表。当一个 Frangipani 文件系统挂载时，Frangipani 服务器会请求内嵌的 clerk，然后 clerk 就会打开绑定的锁表。当 clerk 成功打开锁表时，锁服务会返回一个租约标识符，这个租约标识符会在后续通信中使用。当文件系统取消挂载时，clerk 就会关闭锁表。
clerk 和锁节点间使用异步消息而不是 RPC 来通信，这样做能减少内存的使用并同时有着足够好的灵活性和性能。和锁相关的基础消息类型是 request，grant，revoke 和 release。request 和 release 消息是由 clerk 发送给锁节点，而 grant 和 revoke 消息则是由锁节点发送给 clerk。锁的升级和降级同样由这四种消息类型来处理。
锁服务使用了支持容错，分布式的异常监测机制来检测锁节点的异常。这个机制同时也被用于 Petal。该机制基于各节点间定期的心跳交换，同时使用了共识算法来容忍网络分区。
一把锁会在服务端和 clerk 侧都需要消耗内存。在当前的实现中，服务端会为每个锁分配112字节，每个 clerk 如果有进行中或者已分配的锁请求则额外还需要104字节。所以每个客户端每个锁最多使用232字节。为了避免长时间持有锁带来的内存消耗，clerk 会丢弃长时间（1小时）未使用的锁。
一小部分全局且不经常修改的状态信息会由 Lamport 的 Paxos 算法复制到所有的锁服务器上。锁服务复用了为 Petal 实现的 Paxos 算法。全局的状态信息包括锁服务器列表，每个锁服务器负责的锁列表，以及打开还未关闭锁表的 clerk 列表。这些信息用于达成共识，即在各个锁服务器间重新分配锁，当某个锁服务器发生异常时能恢复某个锁的状态，以及协助 Frangipani 服务器的异常恢复。从效率考虑，所有的锁被划分到100个不同的锁组中（lock groups），然后以组的形式分配给锁服务器，而不是以单个锁的形式。
有时候一把锁会被重新分配给其他的锁服务器，一方面是为了故障转移，另一方面是为了充分利用刚异常恢复的锁服务器，避免流量集中。当某个锁服务器被永久的添加到集群或者从集群中删除时，会发生类似的锁重分配。在这种情况下，所有的锁始终会被重分配，因为需要保证每台锁服务器持有的锁的数量是均衡的，锁重分配的次数要尽可能的少，以及每个锁都只会分配给一台锁服务器。锁的重分配也是由两阶段进行。在第一阶段，各个锁服务器丢弃保存在内部状态中的锁。第二阶段，锁服务器会和 clerk 通信，根据其所打开的锁表来重新分配锁。锁服务器根据 clerk 的锁表来重新生成锁的状态，同时通知 clerk 每把锁在重新分配后对应的锁服务器。
当某个 Frangipani 服务器异常时，在正确的恢复操作执行前，它所持有的锁不能被释放。特别的，系统需要先处理异常 Frangipani 服务器的日志并将未持久化的元数据更新写入到 Petal。当 Frangipani 服务器的租约到期时，锁服务会通知另一台 Frangipani 服务器上的 clerk 来执行恢复操作，并撤销原来异常服务器持有的全部锁。负责恢复的 clerk 会获取一把异常服务器的日志的互斥锁。这把锁同样分配了一个租约，所以当负责恢复的服务器异常时锁服务会再找一台服务器重新开始恢复任务。
一般来说，Frangipani 系统能够容忍网络分区，并在可能的情况下继续运行，否则就停止服务。特别的，Petal 可以在网络分区的情况下继续运行，只要大多数的 Petal 服务器依然存活并且相互之间可以通信，不过如果某些 Petal 虚拟磁盘在大多数的 Petal 服务器上没有备份的话，那么这些磁盘无法被继续访问。同样的，只要大多数的锁服务器依然存活并且相互之间可以通信，整个锁服务也依然可用。如果某个 Frangipani 服务器无法和锁服务通信，那么它将再也不能延长租约。此时锁服务会认为这个 Frangipani 服务器发生异常，然后会基于它的日志挑选一个新的 Frangipani 服务器发起恢复流程。如果某个 Frangipani 服务器无法和 Petal 通信，那么它将无法读取和写入虚拟磁盘。不管在哪种情况下，Frangipani 服务器都会拒绝后续受影响的文件系统的用户请求，直到网络分区恢复以及文件系统被重新挂载。
当 Frangipani 服务器的租约过期时存在一个潜在的问题。如果服务器依然存活而只是由于网络原因造成无法和锁服务通信，那么这台服务器可能依然会在租约过期后访问 Petal。Frangipani 服务器会在写入 Petal 前检查租约是否依然有效（并确保在未来的tmargin秒内依然有效）。不过，Petal 并不会校验某个写入请求是否还在租约有效期内。所以，如果 Frangipani 服务器检查租约和写请求到达 Petal 的时间大于剩余租约的时间，那就会带来一个问题：当 Petal 收到写请求时，租约已经过期，该服务器持有的写锁已经分配给了其他服务器。Frangipani 为tmargin选择了一个足够大的值（15秒）来确保在正常情况下上述问题不会发生，不过依然不能确保一定不会发生。
在未来 Frangipani 会尝试解决这个问题，论文给出了一个可能的解决方案。Frangipani 会给每一个 Petal 的写请求附加一个过期的时间戳。这个时间戳的值为生成写请求时的租约过期时间减去
tmargin。这样 Petal 就可以忽略任何时间戳小于当前时间的写请求。只要 Petal 和 Frangipani 服务器的时钟在tmargin内保持同步，Petal 就能够可靠的拒绝租约过期的写请求。
另一种解决方案则不依赖时钟同步，但是需要将锁服务和 Petal 集成，并且将 Frangipani 服务器获取的租约标识符附加到写请求中，Petal 收到写请求后就可以根据租约标识符校验租约是否过期，从而拒绝过期的写请求。
添加和删除服务器
系统管理员有时需要添加或者删除 Frangipani 服务器。Frangipani 被设计成能够轻易的处理这些场景。
添加一台服务器到运行中的系统只需要一点点的系统管理工作。新添加的服务器只需要知道使用哪块 Petal 虚拟磁盘以及锁服务的地址即可。新添加的服务器会和锁服务通信来获取租约，然后根据租约标识符决定使用哪部分的日志空间，然后就开始提供服务。系统管理员不需要修改其他服务器的配置，其他服务器能自动适配新服务器的上线。
删除一台 Frangipani 服务器则更简单。可以直接关闭这台服务器。不过更可取的方式是让这台服务器先将未持久化的数据写入到 Petal，然后释放持有的锁，最后再停机，不过这不是强制要求的。当服务器异常停机时，如果后续该服务器持有的锁需要被使用，则系统会自动发起恢复流程，并最终使得共享磁盘的数据达成一致。同样的，系统管理员也不需要修改其他服务器的配置。
如 Petal 的论文所描述，Petal 服务器同样可以无缝的添加和删除，锁服务器也同理。
备份
Petal 的快照功能提供了一个简便的方法来备份一份完整的 Frangipani 文件系统快照。Petal 的客户端可以在任意时刻创建一个虚拟磁盘的快照。所创建的快照的虚拟磁盘和普通的虚拟磁盘一样，只不过它是只读的。实际快照实现时采用了写时复制（copy-on-write）技术来提高效率。Petal 创建的快照是崩溃一致的（crash-consistent）：也就是说，快照中保存的是在 Petal 虚拟磁盘中的数据，Frangipani 服务器内存中的数据不会记录到快照中。
因此，我们可以简单的通过创建 Petal 快照并将其拷贝到磁带中来备份一个 Frangipani 文件系统。快照会包含所有的日志，所以可以将其复制到一个新的 Petal 虚拟磁盘中然后根据日志运行恢复程序来恢复一个 Frangipani 文件系统。归功于崩溃一致的特性，从快照中恢复系统后要解决的问题就简化成了和发生系统级别的停电后恢复系统所要解决的问题一样。
可以对 Frangipani 稍作修改来改进这个恢复机制，即创建一个系统文件级别一致的快照，从而也无需执行恢复操作。可以让备份程序先强制要求所有的 Frangipani 服务器进入一个栅栏，这个功能可以由锁服务提供的全局锁来实现。每个 Frangipani 服务器以共享的模式获取这把锁然后执行修改操作，而备份程序以互斥的方式来处理请求。当 Frangipani 服务器收到请求要求释放锁时，它会阻塞所有新的修改数据的文件系统调用然后进入栅栏，接着清空缓存中已修改的数据，最后释放锁。当所有的 Frangipani 服务器进入栅栏后，备份程序会以互斥的模式获取锁，然后创建一个 Petal 快照并释放锁。之后各 Frangipani 就可以继续以共享的模式获取锁，然后恢复服务。
在后一种方案下，一个 Frangipani 的快照可以无需进行恢复就直接挂载使用。用户就可以从新的磁盘卷中在线获取单个文件，或者将其以一个更方便的格式转储到磁带中而无需 Frangipani 参与数据恢复。新添加的卷必须以只读的格式挂载，因为底层的 Petal 快照是只读的。在未来作者可能扩展 Petal 的快照使其可写，或者在 Petal 之上再抽象一层来模拟写操作。
参考
