基于快照的细粒度文件与目录版本管理方法

摘要

基于快照的细粒度文件与目录版本管理方法属于多版本文件系统领域。将整个文件系统中文件和目录名字组成的名字空间与代表不同版本生成时间的版本空间独立开来，采用相对独立的策略进行管理，形成了层级化的二维结构：在名字空间中形成从根目录到文件的层级结构；版本空间中，文件和目录的版本按照版本生成的时间通过索引结构组织起来，形成版本空间中的层级结构。名字空间的检索采用了基于动态哈希的索引策略，版本空间的检索采用了基于红黑树的索引策略，目录版本和文件版本分别采用针对各自特点的红黑树结构变体。本发明能够大大提升系统的可用性和性能，将维护历史版本所带来的时间空间消耗控制在可接受的范围内。

说明书

技术领域

基于快照的细粒度文件与目录版本管理方法属于多版本文件系统领域，尤其涉及文件与目录版本的生成、文件与目录数据的组织及检索领域。

背景技术

多版本文件系统是这样一种具有高可靠性的文件系统：通过将文件的数据和历史数据保存为不同的版本，在用户误操作或系统故障导致数据损失时文件系统能够自动查询正确的版本恢复损失的数据；同时，文件系统能够提供文件数据的变化记录供用户分析文件访问模式、追踪可疑的数据变化。传统多版本文件系统主要通过记录日志和历史数据实时拷贝技术来实现版本的保留。前者将对文件的每次改变都以一条记录的形式记录在日志中，占用空间量大，同时使用日志恢复历史数据时需要回滚日志，性能差；后者将文件系统在某一时刻的历史数据集中拷贝到一专门开辟的历史数据存储空间中，不但性能差、不易实现在线拷贝、占用空间量大，而且保留整个文件系统历史数据映像的操作粒度过粗，不能满足用户灵活保留部分目录与文件内容的需求，不利于管理。同时，使用以上技术的传统多版本文件系统在检索文件的指定历史版本时往往需要线性遍历之前的所有版本，存在性能瓶颈。

基于快照的细粒度文件与目录版本管理方法提出了一整套新的版本生成、组织与检索技术，有效的解决了上述问题。

发明内容

本发明的目的在于提供一个能够全面满足网络服务和科学计算服务需求的高可靠高性能的多版本文件系统，实现数据的在线实时保护。本发明的重点是：轻量级细粒度版本生成机制和高效版本检索模块的设计。

本发明的特征在于：快照技术为轻量级，快照执行时仅保留基本的时间信息，所有的拷贝操作(包括数据的拷贝和元数据的拷贝)被转移到真正需要修改时再进行。

将整个文件系统中由文件和目录名字组成的名字空间与由不同时间生成的版本所组成的的版本空间独立开来，采用相对独立的策略进行管理。名字空间中，彼此相关的子文件和子目录存放在同一父目录下，形成从根目录到各级子目录，最后到文件的层级结构，这里的每个文件和目录都对应一系列的版本；版本空间中，文件和目录的版本按照版本生成的时间通过索引结构组织起来，生成时间相近的文件和子目录版本存放在同一个父目录下，形成版本空间中的层级结构。

名字空间的检索采用了基于动态哈希的索引策略，用来代替传统文件系统中的线性索引策略，不但使得检索时间不随目录规模的扩大而线性增加，而且保证了较低的额外空间占用率。版本空间的检索采用了基于红黑树的索引策略，目录版本和文件版本分别采用针对各自特点的红黑树结构变体，相应元数据存放在版本对应的inode结构体(类UNIX系统中用来表示文件或目录的数据结构)中。

所述的基于快照的细粒度文件与目录版本管理方法依次含有以下步骤：

步骤1：细粒度版本生成

步骤1.1，按以下方式执行快照操作：

当快照生成时在系统对应数据结构中记录快照的位置和时间，快照后的时间分别记录在：文件系统的全局变量中，称为全局快照的时间戳，即全局snapepoch；在用户执行快照操作所针对的文件或目录的当前版本的元数据中，称为该文件或目录的本地快照时间戳，即本地snapepoch；

步骤1.2，按以下方式修改文件或目录：

