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

doi:10.19665/j.issn1001-2400.2023.03.013

西安电子科技大学学报 ›› 2023, Vol. 50 ›› Issue (3): 132-141.doi: 10.19665/j.issn1001-2400.2023.03.013

• 计算机科学与技术 & 网络空间安全 • 上一篇下一篇

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

王禹博¹(),孙蓉^1,²(),刘景伟³()

1.西安电子科技大学空天地一体化综合业务网全国重点实验室,陕西西安 710071
2.华侨大学厦门市移动多媒体通信重点实验室,福建厦门 361021
3.西安电子科技大学陕西省区块链与安全计算重点实验室,陕西西安 710071

收稿日期:2022-08-16 出版日期:2023-06-20 发布日期:2023-10-13
通讯作者: 孙蓉
作者简介:王禹博(1999—),男,西安电子科技大学硕士研究生,E-mail:ybwang21@stu.xidian.edu.cn；|刘景伟(1978—),男,副教授,博士,E-mail: jwliu@mail.xidian.edu.cn
基金资助:
国家重点研发计划(2021YFA000500);国家自然科学基金(62171356);陕西省重点研发计划-重点产业创新链项目(2020ZDLGY05-04);陕西省重点研发计划-重点产业创新链项目(2021ZDLGY05-03)

New grouped piggybacking framework for distributed storage

WANG Yubo¹(),SUN Rong^1,²(),LIU Jingwei³()

1. State Key Laboratory of Integrated Services Networks,Xidian University,Xi’an 710071,China
2. Xiamen Key Laboratory of Mobile Multimedia Communications,Huaqiao University,Xiamen 361021,China
3. Shaanxi Key Laboratory of Blockchain and Secure Computing,Xidian University,Xi’an 710071,China

Received:2022-08-16 Online:2023-06-20 Published:2023-10-13
Contact: Rong SUN

摘要/Abstract

摘要：

随着互联网技术的快速发展,全球数据量爆炸式增长对分布式存储系统的可靠性和可用性提出了严峻的挑战。Piggybacking框架作为一种高效的数据容错技术成为近年来研究的热点。目前,绝大多数piggybacking框架均以牺牲子条带数和修复度的方式来降低修复带宽,导致修复失效节点过程中所节省的数据量通常无法有效地提升磁盘读取效率。针对上述情况,提出一种新型分组piggybacking框架,在保证较低修复带宽的同时,进一步降低了子条带数和信息节点修复度,从而提升分布式存储系统的输入/输出性能。该框架将校验节点分为两个部分,信息符号和校验符号分别按照一定规则分组后依次嵌入到对应的校验节点中,设计简单。通过这种设计,可以同时有效修复信息节点和校验节点,既减少了子条带数,又使其在校验节点个数较多时拥有较强的综合修复能力。与其他piggybacking框架相比,新型分组piggybacking框架能更好地权衡修复带宽、修复度与子条带数,适合在实际系统中应用。

关键词: 分布式存储, piggybacking框架, 子条带数, 修复度, 修复带宽

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

中图分类号:

TN911.22

王禹博,孙蓉,刘景伟. 分布式存储中新型分组piggybacking框架[J]. 西安电子科技大学学报, 2023, 50(3): 132-141.

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

图/表 7

图1

图2

图3

图4

表1

3种待比较piggybacking框架的子条带数、平均修复带宽比率和平均修复度比率"

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$

表1

图5

图6

参考文献 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

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

New grouped piggybacking framework for distributed storage

RichHTML

PDF (PC)

赞

可视化

摘要/Abstract

引用本文

使用本文

图/表 7

参考文献 13

相关文章 5

Metrics

本文评价

推荐阅读 10

[1]	代明军,李晓凤,邓海燕,陈彬. 具有低编解码复杂度的私有信息检索[J]. 西安电子科技大学学报, 2021, 48(6): 212-220.
[2]	杨颜博,张嘉伟,马建峰. 一种使用区块链保护车联网数据隐私的方法[J]. 西安电子科技大学学报, 2021, 48(3): 21-30.
[3]	张璐,孙蓉,刘景伟. 分布式存储中的克隆piggybacking框架[J]. 西安电子科技大学学报, 2020, 47(6): 139-147.
[4]	王祥旭,车书玲,纪玉晖. 一种有效的局部可修复码的构造方法[J]. 西安电子科技大学学报, 2019, 46(3): 26-31.
[5]	郝晓慧;车书玲;张欣瑜. LRC码最小距离限的深入分析[J]. 西安电子科技大学学报, 2018, 45(5): 75-79+135.