Frangipani论文(1-8节)
Last updated
Last updated
Frangipani: 一个可扩展的分布式文件系统
自翻，只翻译到第八节。
这个分布式文件系统将为其所有用户提供连贯的、共享的文件访问，同时可以任意扩展，为不断增长的用户群体提供更多的存储空间和更高的性能。它将在组件故障的情况下保持高度可用。它需要最少的人力管理，而且管理不会随着更多组件的加入而变得更加复杂。
Frangipani是一个新的文件系统，它接近于这个理想，因为它的两层结构而相对容易建立。下层是Petal（在以前的一篇论文中描述过），这是一个分布式存储服务，提供可逐步扩展、高度可用、自动管理的虚拟磁盘。在上层，多台机器在共享的Petal虚拟磁盘上运行相同的Frangipani文件系统代码，使用分布式锁服务来确保一致性。
Frangipani是为了在一个共同管理的机器集群中运行，并能安全地进行通信。这些机器相互信任，共享虚拟磁盘的方法很实用。当然，Frangipani文件系统可以使用普通的网络文件访问协议输出到不受信任的机器上。
我们已经在一组运行DIGITAL Unix 4.0的Alphas上实现了Frangipani。初步测量表明，Frangipani具有出色的单服务器性能，而且随着服务器的增加，其扩展性很好。
对于使用当今技术建立的大型、不断增长的计算机装置来说，文件系统管理是一项艰巨的任务。为了保存更多的文件和服务更多的用户，必须增加更多的磁盘，连接到更多的机器上。这些组件中的每一个都需要人工管理。文件组经常被手动分配到特定的磁盘上，然后在组件填满、失效或成为性能热点时手动移动或复制。使用RAID技术将多个磁盘驱动器连接成一个单元只是一个部分解决方案；一旦系统增长到需要多个RAID和多个服务器机器时，管理问题仍然会出现。
Frangipani是一个新的分布式文件系统，它将多台机器上的磁盘集合作为一个单一的共享存储池来管理。这些机器被认为是在一个共同的管理之下，并且能够安全地进行通信。在建立分布式文件系统方面已经有很多早期的尝试，这些系统在吞吐量和容量方面都有很好的扩展[1, 11, 19, 20, 21, 22, 26, 31, 33, 34]。Frangipani的一个突出特点是它有一个非常简单的内部结构--一组合作的机器使用一个共同的存储，并通过锁来同步访问该存储。这种简单的结构使我们能够用非常少的机器来处理系统恢复、重新配置和负载平衡。Frangipani的另一个关键方面是，它结合了一系列的功能，使得Frangipani比我们所知的现有文件系统更容易使用和管理。
1.所有用户对同一组文件都有一致的看法。 2.更多的服务器可以很容易地添加到现有的Frangipani安装中，以增加其存储容量和吞吐量，而不改变现有服务器的配置，或中断其操作。这些服务器可以被看作是 "砖块(bricks)"，可以逐步堆叠，根据需要建立一个大的文件系统。 3.系统管理员可以添加新的用户，而不必担心哪台机器将管理他们的数据或哪块磁盘将存储这些数据。 4.系统管理员可以对整个文件系统进行全面和持续的备份，而不必使其瘫痪。备份可以选择在线保存，允许用户快速访问被意外删除的文件。 5.文件系统可以容忍和恢复机器、网络和磁盘的故障，而不需要操作员的干预。
Frangipani是分层在Petal[24]之上的，这是一个易于管理的分布式存储系统，为其客户提供虚拟磁盘。像物理磁盘一样，Petal虚拟磁盘提供了可以按块(blocks)读取或写入的存储。与物理磁盘不同，虚拟磁盘提供一个稀疏的2^64字节的地址空间，物理存储只在需要时分配。Petal可以选择复制数据以实现高可用性。Petal还提供高效的快照[7, 10]以支持一致的备份。Frangipani从底层存储系统中继承了大部分的可扩展性、容错性和易管理性，但需要精心设计，将这些特性扩展到文件系统层面。下一节将更详细地描述Frangipani的结构和它与Petal的关系。
图1说明了Frangipani系统中的分层。多个可互换的Frangipani服务器通过在共享的Petal虚拟磁盘上运行，提供对相同文件的访问，用锁协调它们的行动以确保一致性。文件系统层可以通过增加Frangipani服务器来扩大规模。它通过从服务器故障中自动恢复并继续使用幸存的服务器来实现容错。它通过分割文件系统负载并将其转移到使用文件的机器上，提供比集中式网络文件服务器更好的负载平衡。Petal和锁服务也是分布式的，以实现可扩展性、容错和负载平衡。
图一：几个可互换的Frangipani服务器提供对一个Petal虚拟磁盘上的一组文件的访问。
Frangipani服务器相互信任，Petal服务器和锁服务。Frangipani被设计为在一个单一管理域内的工作站集群中运行良好，尽管Frangipani文件系统可以输出到其他域中。因此，Frangipani可以被看作是一个集群文件系统。
我们已经在DIGITAL Unix 4.0下实施了Frangipani。由于Frangipani在现有的Petal服务上的干净分层，我们能够在短短几个月内实现一个工作系统。
Frangipani是针对有程序开发和工程工作负载的环境。我们的测试表明，在这样的工作负载上，Frangipani具有出色的性能，并能扩展到网络施加的限制。
图2描述了一个典型的对机器的功能分配。上面显示的机器运行用户程序和Frangipani文件服务器模块；它们可以是无盘的。底部的机器则运行Petal和分布式锁服务。
Frangipani的组件不需要完全按照图2所示的方式分配给机器。Petal和Frangipani服务器不需要在不同的机器上；每台Petal机器也运行Frangipani是有意义的，特别是在Petal机器负载不重的安装中。分布式锁服务是独立于系统其他部分的；我们显示每个Petal服务器机器上运行的是锁服务器，但它们也可以在Frangipani主机或任何其他可用的机器上运行。
图2：Frangipani结构。在一个典型的Frangipani配置中，一些机器运行用户程序和Frangipani文件服务器模块；其他机器运行Petal和分布式锁服务。在其他配置中，同一台机器可能同时扮演两种角色。
如图2所示，用户程序通过标准的操作系统调用接口访问Frangipani。在不同机器上运行的程序都能看到相同的文件，他们的观点是一致的；也就是说，在一台机器上对文件或目录所做的改变在其他机器上都能立即看到。程序得到的语义保证与本地Unix文件系统基本相同：对文件内容的修改通过本地内核缓冲池分阶段进行，在下一次适用的fsync或sync系统调用之前，不保证到达非易失性存储，但元数据[我们将元数据定义为除普通文件内容之外的任何磁盘数据结构。]修改被记录下来，在系统调用返回时，可以选择保证非易失性。与本地文件系统的语义略有不同的是，Frangipani只近似地维护文件的最后访问时间，以避免在每次数据读取时进行元数据写入。
每台机器上的Frangipani文件服务器模块在操作系统内核中运行。它在内核的文件系统开关中注册为可用的文件系统实现之一。文件服务器模块使用内核的缓冲池来缓存最近使用的文件的数据。它使用本地Petal设备驱动程序读写Petal虚拟磁盘。所有的文件服务器在共享的Petal磁盘上读写相同的文件系统数据结构，但每个服务器在Petal磁盘的不同区域保存自己的待处理变化的重做日志(redo log)。日志被保存在Petal中，这样当一个Frangipani服务器崩溃时，另一个服务器可以访问日志并运行恢复。Frangipani服务器之间不需要直接通信；它们只与Petal和锁服务通信。这使服务器的增加、删除和恢复变得简单。
Petal设备驱动隐藏了Petal的分布式特性，使Petal在操作系统的高层看来就像一个普通的本地磁盘。驱动程序负责联系正确的Petal服务器，并在必要时故障转移到另一个服务器。任何数字Unix文件系统都可以在Petal之上运行，但只有Frangipanip可以从多台机器上连贯地访问相同的文件。
Petal服务器合作运行，为Frangipani提供大型、可扩展、容错的虚拟磁盘，在连接到每个服务器的普通物理磁盘之上实现。Petal可以容忍一个或多个磁盘或服务器的故障，只要大多数Petal服务器保持运行和通信，每个数据块至少有一个副本保持物理访问。关于Petal的其他细节可在另一篇论文中找到[24]。
锁服务是一个通用的服务，为网络上的clients提供多读/单写锁。它的实现是分布式的，以实现容错和可扩展的性能。Frangipani使用锁服务来协调对虚拟磁盘的访问，并在多个服务器上保持缓冲区缓存的一致性。
在图2所示的配置中，每台承载用户程序的机器也承载着一个Frangipani文件服务器模块。这种配置有可能实现良好的负载平衡和扩展，但也带来了安全问题。任何Frangipani机器都可以读取或写入共享Petal虚拟磁盘的任何区块，所以Frangipan必须只运行在具有可信操作系统的机器上；如果Frangipani机器向Petal认证自己是代表某个特定用户行事，就像NFS等远程文件访问协议那样，是不够的。全面的安全还要求Petal服务器和锁服务器在可信的操作系统上运行，所有这三种类型的组件都要相互认证。最后，为确保文件数据的私密性，应防止用户窃听Petal和Frangipani机器之间的网络。
我们可以通过将机器放置在一个防止用户在上面启动修改过的操作系统内核的环境中，并将它们与一个用户进程不被允许访问的私有网络互连，来完全解决这些问题。这并不一定意味着机器必须被锁在一个有私人物理网络的房间里；可以使用已知的安全启动、认证和加密链接的加密技术来代替[13, 37]。此外，在许多应用中，部分解决方案可能是可以接受的；典型的现有NFS安装并不安全，不能防止网络窃听，甚至不能防止用户在他的工作站上启动一个修改过的内核来修改数据。到目前为止，我们还没有实施任何这些安全措施，但我们可以通过让Petal服务器只接受属于受信任的Frangipani服务器机器的网络地址列表来达到大致的NFS安全水平。
Frangipani文件系统可以通过图3所示的配置，输出到管理员域外的不受信任的机器上。这里我们区分了Frangipani的客户机和服务器机。只有受信任的Frangipani server与Petal和锁服务进行通信。如上所述，它们可以位于一个受限的环境中，并通过一个私人网络相互连接。远程的、不受信任的客户机通过一个单独的网络与Frangipani服务器交谈，不能直接访问Petal服务器。
客户可以使用主机操作系统支持的任何文件访问协议与Frangipani服务器对话，如DCE/DFS、NFS或SMB，因为Frangipani看起来就像运行Frangipani服务器的机器上的本地文件系统。当然，支持一致性访问的协议（如DCE/DFS）是最好的，这样Frangipani在多个服务器上的一致性就不会在下一级被丢弃。理想情况下，该协议还应该支持从一个Frangipani服务器到另一个服务器的故障转移。刚才提到的协议并不直接支持故障转移，但让新机器接管故障机器的IP地址的技术已经在其他系统中使用[3, 25]，在这里也可以应用。
除了安全之外，使用这种客户/服务器配置还有第二个原因。由于Frangipani在内核中运行，它不能在不同的操作系统甚至不同的Unix版本中快速移植。客户端可以从一个不支持的系统中通过远程访问支持的系统来使用Frangipani。
将文件系统分为两层--低层提供存储库，高层提供名称、目录和文件--这种想法并非Frangipani独有。我们知道的最早的例子是通用文件服务器[4]（Universal File Server）。然而，Petal提供的存储设施与早期系统有很大不同，导致了不同的高层结构。第10节包含了与以前系统的详细比较。
Frangipani被设计为与Petal提供的存储抽象一起工作。我们还没有充分考虑利用其他存储抽象（如NASD[13]）所需的设计变化。
Petal提供了高度可用的存储，可以随着资源的增加而扩大吞吐量和容量。然而，Petal没有协调或在多个客户端之间共享存储的规定。此外，大多数应用程序不能直接使用Petal的客户接口，因为它是类似于磁盘而不是文件的。Frangipani提供了一个文件系统层，使Petal对应用程序有用，同时保留并扩展其良好的特性。
Frangipani的一个优势是它允许透明的服务器添加、删除和故障恢复。它通过将写前日志和锁与统一访问、高可用的存储结合起来，能够轻松做到这一点。
Frangipani的另一个优点是它能够在系统运行时创建一致的备份。Frangipani的备份机制将在第8节中讨论。
Frangipani的设计有三个方面可能会有问题。将Frangipani与复制的Petal虚拟磁盘一起使用，意味着日志有时会发生两次，一次是在Frangipani的日志上，一次是在Petal本身中。其次，Frangipani在放置数据时不使用磁盘位置信息，事实上它不能，因为Petal虚拟了磁盘。最后，Frangipani锁定的是整个文件和目录，而不是单个块。我们没有足够的使用经验来评估我们的设计在一般情况下的这些方面，但如果不考虑这些，Frangipani在我们测试的工程负载上的测量性能是很好的。
Frangipani使用Petal的大而稀疏的磁盘地址空间来简化其数据结构。这个总体思路让人想起过去在大内存地址空间的计算机编程方面的工作[8]。有如此多的地址空间可用，以至于它可以被慷慨地分割开来。
一个Petal虚拟磁盘有2^64字节的地址空间。Petal只在虚拟地址被写入时，将物理磁盘空间提交给虚拟地址。Petal还提供了一个取消提交的基元（primitive ），它释放了支持一系列虚拟磁盘地址的物理空间。
为了保持其内部数据结构的小型化，Petal以相当大的块来提交和解约空间，目前是64KB。也就是说，每一个64KB的地址范围 【a*2^16,(a+1)*2^16】中，有一些数据已经被写入，但没有被解约，有64KB的物理磁盘空间分配给它。因此，Petal客户不能使他们的数据结构过于稀疏，否则过多的物理磁盘空间将因碎片化而被浪费。图4显示了Frangipani是如何划分其虚拟磁盘空间的。
第一个区域存储共享的配置参数和内务管理信息。我们允许这个区域有一兆字节（TB）的虚拟空间，但实际上目前只使用了其中的几千字节。
第二个区域存储日志。每台Frangipani服务器获得一部分空间来存放其私人日志。我们为这个区域保留了一个TB（2^40字节），划分为256个日志。这一选择限制了我们目前的实施，使其只能容纳256个服务器，但这很容易被调整。
第三个区域用于分配位图(bitmaps)，以描述其余区域中哪些块是空闲的。每个Frangipani服务器锁定一部分位图空间供其专用。当一个服务器的位图空间满了，它就会找到并锁定另一个未使用的部分。位图区域的长度为3TB。
第四个区域存放节点。每个文件都需要一个inode来保存其元数据，如时间戳和指向其数据位置的指针。[在本节中，文件一词包括目录、符号链接等。］ 符号链接将其数据直接存储在inode中。我们将节点的长度定为512字节，即一个磁盘块的大小，从而避免了服务器之间不必要的争夺（"虚假共享"），如果两个服务器需要访问同一块中的不同节点，就会出现这种情况。我们分配了一TB的节点空间，允许2^31个节点的空间。分配位图中的位和节点之间的映射是固定的，所以每个Frangipaniserver只从与分配位图的部分相对应的节点空间中为新文件分配节点。但任何Frangipani服务器都可以读取、写入或释放任何现有文件的节点。
第五个区域存放小数据块，每个4 KB（2^12字节）大小。一个文件的前64 KB（16个块）被存储在小块中。如果一个文件增长到超过64KB，剩下的就存储在一个大块中。我们为小块分配2^47字节，因此允许最多有2^35个小块，是最大节点数的16倍。
Petal地址空间的其余部分用于存放大型数据块。每个大块都保留了1TB的地址空间。
我们使用4KB块的磁盘布局政策可能会比更谨慎地分配磁盘空间的政策遭受更多的碎片化。此外，为每个节点分配512字节的空间也有些浪费。我们可以通过将小文件存储在inode本身来缓解这些问题[29]。我们的设计所获得的是简单性，我们相信这对于额外的物理磁盘空间的成本来说是一个合理的权衡。
目前的计划将Frangipani限制在略低于2^24(1600万)个大文件，其中大文件是指任何大于64 KB的文件。另外，任何文件都不能大于16个小块加一个大块（64KB加1TB）。如果这些限制被证明太小，我们可以很容易地减少大块的大小，从而使更多的数量可用，并允许大文件跨越一个以上的大块，从而提高最大文件大小。如果2^64字节的地址空间限制被证明是不够的，一个Frangipani服务器可以在多个虚拟磁盘上支持多个Frangipani文件系统。
我们根据早期文件系统的使用经验，选择了这些文件系统参数。我们相信我们的选择将为我们提供良好的服务，但只有时间和使用才能证实这一点。Frangipani的设计足够灵活，我们可以以文件系统的备份和恢复为代价来试验不同的布局。
Frangipani使用元数据的写前(write-ahead)重现(redo)日志，以简化故障恢复并提高性能；用户数据不被记录。
每个Frangipani服务器在Petal中都有自己的私人日志。当一个Frangipani文件服务器需要进行元数据更新时，它首先创建一个描述更新的记录，并将其附加到内存中的日志中。这些日志记录会按照它们所描述的更新被请求的顺序定期写入Petal。(我们可以选择让日志记录同步写入。这提供了稍好的故障语义，但代价是增加了元数据操作的延迟）。只有在日志记录被写入Petal之后，服务器才会修改其永久位置上的实际元数据。永久位置由Unix update demon定期更新（大约每30秒）。
日志的大小是有限制的，在目前的实现中是128KB。考虑到Petal的分配策略，一个日志将由两个不同的物理磁盘上的两个64KB片段组成。为每个日志分配的空间被作为一个循环缓冲区管理。当日志填满时，Frangipani会回收最旧的25%的日志空间，用于新的日志条目。通常情况下，回收区域的所有条目都是指已经写入Petal的元数据块（在之前的同步操作中），在这种情况下，不需要进行额外的Petal写入。如果有尚未写入的元数据块，这项工作将在日志被回收之前完成。考虑到日志的大小和Frangipani日志记录的典型大小（80-128字节），如果在两个周期性的同步操作中，有大约1000-1600个修改元数据的操作，日志就会被填满。
如果一个Frangipani服务器崩溃了，系统最终会检测到失败，并在该服务器的日志上运行恢复。故障可能是由故障服务器的客户端检测到的，或者当锁服务要求故障服务器返回它所持有的锁而没有得到答复时。恢复 demon 被隐含地赋予失败服务器的日志和锁的所有权。demon 找到日志的开始和结束，然后按顺序检查每条记录，执行每个尚未完成的描述的更新。在日志处理完成后，恢复demon释放其所有的锁并释放日志。然后其他Frangipani服务器可以不受故障服务器的阻碍，故障服务器本身也可以选择重新启动（有一个空日志）。只要底层的Petal卷保持可用，系统可以容忍无限数量的Frangipani服务器故障。
为了确保恢复能够找到日志的结尾（即使磁盘控制器不按顺序写入数据），我们在日志的每个512字节的块上附加一个单调增加的日志序列号。通过找到一个比前一个序列号低的序列号，可以可靠地检测到日志的结束。
Frangipani确保在有多个日志的情况下，日志和恢复工作正常。这需要注意几个细节。
首先，Frangipani的锁协议，在下一节中描述，确保不同服务器对相同数据的更新请求被序列化。只有在脏数据被原始锁持有者或代表其运行的恢复恶魔（damon)写入Petal后，覆盖脏数据的写锁才能改变所有者。这意味着最多只有一个日志可以保存任何给定块的未完成的更新。
其次，Frangipani确保恢复只适用于自服务器获得覆盖它们的锁以来所记录的更新，并且它仍然持有这些锁。这是为了确保锁协议所规定的序列化不被违反而需要的。我们通过强制执行一个更强的条件来实现这一保证：恢复绝不重放描述已经完成的更新的日志记录。为了完成后者，我们在每个512字节的元数据块上保留一个版本号。像目录这样跨越多个块的元数据，有多个版本号。对于日志记录中更新的每个块，记录中包含了对变化的描述和新的版本号。在恢复过程中，只有当块的版本号小于记录的版本号时，才会应用对块的更改。
因为用户数据的更新没有被记录下来，只有元数据块有预留空间给版本号。这就产生了一个复杂的问题。如果一个块被用于元数据，被释放，然后被重新用于用户数据，那么在版本号被任意的用户数据覆盖后，引用该块的旧日志记录可能不会被正确地跳过。Frangipani通过重用释放的元数据块来避免这个问题，该块只用于保存新的元数据。
最后，Frangipani确保在任何时候，只有一个恢复恶魔(recovery demon)在试图重放特定服务器的日志区域。锁服务通过授予活动的恢复恶魔对日志的独占锁来保证这一点。
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保留多个日志。
由于多个Frangipani服务器都在修改共享的磁盘数据结构，因此需要仔细的同步，以使每个服务器对数据有一个一致的看法，同时允许有足够的并发性，以便在负载增加或服务器增加的情况下扩展性能。Frangipani使用多读/单写锁来实现必要的同步。当锁服务检测到冲突的锁请求时，会要求锁的当前持有者释放或降级以消除冲突。
一个读锁允许服务器从磁盘上读取相关数据并进行缓存。如果一个服务器被要求释放它的读锁，它必须在遵守之前使其缓存条目失效。写锁允许服务器读取或写入相关数据并进行缓存。只有当一个服务器持有相关的写锁时，它对一个磁盘块的缓存副本才能与磁盘上的版本不同。因此，如果一个服务器被要求释放其写锁或降级为读锁，它必须在遵守之前将脏数据写入磁盘。如果是降级锁，它可以保留其缓存条目，但如果释放锁，则必须使其失效。
当写锁被释放或降级时，我们可以选择绕过磁盘，将脏数据直接转发给请求者，而不是将脏数据冲到磁盘。出于简单的原因，我们没有这样做。首先，在我们的设计中，Frangipani服务器不需要互相通信。它们只与Petal和锁服务器通信。第二，我们的设计确保当一个服务器崩溃时，我们只需要处理该服务器使用的日志。如果脏缓冲区被直接转发，并且拥有脏缓冲区的目标服务器崩溃，参考脏缓冲区的日志条目可能会被分散到几台机器上。这将会给恢复工作带来问题，也会在日志空间填满的情况下造成回收的问题。
我们将磁盘上的结构分为逻辑段，并为每个段加锁。为了避免错误的共享，我们确保一个磁盘扇区不包含一个以上的可以共享的数据结构。我们将磁盘上的数据结构划分为可上锁的段，是为了保持合理的锁的数量，但又要避免普通情况下的锁争夺，这样，锁服务就不会成为系统的瓶颈。
有些操作需要原子化地更新由不同锁覆盖的几个磁盘数据结构。我们通过对这些锁进行全局排序并在两个阶段获得这些锁来避免死锁。首先，一个服务器确定它需要什么锁。这可能涉及到获取和释放一些锁，例如在一个目录中查找名字。其次，它按照节点地址对锁进行排序，并依次获取每个锁。然后，服务器检查它在第一阶段检查的任何对象是否在其锁被释放时被修改。如果是的话，它就释放锁，并循环重复第一阶段。否则，它就执行操作，弄脏缓存中的一些块，并写一条日志记录。它保留每个锁，直到它覆盖的脏块被写回磁盘。
我们刚刚描述的缓存一致性协议与Echo[26]、Andrew文件系统[19]、DCE/DFS[21]和Sprite[30]中用于客户端文件缓存的协议相似。避免死锁的技术与Echo的类似。像Frangipani一样，Oracle数据库（Oracle Parallel Server），也是将脏数据写入磁盘，而不是在写锁的连续所有者之间使用缓存到缓存的传输。
Frangipani只需要其锁服务的一小部分通用功能，而且我们不希望该服务在正常运行中成为性能瓶颈，许多不同的实现可以满足其要求。在Frangipani项目的过程中，我们已经使用了三种不同的锁服务实现，其他现有的锁服务也可以提供必要的功能，也许只需要在上面增加一层薄薄的代码。
锁服务提供多读/单写锁。锁是粘性的(sticky)；也就是说，一个客户通常会保留一个锁，直到其他客户需要一个冲突的锁。(回顾一下，锁服务的客户是Frangipani服务器）。
锁服务使用租约(leases )来处理客户端故障[15, 26]。当一个客户第一次联系锁服务时，它获得了一个租约。客户端获得的所有锁都与租约相关。每个租约都有一个过期时间，目前设置为创建或最后一次更新后的30秒。客户端必须在到期时间前更新其租约，否则服务会认为它已经失败。
网络故障可以阻止Frangipani服务器更新其租赁，即使它没有崩溃。当这种情况发生时，服务器会丢弃它所有的锁和缓存中的数据。如果缓存中的任何东西是脏的，Frangipani会打开一个内部标志，使所有来自用户程序的后续请求返回一个错误。文件系统必须被卸载以清除这个错误状况。我们选择了这种激烈的报错方式，使它难以被无意中忽略。
我们最初的锁服务实现是一个单一的、集中的服务器，它将所有的锁状态保存在易失性内存中。这样的服务器对Frangipani来说是合适的，因为Frangipani服务器和它们的日志拥有足够的状态信息，即使锁服务在崩溃时失去了所有的状态，也可以恢复。然而，锁服务的失败将导致一个巨大的性能故障。
我们的第二个实施方案将锁状态存储在Petal虚拟磁盘上，在返回客户端之前将每个锁状态的变化写入Petal。如果主锁服务器崩溃了，备份服务器将从Petal中读取当前状态，并接管提供持续服务。有了这个方案，故障恢复更加透明，但普通情况下的性能比集中式的内存方法要差。在进入下一个实施方案之前，我们没有完全实现对所有故障模式的自动恢复。
我们的第三个也是最后一个锁服务实现是完全分布式的，以实现容错和可扩展的性能。它由一组相互合作的锁服务器和一个链接到每个Frangipani服务器的接待(clerk)模块组成。
锁服务将锁组织成由ASCII字符串命名的表。表内的单个锁是由64位整数命名的。回顾一下，一个Frangipani文件系统只使用一个Petal虚拟磁盘，尽管在同一台机器上可以安装多个Frangipani文件系统。每个文件系统都有一个与之相关的表。当一个Frangipani文件系统被挂载时，Frangipani服务器调用办事器，打开与该文件系统相关的锁表。锁服务器在成功打开时给办事员(clerk)一个租赁标识符，该标识符用于他们之间的所有后续通信。当文件系统被卸载时，办事员会关闭锁表。
办事员(clerks)和锁服务器通过同步消息而不是RPC进行通信，以尽量减少内存的使用量，并实现良好的灵活性和性能。对锁进行操作的基本消息类型是请求、授予、撤销和释放。请求和释放消息类型是由clerk发送给锁服务器的，而授予和撤销消息类型是由锁服务器发送给clerk的。锁的升级和降级操作也是使用这四种消息类型处理的。
锁服务使用一个容错的分布式故障检测机制来检测锁服务器的崩溃。这与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服务器的租约到期时，有一个小的危险。如果服务器没有真正崩溃，而只是由于网络问题失去了与锁服务的联系，它可能在租约过期后仍然试图访问Petal。Frangipani服务器在尝试向Petal写东西之前，会检查它的租约是否仍然有效（并且在一定时间内仍然有效）。然而，Petal在收到写请求时不做任何检查。因此，如果在Frangipani的租约检查和随后的写请求到达Petal之间有足够的时间延迟，我们就会有一个问题：租约可能已经过期，锁被给了另一个服务器。我们使用了足够大的误差范围（15秒），在正常情况下，这个问题不会发生，但我们不能绝对排除它。
在未来，我们希望能消除这种危险；一种可行的方法是如下。我们在每个写给Petal的请求上添加一个到期时间戳。时间戳被设置为写请求产生时的当前租约到期时间，并减去边缘(margin)。然后我们让Petal忽略任何时间戳小于当前时间的写请求。只要Petal和Frangipani服务器的时钟同步在margin范围内，这种方法就能可靠地拒绝租约过期的写入。
另一种不需要同步时钟的方法是将锁服务器与Petal结合起来，并将从锁服务器获得的租约标识符与每一个写给Petal的请求结合起来。然后Petal将拒绝任何带有过期租赁标识符的写请求。
随着Frangipani安装的增长和变化，系统管理员偶尔会需要增加或删除服务器机器。Frangipani的设计是为了使这项任务变得简单。
在一个正在运行的系统中添加另一个Frangipani服务器，只需要少量的管理工作。新的服务器只需要被告知使用哪个Petal虚拟磁盘和在哪里找到锁服务。新的服务器与锁服务联系以获得租约，从租约标识符中确定使用哪一部分日志空间，然后开始运行。管理员不需要接触其他服务器；它们会自动适应新服务器的存在。
移除Frangipani服务器甚至更容易。简单地关闭服务器就可以了。服务器最好在停止前冲刷所有的脏数据并释放它的锁，但这并不是严格的需要。如果服务器突然停止，在下次需要它的一个锁的时候，恢复将在它的日志上运行，使共享磁盘进入一个一致的状态。同样，管理员不需要接触其他服务器。
Petal服务器也可以透明地添加和删除，如Petal论文[24]中所述。锁定服务器的添加和删除方式类似。
Petal的快照功能为us提供了一种方便的方式，可以对Frangipani文件系统进行一致的完整转储。Petal允许客户在任何时间点创建一个虚拟磁盘的精确拷贝。快照副本看起来与普通的虚拟磁盘相同，只是它不能被修改。该实现使用写时拷贝技术来提高效率。快照是崩溃一致的；也就是说，快照反映了一个连贯的状态，如果所有的Frangipani服务器都崩溃了，Petal虚拟磁盘也会被留在这个状态。
因此，我们可以简单地通过提取Petal快照并复制到磁带上来备份一个Frangipani文件系统。该快照将包括所有的日志，因此可以通过将其复制到一个新的Petal虚拟磁盘并在每个日志上运行恢复来恢复。由于崩溃的一致性，从快照中恢复可以减少到与从整个系统的电源故障中恢复一样的问题。
我们可以通过对Frangipani的一个小改动来改进这个方案，创建在文件系统层面上一致的快照，并且不需要恢复。我们可以通过让备份程序强制所有的Frangipani服务器进入一个屏障来实现，这个屏障使用一个由锁服务提供的普通全局锁。Frangipani服务器以共享模式获得这个锁，以进行任何修改操作，而备份程序则以独占模式请求它。当Frangipani服务器收到释放屏障锁的请求时，它通过阻止所有修改数据的新文件系统调用进入屏障，清理其缓存中的所有脏数据，然后释放该锁。当所有的Frangipani服务器都进入屏障时，备份程序能够获得独占锁；然后它制作一个Petal快照并释放锁。在这一点上，服务器在共享模式下重新获得了锁，正常的操作就恢复了。
在后一种方案中，新的快照可以被挂载为Frangipani卷而不需要恢复。新的卷可以被在线访问以检索单个文件，也可以以传统的备份格式转储到磁带上，不需要Frangipani来恢复。然而，新卷必须以只读方式挂载，因为Petal的快照目前是只读的。在未来，我们可能会扩展Petal以支持可写快照，或者在Petal上面实现一个薄层来模拟它们。
