Balancing storage unit utilization within a dispersed storage network

• US 9,632,722 B2
• Filed: 08/13/2014
• Issued: 04/25/2017
• Est. Priority Date: 05/19/2010
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Motwani, Manish
• Primary Examiner(s): Rutz, Jared
• Assistant Examiner(s): OLSON, ALEX G
• Application Number:
  US14/458,969
• Publication Number:
  US 20140351528A1
• Time in Patent Office: 986 Days
• Field of Search: 711154
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 3/0608 Saving storage space on storage systems
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• 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 2209/04 Masking or blinding
• CPC Class Codes: H04L 2209/34 Encoding or coding, e.g. Huffman coding or error correction
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/0863 involving passwords or one-time passwords network architectures or network communication protocols for using one-time keys in a packet data network H04L63/067
• CPC Class Codes: H04L 9/0869 involving random numbers or seeds
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage

Abstract

A method begins by a processing module determining to move a range of encoded data slices from a first storage unit to a second storage unit of a plurality of storage units, where data objects are dispersed storage error encoded to produce pluralities of sets of encoded data slices, and where the pluralities of sets of encoded data slices are stored in the plurality of storage units. The method continues with the processing module transferring the range of encoded data slices from the first storage unit to the second storage unit. In response to the transferring the range of encoded data slices from the first storage unit to the second storage unit, the method continues with the processing module transferring a corresponding range of second encoded data slices from a third storage unit to a fourth storage unit.

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 to move a range of encoded data slices from a first storage unit to a second storage unit of a plurality of storage units, wherein data objects are dispersed storage error encoded to produce pluralities of sets of encoded data slices, wherein the pluralities of sets of encoded data slices are stored in the plurality of storage units, wherein first encoded data slices of the pluralities of sets of encoded data slices have a first common addressing component within addresses of the first encoded data slices, wherein the first storage unit stores a first sub-set of the first encoded data slices and the second storage unit stores a second sub-set of the first encoded data slices, wherein the range of encoded data slices includes at least some of the first sub-set of the first encoded data slices, and wherein the range of encoded data slices is identified by a corresponding slice address range that includes a range of the addresses of the at least some of the first sub-set of the first encoded data slices;

transferring the range of encoded data slices from the first storage unit to the second storage unit; and

in response to the transferring the range of encoded data slices from the first storage unit to the second storage unit, transferring a corresponding range of second encoded data slices from a third storage unit to a fourth storage unit, wherein the second encoded data slices of the pluralities of sets of encoded data slices have a second common addressing component within addresses of the second encoded data slices, wherein the third storage unit stores a first sub-set of the second encoded data slices and the fourth storage unit stores a second sub-set of the second encoded data slices, wherein the range of second encoded data slices includes at least some of the first sub-set of the second encoded data slices, and wherein the range of second encoded data slices is identified by a second corresponding slice address range that includes a range of the addresses of the at least some of the first sub-set of the second encoded data slices.

2. The method of claim 1 further comprises:

wherein a data object of the data objects is divided into a plurality of data segments, wherein the plurality of data segments is dispersed storage error encoded to produce a plurality of sets of encoded data slices of the pluralities of sets of encoded data slices, wherein a data segment is dispersed storage error encoded to produce a set of encoded data slices of the pluralities of sets of encoded data slices, and wherein the first encoded data slices includes a first encoded data slice of each set of the plurality of sets of encoded data slices.

3. The method of claim 1, wherein the first common addressing component comprises one of:

a number within a range of 1 to a pillar number, wherein the pillar number corresponds to a number of encoded data slices in a set of encoded data slices of the pluralities of sets of encoded data slices;

a storage unit identifier; and

a common random value.

4. The method of claim 1, wherein the determining to move the range of encoded data slices comprises:

determining a loading imbalance between the first storage unit and the second storage unit; and

based on the loading imbalance, selecting the range of encoded data slices.

5. The method of claim 1 further comprises:

in response to the transferring the range of encoded data slices from the first storage unit to the second storage unit, transferring a corresponding range of third encoded data slices from a fifth storage unit to a sixth storage unit, wherein the third encoded data slices of the pluralities of sets of encoded data slices have a third common addressing component within addresses of the third encoded data slices, wherein the fifth storage unit stores a first sub-set of the third encoded data slices and the sixth storage unit stores a second sub-set of the third encoded data slices, wherein the range of third encoded data slices includes at least some of the first sub-set of the third encoded data slices, and wherein the range of third encoded data slices is identified by a third corresponding slice address range that includes a range of the addresses of the at least some of the first sub-set of the third encoded data slices.

