BALANCING MEMORY UTILIZATION IN A DISPERSED STORAGE NETWORK

• US 20120117351A1
• Filed: 11/04/2011
• Published: 05/10/2012
• Est. Priority Date: 11/09/2010
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Motwani, Manish, Baptist, Andrew
• Granted Patent: US 10,084,770 B2
• Time in Patent Office: Days
• US Class Current: 711/165
• 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 comprises:

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;

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; and

when the available memory imbalance exists, migrating one or more encoded data slices between the first and second memory devices to reduce the available memory imbalance.

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

determining an available memory value of the first memory device;

determining an available memory value of the second memory device;

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 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 1 further comprises:

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

when the second available memory imbalance exists, migrating another one or more encoded data slices between the third and fourth memory devices to reduce the available memory imbalance.

5. The method of claim 4 further comprises:

comparing the available memory imbalance with the second available memory imbalance; and

prioritizing the migrating of the one or more encoded data slices between the first and second memory devices and the migrating of the other one or more encoded data slices between the third and fourth memory devices based on the comparing.

6. The method of claim 1 further comprises:

updating a slice location table based on the migrating the one or more encoded data slices between the first and second memory devices.

7. The method of claim 1, wherein the migrating the one or more encoded data slices between the first and second memory devices comprises:

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

selecting the one or more encoded data slices associated with the first memory for migration to produce a migration set of encoded data slices;

retrieving the migration set of encoded data slices from the first memory device;

storing the migration set of encoded data slices in the second memory device;

modifying a first set of DSN addresses associated with the first memory device to produce a modified first set of DSN addresses; and

modifying a second set of DSN addresses associated with the second memory device to produce a modified second set of DSN addresses.

8. The method of claim 7, wherein the selecting the one or more encoded data slices comprises:

determining a magnitude of the available memory imbalance;

determining data size of the one or more encoded data slices; and

selecting the one or more encoded data slices based on the magnitude of the available memory imbalance and the data size of the one or more encoded data slices.

9. The method of claim 7, 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 associated with the migration set of encoded data slices.

10. The method of claim 7, 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 to include DSN addresses associated with the migration set of encoded data slices.

11. A dispersed storage (DS) unit of a dispersed storage network (DSN) memory comprises:

an interface;

a memory that includes a plurality of memory devices; and

a processing module operable to;

store a plurality of encoded data slices in the plurality of memory devices 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;

determine 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; and

when the available memory imbalance exists, migrate one or more encoded data slices between the first and second memory devices to reduce the available memory imbalance.

12. The DS unit of claim 11, wherein the processing module functions to determine whether the available memory imbalance exists by:

determining an available memory value of the first memory device;

determining an available memory value of the second memory device;

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 available memory imbalance exists.

13. The DS unit of claim 12, wherein the processing module functions 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.

14. The DS unit of claim 11, wherein the processing module further functions to:

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

when the second available memory imbalance exists, migrate another one or more encoded data slices between the third and fourth memory devices to reduce the available memory imbalance.

15. The DS unit of claim 14, wherein the processing module further functions to:

compare the available memory imbalance with the second available memory imbalance; and

prioritize the migrating of the one or more encoded data slices between the first and second memory devices and the migrating of the other one or more encoded data slices between the third and fourth memory devices based on the comparing.

16. The DS unit of claim 11, wherein the processing module further functions to:

update a slice location table based on the migrating the one or more encoded data slices between the first and second memory devices.

17. The DS unit of claim 11, wherein the processing module functions to migrate the one or more encoded data slices between the first and second memory devices by:

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

selecting the one or more encoded data slices associated with the first memory for migration to produce a migration set of encoded data slices;

retrieving the migration set of encoded data slices from the first memory;

storing the migration set of encoded data slices in the second memory;

modifying a first set of DSN addresses associated with the first memory device to produce a modified first set of DSN addresses; and

modifying a second set of DSN addresses associated with the second memory device to produce a modified second set of DSN addresses.

18. The DS unit of claim 17, wherein the processing module functions to select the one or more encoded data slices by:

determining a magnitude of the available memory imbalance;

determining data size of the one or more encoded data slices; and

selecting the one or more encoded data slices based on the magnitude of the available memory imbalance and the data size of the one or more encoded data slices.

19. The DS unit of claim 17, wherein the processing module functions 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 associated with the migration set of encoded data slices.

20. The DS unit of claim 17, wherein the processing module functions 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 to include DSN addresses associated with the migration set of encoded data slices.