Load balancing method based on local repair code in distributed storage

doi:10.11772/j.issn.1001-9081.2022010074

Journal of Computer Applications ›› 2023, Vol. 43 ›› Issue (3): 767-775.DOI: 10.11772/j.issn.1001-9081.2022010074

Special Issue: 数据科学与技术

• Data science and technology • Previous Articles Next Articles

Load balancing method based on local repair code in distributed storage

Yunbo LONG¹^,², Dan TANG³()

^1.Chengdu Institute of Computer Application，Chinese Academy of Sciences，Chengdu Sichuan 610041，China
^2.School of Computer Science and Technology，University of Chinese Academy of Sciences，Beijing 100049，China
^3.School of Software Engineering，Chengdu University of Information Technology，Chengdu Sichuan 610225，China

Received:2022-01-20 Revised:2022-03-19 Accepted:2022-03-21 Online:2022-04-21 Published:2023-03-10
Contact: Dan TANG
About author:LONG Yunbo， born in 1997， M. S. candidate. His research interests include distributed storage， coding theory.
Supported by:
Major Science and Technology Program of Sichuan Province(2019ZDZX0005)

分布式存储中基于局部修复码的负载均衡方法

龙运波¹^,², 唐聃³()

^1.中国科学院成都计算机应用研究所, 成都 610041
^2.中国科学院大学计算机科学与技术学院, 北京 100049
^3.成都信息工程大学软件工程学院, 成都 610225

通讯作者: 唐聃
作者简介:龙运波（1997—），男，贵州黔东南人，硕士研究生，主要研究方向：分布式存储、编码理论
唐聃（1982—），男，四川绵阳人，教授，博士，CCF会员，主要研究方向：编码理论、分布式存储。
基金资助:
四川省重大科技专项(2019ZDZX0005)

Abstract

Abstract:

For the low performance of hot data access in distributed storage， a load balancing method based on Local Repair Code （LRC） was proposed， which uses coding to avoid centralized access of nodes and improve the access efficiency of hot data. Firstly， a kind of special LRC suitable for small-scale storage systems was constructed by using Balanced Incomplete Block Design （BIBD）， and it was able to provide multiple access methods for encoded data. Secondly， based on Reed Solomon （RS） code and random array code， LRC was extended to a larger scale situation， and it was able to meet certain fault tolerance requirements of the storage system. Finally， a hot data access algorithm was given to reduce the pressure of hot data access， and combined with a reasonable data layout scheme， the load balancing of the storage system in high-frequency access scenarios was achieved. Theoretical analysis and experimental results show that the proposed method can achieve load balancing with very small cost， and its effect is significantly better than that of the load balancing method implemented by multiple copies and Maximum-Distance-Separable （MDS） code in the traditional method. Especially， the proposed method solves the load imbalance problem caused by uneven access to hot and cold data， which can effectively improve the access efficiency of hot data storage systems.

Key words: distributed storage, hot data, Local Repair Code (LRC), load balancing, data layout

摘要：

针对分布式存储中热数据访问性能低下的问题，提出一种基于局部修复码（LRC）的负载均衡方法，采用编码的方式规避节点的集中式访问，并提高热数据的访问效率。首先，利用平衡不完全区组设计（BIBD）构造一类适用于小规模存储系统的特殊LRC，从而为编码数据提供多种访问方式；然后，分别基于里所（RS）码和随机阵列码将LRC推广到更大规模，并使它满足存储系统一定的容错需求；最后，提出一种热数据访问算法以降低热数据的访问压力，并结合合理的数据布局方案实现存储系统在高频访问场景下的负载均衡。理论分析和实验结果表明，所提方法能以极小的代价实现负载均衡，明显优于传统方法中利用多副本及最大距离可分（MDS）码实现的负载均衡方法，尤其是解决了因冷热数据访问不均带来的负载失衡问题，可以有效提高热数据存储系统的访问效率。

关键词: 分布式存储, 热数据, 局部修复码, 负载均衡, 数据布局

CLC Number:

TP333.3

