Reliable RAID system with embedded spare capacity and flexible growth
A subset of drives with protection groups that have D data members and P parity members is created with (D+P+1) drives each having (D+P) partitions. One of the protection groups is used for spare capacity. (D+P) sequentially numbered protection groups are created by distributing protection group members such that members of protection group (X+Y) modulo (D+P+1) are located on the partition at drive X of partition Y. Alternatively, members of protection group (X−Y) modulo (D+P+1) are located on the partition at drive X of partition Y. New drives are added in single drive increments. When a new drive is added the first (D+P) protection group members of the lowest numbered unrotated partition of the (D+P) lowest numbered drives are rotated onto the new drive. Members are rotated in ascending order by drive to locations in ascending order by partition. A new protection group is created in the partitions made available due to rotation. When there are enough drives in the drive subset to enable a split, then the drive subset is split into two drive subsets, e.g. a first drive subset of (D+P) drives and a second drive subset of (D+P+1) drives.
1. A method, comprising:
creating (D+P) partitions that are equal in size and number on (D+P+1) drives;
creating protection groups that have D data members and P parity members by symmetrically distributing the protection group members on the partitions using modulo arithmetic;
individually adding new drives with (D+P) partitions equal in size and number to the partitions of the (D+P) drives;
for the first new drive:
selecting (D+P) protection group members located on the first partition of the (D+P) drives;
rotating the selected members as a column of a matrix to the new drive as a new row of the matrix; and
creating a new protection group using freed space of the rotated members; and
for each of the next new drives:
selecting (D+P) protection group members located on an unrotated partition of the (D+P) drives;
rotating the (D+P) selected protection group members from the unrotated partition to the new drive; and
creating a new protection group using partitions freed by rotating the selected protection group members to the new drive.
2. The method of claim 1 wherein creating protection groups by symmetrically distributing the protection group members on the partitions using modulo arithmetic comprises creating (D+P) protection groups and a spare group of (D+P) spare partitions.
3. The method of claim 1 wherein symmetrically distributing the protection group members on the partitions using modulo arithmetic comprises locating members of protection group (X+Y) modulo (D+P+1) on the partition at drive X of partition Y.
4. The method of claim 1 wherein symmetrically distributing the protection group members on the partitions using modulo arithmetic comprises locating members of protection group (X-Y) modulo (D+P+1) on the partition at drive X of partition Y.
5. The method of claim 1 wherein selecting (D+P) protection group members comprises selecting the (D+P) protection group members from the lowest sequentially numbered unrotated partition of the (D+P) lowest sequentially numbered drives.
6. The method of claim 1 wherein rotating the selected protection group members to the new drive comprises rotating the (D+P) protection group members from the drives in ascending order to the partitions of the new drive in ascending order.
7. The method of claim 1 comprising splitting the drives into two independent groups when (D+P) new drives have been added.
8. An apparatus, comprising:
a plurality of non-volatile drives;
a plurality of interconnected compute nodes that manage access to the drives; and
a drive manager configured to:
create (D+P) partitions that are equal in size and number on (D+P+1) drives;
create protection groups that have D data members and P parity members by symmetrically distributing the protection group members on the partitions using modulo arithmetic;
individually add new drives with (D+P) partitions equal in size and number to the partitions of the (D+P) drives;
for each of the new drives:
select (D+P) protection group members located on an unrotated partition of the (D+P) drives;
rotate the (D+P) selected protection group members from the unrotated partition to the new drive; and
create a new protection group using partitions freed by rotating the selected protection group members to the new drive.
9. The apparatus of claim 8 wherein the drive manager creates (D+P) protection groups and a spare group of (D+P) spare partitions.
10. The apparatus of claim 8 wherein the drive manager locates members of protection group (X+Y) modulo (D+P+1) on the partition at drive X of partition Y.
11. The apparatus of claim 8 wherein the drive manager locates members of protection group (X−Y) modulo (D+P+1) on the partition at drive X of partition Y.
12. The apparatus of claim 8 wherein the drive manager selects the (D+P) protection group members from the lowest sequentially numbered unrotated partition of the (D+P) lowest sequentially numbered drives.
13. The apparatus of claim 8 wherein the drive manager rotates the (D+P) protection group members from the drives in ascending order to the partitions of the new drive in ascending order.
14. The apparatus of claim 8 wherein the drive manager splits the drives into two independent groups when (D+P) new drives have been added.
15. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method for using a computer system to scale a subset of drives, the method comprising:
creating (D+P) partitions that are equal in size and number on (D+P+1) drives;
creating protection groups that have D data members and P parity members by symmetrically distributing the protection group members on the partitions using modulo arithmetic;
individually adding new drives with (D+P) partitions equal in size and number to the partitions of the (D+P) drives;
for each of the new drives:
selecting (D+P) protection group members located on an unrotated partition of the (D+P) drives;
rotating the (D+P) selected protection group members from the unrotated partition to the new drive; and
creating a new protection group using partitions freed by rotating the selected protection group members to the new drive.
16. The non-transitory computer-readable storage medium of claim 15 wherein the method further comprises creating (D+P) protection groups and a spare group of (D+P) spare partitions.
17. The non-transitory computer-readable storage medium of claim 15 wherein the method further comprises locating members of protection group (X+Y) modulo (D+P+1) on the partition at drive X of partition Y.
18. The non-transitory computer-readable storage medium of claim 15 wherein the method further comprises locating members of protection group (X−Y) modulo (D+P+1) on the partition at drive X of partition Y.
19. The non-transitory computer-readable storage medium of claim 15 wherein the method further comprises selecting the (D+P) protection group members from the lowest sequentially numbered unrotated partition of the (D+P) lowest sequentially numbered drives.
20. The non-transitory computer-readable storage medium of claim 15 wherein the method further comprises rotating the (D+P) protection group members from the drives in ascending order to the partitions of the new drive in ascending order.