Frangipani论文阅读总结

1. Frangipani文件系统是什么，他与传统的文件系统相比具有什么优势？

1.1 Frangipani文件系统的大概架构

Frangipani是一个新的文件系统，它接近这个理想，但相对容易构建，因为它具有两层结构。下层是Petal（在早期的一篇论文中进行了描述），它是一个分布式存储服务，提供递增可扩展、高可用、自动管理的虚拟磁盘。在上层，多台机器在共享的Petal虚拟磁盘上运行相同的Frangipani文件系统代码，使用分布式锁服务来确保一致性。

Frangipani是一个新的可扩展的分布式文件系统，将多台机器上的磁盘集合管理为一组共享的存储池。

Frangipani的一个显著特点是它具有非常简单的内部结构——一组协作的机器使用一个共同的存储器，并使用锁来同步访问该存储器。这种简单的结构使我们能够使用非常简单的机制来处理系统恢复、重新配置和负载平衡。

1.2 Frangipani文件系统具有的优势

1. 所有用户都能够获得一致的文件集视图。
2. 可以轻松地向现有的Frangipani安装添加更多的服务器，以增加其存储容量和吞吐量，而无需更改现有服务器的配置或中断它们的运行。这些服务器可以被视为“砖块”，可以逐步堆叠以构建所需的大型文件系统。
3. 系统管理员可以添加新用户，而不必担心哪些机器将管理其数据或哪些磁盘将存储它。
4. 系统管理员可以对整个文件系统进行完整且一致的备份，而无需将其关闭。备份可以选择在线保留，允许用户快速访问意外删除的文件。
5. 文件系统可以容忍并从机器、网络和磁盘故障中恢复，而无需操作员干预。
6. 与集中式网络文件服务器相比，它通过将文件系统负载分割并将其转移到使用文件的机器上，提供了更好的负载平衡。Petal和锁服务也是分布式的，以实现可扩展性、容错性和负载平衡。

1.3 关于petal的简要说明

Frangipani是基于Petal[24]构建的，Petal是一个易于管理的分布式存储系统，为其客户端提供虚拟磁盘。与物理磁盘一样，Petal虚拟磁盘提供可读写的块存储。不同于物理磁盘的是，虚拟磁盘提供了一个稀疏的2的64次方字节的地址空间，物理存储只有在需要时才进行分配。

Petal还可以选择复制数据以获得高可用性。Petal还提供了高效的快照[7、10]以支持一致的备份。Frangipani从底层存储系统继承了大部分可扩展性、容错性和易于管理性，但需要仔细设计来将这些属性扩展到文件系统级别。下一节将更详细地描述Frangipani的结构及其与Petal的关系。

所以petal本身只是一个存储服务，本身并不具有文件系统的功能，只有在其上层运行了Frangipani服务器后，才能使其成为一个真正的文件系统。

2. Frangipani文件系统分块介绍

2.1 整体系统架构

在典型的Frangipani配置中，一些计算机运行用户程序和Frangipani文件服务器模块，而其他计算机运行Petal和分布式锁定服务。在其他配置中，同一台计算机可能扮演两个角色。

上图是Frangipani服务器的一个典型配置，但是这不是绝对的。用户程序、Frangipani服务器程序、petal服务器程序并不是必然的按照某种分布进行配置的。

Frangipani的组件不必像上图所示的那样准确地分配到计算机上。Petal和Frangipani服务器不一定要在不同的计算机上；在Petals机器没有过重负载的情况下，每个Petal机器都运行Frangipani也是有意义的。分布式锁定服务与系统的其他部分是独立的；我们在每个Petal服务器机器上运行一个锁服务器，但它们同样可以在Frangipani主机或任何其他可用的机器上运行。

2.2 Frangipani服务器介绍

用户程序通过标准操作系统调用接口访问Frangipani。在不同机器上运行的程序都可以看到相同的文件，它们的视图是一致的；也就是说，在一台机器上对文件或目录所做的更改会立即在所有其他机器上可见。程序可以获得与本地Unix文件系统基本相同的语义保证：文件内容的更改通过本地内核缓冲池进行阶段性提交，并不能保证在下一个适用的fsync或sync系统调用之前到达非易失性存储，但是元数据更改会被记录，并且可以选择在系统调用返回时保证不易失性。

我们可以选择保证文件元数据的更改被持久化，当系统崩溃恢复后，可以通过检查元数据的更改推断系统崩溃时的状态，但是无法十分准确的推断。 文件内容的更改会首先写入本地内核缓冲区，因为一些文件内容上的更改没有来得及写盘，Frangipani系统选择定期的将缓存中的文件更改刷盘，因为频繁地调用fsync和sync会造成系统负担，因此这是frangipani文件系统在性能和准确性上做的权衡。 即在不牺牲性能的情况下尽可能的保护文件系统数据的完整性。

与本地文件系统语义略有不同的是，Frangipani仅以大约的方式维护文件的最后访问时间，以避免针对每次数据读取都进行元数据写入。

元数据：除了普通文件内容以外的磁盘上的任何数据结构。

每台机器上的Frangipani文件服务器模块都在操作系统内核中运行。它将自己注册为可用的文件系统实现之一，并与内核的文件系统切换器进行交互。文件服务器模块使用内核的缓冲池来缓存最近使用的文件数据。它使用本地的Petal设备驱动程序读取和写入Petal虚拟磁盘。

所有文件服务器都从共享的Petal磁盘上读取和写入相同的文件系统数据结构，但每个服务器都在Petal磁盘的不同部分保留其自己的待处理更改的重新执行日志。这些日志保存在Petal中，以便当Frangipani服务器崩溃时，另一台服务器可以访问日志并运行恢复操作。

Frangipani服务器无需直接相互通信；它们只与Petal和锁服务进行通信。这使得服务器的添加、删除和恢复变得简单。

2.3 Petal设备驱动程序

Petal设备驱动程序隐藏了Petal的分布式特性，使得Petal在操作系统的更高层面上看起来像一个普通的本地磁盘。驱动程序负责联系正确的Petal服务器(下面介绍)，并在必要时进行故障转移。任何Digital Unix文件系统都可以在Petal上运行，但只有Frangipani可以提供多台机器对同一文件的一致访问。

