Efficient storage load redistribution

• US 8,924,676 B1
• Filed: 06/29/2011
• Issued: 12/30/2014
• Est. Priority Date: 06/29/2011
• Status: Active Grant

• Current Assignee: Emc IP Holding Company LLC (Dell Technologies Inc.)
• Original Assignee: EMC Corporation (Dell Technologies Inc.)
• Inventors: Anderson, David
• Primary Examiner(s): Bragdon, Reginald
• Assistant Examiner(s): VO, THANH DUC
• Application Number:
  US13/171,771
• Time in Patent Office: 1,280 Days
• US Class Current: 711/165
• CPC Class Codes: G06F 12/0646 Configuration or reconfiguration
• CPC Class Codes: G06F 12/0653 with centralised address assignment

Abstract

An improved technique of redistributing files on a set of storage disks involves specifying a tolerable difference in the load between a most-loaded storage disk and a least-loaded storage disk. From such a specified tolerable difference, a processor generates a file transfer plan listing a set of files to be moved, from which storage disks the files are to be moved and to which storage disks to move the files. File transfer plans which result from allowing the maximum difference in load between the storage disks to be a small but finite amount typically result in a very small number of files to be moved, resulting in much smaller processing times for transferring the files.

Claims

1. A method of redistributing files stored on a set of storage devices, the method comprising:

receiving, by controlling circuitry within a controller, a load balancing tolerance value which identifies a target difference between a load on a most-loaded storage device and a load on a least-loaded storage device of the set of storage devices, a load on a storage device representing an amount of consumed storage space on the storage device;

generating, by the controlling circuitry, a file transfer plan based on (i) a file size of each file stored on the set of storage devices, (ii) a load on each storage device of the set of storage devices and (iii) the load balancing tolerance value; and

transferring, by the controlling circuitry, files between storage devices according to the file transfer plan to redistribute the files stored on the set of storage devices;

wherein the load balancing tolerance value is greater than zero; and

wherein the target difference is a number specified by a user representing a maximum difference tolerable to the user.

2. A method according to claim 1, wherein the file transfer plan includes a transfer table having a set of entries, each entry of the set of entries including:

a file identifier which identifies a file stored on a storage device of the set of storage devices,

a first storage device identifier which identifies a first storage device on which the file identified by the file identifier is stored, and

a second storage device identifier which identifies a second storage device to which the file identified by the file identifier is to be moved; and

wherein transferring the files between the storage devices according to the file transfer plan includes;

in each entry of the set of entries, moving the file identified by the file identifier of the entry from the first storage device identified in the entry to the second storage device identified in the entry;

wherein, after transferring the files according to the set of entries of the transfer table, a difference between the load on the most-loaded storage device and a load on the least-loaded storage device of the set of storage devices is less than or equal to the load balancing tolerance value.

3. A method according to claim 2, wherein generating a file transfer plan includes:

generating a collection of storage device identifiers;

generating a collection of file identifiers;

sorting the storage device identifiers of the collection of storage device identifiers according to an amount of a load on each of the storage devices identified by the storage device identifiers; and

sorting the file identifiers of the collection of files according to the file size of each file identified by a file identifier.

4. A method according to claim 3, further comprising:

classifying a first group of storage device identifiers as source storage device identifiers and a second group of storage device identifiers as destination storage device identifiers, the source storage device identifiers identifying source storage devices to which no files are moved, the destination storage device identifiers identifying destination storage devices from which no files are moved;

wherein generating a collection of storage device identifiers includes;

generating a collection of source storage device identifiers and a collection of destination storage device identifiers;

wherein sorting the storage device identifiers includes;

arranging the collection of source storage device identifiers in a descending order from that identifying a most-loaded source storage device to that identifying a least-loaded source storage device; and

arranging the collection of destination storage device identifiers in an ascending order from that identifying a least-loaded destination storage device to that identifying a most-loaded destination storage device.

5. A method according to claim 4, wherein generating the file transfer plan further includes:

receiving a file transfer index;

adding, to a file list, the file identifiers identifying the files having the largest file size stored on the most-loaded source storage device, the number of file identifiers in the file transfer list being the file transfer index;

repeating, until the file list is empty;

identifying, from the collection of source storage device identifiers, the most-loaded source storage device;

generating an entry of the transfer table, the file identifier of the entry identifying, as the largest file, the file of the file list having the largest file size, the first storage device identifier identifying the source storage device on which the largest file is stored;

removing, from the file list, the largest file;

subtracting, from the value of the load on the most-loaded source storage device, the file size of the largest file; and

arranging the collection of source storage device identifiers in a descending order from that identifying a most-loaded source storage device to that identifying a least-loaded source storage device;

repeating, for each entry in the transfer table;

identifying, from the collection of destination storage device identifiers, the least-loaded destination storage device;

