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

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

Abstract

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

CLC Number:

TN911.22

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.

Figures/Tables 7

Fig.1

Fig.2

Fig.3

Table 1

Fig.4

Fig.5

Fig.6

References 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

[1]	Renzhi WANG, Kegang PAN, Ruixiang ZHAO. Optimal design of LDPC codes in frequency hopping anti-jamming communication system [J]. Systems Engineering and Electronics, 2022, 44(11): 3548-3555.
[2]	Xinying DAI, Jianping WANG. Optimization of combined degree distribution of LT codes based on output ripple size [J]. Systems Engineering and Electronics, 2020, 42(3): 727-732.
[3]	GUO Li-li, YUE Dian-wu, YAN Qiu-na. Asynchronous cooperative transmission scheme for wireless sensor networks [J]. Journal of Systems Engineering and Electronics, 2009, 31(10): 2331-2335.
[4]	ZHAO Cheng-lin, PENG Xiu-ping, XU Cheng-qian. Study on the characters of perfect ternary array pairs [J]. Journal of Systems Engineering and Electronics, 2009, 31(5): 1030-1034.
[5]	SUN Juan-juan, WU Jian-wei. Method on sampling & analysis of field test data in mobile communications network [J]. Journal of Systems Engineering and Electronics, 2009, 31(01): 229-232.
[6]	SUN Juan-juan, WU Jian-wei. Method on sampling & analysis of field test data in mobile communications network [J]. Journal of Systems Engineering and Electronics, 2009, 31(1): 229-232.

Novel construction of repairable fountain code in distributed storage systems

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 7

References 31

Related Articles 6

Recommended Articles

Metrics

Comments