CN102915340A - 一种扩展的基于b+树对象文件系统 - Google Patents

Abstract

一种扩展的基于B+树对象文件系统，包括：空闲空间组织模块，用于设定extent表示磁盘空闲空间，extent用块起始地址和连续块长度为参数的二元数组表示出来；对于每组中的多个空闲extent，除考虑各个extent的大小外，还以各extent的起始地址为关键字用B+树进行组织；空闲空间分配模块，用于在分配磁盘空闲空间时按extent进行分配，分配空闲块时既考虑空闲块大小也考虑空闲块起始地址，采用最接近的最优匹配原则；对象空间分配模块，用于采用预分配方法在一次写请求中给对象分配空间，设置一个固定的预分配值。本发明提高可靠性和可扩展性、提高储系统的输入输出速率和数据吞吐率。

Description

一种扩展的基于B+树对象文件系统

技术领域

本发明涉及计算机存储技术，尤其是一种对象文件系统。

背景技术

信息技术的飞速发展使得信息存储应用日益简单，存储容量剧增，新一代的文件系统需要支持具有高效扩展和高效管理的高性能计算环境。传统的分布式文件系统一般包括文件管理和存储管理两个组件。文件管理组件实现的是层次管理、访问控制和命名等功能；存储管理组件是将逻辑数据结构映射到底层物理存储介质上，实现物理存储。在新一代大规模分布式存储系统中，将每个独立的存储设备分别添加存储管理组件，这样可以使得存储设备具有高效扩展性和高效管理性。

基于对象文件系统也是采用这般模型，保存对象的存储设备被称为OSD(object-based storage devices)。OSD是一种智能设备，包括内存、处理器、存储介质、网络接口等控制部件。OSD是提供对外的访问接口来管理本地对象及对象与存储设备间的映射关系。

OSD的主要功能是数据存储和安全访问。OSD实用对象对所有的数据进行管理。它将数据存放在磁盘的磁道和扇区，将若干磁道和扇区组合起来构成对象，并通过此对象向外界提供对数据的访问。每个对象都包含有读操作、写操作等访问接口，每个对象可能包含若干的文件，也可能是某个文件的一部分，并且每个对象都是独立于操作系统的。除了具体的用户数据之外，OSD还记录了每个对象的属性信息，既有静态属性（如建立的时间等）也有动态属性（如最后的访问时间等）。根据不同的特征应用，创建者可以为对象属性设置不同的内容和大小。这些信息存放在OSD上，大大减轻了元数据服务器的负担，增强了整个存储系统的并行访问性能和可扩展性。OSD模型如图1所示。

由于存储容量的急剧增加，存储设备数量的不断增加，存储设备效率的存储管理将影响到整个系统的性能。很多基于对象存储的分布式系统中的OSD都是采用磁盘文件系统进行存储管理的。然而这些对象文件系统在以下几个问题：

首先对象文件系统没有目录层次概念，所有对象ID构成了一个巨大的平面名字空间。这会使得本地文件系统中基于目录层次信息的优化不能直接运用到OSD上。例如，本地文件系统(ext2或ext3等)通常以目录为线索对文件数据布局、缓存和预取进行有效的优化，而这些优化迁移到OSD上时变得困难。此外，巨大的平面名字空间使得对象查找需要进行新的优化。

其次，对象文件系统可能支持很多大文件。本地文件系统中多数都是小文件，因而文件的组织管理方式对中小型文件特别有效。对于大文件可能就失去了原有的高效性了。

最后在特定的上层分布式文件系统部署下，当对象存储控制器上对象文件系统负载可能有更加鲜明的分布特点，这时需要采用特殊的磁盘布局和分配策略来提高对象文件系统的性能。

发明内容

为了克服已有对象文件系统的可靠性较差、可扩展性较差、存储系统的输入输出速率和数据吞吐率较低的不足，本发明提供一种提高可靠性和可扩展性、提高储系统的输入输出速率和数据吞吐率的扩展的基于B+树对象文件系统。

本发明解决其技术问题所采用的技术方案是：

