Patent ID: 7945729

Claim:
A processor-implemented method of protecting against concurrent failures occurring in at most T different storage devices in a group of N storage devices, comprising: setting positive integers parameters n, r, v, h s, where n+h=N, v≧1, h≧1, T<n, and v+h≦T and r ≤ v ⁢ n - T T - h , are valid based on the positive integers that have been set, and wherein the following condition is satisfied: (a) T=2 and r<n−2, and wherein n is a prime number; logically partitioning a portion of each of the storage devices into one strip spanning across a single storage device comprising the portion that has been logically partitioned; organizing strips across the storage devices into a stripe; designating n of the strips to each be a data and vertical parity strip; designating h of the strips to each be a horizontal parity strip; partitioning each of the data and vertical parity strips into r data elements and v vertical parity elements, wherein each data element is used to create at least T parity values; partitioning each of the horizontal parity strips into at least r horizontal parity elements and a remainder of each of the horizontal parity strips as unused elements; wherein for each vertical parity element and horizontal parity element, selecting a set of data elements from a collection of one or more data elements in the stripe so that: (a) the selected set of data elements as a whole has not already been selected for another parity element, wherein each data element in the collection of one or more data elements is selected for a number of T different parity elements; (b) storage devices of the selected data elements are different from the storage device of a parity element for which the set of data elements are being selected from the collection of one or more data elements in the stripe; (c) wherein for each vertical parity element in a data and vertical parity strip, there is a sequence of selected sets of data elements from the stripe, wherein a first selected set in the sequence is a selected set for the vertical parity element and wherein each consecutive pair of selected sets in the sequence comprise a data element in common, and wherein a last selected set in the sequence comprises a data element in the data and vertical parity strip; and generating a parity value from data values stored in the data elements in the selected set of data elements and storing the parity value in the vertical parity element and the horizontal parity element, respectively.