Rebalancing efficiency with optimal logical insertion locations

• US 10,416,906 B2
• Filed: 03/23/2017
• Issued: 09/17/2019
• Est. Priority Date: 03/29/2016
• Status: Active Grant

• Current Assignee: Workday Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Baptist, Andrew D., Khadiwala, Ravi V., Motwani, Manish, Resch, Jason K.
• Primary Examiner(s): Chery, Mardochee
• Application Number:
  US15/467,754
• Publication Number:
  US 20170289250A1
• Time in Patent Office: 908 Days
• Field of Search: 711170
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 21/31 User authentication
• CPC Class Codes: G06F 2221/2133 Verifying human interaction, e.g., Captcha
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0611 in relation to response time
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• CPC Class Codes: G06F 3/0635 by changing the path, e.g. traffic rerouting, path reconfiguration
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/0644 Management of space entities, e.g. partitions, extents, pools
• CPC Class Codes: G06F 3/0647 Migration mechanisms
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 8/65 Updates security arrangements therefor G06F21/57
• CPC Class Codes: G06F 9/485 Task life-cycle, e.g. stopping, restarting, resuming execution G06F9/4881 takes precedence
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: H03M 13/05 using block codes, i.e. a predetermined number of check bits joined to a predetermined number of information bits H03M13/2906 takes precedence
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/373 : with erasure correction and erasure determination, e.g. for packet loss recovery or setting of erasures for the decoding of Reed-Solomon codes
• CPC Class Codes: H03M 13/616 : Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations
• CPC Class Codes: H04L 61/10 : of different types
• CPC Class Codes: H04L 61/50 : Address allocation
• CPC Class Codes: H04L 63/08 : for authentication of entities cryptographic mechanisms or cryptographic arrangements for entity authentication H04L9/32
• CPC Class Codes: H04L 63/104 : Grouping of entities
• CPC Class Codes: H04L 63/108 : when the policy decisions are valid for a limited amount of time
• 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]
• CPC Class Codes: H04L 67/56 : Provisioning of proxy services store-and-forward switching systems in data switching networks H04L12/54

Abstract

A method includes determining, by a managing unit of a dispersed storage network (DSN), an addition of a new storage unit to a group of storage units. The DSN includes a logical address space divided into a set of logical address sub-spaces, one of which is allocated to the group of storage units. The method further includes reorganizing, by the managing unit, distribution of the logical address sub-space among the new storage unit and each storage unit in the group of storage units to produce a reorganized logical address sub-space. The allocation includes the new storage unit'"'"'s portion being between portions of first and second storage units. The method further includes transferring, by the first storage unit, a first group of encoded data slices to the new storage unit and transferring, by the second storage unit, a second group of encoded data slices to the new storage unit.

Claims

1. A method comprises:

determining, by a managing unit of a dispersed storage network (DSN), an addition of a new storage unit to a group of storage units, wherein the DSN includes a logical address space that is divided into a set of logical address sub-spaces, wherein the group of storage units is allocated a logical address sub-space of the set of logical address sub-spaces, and the new storage unit and each storage unit in the group of storage units includes a plurality of memory devices;

reorganizing, by the managing unit, distribution of the logical address sub-space among the new storage unit and each storage unit in the group of storage units to produce a reorganized logical address sub-space, wherein allocation of a first portion of the logical address sub-space is allocated to the new storage unit, wherein the first portion of the logical address sub-space is between second and third portions of the logical address sub-space, wherein the second portion of the logical address sub-space is allocated to a first storage unit of the group of storage units and the third portion of the logical address sub-space is allocated to a second storage unit of the group of storage units;

transferring, by the first storage unit, a first group of encoded data slices to the new storage unit in accordance with the reorganized logical address sub-space;

transferring, by the second storage unit, a second group of encoded data slices to the new storage unit in accordance with the reorganized logical address sub-space;

determining, by the managing unit, an addition of a second new storage unit to a second group of storage units, wherein the second group of storage units is allocated a second logical address sub-space of the set of logical address sub-spaces;

reorganizing, by the managing unit, distribution of the second logical address sub-space among the second new storage unit and each storage unit in the second group of storage units to produce a reorganized second logical address sub-space, wherein allocation of a first portion of the second logical address sub-space is allocated to the second new storage unit, wherein the first portion of the second logical address sub-space is between second and third portions of the second logical address sub-space, wherein the second portion of the second logical address sub-space is allocated to a third storage unit of the second group of storage units and the third portion of the second logical address sub-space is allocated to a fourth storage unit of the second group of storage units;

transferring, by the third storage unit, a third group of encoded data slices to the second new storage unit in accordance with the reorganized second logical address sub-space; and

