分布式存储系统中新型可修复喷泉码构造

doi:10.12305/j.issn.1001-506X.2022.01.35

系统工程与电子技术 ›› 2022, Vol. 44 ›› Issue (1): 285-291.doi: 10.12305/j.issn.1001-506X.2022.01.35

分布式存储系统中新型可修复喷泉码构造

周安安, 易本顺*, 刘羽升, 罗来干

武汉大学电子信息学院, 湖北武汉 430072

收稿日期:2020-11-23 出版日期:2022-01-01 发布日期:2022-01-19
通讯作者: 易本顺
作者简介:周安安(1991—), 男, 博士研究生, 主要研究方向为无线信道编码、分布式存储编码|易本顺(1965—), 男, 教授, 博士, 主要研究方向为多媒体网络通信、信源信道编码、无线通信|刘羽升(1993—), 男, 博士研究生, 主要研究方向为信道编码、图像处理、深度学习|罗来干(1995—), 男, 博士研究生, 主要研究方向为信道编码、图像处理、深度学习
基金资助:
国家自然科学基金(61371125);湖北省教育厅科学技术研究计划青年人才项目(Q20201902)

Novel construction of repairable fountain code in distributed storage systems

Anan ZHOU, Benshun YI*, Yusheng LIU, Laigan LUO

School of Electronic Information, Wuhan University, Wuhan 430072, China

Received:2020-11-23 Online:2022-01-01 Published:2022-01-19
Contact: Benshun YI

摘要/Abstract

摘要：

为了缓解可修复喷泉码(repairable fountain codes, RFC)编码包传输需消耗大量带宽资源的难题, 提出了一种基于改进压缩列存储算法的新型RFC构造方法(RFC based on improved compressed column storage, ICCS-RFC)。对于ICCS-RFC方案, 编码包的邻域信息被建模为序列, 并以生成矩阵的列为单位进行无损压缩。在保留可修复喷泉码性能的前提下, 该方案可以有效减少故障节点修复和源文件恢复所需的传输数据量。此外, 还提出了一种新的性能指标——有效吞吐量来分析ICCS-RFC方案的性能。理论分析和仿真结果验证了该方案的优越性能, 表明该方法能够显著降低有效吞吐量, 尤其是对于单故障节点修复的情况。

关键词: 可修复喷泉码, 生成矩阵, 压缩列存储, 有效吞吐量

Abstract:

In order to alleviate the large consumption of the bandwidth resource during the encoding packet transmission for repairable fountain codes (RFC), a novel construction of RFC based on improved compressed column storage algorithm (ICCS-RFC) is proposed. For the ICCS-RFC scheme, the neighbor information of coded packets is modeled as sequence and compressed losslessly by taking the columns of the generator matrix as unit. In the scenario of keeping the advantages of RFC, the scheme effectively reduces the amount of data transmitted of repairing the failed nodes and downloading the source file. In addition, a new performance evaluation index, named effective throughput, is proposed to analyze the performance of ICCS-RFC scheme. Theoretical analysis and simulation results verify the superiority of the proposed scheme, which can significantly improve the effectiveness of transmission and reduce the effective throughput, especially for repairing the single failure.

Key words: repairable fountain codes (RFC), generator matrix, compressed column storage, effective throughput

中图分类号:

TN911.22

周安安, 易本顺, 刘羽升, 罗来干. 分布式存储系统中新型可修复喷泉码构造[J]. 系统工程与电子技术, 2022, 44(1): 285-291.

Anan ZHOU, Benshun YI, Yusheng LIU, Laigan LUO. Novel construction of repairable fountain code in distributed storage systems[J]. Systems Engineering and Electronics, 2022, 44(1): 285-291.

图/表 7

图1

图2

图3

表1

图4

图5

图6

参考文献 31

1	REINSEL D, GANTZ J, RYDNING J. Data age 2025-IDC[EB/OL]. [2021-07-23]. https://www.seagate.com/files/www-content/our-story/trends/files/dataage-idc-report-final.pdf.
2	宫婧, 王文君. 大数据存储中的容错关键技术综述[J]. 南京邮电大学学报(自然科学版), 2014, 34 (4): 20- 25. doi: 10.3969/j.issn.1673-5439.2014.04.004
	GONG J , WANG W J . Fault tolerance technology for big data storage[J]. Journal of Nanjing University of Posts and Telecommunications (Natural Science), 2014, 34 (4): 20- 25. doi: 10.3969/j.issn.1673-5439.2014.04.004