这段话介绍了Petal设备驱动程序的作用和Petal与Frangipani之间的关系。Petal是一个分布式的存储系统，由多个服务器共同组成，而Petal设备驱动程序的作用是隐藏Petal的分布式特性，使得操作系统的更高层面上可以像访问本地磁盘一样访问Petal。同时，驱动程序还负责维护Petal服务器的联系和故障转移等功能。 此外，该段还提到任何Digital Unix文件系统都可以在Petal上运行，但只有Frangipani可以提供多台机器对同一文件的一致访问。这是因为Frangipani文件系统实现了分布式锁和重新执行日志等机制，使得多台机器可以通过Frangipani文件系统来协同访问同一文件，并保证数据的一致性和完整性。

2.4 Petal服务器模块

可以将Petal理解为一个具有数据分片和容错功能的分布式存储系统。Petal是由多个服务器组成的，每个服务器上都存储着部分数据，这些数据被分片存储在Petal的不同节点上。通过数据分片和复制，Petal实现了数据的冗余和容错，即使某个节点出现故障，也不会导致数据的丢失和不可访问。

同时，Petal还提供了一个设备驱动程序，用于将Petal的分布式特性隐藏在操作系统的更高层面上，使得用户可以像访问本地磁盘一样访问Petal。这种透明性使得Petal可以作为一个通用的存储后端，支持各种文件系统和应用程序的访问。

Petal服务器之间协同工作，为Frangipani提供大型、可扩展、容错的虚拟磁盘，这些磁盘是在每个服务器上连接的普通物理磁盘之上实现的。只要大多数Petal服务器保持运行状态并保持通信，每个数据块至少有一个副本仍然可以物理访问，Petal就可以容忍一个或多个磁盘或服务器故障。更多的细节可以看petal的论文。

总之，Petal是一个具有分布式存储、数据分片和容错功能的系统，可以提供高可用性和可靠性的存储服务。

2.5 安全和使用C/S架构的配置

目前还没有实施任何安全措施，但通过让Petal服务器仅接受来自受信任的Frangipani服务器机器的网络地址列表请求，可以达到大约与NFS相同的安全级别。

Frangipani服务器不仅可以为本地机器提供文件访问，还可以为通过标准网络文件系统协议连接的远程客户端机器提供访问。

客户端可以使用主机操作系统支持的任何文件访问协议（如DCE/DFS、NFS或SMB）与Frangipani服务器进行通信，因为Frangipani在运行Frangipani服务器的机器上看起来就像本地文件系统一样。当然，最好使用支持一致访问（例如DCE/DFS）的协议，以便Frangipani在上一级不会失去对多个服务器的一致性。理想情况下，协议还应支持从一个Frangipani服务器故障转移至另一个服务器。

Frangipani文件系统可以使用上图所示的配置导出到管理域外的不受信任的机器。在这里，我们区分Frangipani客户端和服务器机器。只有受信任的Frangipani服务器与Petal和锁服务进行通信。它们可以位于受限环境中，并通过私有网络相互连接，如上面所讨论的。远程的不受信任的客户端通过单独的网络与Frangipani服务器通信，并且不能直接访问Petal服务器。

除了安全性之外，使用这种客户端/服务器配置的另一个原因是Frangipani运行在内核中，因此不能轻易地在不同的操作系统甚至不同版本的Unix之间移植。客户端可以通过远程访问支持的系统来使用Frangipani，通过这种方式，即使客户端在不支持Frangipani的系统上也可以使用它。

2.6 Frangipani锁信息分布

2.7 Frangipani体系结构总结

Frangipani文件系统的思想：一个由两层组成的文件系统——较低层提供存储库，较高层提供名称、目录和文件。这种思想以前就已经出现过了，并不是Frangipani所独有的。但是目前Frangipani文件系统的底层存储层目前只能支持petal。别的替代的存储抽象的设计还未考虑。

Petal提供高可用性的存储，可以随着资源的添加而扩展吞吐量和容量。然而，Petal没有为多个客户端之间的协调或共享存储提供任何规定。此外，大多数应用程序无法直接使用Petal的客户端接口，因为它类似于磁盘而不是文件。Frangipani提供了一个文件系统层，使Petal对应用程序有用，同时保留和扩展其良好的特性。

Frangipani的一个优点是它允许透明地添加、删除和恢复服务器故障。通过将预写式日志和锁与统一可访问的高可用存储相结合，Frangipani能够轻松实现这一点。

结合上下文不难理解，这里的预写式日志保存的是指的是对文件的元数据的更改。

Frangipani设计中存在三个可能会有问题的方面：

• 使用复制的Petal虚拟磁盘与Frangipani一起使用意味着有时会发生日志记录两次的情况，一次是记录到Frangipani服务器的日志中，一次是在Petal本身内部再次记录。
• Frangipani不使用磁盘位置信息来存储数据，因为Petal将磁盘虚拟化了。
• Frangipani锁定整个文件和目录，而不是单个块。我们没有足够的使用经验来在一般情况下评估我们设计中的这些方面，但尽管存在这些问题，Frangipani在我们测试的工程工作负载上的性能表现良好。

3. petal虚拟磁盘

Frangipani使用Petal的大型、稀疏磁盘地址空间来简化其数据结构。这个一般的想法让人想起了过去关于使用大型内存地址空间编程计算机的工作[8]。有如此多的地址空间可用，可以慷慨地分配它们。

Petal虚拟磁盘具有2的64次方字节的地址空间。Petal只在虚拟地址被写入时才将物理磁盘空间分配给这些地址。此外，Petal还提供了一个de-commit原语，用于释放支持一段虚拟磁盘地址的物理空间。

即写时分配机制，将一段虚拟地址先分配给一个Frangipani服务器，但是并不马上分配实际的物理地址，只有在真正写入时才会分配物理地址。 这里可以对比一下，和Linux的COW（copy-on-write）机制有一些相似之处，相似点在于lazy-allocate。

Frangipani利用Petal的大型稀疏磁盘地址空间来简化其数据结构。每个服务器都有自己的日志和自己的分配位图空间块

为了保持其内部数据结构的小型化，Petal以相当大的块（目前为64 KB）进行空间的提交和撤销。

下面介绍petal虚拟磁盘的各个区域的作用：

