Frangipani: A Scalable Distributed File System

[KTurnura]

Frangipani 是一个分布式文件系统，底层基于Petal分布式存储服务，在上层，多个运行Frangipani的服务器使用共享Petal虚拟磁盘，然后使用Lock服务保证cache coherence。该文件系统针对的场景主要是可信任的小群体，不用担心安全问题。

[KTurnura]

1. Frangipani Chanllenge

最开始我们介绍Frangipani所要解决的问题

1. Cacheing ： 主要逻辑放在Client端
   1. 强一致性（此处称为Cache Coherence） ：能很快看到其他节点对某目录下做出的更改
   2. Atomicity ：
   3. 单台服务器的崩溃恢复能力：不希望因为一个工作站发生的崩溃，导致其他使用同一个共享系统的用户也受到影响

上述主要针对Client端，而Petal内部有一套独立的恢复系统，类似于链式复制的内容

2. frangipani组成

在frangipani系统中，除了保存frangipani的服务器（Workstation）之外，还有Petal服务器，还有一个lock服务器，总共这三种

lock 服务器保存锁表，为每个文件分配一个锁

frangipani 工作站上也会保存一个锁表，上面记录了对应文件名，对应的锁session状态，即用到了哪种锁，还有锁的内容

3. Cache Cohherence

实现Cache一致性的主要方式：锁。只要没有人或者工作站查看这个文件，那么我们就可以对文件进行修改，在锁支持的目录下创建或删除文件，或者做一些其他操作

从最开始，先写入本地内存，然后经过一段时间后再写入Petal共享磁盘（可能每半分钟执行一次），这个过程不需要通过向服务器发送RPC请求

要求文件系统的业务逻辑必须存在于每个工作站（WorkStation，后续简称WS）中，以便我的WS能够实现诸如创建仅在其本地缓存之外运行的文件之类的操作

文件系统所有的复杂性都放在了每个Client端的frangipani中，这是一种去中心化的方案，优点：当添加新机器时，你会自动地获得更多的CPU处理能力，以此来执行这些新用户对文件系统的操作

lock 服务器保存锁表，为每个文件分配一个锁

frangipani 工作站上也会保存一个锁表，上面记录了对应文件名，对应的锁session状态，即用到了哪种锁，还有锁的内容

workstation的锁表内容

FILE（Frangipani使用unix风格的i-number对文件进行关联）	Lock	CONTENT
x	busy	～～～
y	IDLE	～～～

Lock Server内容

FILE	OWNER
x	Work Station 1
y	Work Station 1

RULE

除非工作站持有该数据所对应的锁， 我们才允许他对数据进行缓存

缓存流程

1. 从Lock Server中获取锁
2. 有读取Petal 磁盘内容的权限
3. 将Petal中的内容，缓存到自己的服务器上

释放锁的过程

1. 如果对缓存中的数据进行了修改，需要先将修改后的数据写回到Petal中
2. 只有Petal返回：确认收到消息后，
3. 该Work station才会释放锁

其他服务器请求锁的过程 LS为Lock Server

1. Request WS B-> LS
2. GRANT LS -> WS B
   1. 锁空闲： 直接分配
   2. 锁占有： Revoke LS -> WS A lock use
3. RELEASE WS A -> LS
4. GRANT LS -> WS B

如果Revoke消息收到后，锁目录中的lock信息是IDLE的话，并且该服务器中缓存的数据是脏数据的话，会首先将数据写回petal， 该workstation就会释放该锁，

为了防止数据丢失，会每30s让这些工作站将他们缓存中修改过的数据写回petal

4. WS使用的锁在使用完后延迟返还给锁服务器的原因

WS在使用完锁后并不立即返还给锁服务器，而是一直保持，直到锁服务器发送Revoke消息，才会执行释放锁的操作 如果我在我的工作站上创建了一个文件Y，我会将Y应用于其他领域，所以对于工作站来说，将最近锁使用过的文件上的锁积累起来再还给lock服务器，这样做是非常有利的

当其他用户想要查看我的文件时，他就需要获得该文件的锁，之前的WS也需要放弃这个文件的锁

4. Atomic muliti-step operation

类似于事务的概念，但frangipani是通过锁来实现的