3	王意洁, 许方亮, 裴晓强. 分布式存储中的纠删码容错技术研究[J]. 计算机学报, 2017, 40 (1): 236- 254.
	WANG Y J , XU F L , PEI X Q . Research on erasure code-based fault-tolerant technology for distributed storage[J]. Chinese Journal of Computers, 2017, 40 (1): 236- 254.
4	WANG Y J , LI S . Research and performance evaluation of data replication technology in distributed storage systems[J]. International Journal of Computers and Mathematics with Applications, 2006, 51 (11): 1625- 1632. doi: 10.1016/j.camwa.2006.05.002
5	WEATHERSPOON H, KUBIATOWICZ J. Erasure coding vs. replication: a quantitative comparison[C]//Proc. of the 1st International Workshop on Peer-to-Peer Systems, 2002: 328-337.
6	WANG J Z , LUO Y , SHU M K W . Storage and repair bandwidth tradeoff for heterogeneous cluster distributed storage systems[J]. Science China (Information Sciences), 2020, 63 (2): 131- 145.
7	LI Y Z, ZHOU J, WANG W P, et al. RE-store: reliable and efficient KV-store with erasure coding and replication[C]//Proc. of the IEEE International Conference on Cluster Computing, 2019.
8	Facebook. HDFS-RAID[EB/OL]. [2021-07-21]. https://wiki.apache.org/hadoop/HDFS-RAID.
9	TANG Y J , ZHANG X M . Fast en/decoding of reed-Solomon codes for failure recovery[J]. IEEE Trans.on Computers, 2021, 82 (5): 367- 381.
10	YU L L , LIN Z C , LIN S J , et al. Fast encoding algorithms for reed-Solomon codes with between four and seven parity symbols[J]. IEEE Trans.on Computers, 2020, 69 (5): 699- 705. doi: 10.1109/TC.2019.2963827
11	YE M , BARG A . Explicit constructions of high-rate MDS array codes with optimal repair bandwidth[J]. IEEE Trans.on Information Theory, 2017, 63 (4): 2001- 2014. doi: 10.1109/TIT.2017.2661313
12	HOLZBAUR L , PUCHINGER S , YAAKOBI E , et al. Partial MDS codes with regeneration[J]. IEEE Trans.on Information Theory, 2021, 425 (38): 3916- 3928.
13	XU Y, DU Q H, SONG H B. Security-enhanced wireless multicast via adaptive fountain codes over distributed caching network[C]//Proc. of the IEEE Smart World Ubiquitous Intelligence & Computing, Advanced & Trusted Computing, Scalable Computing & Communications, Cloud & Big Data Computing, Internet of People and Smart City Innovation, 2018: 8-12.
14	RECAVTE E , LAZARO F , LIVA G . Caching in heteroge-neous satellite networks with fountain codes[J]. International Journal of Satellite Communications and Networking, 2021, 32 (4): 218- 234.
15	DIMAKISA G , GODFREYP B , WU Y , et al. Network coding for distributed storage systems[J]. IEEE Trans.on Information Theory, 2010, 56 (9): 4539- 4551. doi: 10.1109/TIT.2010.2054295
16	RASHMI K V , SHAH N B , KUMAR P V . Optimal exact-regenerating codes for distributed storage at the MSR and MBR points via a product-matrix construction[J]. IEEE Trans.on Information Theory, 2011, 57 (8): 5227- 5239. doi: 10.1109/TIT.2011.2159049
17	OKPOTSE T, YOUSEFI S. Locality-aware fountain codes for massive distributed storage systems[C]//Proc. of the IEEE 14th Canadian Workshop on Information Theory, 2015: 18-21.
18	王静, 张崇, 梁伟, 等. 分布式存储系统中基于Pyramid码的局部性修复编码[J]. 电子测量与仪器学报, 2017, 31 (9): 1481- 1487.
	WANG J , ZHANG C , LIANG W , et al. Locally repairable codes based on pyramid codes in distributed storage systems[J]. Journal of Electronic Measurement and Instrumentation, 2017, 31 (9): 1481- 1487.
