Expansion of dispersed storage network (DSN) memory

• US 9,959,169 B2
• Filed: 09/30/2016
• Issued: 05/01/2018
• Est. Priority Date: 10/30/2015
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Wozniak, Ethan S.
• Primary Examiner(s): Chase, Shelly A
• Application Number:
  US15/282,999
• Publication Number:
  US 20170123922A1
• Time in Patent Office: 578 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/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 11/1096 Parity calculation or recalculation after configuration or reconfiguration of the system
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 12/0646 Configuration or reconfiguration
• CPC Class Codes: G06F 2201/805 Real-time
• CPC Class Codes: G06F 2201/82 Solving problems relating to consistency
• CPC Class Codes: G06F 2212/1008 Correctness of operation, e.g. memory ordering
• CPC Class Codes: G06F 2212/657 Virtual address space management
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0622 in relation to access
• CPC Class Codes: G06F 3/0623 in relation to content
• 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/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 9/4856 resumption being on a different machine, e.g. task migration, virtual machine migration G06F9/5088 takes precedence
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• 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
• CPC Class Codes: H04L 41/0816 : the condition being an adaptation, e.g. in response to network events
• CPC Class Codes: H04L 47/803 : Application aware
• CPC Class Codes: H04L 63/0428 : wherein the data content is protected, e.g. by encrypting or encapsulating the payload
• CPC Class Codes: H04L 63/0457 : wherein the sending and receiving network entities apply dynamic encryption, e.g. stream encryption cryptographic mechanisms or cryptographic arrangements for stream encryption H04L9/065
• CPC Class Codes: H04L 63/06 : for supporting key management in a packet data network cryptographic mechanisms or cryptographic arrangements for key management H04L9/08
• CPC Class Codes: H04L 63/068 : using time-dependent keys, e.g. periodically changing keys cryptographic mechanisms or cryptographic arrangements for controlling usage of secret information H04L9/088
• 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/101 : Access control lists [ACL]
• 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 9/0861 : Generation of secret information including derivation or calculation of cryptographic keys or passwords
• CPC Class Codes: H04L 9/14 : using a plurality of keys or algorithms

Abstract

A computing device includes an interface configured to interface and communicate with a dispersed storage network (DSN), a memory that stores operational instructions, and a processing module operably coupled to the interface and memory such that the processing module, when operable within the computing device based on the operational instructions, is configured to perform various operations. A computing device identifies data slices (EDSs) of pillar width (associated with data object) to be stored within a pillar width number of a plurality of storage units (SUs). The computing device the identifies head SUs among the pillar width number of the SUs such that, based on a ring arrangement, each set of EDSs is distributedly stored among the ring arrangement of the pillar width number of the SUs starting with its respective head EDS at a respective head SU and ending with a last tail EDS at a respective last tail SU.

Claims

1. A computing device comprising:

an interface configured to interface and communicate with a dispersed storage network (DSN);

memory that stores operational instructions; and

a processing module operably coupled to the interface and to the memory, wherein the processing module, when operable within the computing device based on the operational instructions, is configured to;

identify a plurality of encoded data slices (EDSs) of pillar width and associated with a data object to be stored within a plurality of storage units (SUs), wherein the data object is segmented into a plurality of data segments, and wherein a data segment of the plurality of data segments is dispersed error encoded in accordance with dispersed error encoding parameters to produce a set of EDSs that includes a head EDS followed by tail EDSs; and

identify a plurality of head SUs among the plurality of SUs such that, based on a ring arrangement of the plurality of SUs, each set of EDSs being distributedly stored among the ring arrangement of the plurality of SUs starting with its respective head EDS at a respective head SU and ending with a last tail EDS at a respective last tail SU, wherein the plurality of head SUs are staggered among the ring arrangement of the plurality of SUs.

2. The computing device of claim 1, wherein the processing module, when operable within the computing device based on the operational instructions, is further configured to:

identify the plurality of head SUs based on a first system configuration of a Decentralized, or Distributed, Agreement Protocol (DAP) for the plurality of SUs;

generate, based on addition of a SU to the plurality of SUs to generate another plurality of SUs, a second system configuration of the DAP for the another plurality of SUs;

identify, based on difference between the first system configuration of the DAP for the plurality of SUs to the second system configuration of the DAP for the another plurality of SUs, a number of head EDSs and a number of tail EDSs to transfer from head SUs and tail SUs to the SU added to the plurality of SUs to generate the another plurality of SUs; and

