Frangipani 与 Cache Consistency
Intro
Frangipani 是一篇古早的分布式文件系统论文，来自我没听过的公司（Systems Research Center - Digital Equipment Corporation），Frangipani 这个词本身似乎是鸡蛋花的意思。从整体架构上来说，Frangipani就是一个网络文件系统（NFS，Network File System）。它的目标是与已有的应用程序一起工作，比如说一个运行在工作站上的普通 UNIX 程序。
每个用户有一台 PC / Work Station，每台上面运行了一个 Frangipani 软件。系统内核中也有一个 Frangipani 模块，实现了文件系统。用户可以用什么 vim，什么 gcc 正常地操作这些文件。
至于实际的文件数据，例如文件内容、inode、目录、目录的文件列表、inode 和块的空闲状态，则存储在一些远端的其他服务器中，这些服务器被称为 Petal 花瓣。每个 Petal 服务器都还会有一个镜像副本，所以可以认为是成对出现。当 Frangipani 需要读写文件时，它会向正确的 Petal 服务器发送 RPC，并说，我需要这个块，请读取这个块，并将数据返回给我。在大部分时候，Petal 表现的就像是一个磁盘，你可以把它看做是共享的磁盘，所有的 Frangipani 都会与之交互。
论文作者期望使用 Frangipani 的目的，是驱动设计的一个重要因素。作者想通过 Frangipani 来支持他们自己的一些活动，作者们是一个研究所的成员，假设研究所有 50 个人，他们习惯于使用共享的基础设施，例如分时间段使用同一批服务器，工作站。他们还期望通过网络文件系统在相互协作的研究员之间共享文件。所以他们想要这样一个文件系统，它可以用来存放每一个研究员的 home 目录，同时也可以存放共享的项目文件。这意味着，如果我编辑了一个文件，我希望其他与我一起工作的人可以读到我刚刚编辑的文件。他们期望达成这样的共享的目的。
除此之外，如果我坐在任意一个工作站前面，我都能获取到所有的文件，包括了我的 home 目录，我环境中所需要的一切文件。所以他们需要的是一个在相对小的组织中，针对普通使用者的共享文件系统。相对小的组织的意思是，每个人在每台工作站前都被信任。本质上来说，Frangipani 的设计并没有讨论安全。在一个类似 Athena 的系统中，是不能随意信任使用者和工作站。所以，Frangipani 是针对作者自己环境的一个设计。
另外，为了提高速度，PC 们一般刚开始都把修改缓存在本地而不是直接往 Petal 里写，最后进行一次整体的 RPC，这样的 write back 有着更高的效率。毕竟远端服务器的读写相应肯定高了一些数量级。
在 Frangipani 的设计中，Petal 作为共享存储系统存在，它不知道文件系统，文件，目录，它只是一个很直观简单的存储系统，所有的复杂的逻辑都在工作站中的 Frangipani 模块中。所以这是一个非常去中心化的设计。
这种设计有好的影响。因为主要的复杂度，主要的 CPU 运算在每个工作站上，这意味着，随着你向系统增加更多的工作站，增加更多的用户，你自动的获得了更多的 CPU 算力来运行这些新的用户的文件系统操作。因为大部分的文件系统操作只在工作站本地发生，所以大部分 CPU 消耗的都是本地的，所以这个系统的天然自带扩展性。每个新工作站会接收来自一个新用户更多的负担，但是它同时也带来更多的 CPU 算力来运行那个用户的文件系统操作。
当然，在某个时间点，瓶颈会在 Petal。因为这是一个中心化的存储系统，这时，你需要增加更多的存储服务器。
这个架构引发的最大挑战还是在于，它在 PC 里面做了大量的缓存，并且文件的修改可以在本地缓存完成，引出了缓存一致性问题。
Lock Server && Cache Coherence
Frangipani的第一个挑战是缓存一致性（Cache Coherence），这个词和 Cache Consistency 不同也许纯粹是历史原因。在这里我们想要的是线性一致性和缓存带来的好处。对于线性一致性来说，当我查看文件系统中任何内容时，我总是能看到最新的数据。对于缓存来说，我们想要缓存带来的性能提升。某种程度上，我们想要同时拥有这两种特性的优点。
Frangipani 的缓存一致性核心是由锁保证的，我们之后在原子性和故障恢复中将会再次看到锁。但是现在，我们只讨论用锁来保证缓存一致，用锁来帮助工作站确定当它们缓存了数据时，它们缓存的是最新的数据。
在 Petal Servers 中，我们还有一个 Lock Server（也可以分片，变成一些），它存储了一个 Lock 表单，对于每一个文件，都有一个锁，这个锁可以被某个 PC 持有。这里先讨论简单的互斥锁，后续的读写锁也并不难懂。
假设文件X最近被工作站 WS1 使用了，所以 WS1 对于文件 X 持有锁。同时文件 Y 最近被工作站 WS2 使用，所以 WS2 对于文件 Y 持有锁。锁服务器会记住每个文件的锁被谁所持有。当然一个文件的锁也有可能不被任何人持有。
Lock Server
| File | Locker |
|---|---|
| x | WS1 |
| y | WS2 |
另外，在每个 PC / Work Station 内，也会记录跟踪它持有的锁，和文件的相关数据放在一起。
当一个 Frangipani 服务器决定要读取文件，比如读取目录 /、读取文件 A、查看一个 inode，首先，它会向一个锁服务器请求文件对应的锁，之后才会向 Petal 服务器请求文件或者目录的数据。收到数据之后，工作站会记住，本地有一个文件 X 的拷贝，对应的锁的状态，和相应的文件内容。
每一个工作站的锁至少有两种模式。工作站可以读或者写相应的文件或者目录的最新数据，可以在创建，删除，重命名文件的过程中，如果这样的话，我们认为锁在 Busy 状态。
在工作站完成了一些操作之后，比如创建文件，或者读取文件，它会随着相应的系统调用（例如rename，write，create，read）释放锁。只要系统调用结束了，工作站会在内部释放锁，现在工作站不再使用那个文件。但是从锁服务器的角度来看，工作站仍然持有锁。工作站内部会标明，这是锁时 Idle 状态，它不再使用这个锁。所以这个锁仍然被这个工作站持有，但是工作站并不再使用它。
Work Station Frangipani
| File | Lock | Content |
|---|---|---|
| x | Busy | xixi |
| y | Idle | haha |
为了保证缓存一致性，Frangipani 规定必须持有锁才能缓存数据到本地来读写。而在归还 Lock Server 端的文件锁前，必须把所有的改动写回到 Petal Servers。
这里本机的 Lock 状态为 Idle 是干什么的呢？
考虑到比如一个文件被创建，那接下来非常非常可能继续修改它，但创建完会把本机的锁暂时标记为 Idle，远端 Petal 的锁还没释放。这时候继续修改就可以直接把 Idle 再置 Busy，也就是少了一次归还和获取，提高效率，另外也可以 piggyback（捎带，多次合为一次） 地写回。
如果一个文件在本机 Idle 了 30 秒，那会自动触发写回，并释放锁。
如果有其他 PC 想获取这个文件的锁，那 Lock Server 会给持有锁的这台 PC 发一个 Revoke 指示，请他把锁归还。如果持有锁的 PC 还在 Busy，那就阻塞，等 Idle 了归还。如果已经 Idle 了，直接归还这把锁。归还了之后，Lock Server 才把锁交给其他 PC。
Atomicity
一个事务完成前，我们希望其他 PC 看不到。如果崩溃了，我们希望不要把中间结果放在 Petal Servers 里。
这里其实非常简单，比如我们一个事务要把文件 A 从目录 M 移到目录 N，那么我们就获取文件 A 、目录 M、目录 N 这样全部的锁，再开始操作，并且操作在本机缓存执行。全部完成后再写回 Petal Servers。在事务期间，其他 PC 无法读写这些文件。在事务结束后，它们可以看到变化。如果事务期间，本 PC 崩溃，那 Petal Servers 也还没有被修改。
对于锁来说，这里有一件有意思的事情，Frangipani 使用锁实现了两个几乎相反的目标。对于缓存一致性，Frangipani 使用锁来确保写操作的结果对于任何读操作都是立即可见的，所以对于缓存一致性，这里使用锁来确保写操作可以被看见。但是对于原子性来说，锁确保了人们在操作完成之前看不到任何写操作，因为在所有的写操作完成之前，工作站持有所有的锁。
Log && Crash Recovery
首先我们还是需要 Write Ahead Log (WAL)，因为终究有一个要把更新内容写回 Petal 的时候，如果这个过程中间崩溃了，我们不能让这样的半成品影响 Petal 的数据。
Frangipani 的 log 形式非常神秘。首先是每个 PC 的 Frangipani 软件自己独有自己的操作 log 而不是所有数据一起，另外，这个独有的 log 居然是放在 Petal 里的而不是放在本机的。Petal 中为每个 PC 的 Log 留了一块空间。
有了 Log，把数据写回 Petal 的完整过程为：先写回 Log，再写回数据，最后通知 Lock Server 释放锁。
因为有了 Log，所以崩溃才是可恢复的。Lock Server 在检查到某个 PC 挂了之后，会把这个 PC 占有的锁全部释放，避免某些文件陷入一直不可用的境地。然后我们来看看崩溃恢复的情况：
- 写回 Log 写到一半崩溃。后面别的 PC 用到相关文件时，会用某种标记意识到前一个占用者崩溃了，会把已经写入 Petal 的 Log 执行一遍，让上一台崩溃的 PC 的操作恢复一部分。（当然执行到一半的事务应当被废止来保证原子性，如果文件系统里有事务的话。这种废止应该由 Log 中的事务标记如 start commit 等来帮助完成）
- 写回数据到一半崩溃。此时 Log 已经完整了。别的 PC 并不知道数据写到哪了，所以也是把 Log 整个执行一遍。因为 Log 不是 x += 10 这种形式而是 x = 20 这样的值替换，所以重复执行的操作也并不会改变结果，后续未执行的操作被补齐。
上述后续 PC 对崩溃 PC 的操作恢复都是在本机完成，也是采用缓存->写回的步骤。
References
Lecture 11 - Cache Consistency: Frangipani - MIT6.824 (gitbook.io)
回过头来看，尽管 Frangipani 有大量有意思且值得记住的技术，但是它对于存储系统的演进并没有什么影响。部分原因是，Frangipani 的目标环境是一个小的工作组，人们坐在桌子上的工作站前共享文件。这样的环境现在还存在与某些地方，但是却不是分布式存储的主要应用场景。真正的应用场景是一些大型的数据中心、大型网站、大数据运算，在这些场景中，文件系统的接口相比数据库接口来说，就不是那么有用了。比如，在大型网站的环境中，人们非常喜欢事务，但是人们在非常小的数据下才需要事务，这些小的数据也就是你会存储在数据库中的数据，而不是你会存储在文件系统中的数据。所以这里的一些技术，你可以在一些现代的系统中看到类似的设计，但是通常出现在数据库中。
另一个大的场景是为大数据运算存储大的文件，例如 MapReduce。实际上 GFS 某种程度上看起来就像是一个文件系统，但是实际上是为了 MapReduce 设计的存储系统。但是不论对于 GFS 也好，还是大数据运算也好，Frangipani 关注在工作站的本地缓存和缓存一致性，反而不是很有用。如果你读取 10TB 的数据，缓存基本上没什么用，并且会适得其反。所以，随着时间的推移，Frangipani 在一些场合还是有用的，但是并不符合在设计新系统时候的需求。