在文件系统层级结构树中，自顶向下执行由根目录当前版本到要修改的目录或文件的当前版本的寻径。对寻径途中所经过的各文件或目录的当前版本，找出其在名字空间中的父目录，按以下公式对该版本的本地snapepoch进行调整：

本地snapepoch＝MAX(目录或文件的父目录当前版本的snapepoch，本地snapepoch)；

步骤1.3，判断步骤1.2所述的待修改的文件或目录在调整快照时间后是否应该生成新的版本：比较经步骤1.2修改过的目录或文件的当前版本的Inode中的epoch与snapepoch的值，若：snapepoch大于epoch，说明最近一次快照操作后该版本还未被修改，该当前版本已经过期，需要保留旧数据，并复制该目录或文件当前版本的Inode元数据，作为历史版本保留，加入到索引结构中，同时通过位图形式记录当前版本与历史版本的数据共享信息；否则，说明当前版本没有过期，不用保留旧数据与元数据，直接修改当前版本的相关数据，同时修改当前版本的数据共享位图。

步骤2：在名字空间中建立快速索引

名字空间中目录内部采用动态哈希表来组织各目录项，与传统线性索引相比，用动态哈希表组织各个目录项具有检索速度快且恒定的优点，同时相对于普通哈希表而言，其空间消耗能够随目录规模而自适应变化，扩展性好且空间利用率高。动态哈希表使用了一族哈希函数，其中各个函数对应的地址空间大小满足指数级递增的规律。当目录规模较小时，我们使用较小地址空间的哈希函数，当目录内容增加导致当前哈希函数地址空间无法容纳某个目录项时，需要进行哈希函数的升级，扩大地址空间，反之则要降级。

按以下步骤在名字空间中建立快速索引：

步骤2.1，在名字空间目录中建立动态哈希表，其中，每个表项代表目录中的一个子目录或子文件，其地址存储在目录版本Inode中的记录映射表i_block域中，该目录当前所用哈希函数被存储在Inode中的hash域；该动态哈希表的每个表项包括两个部分：(a)指针pointer，指向一个基本存储单元bucket，设定为一个物理块的大小，内存着子目录或子文件的目录项，且其中变长数据块代表存储在该bucket中的目录项，该目录项含有子目录或子文件的名字及该目录项所代表的子目录或子文件的Inode号；(b)当前表项的级别Level，代表表项所指bucket被分裂的次数，当新插入的目录项映射到某表项，且该表项的pointer所指向的bucket没有足够的空间容纳该目录项，bucket就需要分裂；动态哈希表的每个哈希表项有不同的存储地址，作为名字的哈希值来把子目录或子文件映射到该表项；在该动态哈希表中采用了一组哈希函数h₀、h₁……h_k，n为该系统中目录可容纳的目录项的最大数目，i∈{0，1，2，......，k}，(i为哈希函数的级别level)，h_i＝hmod2ⁱ(h为具有均匀分布特性的传统哈希函数，例如信息摘要算法MD5，安全哈希算法SHA)。

步骤2.2，以子目录名或子文件名作为输入，哈希函数的计数结果即为相应子目录或子文件所对应的表项在动态哈希索引表中的地址；

步骤3：在版本空间中建立快速索引

步骤3.1，为文件系统中同一目录的不同版本建立基于Inode内嵌式红黑树的快速索引，以检索目录版本的元数据，其步骤如下：

步骤3.1.1，该红黑树的叶结点只作为外部结点，没有对应实体，只为维持一个红黑树而存在；该红黑树的非叶结点作为内部结点，其中每一个内部结点与目录的某个具体版本一一对应；

步骤3.1.2，内部结点的数据都存储在代表该目录版本的Inode中，存放在外存中，存储以下信息：结点关键值，为版本的生成时间epoch，指向该结点相应父结点的指针，指向左子树的指针，指向右子树的指针以及本结点的颜色；外部结点没有对应实体，只存在于内存中，存储以下信息：指向该结点相应父结点的指针，外部结点的颜色(缺省为黑色)；在各个内部结点之间，结点按关键值排序：以根结点为基准，结点关键值比根结点大的内部结点，代表创建时间较晚的目录版本，位于根结点的左子树中，反之，则位于右子树中。按照红黑树树体调整算法，随着结点的插入和删除，各个结点(含根结点)的位置会自适应的变动。

