Declustered array of storage devices with chunk groups and support for multiple erasure schemes

Patent metadata

Field	Value
Publication number	US-9841908-B1
Application number	US-201615198245-A
Country	US
Kind code	B1
Filing date	Jun 30, 2016
Priority date	Jun 30, 2016
Publication date	Dec 12, 2017
Grant date	Dec 12, 2017

Abstract

Embodiments of a declustered, fault-tolerant array of storage devices for use with computer, networked, cloud-based, and other data storage applications are described. In some embodiments, the array generates a chunk group mapping with a high utilization of storage device space, provides evenly distributed hot spares, supports multiple erasure schemes including Reed-Solomon codes and Local Reconstruction Codes, and provides high storage device rebuild speed after storage device failure. Embodiments of methods of generating chunk group mappings are also disclosed. In some embodiments, chunk group mappings are determined based on the desired erasure scheme, the number of storage devices connected to the declustered, fault-tolerant array of storage devices, and a generated balanced incomplete block design or a generated partial balanced incomplete block design. Chunk group mappings are stored as a multi-level lookup table which includes at least a first erasure scheme pattern table and at least a second chunk group lookup table.

First claim

What is claimed is:

1. A method of storing data and parity information in a declustered array of storage devices, the method comprising:
receiving an erasure scheme for distributing data and parity in the declustered array of storage devices, wherein each storage device is partitioned into a plurality of stripes, and wherein each stripe is configured to store data, parity information or is reserved for data recovery as a hot spare stripe;
determining a balanced incomplete block design mapping compatible with the number of storage devices in the declustered array of storage devices and the erasure scheme;
grouping subsets of stripes into a plurality of chunk groups based on the balanced incomplete block design mapping, wherein each chunk group comprises stripes from different storage devices; and
storing information representative of the erasure scheme and chunk groups within a multi-level table comprising:
at least a first-level erasure scheme pattern table, and
at least a second-level chunk group lookup table, and

storing data and parity information in at least a subset of the plurality of stripes in accordance with the multi-level table;
wherein the method is performed under control of at least one array controller.

2. The method of claim 1 , wherein determining the balanced incomplete block design mapping further comprises:
generating a first K-by-K matrix comprising entries that are a random permutation of integers 1 through N, wherein N is the number of said storage devices within the declustered array of storage devices and K is the number of data and parity stripes associated with said received erasure scheme and N is equal to K squared;
generating a second matrix that is a transpose of the first matrix;
generating K−1 square matrices, wherein each of said K−1 square matrices is formed by performing successive rotational operations on the first matrix; and
generating the balanced incomplete block design mapping wherein each chunk group is defined by a row of each square matrix generated.

3. The method of claim 1 ,
wherein the first-level erasure scheme pattern table comprises entries for select permutations of data and parity stripes according to the erasure scheme, and
wherein the second-level chunk group lookup table comprises entries defining chunk groups, each chunk group comprising a plurality of data and parity stripes, wherein each stripe of each chunk group is located on a different storage device, and wherein the chunk group lookup table entries further identify an erasure scheme pattern defined in the erasure scheme pattern table.

4. The method of claim 3 ,
wherein the select permutations of data and parity stripes are a left-symmetric one-round rotation of data and parity stripes;
and wherein each storage device is labeled with an identification number;
and wherein the entries of the second-level chunk group lookup table are arranged such that the storage device identification numbers within each entry are monotonically increasing.

5. The method of claim 1 , further comprising recovering data stored in a failed storage device by:
determining a set of chunk groups that includes one or more stripes located in the failed storage device;
reading data and parity stored in the other stripes associated with the set of chunk groups;
reconstructing data and parity stored in the one or more stripes located on the failed storage device based on the erasure scheme; and
storing the reconstructed data and parity in at least a subset of the plurality of hot spare stripes reserved for data recovery.

6. The method of claim 1 , further comprising recovering data stored in a failed storage device by:
determining a set of chunk groups that includes one or more stripes located in the failed storage device;
connecting a new storage device to the declustered array of storage devices, wherein the new storage device is partitioned into stripes of the same size as stripes in the other storage devices;
reading data and parity from the other stripes associated with the set of chunk groups;
reconstructing data and parity stored in the one or more stripes located on the failed storage device based on the erasure scheme;
storing the reconstructed data and parity in at least a subset of a plurality of stripes on the new storage device.

7. The method of claim 1 , wherein the number of data and parity stripes in each chunk group is a prime number greater than or equal to 3.

8. The method of claim 1 , wherein the hot spare stripes that are reserved for data recovery are evenly distributed throughout the array of storage devices.

9. The method of claim 1 wherein the erasure scheme is selected from a group consisting of a RAID scheme, a Reed-Solomon code, and a Local Reconstruction Code.

10. A method of storing data and parity information in a declustered array of storage devices comprising:
receiving an erasure scheme for distributing data and parity in the declustered array of storage devices, wherein each storage device is partitioned into a plurality of stripes, and wherein each stripe is configured to store data, parity information or is reserved for data recovery as a hot spare stripe;
determining a partial balanced incomplete block design mapping compatible with the number of storage devices in the declustered array of storage devices and the erasure scheme;
grouping subsets of stripes into a plurality of chunk groups based on the partial balanced incomplete block design mapping, wherein each chunk group comprises stripes from different storage devices; and
storing information representative of the erasure scheme and chunk groups within a multi-level table comprising:
at least a first-level erasure scheme pattern table, and
at least a second-level chunk group lookup table, and

storing data and parity information in at least a subset of the plurality of stripes in accordance with the multi-level table;
wherein the method is performed under control of at least one array controller.

11. The method of claim 10 , wherein determining the partial balanced incomplete block design further comprises:
defining an integer D equal to the floor of N divided by K, wherein N is the number of storage devices in the declustered array of storage devices and K is the number of stripes associated with each chunk group;
initializing a chunk group list to hold chunk group mappings; and
iteratively adding chunk group mappings to the chunk group list by:
generating a 1 by N array consisting of a random permutation of the numbers 1 through N,
dividing the array into D subarrays of K elements each and discarding any remaining elements,
appending the D subarrays to said chunk group list, wherein the D subarrays define chunk group mappings, and
ending the iteratively adding if the number of times each storage device appears with every other storage device in a chunk group is at least 1 for every pair of storage devices.

12. The method of claim 11 , wherein iteratively adding chunk group mappings to the chunk group list further comprises:
determining a utilization ratio of the storage devices; and
ending the iteratively adding if the number of times each storage device appears with every other storage device in a chunk group is at least 1 and the utilization ratio is at least 90 percent.

13. The method of claim 10 ,
wherein the first-level erasure scheme pattern table comprises entries for select permutations of data and parity stripes according to the erasure scheme, and
wherein the second-level chunk group lookup table comprises entries defining chunk groups, each chunk group comprising a plurality of data and parity stripes, w

Assignees

• Western Digital Tech Inc

Inventors

• Zhao Zhengyi
• Xu Jun

Classifications

• G06F2201/84

  Using snapshots, i.e. a logical point-in-time copy of the data · CPC title

• G06F3/0611 Primary

  in relation to response time · CPC title

• G06F11/1469

  Backup restoration techniques · CPC title

• G06F3/064

  Management of blocks · CPC title

• G06F3/0644

  Management of space entities, e.g. partitions, extents, pools · CPC title