Study On Group Encoding Technique For RAID Storage Systems

With the rapid development of the Internet, a large volume of digital data has been produced every day. To store such large volume of data, Redundant Arrays of Independent Disks (RAID) aggregates a set of disks to provide huge storage capacity and high I/O bandwidth. In large-scale RAID systems, due to the large number of disks, disk failure becomes common event. So some redundancy must be introduced to RAID systems to keep data reliability. Upon disk failures, RAID systems recover the failed disks to keep the data availability. The recovery process should be done as fast as possible, because if the recovery process lasts too long, user access will be impacted for a long time. Moreover, more disks may fail during the recovery process, causing permanent data loss. However, the volume of a disk increases rapidly, but the I/O performance of a disk increases slowly, hence the recovery process of a terabyte disk in the conventional RAID systems will cost really a long time.To greatly speed up the single disk recovery process of a storage system, in this paper, we propose a new RAID architecture, OI-RAID, which is essentially a kind of group encoding technique. OI-RAID is based on a hierarchical architecture, containing two layers of codes, outer layer code and inner layer code. The outer layer code is based on Balanced Incomplete Block Design (BIBD) with skewed data layout, providing efficient parallel I/O of all disks for single disk failure recovery. The inner layer code is based on each diagonal and deployed within each group. In this paper, we introduce the construction of OI-RAID through an example. We deploy RAID5 in both layers and present detailed performance analysis with experiment. Results show that OI-RAID achieves a speed-up ratio of 60 with less than 350 disks, meaning that we can rebuild a terabyte disk in a short period of time. OI-RAID reads much less data from surviving disks than MDS erasure codes tolerating the same disk failures during the single disk recovery process, reducing network bandwidth and I/Os. OI-RAID needs nearly the theoretically fewest disks to achieve the high speed of data recovery, keeping low disks cost. OI-RAID keeps low storage overhead, which is between 0.2 and 0.6. The update overhead of OI-RAID is optimum.In practical scenarios, to relax the restriction of number of disks in storage systems caused by group encoding technique, we build OI-RAID based on Steiner triple system and complete graph respectively, and then propose two kinds of virtual disk technique. All these methods increase the flexibility of the construction of OI-RAID, provide more optional parameters, while costing higher storage overhead. To further enhance the data reliability of OI-RAID, we deploy MDS erasure codes tolerating multiple disk failures into both layers of OI-RAID respectively. If we deploy MDS codes which tolerate 3 disk failures in both layers, then the OI-RAID could tolerate 15 arbitrary disk failures, greatly enhancing the data reliability. Finally, we discuss how to deploy the group encoding technique of OI-RAID into data center, and propose a hybrid recovery scheme which reduces network overhead during the single disk recovery process.