分布式存储中新型分组piggybacking框架

doi:10.19665/j.issn1001-2400.2023.03.013

Abstract

Abstract:

With the rapid development of Internet technology,the explosive growth of the global data volume has led to a serious challenge to the reliability and availability of distributed storage systems.As an efficient data fault-tolerant technology,the piggybacking framework has become a research hotspot in recent years.Most piggybacking frameworks reduce the repair bandwidth by sacrificing the number of substripes and the repair degree,in which the amount of data saved in the process of repairing ineffective nodes usually cannot effectively improve the disk reading efficiency.For the above situation,a novel grouped piggybacking framework is proposed,which can reduce both the number of substripes and the repair degree of information nodes while ensuring a low repair bandwidth,thereby improving the Input/Output(I/O) performance of distributed storage systems.In the novel framework,the parity nodes are divided into two parts,and information symbols and parity symbols are grouped according to certain rules so as to be piggybacked into the corresponding parity nodes.The process is simple to implement.Using the proposed framework,information nodes and parity nodes can be effectively repaired at the same time,which not only reduces the number of substripes,but also makes it to have a strong comprehensive repair ability when the number of parity nodes is large.Compared with other piggybacking frameworks,the new grouped piggybacking framework can better balance the repair bandwidth,the repair degree and the number of substripes,and is suitable for application in actual systems.

Key words: distributed storage, piggybacking framework, the number of substripes, repair degree, repair bandwidth

CLC Number:

TN911.22

WANG Yubo,SUN Rong,LIU Jingwei. New grouped piggybacking framework for distributed storage[J].Journal of Xidian University, 2023, 50(3): 132-141.

Figures/Tables 7

piggybacking 框架	子条带数	信息节点平均修复带宽比率	校验节点平均修复带宽比率	信息节点平均修复度比率
OOP^[9]	t+r-1	$t 2 + t + r - 1 t 2 + t r + r - 1$	$r (t + 2) - 2 r (t + r - 1)$ + $(r - 2) (r - 1) 2 r k (t + r - 1)$	$k + r - 1 k$
NSPB^[10]	r	$L 2 r$ + $1 L$ - $1 2 L r$	$k + r k r$ + $(k r - k - r) (L + 1) k r 2$ + $2 (r - L - 1) 2 k (4 r - 3 - L)$	$(k + r) k - ∑ l = 1 L l φ l k 2$
NPB^[11]	r	$L 2 r$ + $1 L$ - $3 2 L r$ + $1 L 2 r$	$1 k r 2 y + k L r + y 2 + v (x - v) x + (r - L) (k - v u)$ ,v≥r-L $1 k r 2 y + k L r + y 2 + v (x - v) x + (r - L) (k - v l)$ ,v<r-L	$(k + r) k - ∑ l = 1 L l φ l + φ L k 2$

References 13

[1]	李鑫, 孙蓉, 刘景伟. 分布式存储系统中容错技术综述[J]. 无线电通信技术, 2019, 45(5):463-475.
	LI Xin, SUN Rong, LIU Jingwei. Overview of Fault-Tolerant Techniques in Distributed Storage Systems[J]. Radio Communications Technology, 2019, 45(5):463-475.
[2]	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. doi: 10.1109/TIT.2010.2054295
[3]	PAPAILIOPOULOS D S, DIMAKIS A G. Locally Repairable Codes[J]. IEEE Transactions on Information Theory, 2014, 60(10):5843-5855. doi: 10.1109/TIT.2014.2325570
[4]	RASHMI K V, SHAH N B, RAMCHANDRAN K. A Piggybacking Design Framework for Read-and Download-Efficient Distributed Storage Codes[C]//Proceedings of the 2013 IEEE International Symposium on Information Theory. Piscataway:IEEE, 2013:331-335.
[5]	SHANGGUAN C, GE G. A New Piggybacking Design for Systematic MDS Storage Codes[J]. Designs,Codes and Cryptography, 2019, 87(12):2753-2770. doi: 10.1007/s10623-019-00650-9
[6]	YUAN S, HUANG Q. Generalized Piggybacking Codes for Distributed Storage Systems[C]//Proceedings of the 2016 IEEE Global Communications Conference. Piscataway:IEEE, 2016:1-6.
[7]	张璐, 孙蓉, 刘景伟. 分布式存储中的克隆piggybacking框架[J]. 西安电子科技大学学报, 2020, 47(6):139-147.
	ZHANG Lu, SUN Rong, LIU Jingwei. Cloned Piggybacking Framework for Distributed Storage[J]. Journal of Xidian University, 2020, 47(6):139-147.
[8]	JIANG Z, HOU H, HAN Y S, et al. An Efficient Piggybacking Design with Lower Repair Bandwidth and Lower Sub-Packetization[C]//Proceedings of the 2021 IEEE International Symposium on Information Theory. Piscataway:IEEE, 2021:2328-2333.
[9]	LI G Y, LIN X, TANG X. An Efficient One-to-One Piggybacking Design for Distributed Storage Systems[J]. IEEE Transactions on Communications, 2019, 67(12):8193- 8205. doi: 10.1109/TCOMM.26
[10]	SUN R, ZHANG L, LIU J. A New Piggybacking Design with Low-Repair Bandwidth and Complexity[J]. IEEE Communications Letters, 2021, 25(7):2099-2103. doi: 10.1109/LCOMM.2021.3071855
[11]	SHI H, HOU H, HAN Y S, et al. New Piggybacking Codes with Lower Repair Bandwidth for Any Single-Node Failure[C]//Proceedings of the 2022 IEEE International Symposium on Information Theory. Piscataway:IEEE, 2022:2601-2606.
[12]	RASHMI K. Erasure Coding for Big-Data Systems:Theory and Practice:UCB/EECS-2016-155[R]. Berkeley: University of California, Berkeley, 2016.
[13]	SHAH N B, RASHMI K V, KUMAR P V, et al. Distributed Storage Codes with Repair-by-Transfer and Nonachievability of Interior Points on the Storage-Bandwidth Tradeoff[J]. IEEE Transactions on Information Theory, 2012, 58(3):1837-1852. doi: 10.1109/TIT.2011.2173792

New grouped piggybacking framework for distributed storage

RichHTML

PDF (PC)

Like

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 7

References 13

Related Articles 5

Metrics

Comments

Recommended 10

[1]	DAI Mingjun,LI Xiaofeng,DENG Haiyan,CHEN Bin. Private information retrieval with low encoding/decoding complexity [J]. Journal of Xidian University, 2021, 48(6): 212-220.
[2]	YANG Yanbo,ZHANG Jiawei,MA Jianfeng. Method for using the blockchain to protect data privacy of IoV [J]. Journal of Xidian University, 2021, 48(3): 21-30.
[3]	ZHANG Lu,SUN Rong,LIU Jingwei. Cloned piggybacking framework for distributed storage [J]. Journal of Xidian University, 2020, 47(6): 139-147.
[4]	HAO Xiaohui;CHE Shuling;ZHANG Xinyu. In-depth analysis of bounds on the minimum distance of LRCs [J]. Journal of Xidian University, 2018, 45(5): 75-79+135.
[5]	ZHANG Wei1,2;MA Jian-feng2;YANG Xiao-yuan1. Reliability of distributed storage systems [J]. J4, 2009, 36(3): 480-485.