步骤3.1.3，目录新版本生成后，为代表该目录版本的Inode赋初值，置结点关键值为该版本的生成时间，置各指针为空，设定颜色为红色。

步骤3.1.4，根据版本关键值在红黑树索引结构中搜索该目录版本应该插入的位置，索引方法如下：首先比较待插入结点与根结点的关键值，如果前者大于后者，则前进到根结点的左子树中继续搜索，否则，前进到右子树中，以此类推，直到抵达叶结点为止，缓存叶结点的父节点；然后用该结点替换叶结点，修改父结点中的相应子树指针指向该结点，修改该结点中的父结点指针指向父结点，并自动为该结点生成左右两个外部子结点，同时设其颜色为黑色，作为新的叶结点。由于版本生成时间的唯一性，如果搜索过程中发现已有结点与该结点关键值相等，则报错退出。

步骤3.1.5，检查树体结构，如果不平衡则作相应调整，具体原则是：结点到其子孙结点的每条简单路径都包含相同数目的“黑色”结点，同时不能存在两个连续的红色结点；具体方法是：检查该版本结点的颜色与其父结点的颜色，如果两者不同时为红色，则操作结束；否则，按照Bayer在1972年提出的对称二叉B树树体调整算法，对包含该结点的相应子树作左旋或右旋操作，在子树中重新设置结点颜色，使该子树满足调整原则，保持树体平衡，并以旋转结束后的子树根结点为目标，进行下一轮的检查，如此循环往复。

步骤3.2：为文件系统中同一文件的不同版本建立带权重线索红黑树的快速索引，以检索文件版本的元数据，其步骤如下：

步骤3.2.1，该红黑树的非叶结点即内部结点，只作为索引结构使用，没有对应实体；该红黑树的叶结点作为外部结点，与文件的某个具体版本一一对应；

步骤3.2.2，外部结点的数据都存储在代表该文件版本的Inode中，存放在外存中，存储以下信息：结点关键值，为版本的生成时间epoch，指向该结点相应父结点的指针，结点权重，分别指向权重链表中前驱和后继的指针以及本结点的颜色；内部结点只存在于内存中，存储以下信息：线索，即指向红黑树中序遍历中该内部结点前驱的指针(该前驱必定是外部结点)，用来提取前驱的关键值，指向该结点相应父结点的指针，指向左子树的指针，指向右子树的指针以及本结点的颜色；在各个内部结点之间，结点按其线索所指前驱的关键值排序，排序方式类似内嵌式红黑树，不同处仅在于各内部结点没有关键值，必须使用该内部结点的线索所指向的外部结点的关键值替代。

步骤3.2.3，文件新版本生成后，为代表该文件版本的Inode赋初值，置相应外部结点关键值为该版本的生成时间，置其父结点指针和权重链表指针为空，设定颜色为黑色。

步骤3.2.4，根据版本关键值在红黑树索引结构中搜索该文件版本应该插入的位置，索引方法如下：首先比较待插入结点关键值与根结点线索所指前驱的关键值，如果前者大于后者，则前进到根结点的左子树中继续搜索，否则，前进到右子树中，以此类推，直到抵达叶结点为止，缓存该叶结点(后文简称其为兄弟结点)及其父结点；然后生成新的内部结点，初始化该内部结点颜色为红色，同时使该内部结点的父结点指针指向上述父结点，以上述缓存的叶结点以及待插入外部结点作为该内部结点的两个子结点，同时初始化该内部结点的线索指向其左子结点。由于版本生成时间的唯一性，如果搜索过程中发现已有结点的关键值与该版本关键值相等，则报错退出。

步骤3.2.5，检查树体结构，如果不平衡则作相应调整，调整具体原则是：结点到其子孙结点的每条简单路径都包含相同数目的“黑色”结点，同时不能存在两个连续的红色结点；具体方法是：以新插入版本结点(外部结点)的父结点(内部结点)为起始结点，检查该结点的颜色与其父结点的颜色，如果两者不同时为红色，则操作结束；否则，按照Bayer在1972年提出的对称二叉B树树体调整算法，对包含该结点的相应子树作左旋或右旋操作，在子树中重新设置结点颜色，使该子树满足调整原则，保持树体平衡，并以旋转结束后的子树根结点为目标，进行下一轮的检查，如此循环往复。

