Protocols for expanding existing sites in a dispersed storage network

• US 10,169,229 B2
• Filed: 11/09/2016
• Issued: 01/01/2019
• Est. Priority Date: 06/05/2012
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Baptist, Andrew D., Dhuse, Greg R., Motwani, Manish, Volvovski, Ilya
• Primary Examiner(s): Dudek, Jr., Edward J
• Assistant Examiner(s): RUSSELL, ANDREW D
• Application Number:
  US15/347,132
• Publication Number:
  US 20170060739A1
• Time in Patent Office: 783 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 11/1658 Data re-synchronization of a redundant component, or initial sync of replacement, additional or spare unit
• CPC Class Codes: G06F 11/1662 the resynchronized component or unit being a persistent storage device re-synchronization of failed mirror storage G06F11/2082; rebuild or reconstruction of parity RAID storage G06F11/1008
• CPC Class Codes: G06F 11/3034 where the computing system component is a storage system, e.g. DASD based or network based digital input from or digital output to record carriers G06F3/06; digital recording or reproducing G11B20/18; 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], H04L67/1097
• CPC Class Codes: G06F 11/3055 Monitoring arrangements for monitoring the status of the computing system or of the computing system component, e.g. monitoring if the computing system is on, off, available, not available error or fault processing without redundancy G06F11/0703; error detection or correction by redundancy in data representation G06F11/08; error detection or correction by redundancy in operation G06F11/14; error detection or correction by redundancy in hardware G06F11/16
• CPC Class Codes: G06F 12/0284 Multiple user address space allocation, e.g. using different base addresses interprocessor communication G06F15/163
• CPC Class Codes: G06F 2212/154 Networked environment
• CPC Class Codes: H03M 13/00 Coding, decoding or code conversion, for error detection or error correction; Coding theory basic assumptions; Coding bounds; Error probability evaluation methods; Channel models; Simulation or testing of codes error detection or error correction for analogue/digital, digital/analogue or code conversion H03M1/00 – H03M11/00; specially adapted for digital computers G06F11/08; for information storage based on relative movement between record carrier and transducer G11B, e.g. G11B20/18; for static stores G11C
• CPC Class Codes: H03M 13/3761 using code combining, i.e. using combining of codeword portions which may have been transmitted separately, e.g. Digital Fountain codes, Raptor codes or Luby Transform [LT] codes

Abstract

A dispersed storage and task network (DSTN) includes a site housing current distributed storage and task (DST) execution units. A determination is made to add new DST execution units to the site. A first address range assigned to the plurality of current DST execution units is obtained, and a common magnitude of second address ranges to be assigned to each of the new DST execution units and the current DST execution units is determined based, at least in part, on the first address range. Insertion points for each of the plurality of new DST execution units are determined, and transfer address ranges are determined in accordance with the insertion points. Transfer address ranges correspond to at least the part of the first address ranges to be transferred to the new DST execution units. Address range assignments are transferred from particular current DST execution units to particular new DST execution units.

Claims

1. A method for execution by computing device within a dispersed storage and task network (DSTN) including at least one site housing a plurality of current distributed storage and task (DST) execution units, the method comprising:

determining that a plurality of new DST execution units are to be added to the at least one site;

in response to determining that the plurality of new DST execution units are to be added to the at least one site, assigning the new DST execution units to positions within the at least one site to limit a number of DST execution units through which data must be moved during migration of data to the new DST execution units to a maximum number, the maximum number being less than the number of current DST execution units included in the at least one site, wherein assigning the new DST execution units to positions within the at least one site includes;

obtaining first address ranges assigned to the plurality of current DST execution units;

determining a common magnitude of second address ranges to be assigned to the plurality of new DST execution units and the plurality of current DST execution units;

determining insertion points for each of the plurality of new DST execution units, wherein the insertion points are selected to intersperse the plurality of new DST execution units among the current DST execution units in a pattern arranged so that each current DST execution unit is no more than a predetermined number of current DST execution units distant from one of the plurality of new DST execution units;

determining transfer address ranges, where transfer address ranges correspond to at least a portion of the first address ranges to be transferred to the plurality of new DST execution units in accordance with the insertion points; and

facilitating transfer of address range assignments from particular current DST execution units to particular new DST execution units.

2. The method of claim 1, further comprising:

facilitating transfer of encoded slices having addresses in the transfer address ranges from the plurality of current DST execution units to the plurality of new DST execution units.

3. The method of claim 1, further comprising:

determining that a plurality of new DST execution units are to be added to the at least one site based on a storage capacity utilization level associated with the plurality of current DST execution units.

4. The method of claim 1, further comprising:

determining the common magnitude of second address ranges by evenly dividing a total number of addresses included in the first address ranges assigned to the plurality of current DST execution units among a combined total number of current and new DST execution units.

5. The method of claim 1, wherein determining the insertion points for each of the plurality of new DST execution units includes:

interspersing the plurality of new DST execution units between current DST execution units.

6. The method of claim 1, further comprising:

determining the transfer address ranges so that each of the plurality of new and current DST execution units includes;

a number of addresses corresponding to the common magnitude; and

a contiguous address range with regards to an adjacent pair of DST execution units.

7. The method of claim 1, further comprising:

