论文地址：Frangipani
我们可以从这篇论文学到什么？
这篇文章在GFS之前，它的设计目标是解决高可扩展性和高吞吐，同时他希望可以使得administration更加简单。
比如当ADMIN 去增加或移除文件SERVER要非常简单，当服务器挂了可以立刻切到备份上。 文件系统如果出错可以自动恢复而不需要ADMIN的介入。
所以他的设计目标还是和GFS有很大不同。
和GFS比较
GFS是一个高可用，容错，低延迟的文件系统。一般是给巨大的文件用的，所以拥有很大的CHUNK SIZE。他提供弱的一致性模型，并且是运作在APPLICATION LEVEL.那么用户要使用GFS的时候，必须要有感知的去用GFS提供的库去编写程序。
Frangipani的目标是强一致性且用户无感知的文件系统，所以运行在KERNEL层。他还拥有很好的SCALE的能力因为它模块化的性质和基于虚拟DISK（PETAL）
架构上的差异是GFS在服务器中拥有大多数文件系统逻辑，而Frangipani则将逻辑分布在运行Frangipani的工作站上。也就是说，Frangipani并不像GFS那样真正具有文件服务器的概念，只有文件客户端。
当大多数活动是客户端工作站读取和写入单个用户的文件时，Frangipani的设计很有意义，这完全可以从工作站Frangipani缓存中进行。在这种情况下，Frangipani可提供出色的性能。
Frangipani有很多机制可以确保工作站缓存保持一致，既可以使一个工作站上的写入对于另一工作站上的读取而言立即可见，又可以使复杂的操作（如创建文件）成为原子操作，即使其他工作站是试图查看所涉及的文件或目录。
对于Frangipani，最后一种情况是棘手的，因为没有指定的文件服务器可以对给定的文件或目录执行所有操作。
相反，GFS根本没有缓存，因为它的重点是对大型文件的顺序读取和写入，这些文件太大而无法容纳在任何缓存中。通过在许多GFS服务器上剥离每个文件，它可以读取大型文件，从而获得高性能。因为GFS没有缓存，所以GFS没有缓存一致性协议。
架构
Frangipani是一个建立在Petal之上的分布式文件系统，采用分布式锁来保证一致性。其中Petal是一个增量扩展、高可用可以自动管理的分布式虚拟磁盘。
image.png
Frangipani最为显著的特性为——一组机器使用一个公共存储，使用锁进行同步访问。要求的其他特性包括：
- 所有用户看到文件的一致视图
- 更多的服务器可以很方便地添加到集群中来扩展容量和带宽而不需要改变已有服务器的配置甚至打断它们运行
- 管理员可以添加用户而不需要担心数据如何被管理
- 可以在不打断系统运行的情况下进行全局一致备份
- 可以在不需要运维介入的情况下从机器故障、网络故障以及磁盘故障中恢复
image.png
用户程序使用系统调用（文件系统）访问Frangipani文件系统，任何修改缓存在内核缓冲区中，直到调用fsync或者sync才被写入，显然Frangipani文件系统模块需要运行在操作系统内核中。所有的文件系统读写Petal上相同的数据结构，但是在虚拟磁盘上独立保存各自的redo日志。Petal提供了巨大、可扩展、容错的虚拟硬盘，而锁服务实现了多读单写锁。
安全性问题
Frangipani运行在可信环境中，并没有设计安全措施。如果需要在不可信环境使用Frangipani，可以将包含Petal的Frangipani服务器部署在可信环境，然后将不包含Petal的客户端和Frangipani服务器连接。
image.png
磁盘布局
Petal为Frangipani提供了一个巨大的虚拟磁盘空间，地址空间大小为2^64
，虚拟磁盘使用方式如下：
image.png
- 第一个区域（1TB）保存共享的配置参数和内部信息；
- 第二个区域（1TB）保存日志，每个服务器拥有私有的日志，目前划分了256个空间，因此最多支持256个Frangipani服务器；
- 第三个区域（3TB）保存位图，追踪剩余区域中的空闲块；
- 第四个区域（1TB）保存i节点，每个i节点大小为512B；
- 第五个区域（128TB）保存小数据块，每个数据块为4KB；
- 剩余区域保存大数据块，每个数据块为1TB。
比64KB小的文件只保存在小数据块中，更大的文件保存在16个小数据块加上1个大数据块中，文件大小不能超过16个小数据块加上1个大数据块的容量。如果超过需要修改整体的Frangipani配置，重新分配地址分布。
缓存的运用
Frangipani's 非常好的利用了缓存的特性。首先每个工作站都激进的缓存，为了速度。
缓存策略是write-back的，也就是只在需要的时候去刷回硬盘，不然就一直缓存着。这样就可以允许更新文件而没用网络。所有的操作都在工作站本地，非常快。这样就必须要求文件系统的代码要维护在工作站，而不是SERVER，这样就分布式化了。不再需要集中式的。
那么Frangipani 的工作站里缓存存了什么？
举个例子，WS1（work station 1）想要创建和写/u/rtm/grades
他第一步会去问Petal 读/u/rtm的信息到WS1的缓存。然后增加grades entry到这个缓存里。 他不会立刻写回PETAL，这样WS1之后可以做更多修改。
挑战就是WS2 去查看 "cat /u/rtm/grades" 不就读不到WS1写的内容了吗
另外一个问题是，如果2个WS 同时在一个目录下创建条目会不会一个覆盖了另外一个呢？
还有如果WS1挂了，他缓存的东西会不会成为脏数据，如何CLEAN UP呢
缓存的三个挑战的解决方案
首先缓存一致性协议可以解决“读看到最新写”的问题
已经有非常多的缓存一致性的协议，包括JVM里，想了解的可以看我这篇博客指令重排序 下的缓存一致性章节
Frangipani's coherence protocol：
首先有lock server (简称LS)， 每个文件或目录都会有一个锁。
锁的持有者是某一个WS，或者是NIL（没有持有者）
workstation (WS) Frangipani cache：
缓存的文件有2个状态： present, or not present
缓存的锁3个状态：locked-busy, locked-idle, unlocked
WS的规则：
- 上锁，然后去问PETAL读信息
- 写回PETAL，解锁
- 不能CACHE，除非拿到了锁
coherence protocol messages:
request (WS -> LS)
grant (LS -> WS)
revoke (LS -> WS)
release (WS -> LS)
例子： WS1 修改目录/u/rtm， WS2 读取它。
image.png
锁配合规则使得读可以看到最新的写。锁也可以确保最新的写是WELL-DEFINED的。
coherence optimizations
上述有一个locked-idle的状态，这已经是一个优化。他代表随后可以释放锁的状态。那么只有有别的WS需要这把锁，REVOKE就会被触发。同时Frangipani 是读写锁，所以允许多个读同时进行。最后因为都和LS和PETAL交互，而避免了WS之间的交互。这大大减少了COHERANCE 的通讯COST。
下面如何实现原子性呢？
同样也是用锁，一个WS要做一件事前，必须先持有对应资源的锁，当它做完了再去释放它。这样就确保了原子性。也不会发生2个文件同时创建，一个覆盖另一个的情况。
下面如何失败恢复呢？
当一个WS持有着锁死去，另一个WS想要操作这个资源该怎么办？
这里面涉及到很多不好的情况，比如拐到的WS已经有修改的数据再CACHE里，但是还没同步回PETAL。或者已经开始写回PETAL，写到半当中挂了。
我们应该等这个挂掉的机器修复重启还是应该不等呢？
Frangipani uses write-ahead logging for crash recovery
所以如果一个挂掉的WS已经做了一些PETAL写但是没有做完，这些没做完的操作可以通过LOG被完成。
- Frangipani 每个工作站都有一个单独的日志，而不是每个分片的传统日志，这避免了日志记录瓶颈，简化了分散操作，但将更新分散在给定文件上
- Frangipani 的日志位于共享的PETAL存储中WS2可能会读取WS1的日志以从WS1崩溃中恢复
WAL里有什么？
log sequence number
array of updates:
block number, new version number, offset, new bytes
其中只包含METADATA的更新，不包含文件内容的更新
示例-创建文件d / f会生成一个日志条目：
两个条目的更新数组：
在d的内容块中添加“ f”条目，并添加新的i编号
为f初始化i-node
最初，日志条目位于WS本地内存（尚未在PETAL）中
当WS从LS获得对修改后的目录的锁吊销时：
1）将其整个log送至petal，然后
2）将缓存的更新块发送到Petal，然后
3）释放LS的锁
有了上述的规则，我们来看当WS1持有着锁挂了该怎么办？
WS2要求获得LS1持有的锁
LS发送REVOKE没有接受到WS1的响应，超时后，然后LS告诉WS2去恢复WS1从PETAL的LOG里。
WS2去读WS1写的LOG 从PETAL里，随后执行这些LOG，然后告诉LS做完了，这个时候LS就可以释放WS1的锁，然后给WS2了。
所以把LOG存进共享的PETAL是非常重要的。这样就可以被别的WS去恢复。如果WS连LOG都没写进PETAL，这些操作就彻底丢失了。
下面我们来看另一个例子
image.png
如果WS3去无脑恢复WS1的LOG，就会把WS2创建的目录给删了。
所以为了避免这个情况我们需要增加一个version number的保护机制。
在REPLAY LOG的时候要去CHECK version > block version
当一个WS释放掉锁的时候，VERSION NUMBER++
如果VERSION NUMBER和前一个操作一样的情况下，代表WS1还没有释放锁，所以WS3去REPLAY LOG是安全的
为什么LOG不含有文件内容是OK的？
如果WS在将内容写入Petal之前崩溃，它将丢失。
Frangipani 恢复可以保护文件系统自己的数据结构。
应用程序可以使用fsync（）进行自己的可恢复内容写入。
对于Frangipani 来说，记录内容写入将太昂贵了。
大多数磁盘文件系统（例如Linux）都是相似的，因此应用程序已经知道如何应对崩溃前的写丢失。
当发生网络分区的时候会如何？
WS1持有锁，但是网络分区了，LS无法联系到WS1。但是锁是带EXPIRE TIME的。
这个时候WS1会持续写因为它持有锁。当锁到时间了，WS1要去和LS交互去刷新LEASE会发生刷新不了。那么之后WS1就不再拥有锁了，也写不了了。这个时候WS2去认为WS1死了，去恢复WS1的LOG，然后释放WS1的锁就是安全的了。
锁服务器挂了会如何？
锁服务器也是多个的，并且用类似PAXOS的协议去复制。这也包括了PETAL主备间的复制。这样确保了在PARTITION的时候，有一个LOCK SERVER。 确保只有一个PRIMARY FOR 每一个PETAL SHARD。这里具体可以参考ZOOKEEPER的博客ZooKeeper: Wait-free coordination for Internet-scale systems
性能
reads scale well with more machines
image.png
总的来说随着机器的增长，性能也在线性的增长，还是很SCALE的。没有先出的共享的瓶颈。
如果文件大于CACHE，或者有很多读写共享，或者缓存需要一个很大的SIZE时，或者经常要针对一个文件去操作，这个时候Frangipani 的性能就会变差。
同时增加服务器非常简单，只需要告知使用哪个Petal虚拟磁盘，以及如何找到锁服务。新服务器会联系锁服务获得租期，确定日志保存位置，然后开始处理操作。移除服务器就更加简单了，直接关闭即可。
总结
Frangipani 是一个CLIENT-SIDE 的CACHE策略，这样的策略性能会好。
同时利用了分布式锁服务实现了缓存一致性协议
非集中式的复杂服务在简单的共享的存储层上。
针对每一个CLIENT的LOG来非集中式的恢复。
FAQ
Q：Frangipani 系统中的Petal服务器为什么有块接口？ 为什么不拥有知道目录和文件之类的文件服务器（如AFS）？
A: 一个原因是作者首先开发了Petal。 Petal已经解决了许多容错和SCALE问题，因此使用它可以简化Frangipani 设计的某些方面。 这种安排将工作从集中式服务器转移到客户端工作站，这有助于在增加更多工作站时很好地扩展。
但是，由于没有一个实体负责，Frangipani /petal拆分使在文件系统级结构上强制执行不变式变得更加困难。 Frangipani 建立自己的事务系统（使用锁服务和Frangipani 的日志），以便能够对存储在Petal中的文件系统进行复杂的原子更新。
Q：运行Frangipani 的工作站能否破坏安全性？
A：可以。 由于文件系统逻辑位于客户端工作站中，因此设计将信任置于客户端中。 用户可以修改本地Frangipani 软件，并在Petal中读取/写入其他用户的数据。 如果用户是不值得信任的，这将使Frangipani 失去吸引力。 在小型组织中，或者如果Frangipani 在单独的专用服务器上（而不是在工作站上）运行并使用诸如NFS的协议与用户工作站进行通信，这可能仍然有意义保证安全。
Q: Frangipani 的日志填满时为啥会花更多时间？
A：由于存在日志记录，所有更改都必须写入Petal两次：一次写入日志，一次写入文件系统。必须先将操作写入日志（因此称为“预写日志”）。然后可以写入磁盘文件系统结构。只有这样，才能从日志中删除该操作。也就是说，只有在该部分中所有磁盘上文件系统的操作更新都已写入Petal之后，才能释放该日志的一部分。
因此，当Frangipani 的日志填满时，Frangipani 必须停止处理新的操作，将已修改的块从其高速缓存发送到Petal，以便在要重用的日志部分中进行操作，然后释放该部分并继续处理新的操作。
Q：为什么恢复只恢复METADATA,而不恢复文件内容？
A：如果工作站上的用户将某些数据写入Frangipani文件系统，然后工作站立即崩溃，则最近写入的数据可能会丢失。即，如果用户登录到另一个工作站并查看该文件，则可能会丢失最近写入的数据。
普通的Unix文件系统（例如笔记本电脑上的Linux）具有相同的属性：在崩溃之前写入的文件内容可能会丢失。
关心崩溃恢复的程序（例如，文本编辑器和数据库）可以要求Unix更加谨慎，但会降低性能。特别是，应用程序可以调用fsync（），该命令告诉Unix立即将数据强制到磁盘上，以便在崩溃时幸免。本文在第2.1节中提到了fsync（）。
这里的理由是文件系统谨慎地捍卫自己的内部不变量（基于自己的元数据），因为否则文件系统在崩溃后可能根本无法使用。但是文件系统将文件内容的不变量维护交给应用程序，因为只有应用程序知道哪些数据必须立即（且昂贵）立即写入磁盘。
Q： Frangipani上的LOG和PETAL上的LOG有什么不同？
A：Petal论文几乎没有提到Petal的日志。 我的猜测是，Petal记录更改为从逻辑块号到该块当前磁盘位置的映射，日志更改为“busy”位，该位指示哪个块更新该块的另一个副本可能缺失。 即，Petal记录有关低级块操作的信息。
Frangipani记录有关文件系统操作的信息，该信息通常涉及更新Petal中多个文件系统状态。 例如，用于删除文件的Frangipani日志条目可能表示删除操作修改了某些块和inode可用bitmap位，并且该操作删除了特定的目录条目。
这两个日志都存储在Petal的磁盘上。 从Petal的角度来看，Frangipani的日志只是存储在Petal块中的数据。 Petal对Frangipani的log并不特别了解。
Q： 论文说Frangipani 不会立刻发新的LOG到PETAL。那么如果这个时候WS CRASH了会如何？
A：假设在Frangipani 工作站上运行的应用程序创建了一个文件。 一段时间以来，有关新创建文件的信息仅存在于该工作站的缓存（在RAM中）中。 如果工作站在将信息写入Petal之前崩溃，则新文件将完全丢失。 它不会被恢复。
网友评论