基于负载均衡的纠删码修复流水线

doi:10.3969/j.issn.0372-2112.2020.05.013

电子学报 ›› 2020, Vol. 48 ›› Issue (5): 930-936.DOI: 10.3969/j.issn.0372-2112.2020.05.013

基于负载均衡的纠删码修复流水线

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

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

收稿日期:2019-07-04 修回日期:2020-02-07 出版日期:2020-05-25
- 通讯作者:
- 李贵洋
- 作者简介:
- 江小玉 女,1994年出生于四川自贡,现为四川师范大学计算机科学学院硕士研究生,主要研究方向为分布式存储、纠删码.E-mail:jiang_xy0805@163.com
- 基金资助:
- 国家自然科学基金 (No.61701331）

Repair Pipelining for Erasure-Coded Storage Based on Load-Balanced

JIANG Xiao-yu, LI Gui-yang, ZHOU Yue, HU Jing-ping, LI Hui

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

Received:2019-07-04 Revised:2020-02-07 Online:2020-05-25 Published:2020-05-25
- Corresponding author:
- LI Gui-yang
- Supported by:
- National Natural Science Foundation of China (No.61701331)

摘要/Abstract

摘要： 大数据分布式存储系统中，修复流水线（Repair Pipelining，RP）减少90%的修复时间，有效地解决由于修复时间开销较大，纠删码不适用于存储热数据的问题.然而，现有的RP存在节点负载不均衡的问题，导致系统性能下降.通过研究后，设计节点负载均衡的纠删码修复流水线（Node Load Balancing-based Repair Pipelining，NLB-RP），并根据性能评价指标提出计算节点负载的算法和计算修复时间的算法.理论分析及实验结果表明，在没有引入额外修复代价的情况下，NLB-RP从局部到整体有效地平衡并减少节点的负载.相比RP，NLB-RP的节点负载方差为0，即每个节点的负载相同.因此，NLB-RP具有最优的负载均衡性.

关键词: 大数据, 分布式存储, 纠删码, 修复流水线, 负载均衡

Abstract: In distributed storage system for big data,the repair pipelining (RP) reduces repair time by 90%, which effectively solves the problem that erasure code is not suitable for storing hot data due to the heavy overhead of repair time. However, the existing RP has the problem of unbalanced load among nodes,which leads to the degradation of system performance. In this paper, a repair pipelining based on node load balancing (NLB-RP) is designed, and then the algorithms for calculating the load of nodes and repair time according to the evaluation index of performance are proposed. Theoretical analysis and experimental results both show that, from local to global, the NLB-RP can effectively balance and reduce the load of nodes without introducing extra repair cost. Compared with the RP, the load variance of the NLB-RP is zero, that is, the load of each node is the same. Thus, the proposed NLB-RP has the optimal load balance.

Key words: big data, distributed storage, erasure code, repair pipelining, load balancing

中图分类号:

TP333

江小玉, 李贵洋, 周悦, 等. 基于负载均衡的纠删码修复流水线[J]. 电子学报, 2020, 48(5): 930-936.

JIANG Xiao-yu, LI Gui-yang, ZHOU Yue, et al. Repair Pipelining for Erasure-Coded Storage Based on Load-Balanced[J]. Acta Electronica Sinica, 2020, 48(5): 930-936.

参考文献

[1] Huang C,Simitci H,Xu Y,et al.Erasure coding in windows azure storage[A].Proceedings of the 2012 USENIX conference on Annual Technical Conference[C].Berkeley,CA:USENIX,2012.2-2.
[2] 王意洁,许方亮,裴晓强.分布式存储中的纠删码容错技术研究[J].计算机学报,2017(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(01):238-257.(in Chinese)
[3] Ford D,Labelle F,Popovici F I,et al.Availability in globally distributed storage systems[A].Proceedings ofUsenix Conference on Operating Systems Design & Implementation[C].Berkeley,CA:USENIX,2010.61-74.
[4] 吴炀,付印金,陈卫卫,倪桂强.一种高效的混合内存布局机制与编码技术[J].计算机科学,2017,44(6):57-62. Wu Yang,Fu Yin-jin,Chen Wei-wei,Ni Gui-qiang.Efficient mechanism of hybrid memory placement and erasure code[J].Computer Science,2017,44(6):57-62.(in Chinese)
[5] Plank 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.
[6] Ghemawat S,Gobioff H,Leung S,et al.The Google file system[J].Symposium on Operating Systems Principles,2003,37(5):29-43.
[7] The Apache Software Foundation.HDFSArchitecture[DB/OL].http://hadoop.apache.org/docs/current/hadoop-project-dist/hadoop-hdfs/HDFSErasureCoding.html,2018-11-13.
[8] Wilkinson S,Boshevski T,Prestwich J,et al.Storj a peer-to-peer cloud storage network[DB/OL].https://storj.io/storjv2.pdf,2016-12-15.
[9] Protocol Labs.FileCoin:A decentralized storage network[DB/OL].http://filecoin.io/filecoin.pdf,2017-6-19.
[10] KosaianJ,Rashmi K V,Venkataraman S.Learning a code:Machine learning for approximate non-linear coded computation[J].arXiv:Learning,2018.
[11] Karakus C,Sun Y,Diggavi S,et al.Redundancy techniques for straggler mitigation in distributed optimization and learning[J].arXiv:Machine Learning,2018.
[12] Sathiamoorthy M,Asteris M,Papailiopoulos D S,et al.XORing elephants:Novel erasure codes for big data[J].very large data bases,2013,6(5):325-336.
[13] 李元超.面向冷数据存储的分布式编码技术研究与实现[D].武汉:华中科技大学,2016.1-62. Li Yuanchao.Research and Implementation of Distributed Coding Technology for Cold Data Storage[D].Wuhan:Huazhong University of Science and Technology,2016.1-62.(in Chinese)
[14] Rashmi K V,Nakkiran P,Wang J,et al.Having your cake and eating it too:jointly optimal erasure codes for I/O,storage and network-bandwidth[A].Proceedings of Usenix Conference on File & Storage Technologies[C].Berkeley,CA:USENIX,2015.81-94.
[15] Rashmi K V,Shah N B,Gu D,et al.A "hitchhiker's" guide to fast and efficient data reconstruction in erasure-coded data centers[J].ACM Special Interest Group on Data Communication,2015,44(4):331-342.
[16] Mitra S,Panta R K,Ra M,et al.Partial-parallel-repair (PPR):a distributed technique for repairing erasure coded storage[A].Proceedings of European Conference on Computer Systems[C].Dresden,Germany:ACM,2016.1-30.
[17] Li R,Li X,Lee P P,et al.Repair pipelining for erasure-coded storage[A].Proceedings of the 2017 USENIX Conference on Annual Technical[C].Berkeley,CA:USENIX,2017.567-579.
[18] Yuan S,Huang Q,Wang Z.A repair-efficient coding for distributed storage systems under piggy backing framework[J].IEEE Transactions on Communications,2018,66(8):3245-3254.
[19] Pamiesjuarez L,Blagojevic F,Mateescu R,et al.Opening the chrysalis:on the real repair performance of MSR codes[A].Proceedings of the Conference on File and Storage Technologies[C].Berkeley,CA:USENIX,2016.81-94.
[20] Reed I S,Solomon G.Polynomialcodes over certain finite fields[J].Journal of the Society for Industrial and Applied Mathematics,1960,8(2):300-304.
[21] Plank J S,Xu L.Optimizing cauchy reed-solomon codes for fault-tolerant network storage applications[A].Proceedings of Network Computing and Applications[C].Cambridge,USA:IEEE,2006.173-180.

基于负载均衡的纠删码修复流水线

Repair Pipelining for Erasure-Coded Storage Based on Load-Balanced

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	刘焕淋, 胡俊岭, 任杰, 胡会霞, 唐畅, 陈浩楠. 基于光路负载均衡和邻域匹配的串扰感知资源分配方法[J]. 电子学报, 2022, 50(11): 2746-2753.
[2]	刘耿耿, 李泽鹏, 郭文忠, 陈国龙, 徐宁. 面向超大规模集成电路物理设计的通孔感知的并行层分配算法[J]. 电子学报, 2022, 50(11): 2575-2583.
[3]	侯秀聪, 赖晓平, 曹九稳. 正则化超限学习机的最大分划广义交替方向乘子法[J]. 电子学报, 2021, 49(4): 625-630.
[4]	周悦, 李贵洋, 韩鸿宇, 李慧, 胡金平. 一种均衡分配的修复校验节点的Piggybacks捎带设计[J]. 电子学报, 2021, 49(4): 812-816.
[5]	崔子熙, 胡宇翔, 兰巨龙, 王雨. 基于流分类的数据中心网络负载均衡机制[J]. 电子学报, 2021, 49(3): 559-565.
[6]	王宁远, 刘亮, 陈东, 刘欢, 郝时光. 低轨巨星座多品类业务流低复杂度分段路由方法[J]. 电子学报, 2021, 49(11): 2124-2132.
[7]	杨洋. 改进帕累托算法求解超大规模多选择背包问题[J]. 电子学报, 2020, 48(6): 1205-1212.
[8]	陆佳炜, 吴涵, 陈烘, 张元鸣, 梁倩卉, 肖刚. 一种基于动态拓扑的流计算性能优化方法及其在Storm中的实现[J]. 电子学报, 2020, 48(5): 878-890.
[9]	徐超, 陈勇, 葛红美, 何炎祥. 基于大数据的审计技术研究[J]. 电子学报, 2020, 48(5): 1003-1017.
[10]	张鹏, 叶剑, 张鹏. 基于概念漂移检测的大数据交易过程模型优化方法[J]. 电子学报, 2019, 47(7): 1465-1474.
[11]	刘焕淋, 胡浩, 陈勇, 杜君丹, 向敏. 联合能耗与负载均衡的虚拟网络映射方法[J]. 电子学报, 2019, 47(12): 2488-2494.
[12]	魏波, 吴瑞峰, 张文生, 吕敬钦, 王莹莹, 夏学文. 具有双重稀疏机制的在线学习算法[J]. 电子学报, 2019, 47(10): 2202-2210.
[13]	金宏桥, 董一鸿, 陈华辉, 钱江波. 分布式环境下基于马尔科夫链的图流三角近似计算[J]. 电子学报, 2018, 46(9): 2139-2148.
[14]	郭艺, 叶剑, 张鹏. 基于偏差约减的大数据交易模型分析与修复方法[J]. 电子学报, 2018, 46(7): 1754-1761.
[15]	黄建洋, 兰巨龙, 胡宇翔, 马腾. 一种基于分段路由的多路径流传输机制[J]. 电子学报, 2018, 46(6): 1488-1495.