Optimizing spare capacity and spare distribution
Configuring spare sections in a system having a plurality of devices and having a plurality of erasure encoding groups, each of the devices having a plurality of sections and each of the groups having a plurality of members located on the sections of the devices, includes configuring the system to have a plurality of erasure encoding groups with no spare sections, ordering the groups according to desirability of converting members of each of the groups into spare sections, converting members of a subset of the groups into spare sections according to ordering of the groups, and determining if the spare sections for the system provide sufficient coverage for the system in response to failure of each of the devices. The erasure encoding may be a RAID encoding.
1. A method of configuring spare sections in a data storage system having a plurality of devices and having a plurality of erasure encoding groups, each of the devices having a plurality of sections and each of the groups having a plurality of members located on the sections of the devices, the method comprising:
configuring the data storage system to have a plurality of erasure encoding groups with no spare sections;
ordering the groups according to a total collision count that corresponds to a weighted sum of collision counts between each of the groups and each other ones of the groups;
mapping members of a subset of the groups into spare sections according to the ordering of the groups; and
determining if the spare sections for the system provide sufficient coverage for the system in response to failure of each of the devices, wherein the determining if the spare sections for the system provide sufficient coverage includes trying different combinations of spare assignments and, in response to a combination that does not work, choosing a next combination that swaps two of the spare assignments.
2. A method, according to claim 1 , wherein the determining if the spare sections provide sufficient coverage includes determining if each of the erasure encoding groups can be reconstructed using the spare sections following a failure of each of the devices.
3. A method, according to claim 1 , wherein a weighting function is used to determine the weighted sum and is provided by:
w ( c ij )=(max− c ij ) 2
where c ij is a collision count between erasure coding group i and erasure coding group j and max is a maximum value of the collision count for all of the erasure groups.
4. A method, according to claim 3 , wherein the total collision count is provided by:
TCC i =Σ j=1 NRG w ( c ij ) c ij
where NEG is a total number of erasure groups.
5. A method, according to claim 1 , wherein ordering the groups includes providing a list of groups in order according to the total collision count.
6. A method, according to claim 1 , wherein the determining if the spare sections for the system provide sufficient coverage includes simulating failure of each of the devices.
7. A method, according to claim 6 , wherein the determining if the spare sections for the system provide sufficient coverage includes using an Edmonds-Karp technique.
8. A method, according to claim 1 , wherein the erasure coding is RAID erasure coding.
9. A non-transitory computer-readable medium containing software that configures spare sections in a data_storage system having a plurality of devices and having a plurality of erasure encoding groups, each of the devices having a plurality of sections and each of the groups having a plurality of members located on the sections of the devices, the software comprising:
executable code that configures the data storage system to have a plurality of erasure encoding groups with no spare sections;
executable code that orders the groups according to a total collision count that corresponds to a weighted sum of collision counts between each of the groups and each other ones of the groups;
executable code that maps members of a subset of the groups into spare sections according to the ordering of the groups; and
executable code that determines if the spare sections for the system provide sufficient coverage for the system in response to failure of each of the devices, wherein the executable code that determines if the spare sections for the system provide sufficient coverage tries different combinations of spare assignments and, in response to a combination that does not work, chooses a next combination that swaps two of the spare assignments.
10. A non-transitory computer-readable medium, according to claim 9 , wherein the executable code that determines if the spare sections provide sufficient coverage determines if each of the erasure encoding groups can be reconstructed using the spare sections following a failure of each of the devices.
11. A non-transitory computer-readable medium, according to claim 9 , wherein the weighting function is used to determine the weighted sum and is provided by:
w ( c ij )=(max− c ij ) 2
where c ij is a collision count between erasure coding group i and erasure coding group j and max is a maximum value of the collision count for all of the erasure groups.
12. A non-transitory computer-readable medium, according to claim 11 , wherein the total collision count is provided by:
TCC i =Σ j=1 NRG w ( c ij ) c ij
where NEG is a total number of erasure groups.
13. A non-transitory computer-readable medium, according to claim 9 , wherein the executable code that orders the groups provides a list of groups in order according to the total collision count.
14. A non-transitory computer-readable medium, according to claim 9 , wherein the executable code that determines if the spare sections for the system provide sufficient coverage simulates failure of each of the devices.
15. A non-transitory computer-readable medium, according to claim 14 , wherein the executable code that determines if the spare sections for the system provide sufficient coverage uses an Edmonds-Karp technique.
16. A non-transitory computer-readable medium, according to claim 9 , wherein the erasure coding is RAID erasure coding.