transferring, by the fourth storage unit, a fourth group of encoded data slices to the second new storage unit in accordance with the reorganized second logical address sub-space.

2. The method of claim 1 further comprises:

allocating, by the new storage unit, the first portion of the logical address sub-space among the plurality of memory devices of the new storage unit to produce a first logical-to-physical storage mapping; and

as encoded data slices are received, storing, by the new storage unit, the encoded data slices in the plurality of memory devices of the new storage unit in accordance with the first logical-to-physical storage mapping.

3. The method of claim 1, wherein the transferring the first group of encoded data slices comprises:

determining, by the first storage unit, logical DSN addresses of a previous portion of the logical address sub-space that was allocated to the first storage unit that are being reallocated to the new storage unit based on a difference between the second portion of the logical address sub-space and the previous portion of the logical address sub-space; and

identifying, by the first storage unit, the first group of encoded data slices as encoded data slices having slice names that correspond to the logical DSN addresses that are being reallocated.

4. The method of claim 3, wherein the identifying the first group of encoded data slices comprises:

accessing, by the first storage unit, a previous logical-to-physical storage mapping of the previous portion of the logical address sub-space to the plurality of memory devices of the first storage unit, wherein, in accordance with the previous logical-to-physical storage mapping, the first group of encoded data slices is stored in a set of memory devices of the plurality of memory devices, wherein the set of memory devices includes one or more memory devices, but less than all of the memory devices, of the plurality of memory devices of the first storage unit.

5. The method of claim 1 further comprises:

identifying, by the first storage unit, a set of memory devices of the plurality of memory devices of the first storage unit that is allocated DSN addresses of a previous portion of the logical address sub-space that are now part of the first portion of the logical address sub-spaces, wherein;

the previous portion of the logical address sub-space was allocated among the plurality of memory devices,

a first memory device of the plurality of memory devices was allocated a first part of the previous portion of the logical address sub-space,

a last memory device of the plurality of memory devices was allocated a last part of the previous portion of the logical address sub-space,

the set of memory devices includes one or more memory devices, but less than all of the memory devices, of the plurality of memory devices of the first storage unit, and

the set of memory devices includes either the first or the last memory device;

reorganizing, by the first storage unit, the previous portion of the logical address sub-space to a new logical-to-physical storage mapping based on the second portion of the logical address sub-space by;

logically repositioning the set of memory devices between other memory devices of the plurality of memory devices of the first storage unit; and

transferring allocation of some DSN addresses of the other memory devices to the set of memory devices.

6. The method of claim 5, wherein the reorganizing the previous portion of the logical address sub-space to the new logical-to-physical storage mapping further comprises:

adjusting allocation of remaining DSN addresses of the second portion of the logical address sub-space among at least some remaining memory devices of the plurality of memory devices of the first storage unit.

7. The method of claim 1 further comprises:

transferring, by at least one storage unit of the group of storage units, encoded data slices to another storage unit of the group of storage units in accordance with the reorganized logical address sub-space.

8. The method of claim 7, wherein the transferring encoded data slices from the at least one storage unit to the other storage units comprises at least one of:

transferring, by a first other storage unit of the at least one storage unit, at least one of the encoded data slices to the first storage unit in accordance with the reorganized logical address sub-space; and

transferring, by a second other storage unit of the at least one storage unit, at least another one of the encoded data slices to the second storage unit in accordance with the reorganized logical address sub-space.

9. A computer readable memory device comprises:

a first memory section that stores operational instructions that, when executed by a managing unit of a dispersed storage network (DSN), causes the managing unit to;

determine an addition of a new storage unit to a group of storage units, wherein the DSN includes a logical address space that is divided into a set of logical address sub-spaces, wherein the group of storage units is allocation a logical address sub-space of the set of logical address sub-spaces, and the new storage unit and each storage unit in the group of storage units includes a plurality of memory devices; and

reorganize distribution of the logical address sub-space among the new storage unit and each storage unit in the group of storage units to produce a reorganized logical address sub-space, wherein allocation of a first portion of the logical address sub-space is allocated to the new storage unit, wherein the first portion of the logical address sub-space is between second and third portions of the logical address sub-space, wherein the second portion of the logical address sub-space is allocated to a first storage unit of the group of storage units and the third portion of the logical address sub-space is allocated to a second storage units of the group of storage units;

a second memory section that stores operational instructions that, when executed by the first storage unit, causes the first storage unit to;

transfer a first group of encoded data slices to the new storage unit in accordance with the reorganized logical address sub-space; and

a third memory section that stores operational instructions that, when executed by the second storage unit, causes the second storage unit to;

transfer a second group of encoded data slices to the new storage unit in accordance with the reorganized logical address sub-space;

a fourth memory section that stores operational instructions that, when executed by the managing unit, causes the managing unit to;

