Balancing storage node utilization of a dispersed storage network

• US 9,794,337 B2
• Filed: 09/17/2013
• Issued: 10/17/2017
• Est. Priority Date: 10/30/2012
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Peake, Andrew George, Resch, Jason K., Motwani, Manish
• Primary Examiner(s): Vu, Viet
• Application Number:
  US14/028,881
• Publication Number:
  US 20140122636A1
• Time in Patent Office: 1,491 Days
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: H04L 67/1097 for distributed storage of data in networks, e.g. transport arrangements for network file system [NFS], storage area networks [SAN] or network attached storage [NAS]

Abstract

A method begins by a dispersed storage (DS) processing module determining memory space utilization state of logical storage nodes of a dispersed storage network DSN. When a logical storage node is in an over-utilized memory space utilization state and another logical storage node is in an under-utilized memory space utilization state, the method continues with the DS processing module selecting the other logical storage node to produce a selected logical storage node and reassigning a portion of a DSN address range assigned to the selected logical storage node to a logical storage node that is in an average memory space utilization state to create an address free logical storage node. The method continues with the DS processing module reassigning address blocks assigned to the logical storage node that is in the over-utilized memory space utilization state to the address free logical storage node.

Claims

1. A method for execution by one or more processing modules of one or more computing devices of a dispersed storage network (DSN), the method comprises:

determining memory space utilization state of a plurality of logical storage nodes of the DSN, wherein DSN memory of the DSN is logically divided into the plurality of logical storage nodes, wherein a DSN address range of the DSN memory is assigned to the plurality of logical storage nodes, wherein a logical storage node of the plurality of logical storage nodes is assigned a portion of the DSN address range, and wherein the memory space utilization state of the logical storage node of the plurality of logical storage nodes is under-utilized, over-utilized, or average; and

when one or more logical storage nodes of the plurality of logical storage nodes is in the over-utilized memory space utilization state and another one or more logical storage nodes of the plurality of logical storage nodes is in the under-utilized memory space utilization state;

selecting one of the other one or more logical storage nodes of the plurality of logical storage nodes that is in the under-utilized memory space utilization state to produce a selected logical storage node;

reassigning the portion of the DSN address range assigned to the selected logical storage node to one or more logical storage nodes of the plurality of logical storage nodes that is in the average memory space utilization state to create an address free logical storage node; and

reassigning one or more address blocks of the portion of the DSN address range assigned to one of the one or more logical storage nodes of the plurality of logical storage nodes that is in the over-utilized memory space utilization state to the address free logical storage node.

2. The method of claim 1, wherein the determining the memory space utilization state comprises:

for each logical storage node of the plurality of logical storage nodes;

determining a quantity of addresses of the assigned portion of the DSN address range that are utilized;

when the quantity compares unfavorably to an address over-used threshold, indicating the over-utilized memory space utilization state;

when the quantity compares unfavorably to an address under-used threshold, indicating the under-utilized memory space utilization state; and

when the quantity compares favorably to the address over-used threshold and to the address under-used threshold, indicating the average memory space utilization state.

3. The method of claim 2 further comprises:

determining the address over-used threshold and the address under-used threshold based on a function of overall address usage of the DSN memory and a ratio between desired address overuse and underuse levels.

4. The method of claim 1, wherein the determining the memory space utilization state comprises:

for each logical storage node of the plurality of logical storage nodes;

determining a data storage level;

when the data storage level compares unfavorably to a storage over-used threshold, indicating the over-utilized memory space utilization state;

when the data storage level compares unfavorably to a storage under-used threshold, indicating the under-utilized memory space utilization state; and

when the data storage level compares favorably to the storage over-used threshold and to the storage under-used threshold, indicating the average memory space utilization state.

5. The method of claim 4 further comprises:

determining the storage over-used threshold and the storage under-used threshold based on a function of overall storage usage of the DSN memory and a ratio between storage overuse and underuse levels.

6. The method of claim 1 further comprises:

