期刊文献+

一种三容错数据布局 被引量:2

A Data Placement Based on Toleration Triple Failures
下载PDF
导出
摘要 随着存储介质的增多,单容错、双容错的数据布局方案已经无法满足现有分布式存储系统对可靠性要求。该文在双容错行对角奇偶校验(Row Diagonal Parity,RDP)码的基础上,提出一种新的扩展行对角奇偶校验(Extending Row Diagonal Parity,E-RDP)码,能够容许任何3存储节点出错,具有最大距离可分(Maximum Distance Separable,MDS)编码特性,冗余率与纠错能力达到3容错编码最优。并采用不同斜率几何直线图描述编译码过程,给出了一种快速译码算法,易于软硬件实现。与其它纠删码数据布局方案进行比较,理论分析结果表明,E-RDP码的空间利用率、编译码效率、小写性能以及平衡性的综合性能达到最优,具有实用价值。 With increase of storage devices, the data placements based on toleration single or double failures can not meet the requirement of the reliability in the distributed storage systems. On the basis of the Row Diagonal Parity (RDP) code for double toleration failures, a new class of array codes for triple storage failures is presented which is called Extending Row Diagonal Parity (E-RDP) code. The E-RDP code has the Maximum Distance Separable (MDS) property, and it is optimal in redundancy rate and erasure correcting capability among triple erasure-correcting codes. The procedures of encoding and decoding are depicted by geometrical lines of different slope, then a fast decoding algorithm is given and it is more easily implemented by software and hardware. The theoretical analysis shows that the comprehensive properties of the E-RDP code such as encoding and decoding efficiency, small writes and balance performance, are better than other popular MDS codes, thus the E-RDP code is practically meaningful for storage systems.
出处 《电子与信息学报》 EI CSCD 北大核心 2013年第10期2341-2346,共6页 Journal of Electronics & Information Technology
基金 国家自然科学基金(60873216) 四川省教育厅重点项目(12ZA223)资助课题
关键词 数据存储 编码 纠删码 行对角奇偶校验(RDP)码 可靠性 Data storage Coding Erasure-correcting codes Row Diagonal Parity (RDP) code Reliability
  • 相关文献

参考文献3

二级参考文献53

  • 1Layman P, Varian H R. How much information 2003? [EB/OL]. [2010 10-18]. http://www2, sims. berkeley. edu/research/proiects/how-mueh-info-2003. 被引量:1
  • 2Pinheiro E, Weber W D, Barroso L A. Failure trends in a large disk drive population [C] //Proc of the 5th USENIX Conf on File and Storage Technologies. Berkeley, CA: USENIX Association, 2007 : 17-28. 被引量:1
  • 3Schroeder B, Gibson G A. Disk failures in the real world: What does an MTTF of 1,000,000 hours mean to you? [C] //Proc of the 5th USENIX Conf on File and Storage Technologies. Berkeley, CA: USENIX Association, 2007: 1-16. 被引量:1
  • 4Bairavasundaram L N, Goodson G R, Pasupathy S, et al. An analysis of latent sector errors in disk drives [C]//Proc of 2007 ACM SIGMETRICS Int Conf on Measurement and Modeling of Computer Systems. New York: ACM, 200: 289-300. 被引量:1
  • 5Hafner J M, Deenadhayalan V, Rao K, et al. Matrix methods for lost data reconstruction in erasure codes [C] // Proc of the 4th USENIX Conf on File and Storage Technologies. Berkeley, CA: USENIX Association, 2005: 183-196. 被引量:1
  • 6Hafner J M, Deenadhayalan V, Kanungo T, et al. Performance metrics for erasure codes in storage systems, RJ 10321 [R]. San Jose, [A] IBM Research, 2004. 被引量:1
  • 7Li M, Shu J, Zheng W. GRID Codes: Strip based erasure codes with high fault tolerance for storage systems [J].ACM Transon Storage, 2009, 4(4): 1-22. 被引量:1
  • 8Blaum M, Brady J, Bruek J, et al. EVENODD: An efficient scheme for tolerating double disk failures in RAID architectures [J].IEEE Trans on Computer, 1995, 44 (2) 192-202. 被引量:1
  • 9Corbett P, English B, Goel A, et al. Row-diagonal redundant for double disk failure correction [C] //Proc of the 3rd USENIX Conf on File and Storage Technologies. Berkeley, CA: USENIX Association, 2004:2-15. 被引量:1
  • 10Xu L, Bruck J. X-code: MDS array codes with optimal encoding[J]. IEEE Trans on Information Theory, 1999, 45 (1) : 272-276. 被引量:1

共引文献367

同被引文献21

  • 1万武南,吴震,陈运,王晓京.一种基于3容错阵列码的RAID数据布局[J].计算机学报,2007,30(10):1721-1730. 被引量:18
  • 2LUO J Q, MOCHAN S, XU L H, et al. Efficient encoding schedules for XOR-based erasure codes[J]. IEEE Transactions on Computers, 2014, 63(9): 2259-2272. 被引量:1
  • 3LI M, SHU J. On cyclic lowest density MDS array codes constructed using starters[J]. IEEE International Symposium on Information Theory, 2010, 41(3): 1315-1319. 被引量:1
  • 4KVASHENNIKOV V V. Application of fast polynoamial transforma-tions over GALOIS GF(2m) fields in Reed-Solomon coding and de-coding[J]. Telecommunications and Radio Engineering, 2012, 71(10): 85-90. 被引量:1
  • 5BURGISSER P, CLAUSEN M, SHOKROLLAHI MA. Algebraic complexity theory[M]. Springer Verlag Heidelberg. 1996. 被引量:1
  • 6LACAN J, FIMES J. Systematic MDS erasure codes based on Van-dermonde matrices[J]. IEEE Communications Letters, 2004, 8(9): 570-582. 被引量:1
  • 7PLANK J S, XU L.Optimizing cauchy Reed-Solomon codes for fault-tolerant network storage applications[C]//The 5th IEEE Interna-tional Symposium on Network Computing and Applications (IEEE NCA06). Cambridge, MA, 2006: 1-8. 被引量:1
  • 8KALCHER S, LINDENSTRUTH V. Accelerating Galois field arith-metic for Reed-Solomon erasure codes in storage applications[C]// IEEE International Conference on Cluster Computing. 2011: 290-298. 被引量:1
  • 9KHAN O, BURNS R, PLANK J S. Rethinking erasure codes for cloud file systems: minimizing I/O for recovery and degraded reads[C]// USENIX. FAST 2012: 10th USENIX Conference on File and Storage Technologies. San Jose, CA, 2012: 1-14. 被引量:1
  • 10PLANK J S. A tutorial on Reed-Solomon coding for fault-tolerance in RAID-like systems[J]. Software: Practice and Experience, 1997, 27(9): 995-1012. 被引量:1

引证文献2

二级引证文献5

相关作者

内容加载中请稍等...

相关机构

内容加载中请稍等...

相关主题

内容加载中请稍等...

浏览历史

内容加载中请稍等...
;
使用帮助 返回顶部