transfer the number of head EDSs and the number of tail EDSs to the SU added to the plurality of SUs to generate the another plurality of SUs.

3. The computing device of claim 1, wherein:

a first head EDS of a first set of EDSs is stored in a first head SU of the plurality of SUs followed by first tail EDSs of the first set of EDSs and ending with a last tail EDS of the first tail EDSs stored in a first last tail SU of the plurality of SUs; and

a second head EDS of a second set of EDSs is stored in a second head SU of the plurality of SUs followed by second tail EDSs of the second set of EDSs and ending with a last tail EDS of the second tail EDSs stored in a second last tail SU of the plurality of SUs, wherein the second head SU is staggered from the first head SU among the ring arrangement of the plurality of SUs.

4. The computing device of claim 3, wherein:

a third head EDS of a third set of EDSs is stored in a third head SU of the plurality of SUs followed by third tail EDSs of the third set of EDSs and ending with a last tail EDS of the third tail EDSs stored in a third last tail SU of the plurality of SUs, wherein the third head SU is staggered from the second head SU among the ring arrangement of the plurality of SUs by as same amount that the second head SU is staggered from the first head SU among the ring arrangement of the plurality of SUs.

5. The computing device of claim 3, wherein:

a third head EDS of a third set of EDSs is stored in a third head SU of the plurality of SUs followed by third tail EDSs of the third set of EDSs and ending with a last tail EDS of the third tail EDSs stored in a third last tail SU of the plurality of SUs, wherein the third head SU is staggered from the second head SU among the ring arrangement of the plurality of SUs by as different amount that the second head SU is staggered from the first head SU among the ring arrangement of the plurality of SUs.

6. The computing device of claim 1, wherein the computing device is located at a first premises that is remotely located from at least one SU of the plurality of SUs within the DSN.

7. The computing device of claim 1 further comprising:

a SU of the plurality of SUs within the DSN, a wireless smart phone, a laptop, a tablet, a personal computers (PC), a work station, or a video game device.

8. The computing device of claim 1, wherein the DSN includes at least one of a wireless communication system, a wire lined communication systems, a non-public intranet system, a public internet system, a local area network (LAN), or a wide area network (WAN).

9. A computing device comprising:

an interface configured to interface and communicate with a dispersed storage network (DSN);

memory that stores operational instructions; and

a processing module operably coupled to the interface and to the memory, wherein the processing module, when operable within the computing device based on the operational instructions, is configured to;

identify a plurality of encoded data slices (EDSs) of pillar width and associated with a data object to be stored within a plurality of storage units (SUs), wherein the data object is segmented into a plurality of data segments, and wherein a data segment of the plurality of data segments is dispersed error encoded in accordance with dispersed error encoding parameters to produce a set of EDSs that includes a head EDS and a tail EDS;

identify, based on a first system configuration of a Decentralized, or Distributed, Agreement Protocol (DAP) for the plurality of SUs, a plurality of head SUs among the plurality of SUs such that, based on a ring arrangement of the plurality of SUs, each set of EDSs is distributedly stored among the ring arrangement of the plurality of SUs starting with its respective head EDS at a respective head SU and ending with its respective tail EDS at a respective tail SU, wherein the plurality of head SUs are staggered among the ring arrangement of the plurality of SUs;

generate, based on addition of a SU to the plurality of SUs to generate another plurality of SUs, a second system configuration of the DAP for the another plurality of SUs;

identify, based on difference between the first system configuration of the DAP for the plurality of SUs to the second system configuration of the DAP for the another plurality of SUs, a number of head EDSs and a number of tail EDSs to transfer from head SUs and tail SUs to the SU added to the plurality of SUs to generate the another plurality of SUs; and

transfer the number of head EDSs and the number of tail EDSs to the SU added to the plurality of SUs to generate the another plurality of SUs to balance substantially storage of the plurality of EDSs among the another plurality of SUs.

10. The computing device of claim 9, wherein the processing module, when operable within the computing device based on the operational instructions, is further configured to:

a first head EDS of a first set of EDSs is stored in a first head SU of the plurality of SUs followed by first tail EDSs of the first set of EDSs and ending with a last tail EDS of the first tail EDSs stored in a first last tail SU of the plurality of SUs; and

a second head EDS of a second set of EDSs is stored in a second head SU of the plurality of SUs followed by second tail EDSs of the second set of EDSs and ending with a last tail EDS of the second tail EDSs stored in a second last tail SU of the plurality of SUs, wherein the second head SU is staggered from the first head SU among the ring arrangement of the plurality of SUs.

