Balancing memory utilization in a dispersed storage network

• US 10,084,770 B2
• Filed: 11/04/2011
• Issued: 09/25/2018
• Est. Priority Date: 11/09/2010
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Motwani, Manish, Baptist, Andrew
• Primary Examiner(s): Sain, Gautam
• Application Number:
  US13/289,200
• Publication Number:
  US 20120117351A1
• Time in Patent Office: 2,517 Days
• Field of Search: 711165
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 12/06 Addressing a physical block of locations, e.g. base addressing, module addressing, memory dedication G06F12/08 takes precedence
• CPC Class Codes: G06F 2211/1057 Parity-multiple bits-RAID6, i.e. RAID 6 implementations
• CPC Class Codes: G06F 3/0605 by facilitating the interaction with a user or administrator
• CPC Class Codes: G06F 3/0614 Improving the reliability of storage systems
• CPC Class Codes: G06F 3/0643 Management of files
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: H04L 63/0823 using certificates cryptographic mechanisms or cryptographic arrangements for entity authentication involving certificates H04L9/3263

Abstract

A method begins by a processing module storing a plurality of encoded data slices in a plurality of memory devices of a dispersed storage (DS) unit of a dispersed storage network (DSN) memory using a quantity load balancing function to substantially balance a quantity of encoded data slices stored within each of the plurality of memory devices, wherein data size of at least some of the plurality of encoded data slices is different. The method continues with the processing module determining whether an available memory imbalance exists between a first memory device of the plurality of memory devices and a second memory device of the plurality of memory devices. The method continues with the processing module migrating one or more encoded data slices between the first and second memory devices to reduce the available memory imbalance when the available memory imbalance exists.

Claims

1. A method for execution by a set of storage units of a dispersed storage network (DSN), the method comprises:

receiving, by the set of storage units of the DSN, sets of encoded data slices for storage;

storing, by each storage unit of the set of storage units, respective groups of encoded data slices of the sets of encoded data slices, wherein a first storage unit of the set of storage units stores a first group of encoded data slices that includes a first encoded data slice from each of the sets of encoded data slices and a second storage unit of the set of storage units stores a second group of encoded data slices that includes a second encoded data slice from each of the sets of encoded data slices;

utilizing, by the first storage unit, a first load balancing scheme to distributedly store the first group of encoded data slices among a first plurality of memory devices of the first storage unit, wherein the first load balancing scheme functions to distribute the first group of encoded data slices substantially equally among the first plurality of memory devices, and further wherein the data size of one or more encoded data slices of the first of group encoded data slices is substantially larger than at least one other encoded data slice of the first of group encoded data slices;

utilizing, by the second storage unit, the first load balancing scheme to distributedly store the second group of encoded data slices among a second plurality of memory devices of the second storage unit, wherein the data size of one or more encoded data slices of the second of group encoded data slices is substantially larger than at least one other encoded data slice of the second of group encoded data slices;

utilizing, by the first storage unit, a second load balancing scheme to redistribute at least one encoded data slice of the first group of encoded data slices between a pair of memory devices within the first plurality of memory devices when a first available memory imbalance exists, wherein said imbalance comprises a difference of at least a threshold amount of available memory between the pair of memory devices, wherein the second load balancing scheme functions to provide approximately equal available memory capacity between the pair of memory devices;

modifying a DSN memory address for the redistributed at least one encoded data slice of the first group of encoded data slices to produce a modified DSN memory address for the redistributed at least one encoded data slice of the first group of encoded data slices;

translating, by the first storage unit, the modified DSN memory address for the redistributed at least one encoded data slice of the first group of encoded data slices to a first physical address,

wherein the first physical address is associated with a memory device from the first plurality of memory devices;

utilizing, by the second storage unit, the second load balancing scheme to redistribute at least one encoded data slice of the second group of encoded data slices between a pair of memory devices within the second plurality of memory devices when a second available memory imbalance exists, wherein said imbalance comprises a difference of at least a threshold amount of available memory between the pair of memory devices within the second plurality of memory devices, wherein the second load balancing scheme functions to provide approximately equal available memory capacity between the pair of memory devices within the second plurality of memory devices;

modifying a DSN memory address for the redistributed at least one encoded data slice of the second group of encoded data slices to produce a modified DSN memory address for the redistributed at least one encoded data slice of the second group of encoded data slices; and

translating, by the second storage unit, the modified DSN memory address for the redistributed at least one encoded data slice of the first group of encoded data slices to a second physical address, wherein the second physical address is associated with a memory device from the second plurality of memory devices.

