S-Code: Lowest Density MDS Array Codes for RAID-6

RAID, a storage architecture designed to exploit I/O parallelism and provide data reliability, has been deployed widely in computing systems as a storage building block. In large scale storage systems, in particular, RAID-6 is gradually replacing RAID-5 as the dominant form of disk arrays due to its capability of tolerating concurrent failures of any two disks. MDS (maximum distance separable) array codes are the most popular erasure codes that can be used for implementing RAID-6, since they enable optimal storage efficiency and efficient encoding and decoding algorithms. In this paper, we propose a new class of MDS array codes called S(ymmetry)-code, aiming to optimize every metric of coding. Specifically, S-code has the following properties: (a) optimality in encoding, decoding and update, (b) code length of either p or p-1 with p being a prime number, and (c) the least I/O cost for single-disk failure recovery among current representative RAID-6 codes. Our comprehensive evaluation shows that compared with other codes, S-code achieves the best trade-off among all the metrics of coding