the determining the memory space utilization state of the plurality of logical storage nodes based on an initial balanced assignment of portions of the DSN address range among the plurality of logical storage nodes and a balanced allocation of physical memory space among the plurality of logical storage nodes.

7. The method of claim 1, wherein the selecting the selected logical storage node comprises at least one of:

selecting a least used one of the other one or more logical storage nodes of the plurality of logical storage nodes that is in the under-utilized memory space utilization state as the selected logical storage node; and

selecting the least used one of the other one or more logical storage nodes of the plurality of logical storage nodes that is in the under-utilized memory space utilization state and has a neighboring logical storage node in the average memory space utilization state as the selected logical storage node.

8. The method of claim 1, wherein the reassigning the portion of the DSN address range assigned comprises:

identifying neighboring logical storage nodes of the plurality of logical storage nodes of the selected logical storage node;

when at least one of the neighboring logical storage nodes is in the average memory space utilization state, selecting the at least one of the neighboring logical storage nodes as the one or more logical storage nodes of the plurality of logical storage nodes; and

transferring data stored in the address free logical storage node to the one or more logical storage nodes of the plurality of logical storage nodes.

9. The method of claim 8, wherein the selecting comprises:

determining that the one or more logical storage nodes of the plurality of logical storage nodes has memory space capacity to receive the data stored in the address free logical storage node and remain in the average memory space utilization state.

10. The method of claim 1, wherein the reassigning the one or more address blocks of the portion of the DSN address range comprises at least one of:

selecting the one or more address blocks based on at least one of;

ordering of the DSN address range and utilization of address blocks of the portion of the DSN address range; and

partitioning the portion of the DSN address range into a plurality of address blocks and selecting the one or more address blocks from the plurality of address blocks.

11. The method of claim 1, wherein the determining the memory space utilization state of the plurality of logical storage nodes comprises:

determining vault utilization levels of a plurality of storage vaults, wherein a storage vault of the plurality of storage vaults is a logical assignment of at least a portion of one or more of the plurality of logical storage nodes to a user entity.

12. The method of claim 1 further comprises:

the DSN memory including a plurality of sites, wherein a site of the plurality of sites includes one or more physical storage units, wherein the logical storage node maps to;

at least a portion of one of the one or more physical storage units of one of the plurality of sites;

at least a portion of multiple physical storage units of one of the plurality of sites;

at least a portion of one of the one or more physical storage units of multiple sites of the plurality of sites;

or

at least a portion of multiple physical storage units of multiple sites of the plurality of sites.

13. A dispersed storage (DS) module of a dispersed storage network (DSN), the DS module comprises:

a utilization module, when operable within a computing device, causes the computing device to;

determine memory space utilization state of a plurality of logical storage nodes of the DSN, wherein DSN memory of the DSN is logically divided into the plurality of logical storage nodes, wherein a DSN address range of the DSN memory is assigned to the plurality of logical storage nodes, wherein a logical storage node of the plurality of logical storage nodes is assigned a portion of the DSN address range, and wherein the memory space utilization state of the logical storage node of the plurality of logical storage nodes is under-utilized, over-utilized, or average; and

an address range assignment module, when operable within the computing device, causes the computing device to;

when one or more logical storage nodes of the plurality of logical storage nodes is in the over-utilized memory space utilization state and another one or more logical storage nodes of the plurality of logical storage nodes is in the under-utilized memory space utilization state;

select one of the other one or more logical storage nodes of the plurality of logical storage nodes that is in the under-utilized memory space utilization state to produce a selected logical storage node;

reassign the portion of the DSN address range assigned to the selected logical storage node to one or more logical storage nodes of the plurality of logical storage nodes that is in the average memory space utilization state to create an address free logical storage node; and

reassign one or more address blocks of the portion of the DSN address range assigned to one of the one or more logical storage nodes of the plurality of logical storage nodes that is in the over-utilized memory space utilization state to the address free logical storage node.

14. The DS module of claim 13, wherein the utilization module functions to determine the memory space utilization state by:

for each logical storage node of the plurality of logical storage nodes;

determining a quantity of addresses of the assigned portion of the DSN address range that are utilized;