2. The method of claim 1, wherein determining whether the first available memory imbalance exists comprises:

determining an available memory value of a first memory device of the first plurality of memory devices;

determining an available memory value of a second memory device of the first plurality of memory devices;

determining a difference of available memory value based on the available memory values of the first and second memory device;

comparing the difference of available memory value with an available memory differential threshold; and

when the comparing the difference of available memory value with the available memory differential threshold is unfavorable, indicating that the first available memory imbalance exists.

3. The method of claim 2, wherein the determining the difference available memory value comprises at least one of:

subtracting the available memory value of the first memory device from the available memory value of the second memory device to produce the difference available memory value; and

calculating a migration score based on a subtraction of the available memory value of the first memory device from the available memory value of the second memory device to produce an available memory resultant value and dividing the available memory resultant value from one of the available memory value of the first memory device and the available memory value of the second memory device.

4. The method of claim 2 further comprises:

determining whether another first available memory imbalance exists between a third memory device of the first plurality of memory devices and a fourth memory device of the first plurality of memory devices; and

when the other first available memory imbalance exists, redistributing another at least one encoded data slice of the first group of encoded data slices between the third and fourth memory devices to reduce the other first available memory imbalance.

5. The method of claim 4 further comprises:

comparing the first available memory imbalance with the other first available memory imbalance; and

prioritizing the redistributing the at least one encoded data slice of the first group of encoded data slices between the first and second memory devices and the redistributing the other at least one encoded data slice of the first group of encoded data slices between the third and fourth memory devices based on the comparing.

6. The method of claim 1 further comprises:

when the first available memory imbalance exists because an available memory value of a first memory device of the first plurality of memory devices is less than an available memory value of a second memory device of the first plurality of memory devices;

modifying a first set of DSN addresses of an allocated range of DSN addresses to produce a modified first set of DSN addresses for use in subsequent processing of write requests of the plurality of write requests, wherein the first set of DSN addresses is associated with the first memory device; and

modifying a second set of DSN addresses of the allocated range of DSN addresses associated with the second memory device to produce a modified second set of DSN addresses for use in subsequent processing of write requests of the plurality of write requests.

7. The method of claim 6, wherein the modifying the first set of DSN addresses to produce the modified first set of DSN addresses comprises:

modifying the first set of DSN addresses to exclude DSN addresses of the allocated range of DSN addresses associated with a set of encoded data slices to be redistributed from the first memory device to the second memory device.

8. The method of claim 6, wherein the modifying the second set of DSN addresses to produce the modified second set of DSN addresses comprises:

modifying the second set of DSN addresses of the allocated range of DSN addresses to include DSN addresses associated with a set of encoded data slices to be redistributed from the first memory device to the second memory device.

9. A computer readable memory comprises:

a first memory that stores operational instructions that, when executed by one or more processors of a first storage unit of a set of storage units of a dispersed storage network (DSN), causes the first storage unit to;

receive and store a first group of encoded data slices of sets of encoded data slices, wherein the first group of encoded data slices includes a first encoded data slice from each of the sets of encoded data slices;

utilize a first load balancing scheme to distributedly store the first group of encoded data slices among a first plurality of memory devices of the first storage unit, wherein the first load balancing scheme functions to distribute the first group of encoded data slices substantially equally among the first plurality of memory devices, and further wherein the data size of one or more encoded data slices of the first of group encoded data slices is substantially larger than at least one other encoded data slice of the first of group encoded data slices;

utilize a second load balancing scheme to redistribute at least one encoded data slice of the first group of encoded data slices between a pair of memory devices within the first plurality of memory devices when a first available memory imbalance exists, wherein said imbalance comprises a difference of at least a threshold amount of available memory between the pair of memory devices, wherein the second load balancing scheme functions to provide approximately equal available memory capacity between the pair of memory devices;

modify a DSN memory address for the redistributed at least one encoded data slice of the first group of encoded data slices to produce a modified DSN memory address for the redistributed at least one encoded data slice of the first group of encoded data slices;

translate the modified DSN memory address for the redistributed at least one encoded data slice of the first group of encoded data slices to a first physical address, wherein the first physical address is associated with a memory device from the first plurality of memory devices;

a second memory that stores operational instructions that, when executed by one or more processors of a second storage unit of the set of storage units, causes the second storage unit to;

