Fast Repair of Faulty Nodes Based on Graph Factorization
Author:
  • Article
  • | |
  • Metrics
  • |
  • Reference [25]
  • |
  • Related [20]
  • | | |
  • Comments
    Abstract:

    To improve the efficiency of repairing faulty nodes in a distributed storage system, this study proposes a new construction algorithm for fractional repetition (FR) codes. The algorithm resorts to the factorization of the complete graph for node construction, and the nodes constructed are referred to as complete graph factorization based FR (CGFBFR) nodes. Specifically, the complete graph is factorized, and the number of factors generated from the complete graph after the factorization is completed is determined. The number of factors of the complete graph is selected according to the repetition degrees of the data blocks that need to be stored. All the vertices of the selected factors of the complete graph are regarded as the data blocks that need to be stored in the distributed storage system. Then, the edges of the selected factor graph are marked and stored as distributed data nodes. Finally, an encoding matrix is generated with the vertices and edges of the selected factors, and the distributed storage system stores the data blocks respectively according to the data in the encoding matrix. The experimental simulation results show that compared with the Reed-Solomon (RS) codes, the simple regenerating codes (SRCs), and the latest cyclic variable FR (VFR) codes in the distributed storage system, the codes generated by the new FR code construction algorithm proposed in this study can quickly repair the faulty node when the system repairs the node. The proposed algorithm can be widely applied to distributed storage systems as it reduces the repair bandwidth overhead, repair locality, and repair complexity of the faulty node, provides a simple construction process, and allows flexible selection of construction parameters.

    Reference
    [1] Siddiqa A, Karim A, Gani A. Big data storage technologies: A survey. Frontiers of Information Technology & Electronic Engineering, 2017, 18(8): 1040–1070
    [2] Mazumdar S, Seybold D, Kritikos K, et al. A survey on data storage and placement methodologies for cloud-big data ecosystem. Journal of Big Data, 2019, 6(1): 15. [doi: 10.1186/s40537-019-0178-3
    [3] Lv Z, Li X, Lv H, et al. BIM big data storage in WebVRGIS. IEEE Transactions on Industrial Informatics, 2019, 16(4): 2566–2573
    [4] Li RN, Song TY, Mei B, et al. Blockchain for large-scale Internet of Things data storage and protection. IEEE Transactions on Services Computing, 2019, 12(5): 762–771. [doi: 10.1109/TSC.2018.2853167
    [5] Yang Y, Zheng XH, Guo WZ, et al. Privacy-preserving smart IoT-based healthcare big data storage and self-adaptive access control system. Information Sciences, 2019, 479: 567–592. [doi: 10.1016/j.ins.2018.02.005
    [6] Liang W, Fan YK, Li KC, et al. Secure data storage and recovery in industrial blockchain network environments. IEEE Transactions on Industrial Informatics, 2020, 16(10): 6543–6552. [doi: 10.1109/TII.2020.2966069
    [7] Lee OT, Akash GJ, Kumar SDM, et al. Storage node allocation methods for erasure code-based cloud storage systems. Arabian Journal for Science and Engineering, 2019, 44(11): 9127–9142. [doi: 10.1007/s13369-019-03983-8
    [8] Knauft E, Goggin EJ, Li RC, et al. Automatically removing dependency on slow disks in a distributed storage system: US, 10168942. 2019-01-01.
    [9] 余春雷, 王静, 王秘, 等. 图因子分解的部分重复码构造. 中国科技论文, 2019, 14(11): 1260–1264
    [10] Vaishampayan VA. Lattice erasure codes of low rank with noise margins. Proceedings of the 2018 IEEE International Symposium on Information Theory (ISIT). Vail: IEEE, 2018. 961–965.
    [11] Balaji SB, Krishnan MN, Vajha M, et al. Erasure coding for distributed storage: An overview. Science China Information Sciences, 2018, 61(10): 100301. [doi: 10.1007/s11432-018-9482-6
    [12] 余春雷, 王静, 杨成福, 等. 哈夫曼树的异构部分重复码构造. 北京邮电大学学报, 2021, 44(6): 116–121
    [13] Papailiopoulos DS, Dimakis AG, Cadambe VR. Repair optimal erasure codes through hadamard designs. IEEE Transactions on Information Theory, 2013, 59(5): 3021–3037. [doi: 10.1109/TIT.2013.2241819
    [14] Goparaju S, Fazeli A, Vardy A. Minimum storage regenerating codes for all parameters. IEEE Transactions on Information Theory, 2017, 63(10): 6318–6328. [doi: 10.1109/TIT.2017.2690662
    [15] Kralevska K, Gligoroski D, Jensen RE, et al. HashTag erasure codes: From theory to practice. IEEE Transactions on Big Data, 2018, 4(4): 516–529. [doi: 10.1109/TBDATA.2017.2749255
    [16] 朱兵, 李挥, 陈俊, 等. 基于可分组设计的部分重复码研究. 通信学报, 2015, 36(2): 98–105. [doi: 10.11959/j.issn.1000-436x.2015038
    [17] Ahmad I, Wang CC. Flexible fractional repetition codes for distributed storage networks. Proceedings of the 56th Annual Allerton Conference on Communication, Control, and Computing (Allerton). Monticello: IEEE, 2018. 805–812.
    [18] Zhu B. A study on universally good fractional repetition codes. IEEE Communications Letters, 2018, 22(5): 890–893. [doi: 10.1109/LCOMM.2018.2813391
    [19] Porter A, Silas S, Wootters M. Load-balanced fractional repetition codes. Proceedings of the 2018 IEEE International Symposium on Information Theory (ISIT). Vail: IEEE, 2018. 2072–2076.
    [20] Wang J, Wang TT, Liu XY, et al. Locally repairable codes based on fractional repetition codes in distributed storage systems. 14th International Conference on Wireless Communications, Networking and Mobile Computing (WiCOM 2018). Lancaster, PA: DEStech Publications, Inc., 2018, 306: 578–587.
    [21] Dukes PJ, Lamken ER, Ling ACH. Resolvable group divisible designs with large groups. The Electronic Journal of Combinatorics, 2016, 23(4): 4.24. [doi: 10.37236/5435
    [22] Zhu B, Zhang SG, Wang WP. Expandable fractional repetition codes for distributed storage systems. Proceedings of the 2021 IEEE Information Theory Workshop (ITW). Kanazawa: IEEE, 2021. 1–5.
    [23] Zhu B, Shum KW, Li H, et al. On the optimal reconstruction degree of fractional repetition codes. Proceedings of the 2019 IEEE International Symposium on Information Theory (ISIT). Paris: IEEE, 2019. 1557–1561.
    [24] Su YS. Optimal pliable fractional repetition codes that are locally recoverable: A bipartite graph approach. IEEE Transactions on Information Theory, 2019, 65(2): 985–999. [doi: 10.1109/TIT.2018.2876284
    [25] Aghayev A, Weil S, Kuchnik M, et al. File systems unfit as distributed storage backends: Lessons from 10 years of Ceph evolution. Proceedings of the 27th ACM Symposium on Operating Systems Principles. Huntsville: ACM, 2019. 353–369.
    Cited by
    Comments
    Comments
    分享到微博
    Submit
Get Citation

余春雷,王娥,刘星,谢锐,冉彪.图因子分解的故障节点快速修复.计算机系统应用,2023,32(2):394-399

Copy
Share
Article Metrics
  • Abstract:778
  • PDF: 1645
  • HTML: 1159
  • Cited by: 0
History
  • Received:June 15,2022
  • Revised:September 07,2022
  • Online: November 04,2022
Article QR Code
You are the first1015025Visitors
Copyright: Institute of Software, Chinese Academy of Sciences Beijing ICP No. 05046678-3
Address:4# South Fourth Street, Zhongguancun,Haidian, Beijing,Postal Code:100190
Phone:010-62661041 Fax: Email:csa (a) iscas.ac.cn
Technical Support:Beijing Qinyun Technology Development Co., Ltd.

Beijing Public Network Security No. 11040202500063