一种结合引用引用时间图和容器位表的垃圾回收方法
专利类型：发明专利
语 言：中文
申 请 号：CN201710478633.7
申 请 日：20170622
申 请 人：重庆大学
申请人地址：400044重庆市沙坪坝区沙正街174号
公 开 日：20171027
公 开 号：CN107301019A
代 理 人：
代理机构：
摘 要：本发明提出一种垃圾回收方法，用于提高基于重复数据删除技术的备份系统中垃圾数据的回收性能。该方法记录每个数据块的最新引用版本和每个数据容器相对于上一个备份版本的引用状态，分别称为引用时间图和容器位表。通过引用时间图和容器位表生成实际的引用时间图并利用其进行垃圾回收。与已有的方法不同的是，该方法在回收阶段，并不需要访问备份数据的元数据，而用已有的引用时间图和容器位表就可以进行回收，以相对较低的空间代价来大幅提高垃圾回收处理速度。此外，在多次数据备份中，本垃圾回收方法需要增加的空间开销非常小。??全部
主 权 项：本发明提出一种基于重复数据删除技术的备份系统中通过使用引用时间图和容器位表进行垃圾回收的方法。主要分为备份阶段与垃圾回收相关的数据预处理过程和垃圾回收阶段的垃圾回收过程。备份阶段与垃圾回收相关的数据预处理过程，具体步骤为：(1)对需要备份的数据集使用数据块变长算法或定长算法进行分块，然后采用哈希算法计算每个数据块的指纹。(2)对步骤(1)中得到的数据块指纹和已有的指纹表进行对比，如果不存在该指纹，则标记对应的数据块为新数据块；反之若存在该指纹，标记该数据块为重复数据块。(3)对步骤(2)中处理完成的每一个数据块，如果是新的数据块，对其添加引用时间图的尾部，并更新数据块的引用时间为当前版本号。如果是重复的数据块，其引用时间图暂不更新。(4)在步骤(3)结束后更新容器位表。容器位表是对每个数据容器，用两个比特位标记容器相对之前版本的内部数据块的引用情况。如果数据容器内的所有数据块在当前版本中都被引用，则是全部引用状态，用11标记；如果数据容器内只有部分数据块被当前版本引用，则是部分引用状态，就用10标记，如果数据容器内只所有数据块被没有被当前版本引用，则是完全没引用状态，就用00标记，对于步骤(3)中新的数据块，标记为新增引用状态，对应的容器位表用01标记，完成容器位表更新操作，这样就生成当前版本容器的容器位表。(5)引用时间图的更新。对于是全部引用状态的数据容器，其对应的引用时间图暂不更新，而在垃圾回收过程进行更新。对于部分引用状态的数据容器，数据容器内部部分被引用的数据块对应的引用时间图将被更新成当前版本。对于完全不引用状态的数据容器，则不用更新其引用时间图。而状态为新增引用?的数据容器，在步骤(3)中就已完成其对应引用时间图的更新。(6)在备份结束前，将对应的引用时间图和容器位表存储到磁盘上。备份结束。垃圾回收阶段的垃圾回收过程具体步骤为：(1)开始垃圾回收，读取在备份阶段与垃圾回收相关的数据预处理过程中存储的引用时间图和最新版本的容器位表。(2)根据最新版本容器位表生成实际引用时间图。(2.1)如果容器位表中数据容器对应的状态为11，表示完全引用，容器内所有的数据块对应的引用时间图更新为最新版本号；(2.2)如果容器位表中数据容器对应的状态为00，表示当前版本没有引用，则递归查找之前备份版本容器位表中对应位置的容器位表状态标识，直到找到对应容器位表为非00的状态，具体为：(a)若找到容器位表状态为01或10的容器，其引用时间图在权利要求书中备份阶段与垃圾回收相关的数据预处理过程步骤(3)和步骤(5)中已完成更新，所以不用更新引用时间图。(b)若找到容器位表状态为11的容器，记录11状态容器位表版本号，其对应数据容器内所有数据块都更新为此版本号。(2.3)如果是01或者10，因为其对应数据容器的引用时间图已经在备份阶段回收数据预处理过程完成了，所以不做处理。按照上面过程更新得到可用于垃圾回收的引用时间图。(3)用户给出回收版本T。(3.1)如果是单个版本回收方法，首先由回收版本T之前的所有容器位表进行或操作得到一个合并的容器位表，如果数据容器在合并后的容器位表中为?00状态，表明这个容器在之前所有备份版本中都没有被引用。然后遍历通过步骤(2)生成的引用时间图。回收该数据容器中引用时间为T的数据块。(3.2)如果是批量回收方法，引用时间中最新引用时间小于等于T的所有数据块都可以被回收。(4)释放步骤(2)所生成的实际引用时间图，垃圾回收结束。
关 键 词：
法律状态：公开
IPC专利分类号：G06F3/06(2006.01)I