setting, as the second storage device identifier of the entry, the destination storage device identifier identifying the least-loaded destination storage device;

adding, to the value of the load on the least-loaded destination storage device, the file size of the file identified by the file identifier of the entry; and

arranging the collection of destination storage device identifiers in an ascending order from that identifying a least-loaded destination storage device to that identifying a most-loaded destination storage device;

identifying the most-loaded storage device and the least-loaded storage device identified in a combined collection of source storage device identifiers and destination storage device identifiers; and

evaluating a difference in the load on the most-loaded storage device and the least-loaded storage device.

6. A method according to claim 5, wherein generating the file transfer plan further includes:

generating a lower bound and an upper bound of a search interval;

generating an optimum index having an initial value equal to zero;

repeating until the lower bound of the search interval is greater than or equal to the upper bound of the search interval;

identifying, as the file transfer index, a number within the search interval;

if the difference between the load on the most-loaded storage device and the least-loaded storage device is less than or equal to the load balancing tolerance value;

setting a value of the optimum index equal to the file transfer index;

identifying, as the transfer table associated with the value of the optimum index, the file transfer plan generated from the file transfer index; and

setting the value of the upper bound of the search interval to the file transfer index; and

if the difference between the load on the most-loaded storage device and the least-loaded storage device is greater than the load balancing tolerance value;

setting the value of the lower bound of the search interval to one more than the file transfer index;

if the value of the optimum index is greater than zero;

outputting the transfer table associated with the value of the optimum index; and

if the value of the optimum index is less than or equal to than zero;

outputting an error message.

7. A method according to claim 5, wherein the set of storage devices are located within a set of storage servers, each storage server of the set of storage servers including storage devices of the set of storage devices;

wherein the method further comprises;

receiving a server balancing tolerance value which identifies a target difference between a load on a most-loaded storage server and a load on a least-loaded storage server of the set of storage servers, the load on a storage server being the sum of the loads of the storage devices of the storage server;

wherein generating the file transfer plan further includes;

generating a collection of storage server identifiers, each storage server identifier identifying a storage server of the set of storage servers;

sorting the storage server identifiers of the collection of storage server identifiers according to a value of the load on each of the storage servers identified by the storage server identifiers;

identifying, from the collection of storage server identifiers, a most-loaded storage server and a least-loaded storage server;

generating a lower bound and an upper bound of a search interval;

generating an optimum index having an initial value equal to zero;

repeating until the lower bound of the search interval is greater than or equal to the upper bound of the search interval;

identifying, as the file transfer index, a number within the search interval;

if the difference between the load on the most-loaded storage device and the least-loaded storage device is less than or equal to the load balancing tolerance value;

setting a value of the optimum index equal to the file transfer index;

identifying, as the transfer table associated with the value of the optimum index, the file transfer plan generated from the file transfer index; and

setting the value of the upper bound of the search interval to the file transfer index; and

if the difference between the load on the most-loaded storage device and the least-loaded storage device is greater than the load balancing tolerance value;

setting the value of the lower bound of the search interval to one more than the file transfer index;

if the value of the optimum index is greater than zero;

outputting the transfer table associated with the value of the optimum index; and

if the value of the optimum index is less than or equal to than zero;

outputting an error message.

8. A method according to claim 3, wherein generating the file transfer plan further includes:

receiving a threshold file value size; and

removing, from the collection of file identifiers, file identifiers which identify files having a file size smaller than the threshold file size value.

9. A method according to claim 8, wherein each file stored on a set of storage devices includes a set of file segments, information stored in the set of file segments of each file being equivalent to information stored in the file, each file segment of the set of file segments being stored on a different storage device, each file segment being identified by a file identifier which identifies the file segment and the file which includes the file segment;

wherein removing the file identifiers includes;

receiving, from a file identifier of the collection of file identifiers, and indication whether the file identifier identifies a file segment or a file;

if the file identifier identifiers a file segment;

performing a query operation constructed and arranged to ascertain the file size of the file which includes the file segment;

if the size of the file as ascertained by the query operation is less than the threshold file size value, removing the file identifier from the collection of file identifiers; and

if the size of the file as ascertained by the query operation is greater than or equal to the threshold file size value, keeping the file identifier in the collection of file identifiers; and

if the file identifier does not identify a file segment;

removing the file identifier from the collection of file identifiers.

10. A method according to claim 1, wherein transferring the files between the storage devices according to the file transfer plan further includes:

transferring the files identified in the file transfer plan according to a round-robin distribution.

11. A method as in claim 1, wherein transferring the files between the storage devices according to the file transfer plan includes:

terminating the transfer of the files when a difference between the load on the most-loaded storage device and the load on the least-loaded storage device of the set of storage devices is less than or equal to the target difference.