6. The method of claim 1 further comprises at least one of:

generating, by the first storage unit, the response to transfer the corresponding range of second encoded data slices; and

generating, by a DSN managing unit, the response to transfer the corresponding range of second encoded data slices.

7. The method of claim 1 further comprises:

updating storage mapping information to reflect the moving of the ranges of first and second encoded data slices.

8. The method claim 1, wherein the determining to move the range of encoded data slices comprises:

determining size of the range of encoded data slices based on a number of encoded data slices included in a batch read or write request.

9. A computer readable memory comprises:

at least one memory section that stores operational instructions that, when executed by one or more processing modules of one or more computing devices of a dispersed storage network (DSN), causes the one or more computing devices to;

determine to move a range of encoded data slices from a first storage unit to a second storage unit of a plurality of storage units, wherein data objects are dispersed storage error encoded to produce pluralities of sets of encoded data slices, wherein the pluralities of sets of encoded data slices are stored in the plurality of storage units, wherein first encoded data slices of the pluralities of sets of encoded data slices have a first common addressing component within addresses of the first encoded data slices, wherein the first storage unit stores a first sub-set of the first encoded data slices and the second storage unit stores a second sub-set of the first encoded data slices, wherein the range of encoded data slices includes at least some of the first sub-set of the first encoded data slices, and wherein the range of encoded data slices is identified by a corresponding slice address range that includes a range of the addresses of the at least some of the first sub-set of the first encoded data slices;

transfer the range of encoded data slices from the first storage unit to the second storage unit; and

in response to the transferring the range of encoded data slices from the first storage unit to the second storage unit, transfer a corresponding range of second encoded data slices from a third storage unit to a fourth storage unit, wherein the second encoded data slices of the pluralities of sets of encoded data slices have a second common addressing component within addresses of the second encoded data slices, wherein the third storage unit stores a first sub-set of the second encoded data slices and the fourth storage unit stores a second sub-set of the second encoded data slices, wherein the range of second encoded data slices includes at least some of the first sub-set of the second encoded data slices, and wherein the range of second encoded data slices is identified by a second corresponding slice address range that includes a range of the addresses of the at least some of the first sub-set of the second encoded data slices.

10. The computer readable memory of claim 9 further comprises:

the at least one memory section stores further operational instructions that, when executed by the one or more processing modules, causes the one or more computing devices of the DSN to;

divide a data object of the data objects into a plurality of data segments; and

dispersed storage error encode the plurality of data segments to produce a plurality of sets of encoded data slices of the pluralities of sets of encoded data slices, wherein a data segment is dispersed storage error encoded to produce a set of encoded data slices of the pluralities of sets of encoded data slices, and wherein the first encoded data slices includes a first encoded data slice of each set of the plurality of sets of encoded data slices.

11. The computer readable memory of claim 9, wherein the first common addressing component comprises one of:

a number within a range of 1 to a pillar number, wherein the pillar number corresponds to a number of encoded data slices in a set of encoded data slices of the pluralities of sets of encoded data slices;

a storage unit identifier; and

a common random value.

12. The computer readable memory of claim 9, wherein the one or more processing modules functions to execute the operational instructions stored by the at least one memory section to cause the one or more computing devices of the DSN to determine to move the range of encoded data by:

determining a loading imbalance between the first storage unit and the second storage unit; and

based on the loading imbalance, selecting the range of encoded data slices.

13. The computer readable memory of claim 9 further comprises:

the at least one memory section stores further operational instructions that, when executed by the one or more processing modules, causes the one or more computing devices of the DSN to;

in response to the transferring the range of encoded data slices from the first storage unit to the second storage unit, transfer a corresponding range of third encoded data slices from a fifth storage unit to a sixth storage unit, wherein the third encoded data slices of the pluralities of sets of encoded data slices have a third common addressing component within addresses of the third encoded data slices, wherein the fifth storage unit stores a first sub-set of the third encoded data slices and the sixth storage unit stores a second sub-set of the third encoded data slices, wherein the range of third encoded data slices includes at least some of the first sub-set of the third encoded data slices, and wherein the range of third encoded data slices is identified by a third corresponding slice address range that includes a range of the addresses of the at least some of the first sub-set of the third encoded data slices.

14. The computer readable memory of claim 9 further comprises:

the at least one memory section stores further operational instructions that, when executed by the one or more processing modules, causes the one or more computing devices of the DSN to;

generate, by the first storage unit, the response to transfer the corresponding range of second encoded data slices; and

