高性能计算技术41 因此元数据量比以上两种方法都要多置信息 的校验和与指纹值,以及与它们对应的位置 采用 B loom Filter技术,对索引表进行全局抽象。 B loom Filter占用空间小,可以常驻内存,插入和查 5)基于应用的分块 询时间都是常数。对于 B loom filter判断为不存在的 以上的几种数据划分方法都是通用的,没有指纹,可以直接认为其在索引表中也不存在;对于 考虑到数据的语义。如果考虑到不同文件格式的差 Bloom filter判断为存在的指纹,需访问索引表进行进 异,为不同的文件类型设计专用的数据划分方法 一步验证。采用 Bloom filter有效的避免了对新指纹进 就能够获取更高的数据缩减率。 ADMAD眵是一个基行査询时的磁盘访问。 DBLK DE主存储系统提出了 于应用的去重归档系统。 ADMAD对于文件的划分是多层 Bloom filter,以使用少量内存存储尽量多的索引 与应用相关的,即理解文件语义的。它利用文件的信息 元数据,对不同数据类型的文件自动选择与之适应 2)利用数据流重复局部性进行优化 的分块策略,并针对MP3,FLV,HTML和 Em ail等文 在传统的磁盘到磁盘的备份中,备份客户端将 件类型设计了不同的分块策略,实验表明基于应用目录树合并成大文件,或者是客户端产生满足虚拟 分块相对于基于内容分块能够获得更高的数据缩减磁带库协议的文件0。以备份操作为例,第一次备份 率B。 中同一个文件夹下有B、C、D这三个文件。假设按照 6)Delt编码技术 B、C、D的顺序进行处理和存储,那么在后续的备份 Del编码是以字节为粒度进行重复数据删除的中,有极大的可能性B的后面接着C、D文件。在文件 技术。采用 shingling、 B lom Filter等相似性检测技术的内部也存在着重复局部性,一个文件可能包含成 检测数据的相似性:然后对相似度超过某个阈值的千上万个数据块,即使文件有修改,这些数据块在 数据采用 Delta编码的方法,存储一个块相对于基准后续的备份中也有极大的可能性一起出现b。数据 块的变化部分。由于Del编码进行数据比对的粒流的重复局部性在这种传统的以任务为粒度的备份 度最小,其数据缩减率最高。Dela编码可以作为重中表现得较为明显,对于新型的备份操作,即以单 复块检测技术的补充,对于检测为相似的数据块进个文件为粒度的备份操作,或者是增量备份,这种 行进一步的编码。但是块的重建会降低系统读取数局部性表现较弱 据的性能。 数据流的重复局部性对于设计高效的去重系统 去重系统的数据缩减率与几个因素有关:第有如下启发。在上面的例子中,如果将B、C、D这 数据本身的冗余程度:第二,数据划分策略 个文件的索引项连续存放,那么在查询B文件块 合适的边界点能够识别出更多的冗余数据块:第指纹的时候,可以连续加载一大段索引表到内存 ,数据块的平均大小,更小的数据块意味着检测这样,对于C和D的指纹查找也极有可能在缓存中命 重复的粒度更细,但同时意味着更高的元数据开销中,减少了随机访问磁盘的次数。目前利用数据流 和计算开销。在以上提出的不同的数据划分算法的重复局部性减轻磁盘访问瓶颈的系统有很多,以 中,WFC和FSC主要被应用于主存储中,而在二级存 EM C Data dom ain系列产品的DDFS和HPD2D产品的 储的产品和研究中几乎都用CDC或者其改进算法。 Sparse Indexing技术为代表 DDFS采用了摘要向量,SBL技术,以及保持局 33减轻磁盘索引瓶颈 部性的缓存策略LPC,使査询过程中的访问磁盘操作 指纹值查询是去重检测过程中关键的一步 减少了99%。DDFS将逻辑上连续的数据块在磁盘上 在数据量小的时候,整个索引表可以放在内存中 连续存放,其对应的索引项也连续存放,以保持数 只要索引表在内存中采用的组织方式合理,查询时据流的重复局部性,称为SISL。SISL配合高命中率的 间就可以控制在常数范围,并且实现全局去重。但缓存LPC,有效地减少了代价 是,索引表会随着数据量的增加而线性增长。对于 HP的D2D备份系统采用基于数据流局部性的稀 8TB的数据,以4KB大小分块,每个索引项40字节 疏索引技术。 Sparse Indexing将到达的数据流划分成 仅指纹值就要占用80GB的空间。当索引表大到无法相对较大的段,每个段只相对于最为相似的几个段 装到内存中时,查询过程就要进行磁盘访问,这种做重复检测。当两个段有多个样本相似的时候,认 频繁的随机访问过程成为去重过程的瓶颈 为这两个段相似。这种方法减少了指纹查询的比较 )利用 Bloom filter进行优化 范围,是一种局部去重的方法。在获得相同数据缩 Ⅴent采用索引缓存和块缓存来减少磁盘访问减量的情况下,采用 Sparse Indexing技术相对DDFS内 次数,但是由于哈希值分布的随机性,缓存命中率存用量更小。 非常低。 Data dom ain5、 HYDRA stor、 Foundation0 3)利用文件相似性进行L0优化高性能计算技术 41 的校验和与指纹值，以及与它们对应的位置信息， 因此元数据量比以上两种方法都要多[17]。 5) 基于应用的分块 以上的几种数据划分方法都是通用的，没有 考虑到数据的语义。如果考虑到不同文件格式的差 异，为不同的文件类型设计专用的数据划分方法， 就能够获取更高的数据缩减率。ADMAD[9]是一个基 于应用的去重归档系统。ADMAD对于文件的划分是 与应用相关的，即理解文件语义的。它利用文件的 元数据，对不同数据类型的文件自动选择与之适应 的分块策略，并针对MP3，FLV，HTML和Email等文 件类型设计了不同的分块策略，实验表明基于应用 分块相对于基于内容分块能够获得更高的数据缩减 率[9]。 6) Delta编码技术 Delta编码是以字节为粒度进行重复数据删除的 技术。采用shingling、Bloom Filter等相似性检测技术 检测数据的相似性；然后对相似度超过某个阈值的 数据采用Delta编码的方法，存储一个块相对于基准 块的变化部分[11]。由于Delta编码进行数据比对的粒 度最小，其数据缩减率最高。Delta编码可以作为重 复块检测技术的补充，对于检测为相似的数据块进 行进一步的编码。但是块的重建会降低系统读取数 据的性能。 去重系统的数据缩减率与几个因素有关：第 一，数据本身的冗余程度；第二，数据划分策略， 合适的边界点能够识别出更多的冗余数据块；第 三，数据块的平均大小，更小的数据块意味着检测 重复的粒度更细，但同时意味着更高的元数据开销 和计算开销。在以上提出的不同的数据划分算法 中，WFC和FSC主要被应用于主存储中，而在二级存 储的产品和研究中几乎都用CDC或者其改进算法。 3.3 减轻磁盘索引瓶颈 指纹值查询是去重检测过程中关键的一步。 在数据量小的时候，整个索引表可以放在内存中， 只要索引表在内存中采用的组织方式合理，查询时 间就可以控制在常数范围，并且实现全局去重。但 是，索引表会随着数据量的增加而线性增长。对于 8TB的数据，以4KB大小分块，每个索引项40字节， 仅指纹值就要占用80GB的空间。当索引表大到无法 装到内存中时，查询过程就要进行磁盘访问，这种 频繁的随机访问过程成为去重过程的瓶颈。 1) 利用Bloom Filter进行优化 Venti[14]采用索引缓存和块缓存来减少磁盘访问 次数，但是由于哈希值分布的随机性，缓存命中率 非常低。Data Domain[5]、HYDRAstor[7]、Foundation[40] 采用Bloom Filter[46]技术，对索引表进行全局抽象。 Bloom Filter占用空间小，可以常驻内存，插入和查 询时间都是常数。对于Bloom Filter判断为不存在的 指纹，可以直接认为其在索引表中也不存在；对于 Bloom Filter判断为存在的指纹，需访问索引表进行进 一步验证。采用Bloom Filter有效的避免了对新指纹进 行查询时的磁盘访问[5]。DBLK[16]主存储系统提出了 多层Bloom Filter，以使用少量内存存储尽量多的索引 信息。 2) 利用数据流重复局部性进行I/O优化 在传统的磁盘到磁盘的备份中，备份客户端将 目录树合并成大文件，或者是客户端产生满足虚拟 磁带库协议的文件[19]。以备份操作为例，第一次备份 中同一个文件夹下有B、C、D这三个文件。假设按照 B、C、D的顺序进行处理和存储，那么在后续的备份 中，有极大的可能性B的后面接着C、D文件。在文件 的内部也存在着重复局部性，一个文件可能包含成 千上万个数据块，即使文件有修改，这些数据块在 后续的备份中也有极大的可能性一起出现[5][6]。数据 流的重复局部性在这种传统的以任务为粒度的备份 中表现得较为明显，对于新型的备份操作，即以单 个文件为粒度的备份操作，或者是增量备份，这种 局部性表现较弱[19]。 数据流的重复局部性对于设计高效的去重系统 有如下启发。在上面的例子中，如果将B、C、D这 三个文件的索引项连续存放，那么在查询B文件块 指纹的时候，可以连续加载一大段索引表到内存。 这样，对于C和D的指纹查找也极有可能在缓存中命 中，减少了随机访问磁盘的次数。目前利用数据流 的重复局部性减轻磁盘访问瓶颈的系统有很多，以 EMC Data Domain系列产品的DDFS[5]和HP D2D产品的 Sparse Indexing[6]技术为代表。 DDFS采用了摘要向量，SISL技术，以及保持局 部性的缓存策略LPC，使查询过程中的访问磁盘操作 减少了99%[5]。DDFS将逻辑上连续的数据块在磁盘上 连续存放，其对应的索引项也连续存放，以保持数 据流的重复局部性，称为SISL。SISL配合高命中率的 缓存LPC，有效地减少了I/O代价。 HP的D2D备份系统采用基于数据流局部性的稀 疏索引技术。Sparse Indexing[6]将到达的数据流划分成 相对较大的段，每个段只相对于最为相似的几个段 做重复检测。当两个段有多个样本相似的时候，认 为这两个段相似。这种方法减少了指纹查询的比较 范围，是一种局部去重的方法。在获得相同数据缩 减量的情况下，采用Sparse Indexing技术相对DDFS内 存用量更小。 3) 利用文件相似性进行I/O优化