Overcoming bottlenecks in zero information gain (ZIG) rebuild operations

• US 10,402,271 B2
• Filed: 12/13/2017
• Issued: 09/03/2019
• Est. Priority Date: 12/02/2014
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Viraraghavan, Praveen, Resch, Jason K.
• Primary Examiner(s): Knapp, Justin R
• Application Number:
  US15/840,999
• Publication Number:
  US 20180101440A1
• Time in Patent Office: 629 Days
• Field of Search: None
• CPC Class Codes: G06F 11/1092 Rebuilding, e.g. when physically replacing a failing disk
• CPC Class Codes: G06F 21/602 Providing cryptographic facilities or services
• 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: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/064 Management of blocks
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G09C 1/00 Apparatus or methods whereby a given sequence of signs, e.g. an intelligible text, is transformed into an unintelligible sequence of signs by transposing the signs or groups of signs or by replacing them by others according to a predetermined system cryptographic typewriters G09C3/00
• CPC Class Codes: H04L 2209/12 Details relating to cryptographic hardware or logic circuitry
• CPC Class Codes: H04L 2209/34 Encoding or coding, e.g. Huffman coding or error correction
• CPC Class Codes: H04L 9/0841 involving Diffie-Hellman or related key agreement protocols
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage

Abstract

A storage unit (SU) includes an interface configured to interface and communicate with a dispersed storage network (DSN), a memory that stores operational instructions, and processing circuitry operably coupled to the interface and to the memory. The SU determines to rebuild an encoded data slice (EDS) of a set of EDSs based on a storage error of the EDS and selects combining units to enable rebuilding of the EDS. The SU also selects participating storage units (SUs) that store at least the decode threshold number of EDSs and facilitates establishing pairwise encryption keys between appropriate components. The SU facilitates the combining units and the SU receiving encrypted representations of the decode threshold number of EDSs of the set of EDSs. The SU combines an encrypted combined partial slice and any additional encrypted representation to generate an encrypted rebuilt EDS and decrypts the encrypted rebuilt EDS to generate a rebuilt EDS.

Claims

1. A storage unit (SU) comprising:

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

memory that stores operational instructions; and

processing circuitry operably coupled to the interface and to the memory, wherein the processing circuitry is configured to execute the operational instructions to;

determine to rebuild an encoded data slice (EDS) of a set of encoded data slices (EDSs) based on a storage error of the EDS, wherein a data object is segmented into a plurality of data segments, wherein a data segment of the plurality of data segments is dispersed error encoded in accordance with dispersed error encoding parameters to produce the set of EDSs, wherein a decode threshold number of EDSs of the set of EDSs are needed to recover the data segment;

select combining units based on a number of combining units to perform receiving of encrypted slice representations to enable rebuilding of the EDS;

select participating storage units (SUs) within the DSN that store at least the decode threshold number of EDSs of the set of EDSs;

facilitate establishing pairwise encryption keys between each of the participating SUs within the DSN and also between the SU and the each of the participating SUs;

facilitate receiving, by the combining units and by the SU, encrypted representations of the decode threshold number of EDSs of the set of EDSs;

receive, from a combining unit of the combining units, an encrypted combined partial slice that is generated by the combining unit of the combining units based on at least some of the encrypted representations of the decode threshold number of EDSs of the set of EDSs received by the combining unit of the combining units from at least some of the participating SUs within the DSN;

combine the encrypted combined partial slice and any additional encrypted representation of the decode threshold number of EDSs of the set of EDSs to generate an encrypted rebuilt EDS; and

decrypt the encrypted rebuilt EDS to generate a rebuilt EDS.

2. The SU of claim 1, wherein the processing circuitry is further configured to execute the operational instructions to:

determine the number of combining units to receive the encrypted slice representations to enable rebuilding of the EDS based on at least one of a number of available storage units (SUs) at a common site with the DSN, system configuration information of the DSN, the decode threshold number, or a performance goal of the DSN.

