Overlay methods for fast and deterministic RAID relocation supporting disk array growth
An initial drive cluster of G drives with G subdivisions is represented by a G*G drive matrix, where G equals the number of data and parity members in the RAID level implemented on the drive cluster. A corresponding G×G overlay matrix is created in which a value at row R, column C equals a remainder of (R+C−2) divided by G, such that there are G distinct values in a range of 0 to G−1. Responsive to addition of N new drives to the drive cluster, the N new drives are added to the drive matrix and the overlay matrix is used to select and relocate RAID members within the drive matrix so that new RAID groups can be created.
1. An apparatus, comprising:
a plurality of non-volatile drives;
at least one compute node configured to manage access of the non-volatile drives, the at least one compute node comprising at least one processor and non-transitory computer-readable memory; and
a Redundant Array of Independent Drives (RAID) controller configured to:
organize the non-volatile drives into drive clusters, each having G non-volatile drives with G subdivisions, where G equals a number of data members and parity members of an implemented RAID level;
create a G*G drive matrix for each of the drive clusters, the drive matrix representing the corresponding drive cluster;
create a G×G overlay matrix in which a value at row R, column C equals a remainder of (R+C−2) divided by G, such that there are G distinct values in a range of 0 to G−1; and
responsive to addition of N new drives to one of the drive clusters, add the N new drives to the corresponding drive matrix and use the overlay matrix to relocate RAID members within the drive matrix.
2. The apparatus of claim 1 further comprising the RAID controller configured to superimpose the overlay matrix on the corresponding drive matrix with greatest drive indices in alignment.
3. The apparatus of claim 2 further comprising the RAID controller configured to select N of the values from the overlay matrix.
4. The apparatus of claim 3 further comprising the RAID controller configured to relocate protection group members within each subdivision index from drive cluster matrix locations superimposed by the selected values of the overlay matrix to drive cluster matrix locations superimposed by unselected values of the overlay matrix.
5. The apparatus of claim 4 further comprising the RAID controller configured to create new RAID groups in subdivisions freed by relocations of protection group members and locate members of each of those RAID groups to subdivisions superimposed by one of the values of the overlay matrix.
6. The apparatus of claim 1 further comprising the RAID controller configured to insert representations of the N new drives into the corresponding drive matrix between drives without relocated protection group members and drives with relocated protection group members.
7. The apparatus of claim 6 further comprising the RAID controller configured to superimpose the overlay matrix on the corresponding drive matrix with last drive indices in alignment.
8. The apparatus of claim 7 further comprising the RAID controller configured to relocate protection group members of the G*G drive matrix within each subdivision index to one of the new drives in accordance with the values of the overlay matrix that superimpose the subdivisions of those protection group members.
9. The apparatus of claim 7 further comprising the RAID controller configured to create new RAID groups in subdivisions freed by relocations of protection group members and locate members of each of those RAID groups to subdivisions superimposed by one of the values of the overlay matrix.
10. A method comprising:
organizing non-volatile drives into drive clusters, each having G non-volatile drives with G subdivisions, where G equals a number of data members and parity members of an implemented RAID level;
creating a G*G drive matrix for each of the drive clusters, the drive matrix representing the corresponding drive cluster;
creating a G×G overlay matrix in which a value at row R, column C equals a remainder of (R+C−2) divided by G, such that there are G distinct values in a range of 0 to G−1; and
responsive to addition of N new drives to one of the drive clusters, adding the N new drives to the corresponding drive matrix and using the overlay matrix to relocate RAID members within the drive matrix.
11. The method of claim 10 further comprising superimposing the overlay matrix on the corresponding drive matrix with greatest drive indices in alignment.
12. The method of claim 11 further comprising selecting N of the values from the overlay matrix.
13. The method of claim 12 further comprising relocating protection group members within each subdivision index from drive cluster matrix locations superimposed by the selected values of the overlay matrix to drive cluster matrix locations superimposed by unselected values of the overlay matrix.
14. The method of claim 13 further comprising creating new RAID groups in subdivisions freed by relocations of protection group members and locate members of each of those RAID groups to subdivisions superimposed by one of the values of the overlay matrix.
15. The method of claim 14 further comprising inserting representations of the N new drives into the corresponding drive matrix between drives without relocated protection group members and drives with relocated protection group members.
16. The method of claim 15 further comprising superimposing the overlay matrix on the corresponding drive matrix with last drive indices in alignment.
17. The method of claim 16 further comprising relocating protection group members of the G*G drive matrix within each subdivision index to one of the new drives in accordance with the values of the overlay matrix that superimpose the subdivisions of those protection group members.
18. The method of claim 17 further comprising creating new RAID groups in subdivisions freed by relocations of protection group members and locate members of each of those RAID groups to subdivisions superimposed by one of the values of the overlay matrix.
19. The method of claim 18 further comprising splitting the drive cluster into two separate drive clusters.
20. A non-transitory computer-readable storage medium with instructions that when executed by a computer perform a method comprising:
organizing non-volatile drives into drive clusters, each having G non-volatile drives with G subdivisions, where G equals a number of data members and parity members of an implemented RAID level;
creating a G*G drive matrix for each of the drive clusters, the drive matrix representing the corresponding drive cluster;
creating a G×G overlay matrix in which a value at row R, column C equals a remainder of (R+C−2) divided by G, such that there are G distinct values in a range of 0 to G−1; and
responsive to addition of N new drives to one of the drive clusters, adding the N new drives to the corresponding drive matrix and using the overlay matrix to relocate RAID members within the drive matrix.