步骤3.2.6，将该版本结点链接入权重链表中，具体方法如下：代表该文件已有版本的所有Inode会按照权重大小链接成一个权重链表，我们的设计中取权重值为结点关键值；如果上文(步骤3.2.4)所述的兄弟结点为该版本结点的左兄弟，则将该版本结点作为该兄弟结点的后继插入权重链表，设置兄弟结点、该版本结点、兄弟结点原来的后继结点的权重链表指针使这三个结点依序链接成链；如果兄弟结点为该版本结点的右兄弟，则将该版本结点作为该兄弟结点的前驱插入权重链表，设置兄弟结点原来的前驱结点、该版本结点、兄弟结点的权重链表指针使这三个结点依序链接成链。

本发明的优点如下：

(1)轻量级的快照技术仅记录快照的时间，将数据及元数据的拷贝操作分散并延后执行，使得快照操作的执行时间短，对系统其他操作的影响可以忽略不计。

(2)细粒度的快照技术能克服已有多版本文件系统不能对局部目录和文件保留版本的缺点，使用户能有选择地对目录和文件保留版本，灵活配置版本生成策略。

(3)名字空间和版本空间相互独立的版本组织与索引结构，能够充分利用同一目录和文件的版本间的紧耦合性，将同一目录和文件的版本组织在一起，存放在相近的物理位置，便于将其作为整体进行管理，同时提高了检索速度。

(4)在版本空间建立了父目录版本与子目录版本、文件版本间的层级结构，使得相近时间生成的子目录版本与文件版本存放在一起。时间越接近的版本，相关性越高，存放在同一个父目录版本下的概率也越高，利用这个特性可以加速从根到指定目录或文件版本的检索过程。

(5)名字空间采用动态哈希表来组织并检索目录内的目录项，具有检索速度快且恒定的优点，同时其空间消耗能够随目录规模而自适应变化，扩展性好且空间利用率高。

(6)版本空间采用树结构为同一目录或文件的众多版本建立索引，能够克服已有多版本文件系统的线性索引检索时间随版本数增加而线性增加的缺点。索引数据结构保存在相应版本的inode中，不改变文件系统在存储介质中的布局，兼容性好。同时，根据目录与文件访问模式的不同，采用略有差异的红黑树结构来建立索引，同时兼顾时间和空间的消耗。

本发明在清华大学计算机系高性能计算技术研究所进行了测试。结果表明，基于快照的细粒度文件与目录版本管理方法可以实现灵活配置版本生成策略的功能，有效提高了检索目录和文件历史版本的性能，同时，维护版本所带来的时间和空间开销小。

对基于快照的细粒度文件与目录版本管理方法的测试分别从历史版本属性访问时间，读写平均反应时间以及系统空间占用三方面进行。测试用服务器配置如下：Intel Xeon 2GHz处理器；512MB内存；Adaptec aic7902 Ultra320 SCSI适配卡；SEAGATE ST336607LW硬盘，容量为34GB。实验采用Linux操作系统，内核版本2.4.22。我们采用基于快照的细粒度文件与目录管理方法实现了一个原型系统thvfs，实验在thvfs、linux自带文件系统ext3、多版本文件系统ext3cow以及wayback之间进行，ext3cow版本为0.1.4，wayback版本为1.0.1。我们将测试用硬盘划分为一个分区，依序安装各个文件系统并测试。实验使用了清华大学计算机系高性能计算技术研究所开发的文件trace播放器作为测试工具，使用美国加州大学大学伯克利分校Roselli等人在1997年采集的文件trace：Research作为测试数据。测试结果见图5、图6、图7、图8。

从测试结果可以看出：如图5，就历史版本访问性能而言，我们的原型系统thvfs较著名多版本文件系统ext3cow提高了34.4％。Trace播放中，如图6，相对于ext3，thvfs的读性能提高12％；如图7，与多版本文件系统wayback、ext3cow相比，thvfs在写性能上的额外消耗最少；同时，如图8，在每72分钟生成一次快照的高频率下，thvfs维护所有历史版本仅需要70％的额外空间。

