N-WAY PARITY TECHNIQUE FOR ENABLING RECOVERY FROM UP TO N STORAGE DEVICE FAILURES
First Claim
1. A method for enabling recovery from up to n concurrent failures of storage devices in a storage array, comprising:
- providing the array with a predetermined number of storage devices, including a plurality of first devices configured to store data and row parity, wherein the predetermined number of storage devices m is less than or equal to p−
1 and wherein p is a prime number;
providing the array with at least three second devices configured to store at least three diagonal parity classes;
dividing each device into blocks;
organizing the blocks into stripes that contain blocks in each device;
computing a row parity for each row of data;
assigning all blocks from the devices storing data and row parity to diagonals; and
for each diagonal parity class, computing diagonal parity along all diagonals having a common slope and storing the computed diagonal parity on one of the second devices associated with the diagonal parity class.
2 Assignments
0 Petitions
Accused Products
Abstract
An n-way parity protection technique enables recovery of up to n storage device (e.g., disk) failures in a parity group of a storage array encoded to protect against n-way disk failures. The storage array is created by first configuring the array with m data disks, where m=p−1 and p is a prime number and a row parity disk. n−1 diagonal parity disks are then added to the array. Each diagonal parity set (i.e., diagonal) is associated with a slope that defines the data and row parity blocks of the array that are included in the diagonal. All diagonals having a common slope within a parity group are organized as a diagonal parity class. For each diagonal parity class, a diagonal parity storage disk is provided to store the diagonal parity.
114 Citations
25 Claims
-
1. A method for enabling recovery from up to n concurrent failures of storage devices in a storage array, comprising:
-
providing the array with a predetermined number of storage devices, including a plurality of first devices configured to store data and row parity, wherein the predetermined number of storage devices m is less than or equal to p−
1 and wherein p is a prime number;providing the array with at least three second devices configured to store at least three diagonal parity classes; dividing each device into blocks; organizing the blocks into stripes that contain blocks in each device; computing a row parity for each row of data; assigning all blocks from the devices storing data and row parity to diagonals; and for each diagonal parity class, computing diagonal parity along all diagonals having a common slope and storing the computed diagonal parity on one of the second devices associated with the diagonal parity class. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12)
-
-
13. A system to enable recovery from up to n concurrent failures of storage devices in a storage array, comprising:
-
the storage array configured with a predetermined number of storage devices, including a plurality of first devices configured to store data and row parity, and a plurality of second devices configured to store diagonal parity, wherein the predetermined number of storage devices m is p−
1 and wherein p is a prime number, wherein each device is divided into blocks and the blocks are organized into stripes that contain a same number of blocks in each device;the storage array further configured with a at least three second devices configured to store diagonal parity classes, each diagonal parity class defined by a slope along the data and row parity; and a storage operating system including a device storage module configured to compute and store diagonal parity for all of the diagonal parity classes. - View Dependent Claims (14, 15, 16, 17, 18, 19, 20, 21, 22)
-
-
23. A method for enabling recovery from up to n concurrent failures of storage devices in a storage array, comprising:
-
associating a set of slopes with the storage array, each slope associated with a diagonal parity class of a set of data and row parity devices within the storage array, wherein no two slopes are equal module a prime number associated with the storage array; determining, by a storage module of a storage operating system executing on a storage system, row parity for each row of data within the storage array and storing the determined row parity on the set of row parity devices; and determining, for each diagonal parity class, a set of diagonal parity that spans the data and row parity devices and storing the determined diagonal parity on a diagonal parity device associated with the diagonal parity class within the storage array. - View Dependent Claims (24, 25)
-
Specification