“Hi，这是小5自学算力大集群相关知识的第7篇笔记。这次我们将从一篇“上古时期”的论文开始说起，来了解缓存机制可以在分布式文件系统中起到什么样的作用，以及在使用本地缓存机制的情况下如何保持数据一致性的一些启发。”
摘要
Frangipani是1997年由数字设备公司（DEC）研发的分布式文件系统，主要用于为实验室或小型团队提供高性能、统一的文件共享服务，支持多节点协同操作并确保数据一致性。
之所以学习这个“上古”的技术，是因为其中包含了大量关于缓存一致性、分布式事务以及分布式崩溃恢复的有趣且优秀的设计，以及它们之间的交互。
- Frangipani 基本概念
设计初衷：需要一个网络文件系统，具备高效的缓存机制，并且在缓存中执行修改操作，以便存储各自的用户目录，同时还能存储共享的项目文件，并且在任何工作站都能访问到自己主目录下的所有文件、目录、环境。
1.主要满足的使用场景
用户处于一个共享网络的环境，并在大多数情况下主要还是通过工作站读取和编辑自己的文件。即，当用户登录系统并使用自己的文件一段时间后，这些文件可以在本地进行缓存，当需要获取这些文件时，系统的响应时间可以从毫秒级缩短至微秒级，而不必每次都从文件服务器中检索。
*该分布式方案本质上并未涉及安全性机制和大规模分布式支持，无法满足公开环境需求。仅适用于小规模、高信任环境（如实验室、企业内部）。
2.关于缓存
不仅在每个工作站、每个Frangipani服务器中会进行缓存，并且还采用了回写式缓存技术。如果用户想要修改某些内容，比如修改文件、在目录中创建或删除文件，或者进行其他任何操作，只要没有其他工作站需要查看这些变更，Frangipani系统就会通过回写缓存来处理。这意味着用户的写入操作仅保持在本地缓存中，通常情况下，这些数据不会立即写回到Petal，而是稍后才进行。
3.关于 Petal
所有数据存储在一个共享的虚拟磁盘上，其称为 Petal。它运行在一组独立的机器上，负责数据复制。在大多数情况下，Petal的行为类似于磁盘驱动器，其类似于所有这些 Frangipanis 节点所共同访问的共享磁盘驱动器。当 Frangipani 服务需要进行读写操作，比如读取目录之类的，它会向正确的 Petal 服务器发送远程过程调用。
实际上 Petal 共享存储系统对文件系统、文件或目录的所有逻辑并不关心。所有的复杂性都存在于每个客户端的 Frangipani 系统中，所以这是一种去中心化的方案。
这么做带来的好处：由于大部分复杂性和消耗的CPU时间都集中在每个客户端。随着增加更多工作站，系统获得了更多的CPU能力来运行那些新用户的文件系统操作。即，虽然每台新加入的工作站都为新用户带来了一丝额外的负载，但同时也提供了更多可用的CPU时间来执行该用户的文件系统操作。这也意味着系统具有一定程度的自然可扩展性。
4. Frangipani 系统基本结构在Frangipani系统中，存在第三种类型的服务器。来自用户的工作站、用于共享存储的 Petal 服务器、锁服务器。其中，锁服务器内基本上只是一个包含命名锁的表格。它会记住对于每个文件，谁持有锁。而在每个工作站中，则会记录其自身所持有的锁，同时跟踪缓存数据，即记录工作站锁定的是哪个文件，锁的类型，以及该文件缓存内容的具体信息。
以上即是 Frangipani 系统梗概与基本概念。接下来我们将着重了解缓存一致性、原子性与崩溃恢复。
- 缓存一致性
如果用户A工作站缓存了某些数据，此时，另一个用户的工作站B对这些数据进行了修改。这里的修改应该能使用户A也看见，而不是用户A还只能看见自己之前所缓存的旧内容。所以这就引出了一个问题，如何解决的时效性与一致性？比如两台不同的工作站同时在修改同一个目录。
Frangipani 的解决方式是由通过对“锁”机制的使用来保证缓存一致性。具体：对于每个文件，都有一个潜在的锁，而每个锁，可能归属于某个所有者。当某个工作站需要需要修改某个文件时，首先会向锁服务器请求对即将使用的资源的锁定，然后请求 Petal 获取该文件、目录或所需读取内容的数据。当工作站正在读取或写入当前的文件或目录，如正处于文件创建、删除、重命名或其他操作的过程中时，锁由工作站持有，并且处于忙碌状态。在工作站完成上述操作之后，就会立即释放锁。从锁服务器的角度来看工作站仍将特有该锁，只是，工作站会标记该锁的状态为idle。
以上的操作流程需要遵循几个规则：
1.任何工作站只有它同时持有与该数据相关联的锁时才可以缓存数据，否则不允许缓存数据。即想要持有任何缓存数据，除非它同时持有与该数据相关联的锁。
工作站在使用数据之前，它首先从锁服务器获取对数据的锁定。在工作站获取锁之后，工作站才会从 Petal 读取数据并将其存入其缓存中。
2.在释放锁之前，如果本地工作站修改了其本地缓存中对应被锁定的数据。工作站必须在释放锁之前将数据写回，即，将修改后的数据写回到 Petal。只有在Petal确认后，才被允许释放锁，也就是把锁归还给锁服务器，并从该工作站的锁表中删除该条目及缓存数据。
3.工作站将在完成该文件系统操作之前都不会释放所持有的锁，无论当时使用该文件的是何种系统调用。如，工作站在持有busy状态的锁的过程中（比如正在执行删除、重命名或其他影响锁定文件的操作），收到撤销指令，在完成该文件系统操作之前不会释放对应的锁。
4. Frangipani 系统具备“共享的读锁”与“独占的写锁”的概念，即锁的属性有共享与独占的区分。
如果有大量的工作站需要读取同一个文件，但没有人对其进行写入操作，它们都可以获得一个锁，即读锁。如果有人试图修改一个已被广泛缓存的文件，他们首先需要撤销所有人的读锁，以便每个人都放弃其缓存副本，只有在这之后，写入者才被允许修改文件。
5.所有工作站都会每30秒将其缓存中的任何内容，当然也包括修改的数据回写到 Petal 中。这是为了防止当只有一个工作站对某个文件进行了创建或修改而没有其他工作站进行过读取或修改请求时，该工作站发生崩溃而导致创建/修改丢失（因为此时可能没有其他工作站对该文件的最新状态进行过缓存）。
- Frangipani 系统协作流程与消息类型
Frangipani 系统通过网络消息的形式与系统内部不同服务器进行交互，它们本质上视为一种单向网络消息。即一致性协议。
锁服务器与工作站之间的协议，包含四种不同类型的消息：
1.工作站向锁服务器的请求消息；
2.锁服务器向工作站发送同意授权消息（该锁没有被其他工作站占用的情况下）；
3.撤销消息。工作站向锁服务器请求一个锁，而此时有其他工作站正持有该锁，锁服务器将向当前拥有该锁的工作站发送一条撤销消息。当工作站收到撤销请求时，若锁处于空闲状态，且缓存数据为脏数据，则工作站将首先将脏数据，即此缓存中修改后的数据，写回 Petal，然后释放锁；
4.释放消息。当数据写回 Petal 后，向锁服务器发送释放消息。
- 原子性
我们希望诸如创建文件、删除文件等操作，能够表现得如同即时完成，即在时间上瞬时发生，从而不会干扰到其他工作站在相近时间内发生的操作，这即是所谓的“原子性”。
Frangipani 通过以下的方式实现原子性：
系统会首先确保其他工作站无法看到某个用户当前的修改，直到其释放其所持有的锁。即，当修改发生时，该工作站会先尝试获取操作期间所涉及到的所有数据上的所有锁，并在完成整个操作之前不释放任何这些锁，即直到对 Petal 进行回写，并在完成后才释放这些锁。
只需确保在整个操作期间持有所有锁，就能获得这种原子性。
- 从服务器的崩溃中恢复
我们的目的是希望即使我的工作站崩溃，也不会干扰到使用同一共享系统的其他人的活动。
我们假设一个场景：假设某个工作站已获取大量锁，它正在大量写入数据，可能涉及创建或删除文件等操作可能已经将其中一些修改写回了Petal，但并未全部完成，随后在释放锁之前发生了崩溃。
此时不能简单地释放其持有的所有锁是正确的，因为这样可以防止任何读取请求的其他工作站看到这种部分更新，这将破坏原子性，也会导致数据一致性被破坏。但如果一直不释放锁，那任何需要使用这些文件的人都将不得不永远等待。
为了解决这个困境， Frangipani 使用预写式日志（write-ahead logging）的方式进行崩溃处理。概述如下：工作站会首先在向 Petal 进行任何写入之前，在其 Petal 日志中追加一条日志条目，描述即将执行的全套操作。只有当描述完整操作集的日志条目安全地存储在 Petal 中，且此时任何其他人都能查看时，工作站才会开始将操作权限发送至 Petal。
这里涉及到一些前置规则：
1. Frangipani 拥有每个工作站的日志，它为每个工作站配备了一个日志，且这些日志是相互独立的；
2.工作站的日志存储在 Petal 中，而非本地磁盘上。以便当某个工作站崩溃时，其他工作站能够获取其日志；
3.每个日志条目都有一个日志序列号，它是一个递增的数字；每个日志都有对应存储在 Petal 上的块信息；每个日志都有一个版本号；每个日志都包含了待写入的信息（但不包含写入文件内容的数据）；
4. Frangipani 检测工作站日志结束的方式：当工作站崩溃时，它通过在 Petal 中向前扫描日志，直至观察到递增序列停止增长，此时具有最高日志 序列号的日志条目必定是最后一条。
当崩溃发生时，要么是在工作站将日志写回至 Petal之前，但尚未将任何修改过的文件或目录块写回；要么是在它正在将这些修改过的块写回时崩溃，因此肯定是在其完整的日志已经写入之后。
崩溃开始，首先发生的是，锁服务器向该工作站发送了撤销请求，但锁服务器没有收到任何响应。此时如果从未有人请求过这个锁，那么基本上，没人会注意到工作站已经崩溃。
在租约时间到期后，锁服务器将判定工作站必然已崩溃，并随即启动恢复流程。锁服务器将通知其他在线的工作站检查崩溃工作站的日志，并重新执行所有近期操作以确保其完整性，完成后告知锁服务器，只有在那时锁服务器才会释放锁。
接下来将会根据实际情况的不同而出现不同的分支场景：
1.工作站在将任何内容写回之前就崩溃了，这意味着进行恢复的另一工作站将查看崩溃工作站的日志。1）若发现其中什么都没有，于是不做任何处理，并释放该工作站所特有的锁；2）工作站可能在它的缓存中修改了某些内容，但如果它没有向其日志区域写入任何信息，那么它就不可能在这些操作过程中写入任何被修改的块。这种情况下，尽管我们会丢失工作站执行的最后几个操作，但文件系统将与该崩溃工作站开始修改任何内容之前的时间点保持一致。
2.工作站写入了一些日志条目。恢复中的工作站将从日志的起点开始向前扫描，直到它停止观察到日志序列号的递增。恢复的工作站将查看这些变更描述中的每—个，并将该变更重写到 Petal 中。当它一路执行到崩溃工作站的日志末端，即其在 Petal 中的状态时，系统会通知锁服务器，而锁服务器则会释放该崩溃工作站的锁。
3.工作站在写入目志之后，以及在自我回写部分数据块之后，才发生了崩溃。即便修改操作已经在 Petal 中完成，在线的工作站依然会重新执行相同的修改操作。
4.崩溃的工作站实际上在崩溃前可能已经完成了整个流程，并且事实上释放了一些锁。即此时其并不是最后一个修改特定数据的工作站。如，工作站A执行了一个删除文件的操作，在这次删除之后，有另一台工作站创建了一个同地址同名的新文件。之后，工作站A崩溃了，此时其他工作站需要进行恢复操作。
此时不能简单地重新执行工作站A的日志而不加思考，因为在恢复过程中重新执行时，工作站A日志中的某个条目可能已经过时了，这会导致新的数据被覆盖或抹除。
Frangipani 解决这一问题的方法是，为存储在 Petal 文件系统中的每一份数据关联版本号，同时，为日志中描述的每一次更新关联相同的版本号。如果区块中的版本号大于或等于日志条目中的版本号，恢复软件将直接忽略该日志条目中的更新，不执行对应操作。即，日志条目中的写入比已经存储在磁盘上的数据更新时才会进行恢复写入。
这么处理也是考虑到在恢复的过程中，某些文件可能正在被其他工作站编辑或使用中。
*恢复工作站不会重写任何目志条目，除非它在 Petal 中拥有完整的日志条目。即要么完全执行要么完全不执行，但绝不会执行只其中的一部分。
- Frangipani 应用现状与意义
在大数据计算领域，文件系统接口相比数据库并不那么实用，因为在大型网站世界中，人们确实偏爱事务处理。通常是非常小的数据项，这类数据通常更适合存储在数据库中，而不是存储在文件系统中。在某些情况下Frangipani 仍然有其作用，但并不是目前主流的选择。
不过 Frangipani 的很多思想具有借鉴价值，如本地缓存的使用，如随着客户端的不断增多并不会对系统本身的性能造成巨大影响。
以上内容来自对 MIT 《分布式系统 6.824》的学习笔记，在此特别声明。