Novel Data Placement Algorithm for Distributed Storage System  Based on Fault-Tolerant Domain

doi:10.1007/s12204-020-2253-5

Abstract

Abstract: The 3-replica redundancy strategy is widely used to solve the problem of data reliability in large-scale distributed storage systems. However, its storage capacity utilization is only 33%. In this paper, a data placement algorithm based on fault-tolerant domain (FTD) is proposed. Owing to the fine-grained design of the FTD, the data reliability of systems using two replicas is comparable to that of current mainstream systems using three replicas, and the capacity utilization is increased to 50%. Moreover, the proposed FTD provides a new concept for the design of distributed storage systems. Distributed storage systems can take FTDs as the units for data placement, data migration, data repair and so on. In addition, fault detection can be performed independently and concurrently within the FTDs.

摘要： The 3-replica redundancy strategy is widely used to solve the problem of data reliability in large-scale distributed storage systems. However, its storage capacity utilization is only 33%. In this paper, a data placement algorithm based on fault-tolerant domain (FTD) is proposed. Owing to the fine-grained design of the FTD, the data reliability of systems using two replicas is comparable to that of current mainstream systems using three replicas, and the capacity utilization is increased to 50%. Moreover, the proposed FTD provides a new concept for the design of distributed storage systems. Distributed storage systems can take FTDs as the units for data placement, data migration, data repair and so on. In addition, fault detection can be performed independently and concurrently within the FTDs.

CLC Number:

TP 391

SHI Lianxing (石连星), WANG Zhiheng (王志恒), LI Xiaoyong (李小勇) . Novel Data Placement Algorithm for Distributed Storage System Based on Fault-Tolerant Domain[J]. J Shanghai Jiaotong Univ Sci, 2021, 26(4): 463-470.

References 16

[1]	PINHEIRO E, WEBER W D, BARROSO L A.Failure trends in a large disk drive population[C]//Proceedings of the 5th USENIX Conference onFile and Storage Technologies (FAST ’07). San Jose,CA, USA: USENIX Association, 2007: 17-29.
[2]	CHEMAWAT S, GOBIOFF H, LEUNG S T. TheGoogle file system [J]. ACM SIGOPS Operating SystemsReview, 2003, 37(5): 29-43.
[3]	SHVACHKO K, KUANG H R, RADIA S, et al. Thehadoop distributed file system [C]//2010 IEEE 26thSymposium on Mass Storage Systems and Technologies(MSST). Washington, DC, USA: IEEE, 2010: 1-10.
[4]	WEIL S A, BRANDT S A, MILLER E L, et al. Ceph:A scalable, high-performance distributed file system[C]// Proceedings of the 7th Symposium on OperatingSystems Design and Implementation. Seattle, WA,USA: USENIX Association, 2006: 307-320.
[5]	ADYA A, J. BOLOSKY W J, CASTRO M, et al.Farsite: Federated, available, and reliable storage foran incompletely trusted environment [C]//Proceedingsof the 5th symposium on Operating systems designand implementation (OSDI 2002). Boston, MA, USA:ACM, 2002, 36: 1-14.
[6]	YANG S L, ZHANG G Y. Review of data recovery instorage systems based on erasure codes [J]. Journal ofFrontiers of Computer Science and Technology, 2017,11(10): 1531-1544(in Chinese).
[7]	REED I S, SOLOMON G. Polynomial codes over certainfinite fields [J]. Journal of the Society for Industrialand Applied Mathematics, 1960, 8(2): 300-304.
[8]	WEIL S A, BRANDT S A, MILLER E L, et al.CRUSH: Controlled, scalable, decentralized placementof replicated data [C]//Proceedings of the 2006ACM/IEEE Conference on Supercomputing. Tampa,USA: ACM, 2006: 122-133.
[9]	HONICKY R J, MILLER E L. Replication under ucalableuashing: A family of algorithms for scalable decentralizeddata distribution [C]//Proceedings of 18thInternational Parallel and Distributed Processing Symposium(IPDPS 2004). Santa Fe, NM, USA: IEEE,2004: 1-10.
[10]	The OpenStack Foundation. Swift’s overview andconcepts: The rings [EB/OL]. (2019-10-26) [2019-10-30]. https://docs.openstack.org/swift/latest/overviewring.html.
[11]	XIN Q, MILLER E L, SCHWARZ S J T J E. Evaluationof distributed recovery in large-scale storage systems[C]//Proceedings of the 13th IEEE InternationalSymposium on High Performance Distributed Computing.Washington, DC, USA: IEEE, 2004: 172-181.
[12]	BACHWANI R, GRYZ L, BIANCHINI R, et al.Dynamically quantifying and improving the reliabilityof distributed storage systems [C]//Proceedings ofthe 27th Symposium on Reliable Distributed Systems.Naples, Italy: IEEE, 2008: 85-94.
[13]	BANERJEE S, DAS A, MAZUMDER A, et al. Onthe impact of coding parameters on storage requirementof region-based fault tolerant distributed file systemdesign [C]//Proceedings of the 2014 InternationalConference on Computing, Networking and Communications(ICNC). Washington, DC, USA: IEEE, 2014:78-82.
[14]	LIAN Q, CHEN W, ZHANG Z. On the impact ofreplica placement to the reliability of distributed brickstorage systems [C]//25th IEEE International Conferenceon Distributed Computing Systems (ICDCS ’05).Washington, DC, USA: IEEE, 2005: 187-196.
[15]	ZHANG L F, TAN X J, DU K. Optimal reliabilityanalysis for large scale storage systems [J]. ComputerEngineering and Applications, 2013, 49(1): 112-119(in Chinese).
[16]	KARGER D, LEHMAN E, LEIGHTON T, et al. Consistent hashing and random trees: Distributed cachingprotocols for relieving hot spots on the World WideWeb [C]//Proceedings of the 29th annual ACM symposiumon Theory of computing. El Paso, Texas, USA:ACM, 1997: 654-663.

