第十章、分布式件系统名字空间实现研究

1、第十章.分布式文件系统名字空间实现研究1、空间概述名字空间(namespace)即文件系统文件目录的组织方式，是文件系统的重要 组成部分，为用户捉供可视化的、可理解的文件系统视图，从而解决或降低人类 与计算机之间在数据存储上的语义间隔。目前树状结构的文件系统组织方式与现 实世界的组织结构最为相似，被人们所广泛接受。因此绝大多数的文件系统皆以 tree方式来组织文件目录,包括各种磁盘文件系统(extx, xfs, jfs, rciscrfs, zfs, btrfs, ntfs, fat32 等)、网络文件系统(nfs, aes, c1fs/smb 等)、集群 文件系统(lustre, pnfs,

2、 pvfs, gpfs, panfs 等)、分布式文件系统(googlefs, hdfs, mfs, kfs, taobaofs, fastdfs 等)。随着面向对象存储和云存储的发展，出现了一种称为偏平化(flat)的文件系 统组织方式，典型代表有 lustre, panfs, amazon s3, google storageo 这种 方式把所有文件目录看作对象object,每一个对象有一个全局唯一的标识uuid, 户使用此uuid(而非路径)來访问存储系统。然而，uuid仅仅对计算机有意义， 在用户接口层往往还是需耍提供树状文件系统视图，再由系统在path和uutd 之间进行转换。在对象

3、存储层，对象或对象数据分片以文件形式存储在磁盘文件 系统z上，物理存储层仍然是树状存储结构。另外，对于法规遵从数据存储领域 广泛使用的固定内容存储系统cas (content addressed storage,内容寻址存 储)，采用基于对象的存储系统，机制与此类似。具体实现上，磁盘文件系统的名字空间宜接在磁盘上来实现，通常以 b*/b+/b-树的形式來组织，元数据和数据存储在相同的介质上。而对于分布式文 件系统来说，兀数据和数据和存储和访问是分离的，这是由高性能、可用性、可 扩展性等设计要求所决定的。通常，数据的存取由i/o服务器来实现，而元数据 由元数据服务器來负责。名字空间是元数据服务器

4、的核心任务z-,此外可能还 耍负责安全机制(如授权与认证)、锁机制、i/o负载均衡等。因此，rfl于元数据 与数据的分离，分布式文件系统名字空间实现的自由度比较大，实现方式有更多 的选择空间。这里将要介绍四种分布式文件系统名字空间实现机制，均为树状文 件系统视图，大致分为基于文件系统的实现和基于全内存的实现，但不包括基于 数据库的实现。基于数据库來实现文件系统名字间有众所周知的性能问题，尤其 是递归遍历文件目录空间。2、文件系统名字空间实现(1) 基于文件系统的设计这是一种站在巨人肩膀上的设计。磁盘文件系统本身就是树状结构视图, 因此可以利用这现成的机制在元数据服务器上实现名字空间。对于分布式

5、文件系统屮的每一个目录或文件，在元数据服务器的本地文件系统z上一一对应创建一 个目录或文件（以下称为元目录和元文件），两者之间的映射关系如图1所示。元 目录用来表示dfs屮的目录，其元目录屈性保存dfs目录屈性；元文件用来表示dfs中的文件，元文件属性保存dfs文件属性，元文件内容则用来保存元数据,包括更详细的文件屈性、访问控制信息、数据分片信息、数据存储位置等信息。dfs名了空间本地文件系统名字空间图1基于文件系统的设计（dfs与本地文件系统名字映射）基于文件系统我们以极小的代价构建了 dfs的名字空间，实现起来简单快速。 元文件仅用来存储数据文件的元数据，一般都是小于1kb的小文件，如果文

6、件口 录数量达到千万量级就会形成losf（lots of small files）的性能问题。实际应 用中如何來解决这种问题呢？目前主要有两种解决方法，一是采用适合海量小文 件存储的文件系统。reiserfs对小文件存储进行了特别优化，它不仅文件查找 效率高，而且节省磁盘存储空间，实际测试结果也验证了这一点。二是采用高性 能的存储介质，尤其是i0ps指标。非常幸运，固态硬盘ssd技术上已经比较成 熟，成本不断降低，非常适合高性能的存储应用。ssd的特点是i0ps高，普通 ssd读写ipos可以达到10000 50000,高端ssd甚至可以达到100000以上， 而fc、sas、sata磁盘的1

7、pos基本小于300,远远小于ssd。因此，采用ssd 和reiserfs文件系统，性能能够得到大幅提升，大多数应用问题不大。（2）基于全内存的分层设计这种方式与hdfs实现相仿。与基于文件系统的实现不同，名字空间完全在 元数据服务器的内存中，使用层次结构來表示，如图2所示。这种层次结构相当 于一棵树，每个结点表示dfs的一个口录或文件，结点的孩子结点理论上没有数 量限制（取决于内存可用量），孩子结点使用动态数组来表示。结点数据结构如下 所示，其中metadata表示（1）中文件目录类似的元数据信息，ch订dren是孩了 结点动态数组，使用二分法实现插入、查找和删除操作，严格按照名称进行升序

