一类新的(k+2,k) Hadamard MSR码

张司娜; 唐小虎; 李杰

doi:10.3969/j.issn.0258-2724.2016.01.026

一类新的(k+2,k) Hadamard MSR码

doi: 10.3969/j.issn.0258-2724.2016.01.026

详细信息

作者简介:
张司娜(1985-),女,博士研究生,研究方向为分布式存储编码,E-mail:nsz1221@163.com

通讯作者:
唐小虎(1971-),男,教授,博士生导师,研究方向为信息安全与编码,E-mail:xhtang_scce@home.swjtu.edu.cn

计量
- 文章访问数: 801
- HTML全文浏览量: 50
- PDF下载量: 273
- 被引次数: 0
出版历程
- 收稿日期: 2015-02-01
- 刊出日期: 2016-01-25

A New (k+2, k) Hadamard Minimum Storage Regenerating Code

摘要

摘要: 为降低分布式存储系统中节点的存储量,构造了一类新(k+2, k)Hadamard MSR码.该码的每个编码矩阵皆对应于2个值,供其对角元素选取.在编码矩阵中,这2个值循环出现,且不同的矩阵,循环出现的周期不同.基于这一特性构造了节点的修复方案,将失效节点中的个数据分成/2组,每一组重建2个数据,其他k+1个节点为每一组各提供1个数据.证明了若新码编码矩阵的对角元素可取的2个值不相等,则可最优修复系统节点;若所有编码矩阵对角元素可取的2个值的和为同一不为0的值,则可最优修复第1个校验节点;若所有编码矩阵对角元素可取的2个值的逆的和为1,则可最优修复第2个校验节点.新码的节点存储量降低到了Hadamard MSR码的理论界,可最优修复任意系统节点和1个校验节点.
- 分布式 /
- 存储 /
- 再生码 /
- MSR码 /
- 高码率 /
- 最优 /
- 修复
Abstract: To reduce the storage capacity of nodes in distributed storage systems, a new (k+2, k) Hadamard Minimum Storage Regenerating (MSR) code was constructed. Each coding matrix is related to two values, from which the diagonal elements of this coding matrix are selected. These two values appear in the coding matrix in a repeating pattern, but with different repeating cycles for different matrices. Based on the structure of the coding matrix, a repair strategy was constructed. The repair strategy divides symbols in the failed node into /2 groups with two symbols in each group, then the two symbols are recovered by downloading one symbol from each of the other k+1 nodes. If the two values related to each coding matrix are unequal, the new Hadamard MSR code can optimally repair systematic nodes. If the sum of two values related to each coding matrix is nonzero and the k values are the same, the new Hadamard MSR code can optimally repair the first parity node. If the sum of the inverse of two values related to each coding matrix is one, the new Hadamard MSR code can optimally repair the second parity node. The new code reduces the storage capacity to the bond for Hadamard MSR code. Further, it can optimally repair all systematic nodes and one parity node.
- distributed /
- storage /
- regenerating code /
- MSR code /
- high code-rate /
- optimal /
- repair

HTML全文

参考文献(16)

RHEA S, WELLS C, EATON P, et al. Maintenance-free global data storage[J]. IEEE Internet Computing, 2001, 5(5): 40-49.

BHAGWAN R, TATI K, CHENG Y C, et al. Total recall: System support for automated availability management[C]//Symposium Networked Systems Design and Implementation. San Francisco: ACM, 2004: 25-25.

DABEK F, LI Jinyang, SIT E, et al. Designing a DHT for low latency and high throughput[C]//Symposium Networked Systems Design and Implementation (NSDI). San Francisco: ACM, 2004: 85-98

HUANG Cheng, SIMITCI H, XU Yi, et al. Erasure coding in windows azure storage[C]//Usenix annual Technical Conference. Boston: ACM, 2012: 15-26.

DIMAKIS A G, GODFREY P B, WU Yunnan, et al. Network coding for distributed storage systems[J]. IEEE Transactions on Information Theory, 2010, 56(9): 4539-4551.

范文礼,刘志刚. 基于传输效率矩阵的复杂网络节点重要度排序方法[J]. 西南交通大学学报,2014,49(2): 337-342. FAN Wenli, LIU Zhigang. Ranking method for node importance based on efficiency matrix[J]. Journal of Southwest Jiaotong University, 2014, 49(2): 337-342.

DIMAKIS A G, RAMCHANDRAN K, WU Yunnan, et al. A survey on network codes for distributed storage[J]. Proceedings of the IEEE, 2011, 99(3): 476-489.

郝杰,逯彦博,刘鑫吉,等. 分布式存储中的再生码综述[J]. 重庆邮电大学学报:自然科学版,2013,25(1): 30-38. HAO Jie, LU Yanbo, LIU Xinji, et al. Survey for regenerating codes for distributed storage[J]. Journal of Chongqing University of Posts and Telecommunications: Natural Science Edition, 2013, 25(1): 30-38.

PAPAILIOPOULOS D S, DIMAKIS A G, CADAMBE V R. Repair optimal erasure codes through hadamard designs[J]. IEEE Transactions on Information Theory, 2013, 59(5): 3021-3037.

TAMO I, WANG Zhiying, BRUCK J. Zigzag codes: MDS array codes with optimal rebuilding[J]. IEEE Transactions on Information Theory, 2013, 59(3): 1597-1616.

WANG Zhiying, TAMO I, BRUCK J. Long MDS codes for optimal repair bandwidth[C]//Proceedings of IEEE International Symposium on Information Theory. Cambridge: IEEE, 2012: 1182-1186.

TAMO I, WANG Zhiying, BRUCK J. MDS array codes with optimal rebuilding[C]//Proceedings of IEEE International Symposium on Information Theory. St. Petersburg: IEEE, 2011: 1240-1244.

CADAMBE V R, JAFAR S A, MALEKI H, et al. Asymptotic interference alignment for optimal repair of MDS codes in distributed storage[J]. IEEE Transactions on Information Theory, 2013, 59(5): 2974-2987.

CADAMBE V R, HUANG Cheng, LI Jin, et al. Polynomial length MDS codes with optimal repair in distributed storage[C]//The 45th Asilomar Conference on Signals, Systems and Computers (ASILOMAR).Pacific Grove: IEEE, 2011: 1850-1854.

CADAMBE V R, HUANG Cheng, LI Jin. Permutation code: Optimal exact-repair of a single failed node in MDS code based distributed storage systems[C]//Proceedings of IEEE International Symposium on Information Theory Proceedings (ISIT).St. Petersburg: IEEE, 2011: 1225-1229.

TAMO I, WANG Zhiying, BRUCK J. Access versus bandwidth in codes for storage[J]. IEEE Transactions on Information Theory, 2014, 60(4): 2028-2037.

施引文献

附加材料(0)

访问统计