Novel Data Placement Algorithm for Distributed Storage System Based on Fault-Tolerant Domain

Novel Data Placement Algorithm for Distributed Storage System Based on Fault-Tolerant Domain

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

References 16

Related Articles 15

Recommended Articles

Metrics

Comments

[1]	WEI Maohua, YANG Ling, WENG Liangtao, YANG Jipei, CHEN Yongqiao. SOC Balancing Strategy for Distributed Energy Storage Units in Isolated DC Microgrids Considering Capacity Differences [J]. Journal of Shanghai Jiao Tong University, 2025, 59(3): 376-387.
[2]	YIN Gaowen, SHEN Feifan, HUANG Sheng, WEI Juan, QU Yinpeng, WANG Pengda. Dispatching Method of Combined Wind-Storage System for Multi-Time Scale Scenarios Application in Electricity Markets [J]. Journal of Shanghai Jiao Tong University, 2024, 58(9): 1410-1419.
[3]	QIU Gefei, FENG Zehua, SHEN Fu, HE Chao, HE Honghui, LIU Kaiming. Dynamic Double-Layer Energy Management Strategy for Park Power Grid Considering Vehicle-to-Grid [J]. Journal of Shanghai Jiao Tong University, 2024, 58(6): 916-925.
[4]	CHEN Hui, HE Gengsheng, LIU Yuliang, ZENG Hongmei, ZHANG Shixu, LI Yaowang. Capacity Allocation Strategy of Energy Storage in Low-Carbon Park Considering Equivalent Energy Storage Characteristics of Thermal System [J]. Journal of Shanghai Jiao Tong University, 2024, 58(6): 863-871.
[5]	ZHANG Cheng, JU Changjiang, XIONG Can, YANG Genke. Optimization of Lithium Battery Lifetime Based on Dual-Stage Active Topology [J]. Journal of Shanghai Jiao Tong University, 2024, 58(5): 719-729.
[6]	XU Liangye, SHI Lianxing, SHAN Rongsheng. A Consistency Checking Method for Erasure-Coded Striped Data [J]. Journal of Shanghai Jiao Tong University, 2024, 58(4): 579-584.
[7]	WANG Jing, LI Jinghui, YANG Jiarong, WANG E. Construction of Optimal Locally Repairable Codes of Triangular Association Schemes [J]. Journal of Shanghai Jiao Tong University, 2024, 58(10): 1596-1605.
[8]	LIU Chuanbin, JIAO Wenshu, WU Qiuwei, CHEN Jian, ZHOU Qian. Strategy of Wind-Storage Combined System Participating in Power System Secondary Frequency Regulation Based on Model Predictive Control [J]. Journal of Shanghai Jiao Tong University, 2024, 58(1): 91-101.
[9]	FAN Hong, WANG Lankun, XING Mengqing, TIAN Shuxin, YU Weinan. Coordinated Scheduling of Multiple Buildings with Electric-Hydrogen Complementary Considering Frequency Stability Constraints [J]. Journal of Shanghai Jiao Tong University, 2023, 57(12): 1559-1570.
[10]	LI Qian, JIANG Xin, ZHANG Junzhao, DUAN Shijie, JIN Yang. Business Models for Large-Scale Energy Storage Systems to Participate in Electricity Spot Market [J]. Journal of Shanghai Jiao Tong University, 2023, 57(12): 1543-1558.
[11]	YAN Qing, LU Jiansha, JIANG Weiguang, SHAO Yiping, TANG Hongtao, LI Yingde. Path Optimization of Stacker in Compact Storage System with Dual-Port Layout [J]. Journal of Shanghai Jiao Tong University, 2022, 56(7): 858-867.
[12]	YANG Bo, WANG Junting, YU Lei, CAO Pulin, SHU Hongchun, YU Tao. Peafowl Optimization Algorithm Based Bi-Level Multi-Objective Optimal Allocation of Energy Storage Systems in Distribution Network [J]. Journal of Shanghai Jiao Tong University, 2022, 56(10): 1294-1307.
[13]	TANG Shengjing, SHI Songwei, ZHANG Yao, ZHOU Liang. Review on the Development of Intelligence-based Distributed Cooperative Operational System [J]. Air & Space Defense, 2019, 2(1): 6-13.
[14]	MA Yiwei (马艺玮), ZHOU Yanmei (周焰梅), ZHANG Jin'ai (张锦爱), PIAO Changhao (朴昌浩) . Economic Dispatch of Islanded Microgrid Considering a Cooperative Strategy Between Diesel Generator and Battery Energy Storage System [J]. Journal of Shanghai Jiao Tong University (Science), 2018, 23(5): 593-599.
[15]	ZHENG Yang,CHEN Haibo,ZANG Binyu. Snooping-Based Distributed Shared Memory [J]. Journal of Shanghai Jiaotong University, 2018, 52(10): 1333-1338.