固定分块检测技术

基于FSP算法的块检测技术

完全文件检测不能用于文件内部的重复数据查找， 因此有研究者提出了更细粒度–块级别的重复数据检测。基于固定尺寸划分算法的相同数据块检测技术是使用固定大小的分块策略在存储系统中识别相同数据的方法
1）提供一个已经预先定义好的块的大小（该值独立于所存取的数据容），所有文件均按照这个固定的块大小进行划分。
2）每个划分好的数据块均通过哈希算法得到一个指纹值。
3）将该值与已存储的指纹值进行比对，如果检测到相同的值，则删除其代表的数据块，否则存储新的数据块。

可变分块检测技术

基于CDC(content-defined-chunking)算法的检测技术

CDC算法是应用Rabin指纹将文件切割成长度大小不一的分块策略，与固定分块策略不同的是，它对文件块进行划分的方法是基于内容的，因此数据块大小是可变的。
1)一个文件按照CDC算法分成若干数据块。CDC算法首先从头文件开始，将固定大小（互相重叠）的滑动窗口中的数据看成组成文件的各个部分。在窗口的每个位置，该窗口中数据的一个指纹被计算出来（此时的指纹是用来确定边界的），因为rabin指纹的高效性，通常使用rabin算法来计算滑动窗口的指纹。当指纹满足某个条件时，如当它的值模某个指定的整数位0时，则把此事窗口的位置作为块的边界。重复这个过程，直到整个文件数据都被分成块。

2）划分出的每个块用Hash函数计算出它的指纹值与已存储的数据块进行对比，如果检测到相同的指纹值，则删除其代表的数据块，否则存储新的数据块。

综上，根据cdc算法的特性，无论是插入还是删除一小部分字节，都只会影响一到两个块，其余的块保持不变，即cdc算法在两个相似对象之间可以检测出更多的冗余。但是，cdc算法也有一定的局限性，它划分的粒度绝大部分取决于期望块的设定。如果改值设置的较小，那么，虽然粒度较细，重复数据查找较为精确，但是额外存储每块信息的开销很大；反之,如果该值设置的较大，则粒度过粗，重复数据删除的效果不好。所有如何权衡精确查找和额外开销是一个难点。

如图：设置两个整数D和r,且r<D,设某时间点，滑动窗口计算出的指纹值是f,则基准点为f mod D=r，如果f mod D = r,则此时为块边界，得到块边界后，计算整个块的hash值，再去与先前存储过的块hash进行比对，若hash已经存在，则删除这个块，如果hash不存在，则存储下来。

基于fingerdiff算法的检测技术

核心思想是将没有变化的块尽可能的合并，以减少各个数据块的元数据占用的存储空间。
1）一个文件先用cdc算法进行块划分，这些块称为子块
2）每个子块按照fingerdiff设置的最大子块数进行合并成超级块
3）每个超级块用hash计算出指纹，然后对比已经存储的超级块的指纹值，如果检测到相同的指纹值，则删除对应的数据块，否则将超级块分割成子块后存储。

CDC和fingerdiff存在两个不足之处：（1）在可变分块检测过程中，对于一个文件中间较小的改变，效果不好；（2）两种技术的数据块划分都是根据内容可变的，但该值很大程度上取决于期望块大小的设定，而期望块大小的选择依赖于文件相似程度和文件修改的位置，这对相同数据检测的性能影响很大。

滑动块检测技术

滑动块检测技术结合了固定块大小检测技术和可变块大小检测技术的优点，块大小固定，管理简单。
1）文件用rsync求和校验（checksum）函数和固定快大小的滑动窗口来计算文件对象的每个重叠快的求和校验值（与CDC的rabin指纹不同，校验和就是用来第一次校验的，滑动块检测的块固定不需要确定边界）
2）对于每个块，比较求和校验值和先前存储的值进行匹配
3）若匹配，则用更严格的hash算法对块进行计算，与之前存储的值进行比较，从而进行冗余检测。如果检测到数据冗余，将其记录后，滑动窗口越过这个冗余块继续前移，而且先前已经被划分的块和最近被检测到冗余之前的这个碎片需要被记录斌且存储。
4）如果求和校验或哈希值不匹配，则滑动窗口继续前移，如果滑动窗口已经移动了一个块大小的距离，但是仍然无法匹配到任何已经被存储的块，则需要对这个块进行求和校验和hash计算，并存储在各自表中，用作以后块的比较对象。

滑动块检测技术的特点是对插入问题和删除问题处理高效，并能检测到更多的冗余数据。
1）插入问题：如果一小部分字节被插入到一个对象中，则只有周围的块会改变，其他的块仍被识别出来并被匹配，并且一个长度等于插入字节数的碎片会产生被记录下来。
2）删除问题：删除一小部分字节也会产生一个长度等于块大小减去被删去部分字节长度的碎片，其他块不受影响。
但是滑动块检测技术也存在一个不足：在插入和删除问题中都会引入碎片，如何能够准确是改变的数据，不影响匹配数据块，从而少产生二外的碎片将是一个研究难点。