when the quantity compares unfavorably to an address over-used threshold, indicating the over-utilized memory space utilization state;

when the quantity compares unfavorably to an address under-used threshold, indicating the under-utilized memory space utilization state; and

when the quantity compares favorably to the address over-used threshold and to the address under-used threshold, indicating the average memory space utilization state.

15. The DS module of claim 14 further comprises:

the utilization module, when operable within the computing device, further causes the computing device to;

determine the address over-used threshold and the address under-used threshold based on a function of overall address usage of the DSN memory and a ratio between desired address overuse and underuse levels.

16. The DS module of claim 13, wherein the utilization module functions to determine the memory space utilization state by:

for each logical storage node of the plurality of logical storage nodes;

determining a data storage level;

when the data storage level compares unfavorably to a storage over-used threshold, indicating the over-utilized memory space utilization state;

when the data storage level compares unfavorably to a storage under-used threshold, indicating the under-utilized memory space utilization state; and

when the data storage level compares favorably to the storage over-used threshold and to the storage under-used threshold, indicating the average memory space utilization state.

17. The DS module of claim 16 further comprises:

the utilization module, when operable within the computing device, further causes the computing device to;

determine the storage over-used threshold and the storage under-used threshold based on a function of overall storage usage of the DSN memory and a ratio between storage overuse and underuse levels.

18. The DS module of claim 13 further comprises:

the utilization module, when operable within the computing device, further causes the computing device to;

determine the memory space utilization state of the plurality of logical storage nodes based on an initial balanced assignment of portions of the DSN address range among the plurality of logical storage nodes and a balanced allocation of physical memory space among the plurality of logical storage nodes.

19. The DS module of claim 13, wherein the address range assignment module functions to select the selected logical storage node by at least one of:

selecting a least used one of the other one or more logical storage nodes of the plurality of logical storage nodes that is in the under-utilized memory space utilization state as the selected logical storage node; and

selecting the least used one of the other one or more logical storage nodes of the plurality of logical storage nodes that is in the under-utilized memory space utilization state and has a neighboring logical storage node in the average memory space utilization state as the selected logical storage node.

20. The DS module of claim 13, wherein the address range assignment module functions to reassign the portion of the DSN address range assigned by:

identifying neighboring logical storage nodes of the plurality of logical storage nodes of the selected logical storage node;

when at least one of the neighboring logical storage nodes is in the average memory space utilization state, selecting the at least one of the neighboring logical storage nodes as the one or more logical storage nodes of the plurality of logical storage nodes; and

transferring data stored in the address free logical storage node to the one or more logical storage nodes of the plurality of logical storage nodes.

21. The DS module of claim 20, wherein the selecting comprises:

determining that the one or more logical storage nodes of the plurality of logical storage nodes has memory space capacity to receive the data stored in the address free logical storage node and remain in the average memory space utilization state.

22. The DS module of claim 13, wherein the address range assignment module functions to reassign the one or more address blocks of the portion of the DSN address range by at least one of:

selecting the one or more address blocks based on at least one of;

ordering of the DSN address range and utilization of address blocks of the portion of the DSN address range; and

partitioning the portion of the DSN address range into a plurality of address blocks and selecting the one or more address blocks from the plurality of address blocks.

23. The DS module of claim 13, wherein the utilization module functions to determine the memory space utilization state of the plurality of logical storage nodes by:

determining vault utilization levels of a plurality of storage vaults, wherein a storage vault of the plurality of storage vaults is a logical assignment of at least a portion of one or more of the plurality of logical storage nodes to a user entity.

24. The DS module of claim 13 further comprises:

the DSN memory including a plurality of sites, wherein a site of the plurality of sites includes one or more physical storage units, wherein the logical storage node maps to;

at least a portion of one of the one or more physical storage units of one of the plurality of sites;

at least a portion of multiple physical storage units of one of the plurality of sites;

at least a portion of one of the one or more physical storage units of multiple sites of the plurality of sites;

or

at least a portion of multiple physical storage units of multiple sites of the plurality of sites.