• 第一个区域存储共享配置参数和维护信息。我们为该区域分配了1TB的虚拟空间，但实际上目前只使用了其中的几KB。
• 第二个区域存储日志。每个Frangipani服务器都获得该空间的一部分来保存其私有日志。我们已经为该区域保留了1TB（2^40字节），分成256个独立的日志区域，即每个frangipani服务器会被分配一块log区域用来存储自己管理的文件内容的日志。这个选择将当前的实现限制在256个服务器内，但这可以很容易地进行调整。
• 第三个区域用于分配位图，以描述其余区域中哪些块是空闲的。每个Frangipani服务器锁定一部分位图空间供其专用使用。当服务器的位图空间填满时，它会查找并锁定另一个未使用的部分。位图区域长度为3TB。
• 第四个区域保存索引节点（inode）。每个文件都需要一个inode来保存其元数据，例如时间戳和指向数据位置的指针。符号链接直接将其数据存储在inode中。我们将inode的长度设置为512字节，与磁盘块的大小相同，从而避免了如果两个服务器需要访问同一块中的不同inode时可能发生的不必要的争用（“false sharing”）。我们分配了1TB的inode空间，允许容纳2^31个inode。分配位图中的位与inode之间的映射是固定的，因此每个Frangipani服务器仅从与其对应的分配位图部分对应的inode空间中为新文件分配inode。但是，任何Frangipani服务器都可以读取、写入或释放任何现有文件的inode。
• 第五个区域保存小数据块，每个块的大小为4KB（2^{12字节）。每个文件的前64KB（16个块）存储在小块中。如果文件的大小超过了64KB，则其余部分将存储在一个大块中。我们为小块分配了2}47字节，因此最多可以容纳2^35个小块，是inode最大数量的16倍。
• Petal地址空间的其余部分保存大型数据块。为每个大块保留了1TB的地址空间。

3.1 petal虚拟磁盘设计思想

使用的是4KB块的磁盘布局策略；每个inode分配512字节的空间有些浪费。上述的两种做法是为了简化管理和实现，尽管这种做法可能浪费一些磁盘空间，但论文中认为这是为了获得更简单的设计而进行的合理权衡。

此外，如果2^64字节的地址空间限制不足，单个Frangipani服务器可以在多个虚拟磁盘上支持多个Frangipani文件系统。

1.一个Frangipani服务器可以通过在多个Petal虚拟磁盘上运行多个Frangipani文件系统来管理多个磁盘。每个Frangipani文件系统将负责管理一个特定的Petal虚拟磁盘，这些虚拟磁盘可以是共享的，也可以是分离的。多个Frangipani文件系统共同管理多个磁盘，从而实现了数据的共享和负载均衡。 2.如果多个Petal虚拟磁盘是共享的，可以将它们视为一个更大的共享磁盘。这个共享磁盘将由多个Frangipani文件系统管理，从而实现了数据的共享和负载均衡。

Frangipani的设计足够灵活，以至于我们可以尝试不同的布局，但这会带来备份和恢复文件系统的成本。

petal虚拟磁盘只负责提供存储与存储地址，它无需理解任何关于文件系统方面的内容。

4. Logging and Recovery

Frangipani使用日志记录元数据的预写式重做日志（write-ahead redo logging）来简化故障恢复并提高性能，但用户数据不会被记录在日志中。同样是日志先行，只有当日志被写入petal虚拟磁盘后，Frangipani服务器才会修改实际元数据所在磁盘的永久位置。

4.1 Frangipani服务器日志结构设计（存有疑惑）

每个Frangipani服务器都有自己的Petal私有日志。当Frangipani文件服务器需要进行元数据更新时，它首先创建一个描述更新的记录，并将其附加到内存中的日志中。这些日志记录会按照它们所描述的更新请求的顺序定期写入到Petal中。（可选地，我们允许将日志记录同步写入。这样做可以在一定程度上提供更好的故障语义，但会增加元数据操作的延迟。）只有在日志记录被写入Petal之后，服务器才会修改实际元数据的永久位置。Unix更新守护进程会定期更新永久位置（大约每30秒一次）。

日志大小被限制在128 KB，这是当前实现中的设置。*根据Petal的分配策略，一个日志将由两个64 KB片段组成，分布在两个不同的物理磁盘上。*为每个日志分配的空间被管理为循环缓冲区。当日志被填满时，Frangipani会回收最老的25%的日志空间用于新的日志条目。通常，在新空间中的所有条目都将引用先前已经写入Petal的元数据块，这时不需要进行额外的Petal写入操作。如果存在尚未写入的元数据块，则需要在回收日志之前完成这项工作。给定日志的大小和Frangipani日志记录的典型大小（80-128字节），如果在该时间间隔内有大约1000-1600个修改元数据的操作，日志可能会在两个周期性同步操作之间填满。

注意这两个片段不仅位于不同的物理磁盘，同样在地址空间也不连续。 在Frangipani中，每个日志条目都由两个64KB的片段组成，这两个片段分别存储在不同的物理磁盘上。这些片段是按照一定规则分配和写入的，例如按照循环方式或随机方式。当需要读取整个日志条目时，Frangipani会根据这些规则找到对应的片段，并将它们合并为一条完整的日志条目。 具体来说，Frangipani使用一个位图来跟踪哪些日志条目已经被完整地写入到磁盘上。当需要读取一条完整的日志条目时，Frangipani会查找位图，找到对应的两个片段，并将它们合并为一条完整的日志条目。如果一个片段丢失或损坏，Frangipani会使用另一个片段和已经写入磁盘的元数据块来恢复数据。 总之，Frangipani不使用Petal的元数据来管理和合并日志片段。相反，Frangipani使用自己的位图来跟踪哪些日志条目已经被写入到磁盘上，并使用这些信息来找到对应的片段并将它们合并为一条完整的日志条目。

如果一个Frangipani服务器崩溃，系统最终会检测到故障并在该服务器的日志上运行恢复。恢复守护进程会隐式地获得失败服务器的日志和锁的所有权。该守护进程找到日志的起始和结束位置，然后按顺序检查每条记录，执行每个未完成的描述更新。日志处理完成后，恢复守护进程释放所有锁并释放日志。其他Frangipani服务器可以继续运行而不受失败服务器的阻碍，而失败的服务器本身可以选择重启（使用空日志）。只要基础的Petal卷仍然可用，系统就可以容忍无限数量的Frangipani服务器故障。