12. A method as in claim 1, wherein the load balancing tolerance value indicates a number of Gigabytes (GB) between the load on the most-loaded storage device and the load on the least-loaded storage device of the set of storage devices;

and

wherein generating the file transfer plan includes counting the number of files to be transferred based on that number of GB.

13. A method as in claim 1, further comprising:

after generating the file transfer plan, comparing a current load difference to the load balancing tolerance value, the current load difference being a difference between the load on the most-loaded storage device and the load on the least-loaded storage device of the set of storage devices, the current load difference being evaluated according to the file transfer plan.

14. A method as in claim 13, further comprising in response to the current load difference being greater than the load balancing tolerance value, generating another file transfer plan prior to transferring the files between the storage devices.

15. A system constructed and arranged to redistribute files stored on a set of storage devices, the system comprising:

a network interface;

a memory; and

a controller which includes controlling circuitry which is coupled to the memory, the controlling circuitry constructed and arranged to;

receive a load balancing tolerance value which identifies a target difference between a load on a most-loaded storage device and a load on a least-loaded storage device of the set of storage devices, a load on a storage device representing an amount of consumed storage space on the storage device;

generate a file transfer plan based on (i) a file size of each file stored on the set of storage devices, (ii) a load on each storage device of the set of storage devices and (iii) the load balancing tolerance value; and

transfer files between storage devices according to the file transfer plan to redistribute the files stored on the set of storage devices;

wherein the load balancing tolerance value is greater than zero; and

wherein the target difference is a number specified by a user representing a maximum difference tolerable to the user.

16. A system according to claim 15, wherein the file transfer plan includes a transfer table having a set of entries, each entry of the set of entries including:

a file identifier which identifies a file stored on a storage device of the set of storage devices,

a first storage device identifier which identifies a first storage device on which the file identified by the file identifier is stored, and

a second storage device identifier which identifies a second storage device to which the file identified by the file identifier is to be moved; and

wherein transferring the files between the storage devices according to the file transfer plan includes;

in each entry of the set of entries, moving the file identified by the file identifier of the entry from the first storage device identified in the entry to the second storage device identified in the entry;

wherein, after transferring the files according to the set of entries of the transfer table, a difference between the load on the most-loaded storage device and a load on the least-loaded storage device of the set of storage devices is less than or equal to the load balancing tolerance value.

17. A system according to claim 16, wherein generating a file transfer plan includes:

generating a collection of storage device identifiers;

generating a collection of file identifiers;

sorting the storage device identifiers of the collection of storage device identifiers according to an amount of a load on each of the storage devices identified by the storage device identifiers; and

sorting the file identifiers of the collection of files according to the file size of each file identified by a file identifier.

18. A system according to claim 17, wherein the controlling circuitry is further constructed and arranged to:

classify a first group of storage device identifiers as source storage device identifiers and a second group of storage device identifiers as destination storage device identifiers, the source storage device identifiers identifying source storage devices to which no files are moved, the destination storage device identifiers identifying destination storage devices from which no files are moved;

wherein generating a collection of storage device identifiers includes;

generating a collection of source storage device identifiers and a collection of destination storage device identifiers;

wherein sorting the storage device identifiers includes;

arranging the collection of source storage device identifiers in a descending order from that identifying a most-loaded source storage device to that identifying a least-loaded source storage device; and

arranging the collection of destination storage device identifiers in an ascending order from that identifying a least-loaded destination storage device to that identifying a most-loaded destination storage device.

19. A system according to claim 18, wherein generating the file transfer plan further includes:

receiving a file transfer index;

adding, to a file list, the file identifiers identifying the files having the largest file size stored on the most-loaded source storage device, the number of file identifiers in the file transfer list being the file transfer index;

repeating, until the file list is empty;

identifying, from the collection of source storage device identifiers, the most-loaded source storage device;

generating an entry of the transfer table, the file identifier of the entry identifying, as the largest file, the file of the file list having the largest file size, the first storage device identifier identifying the source storage device on which the largest file is stored;

removing, from the file list, the largest file;

subtracting, from the value of the load on the most-loaded source storage device, the file size of the largest file; and

arranging the collection of source storage device identifiers in a descending order from that identifying a most-loaded source storage device to that identifying a least-loaded source storage device;

repeating, for each entry in the transfer table;

identifying, from the collection of destination storage device identifiers, the least-loaded destination storage device;

setting, as the second storage device identifier of the entry, the destination storage device identifier identifying the least-loaded destination storage device;

adding, to the value of the load on the least-loaded destination storage device, the file size of the file identified by the file identifier of the entry; and

arranging the collection of destination storage device identifiers in an ascending order from that identifying a least-loaded destination storage device to that identifying a most-loaded destination storage device;

