异构对等分布式存储中的DHitchhiker码

doi:10.12263/DZXB.20200288

电子学报 ›› 2021, Vol. 49 ›› Issue (6): 1151-1158.DOI: 10.12263/DZXB.20200288

异构对等分布式存储中的DHitchhiker码

胡金平, 李贵洋, 周悦, 李慧, 江小玉, 韩鸿宇

四川师范大学计算机科学学院, 四川成都 610101

收稿日期:2020-03-23 修回日期:2020-08-01 出版日期:2021-06-25
- 通讯作者:
- 李贵洋
- 作者简介:
- 胡金平 女,1994年生于重庆云阳.四川师范大学计算机科学学院硕士研究生.研究方向为分布式存储、纠删码.E-mail:hu_jp1124@163.com
- 基金资助:
- 国家自然科学基金 (No.61701331）

DHitchhiker Codes in Heterogeneous Peer-to-Peer Distributed Storage

HU Jin-ping, LI Gui-yang, ZHOU Yue, LI Hui, JIANG Xiao-yu, HAN Hong-yu

College of Computer Science, Sichuan Normal University, Chengdu, Sichuan 610101, China

Received:2020-03-23 Revised:2020-08-01 Online:2021-06-25 Published:2022-06-25
- Corresponding author:
- LI Gui-yang
- Supported by:
- National Natural Science Foundation of China (No.61701331)

摘要/Abstract

摘要： 具有高可用性和安全性的去中心化存储因其应用的相同参数低码率RS（Reed-Solomon codes）码存在修复带宽较高的问题.对此，提出一种基于可信度的低修复带宽DHitchhiker码.首先将Hitchhiker码的第一子条带中的数据节点和部分校验节点捎带在余下的校验节点的第二个子条带上；接着将节点分类，让高可信节点存储余下的校验节点，低可信节点存储数据节点和部分校验节点，并让不同类型的节点采用不同的修复策略；最后理论结合实验证明，在修复低可信节点时，DHitchhiker可降低约25%的修复带宽；在整体上，未分类存放的DHitchhiker码可降低约0.5%的修复带宽，基于可信度的DHitchhiker码可降低约1%的修复带宽和2.5%~3.3%的修复时间.

关键词: MDS码, RS码, 可信度, 去中心化存储, Hitchhiker码

Abstract: Decentralized storage with high availability and security has the problem of high repair bandwidth due to the same parameter low rate Reed-Solomon codes. Thus, a low repair bandwidth DHitchhiker based on credibility is proposed. Data nodes and some parity nodes in the first sub-stripe of Hitchhiker are piggybacked on the second sub-stripe of the remaining parity nodes. We classify the nodes, and let thehigh-credit nodes store the remaining parity nodes, the low-credit nodes store the data nodes and some parity nodes, and different types of nodes adopt different repair strategies. It is proved that the repair bandwidth can be reduced by about 25% at repairing low-credit nodes. And the repair bandwidth can be reduced by about 0.5% without classifying the nodes. What's more, the repair bandwidth can also be reduced by about 1% and the repair time can be reduced by about 2.5%~3.3% based on the credibility of the nodes.

Key words: MDS codes, Reed-Solomon codes, credibility, decentralized storage, hitchhiker

中图分类号:

TP333

胡金平, 李贵洋, 周悦, 等. 异构对等分布式存储中的DHitchhiker码[J]. 电子学报, 2021, 49(6): 1151-1158.

HU Jin-ping, LI Gui-yang, ZHOU Yue, et al. DHitchhiker Codes in Heterogeneous Peer-to-Peer Distributed Storage[J]. Acta Electronica Sinica, 2021, 49(6): 1151-1158.

参考文献

[1] Plank J S.Erasure codes for storage systems:A brief primer[J].The Usenix Magazine,2013,38(6):44-50.
[2] 王意洁,许方亮,裴晓强.分布式存储中的纠删码容错技术研究[J].计算机学报,2017,40(01):238-257. Wang Yijie,Xu Fangliang,Pei Xiaoqiang.Research on error tolerance technology of error correction codes in distributed storage[J].Journal of Computer Science,2017,40(01):238-257.(in Chinese).
[3] Mckusick K,Quinlan S.GFS:Evolution on fast-forward[J].Communications of the ACM,2010,53(3):42-49.
[4] White T.Hadoop:The Definitive Guide[M].American:O'Reilly Media,Inc.2011.
[5] Xiaolu L,Runhui L,Lee P P,et al.OpenEC:Toward unified and configurable erasure coding management in distributed storage systems[A].17th USENIX Conference on File and Storage Technologies[C].Boston,MA:USENIX, 2019.331-344.
[6] Xue R,Guan Z,Gao S,et al.NM2H:Design and implementation of NoSQL extension for HDFS metadata management[A].IEEE 17th International Conference on Computational Science and Engineering[C].Chengdu,China:IEEE,2014.1282-1289.
[7] Nakamoto S.Bitcoin:A Peer-to-peer Electronic Cash System[EB/OL].https://bitcoin.org/en/bitcoin-paper,2008.
[8] Storj Labs.Storj:A Decentralized Cloud Storage Network Framework[EB/OL].https://github.com/storj/whitepaper,2018-10-16.
[9] NebulousLabs.Sia:Simple Decentralized Storage[EB/OL].https://gitlab.com/NebulousLabs/Sia,2018-12-21.
[10] Dau H,Duursma I,Kiah H M,et al.Repairing reed-solomon codes with multiple erasures[J].IEEE Transactions on Information Theory,2018,64(20):6567-6582.
[11] e M,Barg A.Explicit constructions of MDS array codes and RS codes with optimal repair bandwidth[A].2016 IEEE International Symposium on Information Theory (ISIT)[C].Barcelona Spain:IEEE,2016.1202-1206.
[12] Hou H,Han Y S,Shum K W,et al.A unified form of EVENODD and RDP codes and their efficient decoding[J].Communications IEEE Transactions on,2018,66(11):5053-5066.
[13] Rashmi KV,Shah N B,Ramchandran K.A piggybacking design framework for read-and download-efficient distributed storage codes[J].IEEE Transactions on Information Theory,2017,63(9):5802-5820.
[14] Guiyang L,Xing L,Xiaohu T.An efficient one-to-one piggybacking design for distributed storage systems[J].IEEE Transactions on Communications,2019,67(12):8193-8205.
[15] Dimakis A G,Godfrey P B,Wu Y,et al.Network coding for distributed storage systems[J].Information Theory IEEE Transactions on,2008,56(9):4539-4551.
[16] Rashmi K V,Shah N B,Kumar P V.Optimalexact-regenerating codes for distributed storage at the MSR and MBR points via a product-matrix construction[J].IEEE Transactions on Information Theory,2010,57(57):5227-5239.
[17] Alrabiah O,Guruswami V.An exponential lower bound on the sub-packetization of MSR codes[A].Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing[C].Phoenix:ACM,2019.979-985.
[18] Jie L,Xiaohu T,Chao T.A generic transformation to enable optimal repair in MDS codes for distributed storage systems[J].IEEE Transactions on Information Theory,2018,64(9):6257-6267.
[19] Hou H,Lee P P.Binary MDS array codes with optimal repair[J].IEEE Transactions on Information Theory,2020,66(3):1405-1422.
[20] Rashmi KV,Shah N B,Gu D,et al.A "hitchhiker's" guide to fast and efficient data reconstruction in erasure-coded data centers[J].ACM Sigcomm Computer Communication Review,2014,44(4):331-342.
[21] Shen Z,Lee P P,Shu J,et al.Cross-rack-aware single failure recovery for clustered file systems[J].IEEE Transactions on Dependable and Secure Computing,2020,17(2):248-261.
[22] 江小玉,李贵洋,周悦,等.基于负载均衡的纠删码修复流水线[J].电子学报,2020,48(5):930-936. Xiaoyu J,Guiyang L,Yue Z,et al.Repair pipelining for erasure-coded storage based on load-balanced[J].Acta Electronica Sinica,2020,48(5):930-936.(in Chinese).
[23] Bhagwan R.Total recall:System support for automated availability management[J].USENIX Association,2004,01(04):1-25.
[24] Kumar S,Amat A G I,Andriyanova I,et al.Code constructions for distributed storage with low repair bandwidth and low repair complexity[J].IEEE Transactions on Communications,2018,66(12):5847-5860.
[25] Amazon Inc.Amazon Simple Storage Service-ObjectMetadata[EB/OL].https://docs.aws.amazon.com/AmazonS3/latest/dev/UsingMetadata.html,2018.

异构对等分布式存储中的DHitchhiker码

DHitchhiker Codes in Heterogeneous Peer-to-Peer Distributed Storage

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 13

编辑推荐

Metrics

[1]	刘杰, 张立民, 钟兆根. 基于二元域等效的RS码编码参数盲识别[J]. 电子学报, 2018, 46(12): 2888-2895.
[2]	刘康宁, 赵增华, 王宇. AdaCode:IEEE 802.11n长距离无线链路自适应编码算法[J]. 电子学报, 2018, 46(12): 2942-2949.
[3]	李晶, 吴国仕, 谢菲, 姚旭, 齐佳音, 孙鹏飞. 生活消费平台虚假评论识别模型的研究[J]. 电子学报, 2016, 44(12): 2855-2860.
[4]	万明, 张宏科, 尚文利, 沈烁, 刘颖. 一体化标识网络映射缓存DoS攻击防范方法研究[J]. 电子学报, 2015, 43(10): 1941-1947.
[5]	解辉, 黄知涛, 王丰华. 信道编码盲识别技术研究进展[J]. 电子学报, 2013, 41(6): 1166-1176.
[6]	谭智勇;刘铎;司天歌;戴一奇. 一种具有可信度特征的多级安全模型[J]. 电子学报, 2008, 36(8): 1637-1641.
[7]	曾剑平, 郭东辉, . 基于区间值2型模糊集的伪装入侵检测算法[J]. 电子学报, 2008, 36(4): 777-780.
[8]	胡可;汪增福. 一种基于时频分析的语音卷积信号盲分离算法[J]. 电子学报, 2006, 34(7): 1246-1254.
[9]	刘文举, 孙兵, 钟秋海. 基于说话人分类技术的分级说话人识别研究[J]. 电子学报, 2005, 33(7): 1230-1233.
[10]	徐蔚然, 郭军. 手写金融汉字识别中的可信度估计[J]. 电子学报, 2005, 33(10): 1879-1882.
[11]	毛剑;高虎明;王育民. 一个新的广播信道会议密钥协商协议[J]. 电子学报, 2004, 32(4): 642-644.
[12]	张湘平;张金槐;谢红卫. 关于样本容量、验前信息与Bayes决策风险的若干讨论[J]. 电子学报, 2003, 31(4): 536-538.
[13]	张品;李乐民;王晟. 运用模糊数解决非确定环境下的路由问题[J]. 电子学报, 2003, 31(12): 1861-1865.