光与影的个人博客

NEUCoder

0%

Frangipani分布式文件系统

发表于 更新于 分类于 ，

Frangipani 分布式文件系统

Frangipani: A Scalable Distributed File System

Frangipani是20多年前发表论文中描述的一个分布式文件系统，之所以现在还要深度了解一篇这个“古老”的论文，是因为其中的一些设计思路值得我们学习和研究（不还是因为MIT6.824里要讲吗），Frangipani的设计出发点是要实现一个简单、方便扩展和管理的共享文件系统，在读论文时主要关注的点如下：

  1. 如何在分布式环境下实现缓存一致性？
  2. 如何实现分布式事务？
  3. 如何在经常出错的分布式环境中，通过错误恢复实现容错？、

基本架构

如下图所示，Frangipani的架构组成分为两层：

  1. Frangipani文件系统层（Frangipani file server module）：运行在操作系统kernel中，向kernel注册为一个文件系统实现，为上层的用于应用程序提供提供文件系统的操作接口
  2. Petal 虚拟磁盘层（Petal virutal disk）：为了方便扩展，Frangipani底层基于虚拟磁盘Petal，简化了磁盘管理、扩容等操作

整个系统中共有一下几种不同身份职责的运行进程：

  1. Petal server：Petal底层采用多个server+多块磁盘实现大容量分布式容错的虚拟磁盘，Petal server可以理解为接收磁盘操作请求、执行持久化操作的存储服务器
  2. Lock server：文件系统肯定离不开锁，其中lock server用来管理文件系统中的锁（multiple reader/singlewriter lock）。锁由多个lock server分别进行管理，每个lock server管理整个文件系统中部分锁。
  3. Clerk module：每个file server上运行的锁管理进程，用来维护和管理分配给当前file server的锁信息（申请、释放、锁降级等）
  4. Frangipani file server：提供文件系统操作接口，与Petal server交互实现数据操作。
  5. Petal device driver：隐藏petal的细节，使上层file server看起来就是一个大容量磁盘

不同身份职责进程的实际部署情况：

  1. Pertal server: 运行于实际的存储节点上，多个server共同提供一个 large, scalable, fault tolerant的虚拟磁盘
  2. Lock server：可以运行于Pertal server上，也可以运行于Frangipani file server，数量并不是与Pertal server一一对应的
  3. Frangipani file server：运行于任意服务器上，不同的Frangipani file server是等价的，均为用户提供整个文件系统的读取和修改权限

文件系统结构

Frangipani的文件系统结构如下图所示，和Unix的文件系统结构类似，均采用Inode+文件块的形式管理文件存储空间，由于Frangipani底层基于虚拟磁盘（优点是具备更大的可分配空间，缺点是虚拟磁盘上相邻的空间段可能分布于不同server上的磁盘），其对文件系统进行了更细致化的定义和管理。

Frangipani将虚拟磁盘空间划分为了6个逻辑块

  1. 参数块（parameters 0-1T）：存储共享配置信息以及文件系统管理信息，实际上只能用到几kb的空间
  2. 存储日志块（logs 1-2T）：将1T的空间等大小划分为256块，其中每一块（$2^{40}$bytes）属于一个file server的日志存储区（ps:日志是什么在下一部分进行介绍），每个日志存储区可以存储256个日志，即每一条日志最大空间为（$2^{16}$bytes）。
  3. 分配bitmap块（Allocation bitmaps 2-5T）：用来表示剩余的空间块是否为被占用
  4. Inodes块（Inodes 5-6T）：和unix文件系统中的inode功能相同，都是用来记录文件的元数据，每个inode大小与磁盘块大小保持一致512B（避免争抢情况），inode块与bitmap块的对应关系固定，即特定的bitmap永远标识指定的inode。(一方面释放文件是只需要释放bitmap，另一方面方便锁管理)
  5. 小块区（Small blocks 6-134T）：每块大小4 KB ($2^12$ bytes)，用来存储大小小于64kb的文件，当文件大小大于64KB时，剩余文件记录存储在大块区中
  6. 大块区（Large bolcks 136-$2^{34}$T）：每块大小为1T

Frangipani在虚拟磁盘划分时，采用了大量的固定大小分块思想，这样必然会导致内存碎片问题（fragmentation），论文中表示将小文件数据直接存储在inode上，能够缓解这种问题（存疑）

另外Frangipani文件系统还有几个小的trick

  1. 只有真正的写入虚拟空间时，才会真正的分配实际的物理存储空间
  2. 论文中说块的大小都是可调整的，Logs中日志存储区数量也是可调整的（为了掩盖设计不完善，画的饼吧）

基于log的持久化保证

Frangipani采用类似于WAL（write ahead log）日志机制，实现元数据（metadata）的容错，具体实现如下

  1. 每个对于元数据的操作，首先创建一个相关日志写入到file server本地缓存中
  2. 日志周期性的将日志缓存持久化到petal磁盘上（即上面的logs），每个file server有自己单独的log存储区（论文中描述同样支持实时同步，即生成日志立刻持久化到petal磁盘上）
  3. 只有在日志持久化以后，才会真正的修改对应的metadata（论文里没有说什么时候向客户端响应修改成功或者说修改对客户端可见？我觉得是修改缓存成功后，因为论文中说持久化的周期时30S，如果在持久化以后延迟太高）
  4. 对于用户数据（修改文件内容等），Frangipani不通过日志管理，即不保证持久性

随着时间的的增长，log的数量会越来越多，如何解决log的空间占用/不足问题？

  • Frangipani将Petal磁盘上的log存储区管理为环状存储（circular buffer），当log空间不足，删除最老的25%的日志（老日志确保大部分均已提交，并且在踢出日志时，Frangipani会检查未提交日志，执行完毕再踢出存储）
  • 在两次从内存写入Petal磁盘上的刷新间隔中，最多允许1000-1600个对于元数据的操作