/or

generate, by a DSN managing unit, the response to transfer the corresponding range of second encoded data slices.

15. The computer readable memory of claim 9 further comprises:

the at least one memory section stores further operational instructions that, when executed by the one or more processing modules, causes the one or more computing devices of the DSN to;

update storage mapping information to reflect the moving of the ranges of first and second encoded data slices.

16. The computer readable memory of claim 9, wherein the one or more processing modules functions to execute the operational instructions stored by the at least one memory section to cause the one or more computing devices of the DSN to determine to move the range of encoded data slices by:

determining size of the range of encoded data slices based on a number of encoded data slices included in a batch read or write request.

17. A computing device comprises:

an interface;

a memory; and

a processing module operably coupled to the interface and the memory, wherein the processing module functions to;

determine to move a range of encoded data slices from a first storage unit to a second storage unit of a plurality of storage units, wherein data objects are dispersed storage error encoded to produce pluralities of sets of encoded data slices, wherein the pluralities of sets of encoded data slices are stored in the plurality of storage units, wherein first encoded data slices of the pluralities of sets of encoded data slices have a first common addressing component within addresses of the first encoded data slices, wherein the first storage unit stores a first sub-set of the first encoded data slices and the second storage unit stores a second sub-set of the first encoded data slices, wherein the range of encoded data slices includes at least some of the first sub-set of the first encoded data slices, and wherein the range of encoded data slices is identified by a corresponding slice address range that includes a range of the addresses of the at least some of the first sub-set of the first encoded data slices;

transfer the range of encoded data slices from the first storage unit to the second storage unit; and

in response to the transferring the range of encoded data slices from the first storage unit to the second storage unit, transfer a corresponding range of second encoded data slices from a third storage unit to a fourth storage unit, wherein the second encoded data slices of the pluralities of sets of encoded data slices have a second common addressing component within addresses of the second encoded data slices, wherein the third storage unit stores a first sub-set of the second encoded data slices and the fourth storage unit stores a second sub-set of the second encoded data slices, wherein the range of second encoded data slices includes at least some of the first sub-set of the second encoded data slices, and wherein the range of second encoded data slices is identified by a second corresponding slice address range that includes a range of the addresses of the at least some of the first sub-set of the second encoded data slices.

18. The computing device of claim 17, wherein the processing module further functions to:

divide a data object of the data objects into a plurality of data segments; and

dispersed storage error encode the plurality of data segments to produce a plurality of sets of encoded data slices of the pluralities of sets of encoded data slices, wherein a data segment is dispersed storage error encoded to produce a set of encoded data slices of the pluralities of sets of encoded data slices, and wherein the first encoded data slices includes a first encoded data slice of each set of the plurality of sets of encoded data slices.

19. The computing device of claim 17, wherein the first common addressing component comprises one of:

a number within a range of 1 to a pillar number, wherein the pillar number corresponds to a number of encoded data slices in a set of encoded data slices of the pluralities of sets of encoded data slices;

a storage unit identifier; and

a common random value.

20. The computing device of claim 17, wherein the processing module functions to determine to move the range of encoded data by:

determining a loading imbalance between the first storage unit and the second storage unit; and

based on the loading imbalance, selecting the range of encoded data slices.

21. The computing device of claim 17, wherein the processing module further functions to:

in response to the transferring the range of encoded data slices from the first storage unit to the second storage unit, transfer a corresponding range of third encoded data slices from a fifth storage unit to a sixth storage unit, wherein the third encoded data slices of the pluralities of sets of encoded data slices have a third common addressing component within addresses of the third encoded data slices, wherein the fifth storage unit stores a first sub-set of the third encoded data slices and the sixth storage unit stores a second sub-set of the third encoded data slices, wherein the range of third encoded data slices includes at least some of the first sub-set of the third encoded data slices, and wherein the range of third encoded data slices is identified by a third corresponding slice address range that includes a range of the addresses of the at least some of the first sub-set of the third encoded data slices.

22. The computing device of claim 17, wherein the processing module further functions to:

generate, by the first storage unit, the response to transfer the corresponding range of second encoded data slices; and

/or

generate, by a DSN managing unit, the response to transfer the corresponding range of second encoded data slices.

23. The computing device of claim 17, wherein the processing module further functions to:

update storage mapping information to reflect the moving of the ranges of first and second encoded data slices.

24. The computing device of claim 17, wherein the processing module functions to determine to move the range of encoded data slices by:

determining size of the range of encoded data slices based on a number of encoded data slices included in a batch read or write request.