Redistributing parity in a storage system
First Claim
Patent Images
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
18 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. - View Dependent Claims (2, 3, 4, 5, 6)
-
-
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. - View Dependent Claims (8, 9, 10, 11, 12)
-
-
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. - View Dependent Claims (14, 15, 16, 17, 18)
-
Specification