带宽异构网络下的精确修复再生码数据修复方案

计算机工程与科学 ›› 2024, Vol. 46 ›› Issue (06): 1001-1012.

• 计算机网络与信息安全 • 上一篇下一篇

带宽异构网络下的精确修复再生码数据修复方案

王艳,皮婵娟,刘亚东,施君豪

(华东交通大学软件学院，江西南昌 330013)

收稿日期:2023-10-13 修回日期:2023-11-21 接受日期:2024-06-25 出版日期:2024-06-25 发布日期:2024-06-17
基金资助:
国家自然科学基金（61962020）；上海市智能信息处理重点实验室开放基金(IIPL201910)

Exact repair regeneration code data repair scheme under bandwidth heterogeneous networks

WANG Yan,PI Chan-juan,LIU Ya-dong,SHI Jun-hao

(School of Software,East China Jiaotong University,Nanchang 330013,China)

Received:2023-10-13 Revised:2023-11-21 Accepted:2024-06-25 Online:2024-06-25 Published:2024-06-17

摘要/Abstract

摘要： 再生码技术以高容错性、低冗余开销等优点在数据存储领域得到了广泛应用，但基于再生码的冗余技术在修复失效数据时需从其他帮助节点下载多个编码块。考虑到节点间链路带宽的异构性，在实际网络中链路可用带宽容量变化很大，网络流量最小化并不一定意味着数据修复时间最小化，并且现有针对带宽异构网络下的再生码数据修复方案难以支持精确地修复再生码。由于精确修复再生码具有特定的数学结构，其并行修复难以实现，因此提出一个在带宽异构网络下实现精确修复再生码的数据修复方案ERC-TREE，此方案通过构建一棵最优树来有效利用帮助节点之间的可用带宽，从而实现失效节点数据的精确修复。仿真实验结果表明，在带宽异构网络下采用树型结构修复对精确修复再生码具有可行性。在带宽差异很大的情况下，ERC-TREE的数据修复时间相比星型结构的修复时间减少78%。

关键词: 再生码, 数据存储, 异构网络, 树型修复, 精确修复

Abstract: Regeneration code technique has been widely used in the field of data storage with the advantages of high fault tolerance and low redundancy overhead, but the redundancy technique based on regeneration codes needs to download multiple coded blocks from other providers for repairing the failed data. Considering the heterogeneity of link bandwidth between nodes, the available bandwidth capacity of links varies greatly in real networks, minimization of network traffic does not necessarily imply minimization of regeneration time. Moreover, existing regeneration code repair schemes for bandwidth heterogeneity are difficult to support exact repair regeneration codes. Due to the specific mathematical structure of exact repair regeneration codes, their parallel repair is difficult to achieve. Therefore, ERC-TREE is proposed as a repair framework for exact repair regeneration codes under bandwidth heterogeneous networks. This framework efficiently takes advantage of the available bandwidth between providers by constructing an optimal tree to achieve exact repair of failed node data. The simulation experiment shows the feasibility of tree repair for exact repair regeneration codes in heterogeneous bandwidth environments. In the scenario with a significant difference in bandwidth, ERC-TREE reduces the data repair time by 78% compared to star repair.

Key words: regeneration code, data storage, heterogeneous network, tree repair, exact repair

王艳, 皮婵娟, 刘亚东, 施君豪. 带宽异构网络下的精确修复再生码数据修复方案[J]. 计算机工程与科学, 2024, 46(06): 1001-1012.

WANG Yan, PI Chan-juan, LIU Ya-dong, SHI Jun-hao. Exact repair regeneration code data repair scheme under bandwidth heterogeneous networks[J]. Computer Engineering & Science, 2024, 46(06): 1001-1012.

参考文献［21］

［1］	Brown B, Chui M,Manyika J. Are you ready for the era of ‘big data’?［J］.McKinsey & Quarterly, 2011, 4(1):24-35.
［2］	Li Q, Xiang Q, Wang Y X, et al. More than capacity: Performance-oriented evolution of Pangu in Alibaba［C］∥Proc of the 21st USENIX Conference on File and Storage Technologies, 2023:331-345.
［3］	Li P F, Hua Y, Zuo P F, et al. ROLEX:A scalable RDMA-oriented learned key-value store for disaggregated memory systems［C］∥Proc of the 21st USENIX Conference on File and Storage Technologies, 2023:99-114.
［4］	Zhang F, Wan W T, Zhang C Y, et al. CompressDB:Ena- bling efficient compressed data direct processing for various databases［C］∥Proc of the 2022 International Conference on Management of Data, 2022:1655-1669.
［5］	Nygren E, Sitaraman R K, Sun J. The Akamai network:A platform for high-performance Internet applications［J］. ACM SIGOPS Operating Systems Review, 2010, 44(3):2-19.
［6］	Benson T,Akella A, Maltz D A. Network traffic characteristics of data centers in the wild［C］∥Proc of the 10th ACM SIGCOMM Conference on Internet Measurement, 2010:267-280.
［7］	罗象宏, 舒继武. 存储系统中的纠删码研究综述［J］. 计算机研究与发展, 2012, 49(1):1-11.
	Luo Xiang-hong, Shu Ji-wu. Summary of research for erasure code in storage system ［J］. Journal of Computer Research and Development, 2012, 49(1):1-11.
［8］	许方亮,王意洁,裴晓强. NTar:基于网络拓扑的纠删码树型修复方法［J］. 计算机研究与发展, 2013, 50(Suppl.):37-44.
	Xu Fang-liang, Wang Yi-jie, Pei Xiao-qiang. NTar:Network topology-based tree-structured data reconstruction scheme for erasure codes ［J］. Journal of Computer Research and Development, 2013, 50(Suppl.):37-44.
