2013 年 8 月 Journal on Communications August 2013
第 34 卷第 Z1 期
通 信 学 报
Vol.34
No. Z1
基于 X-RDP 阵列码的一种数据分布策略
万武南
1,2
，索望
1
，陈运
2
，王拓
1
(1. 成都信息工程学院 网络工程学院，四川 成都 610225；2. 成都信息工程学院 应用密码学研究所，四川 成都 610225)
摘 要：对双容错 RDP(row diagonal parity)码进行了扩展，提出了一种基于 X-RDP 阵列码 3 容错的数据分布策略。
利用 X-RDP 码的代数定义，从理论上证明了 X-RDP 码具有 MDS 编码特性。并采用不同斜率几何直线图描述编
译码过程，易于软硬件实现。与其他数据分布策略进行比较，理论分析结果表明，X-RDP 码的空间利用率、编译
码效率、小写性能以及平衡性的综合性能达到最优，具有实用价值。
关键词：编码；纠删码；RDP 码；数据布局；磁盘阵列
中图分类号：TP333 文献标识码：A 文章编号：1000-436X(2013)Z1-0067-09
Data distribution strategy based on the X-RDP array codes
WAN Wu-nan
1,2
, SUO Wang
1
, CHEN Yun
2
, WANG Tuo
1
(1. Network Engineering Department, Chengdu University of Information Technology, Chengdu 610225, China;
2. Institute of Applied Cryptograph, Chengdu University of Information Technology, Chengdu 610225, China)
Abstract: A data distribution strategy based on the X-RDP code was presented for correcting triple storage failures,
which is an extension of the double-erasure-correcting RDP code. A theoretical proof that the X-RDP code is an MDS
code was given by using algebraic definition. The encoding and decoding procedures were described by geometrical line
graphs, which were easily implemented by soft hardware. The theoretical analysis shows that the comprehensive proper-
ties of the X-RDP codeis better than other popular MDS codes in encoding and decoding efficiency, small writes and bal-
ance performance, thus the X-RDP code is practically meaningful for storage systems.
Key words: coding; erasure-correcting code; RDP code; data placement; RAID
1 引言
目前，分布式存储系统在硬盘级的数据容错技
术大多采用基于单容错或双容错的数据分布策略
来提高系统可靠性
[1,2]
。双容错数据布局策略已经有
许多研究，文献[3～8]分别提出了 EVENODD 码
[3]
、
X 码
[4]
、B 码
[5]
、C 码
[6]
、RDP 码
[7]
、H 码
[8]
，编译
码只需要异或运算，并具有 MDS 编码特性，数据
冗余率达到了最优。但随着海量存储系统的发展，
存储介质急剧增大，设备发生损毁的概率也越来越
大，因此单容错和双容错数据分布策略已经无法满
足存储系统可靠性的要求，研究 3 容错、多容错的
数据分布策略已成为硬盘级数据容错技术的一个
重要研究问题。
在 3 容错和多容错数据分布策略研究方面，文献
[9～11]提出了 GRID
[9]
、HoVer 码
[10]
、WEAVER 码
[11]
能够纠 4 个以上错误的阵列编码布局，但是这 3 类
编码都不具有 MDS 编码特性，空间利用率只有大概
50%。FENG G L 等人在文献[12,13]中提出了 2 种新
的能够承受 3 个和多个存储介质同时故障的 2 类阵
列编码，分别是由类似于范德蒙矩阵和柯西矩阵来
构造的，编译码结构不易软硬件实现。文献[14,15]
提出的 Blaum 码
[14]
和 T 码
[15]
是低密度奇偶 MDS 码，
理论上能够容许多个错误，但是其译码方法不易实
现。Tau 在文献[16]中提出了 HDD1 码和 HDD2 码，
MDS 编码特性证明不充分，译码过程是基于高斯三
收稿日期：2013-06-21
基金项目：国家自然科学基金资助项目（60873216）；四川省教育厅重点基金资助项目（12ZA223）
Foundation Items: The National Natural Science Foundation of Ch
ina (60873216); Key Project of Sichuan Provincial Department
of Education (12ZA223)
doi:10.3969/j.issn.1000-436x.2013.z1.009
剩余8页未读，继续阅读
资源评论
weixin_38612139
- 粉丝: 3
- 资源: 885
最新资源
- 包含 Andrei Neagoie 的《从零到精通掌握编码面试 - 数据结构 + 算法》课程的所有代码示例，使用 Python 语言 .zip
- 数据库课程设计（图书馆管理系统）springboot+swing+mysql+mybatis
- C++ Vigenère 密码（解密代码）
- zblog日收站群，zblog泛目录
- C++ Vigenère 密码（加密代码）
- Vue Router 是 Vue 生态系统的一部分，是一个 MIT 许可的开源项目，其持续开发完全在赞助商的支持下成为可能 支持 Vue 路由器
- PM2.5 数据集 包含上海、成都、广州、北京、沈阳五地的PM2.5观测，csv文件
- 电动汽车与软件定义汽车（SDV）时代的汽车行业数字化转型
- C的两数相加求和的程序代码
- 使用特定版本的 Python 设置 GitHub Actions 工作流程.zip
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