4.2 Frangipani文件系统恢复协议设计

Frangipani确保在存在多个日志的情况下，日志记录和恢复工作正常，需要注意以下几个细节。具体细节见论文的第5页左下方和右上方的部分。

1. Frangipani的锁协议会确保对同一数据的不同服务器请求的更新是串行化的。（互斥锁）
2. Frangipani确保恢复仅应用自服务器获取覆盖它们的锁以来已记录的更新，并且仅应用仍然持有这些锁的更新。
3. 恢复过程永远不会重放描述已经完成的更新的日志记录。（通过赋予元数据版本号做到这一点）
4. Frangipani确保任何时候只有一个恢复守护程序正在尝试重播特定服务器的日志区域。（互斥锁）

4.3 Frangipani日志的意义

若Frangipani文件系统的一个扇区的两个副本都丢失了，或者Frangipani的数据结构被软件错误破坏了，那么需要进行元数据一致性检查和修复工具（类似于Unix fsck）。到目前为止，我们还没有实现这样的工具。

Frangipani的日志记录并不旨在为其用户提供高级语义保证。它的目的是通过避免每次服务器故障时运行类似于fsck的程序，提高元数据更新的性能并加速故障恢复。只有元数据被记录，而不是用户数据，因此在故障后，用户无法保证文件系统状态从他的角度是一致的。我们并不声称这些语义是理想的，但它们与标准本地Unix文件系统提供的语义相同。在本地Unix文件系统和Frangipani中，用户可以通过在适当的检查点调用fsync来获得更好的一致性语义。

Frangipani不是一个日志结构文件系统；它没有将所有数据保存在日志中，而是维护传统的磁盘数据结构，并使用小型日志作为辅助工具来提供改进的性能和故障原子性。Frangipani保留多个日志，这与某些日志结构的文件系统是相似的。

5. Synchronization and Cache Coherence（缓存一致性）

由于多个Frangipani服务器都修改共享的磁盘数据结构，因此需要仔细的同步来为每个服务器提供一致的数据视图（缓存一致性），同时允许足够的并发性以随着负载的增加或服务器的添加而提高性能。

Frangipani使用多读单写锁来实现必要的同步。当锁服务检测到冲突的锁请求时，会要求锁的当前持有者释放或降级锁以消除冲突。

• 读锁：只有当服务器持有该锁时，其缓存条目才是有效的；释放锁之前必须使缓存条目无效。
• 写锁：服务器缓存的磁盘块的副本只有在它持有相关的写锁时才能与磁盘上的版本不同。因此，如果要求服务器释放其写锁或将其降级为读锁，它必须在遵守之前将脏数据写入磁盘。如果服务器降级锁，则可以保留其缓存条目，但如果释放锁，则必须使其无效。

在写锁被释放或降级时，我们可以选择绕过磁盘，直接将脏数据转发给请求者，而不是将其刷新到磁盘上。由于简单性方面的原因，我们没有采取这种方法。首先，在我们的设计中，Frangipani服务器不需要彼此通信。它们只与Petal和锁服务通信。其次，我们的设计确保当服务器崩溃时，我们只需要处理该服务器使用的日志即可。如果脏缓冲区直接转发，并且具有脏缓冲区的目标服务器崩溃，则引用脏缓冲区的日志条目可能分散在多台机器上。这将在恢复和回收填满日志空间时造成问题。

在Frangipani文件系统中，一个锁保护inode和它指向的任何文件数据。这种以文件为单位的锁粒度适用于工程负载，其中文件很少并发进行写共享。然而，其他负载可能需要更细粒度的锁定。

有些操作需要原子地更新由不同锁覆盖的多个磁盘数据结构。我们通过全局排序这些锁并分两个阶段获取它们来避免死锁。首先，服务器确定它需要哪些锁。这可能涉及获取和释放一些锁，例如在目录中查找名称。其次，服务器按inode地址排序锁，并依次获取每个锁。然后，服务器检查在第一阶段检查的任何对象是否在其锁被释放时被修改。如果是，则释放锁并循环返回重复第一阶段。否则，它执行操作，将其缓存中的一些块变脏并写入日志记录。它保留每个锁，直到它覆盖的脏块被写回磁盘。

像2PL锁协议，其中的检查机制是为了确保在操作期间获取到的数据在该操作进行更改之前是不变的。

6. 锁服务

Frangipani仅需要从其锁服务中获取一小部分通用功能，并且我们不希望该服务在正常运行中成为性能瓶颈，因此许多不同的实现都可以满足其要求。在Frangipani项目的过程中，我们使用了三种不同的锁服务实现，而其他现有的锁服务也可以提供必要的功能，可能需要在其上添加一层轻量级的额外代码。

锁服务的客户端是Frangipani服务器，这一点一定要注意。

6.1 网络故障问题

锁服务使用租约（lease）来处理客户端故障。当客户端第一次联系锁服务时，它会获取一个租约。客户端获取的所有锁都与该租约相关联。每个租约都有一个过期时间，目前设置为创建或最后一次更新后的30秒。客户端必须在过期时间之前更新其租约，否则服务将视其为失败。这种机制可以防止客户端失效，因为在租约过期之前必须定期更新租约。如果客户端失效，则锁服务将释放与该客户端相关联的所有锁，以便其他客户端可以获取这些锁并继续执行操作。

Frangipani 服务器通过定期发送租约续订请求来与锁服务续订租约。在 Frangipani 系统中，每个服务器都有一个称为 clerk 的进程，负责与锁服务通信，并处理锁请求和租约管理。当一个 Frangipani 服务器启动时，它会创建一个 clerk 进程，并向锁服务请求一个租约。如果请求成功，则服务器会获得一个租约和一个租约过期时间。在租约过期之前，Frangipani 服务器会定期向锁服务发送租约续订请求，以保持租约的有效性。如果 Frangipani 服务器无法续订租约，它将被视为失败，并从锁服务中删除它所拥有的所有锁。

网络故障可能会导致Frangipani服务器无法更新其租约，即使它没有崩溃。当发生这种情况时，服务器会丢弃所有锁和缓存中的数据。如果缓存中的任何内容是脏的，则Frangipani会打开一个内部标志，导致所有后续的用户程序请求返回错误。为了清除此错误状态，必须卸载文件系统。我们选择采用这种严厉的报告错误的方式，以使无意中忽略错误变得困难。