当我完成所有的修改后，其他的工作站才能看到我所做的修改

不过为了完成这个目的，首先要去获取我所要读取或写入数据所需的全部锁，直到完成了操作，我才会对这些锁进行释放

5. Recovery

1. 某工作站在持有锁的时候，发生崩溃，甚至已经将某些写操作写回了Petal中

在持有锁时崩溃会影响的组件

1. 锁
   1. 此时崩溃后，锁不能立即释放！（==请思考为何不能释放==），因为存在他要对其他workstation隐藏该崩溃服务器坐出的修改
2. 使用预写式日志（Write ahead logging）来实现这种崩溃后可恢复的事务 ：如果一个工作站需要去执行一个复杂的操作，该操作涉及了要更新petal服务器上文件系统中的很多处数据，他会先向petal中他的日志里面追加日志条目，该日志条目描述了他所要做的这完整的一组操作。只有当这组操作的日志条目已经安全落地到petal中，即所有服务器都可以看到日志时，工作站才回开始发送写操作给petal服务器（此时已经将这所有更新操作的日志条目落地到了petal中）
3. fragipani有两个非常奇怪的预写日志点
   1. 通常一个系统只有一个日志，并且所有事务都是放在这个日志中的，但该系统，每个工作站都使用自己的日记！每个工作站的日志是独立的（而且工作站的日志都是存放在petal中，而不是在工作站自己的本地磁盘中
   2. 如果该工作站崩溃，那么其他工作站可以拿到该工作站的日志，

Petal 磁盘设计

预想下各自服务器的LOG Entry

Log sequence number	petal block number	version number	Data to be written	...

日志之包含对文件系统中目录，inode以及allocation bitmap的元数据的修改信息

一开始log存在frangipani的内存中，直到他不得不将日志写到petal中，他才会将日志写回petal

崩溃场景

崩溃主要针对Revoke的场景 Revoke的步骤

1. write log to petal
2. write modified blocks（锁针对的数据块
3. send release messages

崩溃可能发生在三个步骤前后，总共四种可能，

发生在log 写入petal之前

丢失上次预写日志到revoke的这段时间，重做

发生在第二步和第一步之间

重做数据后，写入数据块即可

发生在第二步和第三步之间

重做日志，在相同位置写入相同数据（幂等性）

发生在第三步之后出现的问题

该崩溃发生有需要讨论的一个点

例子

WS1 执行完删除操作后，已经释放了他的锁，WS2创建了WS1相同目录下的文件，此时Petal磁盘检测WS1故障，要求WS3重做WS1的日志，WS3可能实际上会删除WS2创建的文件夹

解决方法：

1. 使用版本号将存储在petal文件系统中的每个数据关联起来，类似于在位图的这种，会将同一个版本号和日志中所描述的每个更新操作关联起来，
2. 对于petal中所保存的数据（比如元数据，目录内容，数据块之类的，他都有一个版本号）

ws3会看到ws1所做的删除操作的版本号，并使用该版本号

因此该ws3重做后的删除操作并不会实际执行

如果Ws3 在恢复时，其他类似于ws2还存在着ws3恢复时所用的锁，怎么做

1. 不可能实现的方法
   1. 在恢复之前，先去petal中查看数据所对应的锁，但这种谁持有锁，谁没有锁的信息会因为供电故障的原因丢失，
2. 现实
   1. 恢复软件可以在不获取锁的情况下，对petal中的数据进行操作（高权限！），比如ws3在数据恢复时， 发现petal中的版本号比他重做的版本号要高，那么他就可以补充做这个数据块的恢复了（节省了成本）

崩溃检测方法

Frangipani使用lease来检测某个服务器是否崩溃，

特点

Frangipani在两个完全相悖（缓存一致性、原子事务性）的特征上都使用了锁

性能特点

frangipani 随着添加服务器，他的性能并不会受到抑制，赋予了合理的扩展性

该文件系统对学术的影响

并没有对存储系统的演进做出什么影响，因为frangipani所针对环境时面向小团体，通过它来共享文件，但他并没有应用到分布式文件系统中

frangipani的中心放在了缓存一致性和锁上面，对于读取数据和写数据并没有什么用，甚至于缓存根本没有什么用 （比如读取10TB数据，我们没办法进行实际缓存）