3. The SU of claim 1, wherein the processing circuitry is further configured to execute the operational instructions to:

select the combining units based on the number of combining units and also based on at least one of storage unit (SU) availability, local network available capacity, wide area network (WAN) available capacity, or system configuration of the DSN.

4. The SU of claim 1, wherein an encrypted representation of an EDS of the decode threshold number of EDSs of the set of EDSs includes the EDS of the set of EDSs or a corresponding encrypted partially decoded EDS based on the EDS of the set of EDSs based on the storage error of the EDS.

5. The SU of claim 1, wherein the processing circuitry is further configured to execute the operational instructions to:

issue slice representation retrieval requests to the combining units that store the decode threshold number of EDSs of the set of EDSs, where a slice representation retrieval request includes at least one of an EDS or partial slice indicator, a slice name of the EDS of the set of EDSs based on the storage error of the EDS, a slice name of the EDS of the slice representation retrieval request, a partial decoding matrix, an encoding matrix, identifiers of the decode threshold number of EDSs of the set of EDSs, or a destination identifier for an encrypted slice representation associated with the slice representation retrieval request.

6. The SU of claim 1, wherein the encrypted combined partial slice that is generated by the combining unit of the combining units is based on an exclusive OR operation performed by the combining unit of the combining units based on a first encrypted partial slice of a first encrypted slice representation and a second encrypted partial slice of a second encrypted slice representation.

7. The SU of claim 1, wherein the SU and the combining units are located at a first site that is remotely located from a second site that includes at least one SU of the participating SUs within the DSN.

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

9. A storage unit (SU) comprising:

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

memory that stores operational instructions; and

processing circuitry operably coupled to the interface and to the memory, wherein the processing circuitry is configured to execute the operational instructions to;

determine to rebuild an encoded data slice (EDS) of a set of encoded data slices (EDSs) based on a storage error of the EDS, wherein a data object is segmented into a plurality of data segments, wherein a data segment of the plurality of data segments is dispersed error encoded in accordance with dispersed error encoding parameters to produce the set of EDSs, wherein a decode threshold number of EDSs of the set of EDSs are needed to recover the data segment;

select combining units based on a number of combining units to perform receiving of encrypted slice representations to enable rebuilding of the EDS and also based on at least one of storage unit (SU) availability, local network available capacity, wide area network (WAN) available capacity, or system configuration of the DSN;

select participating storage units (SUs) within the DSN that store at least the decode threshold number of EDSs of the set of EDSs;

facilitate establishing pairwise encryption keys between each of the participating SUs within the DSN and also between the SU and the each of the participating SUs;

facilitate receiving, by the combining units and by the SU, the encrypted representations of the decode threshold number of EDSs of the set of EDSs, wherein an encrypted representation of an EDS of the decode threshold number of EDSs of the set of EDSs includes the EDS of the set of EDSs or a corresponding encrypted partially decoded EDS based on the EDS of the set of EDSs based on the storage error of the EDS;

receive, from a combining unit of the combining units, an encrypted combined partial slice that is generated by the combining unit of the combining units based on at least some of the encrypted representations of the decode threshold number of EDSs of the set of EDSs received by the combining unit of the combining units from at least some of the participating SUs within the DSN;

combine the encrypted combined partial slice and any additional encrypted representation of the decode threshold number of EDSs of the set of EDSs to generate an encrypted rebuilt EDS; and

decrypt the encrypted rebuilt EDS to generate a rebuilt EDS.

10. The SU of claim 9, wherein the processing circuitry is further configured to execute the operational instructions to:

determine the number of combining units to receive the encrypted slice representations to enable rebuilding of the EDS based on at least one of a number of available storage units (SUs) at a common site with the DSN, system configuration information of the DSN, the decode threshold number, or a performance goal of the DSN.

11. The SU of claim 9, wherein the processing circuitry is further configured to execute the operational instructions to:

