38<性能计算发展与应用2年第三总第四十人朋 额外产生的元数据s之和。其中,元数据s包括两部2.2重复检测 分:记录文件对应哈希序列的元数据和索引表元数 重复检测这一过程非常关键。它是将计算好 据。对于同一个数据集,越大,重复数据删除效果的各指纹值与己存储的数据的指纹值进行比较的过 越好 程。去重系统需要维持一张索引表以供查询,其中 重复数据删除系统的吞吐率也是一个重要的衡每个索引项记录了一个指纹以及该指纹对应的数据 量指标,这里说的吞吐率是写吞吐率。吞吐率衡量内容在磁盘上的存储位置和引用次数。对于数据量 了单位时间内被重复数据删除系统所处理和存储的大的系统,完整的索引表需要存储在磁盘上,加载 逻辑数据量。相比于一般的存储系统,重复数据删到内存中的索引项通常以散列表或者B+树的形式进 除系统可能会因为引入的额外计算和查询过程造成行组织,以加快查询速度。在内存查询不命中时需 吞吐率的降低,但是也有可能因为减少了大量重复要进行随机的磁盘访问,因此在数据量大的时候, 数据的实际读写过程而使吞吐率增大。目前有很多重复检测过程是去重系统的性能瓶颈。 研究专注于提高系统的吞吐率b9。 通过查询索引表,可以获取指纹值是否已经存 重复数据删除系统的读性能可以用单位时间在的信息。对于已经存在的指纹值,不再进行对应 内从去重系统读取的数据量来度量。由于数据块共数据内容的存储,只是更新索引项中数据块的引用 享,逻辑上连续的数据经过去重后在物理上不再连次数:对于新的指纹值,进行数据存储和元数据更 续,因此重复数据删除系统的数据读取速度比一般新。在冗余消除的过程中,有的时候为了降低数据 的存储系统要差。对于二级存储,读取速度即恢复块分布的碎片化程度,会进行选择性的消除,以保 速度,决定了系统是否能在要求的恢复时间窗口完持数据恢复性能2。 成数据恢复:对于主存储系统则决定了系统的读延 。针对提高恢复速度也开展了大量研究u5m。2.3数据存储 对于上一步重复检测判断为不存在的指纹,需 2.重复数据删除的一般过程 将其数据内容和元数据信息写入磁盘。元数据信息 重复数据删除的一般执行过程可以划分成 即一个索引项的全部内容,包括指纹值、数据块位 个阶段。首先对接收到的数据流进行划分和指纹计置、引用次数。如果以数据块或者索引项为单位进 算,然后对获得的指纹值进行重复检测,最后根据行写入,则会引起大量的随机I 检测的结果进行相应的数据存储或者元数据更新操 在一些利用数据流的重复局部性进行性能优化 的系统中,数据内容和元数据以 con tainer为单位进行 存储和读写B。 Con taine是一个自治的单位,大小 2.1数据划分和指纹计算 般能够存放一千到几千个数据块及它们对应的元 在这一阶段,首先根据预先设定好的策略对数数据。经检测为不重复的数据,先写入内存中为该 据进行划分,然后对划分好的数据单元(可以是文数据流开放的 con tainer缓存中,如果 con tainer已满则 件、或者数据块)分别计算指纹,最后记录构成每将其整个写到磁盘中。恢复过程中也是以 con tainer为 个文件的指纹序列。 单位加载数据和元数据。这么做的目的有四:第 指纹是指利用抗冲突特性好的哈希算法(如,充当写缓存,避免了过多的磁盘随机I0:第 SHA-1,MD5)对数据内容计算得到的一个固定长二, con tainer中的数据和元数据都维持了数据流的逻 度的值,该值可以用来唯一标识数据内容。在判别辑顺序,存在数据流重复局部性:第三,在读的时 数据单元内容是否相同的时候,采用逐字节的方法候以 con tainer为单位进行预取,可以提高缓存命中 本身比对过程慢,而且需要先将原先存储的内容读率;第四,合理的 Icon taine大小可以使底层的RAD达 出,对系统吞吐率影响非常大師。因此,重复数据删 到全条带写。 除系统通过指纹来判断数据内容的相同与否。 对于一个EB级的存储系统,采用160位的SHA 3.重复数据删除技术研究现状 1算法,发生哈希冲突的概率在10-2以下B。如果未 对重复数据删除技术的研究集中在以下几个方 来数据量继续增大,可以选择位数更多的哈希算法面 降低哈希冲突的概率,NST提供了256、384、512位 1)数据集研究 的SHA算法。因此两个指纹值相同的数据块或者文件 对于不同应用场景下数据集特征的研究对设计 可以被认为完全相同。 存储系统来说非常重要。 M icrosof2和EMC分别对 主存储和二级存储文件系统上的文件的一般特征进38 《高性能计算发展与应用》 2014年第三期 总第四十八期 额外产生的元数据sm之和。其中，元数据sm包括两部 分：记录文件对应哈希序列的元数据和索引表元数 据。对于同一个数据集，r越大，重复数据删除效果 越好。 重复数据删除系统的吞吐率也是一个重要的衡 量指标，这里说的吞吐率是写吞吐率。吞吐率衡量 了单位时间内被重复数据删除系统所处理和存储的 逻辑数据量。相比于一般的存储系统，重复数据删 除系统可能会因为引入的额外计算和查询过程造成 吞吐率的降低，但是也有可能因为减少了大量重复 数据的实际读写过程而使吞吐率增大。目前有很多 研究专注于提高系统的吞吐率[5][6][7][8][19][20]。 重复数据删除系统的读性能可以用单位时间 内从去重系统读取的数据量来度量。由于数据块共 享，逻辑上连续的数据经过去重后在物理上不再连 续，因此重复数据删除系统的数据读取速度比一般 的存储系统要差。对于二级存储，读取速度即恢复 速度，决定了系统是否能在要求的恢复时间窗口完 成数据恢复；对于主存储系统则决定了系统的读延 迟。针对提高恢复速度也开展了大量研究[15][21][22][23]。 2. 重复数据删除的一般过程 重复数据删除的一般执行过程可以划分成三 个阶段。首先对接收到的数据流进行划分和指纹计 算，然后对获得的指纹值进行重复检测，最后根据 检测的结果进行相应的数据存储或者元数据更新操 作。 2.1 数据划分和指纹计算 在这一阶段，首先根据预先设定好的策略对数 据进行划分，然后对划分好的数据单元（可以是文 件、或者数据块）分别计算指纹，最后记录构成每 个文件的指纹序列。 指纹是指利用抗冲突特性好的哈希算法（如 SHA-1，MD5）对数据内容计算得到的一个固定长 度的值，该值可以用来唯一标识数据内容。在判别 数据单元内容是否相同的时候，采用逐字节的方法 本身比对过程慢，而且需要先将原先存储的内容读 出，对系统吞吐率影响非常大[5]。因此，重复数据删 除系统通过指纹来判断数据内容的相同与否。 对于一个EB级的存储系统，采用160位的SHA- 1算法，发生哈希冲突的概率在10-20以下[37]。如果未 来数据量继续增大，可以选择位数更多的哈希算法 降低哈希冲突的概率，NIST提供了256、384、512位 的SHA算法。因此两个指纹值相同的数据块或者文件 可以被认为完全相同。 2.2 重复检测 重复检测这一过程非常关键。它是将计算好 的各指纹值与已存储的数据的指纹值进行比较的过 程。去重系统需要维持一张索引表以供查询，其中 每个索引项记录了一个指纹以及该指纹对应的数据 内容在磁盘上的存储位置和引用次数。对于数据量 大的系统，完整的索引表需要存储在磁盘上，加载 到内存中的索引项通常以散列表或者B+树的形式进 行组织，以加快查询速度。在内存查询不命中时需 要进行随机的磁盘访问，因此在数据量大的时候， 重复检测过程是去重系统的性能瓶颈[14]。 通过查询索引表，可以获取指纹值是否已经存 在的信息。对于已经存在的指纹值，不再进行对应 数据内容的存储，只是更新索引项中数据块的引用 次数；对于新的指纹值，进行数据存储和元数据更 新。在冗余消除的过程中，有的时候为了降低数据 块分布的碎片化程度，会进行选择性的消除，以保 持数据恢复性能[22][23]。 2.3 数据存储 对于上一步重复检测判断为不存在的指纹，需 将其数据内容和元数据信息写入磁盘。元数据信息 即一个索引项的全部内容，包括指纹值、数据块位 置、引用次数。如果以数据块或者索引项为单位进 行写入，则会引起大量的随机I/O。 在一些利用数据流的重复局部性进行性能优化 的系统中，数据内容和元数据以container为单位进行 存储和读写[5][6][24]。Container是一个自治的单位，大小 一般能够存放一千到几千个数据块及它们对应的元 数据。经检测为不重复的数据，先写入内存中为该 数据流开放的container缓存中，如果container已满则 将其整个写到磁盘中。恢复过程中也是以container为 单位加载数据和元数据。这么做的目的有四：第 一，充当写缓存，避免了过多的磁盘随机I/O；第 二，container中的数据和元数据都维持了数据流的逻 辑顺序，存在数据流重复局部性；第三，在读的时 候以container为单位进行预取，可以提高缓存命中 率；第四，合理的container大小可以使底层的RAID达 到全条带写。 3. 重复数据删除技术研究现状 对重复数据删除技术的研究集中在以下几个方 面。 1) 数据集研究 对于不同应用场景下数据集特征的研究对设计 存储系统来说非常重要。Microsoft[25]和EMC[26]分别对 主存储和二级存储文件系统上的文件的一般特征进