Yunbo LONG, Dan TANG. Load balancing method based on local repair code in distributed storage[J]. Journal of Computer Applications, 2023, 43(3): 767-775.

龙运波, 唐聃. 分布式存储中基于局部修复码的负载均衡方法[J]. 《计算机应用》唯一官方网站, 2023, 43(3): 767-775.

Figures/Tables 9

Tab. 1 An example of （15，15，3，3，1）-RBIBD

$ε 1$	$ε 2$	$ε 3$
$1,4, 11$	$2,10,12$	$7,10,14$
$6,13,14$	$1,3, 6$	$5,6, 8$
$2,5, 7$	$7,8, 11$	$2,11,13$
$3,9, 10$	$4,13,15$	$1,9, 15$
$8,12,15$	$5,9, 14$	$3,4, 12$

Tab. 1 An example of （15，15，3，3，1）-RBIBD

$ε 1$	$ε 2$	$ε 3$
$1,4, 11$	$2,10,12$	$7,10,14$
$6,13,14$	$1,3, 6$	$5,6, 8$
$2,5, 7$	$7,8, 11$	$2,11,13$
$3,9, 10$	$4,13,15$	$1,9, 15$
$8,12,15$	$5,9, 14$	$3,4, 12$

Fig. 1 Construction procedure for generated matrix G in example 3

Tab. 2 Generation formulas of local parity blocks in example 4

修复集1	修复集2
l₁=m₁⊕m₄⊕m₁₁	l₆=m₂⊕m₁₀⊕m₁₂
l₂=m₆⊕m₁₃⊕m₁₄	l₇=m₁⊕m₃⊕m₆
l₃=m₂⊕m₅⊕m₇	l₈=m₇⊕m₈⊕m₁₁
l₄=m₃⊕m₉⊕m₁₀	l₉=m₄⊕m₁₃⊕m₁₅
l₅=m₈⊕m₁₂⊕m₁₅	l₁₀=m₅⊕m₉⊕m₁₄

Fig. 2 Encoded data layout of a （25，15，3，2）-LRC

Fig. 3 Encoded data layout of a （30，15，3，2）-LRC

Tab. 3 Generation formulas of local parity blocks in example 5

修复集1	修复集2
$l 1 = α 15 m 1 ⊕ α 45 m 4 ⊕ α 115 m 11$	$l 6 = α 26 m 2 ⊕ α 106 m 10 ⊕ α 126 m 12$
$l 2 = α 65 m 6 ⊕ α 135 m 13 ⊕ α 145 m 14$	$l 7 = α 16 m 1 ⊕ α 36 m 3 ⊕ α 66 m 6$
$l 3 = α 25 m 2 ⊕ α 55 m 5 ⊕ α 75 m 7$	$l 8 = α 76 m 7 ⊕ α 86 m 8 ⊕ α 116 m 11$
$l 4 = α 35 m 3 ⊕ α 95 m 9 ⊕ α 105 m 10$	$l 9 = α 46 m 4 ⊕ α 136 m 13 ⊕ α 156 m 15$
$l 5 = α 85 m 8 ⊕ α 125 m 12 ⊕ α 155 m 15$	$l 10 = α 56 m 5 ⊕ α 96 m 9 ⊕ α 146 m 14$

Tab. 3 Generation formulas of local parity blocks in example 5

修复集1	修复集2
$l 1 = α 15 m 1 ⊕ α 45 m 4 ⊕ α 115 m 11$	$l 6 = α 26 m 2 ⊕ α 106 m 10 ⊕ α 126 m 12$
$l 2 = α 65 m 6 ⊕ α 135 m 13 ⊕ α 145 m 14$	$l 7 = α 16 m 1 ⊕ α 36 m 3 ⊕ α 66 m 6$
$l 3 = α 25 m 2 ⊕ α 55 m 5 ⊕ α 75 m 7$	$l 8 = α 76 m 7 ⊕ α 86 m 8 ⊕ α 116 m 11$
$l 4 = α 35 m 3 ⊕ α 95 m 9 ⊕ α 105 m 10$	$l 9 = α 46 m 4 ⊕ α 136 m 13 ⊕ α 156 m 15$
$l 5 = α 85 m 8 ⊕ α 125 m 12 ⊕ α 155 m 15$	$l 10 = α 56 m 5 ⊕ α 96 m 9 ⊕ α 146 m 14$