11. The computing device of claim 10, wherein:

a third head EDS of a third set of EDSs is stored in a third head SU of the plurality of SUs followed by third tail EDSs of the third set of EDSs and ending with a last tail EDS of the third tail EDSs stored in a third last tail SU of the plurality of SUs, wherein the third head SU is staggered from the second head SU among the ring arrangement of the plurality of SUs by as same amount that the second head SU is staggered from the first head SU among the ring arrangement of the plurality of SUs.

12. The computing device of claim 9 further comprising:

a SU of the plurality of SUs within the DSN, a wireless smart phone, a laptop, a tablet, a personal computers (PC), a work station, or a video game device.

13. The computing device of claim 9, wherein the DSN includes at least one of a wireless communication system, a wire lined communication systems, a non-public intranet system, a public internet system, a local area network (LAN), or a wide area network (WAN).

14. A method for execution by a computing device, the method comprising:

identifying a plurality of encoded data slices (EDSs) of pillar width and associated with a data object to be stored within a plurality of storage units (SUs) of a dispersed storage network (DSN), wherein the data object is segmented into a plurality of data segments, and wherein a data segment of the plurality of data segments is dispersed error encoded in accordance with dispersed error encoding parameters to produce a set of EDSs that includes a head EDS followed by tail EDSs; and

identifying a plurality of head SUs among the plurality of SUs such that, based on a ring arrangement of the plurality of SUs, each set of EDSs being distributedly stored among the ring arrangement of the plurality of SUs starting with its respective head EDS at a respective head SU and ending with a last tail EDS at a respective last tail SU, wherein the plurality of head SUs are staggered among the ring arrangement of the plurality of SUs.

15. The method of claim 14 further comprising:

identifying the plurality of head SUs based on a first system configuration of a Decentralized, or Distributed, Agreement Protocol (DAP) for the plurality of SUs;

generating, based on addition of a SU to the plurality of SUs that generates another plurality of SUs, a second system configuration of the DAP for the another plurality of SUs;

identifying, based on difference between the first system configuration of the DAP for the plurality of SUs to the second system configuration of the DAP for the another plurality of SUs, a number of head EDSs and a number of tail EDSs to transfer from head SUs and tail SUs to the SU added to the plurality of SUs to generate the another plurality of SUs; and

transferring the number of head EDSs and the number of tail EDSs to the SU added to the plurality of SUs to generate the another plurality of SUs.

16. The method of claim 14, wherein:

a first head EDS of a first set of EDSs is stored in a first head SU of the plurality of SUs followed by first tail EDSs of the first set of EDSs and ending with a last tail EDS of the first tail EDSs stored in a first last tail SU of the plurality of SUs; and

a second head EDS of a second set of EDSs is stored in a second head SU of the plurality of SUs followed by second tail EDSs of the second set of EDSs and ending with a last tail EDS of the second tail EDSs stored in a second last tail SU of the plurality of SUs, wherein the second head SU is staggered from the first head SU among the ring arrangement of the plurality of SUs.

17. The method of claim 16, wherein:

a third head EDS of a third set of EDSs is stored in a third head SU of the plurality of SUs followed by third tail EDSs of the third set of EDSs and ending with a last tail EDS of the third tail EDSs stored in a third last tail SU of the plurality of SUs, wherein the third head SU is staggered from the second head SU among the ring arrangement of the plurality of SUs by as same amount that the second head SU is staggered from the first head SU among the ring arrangement of the plurality of SUs.

18. The method of claim 16, wherein:

a third head EDS of a third set of EDSs is stored in a third head SU of the plurality of SUs followed by third tail EDSs of the third set of EDSs and ending with a last tail EDS of the third tail EDSs stored in a third last tail SU of the plurality of SUs, wherein the third head SU is staggered from the second head SU among the ring arrangement of the plurality of SUs by as different amount that the second head SU is staggered from the first head SU among the ring arrangement of the plurality of SUs.

19. The method of claim 14, wherein the computing device is a SU of the plurality of SUs within the DSN, a wireless smart phone, a laptop, a tablet, a personal computers (PC), a work station, or a video game device.

20. The method of claim 14, wherein the DSN includes at least one of a wireless communication system, a wire lined communication systems, a non-public intranet system, a public internet system, a local area network (LAN), or a wide area network (WAN).