Block coding method and system for failure recovery in disk arrays

Abstract

A method, system, and data structure for encoding a block of data with redundancy information and for correction of erasure type errors in the block using the redundancy data. In particular, the invention is particularly applicable to disk array storage subsystems which are capable of recovering from total or partial failures of one or two disks in the disk array. Still more specifically, the invention is applicable to RAID level 6 storage devices. A given data block of data is translated into a code block of n.sup.2 elements including 2n XOR parity elements for redundancy. Each code block is manipulated as a square matrix, of n.sup.2 elements with parity elements along the major diagonals of the matrix and data elements in the remainder of the matrix. Each parity element is a dependent variable whose value is the XOR sum of the (n-2) data elements in a minor diagonal which intersects it. If the elements in any one or two columns or one or two rows are erased, their values can be generated from the other elements in the matrix. The invention therefore allows for recovery from data loss resulting from complete failure of any one or two disks in the disk array. Further, since the invention recovers all erased elements in any one or two rows, it allows recovery from data loss resulting from correlated partial failure of all disks in the disk array. Still further, the invention allows recovery from many uncorrelated failure patterns in the storage domain of disk drives in a disk array.