为了解决EB算法去重率较低以及磁盘访问开销较高的问题,本研究提出DBMB算法,主要改进思路如下:
1)聚合多个小文件为局部文件单元,并对文件单元进行去重处理,提高对小文件的去重率;
2)提出一种多特征匹配策略,选取文件的最大块、最小块以及中间块进行匹配,若均不同才认为两文件完全不同; 否则表明存在相似部分,进行去重处理;
3)采用Bloom filter,记录和维护磁盘中数据块的存储状态,使算法执行过程中无需读取磁盘数据,有效减少磁盘I/O开销.
1.1 小文件聚合及多特征匹配
在典型的存储系统中,小文件(一般小于64 kbyte)所占物理空间为20%左右,其文件数目却高达总数的80%,在采用传统的EB算法去重时,内存开销大而去重效果较差. 为此,本研究提出聚合小文件为局部性文件单元,将其作为一个整体进行重复数据删除. 具体而言,对于在顺序存储的小文件(例如存储在同一个文件夹下),通过聚合成局部性文件单元,将多个小文件作为一个整体进行重复数据删除,减少小文件在主索引中的记录条数,最终使小文件的内存开销得以降低.
为了改善EB算法去重率较低的缺陷,本研究提出一种多特征匹配的文件相似性检测策略. 对于一个新文件,计算所有数据块指纹,并选取具有最大、最小以及中间特征指纹值的数据块与主索引中已有记录进行匹配. 若存在匹配成功的指纹,则可判定新文件与已存储的文件存在相同的数据块,进行去重处理. 只有当所有特征都不匹配时,才判定该文件不存在重复数据块,在主索引中增加一条对该文件的描述记录,分别存储代表块特征指纹,并将文件的其他数据块存入磁盘. 根据Broder理论[5],两个文件的最小数据块指纹相同的概率为
P[min(H(F1))=min(H(F2))]=(F1∩F2)/(F1∪F2)(1)
其中, F1和F2是两个以数据块集合表示的文件; H(x)是哈希函数. 同理,两文件的最大块和中间块指纹相同的概率也有类似结论. 由式(1)可以看出,由于采用了最小块、最大块以及中间块指纹进行特征匹配,所以理论上本研究的多特征匹配策略相较于只采用最小块匹配的EB算法,在去重率方面具有更好的性能.
1.2 基于Bloom filter的磁盘数据块去重
由于EB算法对磁盘数据块去重时,需要遍历磁盘中的指纹容器,这会造成大量的I/O开销. 为此,本研究通过建立和维护一个Bloom filter,当数据块存入磁盘时,记录相应状态位; 当需要查询磁盘中是否存在相同数据块时,只需通过再次计算状态位的值即可,避免了将磁盘的指纹容器读入内存. 算法添加和查询一个元素的时间复杂度均为O(k)(k为哈希函数个数),大大提高了访问磁盘的时间效率.
在判断一个元素是否已存在时,Bloom filter会有一定的误检率(false positive rate),所以需要根据数据块集合的大小,选择合适的哈希函数个数k和位数组长度m. 误检率的计算公式为
f=(1-e-kn/m)k(2)
令p=e-kn/m, 则有ln f=k ln(1-p)=-(m/n)ln p ln(1-p), 由对称性法则可知,当p=1/2即k=(m/n)ln 2时,误检率f取得最小值. 同时,当给定误检率的上限φ时,位数组长度m需满足
m≥nlb e·lb(1/φ)=-(nln φ)/((ln 2)2)(3)
由式(3)可见,当已知文件数据块数量n以及系统的误检率上限φ时,就能相应地计算出最佳的位数组长度m以及哈希函数个数k. φ一般根据经验来确定,本研究取0.01%.
基于前文所述,改进的算法主索引结构如图1. 其中最大、最小以及中间块ID作为文件的代表ID进行多特征匹配,位数组用于Bloom filter记录磁盘数据块的存储状态,文件指针则用于连接主索引记录与磁盘指纹容器.
图1 改进的主索引结构
Fig.1 Structure of improved primary index
1.3 DBMB算法流程
DBMB算法伪代码如图2,对于给定的源文件夹和目标文件夹,图2中第4～7行算法首先对小于64 kbyte的小文件进行聚合,并采用基于内容的分块算法(content-defined chunking,CDC)[6]对文件进行变长分块,随后基于MD5信息摘要算法计算数据块指纹. 第7行算法选取最大、最小以及中间块ID(MD5值)作为文件代表块ID,并进行文件的多特征匹配. 第8～16行,若在主索引中找到该代表ID,则表明已存储了相似的文件,采用Bloom filter对磁盘中的数据块进一步匹配,并存储不同的数据块; 否则,直接将所有数据块存储.
算法:DBMB(sourceFolder, targetFolder)输入:源文件夹sourceFolder, 目标文件夹targetFolder
输出:主索引primaryIndex1. initialize primaryIndex; //初始化主索引
2. read file from sourceFolder; //读取文件
3. for all filei∈ sourceFolder do
4. if filei.size()<= 64 kbyte
5. merge small files; //聚合小文件
6. chunkFile = CDC(filei); //文件分块
7. chunkID = MD5(filei); //计算数据块的MD5值
8. find representID from chunkID;
9. if find representID from primaryIndex //找到代表块ID
10. for all chunkIDi∈chunkID do
11. if find chunkIDi
12. bloomFilter.insert(chunkIDi);
13. bin.insert(chunkIDi);
14. else//未找到代表块ID
15. bloomFilter.insert(chunkID);
16. bin.insert(chunkID);
17. write bin file to targetFolder;
18. return primaryIndex
图2 DBMB算法伪代码
Fig.2 Pseudo code of DBMB
