重复数据删除综述(4):可靠性问题、纠删码技术

  接上篇:重复数据删除综述(1):基于相同数据的检测

      重复数据删除综述(2):固定和可变长度数据块

      重复数据删除综述(3):对系统性能的影响问题

  上述这些技术使得共享数据块的文件之间产生了依赖性,几个关键数据块的丢失或错误可能导致多个文件的丢失和错误发生,因此它同时又会降低存储系统的可靠性。为此,一些研究者又引入了冗余复制技术和纠删码技术等来提高重复数据删除系统的可靠性。

  4.1 冗余复制策略

  一些研究者提出通过消除冗余所节省空间的一部分复制一些块,策略性地增加冗余来提高系统可靠性。鉴于单纯为所有数据增加冗余所导致的大量空间消耗,研究者们提出了不同的处理方法:

  1)提出根据块的重要度来决定块的重复度,它按照基于块权重的复制方法来增加数据冗余。在该技术中设定即使一个块只有一个依赖关系,也必须被保护。所以其启发式规则为每个块保存至少两个复制。还有的文献提出的该可靠性技术模型不会影响重复数据删除技术带来的存储空间的节约,它利用合适的启发式规则和参数变化,占用大约一半的存储空间,取得了比传统跨文件压缩方法更高的可靠性。

  2)针对引用数据进行冗余复制,即对实际有用的数据,而非传统的所有数据。研究发现,引用数据或内容固定的数据占据了日常数据量的大部分,并且增长迅速。而引用数据的特征是存在大量的相似数据,且不能被改变,并且需要保持很长的时间。因此下面经典文献提出了一个针对引用数据实现的可靠性存储系统。该系统通过管理数据的唯一块可靠、高效地存储大量的相似数据,并允许被选择的数据被高效删除。其中系统可靠性的设计是基于块与块之间的信息内容来管理数据存储的。

  3)在不同应用或层次上增加冗余数据提高系统的可靠性。RAID是通过引进冗余并以此保证存储系统的可靠性。OceanStore对持久数据提高全局的连续访问,并使用自动复制策略来提高系统可靠性。FARSITE是一个分布式系统,它通过复制文件系统的元数据来提供可靠性。

  经典文献

  uDuplicate management forreference data

  Denehy TE, Hsu WW. IBM Research Report, RJ 10305(A0310-017), IBM Research Division, 2003.

  uProviding high reliability in aminimum redundancy archival storage system

  Bhagwat D, Pollack K, Long DDE, Schwarz T, MillerEL, Pâris JF. In: Proc. of the 14th Int’l Symp. on Modeling, Analysis, andSimulation of Computer and Telecommunication Systems (MASCOTS 2006). Washington:IEEE Computer Society Press, 2006. 413–421.

  4.2 纠删码技术

  在存储系统中,单纯地通过增加完全副本冗余来提高系统的可靠性并不能保证在错误出现时,数据仍具有持久性和可靠性。因此一些研究者提出利用纠删码技术对数据做一定的冗余来增加系统的可靠性。纠删码技术是指将要存储的数据切分为k个部分,然后通过编码算法变换为n(n>k)个部分,其中任意k′(k′≥k)个部分可以用来恢复原始数据。当k’ = k时,称编码算法具有最大距离分割性质(maximum distance separable,简称MDS).

  纠删码主要分为4大类:Reed Solomon Codes, Parity Array Codes,Parity-check Codes和LDPC(low density parity check)Codes。其中,Reed Solomon Codes是基于有限域运算的,后三者主要是基于XOR运算。每种纠删码(erasure codes)都有其各自的优缺点:

  1) Reed Solomon码

  i.MDS码,具有最优的存储利用率;

  ii.容错能力k′可以为任意数;

  iii.数据出度总是大于k′,从而有较高的更新(update)复杂度;

  iv.复杂的代数运算。

  2) Parity Array码:主要是通过单元的二维空间几何分布构成的,适用于RAID系统。

  3) Parity-check码:从奇偶校验码发展而来的多维码,特点是简单且完全基于XOR运算,容易实现,且更新(update)和解码(decode)等操作都具有较好的局部性,其缺点是非MDS,主要适合于大规模存储系统。

  4) LDPC码:基于Tanner图发展起来的一维码,其构造主要是基于图论和蒙特卡洛法。其优点是可以完全用XOR运算实现,并且其存储利用率接近MDS。其解码算法主要是采用迭代方法实现,可以达到很高的容错能力,但是容错能力越高,其构造越不规则,从而导致不易实现。