In data storage systems, it is crucial to protect data from loss due to failures. Erasure codes lay the foundation of this protection, enabling systems to reconstruct lost data when components fail. Erasure codes can, however, impose significant performance overhead in two core operations: encoding, where parity is calculated from newly written data, and decoding, where data is reconstructed after failures. This paper focuses on improving the performance of encoding, the more frequent operation. We observed that CPU cache efficiency has great impact on the encoding performance and proposed several encoding scheduling algorithms to optimize the use of cache memory. We call the technique XOR-scheduling and demonstrate how it applies to a wide variety of existing erasure codes. To illustrate the generality of this technique, we have conducted a performance evaluation of scheduling these codes on a variety of platforms and shown that XOR-scheduling significantly improves upon the conventional approach. Hence, we believe that XOR-scheduling has great potential to have wide impact in practical storage systems.

Network codes designed specifically for distributed storage systems have the potential to provide dramatically higher storage efficiency for the same availability. One main challenge in the design of such codes is the exact repair problem: if a node storing encoded information fails, in order to maintain the same level of reliability we need to create encoded information at a new node. One of the main open problems in this emerging area has been the design of simple coding schemes that allow exact and low cost repair of failed nodes and have high data rates. In particular, all prior known explicit constructions have data rates bounded by 1/2. In this paper we introduce the first family of distributed storage codes that have simple look-up repair and can achieve rates up to 2/3. Our constructions are very simple to implement and perform exact repair by simple XORing of packets. We experimentally evaluate the proposed codes in a realistic cloud storage simulator and show significant benefits in both performance and reliability compared to replication and standard Reed-Solomon codes.

Finite fields are widely used in constructing error-correcting codes and cryptographic algorithms. In practice, error-correcting codes use small finite fields to achieve high-throughput encoding and decoding. Conversely, cryptographic systems employ considerably larger finite fields to achieve high levels of security. We focus on developing efficient software implementations of arithmetic operations in reasonably large finite fields as needed by secure storage applications. In this article, we study several arithmetic operation implementations for finite fields ranging from GF (2 32 ) to GF (2 128 ). We implement multiplication and division in these finite fields by making use of precomputed tables in smaller fields, and several techniques of extending smaller field arithmetic into larger field operations. We show that by exploiting known techniques, as well as new optimizations, we are able to efficiently support operations over finite fields of interest. We perform a detailed evaluation of several techniques, and show that we achieve very practical performance for both multiplication and division. Finally, we show how these techniques find applications in the implementation of HAIL, a highly available distributed cloud storage layer. Using the newly implemented arithmetic operations in GF (2 64 ), HAIL improves its performance by a factor of two, while simultaneously providing a higher level of security.

Recent studies show hard disk drives fail much more often in real systems than specified in their data-sheets, and RAID-5 may not be able to provide necessary reliability for practical systems. It is desirable to have disk arrays and clustered storage systems with higher data redundancy, such as RAID-6. Meanwhile, latest research also indicates that sector failures become a threat to data reliability in storage systems. As a result, disk failures in RAID-6 systems become complex, and call for efficient decoding approaches to recover data when disk failures take place. This paper proposes a simple and efficient decoding algorithm to reconstruct data from disk failures for RAID-6 systems. First, for many well known RAID-6 codes, we provide the conditions to determine the recoverability of disk failures by using Tanner graph. The covered RAID-6 codes include X-code, EVENODD, and RDP. Then, a generic failure decoding algorithm called SCAN algorithm is derived. The SCAN algorithm is able to efficiently reconstruct data for any recoverable disk failures. Extensive performance evaluation shows the SCAN algorithm achieves higher performance than Matrix Method, another general decoding algorithm. Hence, the SCAN algorithm is an attractive decoding algorithm to be integrated into RAID-6 systems.called entire disk failure.

As storage systems grow in size and complexity, various hardware and software component failures inevitably occur, resulting in disk malfunction in failures, as well as silent errors. Existing techniques and schemes overcome the failures and silent errors in a separate fashion. In this paper, we advocate using the STAR code as a unified and systematic mechanism to simultaneously tolerate failures on one disk and silent errors on another. By exploring the unique geometric structure of the STAR code, we propose a novel efficient decoding algorithm - EEL. Both theoretical and experimental performance evaluations show that EEL constantly outperforms a naive Try-and-Test approach by large factors in overall decoding throughput.

In large storage systems, it is crucial to protect data from loss due to failures. Erasure codes lay the foundation of this protection, enabling systems to reconstruct lost data when components fail. Erasure codes can however impose significant performance overhead in two core operations: encoding, where coding information is calculated from newly written data, and decoding, where data is reconstructed after failures. This paper focuses on improving the performance of encoding, the more frequent operation. It does so by scheduling the operations of XOR-based erasure codes to optimize their use of cache memory. We call the technique XOR-scheduling and demonstrate how it applies to a wide variety of existing erasure codes. We conduct a performance evaluation of scheduling these codes on a variety of processors and show that XOR-scheduling significantly improves upon the traditional approach. Hence, we believe that XOR-scheduling has great potential to have wide impact in practical storage systems.