facilitating transfer of address range assignments by updating address range tables in at least one of each DST execution unit and at a system level.

8. A dispersed storage and task network (DSTN) managing unit comprising:

a processor and associated memory configured to;

determine that a plurality of new distributed storage and task (DST) execution units are to be added to a site including a plurality of current DST execution units;

in response to determining that the plurality of new DST execution units are to be added to the at least one site, assign the new DST execution units to positions within the at least one site to limit a number of DST execution units through which data must be moved during migration of data to the new DST execution units to a maximum number, the maximum number being less than the number of current DST execution units included in the at least one site, wherein the processor and memory are configured to assign the new DST execution units to positions within the at least one site by;

obtaining first address ranges assigned to the plurality of current DST execution units;

determining a common magnitude of second address ranges to be assigned to the plurality of new DST execution units and the plurality of current DST execution units;

determining points for each of the plurality of new DST execution units, wherein the insertion points are selected to intersperse the plurality of new DST execution units among the current DST execution units in a pattern arranged so that each current DST execution unit is no more than a predetermined number of current DST execution units distant from one of the plurality of new DST execution units;

determining transfer address ranges corresponding to at least a portion of the first address ranges to be transferred to the plurality of new DST execution units, the transfer address ranges determined in accordance with the insertion points; and

facilitate transfer of address range assignments from particular current DST execution units to particular new DST execution units.

9. The DSTN managing unit of claim 8, the processor and associated memory further configured to:

facilitate transfer of encoded slices having addresses in the transfer address ranges from the current DST execution units to the new DST execution units.

10. The DSTN managing unit of claim 8, the processor and associated memory further configured to:

determine that a plurality of new DST execution units are to be added to the site based on a storage capacity utilization level associated with the plurality of current DST execution units.

11. The DSTN managing unit of claim 8, the processor and associated memory further configured to:

determine the common magnitude of second address ranges by evenly dividing a total number of addresses included in the first address ranges assigned to the plurality of current DST execution units among a combined total number of current and new DST execution units.

12. The DSTN managing unit of claim 8, the processor and associated memory further configured to:

intersperse, both within a namespace and physically, the plurality of new DST execution units between current DST execution units.

13. The DSTN managing unit of claim 8, the processor and associated memory further configured to:

determine the transfer address ranges so that each of the plurality of new and current DST execution units includes;

a number of addresses corresponding to the common magnitude; and

a contiguous address range with regards to an adjacent pair of DST execution units.

14. The DSTN managing unit of claim 8, the processor and associated memory further configured to:

facilitate transfer of address range assignments by updating address range tables in at least one of each DST execution unit and at a system level.

15. A dispersed storage and task network (DSTN) comprising:

a plurality of physical sites, each of the plurality of physical sites including a plurality of current distributed storage and task (DST) execution units arranged in a logical and physical order;

a DSTN managing unit including a processor and associated memory configured to;

determine that a plurality of new distributed storage and task (DST) execution units are to be added to at least one of the plurality of physical sites;

in response to determining that the plurality of new DST execution units are to be added to the at least one site, assign the new DST execution units to positions within the at least one site to limit a number of DST execution units through which data must be moved during migration of data to the new DST execution units to a maximum number, the maximum number being less than the number of current DST execution units included in the at least one site, wherein the DSTN managing unit is further configured to assign the new DST execution units to positions within the at least one site by;

obtaining first address ranges assigned to the plurality of current DST execution units;

determining a common magnitude of second address ranges to be assigned to the plurality of new DST execution units and the plurality of current DST execution units;

determining at least logical insertion points for each of the plurality of new DST execution units, wherein the logical insertion points are selected to intersperse the plurality of new DST execution units among the current DST execution units in a pattern arranged so that each current DST execution unit is no more than a predetermined number of current DST execution units distant from one of the plurality of new DST execution units;

determining transfer address ranges corresponding to at least a portion of the first address ranges to be transferred to the plurality of new DST execution units, the transfer address ranges determined in accordance with the at least logical insertion points; and

facilitate transfer of address range assignments from particular current DST execution units to particular new DST execution units.

16. The DSTN of claim 15, the processor and associated memory further configured to:

determine that a plurality of new DST execution units are to be added to the at least one of the plurality of physical sites based on a storage capacity utilization level associated with the plurality of current DST execution units.

17. The DSTN of claim 15, the DSTN managing unit further configured to:

determine the common magnitude of second address ranges by evenly dividing a total number of addresses included in the first address ranges assigned to the plurality of current DST execution units among a combined total number of current and new DST execution units.

18. The DSTN of claim 15, the DSTN managing unit further configured to:

determine physical insertion points for each of the plurality of new DST execution units.

19. The DSTN of claim 15, the DSTN managing unit further configured to:

determine the transfer address ranges so that each of the plurality of new and current DST execution units includes;

a number of addresses corresponding to the common magnitude; and

a contiguous address range with regards to an adjacent pair of DST execution units.

20. The DSTN of claim 15, the DSTN managing unit further configured to:

facilitate transfer of encoded slices having addresses in the transfer address ranges from the plurality of current DST execution units to the plurality of new DST execution units by updating address range tables in at least one of each DST execution unit and at a system level.