Data unit allocation in distributed storage systems

1 . An apparatus comprising:

at least one processing device comprising a processor coupled to a memory;

the at least one processing device being configured:

to identify data units stored on a plurality of storage nodes of a storage system, wherein at least a first subset of the data units comprise data sub-units stored utilizing a first data striping scheme and at least a second subset of the data units comprise data sub-units stored utilizing a second data striping scheme, where the first data striping scheme stores data sub-units on a first number of the plurality of storage nodes and the second data striping scheme stores data sub-units on a second number of the plurality of storage nodes, the second number being different than the first number;

to maintain a data structure characterizing relationships between the plurality of storage nodes of the storage system, the data structure comprising, for a given data unit stored on a given subset of the plurality of storage nodes, edge weights for data sub-units of the given data unit, the edge weights being proportional to a given number of the data sub-units that are part of the given data unit;

to receive an additional data unit to be stored by the storage system;

to determine, utilizing the data structure, a subset of the plurality of storage nodes of the storage system on which to store data sub-units of the additional data unit; and

to store the data sub-units of the additional data unit on the determined subset of the plurality of storage nodes of the storage system.

2 . The apparatus of claim 1 wherein the first data striping scheme and the second data striping scheme comprise respective Redundant Array of Independent Disk (RAID) schemes.

3 . The apparatus of claim 1 wherein the data units stored on the plurality of storage nodes of the storage system utilize three or more different data striping schemes each having different widths corresponding to numbers of the plurality of storage nodes on which data sub-units of the data units are stored.

4 . The apparatus of claim 1 wherein the at least one processing device is configured to distribute the data units among the plurality of storage nodes to such that sums of edge weights for data sub-units stored in each of the plurality of storage nodes is substantially the same.

5 . The apparatus of claim 1 wherein the edge weights for the given data unit comprise one divided by one less than the given number of the data sub-units that are part of the given data unit.

6 . The apparatus of claim 5 wherein the edge weights for the given data unit are multiplied by a constant value such that all edge weights are integer values.

7 . The apparatus of claim 6 wherein the constant value is a multiplication of all data striping scheme widths utilized by the storage system minus one.

8 . The apparatus of claim 1 wherein the data structure comprises a neighborhood matrix.

9 . The apparatus of claim 8 wherein determining the subset of the plurality of storage nodes of the storage system on which to store the data sub-units of the additional data unit comprises, without migrating any of the data units already stored on the storage system, minimizing the neighborhood matrix in terms of a maximum number of edges between any two of the plurality of storage nodes.

10 . The apparatus of claim 1 wherein determining the subset of the plurality of storage nodes of the storage system on which to store the data sub-units of the additional data unit is further based at least in part on available storage capacity of the plurality of storage nodes.

11 . The apparatus of claim 1 wherein determining the subset of the plurality of storage nodes of the storage system on which to store the data sub-units of the additional data unit is further based at least in part on balancing total numbers of data sub-units stored on each of the plurality of storage nodes.

12 . The apparatus of claim 1 wherein the at least one processing device is further configured to utilize the data structure to perform rebalancing of data units across the plurality of storage nodes of the storage system.

13 . The apparatus of claim 12 wherein the rebalancing is performed periodically.

14 . The apparatus of claim 12 wherein the rebalancing is performed in response to detecting at least a threshold imbalance rate between at least two of the plurality of storage nodes of the storage system.

15 . A computer program product comprising a non-transitory processor-readable storage medium having stored therein program code of one or more software programs, wherein the program code when executed by at least one processing device comprising a processor coupled to a memory, causes the at least one processing device:

to identify data units stored on a plurality of storage nodes of a storage system, wherein at least a first subset of the data units comprise data sub-units stored utilizing a first data striping scheme and at least a second subset of the data units comprise data sub-units stored utilizing a second data striping scheme, where the first data striping scheme stores data sub-units on a first number of the plurality of storage nodes and the second data striping scheme stores data sub-units on a second number of the plurality of storage nodes, the second number being different than the first number;

to maintain a data structure characterizing relationships between the plurality of storage nodes of the storage system, the data structure comprising, for a given data unit stored on a given subset of the plurality of storage nodes, edge weights for data sub-units of the given data unit, the edge weights being proportional to a given number of the data sub-units that are part of the given data unit;

to receive an additional data unit to be stored by the storage system;

to determine, utilizing the data structure, a subset of the plurality of storage nodes of the storage system on which to store data sub-units of the additional data unit; and

to store the data sub-units of the additional data unit on the determined subset of the plurality of storage nodes of the storage system.

16 . The computer program product of claim 15 wherein the data structure comprises a neighborhood matrix.

17 . The computer program product of claim 16 wherein determining the subset of the plurality of storage nodes of the storage system on which to store the data sub-units of the additional data unit comprises, without migrating any of the data units already stored on the storage system, minimizing the neighborhood matrix in terms of a maximum number of edges between any two of the plurality of storage nodes.

18 . A method comprising:

identifying data units stored on a plurality of storage nodes of a storage system, wherein at least a first subset of the data units comprise data sub-units stored utilizing a first data striping scheme and at least a second subset of the data units comprise data sub-units stored utilizing a second data striping scheme, where the first data striping scheme stores data sub-units on a first number of the plurality of storage nodes and the second data striping scheme stores data sub-units on a second number of the plurality of storage nodes, the second number being different than the first number;

maintaining a data structure characterizing relationships between the plurality of storage nodes of the storage system, the data structure comprising, for a given data unit stored on a given subset of the plurality of storage nodes, edge weights for data sub-units of the given data unit, the edge weights being proportional to a given number of the data sub-units that are part of the given data unit;

receiving an additional data unit to be stored by the storage system;

determining, utilizing the data structure, a subset of the plurality of storage nodes of the storage system on which to store data sub-units of the additional data unit; and

storing the data sub-units of the additional data unit on the determined subset of the plurality of storage nodes of the storage system;

wherein the method is performed by at least one processing device comprising a processor coupled to a memory.

19 . The method of claim 18 wherein the data structure comprises a neighborhood matrix.

20 . The method of claim 19 wherein determining the subset of the plurality of storage nodes of the storage system on which to store the data sub-units of the additional data unit comprises, without migrating any of the data units already stored on the storage system, minimizing the neighborhood matrix in terms of a maximum number of edges between any two of the plurality of storage nodes.