Redistributing parity in a storage system

• US 8,910,030 B2
• Filed: 04/22/2013
• Issued: 12/09/2014
• Est. Priority Date: 09/24/2008
• Status: Active Grant

• Current Assignee: NetApp, Inc.
• Original Assignee: NetApp, Inc.
• Inventors: Goel, Atul
• Primary Examiner(s): Bhatia, Ajay
• Assistant Examiner(s): GANDHI, DIPAKKUMAR B
• Application Number:
  US13/867,850
• Publication Number:
  US 20130304987A1
• Time in Patent Office: 596 Days
• 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 comprising:

identifying a parity pattern for parity block distribution for N storage devices, wherein the parity pattern for the N storage devices is based on a repeat interval that indicates a number of stripes before the parity pattern for the N storage devices repeats;

determining a least common multiple of the repeat interval and N+1, wherein N is a number of the storage devices and N+1 represents addition of a storage device to the N storage devices;

creating a parity pattern for parity block distribution for the N+1 storage devices based on the parity pattern for the N storage devices, using the determined least common multiple as a second repeat interval, and a number of parity blocks indicated for each of the N storage devices, wherein said determining the parity pattern for the N+1 storage devices comprises,

for each second repeat interval of stripes, transferring a number of parity block indications from representation of the N storage devices to representation of an additional storage device, wherein the number of transferred parity block indications is based on N+1 and the number of parity blocks indicated for each of the N storage devices; and

redistributing the parity blocks from the N storage devices to the additional storage device based, at least in part, on the parity pattern for the N+1 storage devices.

2. The method of claim 1, wherein the parity pattern for the N+1 storage devices comprises a parity pattern for a RAID system.

3. The method of claim 1 further comprising generating a metadata description of the created parity pattern for the N+1 storage devices.

4. The method of claim 1, wherein said transferring the number of parity block indications from the representations of the N storage devices to the representation of the additional storage device comprises computing a transfer integer number as a number of parity blocks on a first of the N storage devices divided by (N+1) and transferring the transfer number of parity block indications from the representations of the N storage devices to the representation of the additional storage device.

5. The method of claim 4, wherein said transferring the transfer number of parity block indications from the representations of the N storage devices to the representation of the additional storage device comprises transferring a same number of parity block indications from each of the represented N storage devices to equal the transfer number of parity blocks.

6. The method of claim 1, further comprising distinguishing between different types of parity blocks of a same stripe within each of the stripes represented in the parity pattern of the N storage devices before said transferring the number of indicated parity blocks,

wherein said transferring the number of parity block indications comprises transferring based on a number of parity blocks of a same type on each of the N storage devices.

7. A system comprising:

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

parity block distribution metadata stored in at least one of the N storage devices, the parity block distribution metadata indicating a parity pattern for parity block distribution for the N storage devices, wherein the parity pattern is based on a repeat interval that indicates a number of stripes before the parity pattern for the N storage devices repeats; and

a controller, the controller operable to,

determine, as a second repeat interval, a least common multiple of the repeat interval and N+1;

create a parity pattern for parity block distribution for the N+1 storage devices based on the second repeat interval and a number of parity blocks indicated for each of the N storage devices based on the second repeat interval, wherein the controller operable to create the parity pattern for the N+1 storage devices comprises the controller being operable to,

for each second repeat interval of stripes, transfer a number of parity block indications from representations of the N storage devices to a representation of an additional storage device, wherein the number of transferred parity block indications is based on N+1 and the number of parity blocks indicated for each of the N storage devices; and

redistribute the parity blocks from the N storage devices to the (N+1)th storage device based, at least in part, on the parity pattern created for the N+1 storage devices.

8. The system of claim 7, wherein the storage system comprises a RAID system.

9. The system of claim 7, wherein the controller is further operable to generate a metadata description of the created parity pattern for the N+1 storage devices and to store as parity block distribution metadata.

10. The system of claim 7, wherein the controller being operable to transfer the number of parity block indications comprises the controller being operable to compute a transfer integer number as a number of parity blocks on a first of the N storage devices divided by N+1 and to transfer the transfer number of parity block indications from the representations of the N storage devices to the representation of the (N+1)th storage device.

11. The storage system of claim 10, wherein the controller operable to transfer the transfer number of parity block indications from the N storage device representations to the (N+1)th storage device representation comprises the controller operable to transfer a same number of parity block indications from each of the represented N storage devices to equal the transfer number of parity block indications.

12. The system of claim 7, wherein the controller is further operable to distinguish between different types of parity blocks of a same stripe within each of the stripes represented in the parity pattern of the N storage devices before the controller transfers the number of parity block indications,

wherein the controller being operable to transfer the number of parity block indications comprises the controller being operable to transfer based on a number of parity blocks of a same type on each of the N storage devices.

13. A non-transitory machine readable medium having executable program code stored thereon, the executable program code comprising program code to:

identify a parity pattern for parity block distribution for N storage devices, wherein the parity pattern for the N storage devices is based on a repeat interval that indicates a number of stripes before the parity pattern for the N storage devices repeats;

determine, as a second repeat interval, a least common multiple of the repeat interval and N+1, wherein N is a number of the storage devices;

create a parity pattern for parity block distribution for the N+1 storage devices based on the second repeat interval, the parity pattern for the N storage devices, and a number of parity blocks indicated for each of the N storage devices, wherein the program code to create the parity pattern for the N+1 storage devices comprises program code to,

for each second repeat interval of stripes, transfer a number of parity block indications from representations of the N storage devices to a representation of an additional storage device, wherein the number of transferred parity block indications is based on N+1 and the number of parity blocks indicated for each of the N storage devices; and

redistribute the parity blocks from the N storage devices to the additional storage device based, at least in part, on the parity pattern created for the N+1 storage devices.

14. The machine readable medium of claim 13, wherein the parity pattern comprises a parity pattern for a RAID system.

15. The machine readable medium of claim 13, wherein the program code further comprises program code to generate a metadata description of the parity pattern for the N+1 storage devices.

16. The machine readable medium of claim 13, wherein the program code to transfer the number of parity block indications from the representations of the N storage devices to the representation of the additional storage device comprises program code to compute a transfer integer number as a number of parity blocks on a first of the N storage devices divided by (N+1) and to transfer the transfer number of parity block indications i from the representations of the N storage devices to the representation of the additional storage device.

17. The machine readable medium of claim 16, wherein the program code to transfer the transfer number of parity block indications from the representations of the N storage devices to the representation of the additional storage device comprises the program code to transfer a same number of parity block indications from each of the represented N storage devices to equal the transfer number of parity block indications.

18. The machine readable medium of claim 13, further comprising program code to distinguish between different types of parity blocks of a same stripe within each of the stripes represented in the parity pattern of the N storage devices before transfer of the parity block indications,

wherein the program code to transfer the parity block indications comprises program code to transfer based on a number of parity blocks of a same type on each of the N storage devices.