issue slice representation retrieval requests to the combining units that store the decode threshold number of EDSs of the set of EDSs, where a slice representation retrieval request includes at least one of an EDS or partial slice indicator, a slice name of the EDS of the set of EDSs based on the storage error of the EDS, a slice name of the EDS of the slice representation retrieval request, a partial decoding matrix, an encoding matrix, identifiers of the decode threshold number of EDSs of the set of EDSs, or a destination identifier for an encrypted slice representation associated with the slice representation retrieval request.

12. The SU of claim 9, wherein the encrypted combined partial slice that is generated by the combining unit of the combining units is based on an exclusive OR operation performed by the combining unit of the combining units based on a first encrypted partial slice of a first encrypted slice representation and a second encrypted partial slice of a second encrypted slice representation.

13. The SU of claim 9, wherein the DSN includes at least one of a wireless communication system, a wire lined communication system, 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 storage unit (SU), the method comprising:

determining to rebuild an encoded data slice (EDS) of a set of encoded data slices (EDSs) based on a storage error of the EDS, wherein a data object is segmented into a plurality of data segments, wherein a data segment of the plurality of data segments is dispersed error encoded in accordance with dispersed error encoding parameters to produce the set of EDSs, wherein a decode threshold number of EDSs of the set of EDSs are needed to recover the data segment;

selecting combining units based on a number of combining units to perform receiving of encrypted slice representations to enable rebuilding of the EDS;

selecting participating storage units (SUs) within a dispersed or distributed storage network (DSN) that store at least the decode threshold number of EDSs of the set of EDSs;

facilitating establishing pairwise encryption keys between each of the participating SUs within the DSN and also between the SU and the each of the participating SUs;

facilitating receiving, via an interface of the SU that is configured to interface and communicate with the DSN and by the combining units and by the SU, encrypted representations of the decode threshold number of EDSs of the set of EDSs;

receiving, via the interface and from a combining unit of the combining units, an encrypted combined partial slice that is generated by the combining unit of the combining units based on at least some of the encrypted representations of the decode threshold number of EDSs of the set of EDSs received by the combining unit of the combining units from at least some of the participating SUs within the DSN;

combining the encrypted combined partial slice and any additional encrypted representation of the decode threshold number of EDSs of the set of EDSs to generate an encrypted rebuilt EDS; and

decrypting the encrypted rebuilt EDS to generate a rebuilt EDS.

15. The method of claim 14 further comprising:

determining the number of combining units to receive the encrypted slice representations to enable rebuilding of the EDS based on at least one of a number of available storage units (SUs) at a common site with the DSN, system configuration information of the DSN, the decode threshold number, or a performance goal of the DSN.

16. The method of claim 14 further comprising:

selecting the combining units based on the number of combining units and also based on at least one of storage unit (SU) availability, local network available capacity, wide area network (WAN) available capacity, or system configuration of the DSN.

17. The method of claim 14, wherein an encrypted representation of an EDS of the decode threshold number of EDSs of the set of EDSs includes the EDS of the set of EDSs or a corresponding encrypted partially decoded EDS based on the EDS of the set of EDSs based on the storage error of the EDS.

18. The method of claim 14 further comprising:

issuing slice representation retrieval requests to the combining units that store the decode threshold number of EDSs of the set of EDSs, where a slice representation retrieval request includes at least one of an EDS or partial slice indicator, a slice name of the EDS of the set of EDSs based on the storage error of the EDS, a slice name of the EDS of the slice representation retrieval request, a partial decoding matrix, an encoding matrix, identifiers of the decode threshold number of EDSs of the set of EDSs, or a destination identifier for an encrypted slice representation associated with the slice representation retrieval request.

19. The method of claim 14, wherein the encrypted combined partial slice that is generated by the combining unit of the combining units is based on an exclusive OR operation performed by the combining unit of the combining units based on a first encrypted partial slice of a first encrypted slice representation and a second encrypted partial slice of a second encrypted slice representation.

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