摘要（Abstract）
理想的分布式文件系统应该为所有用户提供对同一组文件的一致的统一的访问，并且可以任意伸缩，以便为不断增长的用户社区提供更多的存储空间和更高的性能。尽管组件出现故障，但它仍然具有很高的可用性。这将需要最少的人工管理，并且随着添加更多组件，管理不会变得更加复杂。
Frangipani是一种新的文件系统，它近似于这种理想状态，而且由于它的两层结构，构建起来相对容易。底层是Petal(在之前的文章描述过)，这是一种分布式存储服务，提供可扩展、高可用性、自动管理的虚拟磁盘。在上层，多台机器在共享的Petal虚拟磁盘上运行相同的Frangipani文件系统代码，使用分布式锁服务来确保一致性。
Frangipani是在拥有统一管理下的集群中运行的，可以安全的通信。因此，机器之间相互信任，共享虚拟磁盘方法是可行的。当然，Frangipani文件系统可以使用普通网络文件访问协议剔除不受信任的机器。
我们在运行数码UNIX 4.0的AlphaS集合上实施了Frangipani。初始测量表明，Frangipani随着服务器的增加，其依然具有优异的单服务器性能和可扩展性。
1、介绍（Introduction）
使用当下技术构建的可应用于大型、持续增长的计算机集群的文件管理系统，处理现有业务来说是一项艰巨的任务。其困局是，为了保存更多文件并为更多用户提供服务，必须添加更多磁盘，连接到更多机器上。 这些组件中的每一个都需要人工维护。 文件组通常手动分配到特定磁盘，然后在组件装满、出现故障或成为性能热点时手动移动或复制。 使用RAID技术将多个磁盘驱动器连接成一个单元只是部分解决方案；当系统变得足够大，需要多个raid和多个服务器时，仍然会出现管理问题。
RAID技术是一种将多个磁盘驱动器组合在一起以提高数据存储性能和/或数据冗余的技术。RAID代表“冗余阵列独立磁盘”（Redundant Array of Independent Disks），它通过将数据分散存储在多个磁盘上来提高读写速度，并且可以使用冗余备份来保护数据免受硬件故障的影响。
Frangipani是一种新的可扩展的分布式文件系统，它将多台机器上的磁盘集合管理为一个共享存储池。假定这些机器处于共同的管理之下，并且能够安全地通信。在构建分布式文件系统方面，已经有很多早期的尝试，它们在吞吐量和容量上都有很好的扩展性[1,11,19,20,21,22,26,31,33,34]。Frangipani的一个显著特征是它有一个非常简单的内部结构—一组相互协作的机器使用一个公共存储并用锁同步对该存储的访问。这个简单的结构使我们能够用很少的机器处理系统恢复、重新配置和负载平衡。Frangipani的另一个关键在于，它结合了一组特性，使其比我们所知道的现有文件系统更容易使用和管理Frangipani。
- 所有用户都会给出相同一组文件的一致视图。
- 可以轻松地将更多服务器添加到现有Frangipani集群中，以增加其存储容量和吞吐量，而无需更改现有服务器的配置或中断其操作。这些服务器可以被看作是“砖块”，可以增量堆叠，以根据需要构建尽可能大的文件系统。
- 系统管理员可以添加新用户，而无需考虑哪些计算机将管理其数据或哪些磁盘将存储数据。
- 系统管理员可以在不关闭整个文件系统的情况下对整个文件系统进行完整且一致的备份。备份可以在线保存，允许用户快速访问意外删除的文件。
- 文件系统能够容忍机器、网络和磁盘故障，并在无需操作员干预的情况下进行恢复。
Frangipani位于Petal[24]之上，Petal是一个易于管理的分布式存储系统，它为客户端提供虚拟磁盘。与物理磁盘一样，Petal虚拟磁盘提供了可以在块中读写的存储空间。与物理磁盘不同，虚拟磁盘提供不连续的2^64字节地址空间，物理存储空间按需分配。Petal可以选择性的复制数据以实现高可用性。Petal还提供了高效的快照[7,10]来支持一致的备份。Frangipani从底层存储系统继承了许多可伸缩性、容错性和易于管理的特性，但是需要仔细设计才能将这些属性扩展到文件系统级别。下一节将详细介绍Frangipani的结构及其与Petal的关系。
图1：Frangipani分层。几个可互换的Frangipani服务器提供对一个Petal虚拟磁盘上的一组文件的访问
图1演示了Frangipani系统中的分层。多个可互换的Frangipani服务器通过在共享的Petal虚拟磁盘上运行来提供对相同文件的访问，用锁来协调它们的操作，以确保一致性。文件系统层可以通过添加Frangipani服务器来缩放。它通过自动从服务器故障中恢复并继续使用幸存的服务器来实现容错。它在单一的网络文件服务器上提供了改进的负载平衡，通过分流文件系统负载并将其转移到正在使用这些文件的机器上。Petal和锁服务也被用于在可伸缩性、容错和负载平衡方面。
Frangipani服务器，Petal服务器和锁服务相互信任。Frangipani设计之初用于在单个管理域内的工作站集群中运行良好，但Frangipani文件系统可以导出到其他域。因此，Frangipani可以看作是一个集群文件系统。
我们已经在DIGITAL Unix 4.0下实现了Frangipani。由于Frangipani在现有Petal服务之上的清晰分层，我们能够在短短几个月内实现一个工作系统。
Frangipani针对具有程序开发和工程工作负载的环境。我们的测试表明，在此类工作负载上，Frangipani具有出色的性能，并缩小网络限制。
2、系统结构（System Structure）
图2描述了系统的一个经典情况。上面显示的机器运行用户程序和Frangipani文件服务器模块；它们可以是无磁盘的。底部显示的运行Petal和分布式锁服务。
图2：Frangipani结构。在一个典型的Frangipani配置中，一些机器运行用户程序和Frangipani文件服务器模块；另一些运行Petal和分布式锁服务。在其他配置中，相同的机器可能同时扮演这两个角色。
Frangipani的组件不必完全按照图2所示的方式分配给机器。Frangipani和Petal服务器不需要在单独的机器上；每台Petal机器也可以运行Frangipani，特别是在Petal机器没有重载的情况下。分布式锁服务独立于系统的其他部分;我们展示了在每台Petal服务器上运行一个lock服务器，但它们也可以在Frangipani主机或任何其他可用的机器上运行。
2.1、组件（Components）
如图2所示，用户程序通过标准操作系统调用接口访问Frangipani。在不同机器上运行的程序都看到相同的文件，它们的视图是一致的；也就是说，对一台计算机上的文件或目录所做的更改在所有其他计算机上都立即可见。程序基本上得到了与本地Unix文件系统相同的语义保证：对文件内容的更改通过本地内核缓冲池暂存，在下一次适用的fsync或sync系统调用之前不能保证到达非易失性存储，但是元数据的更改会被记录下来，并且可以选择在系统调用返回时保证为非易失性。与本地文件系统语义稍有不同的是，Frangipani仅粗略地维护一个文件的最后访问时间，以避免每次读取数据时都进行元数据写操作
每台机器上的Frangipani文件服务器模块在操作系统内核内运行。它将自己注册到内核的文件系统中，作为可用的文件系统实现之一。文件服务器模块使用内核的缓冲池来缓存最近使用的文件中的数据。它使用本地Petal设备驱动程序读取和写入Petal虚拟磁盘。所有文件服务器在共享Petal磁盘上读取和写入相同的文件系统数据结构，但每个服务器在Petal磁盘的不同部分保留其自己的挂起更改重做日志。日志保存在Petal中，以便在Frangipani服务器崩溃时，另一台服务器可以访问日志并运行恢复。Frangipani服务器之间不需要直接通信；它们只与Petal和锁服务通信。这使服务器的添加、删除和恢复变得简单。
Petal设备驱动程序隐藏了Petal的分布式特性，使得Petal对于操作系统的更高层来说就像一个普通的本地磁盘。驱动程序负责于对应的Petal服务器通信，并在发生故障时切换到另一个服务器。任何Digital Unix文件系统都可以在Petal上运行，但只有Frangipani提供了从多台机器对相同文件的一致访问。
Petal服务器协同运行，为Frangipani提供大型的、可伸缩的、容错的虚拟磁盘，这些虚拟磁盘是在连接到每个服务器的普通物理磁盘之上实现的。Petal可以容忍一个或多个磁盘或服务器故障，只要Petal服务器的大部分保持正常并保持通信，每个数据块至少有一个副本保持物理上可访问。Petal的更多细节可在另一份文件[24]。
锁服务是一种通用服务，它向网络上的客户端提供多读/单写锁。它的实现是分布式的，以容错和可扩展的性能。Frangipani使用锁服务来协调对虚拟磁盘的访问，并在多个服务器上保持缓冲区缓存一致。
2.2、安全和客户端/服务器配置（Security and the Client/Server Configuration）
在图2所示的配置中，运行用户程序的每台计算机也运行一个Frangipani文件服务器模块。这种配置有可能实现良好的负载平衡和扩展，但会带来安全问题。任何Frangipani机器都可以读取或写入共享Petal虚拟磁盘的任何块，因此Frangipani必须仅在具有可信操作系统的机器上运行；Frangipani机器向Petal验证自己是否代表特定用户是不够的，就像在NFS等远程文件访问协议中所做的那样。完全安全性还要求Petal服务器和锁服务器在受信任的操作系统上运行，并要求所有三种类型的组件彼此进行身份验证。最后，为了确保文件数据保密，应防止用户在连接Petal和Frangipani机器的网络上窃听。
通过将机器放置在一个环境中，防止用户在机器上启动修改过的操作系统内核，并将其与用户进程无权访问的专用网络互连，可以完全解决这些问题。这并不一定意味着必须将机器锁定在具有专用物理网络的房间中；可以使用已知的用于安全引导、身份验证和加密链接的加密技术[13,37]。此外，在许多应用中，部分解决方案是可以接受的；典型的现有NFS安装对于在工作站上引导修改过的内核的用户的网络窃听甚至数据修改都不安全。到目前为止，我们还没有实施任何这些安全措施，但是我们可以通过让Petal服务器只接受来自属于受信任的Frangipani服务器机器的网络地址列表的请求，大致达到NFS安全级别。
NFS代表“网络文件系统”（Network File System），它是一种远程文件访问协议，允许计算机通过网络透明地访问和共享文件。
Frangipani文件系统可以使用图3所示的配置导出到管理域之外的不受信任的机器。这里我们区分Frangipani客户端和服务器。只有受信任的Frangipani服务器与Petal和锁服务通信。它们可以位于受限环境中，并通过如上所述的专用网络互连。远程、不受信任的客户端通过单独的网络与Frangipani服务器通信，无法直接访问Petal服务器。
图3:客户机/服务器配置 Frangipani服务器不仅可以为本地计算机提供文件访问，还可以为通过标准网络文件系统协议连接的远程客户端计算机提供文件访问。
客户端可以使用主机操作系统支持的任何文件访问协议（如DCE/DFS、NFS或SMB）与Frangipani服务器通信，因为Frangipani看起来就像运行Frangipani服务器的机器上的本地文件系统。当然，一个支持一致性访问的协议(例如 DCE/DFS)是最好的，这样Frangipani跨多个服务器的一致性就不会在下一级丢失。 理想情况下，该协议还应该支持从一个Frangipani服务器到另一个Frangipani服务器的故障转移。刚才提到的协议不直接支持故障转移，但是让新机器接管故障机器的IP地址的技术已经在其他系统中使用过[3,25]，也可以在这里应用。
除了安全性之外，使用此客户机/服务器配置还有第二个原因。因为Frangipani在内核中运行，所以它不能在不同的操作系统甚至不同版本的Unix之间快速移植。客户端可以通过远程访问受支持的系统，从不受支持的系统使用Frangipani。
2.3、讨论（Discussion）
将文件系统分为两层构建的想法——较低级别提供存储库，较高级别提供名称、目录和文件——并不是Frangipani所独有的。我们知道的最早的例子是通用文件服务器[4]。然而，Petal提供的存储设施与早期的系统有很大不同，这也导致了不同的更高级别结构。第10节包含与以前系统的详细比较。
Frangipani的设计目的是与Petal提供的存储空间配合使用。我们还没有充分考虑开发NASD等替代存储抽象所需的设计更改[13]。
Petal提供了高可用性存储，可以随着资源的添加而扩展吞吐量和容量。然而，Petal没有提供在多个客户端之间协调或共享存储的功能。此外，大多数应用程序不能直接使用Petal的客户端接口，因为它是磁盘类型而不是文件类型。Frangipani提供了一个文件系统层，使Petal在保留和扩展其良好属性的同时对应用程序有用。
Frangipani的优势在于它允许透明的添加服务器、删除和故障恢复。通过将预写式日志和锁与一个统一的可访问的、高可用性的存储结合起来，它能够轻松地做到这一点。
Frangipani的另一个优势是它能够在系统运行时创建一致的备份。第8节讨论了Frangipani的备份机制。
Frangipani的设计有三个方面可能会有问题。将Frangipani与复制的Petal虚拟磁盘一起使用，意味着日志记录有时会发生两次，一次是到Frangipani日志，另一次是在Petal本身。其次，Frangipani在放置数据时不使用磁盘位置信息，事实上它不能，因为Petal虚拟了磁盘。最后，Frangipani锁定整个文件和目录，而不是单个块。我们没有足够的使用经验来评估我们设计的这些方面，但尽管如此，Frangipani在我们测试的工程工作负载上的测量性能还是不错的。
3、磁盘布局（Disk Layout）
Frangipani使用Petal的大而稀疏的磁盘地址空间来简化其数据结构。这个总体思路让人想起了过去在大内存地址空间的计算机编程工作。有这么多的地址空间可用，可以慷慨地将其分割开来。
Petal虚拟磁盘有2^64字节的地址空间。Petal仅在写入虚拟地址时才将物理磁盘空间提交给虚拟地址。Petal还提供了一个decommit原语，可以释放支持一系列虚拟磁盘地址的物理空间。
为了保持内部数据结构的小型化，Petal以相当大的块（目前为64 KB）提交和释放空间。也就是说，每个64 KB的地址范围【a* 2^16，(a+1)*2^16】（其中一些数据已写入且未解除提交）都分配有64 KB的物理磁盘空间。因此，Petal客户机不能使其数据结构过于稀疏，否则过多的物理磁盘空间将因碎片化而被浪费。图4显示了Frangipani是如何划分其虚拟磁盘空间的。
图4:磁盘布局。 Frangipani利用Petal巨大而不连续的磁盘地址空间来简化其数据结构。每个服务器都有自己的日志和自己的分配位图空间块。
第一个区域存储共享的配置参数和管理信息（Housekeeping information）。我们允许这个区域有一兆字节（TB）的虚拟空间，但实际上目前只使用了其中的几千字节。
Housekeeping information是指文件系统中用于管理文件和目录的元数据，例如文件大小、创建时间、修改时间、访问权限等。
第二个区域存储日志。每台Frangipani服务器获得 一部分空间来存放它的私人日志。我们已经为这个区域保留了 1TB（2^40字节）给这个区域，划分为256个日志。这 这个选择限制了我们目前的实施，使其只能容纳256个服务器，但这很容易进行调整。
第三个区域用于分配位图，以描述剩余区域中的哪些块是空闲的。每个Frangipani服务器都会锁定位图空间的一部分以供其专用。当服务器的位图空间填满时，它会查找并锁定另一个未使用的部分。位图区域的长度为3 TB。
第四个区域存放节点。每个文件都需要一个inode来保存其元数据，如时间戳和指向其数据位置的指针。符号链接将其数据直接存储在inode节点中。我们将节点的长度定为512字节，也就是一个磁盘块的大小，从而避免了服务器之间不必要的争夺（“虚假共享”），如果两个服务器需要访问同一块中的不同节点，就会出现这种情况。我们分配了1TB的节点空间，允许2^31个节点的空间。分配位图和节点之间的映射是固定的，所以每个Frangipani服务器只从与分配位图的部分相对应的节点空间中为新文件分配节点。但任何Frangipani服务器都可以读取、写入或释放任何现有文件的节点。
第五个区域存放小数据块，每个4 KB（2^12字节）大小。一个文件的前64 KB（16个块）被存储在小块中。如果一个文件增长到超过64KB，剩下的就存储在一个大块中。我们为小块分配2^47个字节，因此最多允许有2^35个小块，是最大节点数的16倍。
Petal地址空间的其余部分存放大数据块。每个大数据块都保留了1TB的地址空间。
我们使用4KB块的磁盘布局策略可能会比更谨慎地支配磁盘空间的策略遭受更多的碎片。另外，为每个节点分配512字节的空间也有些浪费。我们可以通过将小文件存储在inode本身来缓解这些问题[29]。我们的设计所获得的是简单性，我们相信这对于额外的物理磁盘空间的成本来说是一个合理的权衡。
目前的方案将Frangipani限制在略低于2^24（1600万）大文件，其中大文件是指大于64KB的任何文件。另外，任何文件都不能大于16个小块加一个大块（64KB加1TB）。如果这些限制被证明太小，我们可以很容易地减少大块的大小，从而使更多的数量可用，并允许大文件跨越一个以上的大块，从而提高最大文件大小。如果2^64字节的地址空间限制被证明是不够的，一个Frangipani服务器可以在多个虚拟磁盘上支持多个Frangipani文件系统。
我们根据早期文件系统的使用经验，选择了这些文件系统参数。我们相信我们的选择将为我们提供良好的服务，但只有时间和使用才能证实这一点。Frangipani的设计足够灵活，我们可以以文件系统的备份和恢复为代价来试验不同的布局。
4、日志和恢复（Logging and Recovery）
Frangipani使用元数据的预写重做日志记录来简化故障恢复并提高性能；用户数据不被记录。每个Frangipani服务器在Petal中都有自己的私有日志。当Frangipani文件服务器需要进行元数据更新时，它首先创建一个描述更新的记录，并将其附加到其内存中的日志中。这些日志记录会按照它们所描述的更新被请求的顺序定期写入Petal。(我们可以选择让日志记录同步写入。这提供了更好的故障语义，但增加了元数据操作的延迟。）。只有在日志记录被写入Petal之后，服务器才会修改其固定位置中的实际元数据。Unix update demon会定期（大约每30秒）更新固定位置。
日志的大小是有限制的，在目前的实现中是128KB。考虑到Petal的分配策略，一个日志将由两个不同的物理磁盘上的两个64KB的片段组成。为每个日志分配的空间被作为一个循环缓冲区管理。当日志填满时，Frangipani会回收最旧的25%的日志空间，用于新的日志条目。通常情况下，回收区域的所有条目都是指已经写入Petal的元数据块（在之前的同步操作中），在这种情况下，不需要进行额外的Petal写入。如果有尚未写入的元数据块，这项工作将在日志被回收之前完成。考虑到日志的大小和Frangipani日志记录的典型大小（80-128字节），如果在两个周期性同步操作之间有大约1000-1600个修改元数据的操作，日志就会被填满。
如果一个Frangipani服务器崩溃了，系统最终会检测到失败，并在该服务器的日志上运行恢复。故障可能是由故障服务器的客户端检测到的，或者当锁服务要求故障服务器返回它所持有的锁而没有得到答复时。恢复守护进程被隐式的赋予失败服务器的日志和锁的所有权。该守护进程找到日志的开始和结束，然后按顺序检查每条记录，执行每一个尚未完成的描述性更新。在日志处理完成后，恢复进程释放其所有的锁并释放日志。然后，其他Frangipani服务器可以不受故障服务器的阻碍，故障服务器本身也可以选择重新启动（有一个空日志）。只要底层的Petal卷保持可用，系统就可以容忍无限数量的Frangipani服务器故障。
为了确保恢复能够找到日志的结尾（即使磁盘控制器不按顺序写入数据），我们在日志的每个512字节块上附加一个单调增加的日志序列号。通过找到一个低于前一个的序列号，可以可靠地检测到日志的结束。
Frangipani确保在有多个日志的情况下，日志和恢复工作正常。这需要注意几个细节。
首先，Frangipani的锁协议，在下一节中描述，确保不同服务器对相同数据的更新请求是序列化的。覆盖脏数据的写锁只有在脏数据被写入 Petal 之后才能更改所有者，可以是原始锁持有者写入，也可以是代表它运行的恢复进程写入。这意味着对于任何给定的块，最多只能有一个日志保存未完成的更新。
其次，Frangipani确保恢复只适用于自服务器获得覆盖它们的锁后所记录的更新，并且它仍然持有这些锁。这是为了确保锁协议所规定的序列化不被违反而需要的。我们通过强制执行一个更强的条件来实现这一保证：恢复绝不重复描述已经完成的更新的日志记录。为了实现后者，我们在每个512字节的元数据块上保留一个版本号。元数据如目录，它跨越了多个块，有多个版本号。对于日志记录所更新的每一个块，该记录包含了对更改的描述和新的版本号。在恢复过程中，只有当块的版本号小于记录的版本号时，才会应用对块的修改。
因为用户数据的更新没有被记录下来，只有元数据块有预留空间给版本号。这就产生了一个强制性的问题。如果一个块被用于元数据，被释放，然后又被重新用于用户数据，那么在版本号被错误的用户数据覆盖后，引用该块的旧日志记录可能不会被正确跳过。Frangipani通过重用释放的元数据块来保存新的元数据，从而避免了这个问题。
最后，Frangipani确保在任何时候只有一个恢复进程试图重放特定服务器的日志区域。锁服务通过授予活动的恢复进程对日志的独占锁来保证这一点。
Frangipani的记录和恢复方案假定，磁盘写入失败会使单个扇区的内容处于旧状态或新状态，但绝不会同时处于这两种状态。如果一个扇区被损坏，以至于读取它时出现CRC错误，Petal的内置复制通常可以恢复它。如果一个扇区的两个副本都丢失了，或者Frangipani的数据结构被软件错误破坏了，就需要一个元数据一致性检查和修复工具（像Unix fsck）。到目前为止，我们还没有实现这样的工具。
Frangipani的日志不是为了向用户提供高级别的语义保证。它的目的是提高元数据更新的性能，并通过避免每次服务器故障时运行fsck等程序来加速故障恢复。只有元数据被记录下来，而不是用户数据，所以用户不能保证在故障后文件系统的状态在他看来是一致的。我们并不声称这些语义是理想的，但它们与标准的本地Unix文件系统所提供的相同。在本地 Unix 文件系统和 Frangipani 中，用户可以通过在适当的检查点调用 fsync 来获得更好的一致性语义。
Frangipani的日志记录是应用了最早为数据库开发的技术[2]，后来被用于其他几个基于日志的文件系统[9, 11, 16, 18]。Frangipani不是一个日志结构的文件系统[32]；它不把所有的数据保存在日志中，而是维护传统的磁盘数据结构，用一个小的日志作为辅助，以提供更好的性能和故障原子性。与上述其他基于日志的文件系统不同，但与日志结构的文件系统Zebra[17]和xFS[1]一样，Frangipani保留多个日志。
5、同步和缓存一致性（Synchronization and Cache Coherence）
由于多个Frangipani服务器都在修改共享的磁盘数据结构，因此需要谨慎地进行同步，以便为每个服务器提供一致的数据视图，同时允许有足够的并发性，以便在负载增加或服务器增加时扩展性能。Frangipani使用多读/单写锁来实现必要的同步。当锁服务检测到冲突的锁请求时，会要求锁的当前持有者释放或降级以消除冲突。
一个读锁允许服务器从磁盘上读取相关数据并进行缓存。如果一个服务器被要求释放它的读锁，它必须在遵守之前使其缓存条目失效。写锁允许服务器读取或写入相关的数据并缓存它。服务器缓存的磁盘块副本只有在它持有相关的写锁时才能与磁盘上的版本不同。因此，如果一个服务器 被要求释放其写锁或将其降级为读锁，它必须在遵守之前将脏数据写到磁盘。如果是降级锁，它可以保留其缓存条目，但如果释放锁，则必须使其失效。
当写锁被释放或降级时，我们可以选择绕过磁盘，将脏数据直接转发给请求者，而不是将脏数据刷到磁盘。出于简单的原因，我们没有这样做。首先，在我们的设计中，Frangipani服务器不需要相互通信。它们只与Petal和锁服务器进行通信。其次，我们的设计确保当一个服务器崩溃时，我们只需要处理该服务器使用的日志。如果直接转发脏缓冲区，并且具有脏缓冲区的目标服务器崩溃，那么指向脏缓冲区的日志条目可能分布在多台机器上。这将给恢复和在日志空间填满时回收日志空间带来问题。
我们将磁盘上的结构分为逻辑段，并为每个段加锁。为了避免错误的共享，我们确保一个磁盘扇区不包含一个以上可以共享的数据结构。我们将磁盘上的数据结构划分为可上锁的段，旨在保持锁的数量合理地少，但又能避免普通情况下的锁争夺，从而使锁服务不成为系统的瓶颈。
因为日志是私有的，所以每个日志都是一个单独的可锁定段。位图空间也被划分为独占锁定的段，这样当分配新文件时就不会有争用。当前未分配给文件的数据块或索引节点受到分配位图段上的锁的保护，该段上的锁持有标记为空闲的位。最后，每个文件、目录或符号链接都是一个段;也就是说，一个锁同时保护inode和它所指向的任何文件数据。这种每个文件的锁粒度适合于很少并发写共享的工程工作负载。然而，其他工作负载可能需要更细粒度的锁定。
有些操作需要原子化的更新由不同锁覆盖的几个磁盘数据结构。我们通过对这些锁进行全局排序并在两个阶段获得这些锁来避免死锁。首先，一个服务器确定它需要什么锁。这可能涉及到获取和释放一些锁，例如在一个目录中查找名字。其次，它按照节点地址对锁进行排序，并依次获取每个锁。然后，服务器检查它在第一阶段检查的任何对象是否在其锁被释放时被修改。如果是的话，它就释放锁，并循环重复第一阶段。否则，它就执行操作，弄脏缓存中的一些块，并写一条日志记录。它保留每个锁，直到它覆盖的脏块被写回磁盘。
我们刚刚描述的缓存一致性协议与Echo[26]、Andrew文件系统[19]、DCE/DFS[21]和Sprite[30]中用于客户端文件缓存的协议相似。避免死锁的技术与Echo的类似。和Frangipani一样，Oracle数据库（Oracle Parallel Server），也是将脏数据写入磁盘，而不是在写入锁的后续所有者之间使用缓存到缓存的传输。
6、锁服务（The Lock Service）
Frangipani只需要其lock server的一小部分通用功能，而且我们不希望该服务在正常运行中成为性能瓶颈，因此许多不同的实现可以满足其要求。在Frangipani项目的过程中，我们已经使用了三种不同的lock server的实现，并且其他现有的lock server可以提供必要的功能，也许只需在上面加一层薄薄的代码。
lock server提供多读/单写锁。锁是粘性的；也就是说，一个客户端通常会保留一个锁，直到其他客户端需要一个冲突的锁。(回顾一下，锁服务的客户端是Frangipani服务器）。
锁定服务使用租约来处理客户端故障[15, 26]。当一个客户端第一次通讯lock server时，它获得了一个租约。客户端获得的所有锁都与租约相关。每个租约都有一个过期时间，目前设置为创建或最后一次更新后的30秒。客户端 必须在到期时间前更新其租约，否则服务会认为它已经失败。
网络故障可以阻止Frangipani服务器更新其租约，即使它没有崩溃。当这种情况发生时，服务器会丢弃它所有的锁和缓存中的数据。如果缓存中的任何东西是脏的，Frangipani会打开一个内部标志，使所有来自用户程序的后续请求返回一个错误。文件系统必须被卸载以清除这个错误状况。我们选择了这种激进的报错方式，使它难以被无意中忽略。
我们最初的lock server实现是一个单一的、集中的服务器，它将所有的锁状态保存在易失性内存中。这样的服务器对Frangipani来说是足够的，因为Frangipani servers和他们的日志持有足够的状态信息，即使锁服务在崩溃中失去了所有的状态，也可以恢复。然而，锁服务的失败将导致一个巨大的性能故障。
我们的第二个实施方案将锁的状态存储在Petal虚拟磁盘上，在返回客户端之前，将每个锁的状态变化写到Petal上。如果主lock server崩溃了，备份服务器将从Petal中读取当前状态并接管，以提供持续服务。有了这个方案，故障恢复更加透明，但普通情况下的性能比集中式的内存方法要差。在进入下一个实施方案之前，我们没有完全实现对所有故障模式的自动恢复。
我们的第三个也是最后一个锁服务实现是完全分布式的，用于容错和可扩展的性能。它由一组相互合作的锁服务器和一个连接到每个Frangipani服务器的客户端模块(clerk module)组成。
锁服务将锁组织成由ASCII字符串命名的表。表内的各个锁是由64位整数命名的。回顾一下，一个Frangipani文件系统只使用一个Petal虚拟磁盘，尽管多个Frangipani文件系统可以安装在同一台机器上。每个文件系统都有一个与之相关的表。当一个Frangipani文件系统被挂载时，Frangipani服务器调用clerk，打开与该文件系统相关的锁表。锁服务器在成功打开时给clerk一个租赁标识符，这个标识符被用于他们之间所有的次序通信。当文件系统被卸载时，clerk关闭锁表。
客户端和锁服务器通过异步消息而不是RPC进行通信，以尽量减少内存的使用量，并实现良好的灵活性和性能。对锁进行操作的基本消息类型是请求、授予、撤销和释放。请求和释放消息类型是由客户端发送给锁服务器的，而授予和撤销消息类型是由锁服务器发送给客户端的。锁的升级和降级操作也是使用这四种消息类型处理的。
锁服务使用一个容错的分布式故障检测机制来检测锁服务器的崩溃。这与Petal使用的机制相同。它是基于各组服务器之间及时交换心跳信息。它使用多数共识来容忍网络分区。
锁在服务器和每个clerk那里都要消耗内存。在我们目前的实现中，服务器为每个锁分配了112个字节的块，此外还有104个字节给每个有未决或已批准的锁请求的clerk。每个客户端每个锁占用232字节。为了避免因为粘性锁而消耗过多的内存，clerk 会丢弃那些长时间（1小时）没有使用的锁。
使用Lamport的Paxos算法[23]，在所有锁服务器上持续复制少量不经常变化的全局状态信息。锁服务重复使用最初为Petal编写的Paxos的实现。全局状态信息包括一个锁服务器的列表，每个服务器负责服务的锁的列表，以及已经打开但尚未关闭每个锁表的clerk的列表。这些信息被用来达成共识，在锁服务器之间重新分配锁，在锁服务器崩溃后从clerk那里恢复锁状态，并促进Frangipani服务器的恢复。为了提高效率，锁被划分为大约一百个不同的锁组，并按组分配给服务器，而不是单独分配。
锁偶尔会在不同的锁服务器之间重新分配，以弥补一个崩溃的锁服务器或利用一个新恢复的锁服务器。当一个锁服务器被永久地添加到系统中或从系统中移除时，也会发生类似的重新分配。在这种情况下，锁总是被重新分配，以便每个服务器提供的锁的数量是平衡的，重新分配的数量是最小的，并且每个锁正好由一个锁服务器提供。重新分配分两个阶段进行。在第一阶段，失去锁的锁服务器从其内部状态中丢弃这些锁。在第二阶段，获得锁的锁服务器与打开相关锁表的clerk联系。这些服务器从clerk那里恢复其新锁的状态，而clerk则被告知其锁的新服务器。
当Frangipani服务器崩溃时，在执行适当的恢复操作之前，无法释放其拥有的锁。具体来说，必须处理崩溃的Frangipani服务器的日志，并且必须将任何挂起的更新写入Petal。当Frangipani服务器的租约到期时，锁服务将要求另一台Frangipani机器上的clerk执行恢复，然后重新租用属于崩溃的Frangipani服务器的所有锁。该clerk被授予一个锁，以确保以独占方式访问日志。此锁本身由租约覆盖，因此如果此恢复过程失败，锁服务将启动另一个恢复过程。
一般来说，Frangipani系统可以容忍网络分区，在可能的情况下继续运行，否则会完全关闭。具体来说，Petal可以在网络分区的情况下继续运行，只要大多数Petal服务器保持正常并处于通信状态，但如果大多数分区中没有副本，Petal虚拟磁盘的部分将无法访问。只要大多数锁服务器保持正常并处于通信状态，锁服务就会继续运行。如果一个Frangipani服务器与锁服务分开，它将无法续租。锁服务将宣布这样的Frangipani服务器死亡，并从它在Petal上的日志开始恢复。如果一个Frangipani服务器被脑裂无法访问Petal，它将无法读取或写入虚拟磁盘。在这两种情况下，服务器将不允许用户进一步访问受影响的文件系统，直到脑裂恢复和文件系统被重新挂载。
当Frangipani server的租约过期时，有一个小的危险。如果服务器没有真正崩溃，而只是由于网络问题与锁服务失去联系，它可能在租约过期后仍然试图访问Petal。Frangipani服务器会检查它的租约是否仍然有效（并且在一定的时间内仍然有效），在失效之前依然试图对Petal进行写入。然而，当写请求到达时，Petal不做任何检查。因此，如果在Frangipani的租约检查和随后的写请求到达Petal之间有足够的时间延迟，我们可能会有一个问题：租约可能已经过期，锁已经给了另一个服务器。我们使用了足够大的误差范围（15秒），在正常情况下，这个问题不会发生，但我们不能绝对排除它。
在未来，我们希望能消除这种危险；一种可行的方法是如下。我们在每个写给Petal的请求上添加一个到期时间戳。时间戳设置为生成写请求时的当前租约到期时间，减去锁延时删除的时间。然后我们让Petal忽略任何时间戳小于当前时间的写请求。只要Petal和Frangipani服务器上的时钟同步在差值范围内，这种方法就能可靠地拒绝租约过期的写入。
另一种不需要同步时钟的方法是将锁服务器与Petal集成，并将从锁服务器获得的租约标识符包含在每个对Petal的写入请求中。然后，Petal将拒绝任何具有过期租约标识符的写入请求。
7、添加和删除服务器（Adding and Removing Servers）
随着Frangipani安装的增长和变化，系统管理员偶尔会需要增加或删除服务器机器。Frangipani的设计使这项任务变得简单。
在一个正在运行的系统中添加另一个Frangipani服务器，只需要少量的管理工作。新的服务器只需要被告知使用哪个Petal虚拟磁盘和在哪里找到锁服务。新的服务器与锁服务通讯以获得租约，从租约标识符中确定使用哪一部分日志空间，然后开始运行。管理员不需要接触其他服务器；它们会自动适应新服务器的存在。
移除Frangipani服务器甚至更容易。简单地关闭服务器就可以了。服务器最好刷新所有脏数据并在停止前释放其锁，但这并不是严格的需要。如果服务器突然停止，在下次启动时，它先获取一个锁，然后在它的日志上运行恢复程序，使共享磁盘进入一个一致的状态。同样，管理员不需要接触其他服务器。
Petal服务器也可以透明地添加和删除，如Petal论文[24]中所述。锁定服务器的添加和删除方式类似。
8、备份（Backup）
Petal的快照功能为我们提供了一种方便的方式，使Frangipani文件系统的完整转储一致。Petal允许客户在任何时间点创建一个虚拟磁盘的精确拷贝。快照副本与普通虚拟磁盘相同，只是无法修改。为了提高效率，该实现使用了写时拷贝技术。快照是崩溃一致的；也就是说，快照反映了一种一致的状态，如果所有Frangipani服务器崩溃，Petal虚拟磁盘可能会处于这种状态。
因此，我们可以简单地通过提取Petal快照并复制到磁带上来备份一个Frangipani文件系统。该快照将包括所有的日志，因此可以通过将其恢复到新的Petal虚拟磁盘，并在每个日志上运行恢复功能来恢复它。由于崩溃的一致性，从快照中恢复与从整个系统的电源故障中恢复的问题相同。
我们可以通过对Frangipani的一个小改动来改进这个方案，创建在文件系统层面上一致的快照，并且不需要恢复。我们可以通过让备份程序强制所有的Frangipani服务器进入一个屏障来实现这一目标，该屏障使用一个由锁服务提供的普通全局锁。Frangipani服务器以共享模式获得这个锁，以进行任何修改操作，而备份程序则以独占模式请求它。当Frangipani服务器收到释放屏障锁的请求时，它通过阻止所有修改数据的新文件系统调用进入屏障，清理其缓存中的所有脏数据，然后释放该锁。当所有的Frangipani服务器都进入屏障时，备份程序能够获得最终锁；然后，它创建一个Petal快照并释放锁。此时，服务器以共享模式重新获取锁，并恢复正常操作。
使用后一种方案，新快照可以作为Frangipani卷装载，而无需恢复。新卷可以在线访问以检索单个文件，也可以以传统备份格式转储到磁带上，而不需要Frangipani进行恢复。但是，新卷必须以只读方式装载，因为Petal快照当前是只读的。将来，我们可能会扩展Petal以支持可写快照，或者在Petal上实现一个分层来模拟它们。
9、性能（Performance）
Frangipani的分层结构使其比单片系统更容易构建，但人们可能会认为分层会导致性能下降。在本节中，我们展示了尽管有分层，Frangipani的性能仍然很好。
与其他文件系统一样，通过在磁盘前面添加非易失性内存(NVRAM)缓冲区，可以直接解决Frangipani中的延迟问题。在我们的系统中放置NVRAM最有效的位置是直接在物理磁盘和Petal服务器软件之间。普通的PrestoServe卡和驱动程序足以满足此目的，无需更改Petal或Frangipani。Petal服务器上NVRAM的故障被Petal视为等同于服务器故障。
franangipani和Petal的几个方面结合起来提供了良好的吞吐量缩放。系统的两层都具有并行性:多个Frangipani服务器、多个petals服务器和多个磁盘分支都并行工作。当许多客户机使用系统时，这种并行性增加了总吞吐量。与集中式网络文件服务器相比，Frangipani处理热点的难度应该更小，因为文件系统处理是分开的，并转移到正在使用这些文件的机器上。Frangipani和Petal日志都可以在一次日志写入(组提交)中提交来自许多不同客户端的更新，从而在负载下提供改进的日志吞吐量。由于 Petal 在多个磁盘和服务器之间分离数据，因此执行大型写入的单个客户端也受益于并行性。
9.1、实验装置（Experimental Setup）
我们计划建立一个大型存储测试平台，其中大约有100个Petal节点连接到数百个磁盘和大约50个Frangipani服务器。Petal节点将是连接到现成磁盘和网络的小型阵列控制器。Frangipani服务器将是典型的工作站。这个测试平台将允许我们研究在大配置下的franangipani的性能。由于这还没有准备好，所以我们从一个较小的配置中报告数字。
对于下面报告的测量，我们使用了7台333 MHz DEC Alpha 500 5/333机器作为Petal服务器。每台机器将数据存储在9个DIGITAL RZ29磁盘上，这些磁盘是3.5英寸快速SCSI驱动器，每个磁盘存储4.3 GB，平均寻道时间为9毫秒，持续传输速率为6 MB/s。每台机器都通过自己的155 Mbit/s点对点链路连接到一个24端口的ATM交换机。包含8 MB NVRAM的PrestoServe卡在这些服务器上使用，如下所示。7个Petal服务器可以以100mb /s的总速率提供数据。使用复制的虚拟磁盘，Petal服务器可以以43 MB/s的总速率接收数据。
9.2、单机性能（Single Machine Performance）
本小节比较了Frangipani的代码流程与另一个Unix vnode文件系统，即DIGITAL的高级文件系统(AdvFS)的优劣。
我们使用AdvFS进行比较，而不是更熟悉的BSD-derived的UFS文件系统[27]，因为AdvFS比UFS快得多。特别是，AdvFS可以跨多个磁盘分条文件，从而在我们的测试机器上实现几乎两倍的UFS吞吐量。此外，与同步更新元数据的UFS不同，AdvFS使用像Frangipani这样的预写日志。这大大减少了文件创建等操作的延迟。AdvFS和UFS在读取小文件和目录时具有相似的性能。
BSD-derived是指基于Berkeley Software Distribution（BSD）操作系统的衍生版本或相关软件。
我们在两台相同的机器上运行AdvFS和Frangipani文件系统，其存储子系统具有相当的I/O性能。每台机器都有一个225 MHz的DEC Alpha 3000/700 CPU和192 MB的RAM，由统一缓冲缓存(UBC， unified buffer cache)管理。每个都通过自己的点对点链路连接到ATM交换机。
Frangipani文件系统不使用本地磁盘，而是通过Petal设备驱动程序访问复制的Petal虚拟磁盘。当使用64kb的块大小通过原始设备接口访问时，Petal驱动程序可以以大约16mb /s的速度读写数据，从而使到Petal服务器的ATM链路饱和。CPU利用率约为4%。Petal磁盘的读延迟大约是11ms。
AdvFS文件系统使用一个存储子系统，其性能与我们使用的Petal配置大致相当。它由8个DIGITAL RZ29磁盘组成，通过两个10 MB/s的快速SCSI字符串连接到两个背板控制器。当通过原始设备接口访问时，控制器和磁盘可以以大约17mb /s的速度提供数据，CPU利用率为4%。读取延迟大约是10 ms.(我们可以将AdvFS文件系统连接到一个Petal虚拟磁盘，以确保两个文件系统使用相同的存储子系统。先前的实验表明，如果在“Petal”上运行，AdvFS将会慢4%左右。为了最好地呈现AdvFS，我们选择不这样做。)
我们不打算将Petal的成本/性能与本地附加磁盘进行比较。显然，为Frangipani和AdvFS提供存储子系统所需的硬件资源有很大的不同。我们的目标是证明，与现有的、调优的商业文件系统相比，Frangipani代码流程是高效的。我们为Petal使用的硬件资源不是微不足道的，但是这些资源是在多个Frangipani服务器之间分摊的。
表1和表2比较了两个系统在标准基准测试中的性能。每个表有四列。在AdvFS Raw列中，在AdvFS直接访问本地磁盘的情况下运行基准测试。在AdvFS NVR专栏中，重新运行了在本地磁盘前面插入NVRAM的基准测试。在Frangipani Raw列中，在Frangipani通过设备接口访问Petal的情况下运行基准测试。在Frangipani NVR列中，通过在Petal和磁盘之间添加NVRAM缓冲，重新测试了Frangipani配置。所有数字都是在10次基准测试中平均的。在所有情况下，标准差都小于平均值的12%。
表1给出了Modified Andrew Benchmark的结果，这是一个广泛使用的文件系统基准测试。基准测试的第一阶段创建目录树。第二阶段将350 KB的C源文件集合复制到树中。第三阶段遍历新树并检查每个文件和目录的状态。第四个阶段读取新树中的每个文件。第五阶段编译和链接文件。
不幸的是，很难使用标准形式的Modified Andrew Benchmark进行比较测量。这是因为基准测试不考虑由文件系统实现延迟的工作。在基准测试的一个阶段中延迟的工作可以在后面的阶段中执行，从而不适当地增加到该阶段，而有些工作可以延迟到基准测试结束后，因此永远不会考虑。
与传统的Unix文件系统一样，AdvFS和Frangipani都将写入脏文件数据的成本推迟到下一个同步操作，这个同步操作可能由用户显式请求或在后台由定期更新程序触发。然而，与传统的Unix文件系统不同，AdvFS和Frangipani都是基于日志的，不将元数据更新同步写入磁盘。相反，元数据更新也会延迟到下一次同步，或者至少延迟到日志包装。
为了正确地考虑延迟工作的所有来源，我们将基准更改为在每个阶段之后卸载文件系统。我们选择卸载而不是使用同步调用，因为在Digital Unix上，同步将脏数据排在队列中等待写入，但不能保证它在返回之前已经到达磁盘。结果如表1所示，Frangipani与AdvFS在各阶段均具有可比性。
表2显示了运行Connectathon Benchmark的结果。Connectathon基准测试单个操作或小组相关操作，提供对Andrew基准中可见的差异来源的更深入的了解。与Andrew基准测试一样，该基准测试也不考虑延迟的工作，因此我们再次在每个阶段结束时卸载文件系统。
NVRAM的Frangipani延迟与AdvFS大致相当，但有四个明显的例外。测试1、4和6表明，使用Frangipani创建文件、设置属性和读取目录所花费的时间要长得多。然而，在实践中，这些延迟小到足以被用户忽略，所以我们并没有非常努力地去优化它们。
使用Frangipani创建文件需要更长的时间，部分原因是在测试期间128 KB的日志被填满了几次。如果我们将日志大小增加一倍，则时间减少到0.89和0.86秒。
Frangipani在文件读取测试(5b)上要慢得多。AdvFS在文件读取测试中做得很好，因为它的实现中有一个特殊的构件。在每次读取测试的迭代中，基准测试在读入文件之前都会进行一次系统调用，使缓冲区缓存中的文件失效。当前的AdvFS实现似乎忽略了这个无效指令。因此，读取测试测量AdvFS从缓存读取而不是从磁盘读取的性能。当我们用冷AdvFS文件缓存重新做这个测试时，性能与Frangipani的相似(1.80秒，有或没有NVRAM)。
接下来我们将报告单个Frangipani服务器在读取和写入大文件时实现的吞吐量。文件读取器位于一个循环中，读取一组10个文件。在循环的每次迭代之前，它从缓冲区缓存中刷新文件的内容。文件写入器处于一个循环中，反复写入一个大的(350mb)私有文件。该文件足够大，有一个稳定的写流量流到磁盘。读和写测试都运行了几分钟，我们观察到吞吐量没有显著变化。表3总结了时间平均稳态结果。NVRAM的存在与否对时间几乎没有影响。
一台Frangipani机器可以以15.3 MB/s的速度写数据，这大约是我们机器上ATM链路和UDP/IP软件限制的96%。Frangipani通过将对Petal的写入聚类成自然对齐的64 KB块来实现良好的性能。很难弥补最后的4%，因为Frangipani偶尔(例如，在同步期间)必须将部分数据写入较小的块中。使用较小的块大小会减少通过UDP/IP堆栈的最大可用吞吐量。Frangipani服务器的CPU利用率约为42%，而Petal服务器的CPU不是瓶颈。
一台Frangipani机器可以以10.3 MB/s的速度读取数据，CPU利用率为25%。我们相信这种性能可以通过改变Frangipani中使用的预读算法来改善。Frangipani目前使用从BSD-derived文件系统UFS借鉴的预读算法，该算法不如AdvFS使用的算法有效。
相比之下，AdvFS在访问连接到两个控制器的8个RZ29磁盘上的大文件时，写入数据的速度约为13.3 MB/s。CPU利用率约为80%。在CPU利用率为50%的情况下，AdvFS的读性能约为13.2 MB/s。CPU和控制器都没有瓶颈，所以我们相信AdvFS的性能可以通过更多的调优来提高一点。
有趣的是，尽管Frangipani使用简单的策略来布局数据，但它的延迟和写吞吐量与使用更复杂策略的传统文件系统相当。
Frangipani具有良好的写延迟，因为延迟关键型元数据更新是异步记录的，而不是就地同步执行的。像UFS这样同步更新元数据的文件系统必须更加小心数据放置。在这里没有描述的单独实验中，我们发现即使在Frangipani同步更新其日志时，性能仍然相当好，因为日志分配在大的物理上连续的块中，并且NVRAM吸收了大部分写延迟。
Frangipani实现了良好的写吞吐量，因为大文件在许多磁盘和机器上以连续的64 KB单位物理分割，而且Frangipani可以利用这种结构中固有的并行性。出于同样的原因，Frangipani对于大文件具有良好的读取吞吐量。
回想第3节，对于小于64 KB的文件，不能在磁盘上连续分配单个4 KB块。此外，Frangipani并不对小文件进行预读，因此它不能总是隐藏磁盘查找访问时间。因此，Frangipani在小文件上的读取性能可能很差。为了量化小文件读取性能，我们进行了一个实验，在一台Frangipani机器上，30个进程试图在缓冲区缓存失效后读取单独的8 KB文件。Frangipani的吞吐量为6.3 MB/s, CPU是瓶颈。使用4 KB块通过原始设备接口访问的petals可以传输8 MB/s。因此，在这种情况下，franangipani获得了大约80%的最大吞吐量。
9.3、缩放（Scaling）
本节研究 Frangipani 的缩放特性。理想情况下，我们希望看到操作延迟保持不变，吞吐量随着服务器的增加而线性扩展。
图5显示了运行Modified Andrew Benchmark时缩放对Frangipani的影响。在本实验中，随着机器数量的增加，我们测量一台franangipani机器完成基准测试所需的平均时间。这个实验模拟了几个用户在共享数据池上进行程序开发的行为。我们注意到，随着Frangipani机器的增加，对延迟的负面影响最小。实际上，在单机器和六台机器实验之间，平均延迟只增加了8%。这并不奇怪，因为基准测试显示很少有写共享，并且我们希望延迟不受服务器数量增加的影响。
图6展示了Frangipani在未缓存数据上的读吞吐量。在这个测试中，我们在多个服务器上复制单服务器实验中的读取器。测试运行了几分钟，我们观察到稳定状态吞吐量的变化可以忽略不计。如图所示，franangipani在本次测试中表现出良好的缩放性。我们正在将Frangipani安装到更多的机器上，我们预计总的读取性能会不断提高，直到达到Petal服务器的容量饱和。
图7展示了Frangipani的写吞吐量。这里，单服务器实验中的写入器被复制到多个服务器上。每个服务器都有一个不同的大文件。实验运行了几分钟，在这段时间内，我们观察到稳定状态吞吐量的变化很小。由于实验中没有锁争用，因此性能被认为可以很好地扩展，直到 ATM 链接到 Petal 服务器已经饱和。由于虚拟磁盘是复制的，因此来自Frangipani服务器的每次写入都会变成对Petal服务器的两次写入。
9.4、锁争用的影响（Effects of Lock Contention）
由于Frangipani对整个文件使用粗粒度锁，因此研究锁争用对性能的影响非常重要。我们在这里报告三个实验。
第一个实验测量读/写共享对文件的影响。一个或多个读取器与单个写入器竞争同一个大文件。最初，文件不是由读取器或写入器缓存的。读取器按顺序读取文件，而写入器则重写整个文件。因此，写入器反复获得写锁，然后获得一个回调来降级它，以便读取器可以获得读锁。这个回调导致写入器将数据刷新到磁盘。同时，每个读操作重复地获得读锁，然后获得一个回调来释放它，这样写操作就可以获得写锁。这个回调会导致读取器使其缓存无效，因此在重新获取锁后的下一次读取必须从磁盘中获取数据。
我们在这个实验中观察到的第一个结果是出乎意料的。我们的分布式锁管理器被设计为公平地授予锁，模拟表明实现是这样的。如果单个写入器和n个读取器以统一的速率发出锁请求，那么它们将以轮询的方式得到服务，因此向写入器连续授予写锁与向读取器授予n次读锁会分开。在两次降级回调之间的间隔期间，可以预期读请求的数量和总读吞吐量会随着读取器的增加而增加。在n很大的极限下，缩放是线性的。然而，我们在实验中并没有观察到这种行为。相反，在运行两个读取器后，读取吞吐量趋于平缓，约为2 MB/s，如图8中的虚线所示。如前面图6所示，在没有锁争用的情况下，这仅是两台Frangipani服务器所能实现的10%左右。
我们推测这种异常行为是由预读引起的，所以我们在没有预读的情况下重复了这个实验来检查。预读在存在严重的读/写争用时是不利的，因为当回调读器以释放其锁时，它必须使其缓存无效。如果缓存中有任何尚未交付给客户端的预读数据，则必须丢弃它，并且读取它的工作被证明是浪费的。因为读取器在做额外的工作，所以它们不能以与写入器相同的速度发出锁请求。在禁用预读的情况下重新进行实验，得到了预期的缩放结果，如图8中的实线所示。
我们可以让用户显式地禁用特定文件的预读，或者设计一种识别这种情况并自动禁用预读的启发式方法，从而使用户能够获得这种性能改进。前者实现起来很简单，但会影响到Frangipani本身以外的操作系统内核的一部分，从而不方便跨内核的未来版本提供支持。后一种方法似乎更好，但我们尚未设计或测试适当的启发式。
第二个实验是第一个实验的变体。这里，读取器和以前一样运行，但是写入器修改的文件数据量不同。由于Frangipani锁定了整个文件，因此无论写入器的行为如何，读取器都必须使其整个缓存无效。但是，当写入器更新的数据块较少时，读取器可以更快地获得锁，因为写入器只需将更少量的数据刷新到磁盘。图9显示了当读取器和写入器同时共享不同数量的数据时，Frangipani(禁用预读)的性能。正如预期的那样，当共享数据更小时，我们可以获得更好的性能。
第三个实验测量写/写共享对文件的影响。作为基本情况，一个Frangipani服务器孤立地写一个文件。然后，我们添加了编写相同文件的Frangipani服务器，并测量了性能的下降。写入器以64kb为块修改文件数据。由于Frangipani执行全文件锁定，因此编写器使用的偏移量与此测试无关。我们发现，所有写入器看到的总带宽从单写入器情况下的15 MB/s下降到两个或更多写入器情况下的略高于1 MB/s。这并不奇怪，因为当多个写程序试图修改一个文件时，几乎每个写系统调用都会导致一个锁撤销请求。这个撤销请求导致锁持有者将其脏数据刷新到Petal。由于每次写系统调用都会撤销锁，而且每次调用只会弄脏64 KB的数据，因此吞吐量非常有限。块大小越小，吞吐量就越小。
我们没有太多处理并发写共享的工作负载的经验。如果有必要，我们认为扩展Frangipani来实现字节范围锁定[6]或块锁定是很简单的。这将提高读取和写入同一文件的不同部分的工作负载的性能，使其与当前系统中写入不同文件的性能相似。多台机器并发地读写同一文件(文件系统被用作进程间通信通道)的相同块的工作负载将执行如上所述。franangipani根本不适合这种工作量。
10、相关工作（Related Work）
像Frangipani一样，Cambridge(或Universal)文件服务器采用两层方法来构建文件系统[4,28]。然而，这两层之间的划分与我们的大不相同。底层的CFS为客户端提供了两个抽象:文件和索引。构建在CFS之上的文件系统可以使用这些抽象来实现文件和目录。CFS和Petal之间的一个主要区别是，在CFS中，一台机器管理所有的存储。
CFS是指Cambridge (or Universal) File Server，是一种基于索引的文件系统。
NFS[31,33]本身并不是一个文件系统，而只是一个远程文件访问协议。NFS协议提供了一个较弱的缓存一致性概念，其无状态设计要求客户端频繁访问服务器以维持这种级别的一致性。Frangipani提供了一个高度一致的单一系统视图，它使用一个协议来维护更多的状态，但消除了对服务器不必要的访问。
Andrew文件系统(AFS)[19]及其分支DCE/DFS[21]提供了比NFS更好的缓存性能和一致性。AFS的可扩展性与Frangipani不同。Frangipani提供了一个统一的集群文件系统，它从单个存储池中提取数据，并且可以扩展到在一个公共管理下跨多台机器的多个磁盘驱动器。相反，AFS具有全局名称空间和安全体系结构，允许在广泛的区域内插入许多独立的文件服务器和客户端。我们认为，AFS和Frangipani的扩展方法是互补的;对于Frangipani服务器来说，使用AFS或DCE/DFS名称空间和访问协议将文件系统导出到广域客户机是很有意义的。
像Frangipani一样，Echo文件系统[5,18,26,35]基于日志，复制数据以保证可靠性，复制访问路径以保证可用性，允许卷跨越多个磁盘，并提供一致的缓存。然而，Echo不具备Frangipani的可扩展性。每次只能由一台服务器管理每个Echo卷，并将故障转移到一个指定的备份。一个卷只能跨越连接到一台机器上的尽可能多的磁盘。在磁盘服务之上有一个内部的文件服务层，但是Echo实现要求这两个层在同一台机器上的相同地址空间中运行，使用Echo的经验表明服务器CPU是一个瓶颈。
VMS集群文件系统[14]将文件系统处理工作分配到作为集群成员的各个机器上，就像Frangipani所做的那样。每个集群成员在共享物理磁盘上运行自己的文件系统代码实例，由分布式锁服务提供同步。共享的物理磁盘可以通过专用的集群互连(磁盘控制器可以直接连接到集群互连)访问，也可以通过普通网络(如以太网和充当磁盘服务器的机器)访问。Frangipani在几个方面改进了这种设计:由petals提供的可扩展的共享虚拟磁盘取代了共享物理磁盘;Frangipani文件系统基于日志，可以快速恢复故障;Frangipani提供了大量的数据和元数据缓存，以获得更好的性能。
Spiralog文件系统[20]还将其文件系统处理工作分配给运行在共享存储系统层之上的单个集群成员。Spiralog中各层之间的接口既不同于最初的VMS Cluster文件系统，也不同于petals。底层既不是文件，也不是简单的磁盘;相反，它提供了一个稳定存储的字节数组，并允许原子操作更新数组中任意分散的字节集。Spiralog的分层简化了文件系统，但使存储系统相当复杂。与此同时，Spiralog的存储系统没有Petal的可扩展性或容错性;Spiralog体积只能跨越连接到一台机器的磁盘，并且在该机器崩溃时变得不可用。
虽然是作为集群文件系统设计的，但Calypso[11]类似于Echo，而不是VMS Clusters或Frangipani。和Echo一样，Calypso将文件存储在多端口磁盘上。直接连接到每个磁盘的机器之一充当存储在该磁盘上的数据的文件服务器;如果那台机器坏了，另一台就会接替。Calypso集群的其他成员作为文件系统客户端访问当前服务器。与Frangipani和Echo一样，客户端也有缓存，与多读/单写锁定协议保持一致。
Shillner和Felten在共享逻辑磁盘[34]之上构建了一个分布式文件系统。他们系统中的分层与我们的类似:在底层，多台机器合作实现单个逻辑磁盘。在上层，多个独立的机器在一个逻辑磁盘上运行相同的文件系统代码，所有机器都提供对相同文件的访问。与Petal不同，它们的逻辑磁盘层不提供冗余。当节点发生故障并重新启动时，系统可以恢复，但不能动态配置故障节点或配置其他节点。他们的文件系统对元数据写入进行了仔细的排序，而不是像Frangipani那样进行日志记录。与日志记录一样，他们的技术避免了在服务器崩溃后进行完整的元数据扫描(fsck)来恢复一致性的需要，但与日志记录不同的是，它可能会在崩溃时丢失对空闲块的跟踪，因此需要偶尔进行垃圾收集扫描才能再次找到它们。目前我们无法将他们的系统性能与我们的系统进行比较，因为他们的文件系统层的性能数据不可用。
xFS文件系统[1,36]在本质上最接近于Frangipani。事实上，两种体系的目标在本质上是相同的。两者都尝试在多台机器上分配文件的管理责任，并提供良好的可用性和性能。在与xFS相同的意义上，Frangipani实际上是“无服务器”的——该服务分布在所有机器上，并且可以在每台机器上配置Frangipani服务器和Petal服务器。Frangipani的锁定比xFS更粗粒度，后者支持块级锁定。
我们的工作在两个主要方面与xFS不同:
首先，我们的文件系统的内部组织及其与存储系统的接口与xFS有很大的不同。与Frangipani不同，xFS为每个文件预先指定了一个管理器，并且它的存储服务器是日志结构的。相反，Frangipani被组织成一组协作的机器，这些机器使用Petal作为共享存储，并使用单独的锁服务进行并发控制。我们的模型更简单，让人想起多线程共享内存程序，它们通过公共存储进行通信，并使用锁进行同步。这个模型允许我们用比xFS更少的机器来处理文件系统恢复和服务器添加和删除，这使得我们的系统更容易实现和测试。
其次，我们已经解决了文件系统恢复和重新配置。到目前为止，这些问题一直是xFS工作的开放性问题。
我们本来希望将Frangipani的性能与xFS的性能进行比较，但是在当前的xFS原型[1]上还有大量的性能工作要完成。此时对系统进行比较是不成熟的，而且对xFS不公平。
11、结论（Conclusions）
Frangipani文件系统为所有用户提供对同一组文件的一致的、共享的访问，并且随着用户群组的增长，可以扩展以提供更多的存储空间、更高的性能和负载平衡。尽管组件出现故障，它仍然可用。它只需要很少的人工管理，而且随着越来越多的组件被添加到不断增长的安装中，管理也不会变得更加复杂。
构建Frangipani是可行的，因为它有两层结构，由多个文件服务器组成，这些服务器在共享的Petal虚拟磁盘上运行相同的简单文件系统代码。使用Petal作为底层提供了几个好处。Petal实现了高可用性的数据复制，从而避免了Frangipani这样做的需要。所有Frangipani服务器都可以统一访问Petal虚拟磁盘，因此任何服务器都可以提供任何文件，当服务器出现故障时，任何机器都可以运行恢复。Petal的大而稀疏的地址空间允许我们简化Frangipani的磁盘数据结构。
尽管Frangipani具有简单的数据布局和分配策略以及粗粒度锁，但我们对它的性能还是很满意的。在我们最初的性能测量中，Frangipani已经可以与生产的DIGITAL Unix文件系统相媲美，我们希望通过进一步调优来改进。Frangipani已经显示出良好的扩展特性，直到我们的测试平台配置的大小(7个Petal节点和6个Frangipani节点)。结果让我们乐观地认为，系统将继续扩展到更多的节点。
我们未来的计划包括为我们自己的日常使用部署Frangipani。我们希望通过负载下的原型获得更多的经验，通过在更大的配置中测试它来验证它的可伸缩性，试验细粒度锁，并完成我们在备份上的工作。最后，当然，我们希望看到Frangipani的想法进入商业产品。