Fig. 4 Load distribution diagram of data blocks in case 1

Fig.5 Load distribution diagram of data blocks in case 2

Fig.6 Load balancing effect in experiment using MDS code

References 44

1	REINSEL D， GANTZ J， RYDNING J. Data age 2025： the digitization of the world from edge to core ［EB/OL］. ［2021-10-17］. .
2	DEAN J， BARROSO L A. The tail at scale［J］. Communications of the ACM， 2013， 56（2）： 74-80. 10.1145/2408776.2408794
3	刘世贤. 数据分区架构下负载均衡技术的研究与应用［D］. 杭州：浙江大学， 2010：27-42.
	LIU S X. Research and application on load balance of data based application partitioning［D］. Hangzhou： Zhejiang University， 2010：27-42.
4	BYERS J， CONSIDINE J， MITZENMACHER M. Simple load balancing for distributed Hash tables［C］// Proceedings of the 2003 International Workshop on Peer-to-Peer Systems， LNCS 2735. Berlin： Springer， 2003： 80-87.
5	李振宇，谢高岗. 基于DHT的P2P系统的负载均衡算法［J］. 计算机研究与发展， 2006， 43（9）： 1579-1585. 10.1360/crad20060914
	LI Z Y， XIE G G. A load balancing algorithm for DHT-based P2P systems［J］. Journal of Computer Research and Development， 2006， 43（9）： 1579-1585. 10.1360/crad20060914
6	周健，洪佩琳，李津生. DHT网络中一种基于树型结构的负载均衡方案［J］. 小型微型计算机系统， 2006， 27（11）： 2042-2046. 10.3969/j.issn.1000-1220.2006.11.012
	ZHOU J， HONG P L， LI J S. Tree-based load balancing method in DHT networks［J］. Mini-Micro Systems， 2006， 27（11）： 2042-2046. 10.3969/j.issn.1000-1220.2006.11.012
7	DATTA A， SCHMIDT R， ABERER K. Query-load balancing in structured overlays［C］// Proceedings of the 7th IEEE International Symposium on Cluster Computing and the Grid. Piscataway： IEEE， 2007：453-460. 10.1109/ccgrid.2007.90
8	孟宪福，陈晓令. 结构化P2P网络热点负载动态迁移策略［J］. 电子学报， 2011， 39（10）： 2407-2411. 10.1631/jzus.C0910717
	MENG X F， CHEN X L. Strategy for hotspot load dynamic migration in structured P2P networks［J］. Acta Electronica Sinica， 2011， 39（10）： 2407-2411. 10.1631/jzus.C0910717
9	陈晨. 结构化对等网络中访问热度引起的负载均衡技术研究［D］. 北京：北京交通大学， 2008：14-22.
	CHEN C. Research on load balancing caused by query hotspot based on structured peer-to-peer networks［D］. Beijing： Beijing Jiaotong University， 2008：14-22.
10	苏跃明，李晨，田丽华. 基于分片一致性哈希负载均衡策略与应用［J］. 计算机技术与发展， 2017， 27（11）： 62-65， 70. 10.3969/j.issn.1673-629X.2017.11.013
	SU Y M， LI C， TIAN L H. A consistent Hashing load balancing strategy based on fragmentation and its application［J］. Computer Technology and Development， 2017， 27（11）： 62-65， 70. 10.3969/j.issn.1673-629X.2017.11.013