一种扩展的基于B+树对象文件系统，所述基于B+树对象文件系统包括：空闲空间组织模块，用于设定extent表示磁盘空闲空间，extent用块起始地址和连续块长度为参数的二元数组表示出来；按空闲extent大小将整个磁盘空闲空间分成多个组，每个组使用数据结构bucket表示，每个组里的extent大小满足边界限制，设定了一个组因子B，假设空闲空间总共分为N个组，N≥2，那么对于第k组中的任意空闲extent，其大小S满足式下式：

$\left\{\begin{array}{c}0<S<=B^k(k=0)\\ B^{k-1}<S<B^k(0<k<=N-2)\\ B^{k-1}<S<{=2}^P-1(k=N-1)\end{array}\right.$

其中，P表示存储系统的位数；

初始化时磁盘上只包含一个大空闲extent，它属于第N-1个bucket；对于每组中的多个空闲extent，除考虑各个extent的大小外，还以各extent的起始地址为关键字用B+树进行组织；

空闲空间分配模块，用于在分配磁盘空闲空间时按extent进行分配，分配空闲块时既考虑空闲块大小也考虑空闲块起始地址，采用最接近的最优匹配原则，首先根据所需空闲块大小确定最小包含所需空闲块大小的bucket，如果满足条件的bucket没有可以分配的空间，则找包含更大空闲块的bucket，再根据所需空闲块首地址找到该bucket中首地址最接近所需空闲块起始地址的空闲extent；一旦满足条件的extent找到，extent中最接近所需空闲块的部分从bucket中移除分配给该对象，extent中剩下的空闲部分按大小和起始地址插入到相应的bucket中去；

对象空间分配模块，用于采用预分配方法在一次写请求中给对象分配空间，设置一个固定的预分配值，假定对象的末尾还没到达并且还需要为对象分配额外的存储空间，依次按照预分配值地址由小到大排序的空闲extent，直到找到本次操作实际需要大小的extent为止；如果找到一个超过预分配值大小的空闲extent，分配器将会按预分配值大小分配该空闲extent。

进一步，所述空闲空间组织模块中，对B+树进行两种查找，一种是从最小关键字开始进行顺序查找；另外一种是从根结点开始找到叶子结点；利用B+树快速检索需要的空闲extent，B+树叶子结点指向一个空闲extent，其中关键字表示各extent的起始地址，Pointer表示各extent的长度，中间结点用于B+树结点块的索引。

本发明的有益效果主要表现在：扩展的基于B+树对象文件系统可以大大减少单个对象内部的extent数并维护单个对象内部数据的连续性，从而可以减少对象访问时的找道开销。由于扩展的基于B+树对象文件系统的磁盘空间管理方法极力维持磁盘已分配空间的连续性，从而使得整个对象文件系统在长期使用过程中可以有很好的性能。

附图说明

图1是OSD模型的示意图。

图2是磁盘空闲空间组织的示意图。

图3是磁盘空闲空间分配的示意图。

图4是分配前磁盘空间状态的示意图。

图5是分配后磁盘空间状态的示意图。

具体实施方式

下面结合附图对本发明作进一步描述。

参照图2~图5，一种扩展的基于B+树对象文件系统，包括三个部分：①空闲空间组织；②空闲空间分配；③对象空间分配。

空闲空间组织：假设extent表示磁盘空闲空间，则extent可以用块起始地址和连续块长度为参数的二元数组表示出来，用extent表示连续块比通用的用块列表表示连续快具有更高的效率和简洁性。extent可以使大文件操作时需要写入的元数据呈数量级的减少，因而可以协助提高文件顺序读写性能。此外，由于多数情况下磁盘具有大量连续空闲空间，extent也能更有效的管理磁盘空闲空间。

为了提高磁盘空闲空间的管理效率，一种扩展的基于B+树对象文件系统按空闲extent大小将整个磁盘空闲空间分成多个组，每个组使用数据结构bucket（桶）表示。每个组里的extent大小满足一定的边界限制。一种扩展的基于B+树对象文件系统设定了一个组因子B，假设空闲空间总共分为N(N>=2)个组，那么对于第k组中的任意空闲extent，其大小S满足式下式：

一种扩展的基于B+树对象文件系统初始化时磁盘上只包含一个大空闲extent(初始磁盘最大空闲空间)，它属于第N-1个bucket（桶）。随着对象空间不停的分配和回收，各个bucket（桶）中的空闲extent不停的删除和添加，磁盘上空闲extent发生着变化，磁盘空闲空间的碎片不断增多。

对于每组中的多个空闲extent，除考虑各个extent的大小外，一种扩展的基于B+树对象文件系统还以各extent的起始地址为关键字(Key)用B+树进行组织。B+树是一种多路平衡查找树，可以对B+树进行两种查找，一种是从最小关键字开始进行顺序查找，这有利于顺序索引的情况；另外一种是从根结点开始找到叶子结点，这有利于随机查找的处理。由于B+树在查找、插入、删除时能提供良好的性能(时间复杂度为O(logn))，利用B+树快速检索需要的空闲extent。B+树叶子结点指向一个空闲extent，其中Key表示各extent的起始地址，Pointer表示各extent的长度。中间结点用于B+树结点块的索引。

空闲空间分配：扩展的基于B+树对象文件系统分配磁盘空闲空间时按extent进行分配，总是试图为对象在磁盘上分配大块连续的单个extent。对于小对象，仅仅需要小的空闲extents就可以完成分配。对于大对象，如果单独的大空闲块缺乏，可能需要分配多个空闲extent。这种情况下，这些extent应该在磁盘上尽量靠近，从而使得对象顺序访问时寻道开销最小。为了减少对象访问时的寻道开销，扩展的基于B+树对象文件系统分配空闲块时既考虑空闲块大小也考虑了空闲块起始地址。扩展的基于B+树对象文件系统采用最接近的最优匹配原则，首先根据所需空闲块大小确定最小包含所需空闲块大小的bucket（桶）。如果满足条件的bucket没有可以分配的空间，则找包含更大空闲块的bucket（桶）。扩展的基于B+树对象文件系统再根据所需空闲块首地址找到该bucket（桶）中首地址最接近所需空闲块起始地址的空闲extent。一旦满足条件的extent找到，extent中最接近所需空闲块的部分从bucket（桶）中移除分配给该对象，extent中剩下的空闲部分按大小和起始地址插入到相应的bucket中去。

对象空间分配：对象空间分配是指对象文件系统为单次对象写操作请求分配多少空闲块空间。扩展的基于B+树对象文件系统的性能与对象空间的分配粒度有很大关系。为了降低系统的碎片和提高系统性能，扩展的基于B+树对象文件系统并不是根据本次写操作的需要为对象分配空闲extent，而是采用预分配方法在一次写请求中给对象分配更多的空间，这样可以使多次写操作的数据在磁盘上更靠近并且可以减少空间分配带来的开销。扩展的基于B+树对象文件系统设置一个固定的预分配值，假定对象的末尾还没到达并且还需要为对象分配额外的存储空间，扩展的基于B+树对象文件系统分配器将会按预分配值地址最接近的空闲extent。如果这种extent找不到，分配器将会找到稍小的extent，一直找到本次操作实际需要大小的extent为止。如果找到一个超过预分配值大小的空闲extent，分配器将会按预分配值大小分配该空闲extent。

实施例：一种扩展的基于B+树对象文件系统按空闲extent大小将整个磁盘空闲空间分成多个组，每个组使用数据结构bucket（桶）表示。每个组里的extent大小满足一定的边界限制。一种扩展的基于B+树对象文件系统设定了一个组因子B，假设空闲空间总共分为N(N>=2)个组，那么对于第k组中的任意空闲extent，其大小S满足式下式：

对于每组中的多个空闲extent，除考虑各个extent的大小外，一种扩展的基于B+树对象文件系统还以各extent的起始地址为关键字(Key)用B+树进行组织。B+树是一种多路平衡查找树，可以对B+树进行两种查找，一种是从最小关键字开始进行顺序查找，这有利于顺序索引的情况；另外一种是从根结点开始找到叶子结点，这有利于随机查找的处理。由于B+树在查找、插入、删除时能提供良好的性能(时间复杂度为O(logn))，利用B+树快速检索需要的空闲空间extent。B+树叶子结点指向一个空闲extent，其中Key表示各extent的起始地址，Pointer表示各extent的长度。中间结点用于B+树结点块的索引。

扩展的基于B+树对象文件系统的磁盘空闲块空间组织的一个例子。图2中组因子B=4，bucket数组第3项表示当前磁盘上所有大小在16到64之间的空闲块集。这些空闲块由B+树组织起来，bucket数组的第3项包含一个指向该B+树根结点的指针。从图2中可以看出，当前磁盘包含三个起始地址小于95、大小在16到64之间的空闲块（extent），即（16，18）、（40，21）、（65，24），这些空闲extent大小分别为18、21和24，并且它们按地址递增的顺序用指针连接起来。

如果要给一个对象分配大小为17、起始地址为41的空闲块空间，则分配算法首先找到bucket[3]中的空闲extent。假如bucket[3]中没有空闲extent，那么就在bucket[4]中查找，一直往包含更大空闲块空间的bucket中寻找下去，直到找到满足要求的bucket或失败为止。当找到图3中所示的bucket[3]后，分配算法选取地址最接近的空闲块(40，21)，并将空闲块(41，17)分配给该对象，然后将原空闲块中因分配剩下的新空闲块(40，l)和(58，3)加入到bucket[0]和bucket[1]中(根据它们的大小和起始地址)。

扩展的基于B+树对象文件系统采用预分配方法在一次写请求中给对象分配更多的空间，这样可以使多次写操作的数据在磁盘上更靠近并且可以减少空间分配带来的开销。扩展的基于B+树对象文件系统设置一个固定的预分配值，假定对象的末尾还没到达并且还需要为对象分配额外的存储空间，扩展的基于B+树对象文件系统分配器将会按预分配值地址最接近的空闲extent。如果这种extent找不到，分配器将会找到稍小的extent，一直找到本次操作实际需要大小的extent为止。如果找到一个超过预分配值大小的空闲extent，分配器将会按预分配值大小分配该空闲extent，参照图4和图5。

Claims (2)

1.一种扩展的基于B+树对象文件系统，其特征在于：所述基于B+树对象文件系统包括：

空闲空间组织模块，用于设定extent表示磁盘空闲空间，extent用块起始地址和连续块长度为参数的二元数组表示出来；按空闲extent大小将整个磁盘空闲空间分成多个组，每个组使用数据结构bucket表示，每个组里的extent大小满足边界限制，设定了一个组因子B，假设空闲空间总共分为N个组，N≥2，那么对于第k组中的任意空闲extent，其大小S满足式下式：

$\left\{\begin{array}{c}0<S<=B^k(k=0)\\ B^{k-1}<S<B^k(0<k<=N-2)\\ B^{k-1}<S<{=2}^P-1(k=N-1)\end{array}\right.$

其中，P表示存储系统的位数；

初始化时磁盘上只包含一个大空闲extent，它属于第N-1个bucket；对于每组中的多个空闲extent，除考虑各个extent的大小外，还以各extent的起始地址为关键字用B+树进行组织；

空闲空间分配模块，用于在分配磁盘空闲空间时按extent进行分配，分配空闲块时既考虑空闲块大小也考虑空闲块起始地址，采用最接近的最优匹配原则，首先根据所需空闲块大小确定最小包含所需空闲块大小的bucket，如果满足条件的bucket没有可以分配的空间，则找包含更大空闲块的bucket，再根据所需空闲块首地址找到该bucket中首地址最接近所需空闲块起始地址的空闲extent；一旦满足条件的extent找到，extent中最接近所需空闲块的部分从bucket中移除分配给该对象，extent中剩下的空闲部分按大小和起始地址插入到相应的bucket中去；

对象空间分配模块，用于采用预分配方法在一次写请求中给对象分配空间，设置一个固定的预分配值，假定对象的末尾还没到达并且还需要为对象分配额外的存储空间，依次按照预分配值地址由小到大排序的空闲extent，直到找到本次操作实际需要大小的extent为止；如果找到一个超过预分配值大小的空闲extent，分配器将会按预分配值大小分配该空闲extent。

2.如权利要求1所述的一种扩展的基于B+树对象文件系统，其特征在于：所述空闲空间组织模块中，对B+树进行两种查找，一种是从最小关键字开始进行顺序查找；另外一种是从根结点开始找到叶子结点；利用B+树快速检索需要的空闲extent，B+树叶子结点指向一个空闲extent，其中关键字表示各extent的起始地址，Pointer表示各extent的长度，中间结点用于B+树结点块的索引。

Images