identifying the most-loaded storage device and the least-loaded storage device identified in a combined collection of source storage device identifiers and destination storage device identifiers; and

evaluating a difference in the load on the most-loaded storage device and the least-loaded storage device.

20. A system according to claim 19, wherein generating the file transfer plan further includes:

generating a lower bound and an upper bound of a search interval;

generating an optimum index having an initial value equal to zero;

repeating until the lower bound of the search interval is greater than or equal to the upper bound of the search interval;

identifying, as the file transfer index, a number within the search interval;

if the difference between the load on the most-loaded storage device and the least-loaded storage device is less than or equal to the load balancing tolerance value;

setting a value of the optimum index equal to the file transfer index;

identifying, as the transfer table associated with the value of the optimum index, the file transfer plan generated from the file transfer index; and

setting the value of the upper bound of the search interval to the file transfer index; and

if the difference between the load on the most-loaded storage device and the least-loaded storage device is greater than the load balancing tolerance value;

setting the value of the lower bound of the search interval to one more than the file transfer index;

if the value of the optimum index is greater than zero;

outputting the transfer table associated with the value of the optimum index; and

if the value of the optimum index is less than or equal to than zero;

outputting an error message.

21. A system according to claim 19, wherein the set of storage devices are located within a set of storage servers, each storage server of the set of storage servers including storage devices of the set of storage devices;

wherein the controlling circuitry is further constructed and arranged to;

receive a server balancing tolerance value which identifies a target difference between a load on a most-loaded storage server and a load on a least-loaded storage server of the set of storage servers, the load on a storage server being the sum of the loads of the storage devices of the storage server;

wherein generating the file transfer plan further includes;

generating a collection of storage server identifiers, each storage server identifier identifying a storage server of the set of storage servers;

sorting the storage server identifiers of the collection of storage server identifiers according to a value of the load on each of the storage servers identified by the storage server identifiers;

identifying, from the collection of storage server identifiers, a most-loaded storage server and a least-loaded storage server;

generating a lower bound and an upper bound of a search interval;

generating an optimum index having an initial value equal to zero;

repeating until the lower bound of the search interval is greater than or equal to the upper bound of the search interval;

identifying, as the file transfer index, a number within the search interval;

if the difference between the load on the most-loaded storage device and the least-loaded storage device is less than or equal to the load balancing tolerance value;

setting a value of the optimum index equal to the file transfer index;

identifying, as the transfer table associated with the value of the optimum index, the file transfer plan generated from the file transfer index; and

setting the value of the upper bound of the search interval to the file transfer index; and

if the difference between the load on the most-loaded storage device and the least-loaded storage device is greater than the load balancing tolerance value;

setting the value of the lower bound of the search interval to one more than the file transfer index;

if the value of the optimum index is greater than zero;

outputting the transfer table associated with the value of the optimum index; and

if the value of the optimum index is less than or equal to than zero;

outputting an error message.

22. A system according to claim 17, wherein generating the file transfer plan further includes:

receiving a threshold file value size; and

removing, from the collection of file identifiers, file identifiers which identify files having a file size smaller than the threshold file size value.

23. A system according to claim 22, wherein each file stored on a set of storage devices includes a set of file segments, information stored in the set of file segments of each file being equivalent to information stored in the file, each file segment of the set of file segments being stored on a different storage device, each file segment being identified by a file identifier which identifies the file segment and the file which includes the file segment;

wherein removing the file identifiers includes;

receiving, from a file identifier of the collection of file identifiers, and indication whether the file identifier identifies a file segment or a file;

if the file identifier identifiers a file segment;

performing a query operation constructed and arranged to ascertain the file size of the file which includes the file segment;

if the size of the file as ascertained by the query operation is less than the threshold file size value, removing the file identifier from the collection of file identifiers; and

if the size of the file as ascertained by the query operation is greater than or equal to the threshold file size value, keeping the file identifier in the collection of file identifiers; and

if the file identifier does not identify a file segment;

removing the file identifier from the collection of file identifiers.

24. A computer program product having a non-transitory computer readable storage medium which stores a set of instructions to redistribute files stored on a set of storage devices, the set of instructions, when carried out by a computerized device, causing the computerized device to:

receive a load balancing tolerance value which identifies a target difference between a load on a most-loaded storage device and a load on a least-loaded storage device of the set of storage devices, a load on a storage device representing an amount of consumed storage space on the storage device;

generate a file transfer plan based on (i) a file size of each file stored on the set of storage devices, (ii) a load on each storage device of the set of storage devices and (iii) the load balancing tolerance value; and

transfer files between storage devices according to the file transfer plan to redistribute the files stored on the set of storage devices;

wherein the load balancing tolerance value is greater than zero; and

wherein the target difference is a number specified by a user representing a maximum difference tolerable to the user.