11	HUANG L B， PAWAR S， ZHANG H， et al. Codes can reduce queueing delay in data centers［C］// Proceedings of the 2012 IEEE International Symposium on Information Theory. Piscataway： IEEE， 2012：2766-2770. 10.1109/isit.2012.6284026
12	JOSHI G， LIU Y P， SOLJANIN E. Coding for fast content download［C］// Proceedings of the 50th Annual Allerton Conference on Communication， Control， and Computing. Piscataway： IEEE， 2012：326-333. 10.1109/allerton.2012.6483236
13	FERNER U J， MÉDARD M， SOLJANIN E. Toward sustainable networking： storage area networks with network coding［C］// Proceedings of the 50th Annual Allerton Conference on Communication， Control， and Computing. Piscataway： IEEE， 2012：517-524. 10.1109/allerton.2012.6483262
14	JOSHI G， LIU Y P， SOLJANIN E. On the delay-storage trade-off in content download from coded distributed storage systems［J］. IEEE Journal on Selected Areas in Communications， 2014， 32（5）： 989-997. 10.1109/jsac.2014.140518
15	JOSHI G， SOLJANIN E， WORNELL G. Efficient redundancy techniques for latency reduction in cloud systems［J］. ACM Transactions on Modeling and Performance Evaluation Computing Systems， 2017， 2（2）： No.12. 10.1145/3055281
16	SHUAI Q Q， LI V O K. Latency analysis of flexible redundant scheme in MDS-coded distributed storage systems［C］// Proceedings of the 2017 IEEE Global Telecommunications Conference. Piscataway： IEEE， 2017：1-6. 10.1109/glocom.2017.8254038
17	SHUAI Q Q， LI V O K， LU Z Y. Which achieves lower latency with redundant requests， replication or coding？［C］// Proceedings of the 2017 IEEE Global Telecommunications Conference. Piscataway： IEEE， 2017：1-6. 10.1109/glocom.2017.8254986
18	HU Y C， NIU D. Reducing access latency in erasure coded cloud storage with local block migration［C］// Proceedings of the 35th IEEE Annual IEEE International Conference on Computer Communications. Piscataway： IEEE， 2016：1-9. 10.1109/infocom.2016.7524628
19	DING C W， WANG L， SUN L S. Load balancing technology based on erasure code in distributed storage system［C］// Proceedings of the 31st Chinese Control Conference. Piscataway： IEEE， 2012：5558-5563.
20	DIMAKIS A G， GODFREY P B， WU Y N， et al. Network coding for distributed storage systems［J］. IEEE Transactions on Information Theory， 2010， 56（9）： 4539-4551. 10.1109/tit.2010.2054295
21	HUANG C， CHEN M H， LI J. Pyramid codes： flexible schemes to trade space for access efficiency in reliable data storage systems［C］// Proceedings of the 6th IEEE International Symposium on Network Computing and Applications. Piscataway： IEEE， 2007：79-86. 10.1109/nca.2007.37
22	JIN L F， MA L M， XING C P. Construction of optimal locally repairable codes via automorphism groups of rational function fields［J］. IEEE Transactions on Information Theory， 2020， 66（1）： 210-221. 10.1109/tit.2019.2946637
23	LI X D， MA L M， XING C P. Optimal locally repairable codes via elliptic curves［J］. IEEE Transactions on Information Theory， 2019， 65（1）： 108-117. 10.1109/tit.2018.2844216
24	CAI H， MIAO Y， SCHWARTZ M， et al. On optimal locally repairable codes with super-linear length［J］. IEEE Transactions on Information Theory， 2020， 66（8）： 4853-4868. 10.1109/tit.2020.2977647
25	FANG W J， FU F W. Optimal cyclic （r， δ） locally repairable codes with unbounded length［J］. Finite Fields and Their Applications， 2020， 63： No.101650. 10.1016/j.ffa.2020.101650
26	CHEN B， XIA S T， HAO J， et al. Constructions of optimal cyclic （r， δ） locally repairable codes［J］. IEEE Transactions on Information Theory， 2018， 64（4）： 2499-2511. 10.1109/tit.2017.2761120
27	CHEN B， FANG W J， XIA S T， et al. Constructions of optimal （r， δ） locally repairable codes via constacyclic codes［J］. IEEE Transactions on Communications， 2019， 67（8）： 5253-5263. 10.1109/tcomm.2019.2916085
28	WANG A Y， ZHANG Z F. Repair locality with multiple erasure tolerance［J］. IEEE Transactions on Information Theory， 2014， 60（11）： 6979-6987. 10.1109/tit.2014.2351404
29	RAWAT A S， PAPAILIOPOULOS D S， DIMAKIS A G， et al. Locality and availability in distributed storage［J］. IEEE Transactions on Information Theory， 2016， 62（8）： 4481-4493. 10.1109/tit.2016.2524510
30	SU Y S. Design of membership matrices for （r， t）-availability in distributed storage［C］// Proceedings of the 2016 IEEE International Symposium on Information Theory. Piscataway： IEEE， 2016：998-1002. 10.1109/isit.2016.7541449
31	HAO J， XIA S T. Constructions of optimal binary locally repairable codes with multiple repair groups［J］. IEEE Communications Letters， 2016， 20（6）： 1060-1063. 10.1109/lcomm.2016.2539160
32	BALAJI S B， PRASANTH K P， KUMAR P V. Binary codes with locality for multiple erasures having short block length［C］// Proceedings of the 2016 IEEE International Symposium on Information Theory. Piscataway： IEEE， 2016：655-659. 10.1109/isit.2016.7541380
33	ZHANG Y， KAN H B. Locally repairable codes with strict availability from linear functions［J］. Science China Information Sciences， 2018， 61（10）： No.109304. 10.1007/s11432-018-9444-4
34	ZHANG Y， KAN H B. Locally repairable codes from combinatorial designs［J］. Science China Information Sciences， 2020， 63（2）： No.122304. 10.1007/s11432-019-2649-5
35	TAMO I， BARG A， FROLOV A. Bounds on the parameters of locally recoverable codes［J］. IEEE Transactions on Information Theory， 2016， 62（6）： 3070-3083. 10.1109/tit.2016.2518663
36	BALAJI S B， KUMAR P V. Bounds on the rate and minimum distance of codes with availability［C］// Proceedings of the 2017 IEEE International Symposium on Information Theory. Piscataway： IEEE， 2017：3155-3159. 10.1109/isit.2017.8007111
37	KADHE S， SOLJANIN E， SPRINTSON A. When do the availability codes make the stored data more available？［C］// Proceedings of the 53rd Annual Allerton Conference on Communication， Control， and Computing. Piscataway： IEEE， 2015：956-963. 10.1109/allerton.2015.7447111
38	AKTAŞ M F， NAJM E， SOLJANIN E. Simplex queues for hot-data download［C］// Proceedings of the 2017 ACM SIGMETRICS / International Conference on Measurement and Modeling of Computer Systems. New York： ACM， 2017：35-36. 10.1145/3078505.3078553
39	AL-ABBASI A O， AGGARWAL V. TTLCache： taming latency in erasure-coded storage through TTL caching［J］. IEEE Transactions on Network and Service Management， 2020， 17（3）： 1582-1596. 10.1109/tnsm.2020.2998175
40	AKTAŞ M， JOSHI G， KADHE S， et al. Service rate region： a new aspect of coded distributed system design［J］. IEEE Transactions on Information Theory， 2021， 67（12）： 7940-7963. 10.1109/tit.2021.3117695
41	KADHE S， SOLJANIN E， SPRINTSON A. Analyzing the download time of availability codes［C］// Proceedings of the 2015 IEEE International Symposium on Information Theory. Piscataway： IEEE， 2015：1467-1471. 10.1109/isit.2015.7282699
42	AKTAŞ M F， KADHE S， SOLJANIN E， et al. Download time analysis for distributed storage codes with locality and availability［J］. IEEE Transactions on Communications， 2021， 69（6）： 3898-3910. 10.1109/tcomm.2021.3067054
43	滕鹏国，张景中，陈亮，等. 随机阵列码：一种高容灾易扩展的RAID存储容灾方法［J］. 工程科学与技术， 2017， 49（3）： 110-116. 10.15961/j.jsuese.201600492
	TENG P G， ZHANG J Z， CHEN L， et al. Random RAID： a RAID storage scheme with high fault-tolerance and flexibility［J］. Advanced Engineering Sciences， 2017， 49（3）： 110-116. 10.15961/j.jsuese.201600492