8、排序。root图2基于全内存的分层设计cppview plaincopyprint?1. struct inode 2. char *dname; /*目录或文件名，不包括路径*/3. char *metadata; /* 元数据 */4. struct inode *children; /* 孩子结点数组 */5. uint32_t count; /*子el录和文件计数器*/6；对于文件系统is操作，首先对路径进行解析并拆分成独立的目录名，然后 从root结点开始查找，孩子结点数组使用logn的二分搜索binarysearch查找， 直到找到对应的目录结点，然后遍历结点的孩子结点数组即叮。假

9、设目录深度为 h, 口录宽度为n,贝ij查找口录文件的时间复杂度为0(h*log(n)。对于文件系 统来说，这种查找时间复杂度显得有点高，尤其是目录层次很深、子目录文件数 量庞大的分布式文件系统。hdfs的设计思想源口 gfs,可是在名字空间设计上还 是与gfs存在一定的差距，可谓形似而神不似。另外，全内存设计对内存需求比 较高，假设每个目录文件的元数据大小为loo字节，则1千力目录文件的元数据 大小总量约等于1, 000, 000, 000 = 1gb。如果需要支持更多的目录文件,则需要 应增加内存量。(3) 基于全内存的hash设计这种方式与gfs实现相仿。gfs论文屮指出其名字空间采用了

10、全内存设计、 偏平式组织、前缀压缩算法、二分查找算法、没有支持is的数据结构，论文中 还指出is操作的效率较低。gfs没有开源，不像iidfs可以查阅原代码，因此也 无法完全重现gfs的名字空间实现，基本全内存的hash设计可能比较接近其设 计。这种设计采用hash和二分查找相结合的来实现，即目录以完整的绝对路径 进行hash定位，该口录下的孩子结点使用二分查找进行定位，如图3所示。它 与分层设计的主要不同在于，只需要一次hash和一次二分查找，而分层设计需 要多次的二分查找，在性能上更优。我们仅对目录进行hash,名字空间具有一 定的偏平性，但没有达到gfs的完全偏平；子文件口录不包括父路径

11、部分，相当 于作了前缀压缩，但不如分层前缀压缩彻底。大胆猜测，gfs可能采用了全hash 设计或全列表设计，is操作通过前缀匹配來实现，即具有相同前缀的文件屈于 同一个目录，如此实现名字空间。图3基于内存的hash设计这种设计下，查找指定文件或执行is,首先将路径分解成父路径名和目录文 件名，对父路径名进行hash运算定位至其孩子结点列表，然后二分查找指定文 件，或者遍历孩子结点列表实现is操作。假设目录宽度为n,查找时间复杂性 为log(n),在内存占用量上要稍稍大于分层设计，因为口录结点均重复一次。 这种设计具有支持is的数据结构，相对于gfs来说，执行is效率要高出许多, 如果gfs是全

12、hash设计则需要遍丿力整个文件空间进行前缀匹配，如果gfs是全 列表设计则需要以父路径名进行二分查找然后局部前缀匹配。(4) 基于全内存的双重hash设计这种方式是对基于全内存hash设计的改进。它先对目录进行第一次hash运 算，然后对子文件目录进行第二次hash运算，从而将查找时间复杂性从log(n) 进一步降低至0(2),如图4所示。目录hash表是全局的，而目录结点的hash 表是局部的，每一个口录结点都包含一个hash表，仅用来存储木口录下的子文 件目录信息，目录结点数据结构如下所示。子文件目录局部hnsh表图4基于内存的双重hash设计cppview plaincopyprint

13、?1.struct inode 2.char *dname; /* h录或文件名，包:括路径*/3char *metadata; /* 元数据 */4.hashtable *children; /* 孩子结点 hash 表5.uint32_t count; /*子目录和文件计数器*/6.；structinode char *dname; /*目录或文件名,包括路径*/char *metadata; /* 元数据 */hashtable *children; /* 孩子结点 hash 表 */uint32_t count; /*子目录和文件计数器*/；对于文件系统1s操作，对路径名进行一次has

14、h运算定位到目录结点，然后 对目录结点屮的hash表进行遍丿力即可。文件查找时，首先将路径名分解成父路 径名和文件目录名，对父路径名进行hash运算定位父目录结点，然后对文件目 录名进行hash运算并在父目录结点中的hash表进行定位。目录结点中的hash 表初始为未创建，直到第一次创建子文件目录时方才创建，屆sh表项数量定义 为平均目录包含的了文件目录数量，在性能和内存空间节省z间进行折中。如杲 内存充足，hash表项数量应该尽量设置大些，以达到更好的散列效果。与基于 全内存的hash设计相比，这种设计查找性能上更上层楼，内存消耗相应有所增 加。3、分析与应用选择上述分布式文件系统名字空间的四种实现方式，按照实现位置划分，可分为 基于文件系统的实现和基于内存的实现。基于文件系统实现的优点是实现简单, 内存要求低，可以运行在普通的机器上，缺