Dynamic load balancing of distributed parity in a RAID array

• US 8,429,514 B1
• Filed: 09/24/2008
• Issued: 04/23/2013
• Est. Priority Date: 09/24/2008
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: Network Appliance Incorporated (NetApp, Inc.)
• Inventors: Goel, Atul
• Primary Examiner(s): Decady, Albert
• Assistant Examiner(s): GANDHI, DIPAKKUMAR B
• Application Number:
  US12/237,138
• Time in Patent Office: 1,672 Days
• Field of Search: None
• US Class Current: 714/805
• 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. A method of redistributing parity blocks within a distributed parity disk array (“

DPDA”

) composed of original data storage devices (“

disks”

) upon the addition of a new disk, comprising;

determining an original parity pattern of the DPDA which indicates parity block assignments among the original disks;

determining an original repeat interval of the original parity pattern;

creating an intermediate parity pattern based on the original parity pattern, the intermediate parity pattern indicating parity block assignments among the original disks and the new disk;

determining a number of parity blocks assigned to each original disk within the intermediate parity pattern;

determining a total number of disks in the DPDA including the original disks and the new disk;

calculating a transfer number equal to the number of parity blocks assigned to each original disk within the intermediate parity pattern divided by the total number of disks within the DPDA;

creating a new parity pattern by transferring to the new disk within the intermediate parity pattern a number of parity blocks from each original disk equal to the transfer number; and

redistributing the parity blocks within the DPDA to conform the new parity pattern.

2. A method as defined in claim 1, wherein metadata related to the DPDA is stored in a DPDA metadata area, the method additionally comprising:

determining an original parity pattern of the DPDA by reading the original parity pattern from the DPDA metadata area; and

writing the new parity pattern to the DPDA metadata area.

3. A method as defined in claim 1, additionally comprising:

creating the intermediate parity pattern based on the original parity pattern by calculating a new repeat interval based on the original repeat interval and the number of disks within the DPDA, including the original disks and the new disk, creating the intermediate parity pattern large enough to contain information concerning parity block location for a number of stripes equal to the new repeat interval, and populating the intermediate parity pattern with multiples of the original parity pattern.

4. A method as defined in claim 3, additionally comprising:

calculating a new repeat interval by determining the least common multiple between the original repeat interval and the total number of disks within the DPDA, including the original disks and the new disk.

5. A method as defined in claim 4, wherein the DPDA has dual or higher order parity, the method additionally comprising:

establishing different symbolic identifiers;

assigning the symbolic identifiers to the parity blocks within the intermediate parity pattern so that no stripe within the intermediate parity pattern contains more than one of the same type of symbolic identifier and each original disk contains a substantially equal number of each of the different symbolic identifiers;

selecting one type of symbolic identifier from the different types of symbolic identifiers; and

creating a new parity pattern by transferring to the new disk form each original disk within the intermediate parity pattern a number of parity blocks which have been assigned the selected symbolic identifier equal to the transfer number.

6. A method as defined in claim 5, additionally comprising:

establishing different symbolic identifiers by establishing as many different symbolic identifiers as the order of parity of the DPDA.

7. A computer system comprising:

a host computer;

a DPDA controller in communication with the host computer, the DPDA controller comprising a processor in communication with a memory, the memory storing computer executable code;

a plurality of original data storage devices (“

disks”

) coupled to at least one of the host computer or the DPDA controller;

a DPDA comprising at least two of the original disks, the DPDA comprising a plurality of stripes;

a DPDA metadata storage area within at least one of the original disks; and

a data structure comprising an original parity pattern within the metadata storage area that defines an original repeat interval of parity blocks distributed within the DPDA,

wherein, when a new disk is added to the DPDA, the processor executes the computer executable code to perform DPDA controller functions comprising;

reading the original parity pattern from the data structure and storing the original parity pattern in the memory;

determining the original repeat interval of the original parity pattern;

creating an intermediate parity pattern based on the original parity pattern, the intermediate parity pattern indicating parity block assignments among the original disks and the new disk, and storing the intermediate parity pattern in the memory;

determining a number of parity blocks assigned to each original disk within the intermediate parity pattern;

determining a total number of disks in the DPDA including the original disks and the new disk;

calculating a transfer number equal to the number of parity blocks assigned to each original disk within the intermediate parity pattern divided by the total number of disks within the DPDA;

using the data structure to determine a location of parity blocks within the DPDA;

creating a new parity pattern by transferring to the new disk within the intermediate parity pattern a number of parity blocks from each original disk equal to the transfer number;

modifying the data structure with the new parity pattern; and

redistributing parity blocks within the DPDA to conform to the new parity pattern within the modified data structure.

8. A computer system as defined in claim 7, wherein the processor executes the computer executable code to perform the following additional functions:

creating the intermediate parity pattern based on the original parity pattern by calculating a new repeat interval based on the original repeat interval and the number of disks within the DPDA, including the original disks and the new disk, the intermediate parity pattern large enough to contain information concerning parity block location for a number of stripes equal to the new repeat interval, and populating the intermediate parity pattern with multiples of the original parity pattern.

9. A computer system as defined in claim 8, wherein the processor executes the computer executable code to perform the following additional functions:

calculating a new repeat interval by determining the least common multiple between the original repeat interval and the total number of disks within the DPDA, including the original disks and the new disk.

10. A computer system as defined in claim 9, wherein the DPDA has a dual or higher order parity and the processor executes the computer executable code to perform the following additional functions:

establishing different symbolic identifiers;

assigning the symbolic identifiers to the parity blocks within the intermediate parity pattern so that no stripe within the intermediate parity pattern contains more than one of the same type of symbolic identifier and each original disk contains a substantially equal number of each of the different symbolic identifiers;

selecting one type of symbolic identifier from the different types of symbolic identifiers; and

creating a new parity pattern by transferring to the new disk from each original disk within the intermediate parity pattern a number of parity blocks which have been assigned the selected symbolic identifier equal to the transfer number.

11. A method of adding a new data storage device (“

disk”

) to a pre-existing striped parity RAID array composed of original disks, comprising;

determining an original parity pattern of the RAID array which defines a repeated distribution of parity blocks throughout the RAID array across the original disks;

creating a new parity pattern from the original parity pattern by repeating the original parity pattern within the new parity pattern a number of times equal to the least common multiple between the length of the original parity pattern and the number of total disks, including the original disks and the new disk, the new parity pattern defining a repeated distribution of parity blocks throughout the RAID array across the original disks and the new disk;

assigning symbolic identifiers to the parity blocks within the new parity pattern after repeating the original parity pattern within the new parity pattern, there being as many different types of symbolic identifiers as an order of parity of the RAID array, each disk within the new parity pattern being assigned an equal number of each of the different types of symbolic identifiers, each of the parity blocks corresponding to a particular stripe within the new parity pattern being assigned exactly one of each type of symbolic identifier;

selecting one of the different symbolic identifiers;

identifying a select number of parity blocks assigned the selected symbolic identifier from each original disk within the new parity pattern; and

redistributing the parity blocks throughout the original disks and the new disk in accordance with the new parity pattern, wherein the redistribution comprises;

moving the identified parity blocks from the original disks to the new disk within the new parity pattern; and

balancing the distribution of parity blocks so that the each of the original disks and the new disk has the same number of parity blocks within the new parity pattern, wherein the original parity pattern is repeated within the new parity pattern at least twice before balancing the distribution of parity blocks within the new parity pattern.

12. A method as defined in claim 11, further comprising:

calculating the select number by dividing the number of parity blocks within each original disk of the new parity pattern by the total number of disks, including the original disks and the new disk.