Almost BPXOR Coding Technique for Tolerating Three Disk Failures in RAID7 Architectures

Abstract

Redundant Array of Independent Disks (RAID) storage architectures provide protection of digital infrastructure against potential disks failures. For example, RAID-5 and RAID-6 architectures provide protection against one and two disk failures, respectively. Recently, the data generation has significantly increased due to the emergence of new technologies. Thus, the size of storage systems is also growing rapidly to accommodate such large data sizes, which increases the probability for disks failures. This necessitates a new RAID architecture that can tolerate up to three disk failures. RAID architectures implement coding techniques. The code specifies how data is stored among multiple disks and how lost data can be recovered from surviving disks. This abstract introduces a novel coding scheme for new RAID-7 architectures that can tolerate up to three disks failures. The code is an improved version of the existing BP-XOR code and is called "Almost BP-XOR".There are multiple codes that can be used for RAID-7 architectures. However, [5,2] BP-XOR codes have significantly lower encoding and decoding complexities than most common codes [1]. Regardless of this fact, this code does not achieve the fastest data decoding and reconstruction speeds due to its relatively low efficiency of 0.4. Furthermore, the existence of MDS [6,3] bx6 BP-XOR codes, b>2 (which achieves efficiency of 0.5) is still an open research question. This work proposes [6,3] 2 x 6 Almost BP-XOR codes. These codes largely utilize the simple and fast BP-XOR decoder while achieving an efficiency of 0.5, leading to the fastest recovery from disk failures among other state-of-the-art codes. An algorithm to generate a [6, 3] 2 x 6 Almost BP-XOR code has been developed and an example code is provided in Table 1. The [6, 3] 2 x 6 Almost BP-XOR codes are constructed in a way that any three-column-erasure pattern will result in one of the following two main scenarios. First: At least one of the surviving degree-three encoding symbols contains two known information symbols. This scenario occurs in 70% of three-column erasure cases (i.e. 14 out of the 20 possible cases). The recovery process in such scenario is identical to that of the BP-XOR codes; Knowing any two information symbols in a degree-three encoding symbol is sufficient to know the third information symbol through performing a simple XOR operation. Second: None of the surviving degree-three encoding symbols contains two known information symbols. This scenario occurs in the remaining 30% of three-column erasure cases (i.e., 6 out if the possible 20). The BP-XOR decoder fails in such a scenario. However, due to the construction of the codes, at least one surviving degree-three encoding symbol contains a known information symbol. Thus, knowing one of the reaming two information symbols in such a degree-three encoding symbol will initiate the BP-XOR decoder again.Table 2 shows these erasure patterns along with an expression for one of the missing information symbols. these expressions can be stored in buffers and used whenever the corresponding erasure pattern occurs. Solutions in Table 2 are derived from the inverse of a 6x6 submatrix that results from a generator matrix G by deleting columns from G corresponding to erased code columns. The read complexity of almost BP-XOR codes is 1. On the other hand. The decoding of almost BP-XOR codes require just 6 XOR operations when for a given three-column-erasure pattern BP-XOR decoding succeeds. However, when the BP- XOR decoder fails, it will require up to 15 XOR operations in total. The normalized repairing complexity is 15/6 = 2.5.Experimentally, Fig.1 shows that the proposed Almost BP-XOR codes require the least amount of time to decode and reconstruct erased columns. Thus, it is concluded that the [6, 3] 2x6 almost BP-XOR codes are best suited for RAID-7 system that requires storage efficiency of 0.5.