附图说明

图1.名字空间与版本空间的层级结构图。

图2.动态哈希索引示意图。

图3.用来建立目录版本索引的inode内嵌式红黑树。

黑内部结点

红内部结点

傀儡外部结点

图4.用来建立文件版本索引的带权重线索红黑树。

链表指针

线索

黑内部结点

红内部结点

外部结点

图5.ext3cow和thvfs版本访问时间的比较。

-●-eXt3eow

图6.trace实验中读平均响应时间(ART)比较。

-▲-ext3

-★-ext3cow

-■-wayback

图7.trace实验中写平均响应时间(ART)比较。

-▲-ext3

-★-ext3cow

-■-wayback

图8.空间占用量对比示意图。

图9.本发明流程示意图。

具体实施方式

基于快照的细粒度文件与目录版本管理方法需要对文件系统的关键数据结构作一定的扩展，具体内容如下：

Inode的扩充：Inode是文件系统中表示文件或目录的数据结构。在传统文件系统中，一个目录或一个文件仅对应一个inode；多版本文件系统中，一个目录或一个文件对应多个inode，原因是：多版本文件系统中的目录和文件有多个版本，每个版本都拥有独立的inode。inode数据结构中增加的内容包括：(1)epoch，版本生成时的操作系统时间，一个文件或目录的不同版本对应不同的epoch，越早生成的版本其对应的epoch值越小，反之越大；(2)snapepoch，用来存放最近一次对目录或文件执行快照操作的时间，与细粒度快照有关；(3)共享位图(share bitmap)，用来存放同一文件或目录不同版本之间的数据共享关系；(4)索引结构(index structure)，存放用来索引其它版本的指针以及相关状态。此外，对于目录版本，其inode结构的特有变化包括：(1)索引数据块的指针i_block由指向一个线性索引表变为指向动态哈希索引表；(2)增加指向哈希函数的指针hash，标志当前系统使用的是一族哈希函数中的哪一个。

Dentry的扩充。dentry代表文件系统中的目录项，如果把文件系统中的目录看成是一个表的话，其中的每一条记录就是一个目录项。dentry数据结构中增加的内容为：生命周期二元组(life cycle tuple)。其具体形式为<death_epoch，birth_epoch>；birth_epoch代表dentry被创建时的系统时间，即出生时间；death_epoch代表dentry被删除时的系统时间，即死亡时间。

基于快照的细粒度文件与目录版本管理方法能够支持指定目录或文件版本的生成与管理，其基本思想主要包含如下两点：

首先，快照生成时在系统元数据相应结构中记录快照的位置和时间。快照的时间记录在执行快照操作的目录或文件当前版本的元数据中，即每个目录或文件当前版本inode的snapepoch域中。例如：对整个文件系统所作全局快照的快照时间被记录在系统根目录当前版本inode的snapepoch中。

其次，对目录或文件的当前版本进行修改时，根据该目录或文件所处位置以及当前版本的时间信息判断是否应该生成新版本，如果需要则拷贝相应的元数据和数掘。这是细粒度版本生成技术的难点，原因是：一个目录或文件同时是其父目录、祖父目录以及根目录等祖先的子孙，在任一祖先上所做的快照都会对该目录或文件的版本产生影响。所以，判断一个目录或文件是否应该生成新版本需要依序遍历其所有祖先(根目录，…，祖父目录，直到父目录)的当前版本，对所有祖先的当前版本的快照时间进行调整和比较。调整的基本原则是：子目录或文件当前版本的快照时间应该晚于或等于父目录当前版本的快照时间。比较的基本原则是：如果被修改目录或文件当前版本的生成时间(记录在inode的epoch域中)早于该版本的快照时间，说明最近一次快照操作后该版本还未被修改，则需要生成新版本，反之则不生成。