“卸载文件系统”意味着，发生网络故障的Frangipani服务器已经无法使用，只有将文件系统从该故障服务器中卸载，这是唯一的解决方法。但是其他正常运行的服务器仍然可以访问文件系统。

6.2 锁服务实现问题（在细节上还有一些模糊）

Frangipani文件系统最初的锁服务实现是一个单一的中央服务器，它将所有锁状态都保存在易失性内存中。这样的服务器对于Frangipani来说是足够的，因为Frangipani服务器及其日志保存了足够的状态信息，即使锁服务在崩溃中失去了所有状态，也能够进行恢复。但是，锁服务的故障会导致大量性能问题。因为所有锁请求都必须通过中央锁服务进行处理，如果锁服务出现故障，则所有的锁请求都会被阻塞或失败，导致系统性能下降。

第二个锁服务实现将锁状态存储在Petal虚拟磁盘上，每次锁状态更改后都会写入Petal，然后再返回给客户端。如果主锁服务器崩溃，备份服务器将从Petal中读取当前状态并接管以继续提供服务。通过这种方案，故障恢复更加透明，但是对于常见情况，性能比集中式内存方法更差。我们在进入下一个实现之前，没有完全实现从所有故障模式中自动恢复的功能。

第三个和最终的锁服务实现是完全分布式的，具有容错和可扩展的性能。它由一组相互协作的锁服务器和链接到每个 Frangipani 服务器的 clerk 模块组成。（最终采用的就是这种方式）

锁服务将锁组织成由 ASCII 字符串命名的表。表中的各个锁由 64 位整数命名。单个 Frangipani 文件系统仅使用一个 Petal 虚拟磁盘，尽管可以在同一台机器上挂载多个 Frangipani 文件系统。每个文件系统都有一个相关联的锁表。当挂载 Frangipani 文件系统时，Frangipani 服务器调用 clerk，后者打开与该文件系统相关联的锁表。如果打开成功，锁服务器会向 clerk 提供租赁标识符，该标识符在它们之间的所有后续通信中都会使用。当卸载文件系统时，clerk 会关闭锁表。

6.3 锁服务故障、锁的重新分配、

为了弥补锁服务器崩溃或利用新恢复的锁服务器，锁有时会在锁服务器之间重新分配。当永久添加或删除锁服务器时，也会发生类似的重新分配。在这种情况下，锁总是重新分配，以使每个服务器服务的锁数量平衡、重新分配的数量最小化，并且每个锁都由一个锁服务器服务。重新分配分两个阶段进行。在第一阶段，失去锁的锁服务器从其内部状态中丢弃锁。在第二阶段，获得锁的锁服务器联系打开有关锁表的clerk。服务器从clerks恢复其新锁的状态，clerk被告知其锁的新服务器。

当一个 Frangipani 服务器崩溃时，它所拥有的锁不能被释放，直到适当的恢复操作被执行。具体来说，必须处理崩溃的 Frangipani 服务器的日志，并将任何未完成的更新写入 Petal。当一个 Frangipani 服务器的租约过期时，锁服务会要求另一台 Frangipani 机器上的 clerk 进行恢复，并释放所有属于崩溃的 Frangipani 服务器的锁。这个 clerk 被授予一个锁，以确保对日志的独占访问。这个锁本身受到租约的保护，所以如果这个恢复过程失败，锁服务将启动另一个恢复过程。

总体来说，Frangipani 系统可以容忍网络分区，尽可能地继续运行，否则会进行干净的关闭。具体来说，只要大多数 Petal 服务器保持运行并处于通信状态，Petal 就可以继续运行，即使面临网络分区，但如果大多数分区中没有复制，则 Petal 虚拟磁盘的某些部分将无法访问。只要大多数锁服务器保持运行并处于通信状态，锁服务就可以继续运行。

如果一个 Frangipani 服务器与锁服务分区，它将无法更新租约。锁服务将宣布此类 Frangipani 服务器已死亡，并从其在 Petal 上的日志中开始恢复。如果一个 Frangipani 服务器与 Petal 分区，它将无法读取或写入虚拟磁盘。在这两种情况下，服务器将禁止用户进一步访问受影响的文件系统，直到分区恢复并重新挂载文件系统。

注意只是禁止用户访问受影响的部分，正常工作的文件系统部分依然是可以访问的。

当一个 Frangipani 服务器的租约过期时，存在两个小的风险。

• 如果服务器并没有真正崩溃，而只是由于网络问题与锁服务失去联系，它在租约过期后仍可能尝试访问 Petal。
• 在尝试写入 Petal 之前，Frangipani 服务器会检查它的租约是否仍然有效（并且在未来 margin 秒内仍将有效）。然而，当写请求到达 Petal 时，Petal 并不会进行检查。因此，如果 Frangipani 的租约检查和后续写请求到达 Petal 之间存在足够的时间延迟，我们可能会遇到问题：租约可能已经过期，并且锁已经被分配给另一个服务器。我们使用足够大的误差 margin（15 秒）来确保在正常情况下不会出现此问题，但我们不能完全排除这种可能性。

由于网络问题失联，Frangipani服务器可能会反复尝试在租约期间未成功的请求。 确保一个Frangipani服务器在完成整个写操作的过程中租约都不会过期，但是在某种特殊情况下依然有这种“半途租约过期”的风险。

6.4 Petal磁盘处理过期写请求问题

即上面的段落中说的问题，一个Frangipani服务器的写请求还未完成时，该服务器的租约过期了，故该写请求应该被无效掉，那么该如何处理呢？

在未来，我们希望消除这个风险；一种可行的方法如下。我们为每个到Petal上的写请求添加一个过期时间戳。时间戳设置为在生成写请求时的当前租约过期时间减去 margin。然后，我们让 Petal 忽略任何时间戳小于当前时间戳的写请求。只要 Petal 和 Frangipani 服务器的时钟在 margin 范围内同步，这种方法可靠地拒绝已过期的写入请求。

