分布式之Frangipani
0. 前言
《Frangipani: A Scalable Distributed File System》是1997年发表的一篇论文，年代较为久远，但其中关于缓存一致性(cache coherence)、分布式事务(distributed transactions)、分布式故障恢复(distributed crash recovery)的设计思想，依旧值得我们学习。
Frangipani可以看作是一个分布式文件系统，它为上层应用提供文件系统的接口。
1. 基本架构
架构中有3大组成部分：
Frangipani模块：运行在用户服务器中，它对用户程序提供与Unix文件系统一致的接口。
Petal虚拟磁盘：一个高可用的分布式虚拟磁盘，对外提供磁盘接口，会自动对数据进行备份。它是一个独立的系统，同样由Frangipani论文的作者所提出。
Lock服务：一个独立的分布式Lock Server集群，提供分布式锁服务。
Frangipani系统的一些设计：
Write-Back缓存：当用户程序调用Frangipani接口对文件进行读写等操作时，Frangipani会先在本地服务器进行缓存，过段时间再将变更写入Petal，这能保证用户服务器有较高的读写性能。
去中心文件服务：不存在中心化的文件服务管理者(leader)，复杂逻辑由用户服务器中的Frangipani模块实现，Petal只提供存储功能。
面临的挑战：
缓存一致性(cache coherence) ：当Server1对文件
/grades进行写操作时，由于先写缓存，Server2能否读到/grades文件的变更。并发问题：当Server1和Server2同时对一个文件或目录进行修改时，如何保证它们的操作都能原子性地完成，相互之间不会覆盖或干扰。
崩溃恢复(crash recovery) ：当Server1进行了一些写入操作，但缓存未更新到Petal磁盘时，Server1崩溃了，如何不影响其它Server，如何在重启后恢复原有状态。
2. Lock服务
Lock服务由Lock Server集群提供，集群间通过Paxos保证一致。
Lock Server上保存着一张关于锁的表，表中记录着哪个文件的锁被哪台服务器占用：
1 | file owner |
同时，用户服务器的Frangipani模块也会记录它所持有锁的情况，如下。其中，锁有两种状态：busy表示文件正在被读写；idle表示文件操作已完成，但服务器依旧持有锁。content则记录着文件的内容。
1 | file/dir lock content |
有了锁，用户服务器操作文件需满足如下规则：
只有用户服务器持有文件对应的锁，才能缓存文件。当用户服务器需要操作文件时，需要先向Lock Server申请锁，然后才能从Petal磁盘中读取文件，缓存到本地。
释放锁之前，需要将修改的文件写回Petal。
当Server1需要获取相应的锁时，Server1需向Lock Server发送请求，LS收到请求后：
若锁未被占用，Lock Server会授予锁给Server1。
若锁被Server2占用，Lock Server会向Server2请求释放锁。如果此时：
锁是idle状态，Server2会先将修改的文件内容写入Petal，然后才把锁还给Lock Server。
锁是busy状态，则会等待操作完成，变成idle状态。
为什么用户服务器操作完成后，依旧持有锁？因为，操作完成的文件，可能不久后又会被使用，这样就不用再次申请锁。同时，在Frangipani系统中，用户服务器通常都操作自己的文件，很少操作共享文件。
另外，Lock服务提供读写锁。对于同一个文件，可以同时多个Server拥有文件的读锁，但一旦有1个Server占有了文件的写锁，那其它Server就不能再获得读写锁。
通过Lock服务（分布式锁），Frangipani能保证：
缓存一致性：每个Server读到的都是最新的数据（最近一次修改后的数据）。
并发隔离：Server在进行一系列操作前，会申请所涉及文件的锁，然后进行操作，当所有的修改都保存到Petal上后，Server才会释放所有锁。
Lock服务会给锁规定租期(leases)。当Server持有的锁超过租期，它将不能再使用该锁。此时，它需要重新申请或归还锁。如果租期已过，Lock Server没收到Server的请求，它会判断该Server已崩溃。
3. 崩溃恢复
如果Server在持有锁期间发生崩溃，Frangipani系统要如何进行处理呢？
Lock Server能单方面强制释放锁吗？如果Server无法恢复，会一直占有锁吗？
对于Server缓存的数据要如何处理？如果Server已经将一部分数据写回Petal，这些数据又要如何处理？
Frangipani通过**WAL(write-ahead logging)**解决崩溃恢复问题。在将修改的缓存数据写入Petal之前，需要先把操作的详情写入Petal中的日志文件。
不同于常规的预写式日志，Frangipani有以下几点不同：
对每个Server都会有一个日志文件，相互间分离。
每个Server的日志文件保存在Petal共享磁盘中，而不是本地。
Frangipani日志文件中的每一条记录会包含如下信息：
日志记录序号。
将要修改的Block的编号。
将要修改的Block的新版本号。
修改的数据内容。其中只包含文件系统的元信息，比如目录的数据、文件的元数据(inode)等。其中不包含写入到文件内容的数据（？），它只在崩溃后用来恢复文件系统的基本结构。
一开始，Server会将日志记录保存在本地，当接收到Lock Server释放锁的请求时，Server会先将锁对应文件的日志记录写入到Petal，然后再将修改的文件内容写入Petal。
当Server1持有锁超过租期，且失去音讯，Lock Server会判断Server1已崩溃。此时，Lock Server会交代另一个已存活的Server2，让它重演Server1日志中最近的操作，以保证一致性。Server2重演操作时，只会重演Block新版本号大于当前版本号的操作（已执行过的操作不再执行）。当Server2完成恢复，Lock Server才会将Server1占有的锁释放。
针对Server1崩溃的几种情况：
如果Server1还没将日志写入Petal就崩溃了，那就什么也不会恢复。
如果Server1在写日志到Petal的过程中崩溃了，那Server2只会恢复已写入Petal的日志。
如果Server1在写入文件内容时崩溃了，Server2在重演日志过程中，只会执行未执行或执行到一半的操作。
4. 总结
由于Frangipani没有中心leader，它的性能不会因服务器数量的增加而明显降低。但个人认为，当服务器数量增加，系统性能还是会受Petal和Lock Server的影响。
Frangipani的设计虽然提出很早，但并没有产生深远影响。Frangipani更适用于组织内各工作电脑间共享一个文件系统，而不太适用于当下的分布式数据存储。目前，在分布式数据存储领域，主要是大型网站的数据库和用于大数据计算的文件系统。Frangipani更类似于文件系统，但它专注于文件缓存和缓存一致性，而这对于大规模数据(10TB)的读写，效果并不显著。
但Frangipani也有一些值得借鉴的点：
延迟释放锁，等到LS请求时再释放锁。
租期是个好东西。
给数据添加版本号，来判断操作是否已执行。