determine an addition of a second new storage unit to a second group of storage units, wherein the second group of storage units is allocated a second logical address sub-space of the set of logical address sub-spaces; and

reorganize distribution of the second logical address sub-space among the second new storage unit and each storage unit in the second group of storage units to produce a reorganized second logical address sub-space, wherein allocation of a first portion of the second logical address sub-space is allocated to the second new storage unit, wherein the first portion of the second logical address sub-space is between second and third portions of the second logical address sub-space, wherein the second portion of the second logical address sub-space is allocated to a third storage unit of the second group of storage units and the third portion of the second logical address sub-space is allocated to a fourth storage unit of the second group of storage units;

a fourth memory section that stores operational instructions that, when executed by the third storage unit, causes the third storage unit to;

transfer a third group of encoded data slices to the second new storage unit in accordance with the reorganized second logical address sub-space; and

a fifth memory section that stores operational instructions that, when executed by the fourth storage unit, causes the fourth storage unit to;

transfer a fourth group of encoded data slices to the second new storage unit in accordance with the reorganized second logical address sub-space.

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

a fourth memory section that stores operational instructions that, when executed by the new storage unit, causes the new storage unit to;

allocate the first portion of the logical address sub-space among the plurality of memory devices of the new storage unit to produce a first logical-to-physical storage mapping; and

as encoded data slices are received, store the encoded data slices in the plurality of memory devices of the new storage unit in accordance with the first logical-to-physical storage mapping.

11. The computer readable memory device of claim 9, wherein the second memory section further stores operational instructions that, when executed by the first storage unit, causes the first storage unit to transfer the first group of encoded data slices by:

determining logical DSN addresses of a previous portion of the logical address sub-space that was allocated to the first storage unit that are being reallocated to the new storage unit based on a difference between the second portion of the logical address sub-space and the previous portion of the logical address sub-space; and

identifying the first group of encoded data slices as encoded data slices having slice names that correspond to the logical DSN addresses that are being reallocated.

12. The computer readable memory device of claim 11, wherein the second memory section further stores operational instructions that, when executed by the first storage unit, causes the first storage unit to identify the first group of encoded data slices by:

access a previous logical-to-physical storage mapping of the previous portion of the logical address sub-space to the plurality of memory devices of the first storage unit, wherein, in accordance with the previous logical-to-physical storage mapping, the first group of encoded data slices is stored in a set of memory devices of the plurality of memory devices, wherein the set of memory devices includes one or more memory devices, but less than all of the memory devices, of the plurality of memory devices of the first storage unit.

13. The computer readable memory device of claim 9, wherein the second memory section further stores operational instructions that, when executed by the first storage unit, causes the first storage unit to:

identify a set of memory devices of the plurality of memory devices of the first storage unit that is allocated DSN addresses of a previous portion of the logical address sub-space that are now part of the first portion of the logical address sub-spaces, wherein;

the previous portion of the logical address sub-space was allocated among the plurality of memory devices,

a first memory device of the plurality of memory devices was allocated a first part of the previous portion of the logical address sub-space,

a last memory device of the plurality of memory devices was allocated a last part of the previous portion of the logical address sub-space,

the set of memory devices includes one or more memory devices, but less than all of the memory devices, of the plurality of memory devices of the first storage unit, and

the set of memory devices includes either the first or the last memory device;

reorganize the previous portion of the logical address sub-space to a new logical-to-physical storage mapping based on the second portion of the logical address sub-space by;

logically repositioning the set of memory devices between other memory devices of the plurality of memory devices of the first storage unit; and

transferring allocation of some DSN addresses of the other memory devices to the set of memory devices.

14. The computer readable memory device of claim 13, wherein the second memory section further stores operational instructions that, when executed by the first storage unit, causes the first storage unit to reorganize the previous portion of the logical address sub-space to the new logical-to-physical storage mapping further by:

adjusting allocation of remaining DSN addresses of the second portion of the logical address sub-space among at least some remaining memory devices of the plurality of memory devices of the first storage unit.

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

a fourth memory section that stores operational instructions that, when executed by at least one storage unit of the group of storage units, causes the at least one storage unit of the group of storage units to;

transfer encoded data slices to another storage unit of the group of storage units in accordance with the reorganized logical address sub-space.

16. The computer readable memory device of claim 15, wherein the further memory section further stores operational instructions that causes transferring of the encoded data slices from the at least one storage unit to the other storage units by at least one of:

transferring, by a first other storage unit of the at least one storage unit, at least one of the encoded data slices to the first storage unit in accordance with the reorganized logical address sub-space; and

transferring, by a second other storage unit of the at least one storage unit, at least another one of the encoded data slices to the second storage unit in accordance with the reorganized logical address sub-space.