让 Petal 忽略任何时间戳小于当前时间的写请求是为了防止 Frangipani 服务器在其租约过期后仍然尝试写入 Petal。具体来说，Frangipani 服务器在写入 Petal 之前会在写请求中包含一个时间戳，该时间戳是在服务器检查租约过期时间时设置的。如果 Frangipani 服务器的租约已经过期，并且它尝试发送一个带有早于当前时间的时间戳的写请求，则 Petal 将忽略该请求并拒绝该写入操作，因为时间戳小于当前时间。 通过这种方法，我们可以确保 Frangipani 服务器仅在其租约仍然有效时才能写入 Petal，从而避免了租约过期后 Frangipani 服务器仍然尝试写入 Petal 的问题。 注意，在正常时期这一策略是看不出来作用的。比如说，我发完这个写请求B后，服务器租约过期，但是还有一个之前的请求A未发送成功，服务器在租约过期后依然会尝试重新发送，不难理解A的发送时间一定是小于写请求B上设置的时间戳的。（因为假设写请求到petal所需的时间为margin）。即只要在B之前未成功的请求、需要重新发送的，都是无效请求。

另一种不需要同步时钟的方法是将锁服务与 Petal 集成，并将从锁服务获取的租约标识符与每个写请求一起包含在 Petal 中。然后，Petal 将拒绝任何带有过期租约标识符的写请求。

这种方法的优点是不需要服务器之间的时钟同步，因为所有与租约相关的信息都由锁服务负责管理。此外，由于锁服务和 Petal 都由同一组服务器管理，因此这种方法还能够减少网络通信的开销。

不过，这种方法的缺点是需要对 Frangipani 和 Petal 的代码进行更改，以便它们能够支持这种集成方式。此外，由于锁服务和 Petal 集成在一起，可能会增加系统的复杂性和可靠性问题。因此，需要仔细考虑这种方法的实现和可能的风险。

7.添加或移除Frangipani服务器

向运行中的系统添加另一个 Frangipani 服务器只需要最少的管理工作。新服务器只需告知它要使用哪个 Petal 虚拟磁盘以及锁服务的位置即可。新服务器会联系锁服务以获取租约，通过租约标识符确定要使用的日志空间的部分，然后开始运行。管理员不需要触及其他服务器，它们会自动适应新服务器的存在。

言外之意，若Frangipani服务器集群只有一个frangipani文件系统（即只有一个petal虚拟磁盘），则几乎不需要进行任何其他操作，无脑加即可。

向运行中的系统添加另一个 Frangipani 服务器只需要最少的管理工作。新服务器只需告知它要使用哪个 Petal 虚拟磁盘以及锁服务的位置即可。新服务器会联系锁服务以获取租约，通过租约标识符确定要使用的日志空间的部分，然后开始运行。管理员不需要触及其他服务器，它们会自动适应新服务器的存在。

在 Frangipani 系统中，每个租约都与一个日志地址范围相关联，该范围表示可以由持有该租约的服务器使用的日志空间的一部分。锁服务器负责管理租约和日志空间，并为新服务器分配租约和日志空间。当新服务器联系锁服务器以获取租约时，锁服务器会分配一个租约，并确定该服务器可以使用的日志地址范围。 如果系统中存在多个日志空间，则锁服务器会选择一个可用的日志空间并将其分配给新服务器。如果系统中只有一个日志空间，则该日志空间将被分配给新服务器。因此，新服务器会分配一个已存在的日志空间或唯一的日志空间。

若新服务器是第一次获取租约都是获得了一个空的、可用的日志空间。

若新服务器是接管之前的服务器的工作，恢复程序会先处理完之前的日志，之后新服务器可以接管并继续操作。并且沿用之前服务器的日志空间。

删除 Frangipani 服务器甚至更加容易。只需要关闭服务器即可。最好的做法是在关闭服务器之前刷新所有脏数据并释放其持有的锁，但这并非必须。如果服务器突然停止运行，下次需要其持有的锁的时候，恢复程序将对其日志进行处理，使共享磁盘处于一致的状态。管理员不需要触及其他服务器。

Petal 服务器也可以像 Petal 论文中所述一样透明地添加和删除。锁服务器的添加和删除也是类似的。

8. Back up

Petal允许客户端在任何时刻创建虚拟磁盘的精确副本。快照副本看起来与普通的虚拟磁盘完全相同，但不能被修改。该实现使用写时复制技术以提高效率。快照是崩溃一致的；也就是说，快照反映了一个协调的状态，如果所有的Frangipani服务器都崩溃了，Petal虚拟磁盘可能会留在这个状态下。

Petal中的写时复制技术：写时复制（Copy-on-write，简称COW）是一种常用的技术，它可以优化数据的复制操作。在Petal的实现中，当一个快照被创建时，它与原始虚拟磁盘共享相同的数据块，这些数据块被标记为只读。当对虚拟磁盘进行写入操作时，Petal会将被修改的数据块复制一份并将其标记为可写，以确保快照数据的一致性。这种方式避免了直接复制整个虚拟磁盘的开销，从而提高了效率。这样，当需要创建多个快照时，它们之间的共享部分可以被重复利用，只需要复制它们各自修改的部分即可。

8.1 快照方案改进

通过对Frangipani进行微小的更改，我们可以改进这个方案，创建在文件系统级别上一致且不需要恢复的快照。我们可以通过使用由锁服务提供的普通全局锁来实现强制备份程序将所有Frangipani服务器都置于栅栏状态。Frangipani服务器以共享模式获取此锁来执行任何修改操作，而备份进程以独占模式请求该锁。当Frangipani服务器收到释放栅栏锁的请求时，它通过阻止所有修改数据的新文件系统调用进入栅栏，清除其缓存中的所有脏数据，然后释放该锁。当所有的Frangipani服务器都进入栅栏时，备份程序能够获取独占锁；然后它创建一个Petal快照并释放锁。此时，服务器以共享模式重新获取锁，正常操作恢复。

此方案可以避免制作的快照中出现处于崩溃状态的Frangipani服务器。 这里所说的“barrier”指的是一个同步屏障（synchronization barrier），它是一种在多个线程或进程之间协调操作的机制，使得这些线程或进程必须等待所有其他线程或进程都到达同步点之后才能继续执行。在这个方案中，同步屏障被用作一种机制，以确保所有的Frangipani服务器都处于一个一致的状态，并且不会在备份过程中进行任何修改操作。当所有的服务器都进入栅栏时，备份进程才能获取独占锁，并创建一个快照。这样做可以确保快照是一致的，并且不需要进行恢复操作。 可以这么理解：当服务器进入“barrier”状态时，它已经完成了所有未完成的修改操作，并且不再接受任何新的修改请求。因此，它只能处于两种状态之一：要么处于未修改的状态，要么处于修改已完成的状态。这样可以确保快照是一致的，并且不需要恢复操作。