基于锁的一致性保证

既然是文件系统就离不开锁，Frangipani提供了写锁和读写锁（multiplereader/singlewriterlocks）分布式锁实现，以实现文件系统的中的并发控制，从而保证数据一致性，基本实现机制如下：

  1. 多个lock server+lock clerk模式：每个lock server管理一部分的锁，每个file server对应一个lock clerk，负责管理当前server的锁以及与lock server进行交互
  2. 其中锁以64位整数命名，每个lock server上的锁组织在一个以ASCII字符命名的table中
  3. 为了避免file server进程意外退出导致无限期占有锁，lock server分配锁时带有lease identifier（超时时间为30S），client必须在超时之前向lock server更新lease
  4. 为了避免死锁，Frangipani为整个文件系统中的锁分配了全局编号，client获取锁之前首先要确定需要的所有锁，之后按照编号顺序从小到大获取，失败则释放已经占有的锁，从头开始从新获取。（分布式事务）

补充一条：Frangipani的锁是sticky的，即client会一直持有锁，直到另外一个client申请锁

lock server和lock clerk相关的锁操作包括：

  • request：clerk向server发送的申请锁的请求
  • grant：server向clerk发送的授予锁的响应
  • revoke：server向clerk发送的撤销锁的请求
  • release：clerk向server发送的释放锁
  • 另外以上四个操作，能够实现锁的升级和降级操作

如何保证一致性

锁通过控制并发实现一致性控制，实际上就是dirty cache刷新时机和锁重分配之间的协调关系，当某个client在持有锁的过程中对数据进行了修改，此时要发生锁权限的变更，根据不同情况需要进行不同处理：

  1. 当前client持有读/读写锁，因为争抢要释放：首先要将dirty cache持久化到petal磁盘中，并将cache标记为无效（等待垃圾回收），最后再释放锁
  2. 当前client持有写锁，要降级为读写锁共享锁（只读不写）：首先要将dirty cache持久化到petal磁盘中，锁降级。此时并不需要invalidate cache，因为另外的client也是读，并不会修改数据

另个一角度理解（锁在缓存在，锁亡缓存亡-锁代表独占权，独占权保证了）：

  • 拥有数据的缓存，同时肯定拥有锁（如果是dirty cache，则拥有写锁）
  • 当server释放锁，同时要释放锁对应的缓存段

通过上述机制，即可保证Fragipani元数据的持久性和一致性

容错和恢复（fault-tolerant & recovery）

容错和恢复是拆不开的两个话题，一般分布式系统中通过多server实现容错，当一个server崩溃其他server能够继续正常运行，恢复纸崩溃server恢复重新提供服务的过程，两者共同保证了分布式系统的高可用性质。由于Frangipani存在多种不同身份职责的进程，因此存在多种情况下的容错和恢复。

Lock server

lock server可以看作一系列地位对等的p2p节点，相互直接之间通hearteart消息，监控状态。通过公式算法（Paxos）实现对于元数据的管理和一致性保证。

  • 元数据包括locker server列表，每个server负责管理的锁
  • 当lock server失效或者新的lock server加入时，lock会在不同节点间进行均匀分配，保证负载均衡

当一个lock server失效时，他所持有的锁以及对映锁状态会重新分配到其他lock server上。lock server恢复即直接作为新的lock server加入server群即可

File server

虽然Frangipani中存在多个file server，然而每个server只为其挂载在unix系统提供服务，当file server崩溃时，唯一的容错措施即在重启file server(看起来不是那么的分布式，或者可以理解为文件系统接口层实际上还是单机)。

虽然只能通过重启进行file server的容错和恢复，在file server崩溃时，需要执行一系列操作以保证数据的一致性，因为当前file server可能存在未持久化的修改、占有锁资源等，具体机制如下：

  1. 当client/lock server长期收不到file server响应时，即认为file server失效

  2. 当认定file server失效后，启动 recovery demon，获得失效server的log和lock,根据log重新执行未执行的更新，完成之后释放锁资源

    the changes to a block are applied only,if the block version number is less than the record version number.

    通过数据的version number判断是否需要重新执行log记录的操作

上述机制中，即使是由于网络分区问题导致的无法联系到file server，file server由于无法更新相关锁的lease，即没有权限操作数据，不会出现“脑裂”问题

Petal server

Frangipani实际上是偷懒了，由于Petal本身支持容错和恢复，所以存储层可以认识是可靠的

备份（Backup）

Copy-on-write：sometimes referred to as implicit sharing[1] or shadowing,[2] is a resource-management technique used in computer programming to efficiently implement a “duplicate” or “copy” operation on modifiable resources. - wikipedia

对于Copy-on-write，实际上可以简单理解为为了避免写阻塞读，写在副本上写，读此时在原数据上读，写完将副本更新到原数据上

在Petal的Copy-on-wirte机制上加了一点微调，实现了自己的备份机制（备份启动不需要recovery过程）

  • 采用了barrier同步机制，使用一个全局锁作为barrier
  • file server执行任何修改之前，必须获得这个共享全局锁
  • 当备份进程要执行时，向所有持有全局锁的file server申请释放，file server释放之前首先将dirty cache持久化，并释放其他锁后进入barrier
  • 当所有file server进入barrier后，备份进程获得全局锁，开始备份，备份完成其他file server退出barrier

显而易见的缺点是当系统备份时，整个系统只读不能写

总结

读完这篇论文发现其中很多设计还是很落后的（file server假分布式等），也存在很多未解决的问题（写请求发送过程中锁超时等），然而其中比较值得学习的就是其锁的管理和缓存一致性的实现。