44	BARAT J. Combinatorics of symmetric designs［J］. Acta Scientiarum Mathematicarum， 2008， 74（3/4）： 945-946.

[1]	Ruixuan NI, Miao CAI, Baoliu YE. DFS-Cache： memory-efficient and persistent client cache for distributed file systems [J]. Journal of Computer Applications, 2024, 44(4): 1172-1180.
[2]	Ming ZHANG, Le FU, Haifeng WANG. Relay control model for concurrent data flow in edge computing [J]. Journal of Computer Applications, 2024, 44(12): 3876-3883.
[3]	Yanan SUN, Jiehong WU, Junling SHI, Lijun GAO. Multi-UAV collaborative task assignment method based on improved self-organizing map [J]. Journal of Computer Applications, 2023, 43(5): 1551-1556.
[4]	Li YANG, Jianting CHEN, Yang XIANG. Performance optimization strategy of distributed storage for industrial time series big data based on HBase [J]. Journal of Computer Applications, 2023, 43(3): 759-766.
[5]	Na ZHOU, Ming CHENG, Menglin JIA, Yang YANG. Medical image privacy protection based on thumbnail encryption and distributed storage [J]. Journal of Computer Applications, 2023, 43(10): 3149-3155.
[6]	ZHAO Quan, TANG Xiaochun, ZHU Ziyu, MAO Anqi, LI Zhanhuai. Low-latency cluster scheduling framework for large-scale short-time tasks [J]. Journal of Computer Applications, 2021, 41(8): 2396-2405.
[7]	QING Xinyi, CHEN Yuling, ZHOU Zhengqiang, TU Yuanchao, LI Tao. Blockchain storage expansion model based on Chinese remainder theorem [J]. Journal of Computer Applications, 2021, 41(7): 1977-1982.
[8]	YANG Ling, JIANG Chunmao. Strategy of energy-aware virtual machine migration based on three-way decision [J]. Journal of Computer Applications, 2021, 41(4): 990-998.
[9]	XU Hongliang, YANG Guiqin, JIANG Zhanjun. Data center adaptive multi-path load balancing algorithm based on software defined network [J]. Journal of Computer Applications, 2021, 41(4): 1160-1164.
[10]	Cui LI, Qingkui CHEN. Dynamic monitoring model based on DPDK parallel communication [J]. Journal of Computer Applications, 2020, 40(2): 335-341.
[11]	ZHANG Hang, LIU Shanzheng, TANG Dan, CAI Hongliang. Erasure code with low recovery-overhead in distributed storage systems [J]. Journal of Computer Applications, 2020, 40(10): 2942-2950.
[12]	ZHANG Guochao, WANG Ruijin. Blockchain shard storage model based on threshold secret sharing [J]. Journal of Computer Applications, 2019, 39(9): 2617-2622.
[13]	LI Zhuhong, ZHAO Canming, YAN Long, ZHANG Xinming. Load balancing opportunistic routing protocol for power line communication network in smart grids [J]. Journal of Computer Applications, 2019, 39(3): 812-816.
[14]	WANG Zewu, SUN Lei, GUO Songhui, SUN Ruichen. Scheduling method of virtual cipher machine based on entropy weight evaluation in cryptography cloud [J]. Journal of Computer Applications, 2018, 38(5): 1353-1359.
[15]	FU Chaojiang, WANG Tianqi, LIN Yuerong. Parallel algorithm for explicit finite element analysis based on efficient parallel computational strategy [J]. Journal of Computer Applications, 2018, 38(4): 1072-1077.

Load balancing method based on local repair code in distributed storage

分布式存储中基于局部修复码的负载均衡方法

RichHTML

PDF

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 9

References 44

Related Articles 15

Recommended Articles

Metrics