细粒度版本生成算法示例如下：细粒度快照在某个目录或文件上执行时，首先，将快照时间即当前时间记录在全局变量superepoch和该目录或文件当前版本inode的snapepoch中。然后，当需要修改该目录或文件时，在文件系统层级结构中，自顶向下执行由根目录当前版本到该目录或文件当前版本的寻径，并作快照时间的调整(根目录除外)。以目录B的当前版本B*为例，设B*的快照时间为snapepochB，其父目录的当前版本为A*且其快照时间为snapepochA，则调整snapepochB的方法用公式表示如下：snapepochB＝MAX(snapepochA，snapepochB)。最后，当该目录或文件的当前版本快照时间结束调整操作后，比较其inode中的epoch与snapepoch值，如果snapepoch＞epoch，说明最近一次快照操作后该版本还未被修改，旧数据应该得到保留，通过复制该目录或文件当前版本的元数据以及被修改的数据，生成新的版本。

在上述遍历过程中，除了调整快照时间外，还需要在各个目录和文件当前版本的inode中缓存系统当前的superepoch值，该值仅保存在内存中，用来在再次执行遍历过程前，判断目标目录或目标文件当前版本inode是否过期，如果不过期，即缓存的superepoch与系统当前superepoch相等，说明自上次遍历后系统中还没有触发新的快照操作，可以跳过遍历，直接进行后续比较与修改。

为了利用同一文件或目录的不同版本间的紧耦合性，将不同版本按照时间顺序组织在一起，采用与名字检索相独立的索引结构，从而将整个文件系统中由文件和目录名字组成的名字空间与代表不同版本生成时间的版本空间独立开来，采用相对独立的策略进行管理。同传统文件系统一样，多版本文件系统的名字空间中，彼此相关的文件和子目录存放在同一父目录下，形成从根目录到文件的层级结构，我们称其为一维结构，如图1a所示。同时，多版本文件系统的版本空间中，我们将生成时间相近的文件和子目录版本存放在父目录的同一版本下，形成版本空间中的层级结构，并与名字空间的层级结构结合，我们称为二维结构，如图1b所示。在名字空间中，我们设计了动态哈希检索策略，在版本空间中，我们设计了基于红黑树的索引策略，目录版本和文件版本分别采用针对各自特点的红黑树结构变体，其中目录采用了inode内嵌式红黑树，文件采用了带权重线索红黑树。

多版本文件系统中，名字空间的动态哈希检索策略可以加速搜索过程，缓解由于保留目录和文件历史版本而给系统带来的额外管理负担。利用哈希索引进行检索的过程中，首先在目录中建立动态哈希索引表，其中每个表项，代表目录中的一个子目录或文件；然后，以子目录名或文件名作为输入，哈希函数的计算结果即为相应子目录或文件所对应的表项在动态哈希索引表中的地址。

动态哈希索引策略的核心是一组哈希函数h₀、h₁……h_k。设定系统中目录可容纳目录项的最大数目为n，则该组函数满足：h_i＝hmod2ⁱ，i∈{0，1，2，......，k)，其中i称为哈希函数的级别。h是传统哈希函数，应该具有将文件名均匀映射到地址空间的特性，可以选择SHA、MD5这样的哈希函数，具体由用户指定。图2为动态哈希索引示意图。

图2中部为动态哈希索引表，其地址存储在目录版本ionde中的i_block域中。该目录当前所用哈希函数的指针被存储在inode中的hash域中。动态哈希索引表每个表项包括两个部分：(1)指针pointer，指向一个基本存储单元bucket，子目录或文件的目录项就存放在bucket中，且目录项一般包含子目录或文件的名字及数据物理地址等信息；(2)当前表项的级别level。图中，每个表项左端的数字为该表项的存储地址，如果子目录或子文件的名字哈希值为该数字，则该子目录或子文件映射到该表项。例如，文件foobar，以其名字foobar作为输入，经过哈希函数h3计算得到的结果为7，则foobar对应的表项地址为7，再通过该表项中的pointer域我们就能够陆续找到该文件的目录项和数据。