［9］	Mitra S, Panta R, Ra M R, et al. Partial-parallel-repair (PPR):A distributed technique for repairing erasure coded storage［C］∥Proc of the 11th European Conference on Computer Systems, 2016:1-16.
［10］	Li X, Yang Z, Li J, et al. Repair pipelining for erasure- coded storage:Algorithms and evaluation［J］.ACM Tran- sactions on Storage, 2021, 17(2):1-29.
［11］	Dimakis A G, Godfrey P B, Wu Y, et al. Network coding for distributed storage systems［J］. IEEE Transactions on Information Theory, 2010, 56(9):4539-4551.
［12］	Lee S J , Sharma P , Banerjee S ,et al. Measuring bandwidth between PlanetLab nodes［C］∥Proc of Passive and Active Network Measurement, 2005:292-305.
［13］	Qian Yu, Maddah-Ali M A, Avestimehr A S. Straggler mitigation in distributed matrix multiplication:Fundamental limits and optimal coding［J］.IEEE Transactions on Information Theory, 2020, 66(3):1920-1933.
［14］	Dimakis A G, Ramchandran K, Wu Y, et al. A survey on network codes for distributed storage［J］. Proceedings of the IEEE, 2011, 99(3):476-489.
［15］	Rashmi K V, Shah N B, Kumar P V, et al. Optimal exact-regenerating codes for distributed storage at the MSR and MBR points via a product-matrix construction［J］. IEEE Transactions on Information Theory, 2011, 57(8):5227-5239.
［16］	Wang Y, Wei D S, Yin X R, et al. Heterogeneity-aware data regeneration in distributed storage systems［C］∥Proc of IEEE Conference on Computer Communications, 2014:1878-1886.
［17］	Li X L, Cheng K Y, Tang K C, et al. ParaRC:Embracing sub-packetization for repair parallelization in MSR-coded storage［C］∥Proc of the 21st USENIX Conference on File and Storage Technologies, 2023:17-32.
［18］	Vajha M , Ramkumar V , Puranik B ,et al. Clay codes:Moulding MDS codes to yield an MSR code［C］∥Proc of the 16th USENIX Conference on File and Storage Technologies, 2018:139-153.
［19］	Li J, Yang S, Wang X, et al. Tree-structured data regene- ration in distributed storage systems with regenerating codes［C］∥Proc of IEEE Conference on Computer Communications, 2010:1-9.
［20］	Kundur V. Prims algorithm［EB/OL］. ［2023-07-26］. http://en.wikipedia.org/wiki/Primsalgorithm.
［21］	Duminuco A, Biersack E. A practical study of regenerating codes for peer-to-peer backup systems［C］∥Proc of the 29th IEEE International Conference on Distributed Computing Systems, 2009:376-384.

[1]	刘世缘, 李云春, 陈晨, 杨海龙. 面向大数据存储的主动与被动相结合的性能评测方法体系结构与实现[J]. 计算机工程与科学, 2022, 44(04): 584-593.
[2]	胡海霞, 贾向东, 叶佩文, 纪澎善, 敬乐天. 混合频谱分配的三层异构网络覆盖概率分析[J]. 计算机工程与科学, 2021, 43(07): 1226-1235.
[3]	纪澎善, 贾向东, 路艺, 徐文娟. NOMA双连接异构网络条件解耦设计架构及性能分析[J]. 计算机工程与科学, 2020, 42(07): 1174-1183.
[4]	刘辉1,2,3，宋家旺1,2，代云霞1,2，朱彬欣1,2. 异构网络中基于用户划分的资源分配与功率控制方案[J]. 计算机工程与科学, 2019, 41(08): 1398-1405.
[5]	谢果君，沈记全，杨焕焕. 基于柯西码的HDFS存储优化策略[J]. 计算机工程与科学, 2019, 41(03): 440-445.
[6]	周猛1，贾向东1,2，颉满刚1. 基于随机几何的大规模MIMO中继异构网络性能分析[J]. 计算机工程与科学, 2018, 40(06): 1037-1044.
[7]	梁倬骞1,2，付丹龙2，邓原1. 级联过程中基于动态信息的负载重分配策略[J]. 计算机工程与科学, 2017, 39(09): 1638-1644.
[8]	李志刚,肖侬. 无线传感器网络中对等数据存储策略研究[J]. J4, 2012, 34(5): 24-30.
[9]	刘仲章文嵩王召福周兴铭. 基于对象存储的集群存储系统设计[J]. J4, 2005, 27(2): 78-81.
[10]	王烁张江陵冯丹. 电视播放系统中数据存储子系统的研究与实现[J]. J4, 2004, 26(8): 37-40.
[11]	金伟谢长生. 一种SAN非对称网络级存储虚拟化实现方式的设计与实现[J]. J4, 2004, 26(8): 89-91.
[12]	朱羚杨宗源. 基于B（V）的关系数据库视图增量更新的研究[J]. J4, 2004, 26(6): 81-84.
[13]	曹计昌张凡. IC卡数据存储模型的研究[J]. J4, 2004, 26(5): 74-76.
[14]	刘劲松张江陵王芳. 异构双通道网络磁盘阵列系统的设计[J]. J4, 2004, 26(1): 7-10.
[15]	张金祥吴泉源等. 一种基于分布对象技术的异构网管系统集成框架[J]. J4, 2001, 23(3): 85-88.

带宽异构网络下的精确修复再生码数据修复方案

Exact repair regeneration code data repair scheme under bandwidth heterogeneous networks

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献［21］

相关文章 15

编辑推荐

Metrics

本文评价

带宽异构网络下的精确修复再生码数据修复方案

Exact repair regeneration code data repair scheme under bandwidth heterogeneous networks

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献 ［21］

相关文章 15

编辑推荐

Metrics

本文评价

参考文献［21］