receive and store a second group of encoded data slices of the sets of encoded data slices, wherein the second group of encoded data slices includes a second encoded data slice from each of the sets of encoded data slices;

utilize the first load balancing scheme to distributedly store the second group of encoded data slices among a second plurality of memory devices of the second storage unit;

utilize the second load balancing scheme to redistribute at least one encoded data slice of the second group of encoded data slices between a pair of memory devices within the second plurality of memory devices when a second available memory imbalance exists, wherein said imbalance comprises a difference of at least a threshold amount of available memory between the pair of memory devices within the second plurality of memory devices, wherein the second load balancing scheme functions to provide approximately equal available memory capacity between the pair of memory devices within the second plurality of memory devices;

modify the DSN memory address for the redistributed at least one encoded data slice of the second group of encoded data slices to produce a modified DSN memory address for the redistributed at least one encoded data slice of the second group of encoded data slices; and

translate the modified DSN memory address for the redistributed at least one encoded data slice of the first group of encoded data slices to a second physical address, wherein the second physical address is associated with a memory device from the second plurality of memory devices.

10. The computer readable memory of claim 9, wherein the first memory further stores operational instructions that, when executed by one or more processors of the first storage unit, causes the first storage unit to determine whether the first available memory imbalance exists by:

determining an available memory value of a first memory device of the first plurality of memory devices;

determining an available memory value of a second memory device of the first plurality of memory devices;

determining a difference available memory value based on the available memory values of the first and second memory device;

comparing the difference available memory value with an available memory differential threshold; and

when the comparing the difference available memory value with the available memory differential threshold is unfavorable, indicating that the first available memory imbalance exists.

11. The computer readable memory of claim 10, wherein the first memory further stores operational instructions that, when executed by one or more processors of the first storage unit, causes the first storage unit to determine the difference available memory value by at least one of:

subtracting the available memory value of the first memory device from the available memory value of the second memory device to produce the difference available memory value; and

calculating a migration score based on the subtraction of the available memory value of the first memory device from the available memory value of the second memory device to produce an available memory resultant value and dividing the available memory resultant value from one of the available memory value of the first memory device and the available memory value of the second memory device.

12. The computer readable memory of claim 10, wherein the first memory further stores operational instructions that, when executed by one or more processors of the first storage unit, causes the first storage unit to:

determine whether another first available memory imbalance exists between a third memory device of the first plurality of memory devices and a fourth memory device of the first plurality of memory devices; and

when the other first available memory imbalance exists, redistribute another at least one encoded data slice of the first group of encoded data slices between the third and fourth memory devices to reduce the other first available memory imbalance.

13. The computer readable memory of claim 12, wherein the first memory further stores operational instructions that, when executed by one or more processors of the first storage unit, causes the first storage unit to:

compare the first available memory imbalance with the other first available memory imbalance; and

prioritize the redistribution of the at least one encoded data slice of the first group of encoded data slices between the first and second memory devices and the redistribution of the other at least one encoded data slice of the first group of encoded data slices between the third and fourth memory devices based on the comparing.

14. The computer readable memory of claim 9, wherein the first memory further stores operational instructions that, when executed by one or more processors of the first storage unit, causes the first storage unit to:

when the first available memory imbalance exists because an available memory value of a first memory device of the first plurality of memory devices is less than an available memory value of a second memory device of the first plurality of memory devices;

modify a first set of DSN addresses of an allocated range of DSN addresses of the storage unit to produce a modified first set of DSN addresses for use in subsequent processing of write requests of the plurality of write requests, wherein the first set of DSN addresses is associated with the first memory device; and

modify a second set of DSN addresses of the allocated range of DSN addresses associated with the second memory device to produce a modified second set of DSN addresses for use in subsequent processing of write requests of the plurality of write requests.

15. The computer readable memory of claim 14, wherein the first memory further stores operational instructions that, when executed by one or more processors of the first storage unit, causes the first storage unit to modify the first set of DSN addresses to produce the modified first set of DSN addresses by:

modifying the first set of DSN addresses to exclude DSN addresses of the allocated range of DSN addresses associated with a set of encoded data slices to be redistributed from the first memory device to the second memory device.

16. The computer readable memory of claim 14, wherein the first memory further stores operational instructions that, when executed by one or more processors of the first storage unit, causes the first storage unit to modify the second set of DSN addresses to produce the modified second set of DSN addresses by:

modifying the second set of DSN addresses of the allocated range of DSN addresses to include DSN addresses associated with a set of encoded data slices to be redistributed from the first memory device to the second memory device.