Data distribution for fast recovery in cluster-based storage systems
The described technology is generally directed towards distributing data fragments and coding fragments of a protection group among storage entities (e.g., nodes or disks) based on affinity levels (e.g., maintained in an affinity matrix) that represent dependency relationships between the storage entities with respect to storing protection groups. The technology operates to distribute a protection group's components such that the affinity level between any pair of storage entities is approximately the same as any other pair. In the event of a storage entity failure, as a result of the affinity-based distribution of the protection group components needed for data recovery, a larger number of the other storage entities can be involved in the data recovery (relative to the number likely involved without affinity-based distribution). This tends to assure a better load balance and faster data recovery.
1. A system, comprising:
a processor, and
a memory that stores executable instructions that, when executed by the processor, facilitate performance of operations, the operations comprising:
maintaining an affinity dataset comprising affinity levels that represent numbers of protection groups comprising data fragments and coding fragments stored in corresponding data fragment components and coding fragment components among storage entities of a data storage system;
obtaining a protection group to be stored;
accessing the affinity dataset, based on the affinity levels associated with the storage entities, to determine a selected group of the storage entities for storage of one or more data fragments and coding fragments of the protection group to be stored,
storing the one or more data fragments and coding fragments of the protection group to be stored among the selected group of the storage entities; and
updating the affinity dataset in conjunction with the storing the one or more data fragments and coding fragments to represent updated affinity levels among the storage entities.
2. The system of claim 1 , wherein the operations further comprise determining a group of the storage entities that have capacity blocks available for allocation, and wherein the accessing the affinity dataset comprises reading the affinity levels of the group of the storage entities that have the capacity blocks available for the allocation to determine the selected group of the storage entities.
3. The system of claim 2 , wherein the determining the group of the storage entities that have the capacity blocks available for the allocation comprises obtaining, from a capacity load balancer, capable storage entities that have capacity for the storage of the one or more data fragments and coding fragments of the protection group to be stored, and wherein the accessing the affinity dataset to determine the selected group of the storage entities comprises evaluating respective affinity levels associated with the capable storage entities.
4. The system of claim 1 , wherein the accessing the affinity dataset to determine the selected group of the storage entities comprises determining which of the storage entities have lowest affinity levels of the affinity levels in the affinity dataset.
5. The system of claim 1 , wherein the storage entities comprise nodes of the data storage system.
6. The system of claim 1 , wherein the storage entities comprise storage devices, and wherein the storage devices are arranged as respective storage device groups associated with respective nodes of the data storage system.
7. The system of claim 1 , wherein the storing the protection group components comprises providing the one or more data fragments and coding fragments and the selected group of the storage entities to an input-output load balancer device.
8. The system of claim 1 , wherein the protection group to be stored among the storage entities of the data storage system comprises twelve data fragments, and four coding fragments encoded from the twelve data fragments.
9. The system of claim 1 , wherein the affinity dataset comprises a matrix data structure having a first dimension based on a number of storage entities available for storage of the protection groups and a second dimension based on the number of storage entities.
10. A method comprising,
obtaining, by a system comprising a processor, a protection group, the protection group comprising one or more data fragments and coding fragments to be stored among data storage entities of a data storage system;
obtaining a first group of data storage entities having available capacity for storing the one or more data fragments and coding fragments:
determining a second group of storage entities from the first group of data storage entities, the determining comprising accessing affinity data that represents respective affinity levels indicating numbers of protection groups stored at respective pairs of storage entities of the first group of data storage entities;
storing the one or more data fragments and coding fragments among the second group of storage entities; and
updating the affinity data, based on the storing the one of more data fragments and coding fragments, resulting in updated affinity data.
11. The method of claim 10 , further comprising excluding a storage entity from the first group of data storage entities based on a data distribution constraint.
12. The method of claim 10 , wherein the storing the one or more data fragments and coding fragments comprises outputting the one or more data fragments and coding fragments and the second group of the storage entities to an input-output load balancer device.
13. The method of claim 10 , wherein a portion of the affinity data for a pair of the respective pairs of storage entities represents a number of matching data fragments and coding fragments stored in common by the pair, and wherein the updating the affinity data comprises incrementing the number of matching data fragments and coding fragments for pairs of storage entities of the second group of storage entities.
14. The method of claim 13 , wherein the affinity data is maintained as a symmetrical matrix data structure of values comprising dimensions based on a number of data storage entities that store data fragments and coding fragments in the data storage system, and wherein the incrementing the number of matching data fragments and coding fragments for the pairs of storage entities of the second group of storage entities comprises, for respective pairs, incrementing a respective first matrix value indexed by a respective first identifier of a first associated storage entity of a respective pair and a respective second identifier of a second associated storage entity of the respective pair, and incrementing a respective second matrix value indexed by the respective second identifier of the associated storage entity of the respective pair and the respective first identifier of the first associated storage entity of the respective pair.
15. The method of claim 10 , wherein the obtaining the first group of data storage entities comprises receiving the first group of data storage entities from a capacity load balancer.
16. The method of claim 10 , wherein the storing the one or more data fragments and coding fragments comprises sending the one or more data fragments and coding fragments and the second group of the storage entities to an input-output load balancer device.
17. A non-transitory machine-readable medium, comprising executable instructions that, when executed by a processor, facilitate performance of operations, the operations comprising:
obtaining a candidate group of data storage entities having available capacity for storage of one or more data fragments and coding fragments of a protection group to be stored among data storage entities of a data storage system;
selecting a group of storage entities from the candidate group based on affinity levels associated with respective pairs of storage entities in the candidate group, in which the affinity levels correspond to a number of common data fragments and coding fragments maintained by the respective pairs of storage entities, the selecting resulting in a selected group of storage entities;
storing the one or more data fragments and coding fragments among the selected group of storage entities; and
updating the affinity levels, based on the storing the protection group, into updated affinity levels.
18. The non-transitory machine-readable medium of claim 17 , wherein the operations further comprise excluding a storage entity from the candidate group based on a data distribution constraint.
19. The non-transitory machine-readable medium of claim 17 , wherein the selecting the group of storage entities from the candidate group based on the affinity levels comprises selecting the group of storage entities from the candidate group based on affinity among the storage entities.
20. The non-transitory machine-readable medium of claim 17 , wherein a matrix data structure is used to represent the affinity levels, the matrix data structure having a first dimension based on a number of available storage entities available for storage of protection groups and a second dimension based on a number of the candidate group of data storage entities.