表项中的pointer指向一个bucket，bucket是一个基本存储单元，设定为一个物理块大小，这是因为：首先，对外部存储的读取是以块为单位，对小于物理块大小的bucket的读取同样需要发起一次磁盘的I/O操作；其次，以ext2文件系统为例，一个物理块可以容纳至少3个目录项，而具有相同哈希地址的目录项可以存放在同一个bucket中，所以设定bucket为物理块大小也可以减少地址冲突的概率。图2右部为bucket示例，bucket中带阴影的变长数据块代表存储在该bucket中的目录项，目录项中的数字代表与该目录项所对应的哈希索引表表项的存储地址。如图第一个bucket内存储有三个目录项，其中两个对应存储地址为0的表项，另外一个对应存储地址为4的表项。图中Bucket内的空白部分代表空闲空间。

表项中的Level代表表项所指bucket被分裂的次数。当新插入的目录项映射到某表项，并且该表项的pointer所指向的bucket没有足够空间容纳该目录项时，bucket就需要分裂。Bucket的分裂需要调整相关索引表表项同buckets间的映射关系。

动态哈希索引策略中的主要算法包括检索、插入、删除以及表项回收。以下论述中，设当前使用的哈希函数为h_k，动态哈希索引表为IdxTbl[]。

检索：

使用动态哈希索引策略进行检索只需读取物理块2次。以检索目录项foobar为例，第一步根据目录项名计算出h_k(foobar)，按照此地址读取相应的动态哈希索引表表项IdxTbl[h_k(foobar)]；第二步，根据表项中的指针IdxTbl[h_k(foobar)]→pointer读取相应的目录项并进而找到文件数据。

插入与删除：

插入算法中当bucket中有足够空间时可以直接插入，否则必须生成新的bucket。如果当前哈希索引表引表具有足够多的表项，则直接建立表项与新生成bucket的映射关系，否则必须升级哈希函数，扩大地址范围，增加索引表表项数目。

删除算法除了执行必要的目录项删除操作外，还需要在必要时合并bucket，释放多余空间。

表项回收：

在动态哈希索引表的频繁插入删除过程中，会生成多余表项。表项回收算法用于压缩动态哈希索引表所占用的空间。首先遍历索引表的所有表项，如果所有表项的level值均小于当前哈希函数的级别k，则回收一半表项，哈希函数降级。表项回收的操作比较耗时，定期触发并在后台运行。

多版本文件系统中，版本空间的索引结构采用了两种基于红黑树的索引结构，包括：inode内嵌式红黑树和带权重线索红黑树。前者的优点是数据都存储于外存中的inode结构中，不占用内存空间，缺点是检索中需要执行较多访问外存的操作，相对后者速度慢；后者的优点是减少了访问外存的操作，速度快，缺点是需要占用额外内存空间。多版本文件系统中目录与文件的访问特点是：对目录的访问多是读取，修改少；而文件修改频繁，版本更新快，对检索性能要求高。综合考虑时间和空间的要求，我们使用inode内嵌式红黑树来索引目录版本元数据，而使用带权重线索红黑树来索引文件版本元数据。

基于红黑树的索引结构提供三种操作：检索、插入和删除。本文中称树的叶结点为外部结点；非叶结点为内部结点。

inode内嵌式红黑树是用来检索目录版本的元数据索引结构，是普通红黑树结构在多版本文件系统中的典型应用。其上的每一个内部结点与目录的某个具体版本一一对应，其数据结构被包含在代表该目录版本的inode中，存放于外存，主要用来存储以下信息：结点关键值、指向父结点的指针，指向左子树的指针，指向右子树的指针以及本结点的状态(颜色属性等)。结点关键值是检索的依据，设定为结点所对应目录版本生成时间epoch。其结构示意如下：

typedef struct embeddedininode_rbt_node{

  int key；         //代表关键值，设定为版本生成时间epoch

  int color；       //代表结点的颜色

  struct embeddedininode_rbt_node*parent；//指向结点的相应父结点

  struct embeddedininode_rbt_node*left；  //指向左子树的指针

  struct embeddedininode_rbt_node*right； //指向右子树的指针

} * pei_rbt_node；

外部结点是傀儡(dummy)结点，只为维持红黑树的性质而存在，没有对应的实体。

图3为inode内嵌式红黑树的示例。图中圆形的内部结点代表目录版本，结点中的数字代表关键值。内部结点按照关键值排序，以根结点为例，关键值比根结点大的内部结点，代表创建时间较晚的目录版本，位于根结点的左子树中；关键值比根结点小的内部结点，代表创建时间较早的目录版本，位于根结点的右子树中。图中方形的是外部结点，没有目录版本与其对应。

