MIT 6.824 -- Cache Consistency -- 11
MIT 6.824 -- Cache Consistency -- 11
课程b站视频地址: MIT 6.824 Distributed Systems Spring 2020 分布式系统
推荐伴读读物:
本节预习作业:
引言
Frangipani 是一篇关于分布式文件系统的古老论文，但是站在目前的角度来看，其更符合适用于小型团体的NFS(网络文件系统)实现。
该篇论文所描述的网络文件系统由两部分组成:
- 每个客户端本地都需要引入一个Frangipani服务，该服务负责对上提供类UNIX文件系统接口，对下负责与Petal集中式存储服务进行通信与数据传输服务。
- 文件系统的数据结构，如: 文件内容，Inode，目录，目录的文件列表，inode和块的空闲状态，这些数据都存储在一个叫Petal的共享虚拟磁盘服务中。
Petal 会运行在不同的服务器上，还会提供分片，副本机制来支持高可用和容错性。当Frangipani需要读写文件时，它会向正确的Petal服务器发送RPC。整个Petal表现的就像是一个磁盘，可以将其看做是共享磁盘，所有Frangipani都会与之交互。
出于性能考虑，Frangipani会在本地缓存中缓存读取到的文件数据，同时采用Write-Back将脏数据异步写回Petal。同时Frangipani服务负责实现文件系统相关的逻辑，Petal只是作为简单的共享存储系统存在，它不关心文件和目录这些概念，以此来实现一个去中心化的设计。
解释一下Frangipani服务负责实现文件系统逻辑的含义:
- Frangipani服务通过Write-Back缓存来管理文件数据信息，这意味着我们对文件的所有修改操作都是发生在缓存中的，比如创建文件时，我们会新创建inode，初始化内容，对应目录列表更新，这些修改都只存在于本地缓存中，稍后才会被写回Petal中。
- 为了让Frangipani服务可以通过操作内存就完成类似创建文件的事情，这意味着我们需要把对文件系统的逻辑和设计在Frangipani服务中也实现一遍。
由于这种去中心化的设计，导致大部分CPU运算逻辑都集中在Frangipani服务中，这意味着我们可以通过增加更多的用户，来获得更多的CPU算力，以此来同时运行更多的文件系统操作。因为大部分的文件系统操作只在客户端本地发生，所以大部分CPU消耗的都是本地的，所以这个系统的天然自带扩展性。
关键点在于此处的本地缓存和异步写回，意味着客户端无需频繁与Petal进行交互，只需要与本地的Frangipani服务进行交互即可。
在某个时间点，瓶颈会在Petal。因为这是一个中心化的存储系统，这时，你需要增加更多的存储服务器。
所以，我们现在有了一个系统，它在客户端本地做了大量的缓存，并且文件的修改可以在本地缓存完成。这会导致我们面临一些严峻挑战。
严峻挑战
Frangipani的挑战主要来自于三方面:
- 缓存一致性问题
- 原子性问题
- 崩溃恢复问题
第一个问题，假设用户1发起了创建文件请求，然后在本地缓存中完成了在dhy目录下创建Main.go文件的任务，由于采用Write-Back机制，此时修改产生的脏数据并不会立马同步回Petal中。
用户2接着发起文件查询请求，他想要获取/dhy目录下的所有文件，但是由于用户1的写操作还未同步回Petal，所以用户2此时无法看到用户1创建的Main.go文件，这就是由于缓存导致的不一致性问题。
另一个问题就是丢失更新问题或者在该场景下还可以成为原子性问题，假设用户1尝试在/dhy目录下创建Main1.go文件，用户2尝试在/dhy目录下创建Main2.go文件，这两个操作看似不冲突，但是他们都需要为/dhy目录增加一个新的目录项，所以这里的问题是，当他们同时操作时，系统能识别这些修改了相同目录的操作，并得到一些有意义的结果吗？
这里的有意义的结果是指，A和B最后都要创建成功，我们不想只创建一个文件，因为第二个文件的创建有可能会覆盖并取代第一个文件。
之所以称当前问题为原子性问题，是因为我们期望类似于创建文件，删除文件这样的操作表现的就像即时生效一样，同时不会与同时发生的其他操作相互干扰。
最后一个问题是，假设客户端修改了大量的内容，由于Write-Back缓存，可能会在本地的缓存中堆积了大量的修改。如果客户端崩溃了，但是这时这些修改只有部分同步到了Petal，还有部分仍然只存在于本地。同时，其他的客户端还在使用文件系统。那么，客户端在执行操作的过程中的崩溃，最好不要损坏其他人同样会使用的文件系统。
这意味着，我们需要的是单个服务器的故障恢复，我希望某个客户端的崩溃不会影响其他使用同一个共享系统的客户端。哪怕说这些客户端正在查看我的目录，我的文件，它们应该看到一些合理的现象。它们可以漏掉我最后几个操作，但是它们应该看到一个一致的文件系统，而不是一个损坏了的文件系统数据。所以这里我们希望有故障恢复。
锁服务
Frangipani的第一个挑战是缓存一致性。在这里我们想要的是线性一致性和缓存带来的好处。对于线性一致性来说，当我查看文件系统中任何内容时，我总是能看到最新的数据。对于缓存来说，我们想要缓存带来的性能提升。某种程度上，我们想要同时拥有这两种特性的优点。
Frangipani的缓存一致性核心是由锁保证的，我们之后在原子性和故障恢复中将会再次看到锁。但是现在，我们只讨论用锁来保证缓存一致，用锁来帮助客户端确定当它们缓存了数据时，它们缓存的是最新的数据。
除了Frangipani服务器（也就是客户端），Petal存储服务器，在Frangipani系统中还有第三类服务器，锁服务器。尽管你可以通过分片将锁分布到多个服务器上，但是我接下来会假设只有一个锁服务器。逻辑上，锁服务器是独立的服务器，但是实际上我认为它与Petal服务器运行在一起。在锁服务器里面，有一个表单，就叫做locks。我们假设每一个锁以文件名来命名，所以对于每一个文件，我们都有一个锁，而这个锁，可能会被某个客户端所持有。
下面举例说明锁服务器工作流程:
- 假设文件X最近被客户端1使用了，所以客户端1对于文件X持有锁。同时文件Y最近被客户端2使用，所以客户端2对于文件Y持有锁。锁服务器会记住每个文件的锁被谁所持有。当然一个文件的锁也有可能不被任何人持有。
- 在每个客户端，会记录跟踪它所持有的锁，和锁对应的文件内容。所以在每个客户端中，Frangipani模块也会有一个lock表单，表单会记录文件名、对应的锁的状态和文件的缓存内容。这里的文件内容可能是大量的数据块，也可能是目录的列表。
由于分片都采用分块存储，所以这里加锁粒度可以细化到chunk层级。
- 当一个Frangipani服务器决定要读取文件，比如读取目录 /、读取文件X、查看一个inode，首先，它会向一个锁服务器请求文件对应的锁，之后才会向Petal服务器请求文件或者目录的数据。收到数据之后，客户端会记住，本地有一个文件X的拷贝，对应的锁的状态，和相应的文件内容。
- 每一个客户端的锁至少有两种模式。客户端可以读或者写相应的文件或者目录的最新数据，可以在创建，删除，重命名文件的过程中，如果这样的话，我们认为锁在Busy状态。
- 在客户端完成了一些操作之后，比如创建文件，或者读取文件，它会随着相应的系统调用（例如rename，write，create，read）释放锁。只要系统调用结束了，客户端会在内部释放锁，现在客户端不再使用那个文件。但是从锁服务器的角度来看，客户端仍然持有锁。客户端内部会标明，这时锁是Idle状态，它不再使用这个锁。所以这个锁仍然被这个客户端持有，但是客户端并不再使用它。这在稍后的介绍中比较重要。
Frangipani这里应用了很多规则，这些规则使得Frangipani以一种提供缓存一致性的方式来使用锁，并确保没有客户端会使用缓存中的旧数据。这些规则、锁、缓存数据需要配合使用。这里的规则包括：
- 客户端不允许持有缓存的数据，除非同时也持有了与数据相关的锁。所以基本上来说，不允许在没有锁保护的前提下缓存数据。从操作意义上来说，这意味着对于客户端来说，在它使用一个数据之前，它首先要从锁服务器获取数据的锁。只有当客户端持有锁了，客户端才会从Petal读取数据，并将数据放在缓存中。
- 所以这里的顺序是，获得锁，之后再从Petal读取数据。所以，直到获取了锁，客户端是不能缓存数据的，要想缓存数据，客户端必须先持有锁，之后，才能从Petal读取数据。
- 如果你在释放锁之前，修改了锁保护的数据，那你必须将修改了的数据写回到Petal，只有在Petal确认收到了数据，你才可以释放锁，也就是将锁归还给锁服务器。
- 所以这里的顺序是，先向Petal存储系统写数据，之后再释放锁。
- 最后再从客户端本地的lock表单中删除关文件的锁的记录和缓存的数据。
缓存一致性问题
客户端和锁服务器之间的缓存一致协议协议包含了4种不同的消息。本质上你可以认为它们就是一些单向的网络消息。
- 首先是Request消息，从客户端发给锁服务器。Request消息会说：hey锁服务器，我想获取这个锁。
- 如果从锁服务器的lock表单中发现锁已经被其他人持有了，那锁服务器不能立即交出锁。但是一旦锁被释放了，锁服务器会回复一个Grant消息给客户端。这里的Request和Grant是异步的。
- 如果你向锁服务器请求锁，而另一个客户端现在正持有锁，锁服务器需要持有锁的客户端先释放锁，因为一个锁不能同时被两个人持有。那我们怎么能让这个客户端获取到锁呢？
前面说过，如果一个客户端在使用锁，并在执行读写操作，那么它会将锁标记为Busy。但是通常来说，当客户端使用完锁之后，不会向锁服务器释放锁。所以，如果我创建了一个新文件，create函数返回时，这些新文件的锁仍然被当前客户端持有。只是说现在锁的状态会变成Idle而不是Busy。但是从锁服务器看来，当前客户端仍然持有锁。
这里延迟将锁还给锁服务器的原因是，如果当前客户端创建了文件Y。我接下来几乎肯定要将Y用于其他目的，或许我向它写一些数据，或许会从它读数据。所以，如果客户端能持有所有最近用过的文件的锁并不主动归还的话，会有非常大的优势。在一个常见的例子中，我使用了home目录下的一些文件，并且其他客户端没有人查看过这些文件。当前客户端最后会为我的文件持有数百个在Idle状态的锁。但是如果某人查看了我的文件，他需要先获取锁，而这时我就需要释放锁了。
所以这里的工作方式是，如果锁服务器收到了一个加锁的请求，它查看自己的lock表单可以发现，这个锁现在正被客户端1所持有，锁服务器会发送一个Revoke消息给当前持有锁的客户端1。并说，现在别人要使用这个文件，请释放锁吧。
当客户端收到了一个Revoke请求，如果锁时在Idle状态，并且缓存的数据脏了，客户端会首先将修改过的缓存写回到Petal存储服务器中，因为前面的规则要求在释放锁之前，要先将数据写入Petal。所以如果锁的状态是Idle，首先需要将修改了的缓存数据发回给Petal，只有在那个时候，客户端才会再向锁服务器发送一条消息说，好吧，我现在放弃这个锁。所以，对于一个Revoke请求的响应是，客户端会向锁服务器发送一条Release消息。
如果客户端收到Revoke消息时，它还在使用锁，比如说正在删除或者重命名文件的过程中，直到客户端使用完了锁为止，或者说直到它完成了相应的文件系统操作，它都不会放弃锁。完成了操作之后，客户端中的锁的状态才会从Busy变成Idle，之后客户端才能注意到Revoke请求，在向Petal写完数据之后最终释放锁。
以上就是Frangipani使用的缓存一致性协议的一个简单版本的描述。这里面没有考虑一个事实，那就是锁可以是为写入提供的排他锁（Exclusive Lock），也可以是为只读提供的共享锁（Shared Lock）。
就像Petal只是一个块存储服务，并不理解文件系统。锁服务器也不理解文件，目录，还有文件系统，它只是维护lock表单，表单中记录的是锁的名字和锁的持有者。Frangipani可以理解锁与某个文件相关联。实际上Frangipani在这里使用的是Unix风格的inode号来作为lock表单的key，而不是文件的名字。
案例演示
本节以一个案例作为演示，来看一下此处缓存一致性协议工作的整个流程。
- 首先我们有两个客户端和一个锁服务器
- 按照协议，如果客户端1想要读取并修改文件Z。在它从Petal读取文件之前，它需要先获取对于Z的锁，所以它向锁服务器发送Request消息
- 如果当前没有人持有对文件Z的锁，或者锁服务器没听过对于文件Z的锁（初始化状态），锁服务器会在lock表单中增加一条记录，并返回Grant消息给客户端1说，你现在持有了对于Z文件的锁
- 从这个时间点开始，客户端1持有了对文件Z的锁，并且被授权可以从Petal读取Z的数据。所以这个时间点，客户端1会从Petal读取并缓存Z的内容。之后，客户端1也可以在本地缓存中修改Z的内容。
- 过了一会，客户端2也想读取文件Z。但是一开始客户端2并没有对于文件Z的锁，所以它要做的第一件事情就是向锁服务器发送Request消息，请求对于文件Z的锁
- 但是，锁服务器知道不能给客户端2回复Grant消息，因为客户端1现在还持有锁。接下来锁服务器会向客户端1发送Revoke消息
- 而客户端1在向Petal写入修改数据之前，不允许释放锁。所以它现在会将任何修改的内容写回给Petal
- 写入结束之后，客户端1才可以向锁服务器发送Release消息
- 锁服务器必然会有一个表单记录谁在等待文件Z的锁，一旦锁的当前持有者释放了锁，锁服务器需要通知等待者。所以当锁服务器收到了这条Release消息时，锁服务器会更新自己的表单，并最终将Grant消息发送给客户端2
- 这个时候，客户端2终于可以从Petal读取文件Z
这就是缓存一致性协议的工作流程，它确保了，直到所有有可能私底下在缓存中修改了数据的客户端先将数据写回到Petal，其他客户端才能读取相应的文件。所以，这里的锁机制确保了读文件总是能看到最新写入文件的数据。
优化
在这个缓存一致性的协议中，有许多可以优化的地方。比如锁的懒释放:
- 每个客户端用完了锁之后，不是立即向锁服务器释放锁，而是将锁的状态标记为Idle就是一种优化
另一个主要的优化是，Frangipani有共享的读锁（Shared Read Lock）和排他的写锁（Exclusive Write Lock）。如果有大量的客户端需要读取文件，但是没有人会修改这个文件，它们都可以同时持有对这个文件的读锁。如果某个客户端需要修改这个已经被大量其他客户端缓存的文件时，那么它首先需要Revoke所有客户端的读锁，这样所有的客户端都会放弃自己对于该文件的缓存，只有在那时，当前客户端才可以修改文件。因为没有人持有了这个文件的缓存，所以就算文件被修改了，也没有人会读到旧的数据。
最后再提一下脏数据写回时机，客户端每隔30秒会将所有修改了的缓存写回到Petal中。所以，如果某个客户端突然崩溃了，我或许会丢失过去30秒的数据，但是不会丢更多，这实际上是模仿Linux或者Unix文件系统的普通工作模式。在一个分布式文件系统中，很多操作都是在模仿Unix风格的文件系统，这样使用者才不会觉得Frangipani的行为异常，因为它基本上与用户在使用的文件系统一样。
原子性问题
当我做了一个复杂的操作，比如说创建一个文件，这里涉及到标识一个新的inode、初始化一个inode（inode是用来描述文件的一小份数据）、为文件分配空间、在目录中为新文件增加一个新的名字，这里有很多步骤，很多数据都需要更新。我们不想任何人看到任何中间的状态，我们希望其他的客户端要么发现文件不存在，要么文件完全存在，但是我们绝不希望它看到中间状态。所以我们希望多个步骤的操作具备原子性。
为了实现原子性，为了让多步骤的操作，例如创建文件，重命名文件，删除文件具备原子性，Frangipani在内部实现了一个数据库风格的事务系统，并且是以锁为核心。
简单来说，Frangipani是这样实现分布式事务的：
- 在完全完成操作之前，Frangipani确保其他的客户端看不到当前客户端的修改。
- 首先当前客户端获取所有读写数据的锁，在完成操作之前，客户端不会释放任何一个锁。
- 并且为了遵循一致性规则，将所有修改了的数据写回到Petal之后，客户端才会释放所有的锁。
比如我将文件从一个目录移到另一个目录，这涉及到修改两个目录的内容，我不想让人看到两个目录都没有文件的状态。为了实现这样的结果，Frangipani首先会获取执行操作所需要的所有数据的锁，之后完成所有的步骤，比如完成所有数据的更新，并将更新写入到Petal，最后释放锁。
因为我们有了锁服务器和缓存一致性协议，我们只需要确保我们在整个操作的过程中持有所有的锁，我们就可以无成本的获得这里的不可分割原子事务。
所以为了让操作具备原子性，Frangipani持有了所有的锁。对于锁来说，这里有一件有意思的事情，Frangipani使用锁实现了两个几乎相反的目标。对于缓存一致性，Frangipani使用锁来确保写操作的结果对于任何读操作都是立即可见的，所以对于缓存一致性，这里使用锁来确保写操作可以被看见。但是对于原子性来说，锁确保了人们在操作完成之前看不到任何写操作，因为在所有的写操作完成之前，客户端持有所有的锁。
故障恢复问题
我们需要能正确应对这种场景：一个客户端持有锁，并且在一个复杂操作的过程中崩溃了。比如说一个客户端在创建文件，或者删除文件时，它首先获取了大量了锁，然后会更新大量的数据，在其向Petal回写数据的过程中，一部分数据写入到了Petal，还有一部分还没写入，这时客户端崩溃了，并且锁也没有释放（因为数据回写还没有完成）。这是故障恢复需要考虑的有趣的场景。
这里有一些很直接的解决方式，但是都存在些许问题:
- 其中一种处理方法是，如果发现客户端崩溃了，就释放它所有的锁。假设客户端在创建新文件，它已经在Petal里将文件名更新到相应的目录下，但是它还没有将描述了文件的inode写入到Petal，Petal中的inode可能还是一些垃圾数据，这个时候是不能释放崩溃客户端持有的锁（因为其他客户端读取这个文件可能读出错误的数据）。
- 另一种处理方法是，不释放崩溃了的客户端所持有的锁。如果客户端在向Petal写入数据的过程中崩溃了，因为它还没有写完所有的数据，也就意味着它不能释放所有的锁。所以，简单的不释放锁是正确的行为，因为这可以将这里的未完成的更新向文件的读取者隐藏起来，这样没人会因为看到只更新了一半的数据而感到困惑了。但是另一方面，如果任何人想要使用这些文件，那么他需要永远等待锁，因为我们没有释放这些锁。
第二种方式也不可行，因为我们绝对需要释放锁，这样其他的客户端才能使用这个系统，使用相同的文件和目录。但同时，我们也需要处理这种场景：崩溃了的客户端只写入了与操作相关的部分数据，而不是全部的数据。
Frangipani与其他的系统一样，需要通过预写式日志（Write-Ahead Log，WAL）实现故障可恢复的事务（Crash Recoverable Transaction）。
当一个客户端需要完成涉及到多个数据的复杂操作时，在客户端向Petal写入任何数据之前，客户端会在Petal中自己的Log列表中追加一个Log条目，这个Log条目会描述整个的需要完成的操作。只有当这个描述了完整操作的Log条目安全的存在于Petal之后，客户端才会开始向Petal发送数据。所以如果客户端可以向Petal写入哪怕是一个数据，那么描述了整个操作、整个更新的Log条目必然已经存在于Petal中。
这是一种非常标准的行为，它就是WAL的行为。但是Frangipani在实现WAL时，有一些不同的地方。 第一个是，在大部分的事务系统中，只有一个Log，系统中的所有事务都存在于这个Log中。当有故障时，如果有多个操作会影响同一份数据，我们在这一个Log里，就会保存这份数据的所有相关的操作。所以我们知道，对于一份数据，哪一个操作是最新的。但是Frangipani不是这么保存Log的，它对于每个客户端都保存了一份独立的Log。
另一个有关Frangipani的Log系统有意思的事情是，客户端的Log存储在Petal，而不是本地磁盘中。几乎在所有使用了Log的系统中，Log与运行了事务的计算机紧紧关联在一起，并且几乎总是保存在本地磁盘中。但是出于优化系统设计的目的，Frangipani的客户端将自己的Log保存在作为共享存储的Petal中。每个客户端都拥有自己的半私有的Log，但是却存在Petal存储服务器中。这样的话，如果客户端崩溃了，它的Log可以被其他客户端从Petal中获取到。所以Log存在于Petal中。
这里其实就是，每个客户端的独立的Log，存放在公共的共享存储中，这是一种非常有意思，并且反常的设计。
log内容
每个客户端的Log存在于Petal已知的块中，并且，每个客户端以一种环形的方式使用它在Petal上的Log空间。Log从存储的起始位置开始写，当到达结尾时，客户端会回到最开始，并且重用最开始的Log空间。所以客户端需要能够清除它的Log，这样就可以确保，在空间被重复利用之前，空间上的Log条目不再被需要。
每个Log条目都包含了Log序列号，这个序列号是个自增的数字，每个客户端按照12345为自己的Log编号，这里直接且唯一的原因在论文里也有提到，如果客户端崩溃了，Frangipani会探测客户端Log的结尾，Frangipani会扫描位于Petal的Log直到Log序列号不再增加，这个时候Frangipani可以确定最后一个Log必然是拥有最高序列号的Log。所以Log条目带有序列号是因为Frangipani需要检测Log的结尾。
除此之外，每个Log条目还有一个用来描述一个特定操作中所涉及到的所有数据修改的数组。数组中的每一个元素会有一个Petal中的块号（Block Number），一个版本号和写入的数据。类似的数组元素会有多个，这样就可以用来描述涉及到修改多份文件系统数据的操作。
这里有一件事情需要注意，Log只包含了对于元数据的修改，比如说文件系统中的目录、inode、bitmap的分配。Log本身不会包含需要写入文件的数据，所以它并不包含用户的数据，它只包含了故障之后可以用来恢复文件系统结构的必要信息。例如，我在一个目录中创建了一个文件F，那会生成一个新的Log条目，里面的数组包含了两个修改的描述，一个描述了如何初始化新文件的inode，另一个描述了在目录中添加的新文件的名字。
这里比较疑惑一点在于:
- 如果Log只包含了元数据的修改，那么在故障恢复的时候，文件的内容都丢失了，也就是对于创建一个新文件的故障恢复只能得到一个空文件，这不太合理。
当然，Log是由多个Log条目组成，每个条目由块号，版本号，写入数据三部分组成。
为了能够让操作尽快的完成，最初的时候，Frangipani客户端的Log只会存在客户端的内存中，并尽可能晚的写到Petal中。这是因为，向Petal写任何数据，包括Log，都需要花费较长的时间，所以我们要尽可能避免向Petal写入Log条目，就像我们要尽可能避免向Petal写入缓存数据一样。
所以，这里的完整的过程是。当客户端从锁服务器收到了一个Revoke消息，要自己释放某个锁，它需要执行好几个步骤。
- 首先，客户端需要将内存中还没有写入到Petal的Log条目写入到Petal中。
- 之后，再将被Revoke的Lock所保护的数据写入到Petal。
- 最后，向锁服务器发送Release消息。
这里采用这种流程的原因是，在第二步我们向Petal写入数据的时候，如果我们在中途故障退出了，我们需要确认其他组件有足够的信息能完成我们未完成修改。先写入Log将会使我们能够达成这个目标：
- 这些Log记录是对将要做的修改的完整记录。所以我们需要先将完整的Log写入到Petal。之后客户端可以开始向Petal写入其修改了的块数据，这个过程中，可能会故障，也可能不会。
- 如果客户端完成了向Petal写入块数据，它就能向锁服务发送Release消息。
- 所以，如果我的客户端修改了一些文件，之后其他的客户端想要读取这些文件，上面的才是一个实际的工作流程。
- 锁服务器要我释放锁，我的客户端会先向Petal写入Log，之后再向Petal写入脏的块数据，最后才向锁服务器发送Release消息。
- 之后，其他的客户端才能获取锁，并读取相应的数据块。这是没有故障的时候对应的流程。
如果我们收到了一个针对特定文件Z的Revoke消息，客户端会将整个Log都写入Petal，或许写入完整的Log显得没那么必要，在这里可以稍作优化。如果Revoke要撤回的锁对应的文件Z只涉及第一个Log，并且客户端中的其他Log并没有修改文件Z，那么可以只向Petal写入一个Log，剩下的Log之后再写入，这样可以节省一些时间。
故障恢复
当客户端需要重命名文件或者创建一个文件时，首先它会获得所有需要修改数据的锁，之后修改自身的缓存来体现改动。但是后来客户端在向Petal写入数据的过程中故障了。客户端可能在很多个位置发生故障，但是由于前面介绍过的工作流程，Frangipani总是会先将自身的Log先写入到Petal。这意味着如果发生了故障，那么发生故障时可能会有这几种场景：
- 要么客户端正在向Petal写入Log，所以这个时候客户端必然还没有向Petal写入任何文件或者目录。
- 要么客户端正在向Petal写入修改的文件，所以这个时候客户端必然已经写入了完整的Log。
当持有锁的客户端崩溃了之后，发生的第一件事情是锁服务器向客户端发送一个Revoke消息，但是锁服务器得不到任何响应，之后才会触发故障恢复。如果没有人需要用到崩溃客户端持有的锁，那么基本上没有人会注意到客户端崩溃了。假设一个其他的客户端需要崩溃了的客户端所持有的一个锁，锁服务器会发出Revoke消息，但是锁服务器永远也不会从崩溃了的客户端收到Release消息。
Frangipani出于一些原因对锁使用了租约，当租约到期了，锁服务器会认定客户端已经崩溃了，之后它会初始化恢复过程。实际上，锁服务器会通知另一个还活着的客户端说：看，客户端1看起来崩溃了，请读取它的Log，重新执行它最近的操作并确保这些操作完成了，在你完成之后通知我。在收到这里的通知之后，锁服务器才会释放锁。这就是为什么日志存放在Petal是至关重要的，因为一个其他的客户端可能会要读取这个客户端在Petal中的日志。
发生故障的场景究竟有哪些呢？
- 第一种场景是，客户端1在向Petal写入任何信息之前就故障了。这意味着，当客户端2执行恢复，查看崩溃了的客户端的Log时，发现里面没有任何信息，自然也就不会做任何操作。之后客户端2会释放客户端1所持有的锁。客户端1或许在自己的缓存中修改了各种各样的数据，但是如果它没有在自己的Log存储区写入任何信息，那么它也不可能在Petal中写入任何它修改的块数据。我们会丢失客户端1的最后几个操作，但是文件系统会与客户端1开始修改之前保持一致。因为很明显，客户端1没能走到向Petal写Log那一步，自然也不可能向Petal写入块数据。
- 第二种场景是，客户端1向Petal写了部分Log条目。这样的话，执行恢复的客户端2会从Log的最开始向后扫描，直到Log的序列号不再增加，因为这必然是Log结束的位置。
- 客户端2会检查Log条目的更新内容，并向Petal执行Log条目中的更新内容。比如Petal中的特定块需要写入特定的数据，这里对应的其实就是客户端1在自己本地缓存中做的一些修改。所以执行恢复的客户端2会检查每个Log条目，并重新向Petal执行客户端1的每一条Log。
- 当客户端2执行完客户端1存放在Petal中的Log，它会通知锁服务器，之后锁服务器会释放客户端1持有的锁。这样的过程会使得Petal更新至故障客户端1在故障前的执行的部分操作。
- 或许不能全部恢复客户端1的操作，因为故障客户端可能只向Petal写了部分Log就崩溃了。同时，除非在Petal中找到了完整的Log条目，否则执行恢复的客户端客户端2是不会执行这条Log条目的，所以，这里的隐含意思是需要有类似校验和的机制，这样执行恢复的客户端就可以知道，这个Log条目是完整的，而不是只有操作的一部分数据。
- 这一点很重要，因为在恢复时，必须要在Petal的Log存储区中找到完整的操作。所以，对于一个操作的所有步骤都需要打包在一个Log条目的数组里面，这样执行恢复的客户端就可以，要么全执行操作的所有步骤，要么不执行任何有关操作的步骤，但是永远不会只执行部分步骤。这就是当在向Petal写入Log时，发生了故障的修复过程。
- 另一个有趣的可能是，客户端1在写入Log之后，并且在写入块数据的过程中崩溃了。先不考虑一些极其重要的细节，执行恢复的客户端2并不知道客户端1在哪个位置崩溃的，它只能看到一些Log条目，同样的，客户端2会以相同的方式重新执行Log。尽管部分修改已经写入了Petal，客户端2会重新执行修改。对于部分已经写入的数据，相当于在相同的位置写入相同的数据。对于部分未写入的数据，相当于更新了Petal中的这部分数据，并完成了操作。
上面的描述并没有涵盖所有的场景，下面的这个场景会更加复杂一些。如果一个客户端，完成了上面流程的步骤1，2，在释放锁的过程中崩溃了，进而导致崩溃的客户端不是最后修改特定数据的客户端。具体可以看下面这个例子:
- 假设我们有一个客户端1，它执行了删除文件（d/f）的操作。
- 之后，有另一个客户端2，在删除文件之后，以相同的名字创建了文件，当然这是一个不同的文件。所以之后，客户端2创建了同名的文件（d/f）。
- 在创建完成之后，客户端1崩溃了，
- 所以，我们需要基于客户端1的Log执行恢复，这时，可能有第三个客户端3来执行恢复的过程。
这里的时序表明，客户端1删除了一个文件，客户端2创建了一个文件，客户端3做了恢复操作。有可能删除操作仍然在客户端1的Log中，当客户端1崩溃后，客户端3需要读取客户端1的Log，并重新执行客户端1的Log中的更新。因为删除文件的Log条目仍然存在于客户端1的Log中，如果不做任何额外的事情，客户端3会删除这个文件（d/f）。但是实际上，客户端3删除的会是客户端2稍后创建的一个完全不同的文件。
这样的结果是完全错误的，因为需要被删除的是客户端1指定的文件，而不是客户端2创建的一个相同名字的文件。因为客户端2的创建是在客户端1的删除之后，所以我们不能只是不经思考的重新执行客户端1的Log，客户端1的Log在我们执行的时候可能已经过时了，其他的一些客户端可能已经以其他的方式修改了相同的数据，所以我们不能盲目的重新执行Log条目。
Frangipani是这样解决这个问题的，通过对每一份存储在Petal文件系统数据增加一个版本号，同时将版本号与Log中描述的更新关联起来。在Petal中，每一个元数据，每一个inode，每一个目录下的内容，都有一个版本号，当客户端需要修改Petal中的元数据时，它会向从Petal中读取元数据，并查看当前的版本号，之后在创建Log条目来描述更新时，它会在Log条目中对应的版本号填入元数据已有的版本号加1。
之后，如果客户端执行到了写数据到Petal的步骤，它也会将新的增加了的版本号写回到Petal。
所以，如果一个客户端没有故障，并且成功的将数据写回到了Petal。这样元数据的版本号会大于等于Log条目中的版本号。如果有其他的客户端之后修改了同一份元数据，版本号会更高。
所以，实际上客户端3看到的客户端1的删除操作对应的Log条目，会有一个特定的版本号，它表明，由这个Log条目影响的元数据对应版本号3（举例）。
客户端2的修改在客户端1崩溃之前，所以客户端1必然已经释放了相关数据的锁。客户端2获得了锁，它会读取当前的元数据可以发现当前的版本号是3，当客户端2写入数据的时候，它会将版本号设置为4。
之后，当客户端3执行恢复流程时，客户端3会重新执行客户端1的Log，它会首先检查版本号，通过查看Log条目中的版本号，并查看Petal中存储的版本号，如果Petal中存储的版本号大于等于Log条目中的版本号，那么客户端3会忽略Log条目中的修改，因为很明显Petal中的数据已经被故障了的客户端所更新，甚至可能被后续的其他客户端修改了。所以在恢复的过程中，客户端3会选择性的根据版本号执行Log，只有Log中的版本号高于Petal中存储的数据的版本时，Log才会被执行。
这里有个比较烦人的问题就是，客户端3在执行恢复，但是其他的客户端还在频繁的读取文件系统，持有了一些锁并且在向Petal写数据。客户端3在执行恢复的过程中，客户端2是完全不知道的。客户端2可能还持有目录 d的锁，而客户端3在扫描故障客户端客户端1的Log时，需要读写目录d，但是目录d的锁还被客户端2所持有。我们该如何解决这里的问题？
一种不可行的方法是，让执行恢复的客户端3先获取所有关联数据的锁，再重新执行Log。这种方法不可行的一个原因是，有可能故障恢复是在一个大范围电力故障之后，这样的话谁持有了什么锁的信息都丢失了，因此我们也就没有办法使用之前的缓存一致性协议，因为哪些数据加锁了，哪些数据没有加锁在断电的过程中丢失了。
但是幸运的是，执行恢复的客户端可以直接从Petal读取数据而不用关心锁。这里的原因是，执行恢复的客户端想要重新执行Log条目，并且有可能修改与目录d关联的数据，它就是需要读取Petal中目前存放的目录数据。接下来只有两种可能，要么故障了的客户端客户端1释放了锁，要么没有。如果没有的话，那么没有其他人不可以拥有目录的锁，执行恢复的客户端可以放心的读取目录数据，没有问题。如果释放了锁，那么在它释放锁之前，它必然将有关目录的数据写回到了Petal。这意味着，Petal中存储的版本号，至少会和故障客户端的Log条目中的版本号一样大，因此，之后恢复软件对比Log条目的版本号和Petal中存储的版本号，它就可以发现Log条目中的版本号并没有大于存储数据的版本号，那么这条Log条目就会被忽略。所以这种情况下，执行恢复的客户端可以不持有锁直接读取块数据，但是它最终不会更新数据。因为如果锁被释放了，那么Petal中存储的数据版本号会足够高，表明在客户端故障之前，Log条目已经应用到了Petal。所以这里不需要关心锁的问题。
小结
本文主要讨论了以下内容:
- Petal是什么
- 缓存一致性
- 分布式事务
- 分布式故障恢复
论文还讨论了一下性能，但是过了20年之后的今天，很难理解这些性能数据。因为作者在一个与今天非常不同的硬件，非常不同的环境测试的性能。笼统来说，作者展示的性能数据表明，随着越来越多的Frangipani客户端加入到系统中，系统并没有明显变慢。即使新加入的客户端在频繁的执行文件系统操作，并不会影响现有的客户端。这样的话，系统可以提供合理的扩展性，因为它可以在不减慢现有客户端的前提下增加更多的客户端。
尽管Frangipani有大量有意思且值得记住的技术，但是它对于存储系统的演进并没有什么影响。部分原因是，Frangipani的目标环境是一个小的工作组，人们坐在桌子上的客户端前共享文件。这样的环境现在还存在与某些地方，但是却不是分布式存储的主要应用场景。真正的应用场景是一些大型的数据中心、大型网站、大数据运算，在这些场景中，文件系统的接口相比数据库接口来说，就不是那么有用了。比如，在大型网站的环境中，人们非常喜欢事务，但是人们在非常小的数据下才需要事务，这些小的数据也就是你会存储在数据库中的数据，而不是你会存储在文件系统中的数据。所以这里的一些技术，你可以在一些现代的系统中看到类似的设计，但是通常出现在数据库中。
另一个大的场景是为大数据运算存储大的文件，例如MapReduce。实际上GFS某种程度上看起来就像是一个文件系统，但是实际上是为了MapReduce设计的存储系统。但是不论对于GFS也好，还是大数据运算也好，Frangipani关注在客户端的本地缓存和缓存一致性，反而不是很有用。如果你读取10TB的数据，缓存基本上没什么用，并且会适得其反。所以，随着时间的推移，Frangipani在一些场合还是有用的，但是并不符合在设计新系统时候的需求。
腾讯云开发者
