本文重点 缓存一致性、分布式事务、分布式故障恢复 设计和功能之间的关联。
缓存一致性是指，如果我缓存了一些数据，之后你修改了实际数据但是并没有考虑我缓存中的数据，必须有一些额外的工作的存在，这样我的缓存才能与实际数据保持一致。
Frangipani就是一个网络文件系统（NFS，Network File System）。它的目标是与已有的应用程序一起工作，比如说一个运行在工作站上的普通UNIX程序。它与Athena的AFS非常类似（没听过）。从一个全局视图来看，它包含了大量的用户（U1，U2，U3）。
每个用户坐在一个工作站前面，在论文那个年代，笔记本还不流行，大家使用的主要是工作站，不过工作站也就是一个带有键盘鼠标显示器和操作系统的计算机。三个用户对应的工作站（Workstation）分别是WS1，WS2，WS3。
每一个工作站运行了一个Frangipani服务。论文中大部分功能都是在Frangipani软件中实现。所以，用户坐在一个工作站前面，他可能在运行一些普通的应用程序，比如说一个普通的文本编辑（VI）或者说一个编译程序（CC）。当这些普通的应用程序执行文件系统调用时，在系统内核中，有一个Frangipani模块，它实现了文件系统。
文件系统的数据结构，例如文件内容、inode、目录、目录的文件列表、inode和块的空闲状态，所有这些数据都存在一个叫做Petal的共享虚拟磁盘服务中。Petal运行在一些不同的服务器上，有可能是机房里面的一些服务器，但是不会是人们桌子上的工作站。Petal会复制数据，所以你可以认为Petal服务器成对的出现，这样就算一个故障了，我们还是能取回我们的数据。当Frangipani需要读写文件时，它会向正确的Petal服务器发送RPC，并说，我需要这个块，请读取这个块，并将数据返回给我。在大部分时候，Petal表现的就像是一个磁盘，你可以把它看做是共享的磁盘，所有的Frangipani都会与之交互。
Frangipani的期望 共享的基础设施、网络文件系统在相互协作的研究员之间共享文件，Frangipani的设计并没有讨论安全默认为都值得信任。
支持Write-Back，这意味着，如果我想要修改某个数据，比如说我修改了一个文件，或者创建了一个文件，或者删除了一个文件，只要没有其他的工作站需要看到我的改动，Frangipani通过Write-Back缓存方式管理这些数据。这意味着，最开始的时候，我的修改只会在本地的缓存中。如果我创建了一个文件，至少在最开始，有关新创建文件的信息，比如说新创建的inode和初始化的内容，home目录文件列表的更新，文件名等等，所有的这些修改最初只会在本地缓存中存在，因此类似于创建文件的操作可以非常快的完成，因为只需要修改本地的内存中对于磁盘的缓存。而这些修改要过一会才会写回到Petal。所以最开始，我们可以为文件系统做各种各样的修改，至少对于我自己的目录，我自己的文件，这些修改完全是本地的。这对于性能来说有巨大的帮助，因为写本地内存的性能比通过RPC向一个远端服务器写要快1000倍。
在这样的架构下，一个非常重要的后果是，文件系统的逻辑需要存在于每个工作站上。为了让所有的工作站能够只通过操作内存就完成类似创建文件的事情，这意味着所有对于文件系统的逻辑和设计必须存在于工作站内部。在Frangipani的设计中，Petal作为共享存储系统存在，它不知道文件系统，文件，目录，它只是一个很直观简单的存储系统，所有的复杂的逻辑都在工作站中的Frangipani模块中。所以这是一个非常去中心化的设计。
当然，在某个时间点，瓶颈会在Petal。因为这是一个中心化的存储系统，这时，你需要增加更多的存储服务器。
所以，我们现在有了一个系统，它在工作站里面做了大量的缓存，并且文件的修改可以在本地缓存完成。这几乎立刻引出了有关设计的几个非常严重的挑战。
Frangipani的挑战主要来自于两方面，一个是缓存，另一个是这种去中心化的架构带来的大量的逻辑存在于客户端之中进而引起的问题。
一个场景是，如果我在一个工作站修改了文件，之后在另一个计算机上编译它，我期望编译器能看到我刚刚做的修改。这意味着，文件系统必须要做一些事情来确保客户端可以读到最新的写入文件。我们之前讨论过这个话题，我们称之为强一致或者线性一致，在这里我们也想要这种特性。但是在一个缓存的环境中，现在说的一致性的问题不是指存储服务器的一致性，而是指工作站上的一些修改需要被其他工作站看到。因为历史的原因，这通常被称为缓存一致性（Cache Coherence）。
另一个问题是，因为所有的文件和目录都是共享的，非常容易会有两个工作站在同一个时间修改同一个目录。假设用户U1在他的工作站W1上想要创建文件/A，这是一个在 / 目录下的新文件，同时，用户U2在他的工作站W2上想要创建文件 /B 。
这里他们在同一个目录下创建了不同名字的两个文件A和B，但是他们都需要修改根目录，为根目录增加一个新的文件名。所以这里的问题是，当他们同时操作时，系统能识别这些修改了相同目录的操作，并得到一些有意义的结果吗？这里的有意义的结果是指，A和B最后都要创建成功，我们不想只创建一个文件，因为第二个文件的创建有可能会覆盖并取代第一个文件。这里期望的行为有很多种叫法，但是这里我们称之为原子性（Atomicity）。
最后一个问题是，假设我的工作站修改了大量的内容，由于Write-Back缓存，可能会在本地的缓存中堆积了大量的修改。如果我的工作站崩溃了，但是这时这些修改只有部分同步到了Petal，还有部分仍然只存在于本地。同时，其他的工作站还在使用文件系统。那么，我的工作站在执行操作的过程中的崩溃，最好不要损坏其他人同样会使用的文件系统。这意味着，我们需要的是单个服务器的故障恢复，我希望我的工作站的崩溃不会影响其他使用同一个共享系统的工作站。
缓存一致性协议所带来的优点，对于线性一致性来说，当我查看文件系统中任何内容时，我总是能看到最新的数据。对于缓存来说，我们想要缓存带来的性能提升。某种程度上，我们想要同时拥有这两种特性的优点。
Frangipani的缓存一致性核心是由锁保证的，我们之后在原子性和故障恢复中将会再次看到锁。
尽管你可以通过分片将锁分布到多个服务器上，但是我接下来会假设只有一个锁服务器。逻辑上，锁服务器是独立的服务器，但是实际上我认为它与Petal服务器运行在一起。在锁服务器里面，有一个表单，就叫做locks。我们假设每一个锁以文件名来命名，所以对于每一个文件，我们都有一个锁，而这个锁，可能会被某个工作站所持有。
Frangipani中的锁更加复杂可以支持两种模式：要么允许一个写入者持有锁，要么允许多个读取者持有锁。
假设文件X最近被工作站WS1使用了，所以WS1对于文件X持有锁。同时文件Y最近被工作站WS2使用，所以WS2对于文件Y持有锁。锁服务器会记住每个文件的锁被谁所持有。当然一个文件的锁也有可能不被任何人持有。
在每个工作站，会记录跟踪它所持有的锁，和锁对应的文件内容。所以在每个工作站中，Frangipani模块也会有一个lock表单，表单会记录文件名、对应的锁的状态和文件的缓存内容。这里的文件内容可能是大量的数据块，也可能是目录的列表。
当一个Frangipani服务器决定要读取文件，比如读取目录 /、读取文件A、查看一个inode，首先，它会向一个锁服务器请求文件对应的锁，之后才会向Petal服务器请求文件或者目录的数据。收到数据之后，工作站会记住，本地有一个文件X的拷贝，对应的锁的状态，和相应的文件内容。 在工作站完成了一些操作之后，比如创建文件，或者读取文件，它会随着相应的系统调用（例如rename，write，create，read）释放锁。只要系统调用结束了，工作站会在内部释放锁，现在工作站不再使用那个文件。但是从锁服务器的角度来看，工作站仍然持有锁。工作站内部会标明，这是锁时Idle状态，它不再使用这个锁。所以这个锁仍然被这个工作站持有，但是工作站并不再使用它。这在稍后的介绍中比较重要。 现在这里的配置是一致的，锁服务器知道文件X和Y的锁存在，并且都被WS1所持有。工作站WS1也有同等的信息，它内部的表单知道它持有了这两个锁，并且它记住了这两个锁对应的文件或者目录。 这里Frangipani应用了很多的规则，这些规则使得Frangipani以一种提供缓存一致性的方式来使用锁，并确保没有工作站会使用缓存中的旧数据。这些规则、锁、缓存数据需要配合使用。这里的规则包括了： ①工作站不允许持有缓存的数据，除非同时也持有了与数据相关的锁。所以基本上来说，不允许在没有锁保护的前提下缓存数据。从操作意义上来说，这意味着对于一个工作站来说，在它使用一个数据之前，它首先要从锁服务器获取数据的锁。只有当工作站持有锁了，工作站才会从Petal读取数据，并将数据放在缓存中。所以这里的顺序是，获得锁，之后再从Petal读取数据。所以，直到获取了锁，工作站是不能缓存数据的，要想缓存数据，工作站必须先持有锁，之后，才能从Petal读取数据。 ②如果你在释放锁之前，修改了锁保护的数据，那你必须将修改了的数据写回到Petal，只有在Petal确认收到了数据，你才可以释放锁，也就是将锁归还给锁服务器。所以这里的顺序是，先向Petal存储系统写数据，之后再释放锁。 ③最后再从工作站的lock表单中删除关文件的锁的记录和缓存的数据。 工作站和锁服务器之间的缓存一致协议协议包含了4种不同的消息。本质上你可以认为它们就是一些单向的网络消息。 Request消息会说：hey锁服务器，我想获取这个锁。 如果从锁服务器的lock表单中发现锁已经被其他人持有了，那锁服务器不能立即交出锁。但是一旦锁被释放了，锁服务器会回复一个Grant消息给工作站。这里的Request和Grant是异步的。 如果锁服务器收到了一个加锁的请求，它查看自己的lock表单可以发现，这个锁现在正被工作站WS1所持有，锁服务器会发送一个Revoke消息给当前持有锁的工作站WS1。并说，现在别人要使用这个文件，请释放锁吧。当一个工作站收到了一个Revoke请求，如果锁时在Idle状态，并且缓存的数据脏了，工作站会首先将修改过的缓存写回到Petal存储服务器中，因为前面的规则要求在释放锁之前，要先将数据写入Petal。所以如果锁的状态是Idle，首先需要将修改了的缓存数据发回给Petal，只有在那个时候，工作站才会再向锁服务器发送一条消息说，好吧，我现在放弃这个锁。所以，对于一个Revoke请求的响应是，工作站会向锁服务器发送一条Release消息。 如果工作站收到Revoke消息时，它还在使用锁，比如说正在删除或者重命名文件的过程中，直到工作站使用完了锁为止，或者说直到它完成了相应的文件系统操作，它都不会放弃锁。完成了操作之后，工作站中的锁的状态才会从Busy变成Idle，之后工作站才能注意到Revoke请求，在向Petal写完数据之后最终释放锁。 每个工作站用完了锁之后，不是立即向锁服务器释放锁，而是将锁的状态标记为Idle就是一种优化。 另一个主要的优化是，Frangipani有共享的读锁（Shared Read Lock）和排他的写锁（Exclusive Write Lock）。如果有大量的工作站需要读取文件，但是没有人会修改这个文件，它们都可以同时持有对这个文件的读锁。如果某个工作站需要修改这个已经被大量工作站缓存的文件时，那么它首先需要Revoke所有工作站的读锁，这样所有的工作站都会放弃自己对于该文件的缓存，只有在那时，这个工作站才可以修改文件。因为没有人持有了这个文件的缓存，所以就算文件被修改了，也没有人会读到旧的数据。 学生提问：如果没有其他工作站读取文件，那缓存中的数据就永远不写入后端存储了吗？ Robert教授：这是一个好问题。实际上，在我刚刚描述的机制中是有风险的，如果我在我的工作站修改了一个文件，但是没有人读取它，这时，这个文件修改后的版本的唯一拷贝只存在于我的工作站的缓存或者RAM上。这些文件里面可能有一些非常珍贵的信息，如果我的工作站崩溃了，并且我们不做任何特殊的操作，数据的唯一拷贝会丢失。所以为了阻止这种情况，不管怎么样，工作站每隔30秒会将所有修改了的缓存写回到Petal中。所以，如果我的工作站突然崩溃了，我或许会丢失过去30秒的数据，但是不会丢更多，这实际上是模仿Linux或者Unix文件系统的普通工作模式。在一个分布式文件系统中，很多操作都是在模仿Unix风格的文件系统，这样使用者才不会觉得Frangipani的行为异常，因为它基本上与用户在使用的文件系统一样。
原子性
当我做了一个复杂的操作，比如说创建一个文件，这里涉及到标识一个新的inode、初始化一个inode（inode是用来描述文件的一小份数据）、为文件分配空间、在目录中为新文件增加一个新的名字，这里有很多步骤，很多数据都需要更新。我们不想任何人看到任何中间的状态，我们希望其他的工作站要么发现文件不存在，要么文件完全存在，但是我们绝不希望它看到中间状态。所以我们希望多个步骤的操作具备原子性。 为了实现原子性，为了让多步骤的操作，例如创建文件，重命名文件，删除文件具备原子性，Frangipani在内部实现了一个数据库风格的事务系统，并且是以锁为核心。并且，这是一个分布式事务系统，我们之后会在这门课看到更多有关分布式事务系统的内容，它在分布式系统中是一种非常常见的需求。 因为我们有了锁服务器和缓存一致性协议，我们只需要确保我们在整个操作的过程中持有所有的锁，我们就可以无成本的获得这里的不可分割原子事务。 所以为了让操作具备原子性，Frangipani持有了所有的锁。对于锁来说，这里有一件有意思的事情，Frangipani使用锁实现了两个几乎相反的目标。对于缓存一致性，Frangipani使用锁来确保写操作的结果对于任何读操作都是立即可见的，所以对于缓存一致性，这里使用锁来确保写操作可以被看见。但是对于原子性来说，锁确保了人们在操作完成之前看不到任何写操作，因为在所有的写操作完成之前，工作站持有所有的锁。故障恢复 我们需要能正确应对这种场景：一个工作站持有锁，并且在一个复杂操作的过程中崩溃了。比如说一个工作站在创建文件，或者删除文件时，它首先获取了大量了锁，然后会更新大量的数据，在其向Petal回写数据的过程中，一部分数据写入到了Petal，还有一部分还没写入，这时工作站崩溃了，并且锁也没有释放（因为数据回写还没有完成）。这是故障恢复需要考虑的有趣的场景。 我们绝对需要释放锁，这样其他的工作站才能使用这个系统，使用相同的文件和目录。但同时，我们也需要处理这种场景：崩溃了的工作站只写入了与操作相关的部分数据，而不是全部的数据。 当一个工作站需要完成涉及到多个数据的复杂操作时，在工作站向Petal写入任何数据之前，工作站会在Petal中自己的Log列表中追加一个Log条目，这个Log条目会描述整个的需要完成的操作。只有当这个描述了完整操作的Log条目安全的存在于Petal之后，工作站才会开始向Petal发送数据。所以如果工作站可以向Petal写入哪怕是一个数据，那么描述了整个操作、整个更新的Log条目必然已经存在于Petal中。 每个工作站的独立的Log，存放在公共的共享存储中。 我们需要大概知道Log条目的内容是什么，但是Frangipani的论文对于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消息，要自己释放某个锁，它需要执行好几个步骤。 1.首先，工作站需要将内存中还没有写入到Petal的Log条目写入到Petal中。 2.之后，再将被Revoke的Lock所保护的数据写入到Petal。 3.最后，向锁服务器发送Release消息。 这里采用这种流程的原因是，在第二步我们向Petal写入数据的时候，如果我们在中途故障退出了，我们需要确认其他组件有足够的信息能完成我们未完成修改。先写入Log将会使我们能够达成这个目标。这些Log记录是对将要做的修改的完整记录。所以我们需要先将完整的Log写入到Petal。之后工作站可以开始向Petal写入其修改了的块数据，这个过程中，可能会故障，也可能不会。如果工作站完成了向Petal写入块数据，它就能向锁服务发送Release消息。所以，如果我的工作站修改了一些文件，之后其他的工作站想要读取这些文件，上面的才是一个实际的工作流程。锁服务器要我释放锁，我的工作站会先向Petal写入Log，之后再向Petal写入脏的块数据，最后才向锁服务器发送Release消息。之后，其他的工作站才能获取锁，并读取相应的数据块。这是没有故障的时候对应的流程。 这里采用这种流程的原因是，在第二步我们向Petal写入数据的时候，如果我们在中途故障退出了，我们需要确认其他组件有足够的信息能完成我们未完成修改。先写入Log将会使我们能够达成这个目标。这些Log记录是对将要做的修改的完整记录。所以我们需要先将完整的Log写入到Petal。之后工作站可以开始向Petal写入其修改了的块数据，这个过程中，可能会故障，也可能不会。如果工作站完成了向Petal写入块数据，它就能向锁服务发送Release消息。所以，如果我的工作站修改了一些文件，之后其他的工作站想要读取这些文件，上面的才是一个实际的工作流程。锁服务器要我释放锁，我的工作站会先向Petal写入Log，之后再向Petal写入脏的块数据，最后才向锁服务器发送Release消息。之后，其他的工作站才能获取锁，并读取相应的数据块。这是没有故障的时候对应的流程。
这里的场景是，当工作站需要重命名文件或者创建一个文件时，首先它会获得所有需要修改数据的锁，之后修改自身的缓存来体现改动。但是后来工作站在向Petal写入数据的过程中故障了。工作站可能在很多个位置发生故障，但是由于前面介绍过的工作流程，Frangipani总是会先将自身的Log先写入到Petal。这意味着如果发生了故障，那么发生故障时可能会有这几种场景： 要么工作站正在向Petal写入Log，所以这个时候工作站必然还没有向Petal写入任何文件或者目录。 要么工作站正在向Petal写入修改的文件，所以这个时候工作站必然已经写入了完整的Log。 因为有了前面的工作流程，我们需要担心的故障发生时间点是有限的。 当持有锁的工作站崩溃了之后，发生的第一件事情是锁服务器向工作站发送一个Revoke消息，但是锁服务器得不到任何响应，之后才会触发故障恢复。如果没有人需要用到崩溃工作站持有的锁，那么基本上没有人会注意到工作站崩溃了。假设一个其他的工作站需要崩溃了的工作站所持有的一个锁，锁服务器会发出Revoke消息，但是锁服务器永远也不会从崩溃了的工作站收到Release消息。Frangipani出于一些原因对锁使用了租约，当租约到期了，锁服务器会认定工作站已经崩溃了，之后它会初始化恢复过程。实际上，锁服务器会通知另一个还活着的工作站说：看，工作站1看起来崩溃了，请读取它的Log，重新执行它最近的操作并确保这些操作完成了，在你完成之后通知我。在收到这里的通知之后，锁服务器才会释放锁。这就是为什么日志存放在Petal是至关重要的，因为一个其他的工作站可能会要读取这个工作站在Petal中的日志。 发生故障的场景究竟有哪些呢？ 第一种场景是，工作站WS1在向Petal写入任何信息之前就故障了。这意味着，当其他工作站WS2执行恢复，查看崩溃了的工作站的Log时，发现里面没有任何信息，自然也就不会做任何操作。之后WS2会释放WS1所持有的锁。工作站WS1或许在自己的缓存中修改了各种各样的数据，但是如果它没有在自己的Log存储区写入任何信息，那么它也不可能在Petal中写入任何它修改的块数据。我们会丢失WS1的最后几个操作，但是文件系统会与WS1开始修改之前保持一致。因为很明显，工作站WS1没能走到向Petal写Log那一步，自然也不可能向Petal写入块数据。 第二种场景是，工作站WS1向Petal写了部分Log条目。这样的话，执行恢复的工作站WS2会从Log的最开始向后扫描，直到Log的序列号不再增加，因为这必然是Log结束的位置。工作站WS2会检查Log条目的更新内容，并向Petal执行Log条目中的更新内容。比如Petal中的特定块需要写入特定的数据，这里对应的其实就是工作站WS1在自己本地缓存中做的一些修改。所以执行恢复的工作站WS2会检查每个Log条目，并重新向Petal执行WS1的每一条Log。当WS2执行完WS1存放在Petal中的Log，它会通知锁服务器，之后锁服务器会释放WS1持有的锁。这样的过程会使得Petal更新至故障工作站WS1在故障前的执行的部分操作。或许不能全部恢复WS1的操作，因为故障工作站可能只向Petal写了部分Log就崩溃了。同时，除非在Petal中找到了完整的Log条目，否则执行恢复的工作站WS2是不会执行这条Log条目的，所以，这里的隐含意思是需要有类似校验和的机制，这样执行恢复的工作站就可以知道，这个Log条目是完整的，而不是只有操作的一部分数据。这一点很重要，因为在恢复时，必须要在Petal的Log存储区中找到完整的操作。所以，对于一个操作的所有步骤都需要打包在一个Log条目的数组里面，这样执行恢复的工作站就可以，要么全执行操作的所有步骤，要么不执行任何有关操作的步骤，但是永远不会只执行部分步骤。这就是当在向Petal写入Log时，发生了故障的修复过程。 另一个有趣的可能是，工作站WS1在写入Log之后，并且在写入块数据的过程中崩溃了。先不考虑一些极其重要的细节，执行恢复的工作站WS2并不知道WS1在哪个位置崩溃的，它只能看到一些Log条目，同样的，WS2会以相同的方式重新执行Log。尽管部分修改已经写入了Petal，WS2会重新执行修改。对于部分已经写入的数据，相当于在相同的位置写入相同的数据。对于部分未写入的数据，相当于更新了Petal中的这部分数据，并完成了操作。 上面的描述并没有涵盖所有的场景，下面的这个场景会更加复杂一些。如果一个工作站，完成了上面流程的步骤1，2，在释放锁的过程中崩溃了，进而导致崩溃的工作站不是最后修改特定数据的工作站。具体可以看下面这个例子，假设我们有一个工作站WS1，它执行了删除文件（d/f）的操作。 之后，有另一个工作站WS2，在删除文件之后，以相同的名字创建了文件，当然这是一个不同的文件。所以之后，工作站WS2创建了同名的文件（d/f）。在创建完成之后，工作站WS1崩溃了，所以，我们需要基于WS1的Log执行恢复，这时，可能有第三个工作站WS3来执行恢复的过程。这里的时序表明，WS1删除了一个文件，WS2创建了一个文件，WS3做了恢复操作。有可能删除操作仍然在WS1的Log中，当WS1崩溃后，WS3需要读取WS1的Log，并重新执行WS1的Log中的更新。因为删除文件的Log条目仍然存在于WS1的Log中，如果不做任何额外的事情，WS3会删除这个文件（d/f）。但是实际上，WS3删除的会是WS2稍后创建的一个完全不同的文件。 这样的结果是完全错误的，因为需要被删除的是WS1指定的文件，而不是WS2创建的一个相同名字的文件。因为WS2的创建是在WS1的删除之后，所以我们不能只是不经思考的重新执行WS1的Log，WS1的Log在我们执行的时候可能已经过时了，其他的一些工作站可能已经以其他的方式修改了相同的数据，所以我们不能盲目的重新执行Log条目。 Frangipani是这样解决这个问题的，通过对每一份存储在Petal文件系统数据增加一个版本号，同时将版本号与Log中描述的更新关联起来。在Petal中，每一个元数据，每一个inode，每一个目录下的内容，都有一个版本号，当工作站需要修改Petal中的元数据时，它会向从Petal中读取元数据，并查看当前的版本号，之后在创建Log条目来描述更新时，它会在Log条目中对应的版本号填入元数据已有的版本号加1。 之后，如果工作站执行到了写数据到Petal的步骤，它也会将新的增加了的版本号写回到Petal。
所以，如果一个工作站没有故障，并且成功的将数据写回到了Petal。这样元数据的版本号会大于等于Log条目中的版本号。如果有其他的工作站之后修改了同一份元数据，版本号会更高。
所以，实际上WS3看到的WS1的删除操作对应的Log条目，会有一个特定的版本号，它表明，由这个Log条目影响的元数据对应版本号3（举例）。
WS2的修改在WS1崩溃之前，所以WS1必然已经释放了相关数据的锁。WS2获得了锁，它会读取当前的元数据可以发现当前的版本号是3，当WS2写入数据的时候，它会将版本号设置为4。
之后，当WS3执行恢复流程时，WS3会重新执行WS1的Log，它会首先检查版本号，通过查看Log条目中的版本号，并查看Petal中存储的版本号，如果Petal中存储的版本号大于等于Log条目中的版本号，那么WS3会忽略Log条目中的修改，因为很明显Petal中的数据已经被故障了的工作站所更新，甚至可能被后续的其他工作站修改了。所以在恢复的过程中，WS3会选择性的根据版本号执行Log，只有Log中的版本号高于Petal中存储的数据的版本时，Log才会被执行。 这里有个比较烦人的问题就是，WS3在执行恢复，但是其他的工作站还在频繁的读取文件系统，持有了一些锁并且在向Petal写数据。WS3在执行恢复的过程中，WS2是完全不知道的。WS2可能还持有目录 d的锁，而WS3在扫描故障工作站WS1的Log时，需要读写目录d，但是目录d的锁还被WS2所持有。我们该如何解决这里的问题？ 一种不可行的方法是，让执行恢复的WS3先获取所有关联数据的锁，再重新执行Log。这种方法不可行的一个原因是，有可能故障恢复是在一个大范围电力故障之后，这样的话谁持有了什么锁的信息都丢失了，因此我们也就没有办法使用之前的缓存一致性协议，因为哪些数据加锁了，哪些数据没有加锁在断电的过程中丢失了。 但是幸运的是，执行恢复的工作站可以直接从Petal读取数据而不用关心锁。这里的原因是，执行恢复的工作站想要重新执行Log条目，并且有可能修改与目录d关联的数据，它就是需要读取Petal中目前存放的目录数据。接下来只有两种可能，要么故障了的工作站WS1释放了锁，要么没有。如果没有的话，那么没有其他人不可以拥有目录的锁，执行恢复的工作站可以放心的读取目录数据，没有问题。如果释放了锁，那么在它释放锁之前，它必然将有关目录的数据写回到了Petal。这意味着，Petal中存储的版本号，至少会和故障工作站的Log条目中的版本号一样大，因此，之后恢复软件对比Log条目的版本号和Petal中存储的版本号，它就可以发现Log条目中的版本号并没有大于存储数据的版本号，那么这条Log条目就会被忽略。所以这种情况下，执行恢复的工作站可以不持有锁直接读取块数据，但是它最终不会更新数据。因为如果锁被释放了，那么Petal中存储的数据版本号会足够高，表明在工作站故障之前，Log条目已经应用到了Petal。所以这里不需要关心锁的问题。 标签：文件,6.824,Log,Frangipani,WS1,工作站,Petal,数据 From： https://www.cnblogs.com/thotf/p/16812561.html