19	ZHU B G , LI H F . Exploring node repair locality in fractional repetition codes[J]. IEEE Communications Letters, 2016, 20 (12): 2350- 2353. doi: 10.1109/LCOMM.2016.2605100
20	TAN P , ZHOU Z C , SIDORENKO V , et al. Two classes of optimal LRCs with information (r, t)-locality[J]. Designs, Codes and Cryptography, 2020, 88, 1741- 1757. doi: 10.1007/s10623-020-00728-9
21	FU Q , LI R H , YANG S . Optimal (r, δ)-locally repairable codes from simplex code and gap code[J]. IEEE Access, 2020, 8, 215414- 215418. doi: 10.1109/ACCESS.2020.3040320
22	RAJPUT C , BHAINTWAL M . Cyclic LRC-LCD codes with hierarchical locality[J]. IEEE Communications letters, 2021, 25 (3): 711- 715. doi: 10.1109/LCOMM.2020.3040170
23	ASTERIS M , DIMAKIS A G . Repairable fountain codes[J]. IEEE Journal on Selected Areas in Communications, 2014, 32 (5): 1037- 1047. doi: 10.1109/JSAC.2014.140522
24	KUMAR S , ROSNES E , AMAT A G I . Secure repairable fountain codes[J]. IEEE Communications Letters, 2016, 20 (8): 1491- 1494. doi: 10.1109/LCOMM.2016.2574355
25	WANG Y , GU S S , ZHAO L , et al. Repairable fountain coded storage systems for multi-tier mobile edge caching networks[J]. IEEE Trans.on Network Science and Engineering, 2019, 14 (8): 396- 398.
26	BAIK J, SUH Y, SHIN M, et al. Locality-improved repairable fountain codes for distributed storage systems[C]//Proc. of the IEEE International Conference on Communication, 2020.
27	YANG J H , QIAN J X , ZHAO D F . The storage structure design of fountain code based on data compression[J]. Journal of Information and Computational Science, 2014, 11 (8): 2801- 2808. doi: 10.12733/jics20103589
28	袁博, 赵旦峰, 钱晋昔. WSN中降低喷泉码存储冗余量的方法研究[J]. 计算机工程, 2014, 40 (5): 68- 72. doi: 10.3969/j.issn.1000-3428.2014.05.015
	YUAN B , ZHAO D F , QIAN J X . Research on storage redundancy reduction method of fountain code in WSN[J]. Computer Engineering, 2014, 40 (5): 68- 72. doi: 10.3969/j.issn.1000-3428.2014.05.015
29	SHIRVANIMOGHADDAM M , LI Y H , VUCETIC B , et al. Binary compressive sensing via analog fountain coding[J]. IEEE Trans.on Signal Processing, 2015, 63 (24): 6540- 6552. doi: 10.1109/TSP.2015.2472362
30	LUUS F P S , MCDONALD A , MAHARAJ B T . Universal decremental redundancy compression with fountain codes[J]. SAIEE Africa Research Journal, 2010, 101 (2): 68- 80. doi: 10.23919/SAIEE.2010.8532229
31	MAHARAJ B T, LUUS F P S. Decremental redundancy compression with fountain codes[C]//Proc. of the IEEE International Conference on Wireless and Mobile Computing Networking and Communications, 2008: 328-332.

编码参数 (k, n)	数据量/bit		压缩比
编码参数 (k, n)	ICCS-RFC 编码前	ICCS-RFC 编码后	压缩比
(300, 750)	225 000	35 100	0.156 0
(700, 1 750)	1 225 000	101 500	0.082 9
(1 000, 2 500)	2 500 000	145 000	0.058 0
(1 500, 3 750)	5 625 000	264 000	0.046 9
(3 000, 7 500)	22 500 000	630 000	0.028 0
(6 000, 15 000)	90 000 000	1 482 000	0.016 5
(10 000, 25 000)	250 000 000	2 870 000	0.011 5

分布式存储系统中新型可修复喷泉码构造

Novel construction of repairable fountain code in distributed storage systems

RichHTML

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 31

相关文章 1

编辑推荐

Metrics

本文评价