DYNAMIC LOAD BALANCING OF DISTRIBUTED PARITY IN A RAID ARRAY

• US 20130304987A1
• Filed: 04/22/2013
• Published: 11/14/2013
• Est. Priority Date: 09/24/2008
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Goel, Atul
• Granted Patent: US 8,910,030 B2
• Time in Patent Office: Days
• US Class Current: 711/114
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 12/00 Accessing, addressing or allocating within memory systems or architectures digital input from, or digital output to record carriers, e.g. to disk storage units, G06F3/06
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity

Abstract

A parity pattern defines a repeated distribution of parity blocks within a distributed parity disk array (“DPDA”). The parity pattern identifies on which disks the parity block or blocks for a stripe are located. When a new disk is added to the DPDA, the parity pattern is modified so that the distribution of parity blocks within the parity pattern is even. Parity blocks within the DPDA are then redistributed to conform with the modified parity pattern.

Claims

1. (canceled)

2. A method in a storage subsystem, comprising:

identifying an original parity pattern for parity block distribution among N storage devices of the storage subsystem, wherein the original parity pattern includes an original repeat interval of a number of stripes after which the original parity pattern repeats among a next number of stripes of the N storage devices, the repeat interval based on having N storage devices;

computing an updated parity pattern for (N+1) storage devices including the N storage devices and an (N+1)th storage device, wherein the updated parity pattern includes distribution of the parity blocks among the (N+1) storage devices;

generating the updated parity pattern for the (N+1) storage devices, wherein the update parity pattern includes an updated repeat interval of a number of stripes based on having (N+1) storage devices; and

selectively redistributing parity blocks from the N storage devices to the (N+1)th storage device in accordance with the updated parity pattern.

3. The method of claim 2, wherein the original parity pattern comprises a parity pattern for a RAID (redundant array of independent disks) system.

4. The method of claim 2, wherein computing the updated parity pattern for the (N+1) storage devices comprises computing a least common multiple (LCM) of the number of stripes after which the original parity pattern repeats, and (N+1), wherein the LCM represents a new number of stripes after which the updated parity pattern repeats.

5. The method of claim 2, wherein generating the updated parity pattern comprises generating a metadata description to store in a metadata storage area.

6. The method of claim 2, wherein redistributing the parity blocks further comprises computing a number of parity blocks to transfer from the N storage devices to the (N+1)th storage device, the number of parity blocks to transfer being an integer value of a total number of parity blocks on the N storage devices divided by (N+1), with an equal number transferred from each of the N storage devices to the (N+1)th storage device.

7. The method of claim 2, wherein an order of parity is higher than one, where multiple parity blocks are stored on each stripe, and further comprising:

assigning a symbolic identifier to each parity block per stripe, with a unique symbolic identifier for each order of parity; and

wherein redistributing the parity blocks from the N storage devices to the (N+1)th storage device comprises redistributing based on the symbolic identifier, to distribute a parity block only of one symbolic identifier type per stripe for stripes where a parity block is redistributed to the (N+1)th storage device.

8. A storage subsystem, comprising:

(N+1) storage devices including N storage devices and an (N+1)th storage device;

a parity block distribution metadata stored in a metadata storage are of at least one of the (N+1) storage devices, the metadata including a data structure identifying an original parity pattern for parity block distribution among N storage devices, wherein the original parity pattern includes an original repeat interval of a number of stripes after which the original parity pattern repeats among a next number of stripes of the N storage devices, the repeat interval based on having N storage devices; and

a parity distribution controller executing on a processing device, the controller to

compute an updated parity pattern for (N+1) storage devices, wherein the updated parity pattern includes distribution of the parity blocks among the (N+1) storage devices;

generate the updated parity pattern for the (N+1) storage devices, wherein the update parity pattern includes an updated repeat interval of a number of stripes based on having (N+1) storage devices; and

selectively redistribute parity blocks from the N storage devices to the (N+1)th storage device in accordance with the updated parity pattern.

9. The storage subsystem of claim 8, wherein the storage subsystem comprises a RAID (redundant array of independent disks) system.

10. The storage subsystem of claim 8, wherein the controller is to further compute a least common multiple (LCM) of the number of stripes after which the original parity pattern repeats, and (N+1), wherein the LCM represents a new number of stripes after which the updated parity pattern repeats.

11. The storage subsystem of claim 8, wherein the controller is to generate a metadata description to store in a metadata storage area.

12. The storage subsystem of claim 8, wherein the controller is to redistribute the parity blocks by computing a number of parity blocks to transfer from the N storage devices to the (N+1)th storage device, the number of parity blocks to transfer being an integer value of a total number of parity blocks on the N storage devices divided by (N+1), with an equal number transferred from each of the N storage devices to the (N+1)th storage device.

13. The storage subsystem of claim 8, wherein an order of parity is higher than one, where multiple parity blocks are stored on each stripe, and further comprising the controller to assign a symbolic identifier to each parity block per stripe, with a unique symbolic identifier for each order of parity;

and

wherein the controller is to redistribute the parity blocks from the N storage devices to the (N+1)th storage device by redistributing based on the symbolic identifier, to distribute a parity block only of one symbolic identifier type per stripe for stripes where a parity block is redistributed to the (N+1)th storage device.

14. An article of manufacture comprising a computer readable storage medium having content stored thereon, which when executed by a controller device, results in operations including:

identifying an original parity pattern for parity block distribution among N storage devices of the storage subsystem, wherein the original parity pattern includes an original repeat interval of a number of stripes after which the original parity pattern repeats among a next number of stripes of the N storage devices, the repeat interval based on having N storage devices;

computing an updated parity pattern for (N+1) storage devices including the N storage devices and an (N+1)th storage device, wherein the updated parity pattern includes distribution of the parity blocks among the (N+1) storage devices;

generating the updated parity pattern for the (N+1) storage devices, wherein the update parity pattern includes an updated repeat interval of a number of stripes based on having (N+1) storage devices; and

selectively redistributing parity blocks from the N storage devices to the (N+1)th storage device in accordance with the updated parity pattern.

15. The article of manufacture of claim 14, wherein the original parity pattern comprises a parity pattern for a RAID (redundant array of independent disks) system.

16. The article of manufacture of claim 14, wherein the content for computing the updated parity pattern for the (N+1) storage devices comprises content for computing a least common multiple (LCM) of the number of stripes after which the original parity pattern repeats, and (N+1), wherein the LCM represents a new number of stripes after which the updated parity pattern repeats.

17. The article of manufacture of claim 14, wherein the content for generating the updated parity pattern comprises content for generating a metadata description to store in a metadata storage area.

18. The article of manufacture of claim 14, wherein the content for redistributing the parity blocks further comprises content for computing a number of parity blocks to transfer from the N storage devices to the (N+1)th storage device, the number of parity blocks to transfer being an integer value of a total number of parity blocks on the N storage devices divided by (N+1), with an equal number transferred from each of the N storage devices to the (N+1)th storage device.

19. The article of manufacture of claim 14, wherein an order of parity is higher than one, where multiple parity blocks are stored on each stripe, and further comprising content for

assigning a symbolic identifier to each parity block per stripe, with a unique symbolic identifier for each order of parity;

and

wherein the content for redistributing the parity blocks from the N storage devices to the (N+1)th storage device comprises content for redistributing based on the symbolic identifier, to distribute a parity block only of one symbolic identifier type per stripe for stripes where a parity block is redistributed to the (N+1)th storage device.