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

摘要

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

主权项

1.基于快照的细粒度文件与目录版本管理方法，其特征在于，该方法是在文件与目录版本管理服务器上依次按照以下步骤实现的：步骤(1).初始化：对文件与目录系统的数据结构作以下扩充：在文件或目录的系统数据结构，即文件系统索引结点Inode中增加以下内容以适应支持文件或目录版本生成机制的系统要求：版本生成时的操作系统时间epoch，一个文件或目录的不同版本对应于不同的epoch值，越早生成的版本其对应的epoch值越小，反之越大；最近一次对文件或目录执行快照操作的时间snapepoch；共享位图，其中存放着同一文件或目录不同版本间的数据共享关系；位图位于Inode中的根索引结构以及间接索引结构内，其形式为比特位的集合；集合中比特与索引结构中的指针是依序一一对应的；比特‘1’代表对应指针所指向的数据块由本Inode管理，本Inode对该数据块有占有权，并可与之前的版本共享该数据块；比特‘0’代表对应指针所指向的数据块不属于本Inode，而是由之后的某个版本的Inode管理，本Inode仅具有对该数据块的使用权；版本索引结构，用来存放索引其他版本的指针以及相关状态；对于目录版本，其Inode中还有：索引数据块的指针i_block，指向动态哈希索引表；指向哈希函数的指针hash，标志当前所使用的哈希函数；文件系统中目录表中的目录项dentry：生命周期二元组，其中包括：出生时间，birth_epoch，即目录项所代表的目录版本被创建时的系统时间；死亡时间，death_epoch，即目录项所代表的目录版本被删去时的系统时间；与此同时，把整个文件系统中由文件和目录的不同名字组成的名字空间与由不同时间生成但名字相同的版本所组成的版本空间独立开来；在名字空间中，把彼此相关的子文件和子目录都存放在名字空间中同一个父目录下，从而不同名字的文件和目录按逻辑上包容的关系形成从名字空间的根目录出发的层级结构；在这里，每一个名字下的各个文件和目录都对应一系列的版本，组成一个版本空间，其中，文件和目录的版本按照版本生成的时间通过索引结构组织起来，使得生成时间相近的子文件和子目录版本按生成时间先后存放在同一个父目录的版本下，形成版本空间中的层级结构；名字空间的搜索采用了基于动态哈希的索引策略，版本空间的检索采用了基于红黑树的索引策略，且目录版本和文件版本分别采用针对各自特点的红黑树结构变体，相应的元数据存放在目录版本和文件版本对应的Inode结构体中；步骤(2)，按以下步骤生成相应版本：步骤(2.1)，按以下方式执行快照操作：当快照生成时在系统对应数据结构中记录快照的位置和时间，快照后的时间分别记录在：文件系统的全局变量中，称为全局快照的时间戳，即全局snapepoch；在用户执行快照操作所针对的文件或目录的当前版本的元数据中，称为该文件或目录的本地快照时间戳，即本地snapepoch；步骤(2.2)，按以下方式修改文件或目录：在文件系统层级结构树中，自顶向下执行由根目录当前版本到要修改的目录或文件的当前版本的寻径；对寻径途中所经过的各文件或目录的当前版本，找出其在名字空间中的父目录，按以下公式对该版本的本地snapepoch进行调整：本地snapepoch＝MAX(目录或文件的父目录当前版本的snapepoch，本地snapepoch)；步骤(2.3)，判断步骤(2.2)寻径结束所找到的那个文件或目录在调整快照时间后是否应该生成新的版本：比较经步骤(2.2)修改过的目录或文件的当前版本的Inode中的epoch与snapepoch的值，若：snapepoch大于epoch，说明最近一次快照操作后该版本还未被修改，该当前版本已经过期，需要保留旧数据，并复制该目录或文件当前版本的Inode元数据，作为历史版本保留，加入到索引结构中，同时通过位图形式记录当前版本与历史版本的数据共享信息；否则，说明当前版本没有过期，不用保留旧数据与元数据，直接修改当前版本的相关数据，同时修改当前版本的数据共享位图；步骤(3)，按以下步骤在名字空间中建立快速索引：步骤(3.1)，在名字空间目录中建立动态哈希表，其中，每个表项代表目录中的一个子目录或子文件，其地址存储在目录版本Inode中的记录映射表i_block域中，该目录当前所用哈希函数被存储在Inode中的hash域；该动态哈希表的每个表项包括两个部分：(a)指针pointer，指向一个基本存储单元bucket，设定为一个物理块的大小，内存着子目录或子文件的目录项，且其中变长数据块代表存储在该bucket中的目录项，该目录项含有子目录或子文件的名字及该目录项所代表的子目录或子文件的Inode号；(b)当前表项的级别Level，代表表项所指bucket被分裂的次数，当新插入的目录项映射到某表项，且该表项的pointer所指向的bucket没有足够的空间容纳该目录项，bucket就需要分裂；动态哈希表的每个哈希表项有不同的存储地址，作为名字的哈希值来把子目录或子文件映射到该表项；在该动态哈希表中采用了一组哈希函数h₀、h₁......h_k，为该系统中目录可容纳的目录项的最大数目，i∈{0，1，2，......，k}，i为哈希函数的级别level，h_i＝hmod2ⁱ，h为具有均匀分布特性的传统哈希函数；步骤(3.2)，以子目录名或子文件名作为输入，哈希函数的计数结果即为相应子目录或子文件所对应的表项在动态哈希索引表中的地址；步骤(4)，在版本空间中建立快速索引：步骤(4.1)，为文件系统中同一目录的不同版本建立基于Inode内嵌式红黑树的快速索引，以检索目录版本的元数据，其步骤如下：步骤(4.1.1)，该红黑树的叶结点只作为外部结点，没有对应实体，只为维持一个红黑树而存在；该红黑树的非叶结点作为内部结点，其中每一个内部结点与目录的某个具体版本一一对应；步骤(4.1.2)，内部结点的数据都存储在代表该目录版本的Inode中，存放在外存中，存储以下信息：结点关键值，为版本的生成时间epoch，指向该结点相应父结点的指针，指向左子树的指针，指向右子树的指针以及本结点的颜色；外部结点没有对应实体，只存在于内存中，存储以下信息：指向该结点相应父结点的指针，外部结点的颜色，后者缺省为黑色；在各个内部结点之间，结点按关键值排序：以根结点为基准，结点关键值比根结点大的内部结点，代表创建时间较晚的目录版本，位于根结点的左子树中，反之，则位于右子树中；按照红黑树树体调整算法，随着结点的插入和删除，各个结点的位置会自适应的变动；步骤(4.1.3)，目录新版本生成后，为代表该目录版本的Inode赋初值，置结点关键值为该版本的生成时间，置各指针为空，设定颜色为红色；步骤(4.1.4)，根据版本关键值在红黑树索引结构中搜索该目录版本应该插入的位置，索引方法如下：首先比较待插入结点与根结点的关键值，如果前者大于后者，则前进到根结点的左子树中继续搜索，否则，前进到右子树中，以此类推，直到抵达叶结点为止，缓存叶结点的父节点；然后用该结点替换叶结点，修改父结点中的相应子树指针指向该结点，修改该结点中的父结点指针指向父结点，并自动为该结点生成左右两个外部子结点，同时设其颜色为黑色，作为新的叶结点；由于版本生成时间的唯一性，如果搜索过程中发现已有结点与该结点关键值相等，则报错退出；步骤(4.1.5)，检查树体结构，如果不平衡则作相应调整，具体原则是：结点到其子孙结点的每条简单路径都包含相同数目的“黑色”结点，同时红色结点只能与黑色结点相邻；具体方法是：检查该版本结点的颜色与其父结点的颜色，如果两者不同时为红色，则操作结束；否则，按照Bayer在1972年提出的对称二叉B树树体调整算法，对包含该结点的相应子树作左旋或右旋操作，在子树中重新设置结点颜色，使该子树满足调整原则，保持树体平衡，并以旋转结束后的子树根结点为目标，进行下一轮的检查，如此循环往复；步骤(4.2)，为文件系统中同一文件的不同版本建立带权重线索红黑树的快速索引，以检索文件版本的元数据，其步骤如下：步骤(4.2.1)，该红黑树的非叶结点即内部结点，只作为索引结构使用，没有对应实体；该红黑树的叶结点作为外部结点，与文件的某个具体版本一一对应；步骤(4.2.2)，外部结点的数据都存储在代表该文件版本的Inode中，存放在外存中，存储以下信息：结点关键值，为版本的生成时间epoch，指向该结点相应父结点的指针，结点权重，分别指向权重链表中前驱和后继的指针以及本结点的颜色；内部结点只存在于内存中，存储以下信息：线索，即指向红黑树中序遍历中该内部结点前驱的指针，由于该前驱必定是外部结点，所以线索被用来提取前驱的关键值，指向该结点相应父结点的指针，指向左子树的指针，指向右子树的指针以及本结点的颜色；在各个内部结点之间，结点按其线索所指前驱的关键值排序，排序方式类似内嵌式红黑树，不同处仅在于各内部结点没有关键值，必须使用该内部结点的线索所指向的外部结点的关键值替代；步骤(4.2.3)，文件新版本生成后，为代表该文件版本的Inode赋初值，置相应外部结点关键值为该版本的生成时间，置其父结点指针和权重链表指针为空，设定颜色为黑色；步骤(4.2.4)，根据版本关键值在红黑树索引结构中搜索该文件版本应该插入的位置，索引方法如下：首先比较待插入结点关键值与根结点线索所指前驱的关键值，如果前者大于后者，则前进到根结点的左子树中继续搜索，否则，前进到右子树中，以此类推，直到抵达叶结点为止，缓存该叶结点，后文简称其为兄弟结点，及其父结点；然后生成新的内部结点，初始化该内部结点颜色为红色，同时使该内部结点的父结点指针指向上述父结点，以上述叶结点以及待插入外部结点作为该内部结点的两个子结点，同时初始化该内部结点的线索指向其左子结点，由于版本生成时间的唯一性，如果搜索过程中发现已有结点的关键值与该版本关键值相等，则报错退出；步骤(4.2.5)，检查树体结构，如果不平衡则作相应调整，调整具体原则是：结点到其子孙结点的每条简单路径都包含相同数目的“黑色”结点，同时不能存在两个连续的红色结点；具体方法是：以新插入版本结点的父结点为起始结点，检查该结点的颜色与其父结点的颜色，如果两者不同时为红色，则操作结束：否则，按照Bayer在1972年提出的对称二叉B树树体调整算法，对包含该结点的相应子树作左旋或右旋操作，在子树中重新设置结点颜色，使该子树满足调整原则，保持树体平衡，并以旋转结束后的子树根结点为目标，进行下一轮的检查，如此循环往复；步骤(4.2.6)，将该版本结点链接入权重链表中，具体方法如下：代表该文件已有版本的所有Inode会按照权重大小链接成一个权重链表，我们的设计中取权重值为结点关键值；如果步骤(4.2.4)所述的兄弟结点为该版本结点的左兄弟，则将该版本结点作为该兄弟结点的后继插入权重链表，设置兄弟结点、该版本结点、兄弟结点原来的后继结点的权重链表指针使这三个结点依序链接成链；如果兄弟结点为该版本结点的右兄弟，则将该版本结点作为该兄弟结点的前驱插入权重链表，设置兄弟结点原来的前驱结点、该版本结点、兄弟结点的权重链表指针使这三个结点依序链接成链。