此外，在这种方案下，新的快照可以作为Frangipani卷挂载，无需进行恢复操作。新卷可以在线访问以检索单个文件，或者可以以不需要Frangipani进行恢复的传统备份格式转储到磁带上。但是，新卷必须以只读方式挂载，因为Petal快照目前是只读的。在将来，我们可能会扩展Petal以支持可写快照，或者我们可能会在Petal之上实现一个thin layer来模拟可写快照。

9. 课程知识点总结

9.1 Frangipani锁机制

教授讲课时说明的锁信息分布情况：

在锁服务器上，有一张锁表，记录了文件级别的锁，如：文件X的锁由workstation1持有。

在工作站（workstation）上，保存了该工作站持有的是锁ID（上图中是FILE）；锁的状态（BUSY或者IDLE），在工作站的cache中保存的该文件的相关内容（CONTENT）。（注意每个工作站中运行着一个Frangipani服务器）。

当工作站完成系统调用后，它会马上将锁状态标记为空闲（IDLE），即他在该系统调用后不使用该锁了，但是在lock server中该锁仍然被此工作站持有。这是一种将锁延后归还给lock服务器机制。这种机制对于工作站而言是十分有利的。

这种工作站处理完工作后，依然持有对应的锁，这是一种优化机制：即工作站将最近所使用过的文件上的锁累积起来归还给lock server，而不是每完成一个系统调用就归还一次。

下面说明lock server上保存的锁表的条目信息：

lock server只保存这些信息：锁id和对应的持有者。lock server或这些锁id（指上图中的FILE），lock server和这些锁并不清楚关于文件、目录或文件系统的任何事情，它知道的仅仅限于锁ID和持有者ID。

锁ID（FILE字段）：frangipani使⽤了unix风格的i-number（信息节点编号）与⽂件进⾏关联，⽽不是使⽤锁的名字。

Frangipani服务器可以根据锁ID，结合自己保存的元数据，分析出这些锁ID是与哪些文件关联的。

9.2 Frangipani的缓存一致性协议分析

为了更具体地讲解Frangipani的缓存⼀致性协议，以及petal操作和lock服务器操作之间的关系，教授举出了一个例子说明这些关系。

背景：有两台工作站（WS1与WS2），WS是workstation，还有一个lock server：

1. WS1想要读取并修改文件Z，首先要获取文件Z对应的锁。
2. WS1向lock服务器发送Acquire Z，可能现在没有⼈拿着这把锁(lock服务器从来就没听过关于Z这个⽂件任何信息，即lock表上目前没有这个信息)。
3. lock服务器就会在它的lock表上添加⼀个关于Z的新条⽬，并对WS1进⾏响应—将这把锁GRANT TO WS1（GRANT Z）。
4. WS1拿到了这把锁，首先从petal 读取文件Z，之后在自己的本地缓存中对文件Z进行修改。（READ Z FROM PETAL）
5. 过了一会，WS2想读取文件Z，但是此时WS2没有持有文件Z的锁。
6. WS2首先向lock server发送Acuqire Z。但是lock server知道目前WS1持有该锁。
7. lock server尝试向WS1发送revoke Z（看WS1是否可以释放该锁）。
8. 当WS1收到revoke Z消息后，它会首先将local cache中的内容写回petal（WRITE TO PETAL）。
9. 之后WS1可以向lock server恢复RELEASE Z消息。（释放自己持有的Z锁）
10. lock server上同时也保存着一条WS2想要获取Z锁的信息（Acuqire Z），当9完成后，lock server会马上回复WS2（GRANT Z）。之后WS2可以做自己要做的操作了。

注意，WS上做的操作都是由上面运行的Frangipani服务器完成的。

这就是Frangipani的缓存一致性协议。为了确保每个⼈都能去读取数据，它会让前⼀个持有锁的⼈先将它们修改过的数据写回petal，这样才去让后⾯的⼈去读取数据，这种锁机制会强制让读操作看到最新写⼊的值。

此外，若一个WS中的数据长时间没有被任何别的WS访问，若没有别的机制，那么此数据会一直在cache中，万一该WS崩溃，则会丢失该更改，因此frangipani有定期将WS的cache中的内容写回到petal中的机制。

Frangipani想试着去模仿普通的Unix风格的工作站锁拥有的特性。

9.3 复杂操作实现atomicity

背景：比如一个WS在进行创建文件操作，该系统调用会经历很多个复杂的步骤，站在atomic的角度，该WS只想让别的WS看到的是该文件存在或不存在，不想让他们看到任何的中间状态（如创建inode、初始化inode等等的中间步骤是不能够被其他WS看到的）。我们想要的是具备原子性的多步骤操作。

Frangipani内置了一个数据库系统风格的事务系统，支持分布式事务（Distributed Txns）。为了保证原子性，当某个WS要进行操作时，会严格遵循以下的步骤：

提前获取所有需要的锁->read from petal->在local cache做更新->write back to petal-> 完成所有操作->在本机的frangipani服务器上标记锁为IDLE。

通过获取所有的锁，我们获取了这些不可分割的事务，获得了多步骤操作的原子性。

9.4 崩溃恢复

要能应对WS发生崩溃的情况，我们感兴趣的一种情况是：一个WS在持有锁，在它更新完cache，在之后的write back过程中，向petal写入了一部分更新内容后（还未写完，故对应锁也未释放完毕），它崩溃了。

这种完成了部分写回后发生的崩溃是难以发现的，因为难以发现，所以无法做到及时的释放锁。

比如，WS创建新文件的操作：已经向petal对应文件目录下写入了该文件的名字，但是对应的inode节点没有及时的写入（初始化），这时该WS崩溃，但是此时释放它的锁是不应该的，因为操作处于中间状态。

若此时释放了会导致别的要读取这段数据的WS读到正处于中间状态的数据，这是不允许的。

若该崩溃的WS一直持有锁，也是不好的，因为可能有别的WS在等待读取这段内容，所以怎么处理呢？