带权重线索红黑树是用来检索文件版本的元数据索引结构。其上的每一个内部结点都是建立在内存中的索引结点，数据结构中包含线索、指向父结点的指针，指向左子树的指针，指向右子树的指针以及本结点的状态(颜色属性等)，但不包含关键值；其上的每一个外部结点与文件的某个具体版本一一对应，数据结构被包含在代表该文件版本的inode中，存放于外存，主要用来存储以下信息：结点关键值、指向父结点的指针和权重，结点关键值设定为结点所对应文件版本生成时的epoch值。其内部结点和外部结点的结构示意如下：

typedef struct weightlink_rbt_node {

  union {

int key；        //用于外部结点，代表权重和关键值，外部结点排序的依据

struct {

  struct weightlink_rbt_node*ll；    //ll代表内部结点的左线索

  struct weightlink_rbt_node*rl；    //rl代表内部结点的右线索

} link；                //用于内部结点，代表结点的线索

  } kl；

  union {

int weight；    //用于外部结点，代表结点权重

int color；    //用于内部结点，代表结点的颜色，外部结点默认为黑色

  } wc；

  union {

struct weightlink_rbt_node*root；    //用于外部结点，指向红黑树的根

struct weightlink_rbt_node*parent；    //用于内部结点，指向本结点的相应父结

点

  } rp；

  union {

struct  {

  struct weightlink_rbt_node*forerunner；//用于外部结点，指向本结点在外部结

点链表中的前驱

  struct weightlink_rbt_node*successor； //用于外部结点，指向本结点在外部结

点链表中的后继

} chain；                 //用来为外部结点构建按权重排序的链表

struct {

  struct weightlink_rbt_node*left；    //用于内部结点，代表指向左子树的指针

  struct weightlink_rbt_node*right；    //用于内部结点，代表指向右子树的指针

} child；                 //用于内部结点，代表指向左右子树的指针

  } cc；

  int flag；         //标志位，存储本结点的属性，如：外部结点/内部结点标志

} * pwl_rbt_node；

权重代表外部结点的重要程度，用来构造红黑树外部结点权重链表，权重最大的结点位于表头，最小的结点位于表尾。为增加系统的可靠性和灵活性，我们在生成和删除文件版本时，除了将该版本从红黑树索引中插入或删除，还会在红黑树外部结点权重链表中执行相应操作。外部结点权重链表可以作为红黑树索引的补充：当红黑树索引意外失效时，用户仍然可以通过权重链表访问相应的文件版本。权重的具体含义可由用户自己设定，例如：可以取外部结点被访问的次数作为权重。

线索是红黑树内部结点中的特殊指针。一个内部结点的线索指向其在红黑树中序遍历过程中的前驱和后继，并且其前驱和后继都是外部结点。增加线索的作用是赋予内部结点以关键值，原因是：内部结点与文件版本间无对应关系，而外部结点有，同时系统中的关键值设定为文件版本生成时的epoch值，所以只有外部结点才包含关键值，内部结点无关键值。但红黑树检索操作需要读取内部结点的关键值，作为与待检索关键值比较的对象，通过线索访问内部结点前驱或后继的关键值可以解决此问题。

图4为带权重线索红黑树的示例，圆形的是内部结点，方形的是外部结点。图中以head为头的双向链表为按权重排序的外部结点权重链表，表头是最大权重外部结点。外部结点中的数字代表关键值，即外部结点所代表文件版本生成时的epoch值。本例中权重与关键值相等。图中由root内部结点引出的带箭头虚线代表root的线索：标注为“ll”的虚线代表root的左线索，指向root在中序遍历过程中的前驱；标注为“rl”的代表右线索，指向root在中序遍历过程中的后继。以检索关键值为2的结点为例，由于root没有关键值与之比较，所以需要将其左(右)线索指向的外部结点中的关键值4(3)读入，然后再比较。如果被访问结点关键值恰与读入关键值相等，则可以直接读入外部结点。如果不等，则转向相应子树继续检索。