High-Performance General Functional Regenerating Codes with Near-Optimal Repair Bandwidth

被引：1

作者：

Liu, Qing ^{[1
]}

Feng, Dan ^{[1
]}

Hu, Yuchong ^{[1
]}

Shi, Zhan ^{[1
]}

Fu, Min ^{[1
]}

机构：

[1] Huazhong Univ Sci & Technol, Wuhan Natl Lab Optoelect F307, 1037 Luoyu Rd, Wuhan 430074, Peoples R China

来源：

ACM TRANSACTIONS ON STORAGE | 2017年 / 13卷 / 02期

基金：

中国国家自然科学基金; 国家高技术研究发展计划(863计划);

关键词：

Erasure codes; failure recovery; repair bandwidth; failure tolerance; performance and evaluation; DISTRIBUTED STORAGE; CONSTRUCTION;

D O I：

10.1145/3051122

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

Erasure codes are widely used in modern distributed storage systems to prevent data loss and server failures. Regenerating codes are a class of erasure codes that trade storage efficiency and computation for repair bandwidth reduction. However, their nonunified coding parameters and huge computational overhead prohibit their applications. Hence, we first propose a family of General Functional Regenerating (GFR) codes with uncoded repair, balancing storage efficiency and repair bandwidth with general parameters. The GFR codes take advantage of a heuristic repair algorithm, which makes efforts to employ as little repair bandwidth as possible to repair a single failure. Second, we also present a scheduled shift multiplication (SSM) algorithm, which accelerates the matrix product over the Galois field by scheduling the order of coding operations, so encoding and repairing of GFR codes can be executed by fast bitwise shifting and exclusiveOR. Compared to the traditional table-lookup multiplication algorithm, our SSM algorithm gains 1.2 to 2 X speedup in our experimental evaluations, with little effect on the repair success rate.

引用

页数：28

共 41 条

[1]

[Anonymous], 2012, P USENIX ANN TECHN C

[2]

Anvin H. P., 2015, MATH RAID 6

[3]

Burkhardt W. A., 1993, Digest of Papers FTCS-23 The Twenty-Third International Symposium on Fault-Tolerant Computing, P432, DOI 10.1109/FTCS.1993.627346

[4] NCCloud: A Network-Coding-Based Storage System in a Cloud-of-Clouds [J].

Chen, Henry C. H. ;

Hu, Yuchong ;

Lee, Patrick P. C. ;

Tang, Yang .

IEEE TRANSACTIONS ON COMPUTERS, 2014, 63 (01) :31-44

[5]

Cullina Daniel, 2009, ARXIV09102245

[6] A Survey on Network Codes for Distributed Storage [J].

Dimakis, Alexandros G. ;

Ramchandran, Kannan ;

Wu, Yunnan ;

Suh, Changho .

PROCEEDINGS OF THE IEEE, 2011, 99 (03) :476-489

[7] Network Coding for Distributed Storage Systems [J].

Dimakis, Alexandros G. ;

Godfrey, P. Brighten ;

Wu, Yunnan ;

Wainwright, Martin J. ;

Ramchandran, Kannan .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2010, 56 (09) :4539-4551

[8]

Greenan KM, 2008, I S MOD ANAL SIM COM, P121

[9]

Greenan Kevin M., 2010, P 2 USENIX C HOT TOP, V5

[10]

Hu YF, 2011, 2011 AASRI CONFERENCE ON APPLIED INFORMATION TECHNOLOGY (AASRI-AIT 2011), VOL 1, P1

← 1 2 3 4 5 →