一种可扩展的重复数据检测方法

摘要

一种可扩展的重复数据检测方法，属于计算机存储技术领域，解决现有重复数据检测方法中存储容量无法高效扩展的问题，以适应存储需求扩大，重删系统面临升级换代的现状。本发明包括分块处理、指纹提取、布隆过滤器检索、指纹子集表检索、未满布隆过滤器判断、新指纹标记、布隆过滤器数量判断以及布隆过滤器阵列扩展步骤。本发明采用布隆过滤器阵列来检索指纹数据，可快速定位检索范围，提高检索效率，实现重复数据的检测，具有高扩展性、高查询性能、支持元素定位、可控制误判率，有效减少内存开销。布隆过滤器阵列由同构的一系列布隆过滤器构成，只需提供误判率ε’及预估检索的指纹总数量n_max，就能计算出需要的布隆过滤器的数量及哈希函数的个数。

主权项

一种可扩展的重复数据检测方法，包括分块处理步骤、指纹提取步骤、布隆过滤器检索步骤、指纹子集表检索步骤、未满布隆过滤器判断步骤、新指纹标记步骤、布隆过滤器数量判断步骤和布隆过滤器阵列扩展步骤，其特征在于：(1)分块处理步骤：将用户需要备份或存储的文件分成数据块，对文件的所有数据块统一编号，数据块最大编号P0为正整数；(2)指纹提取步骤：提取每个数据块的指纹，将指纹按数据块编号形成指纹列表；(3)布隆过滤器检索步骤，包括下述子步骤：(3.1)设置布隆过滤器最大数量r≥1；设置布隆过滤器阵列可容纳元素数量n_max，n_max大于外存储系统最大存储容量，根据系统的存储需求确定；设置布隆过滤器阵列总体误判上限ε′，0.000001<ε′<0.01，ε′越小，系统开销越大，反之则误判率增大；设置布隆过滤器扩展系数t≥2；置布隆过滤器编号变量T＝0，置数据块编号变量P＝1；置新位向量长度m’＝0，置临时位向量长度m”＝0；(3.2)从指纹列表中取出编号为P的指纹X；(3.3)判断外存储器中是否已存在布隆过滤器，是则将外存储器中的布隆过滤器及其对应的指纹子集表读入内存，转子步骤(3.5)，否则进行子步骤(3.4)；(3.4)置单个设计容量n＝n_max/r，计算布隆过滤器的位向量长度m和哈希函数数量k：式中，单个误判率上限ε＝1‑(1‑ε′)^1/r；符号表示大于ln2×(m/n)结果的最小整数；在内存中，通过参数m、k创建一个布隆过滤器及其对应的指纹子集表，并置该布隆过滤器的未满标记为“未满”；所述布隆过滤器，包括位向量和k个独立的哈希函数，所述位向量为长度m个bit的一维向量，所述指纹子集表的最大长度为n个指纹空间，每个指纹空间占据16或20字节，k＜m，n＜m；对该布隆过滤器赋予编号T+1，进行子步骤(3.5)；(3.5)在内存中将每g个布隆过滤器归为一个布隆过滤器组，如果布隆过滤器的数量不能被g整除，则将最后不满g个的布隆过滤器归为一个布隆过滤器组，对各布隆过滤器组顺序赋予从1开始的组号，并将各布隆过滤器组的扩展标记均置为“无”，转子步骤(3.6)；g＝2^5～8；(3.6)创建标志位向量V[g]，V[g]为长度为g个bit的一维向量，V[g]中的每个bit顺序对应一个布隆过滤器组中各布隆过滤器的编号；置布隆过滤器组号变量M＝1；(3.7)将V[g]中各个bit初始化为‘1’；(3.8)判断第M组布隆过滤器组的扩展标记是否为“无”，是则置m”＝m，进行子步骤(3.9)，否则置m”＝m’，再进行子步骤(3.9)；(3.9)选取第M个布隆过滤器组，根据m”计算指纹X的k个哈希值h₁(X),h₂(X),…,h_k(X)，其中，h_i(X)的值域为{1,2,…,m”}，1≤i≤k；将这k个哈希值作为偏移量提取第M个布隆过滤器组中对应的k个位组，若第M个布隆过滤器组中布隆过滤器的个数少于g，则在提取该k个位组后，将k个位组中缺失的位均补为0，所述k个位组的各位组依次与标志位向量V[g]按位对应进行“与”运算，最终结果写回标志位向量V[g]；(3.10)判断V[g]的各位是否全为“零”，是则进行子步骤(3.11)，否则进行子步骤(3.12)；(3.11)判断是否是则表明指纹X为新指纹，转步骤(5)，否则，置M＝M+1，转子步骤(3.7)；(3.12)判断指纹X为可能重复指纹，查找V[g]中首个值为‘1’的bit在V[g]中的位置，转步骤(4)；(4)指纹子集表检索步骤：包括下述子步骤：(4.1)以所述子步骤(3.12)查找的位置作为对应的布隆过滤器编号，进一步查找该编号的布隆过滤器对应的指纹子集表，判断指纹子集表中是否存在指纹X，是则进行子步骤(4.2)，否则转子步骤(4.4)；(4.2)指纹X为重复指纹，指纹X对应的数据块为重复数据，将指纹X移动到指纹子集表的头部，置P＝P+1，判断是否P>P0，是则进行子步骤(4.3)，否则转子步骤(3.2)；(4.3)将内存中的所有布隆过滤器的数据及对应指纹子集表的数据写入外存储器，整个处理过程结束；(4.4)表明该编号的布隆过滤器发生误判，对误判进行计数，判断是否是则表明指纹X为新指纹，转步骤(5)，否则置M＝M+1，转子步骤(3.7)；(5)未满布隆过滤器判断步骤，按照布隆过滤器的编号顺序查找是否存在未满的布隆过滤器BF_t，1≤t≤r，是则转步骤(6)，否则转步骤(7)；(6)新指纹标记步骤，包括下述子步骤：(6.1)判断该布隆过滤器所属布隆过滤器组的扩展标记是否为“无”，是则置m”＝m，进行子步骤(6.2)，否则置m”＝m’，再进行子步骤(6.2)；(6.2)根据m”计算所述指纹X的k个哈希值h₁(X),h₂(X),…,h_k(X)；(6.3)将所述布隆过滤器BF_t位向量的第一位作为起始点，将所述k个哈希值h₁(X),h₂(X),…,h_k(X)作为偏移量，得到位向量中对应的k个位，将这k个位置为‘1’，完成对指纹X的标记；(6.4)查找布隆过滤器BF_t对应的指纹子集表，将指纹X插入到指纹子集表的头部；(6.5)判断布隆过滤器是否装满，是则置该布隆过滤器未满标记为“已满”；(6.6)置P＝P+1，判断是否P>P0，是则进行子步骤(4.3)，否则转子步骤(3.2)；(7)布隆过滤器数量判断步骤，包括下述子步骤：(7.1)判断是否布隆过滤器编号T＜r，是则进行子步骤(7.2)，否则需对布隆过滤器阵列进行扩展，转步骤(8)；(7.2)创建新的布隆过滤器及新的指纹子集表；在内存中，通过参数m、k创建一个布隆过滤器及其对应的指纹子集表，并置该布隆过滤器的未满标记为“未满”；对该布隆过滤器赋予编号T+1，转步骤(5)；(8)布隆过滤器阵列扩展步骤，包括下述子步骤：(8.1)置布隆过滤器临时组号变量M’＝1；(8.2)选择第M’个布隆过滤器组,判断其扩展标记是否为“无”，是则转子步骤(8.5)，否则进行子步骤(8.3)；(8.3)置M’＝M’+1，判断是否是则转子步骤(8.2)，否则进行子步骤(8.4)；(8.4)将各布隆过滤器组的扩展标记置为“无”，置n＝t×n，置m’＝m，转子步骤(8.1)；(8.5)以新设计容量n’＝t×n，误判率上限ε不变，哈希函数数量k不变，计算布隆过滤器的新位向量长度m'＝log₂e×log₂(1/ε)×n'，对组内每个布隆过滤器进行重构，同时，以新设计容量n’扩大布隆过滤器对应的指纹子集表的容量，将该布隆过滤器组中所有的布隆过滤器未满标记置为“未满”，将该布隆过滤器组的扩展标记置为“有”；转步骤(5)。