Erasure codes are widely used in practical storage systems to prevent disk failure and data loss. However, these codes require excessive disk I/Os and network traffic for recovering unavailable data. As a result, the recovery performance of erasure codes is suboptimal. Among all erasure codes, Minimum Storage Regenerating (MSR) codes can achieve optimal repair bandwidth under the minimum storage during recovery, but some open issues remain to be addressed before applying them in real systems. In this paper, we present Hybrid Regenerating Codes (Hybrid-RC), a new set of erasure codes with optimized recovery performance and low storage overhead. The codes utilize the superiority of MSR codes to compute a subset of data blocks while some other parity blocks are used for reliability maintenance. As a result, our design is near-optimal with respect to storage and network traffic. We show that Hybrid-RC reduces the reconstruction cost by up to 21% compared to the Local Reconstruction Codes (LRC) with the same storage overhead. Most importantly, in Hybrid-RC, each block contributes only half the amount of data when processing a single block failure. Therefore, the number of I/Os consumed per block is reduced by 50%, which is of great help to balance the network load and reduce the latency.

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 exclusive-OR. 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.

Erasure codes are widely used in distributed storage systems to prevent data loss. Traditional codes suffer from a typical repair-bandwidth problem in which the amount of data required to reconstruct the lost data, referred to as the repair bandwidth, is often far more than the theoretical minimum. While many novel codes have been proposed in recent years to reduce the repair bandwidth, these codes either require extra storage and computation overhead or are only applicable to some special cases. To address the weaknesses of the existing solutions to the repair-bandwidth problem, we propose Z Codes, a general family of codes capable of achieving the theoretical lower bound of repair bandwidth versus storage. To the best of our knowledge, the Z codes are the first general systematic erasure codes that jointly achieve optimal repair bandwidth and storage. Further, we generalize the Z codes to the GZ codes to gain the Maximum Distance Separable (MDS) property. Our evaluations of a real system indicate that Z/GZ and Reed-Solomon (RS) codes show approximately close encoding and repairing speeds, while GZ codes achieve over 37.5% response time reduction for repairing the same size of data, compared to the RS and Cauchy Reed-Solomon (CRS) codes.

In backup systems, the chunks of each backup are physically scattered after deduplication, which causes a challenging fragmentation problem. We observe that the fragmentation comes into sparse and out-of-order containers. The sparse container decreases restore performance and garbage collection efficiency, while the out-of-order container decreases restore performance if the restore cache is small. In order to reduce the fragmentation, we propose History-Aware Rewriting algorithm (HAR) and Cache-Aware Filter (CAF). HAR exploits historical information in backup systems to accurately identify and reduce sparse containers, and CAF exploits restore cache knowledge to identify the out-of-order containers that hurt restore performance. CAF efficiently complements HAR in datasets where out-of-order containers are dominant. To reduce the metadata overhead of the garbage collection, we further propose a Container-Marker Algorithm (CMA) to identify valid containers instead of valid chunks. Our extensive experimental results from real-world datasets show HAR significantly improves the restore performance by 2.84-175.36 × at a cost of only rewriting 0.5-2.03 percent data.

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 trades storage efficiency and computation for repair bandwidth reduction. However, their non-unified coding parameters and huge computation overhead prohibit their applications. Hence, we first propose a family of Functional Regenerating Codes (FRCs) with uncoded repair, balancing storage efficiency and repair bandwidth with general parameters. FRCs take advantage of a heuristic repair algorithm, which makes efforts to employ as little repair bandwidth as possible. Second, we optimize encoding by constructing the generator matrix with a bitmatrix, so encoding of FRCs can be executed by fast bitwise XORs. Further, we also optimize repairing with the Scheduled Shift Multiplication (SSM) algorithm, which accelerates the matrix product over the Galois field during repair. Compared to the traditional table-lookup multiplication algorithm, our SSM algorithm gains 1.2~2X speed-up.

Erasure codes are widely used in distributed storage systems to prevent data loss. Traditional erasure codes suffer from a typical repair-bandwidth problem in which the amount of data required to reconstruct the lost data, referred to as the repair bandwidth, is often far more than the theoretical minimum. While many novel erasure codes have been proposed in recent years to reduce the repair bandwidth, these codes either require extra storage capacity and computation overhead or are only applicable to some special cases. To address the weaknesses of the existing solutions to the repair-bandwidth problem, we propose Z Codes, a general family of codes capable of achieving the theoretical lower bound of repair bandwidth for a single data node failure. To the best of our knowledge, the Z codes are the first general systematic erasure codes that achieve optimal repair bandwidth under the minimum storage. Our in-memory performance evaluations of a 1-GB file indicate that Z codes have encoding and repairing speeds that are approximately equal to those of the Reed-Solomon (RS) codes, and their speed on the order of GB/s practically removes computation as a performance bottleneck.