论文部分内容阅读
[摘 要] 重复数据删除技术主要有相同数据的检测删除技术和相似数据的检测删除技术两种类型。本文主要研究介绍了相同数据的几种主流检测删除技术。
[关键词] 重复数据 删除 分块检测
一、前言
随着科学技术和社会的发展，社会数字信息量成指数化增长，数据信息占用的空间也越来越大；存储设备也得到快速发展如硬盘，由以前的GB级跨越到了TB级别。在许多行业的应用中，存储系统的容量也由数百GB发展到了数百TB甚至数PB了。随着数据量的指数化增长，也面临一个问题，企业应用中对数据的备份和恢复时间点越多，意味着数据保存成本的上升和数据空间以及能耗的大量消耗。已有研究发现，目前应用中数据的冗余程度达到了60%。如果能大量消除冗余数据，那就意味着，存储空间的和时间的消耗大幅的减少，数据存储成本的大幅降低。于是重复数据删除技术也就显得越来越迫切需要了。
二、重复数据删除的关键技术
重复数据删除技术删除流程一般情况下是这样的：（1）对数据文件进行分割形成一组数据块，对每个数据块计算数据指纹，（2）对指纹进行Hash查找，找到指纹匹配的数据块则表示该数据块为重复数据块，（3）存储数据块索引号，仅对新的唯一数据块进行存储并创建相关元信息，（4）对物理文件在存储系统中建立对应的一个逻辑表示，即由哪些数据块逻辑序列组成。当我们进行读取文件时，先读取逻辑文件，然后根据数据块逻辑序列，从存储系统中取出相应数据块，还原成物理文件。从此可以知道，重复数据删除技术的关键技术主要包括对文件的数据块切分、数据块的指纹计算和数据块的检索。
1）文件数据块切分
重复数据删除技术分为文件级和数据块级的。文件级，就是删除单一存储的重复文件实例；数据块级的删除重复的数据块，可以达到4KB-24KB之间。显然，数据块级的可以降低很多数据的重复率。目前主流的重复数据删除技术产品都是数据块级的。数据分块算法主要有三种，即定长切分、CDC切分和滑动块切分。
定长分块算法采用预先定义块大小对文件进行切分。定长分块算法的优点是简单、性能高，但它对数据插入和删除非常敏感，处理十分低效，不能根据内容变化作调整和优化。
CDC算法是一種变长分块算法，它使用数据指纹将文件分割成长度大小不等的分块策略。与定长分块算法不同之处是基于文件内容进行数据块切分的，因此数据块大小是可变化的。CDC算法可能会出现问题，如果指纹条件不能满足，块边界不确定，就会出现数据块过大，实现中一般限定数据块的大小，设定上下界限。CDC算法对文件内容变化不敏感，插入删除数据只影响较少的数据块，其它不影响。但CDC算法也有缺陷，数据块大小的确定困难，数据块太小则开销太大，数据块过大则重复数据删除效果不佳。
滑动块算法结合了定长切分和CDC切分的优点，块大小固定。它对定长数据块计算弱强校验值，两者都匹配则认为是一个数据块边界。该数据块前的数据碎片则是一个不定长的数据块。滑动块算法对插入删除问题处理高效并能够检测比CDC更多的冗余数据，但它是容易产生数据碎片。
2)数据块指纹计算
数据指纹是数据块的特征，每个唯一数据块具有唯一的数据指纹，不同数据块具有不同数据指纹。数据块本身较大，数据指纹就是用较小的数据来表示和区别不同数据块。数据指纹是对数据块内容进行特定数学运算获取，目前一般使用Hash函数来计算，比如MD5、SHA1、SHA-256、SHA-512等。不过遗憾的是目前这些指纹函数都存在碰撞问题，即不同数据块可能产生相同的数据指纹。只是MD5和SHA系列HASH函数的碰撞概率非常低。
3)数据块检索
对于大存储容量的重复数据删除系统来说，数据块数量将会非常庞大，在这样一个大的数据指纹库中检索，性能就会成为瓶颈。信息检索方法有很多种，常用的相同数据检测技术有：
◆完全文件检测技术
完全文件检测技术，是以整个文件做为数据块进行hash计算数据指纹，然后将该值到数据指纹库中的值进行比较，如果找到了相同的值，则不存储这个文件，而使用指针替换该文件，否则存储新的文件。研究发现，hash算法计算出来的hash值可以唯一表示特定的数据，通过hash计算出固定长度的值，通过比较这些值可以判断数据的重复性。
◆基于固定尺寸划分算法的块检测技术
基于固定尺寸划分算法的块检测技术是在固定大小的数据块的存储系统中检测相同数据的方法。该方法首先定义块的固定大小，然后对划分好的每个数据块进行MD5或SHA1等hash算法计算数据指纹值，最后，将该值与存储的指纹库里的值进行比较，检测到相同值就删除该数据块，否则就存储数据块。基于固定尺寸划分算法的重复数据块检测技术具有缩减存储空间，减少网络传输的数据量的特点同时还可以达到很高的处理速度。
◆可变分块检测技术
可变分块检测技术是基于文件内容对文件进行划分数据块，因此数据块是可变长度的。在数据块划分完毕后，使用hash函数（MD5或SHA-1）对数据块进行指纹计算，得出来的值与存储在hash表中的指纹值进行比较，如果相同则删除对应数据块，否则存储作为新数据块存储，并将该指纹值存入指纹hash表。该检测技术在插入删除一小部分字节内容时只影响很少数据块，其余的不收影响，因此该检测方法可以检测出相似对象中的更多的重复数据。
◆滑动块检测技术
滑动块检测技术是基于滑动块技术的重复数据检测方法。其过程一般分为4步：:（1）计算文件对象的每个重叠块的求和校验值。（2）对每个块进行求和校验值与之前存储的值做比较。（3）)若找到相同的就用SHA-1算法进行hash指纹计算然后再与之前存储的值比较，来做重复数据检测。检测到重复数据就将其记录，然后滑动窗口越过该重复块继续前移。再对先前被划分的块和刚检测到的重复数据块之前碎片做记录并且存储。（4）若求和校验值或hash值不重复，则滑动窗口继续前移。如果滑动窗口已移动一个数据块大小的距离仍然无法匹配到任何已经被存储的块就对该块做求和校验和SHA-1的hash计算然后存储在各自的表中。
三、总结
本文简要讨论了目前的几种重复数据删除技术。重复数据删除技术它是目前一种主流热门的存储技术，可以有效的优化存储容量。它对数据进行计算检测删除重复的数据，只保留其中一份来消除冗余数据。这样就很大程度上减少了对物理存储空间的消耗，满足日益增长的数据存储需求。这种技术在现实应用中必将越来越广泛，并且给我们带来越来越多的利益如：（1）满足投资回报率/总持有成本的需求。（2）有效控制数据量的指数增长。（3）提高存储空间的使用效率。（4）降低存储成本和管理成本。（5）降低数据传输带宽。（6）降低维护成本（如场地、能耗等）等等。■
[关键词] 重复数据 删除 分块检测
一、前言
随着科学技术和社会的发展，社会数字信息量成指数化增长，数据信息占用的空间也越来越大；存储设备也得到快速发展如硬盘，由以前的GB级跨越到了TB级别。在许多行业的应用中，存储系统的容量也由数百GB发展到了数百TB甚至数PB了。随着数据量的指数化增长，也面临一个问题，企业应用中对数据的备份和恢复时间点越多，意味着数据保存成本的上升和数据空间以及能耗的大量消耗。已有研究发现，目前应用中数据的冗余程度达到了60%。如果能大量消除冗余数据，那就意味着，存储空间的和时间的消耗大幅的减少，数据存储成本的大幅降低。于是重复数据删除技术也就显得越来越迫切需要了。
二、重复数据删除的关键技术
重复数据删除技术删除流程一般情况下是这样的：（1）对数据文件进行分割形成一组数据块，对每个数据块计算数据指纹，（2）对指纹进行Hash查找，找到指纹匹配的数据块则表示该数据块为重复数据块，（3）存储数据块索引号，仅对新的唯一数据块进行存储并创建相关元信息，（4）对物理文件在存储系统中建立对应的一个逻辑表示，即由哪些数据块逻辑序列组成。当我们进行读取文件时，先读取逻辑文件，然后根据数据块逻辑序列，从存储系统中取出相应数据块，还原成物理文件。从此可以知道，重复数据删除技术的关键技术主要包括对文件的数据块切分、数据块的指纹计算和数据块的检索。
1）文件数据块切分
重复数据删除技术分为文件级和数据块级的。文件级，就是删除单一存储的重复文件实例；数据块级的删除重复的数据块，可以达到4KB-24KB之间。显然，数据块级的可以降低很多数据的重复率。目前主流的重复数据删除技术产品都是数据块级的。数据分块算法主要有三种，即定长切分、CDC切分和滑动块切分。
定长分块算法采用预先定义块大小对文件进行切分。定长分块算法的优点是简单、性能高，但它对数据插入和删除非常敏感，处理十分低效，不能根据内容变化作调整和优化。
CDC算法是一種变长分块算法，它使用数据指纹将文件分割成长度大小不等的分块策略。与定长分块算法不同之处是基于文件内容进行数据块切分的，因此数据块大小是可变化的。CDC算法可能会出现问题，如果指纹条件不能满足，块边界不确定，就会出现数据块过大，实现中一般限定数据块的大小，设定上下界限。CDC算法对文件内容变化不敏感，插入删除数据只影响较少的数据块，其它不影响。但CDC算法也有缺陷，数据块大小的确定困难，数据块太小则开销太大，数据块过大则重复数据删除效果不佳。
滑动块算法结合了定长切分和CDC切分的优点，块大小固定。它对定长数据块计算弱强校验值，两者都匹配则认为是一个数据块边界。该数据块前的数据碎片则是一个不定长的数据块。滑动块算法对插入删除问题处理高效并能够检测比CDC更多的冗余数据，但它是容易产生数据碎片。
2)数据块指纹计算
数据指纹是数据块的特征，每个唯一数据块具有唯一的数据指纹，不同数据块具有不同数据指纹。数据块本身较大，数据指纹就是用较小的数据来表示和区别不同数据块。数据指纹是对数据块内容进行特定数学运算获取，目前一般使用Hash函数来计算，比如MD5、SHA1、SHA-256、SHA-512等。不过遗憾的是目前这些指纹函数都存在碰撞问题，即不同数据块可能产生相同的数据指纹。只是MD5和SHA系列HASH函数的碰撞概率非常低。
3)数据块检索
对于大存储容量的重复数据删除系统来说，数据块数量将会非常庞大，在这样一个大的数据指纹库中检索，性能就会成为瓶颈。信息检索方法有很多种，常用的相同数据检测技术有：
◆完全文件检测技术
完全文件检测技术，是以整个文件做为数据块进行hash计算数据指纹，然后将该值到数据指纹库中的值进行比较，如果找到了相同的值，则不存储这个文件，而使用指针替换该文件，否则存储新的文件。研究发现，hash算法计算出来的hash值可以唯一表示特定的数据，通过hash计算出固定长度的值，通过比较这些值可以判断数据的重复性。
◆基于固定尺寸划分算法的块检测技术
基于固定尺寸划分算法的块检测技术是在固定大小的数据块的存储系统中检测相同数据的方法。该方法首先定义块的固定大小，然后对划分好的每个数据块进行MD5或SHA1等hash算法计算数据指纹值，最后，将该值与存储的指纹库里的值进行比较，检测到相同值就删除该数据块，否则就存储数据块。基于固定尺寸划分算法的重复数据块检测技术具有缩减存储空间，减少网络传输的数据量的特点同时还可以达到很高的处理速度。
◆可变分块检测技术
可变分块检测技术是基于文件内容对文件进行划分数据块，因此数据块是可变长度的。在数据块划分完毕后，使用hash函数（MD5或SHA-1）对数据块进行指纹计算，得出来的值与存储在hash表中的指纹值进行比较，如果相同则删除对应数据块，否则存储作为新数据块存储，并将该指纹值存入指纹hash表。该检测技术在插入删除一小部分字节内容时只影响很少数据块，其余的不收影响，因此该检测方法可以检测出相似对象中的更多的重复数据。
◆滑动块检测技术
滑动块检测技术是基于滑动块技术的重复数据检测方法。其过程一般分为4步：:（1）计算文件对象的每个重叠块的求和校验值。（2）对每个块进行求和校验值与之前存储的值做比较。（3）)若找到相同的就用SHA-1算法进行hash指纹计算然后再与之前存储的值比较，来做重复数据检测。检测到重复数据就将其记录，然后滑动窗口越过该重复块继续前移。再对先前被划分的块和刚检测到的重复数据块之前碎片做记录并且存储。（4）若求和校验值或hash值不重复，则滑动窗口继续前移。如果滑动窗口已移动一个数据块大小的距离仍然无法匹配到任何已经被存储的块就对该块做求和校验和SHA-1的hash计算然后存储在各自的表中。
三、总结
本文简要讨论了目前的几种重复数据删除技术。重复数据删除技术它是目前一种主流热门的存储技术，可以有效的优化存储容量。它对数据进行计算检测删除重复的数据，只保留其中一份来消除冗余数据。这样就很大程度上减少了对物理存储空间的消耗，满足日益增长的数据存储需求。这种技术在现实应用中必将越来越广泛，并且给我们带来越来越多的利益如：（1）满足投资回报率/总持有成本的需求。（2）有效控制数据量的指数增长。（3）提高存储空间的使用效率。（4）降低存储成本和管理成本。（5）降低数据传输带宽。（6）降低维护成本（如场地、能耗等）等等。■