Load balancing for erasure coding with multiple parities
In a drive cluster in which multiple parity EC (N+P) is implemented, rebuild-related reads are balanced across drives for recovery from drive failure. N members per protection group are read and (P−1) members are skipped, where skipping a member means omission from member rebuild calculations. Per-disk skip counts are calculated, and members that are eligible to be skipped are selected such that per-disk read counts are balanced.
1. A method, comprising:
for a scalable drive cluster in which multiple parity erasure coding of width W is implemented on at least W+1 sequentially indexed drives, each of the drives having W sequentially indexed partitions, each of the partitions having a fixed-size amount of storage capacity equal to storage capacity of other partitions of the scalable drive cluster, protection group members distributed to the partitions with no more than one member of a protection group located on a single one of the drives and reserve capacity partitions distributed across multiple drives of the scalable drive cluster, balancing rebuild-related read operations in the event of drive failure by:
computing a skip count S(n) for each non-failed drive n;
selecting a protection group having a member on a failed one of the drives;
for the selected protection group, selecting one of the non-failed drives having a corresponding member of the selected protection group and being characterized by S(n)>0;
selecting the corresponding member on the selected non-failed drive to be skipped during rebuild;
decrementing S(n); and
iterating until S(n)=0 for all the non-failed drives.
2. The method of claim 1 further comprising computing a read count C(n) as a count of partitions on drive n having protection group members in a set F of the protection groups represented on the failed drive.
3. The method of claim 2 further comprising computing the skip count S(n) as C(n)−A, where A equals an average count of cells to read per drive.
4. The method of claim 3 further comprising computing the average count of cells to read per drive A=(T/R)−1, where T=sum(C(n)) of the drives with rebuild writes and R is a count of protection groups in F.
5. The method of claim 4 further comprising rounding-down S(n) for non-integer values.
6. The method of claim 5 further comprising pre-computing the protection group members to be skipped prior to the drive failure.
7. The method of claim 6 further comprising encoding metadata with a record of pre-computed protection group members to be skipped prior to the drive failure.
8. An apparatus, comprising:
a scalable drive cluster in which multiple parity erasure coding of width W is implemented on at least W+1 sequentially indexed drives, each of the drives having W sequentially indexed partitions, each of the partitions having a fixed-size amount of storage capacity equal to storage capacity of other partitions of the scalable drive cluster, protection group members distributed to the partitions with no more than one member of a protection group located on a single one of the drives and reserve capacity partitions distributed across multiple drives of the scalable drive cluster;
a plurality of interconnected compute nodes that manage access to the drives; and
a rebuild controller configured to:
compute a skip count S(n) for each non-failed drive n;
select a protection group having a member on a failed one of the drives;
for the selected protection group, select one of the non-failed drives having a corresponding member of the selected protection group and being characterized by S(n)>0;
select the corresponding member on the selected non-failed drive to be skipped during rebuild;
decrement S(n); and
iterate until S(n)=0 for all the non-failed drives.
9. The apparatus of claim 8 further comprising the rebuild controller configured to compute a read count C(n) as a count of partitions on drive n having protection group members in a set F of the protection groups represented on the failed drive.
10. The apparatus of claim 9 further comprising the rebuild controller configured to compute the skip count S(n) as C(n)−A, where A equals an average count of cells to read per drive.
11. The apparatus of claim 10 further comprising the rebuild controller configured to compute the average count of cells to read per drive A=(T/R)−1, where T=sum(C(n)) of the drives with rebuild writes and R is a count of protection groups in F.
12. The apparatus of claim 11 further comprising the rebuild controller configured to round-down S(n) for non-integer values.
13. The apparatus of claim 12 further comprising the rebuild controller configured to pre-computing the protection group members to be skipped prior to the drive failure.
14. The apparatus of claim 13 further comprising the rebuild controller configured to encode metadata with a record of pre-computed protection group members to be skipped prior to the drive failure.
15. A non-transitory computer-readable storage medium storing instructions that when executed by a computer cause the computer to perform a method comprising:
for a scalable drive cluster in which multiple parity erasure coding of width W is implemented on at least W+1 sequentially indexed drives, each of the drives having W sequentially indexed partitions, each of the partitions having a fixed-size amount of storage capacity equal to storage capacity of other partitions of the scalable drive cluster, protection group members distributed to the partitions with no more than one member of a protection group located on a single one of the drives and reserve capacity partitions distributed across multiple drives of the scalable drive cluster, balancing rebuild-related read operations in the event of drive failure by:
computing a skip count S(n) for each non-failed drive n;
selecting a protection group having a member on a failed one of the drives;
for the selected protection group, selecting one of the non-failed drives having a corresponding member of the selected protection group and being characterized by S(n)>0;
selecting the corresponding member on the selected non-failed drive to be skipped during rebuild;
decrementing S(n); and
iterating until S(n)=0 for all the non-failed drives.
16. The non-transitory computer-readable storage medium of claim 15 in which the method further comprises computing a read count C(n) as a count of partitions on drive n having protection group members in a set F of the protection groups represented on the failed drive.
17. The non-transitory computer-readable storage medium of claim 16 in which the method further comprises computing the skip count S(n) as C(n)−A, where A equals an average count of cells to read per drive.
18. The non-transitory computer-readable storage medium of claim 17 in which the method further comprises computing the average count of cells to read per drive A=(T/R)−1, where T=sum(C(n)) of the drives with rebuild writes and R is a count of protection groups in F.
19. The non-transitory computer-readable storage medium of claim 18 in which the method further comprises rounding-down S(n) for non-integer values.
20. The non-transitory computer-readable storage medium of claim 19 in which the method further comprises pre-computing the protection group members to be skipped and encoding metadata with a record of pre-computed protection group members to be skipped prior to the drive failure.