每个WS中的frangipani server使用WAL(预写式日志)，在WS要对petal进行任何的操作之前，

这里的操作指的是：如创建文件这样的系统调用的流程，它涉及了对petal的很多处修改，如目录下创建名称，创建关联的inode节点等等的一系列操作。

它会先向petal中它的日志区域里面追加一个日志记录组(包含若干条日志记录)，该组日志记录描述了这一个操作涉及到的对petal的一组修改，只有当该组日志记录成功落地到petal后，该WS才可以对petal执行实际的修改。

上图中就是一个log entry中包含了若干条log记录，每个记录涉及了若干操作，一个log entry中的所有操作对于外界而言必须是一个原子的整体：即要么不执行，要么全部执行完，没有执行部分的情况，因此只有当log entry是完整的时候该log entry才是有效的。

但是我们必须知道frangipani的日志系统与传统的分布式数据库系统不同：

1. 每个WS使用的日志是分开的，只使用自己的涉及到的操作。
2. 每个WS的日志都是放在petal上的，petal为每个WS分配了一块独立的空间专门用来存储日志，而不是在WS自己的本地磁盘上。

9.4.1 一条日志的组成

该paper中并没有明确的说明一条log的格式。但是根据机制可以大概的得出一条log的物理格式：

• LSN：对于每个WS而言是单调唯一递增的。
• Block num：petal上的Block号，对应了此log要修改的block号。
• version no：版本号。当WS崩溃时，用来安全的进行日志重演。下面会介绍。
• data：要写入的数据。

日志中包含了上述的四种内容，可能需要很多字段来表示他们，此外，日志之中只包含对文件系统中的元数据的修改信息（目录、inode、位图等），而没有对用户数据的修改信息，元数据足够用来恢复文件系统的结构。

即便是日志，一个WS的日志也会首先保存在本地cache中，他会尽可能的延迟写回petal的操作，因为写入日志也是一个I/O量较大的工作；对于修改后的文件块（包括元数据、文件内容这两部分），同理也是延迟写回petal，但必须在日志写入之后才能执行。

日志写入触发时机：当lock server向该WS发出revoke z（释放文件z相关的锁）消息时，WS意识到自己必须进行写回操作。首先写回且只写回与Z文件相关的日志（也可能是一下写回全部？看具体场景了，毕竟没有具体的实现可以参考），之后再写回与Z相关的、且被修改的位于petal上的block，之后WS可以告诉lock server可以释放该WS拥有的文件Z相关的锁。

上图说明了一个WS在收到lock server的revoke消息后会做什么。和上面文字描述的一样。

日志写回->apply 日志（更新元数据）->写回文件内容->释放锁。

9.4.2 场景1分析

假设：WS2想获取WS1的锁，但是WS1崩溃了。即WS1持有锁，但是它崩溃了。

lock server会向WS1发送revoke消息，若在lease时间内没有收到WS1的release消息，lock server会判定WS1崩溃了。之后lock server会让另一个工作站去执行WS1的崩溃恢复操作。

只有WS1保存到petal的日志是完整的，负责崩溃恢复的WS才会去重演WS1的日志。若日志不完整、或者在开始写入日志前就崩溃了，那么WS1所做的操作就可以被无视了。

log中有类似于checksum之类的条目，可以用来进行完整性检查。

9.4.3 场景2分析

在场景1的基础上增加复杂度：

WS1执行delete (d/f)：删除目录d下的f文件，并且删除成功，释放了锁；之后不久ws2执行create(d/f)，但是WS1在完成收尾工作过程中崩溃了，因此需要WS3对WS1进行崩溃恢复，但是若不加任何限制，这会在重演WS1的日志的过程中删除掉WS2创建的文件，这显然不是我们想看到的。

很明显前后的两个f是不同的文件。因此我们需要设定一个逻辑：若一个操作执行完毕并且成功持久化到petal了，那么该操作对应的日志就该被以某种方式无效化（delete操作），否则若此处WS3无脑执行WS1的日志时，会将WS2创建的f文件给删除掉，这不是我们希望看到的。

那么Frangipani如何解决上述问题？

9.4.4 Frangipani的安全重放日志机制

frangipani使用版本号的机制来解决上面的问题：他给petal文件系统中的保存的数据都赋予一个version num。即上面log条目中的verison no，每个操作的日志条目中都会有一个针对于特定元数据的单调递增且唯一的版本号，每进行一次修改操作，version no都会自增。

因此，当WS3进行崩溃恢复操作时，他会查看并对比WS1的log条目的版本号与当前petal中对应数据块的版本号，若petal中现有的版本号>=log中的版本号，那么恢复软件不会重放该log。

很明显WS1已经将更新操作写回过petal了。释放了锁后，又有别的WS修改该数据块。

崩溃恢复时，恢复软件会根据版本号有选择的去重放崩溃WS的日志。即始终只接收最新的版本号的更新。此外，恢复软件可以不需要提前获得锁就可以去读写目标数据块。因为WS1崩溃后只有两种情况：WS1释放了锁，WS1未释放锁。

1. 若WS1崩溃时未释放锁，那么不用担心任何问题，在WS3上的恢复软件重放完日志并写入对应的数据更改前，它都会持有锁。

2. 若WS1崩溃时已经释放了锁，如场景2，有新的WS获取到了该锁，此时WS3可以读取目录元数据，他会发现petal中的ver no大于要重放日志的ver no，因此无需执行重放操作；即使没有新WS进行修改，也无需重放，此时是petal上的ver no等于重放日志中的ver no。

   因此WS3只会进行读取操作，而不会进行任何的实际更新操作。

综上两种情况所述，我们无须担心恢复软件是否需要提前获取相关数据块的锁的问题。因为一切情况的发生都是安全的，都是可以通过相关机制解决的。

9.5 扩展能力

Frangipani在不影响现有工作站速度的情况下，可以添加更多的工作站来赋予系统更多的计算资源 。

9.6 总结

frangipani主要用于小团体的协作，该系统并没有真正的推进大型分布式存储的进步。frangipani的重点在于工作站的local cache和工作站本身上，重点在于缓存一致性和锁上面，这对读/写数据而言并不是非常有用。因为通常读取的数据都很大，缓存是很小的。这不适用于现代的大型存储分布式系统。