Verifying encoded data slice integrity in a dispersed storage network

• US 9,141,297 B2
• Filed: 05/09/2013
• Issued: 09/22/2015
• Est. Priority Date: 06/25/2012
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Resch, Jason K.
• Primary Examiner(s): Kerveros, James C
• Application Number:
  US13/890,510
• Publication Number:
  US 20130346716A1
• Time in Patent Office: 866 Days
• Field of Search: 714/763
• US Class Current: 1/1
• CPC Class Codes: G06F 11/008 Reliability or availability analysis
• CPC Class Codes: G06F 11/08 Error detection or correction by redundancy in data representation, e.g. by using checking codes
• CPC Class Codes: G06F 11/10 Adding special bits or symbols to the coded information, e.g. parity check, casting out 9's or 11's
• CPC Class Codes: G06F 11/1068 in sector programmable memories, e.g. flash disk G06F11/1072 takes precedence
• 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 2211/109 Sector level checksum or ECC, i.e. sector or stripe level checksum or ECC in addition to the RAID parity calculation
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/065 Replication mechanisms
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• 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/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
• 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: H03M 13/611 Specific encoding aspects, e.g. encoding by means of decoding

Abstract

A method begins by a dispersed storage (DS) processing module of a storage device receiving an encoded data slice of a set of encoded data slices, where the set of encoded data slices has associated therewith a set of integrity values, and where integrity information is generated from the set of integrity values. The method continues with the DS processing module generating an integrity value for the encoded data slice and obtaining at least a portion of the integrity information from another storage device. The method continues with the DS processing module generating a comparative integrity value for the encoded data slice based on the at least a portion of the integrity information and facilitating storage of the encoded data slice in memory of the storage device when the integrity value compares favorably to the comparative integrity value.

Claims

1. A method for execution by a processing module of a storage device, the method comprises:

receiving, from a requesting entity, an encoded data slice of a set of encoded data slices, wherein a data segment is encoded using a dispersed storage error coding function to produce the set of encoded data slices, in which only a threshold number of the set of encoded data slices are needed to reconstruct the data segment, the threshold number being less than all of the set of encoded data slices, wherein a respective encoded data slice of the set of encoded data slices has associated therewith a respective integrity value, in which integrity information is generated from integrity values corresponding to encoded data slices of the set of encoded data slices, and wherein the set of encoded data slices are separated into individual encoded data slices and distributed to a plurality of devices along with the integrity information;

generating, by the processing module, an integrity value for the encoded data slice received from the requesting entity;

obtaining, by the processing module, at least a portion of the integrity information from another storage device that did not provide the received encoded data slice;

generating, by the processing module, a comparative integrity value for the encoded data slice based on the at least a portion of the integrity information obtained from the other storage device; and

facilitating, by the processing module, storage of the encoded data slice in memory of the storage device when the integrity value is same as the comparative integrity value.

2. The method of claim 1 further comprises:

receiving the encoded data slice as part of a rebuilding process, wherein the encoded data slice is a rebuilt encoded data slice corresponding to one of a corrupt encoded data slice of the set of encoded data slices.

3. The method of claim 1 further comprises:

obtaining, via a request, a retrieved integrity value of the encoded data slice from the other storage device, wherein the other storage device produced the retrieved integrity value from the integrity information; and

generating the comparative integrity value by equating the comparative integrity value to the retrieved integrity value.

4. The method of claim 1 further comprises:

obtaining, via a request, the integrity information from the other storage device;

producing a retrieved integrity value from the integrity information; and

generating the comparative integrity value by equating the comparative integrity value to the retrieved integrity value.

5. The method of claim 1 further comprises:

obtaining, by the processing module, a second at least a portion of the integrity information from a second other storage device; and

generating, by the processing module, the comparative integrity value for the encoded data slice based on the at least a portion of the integrity information and the second at least a portion of the integrity information.

6. The method of claim 1 further comprises:

generating an error message when the integrity value is not the same as the comparative integrity value.

7. A method for execution by a processing module of a storage device, the method comprises:

receiving, from a requesting entity, integrity information and an encoded data slice of a set of encoded data slices, wherein a data segment is encoded using a dispersed storage error coding function to produce the set of encoded data slices, in which only a threshold number of the set of encoded data slices are needed to reconstruct the data segment, the threshold number being less than all of the set of encoded data slices, wherein a respective encoded data slice of the set of encoded data slices has associated therewith a respective integrity value, in which the integrity information is generated from integrity values corresponding to encoded data slices of the set of encoded data slices, and wherein the set of encoded data slices are separated into individual encoded data slices and distributed to a plurality of devices along with the integrity information;

obtaining, by the processing module, at least a portion of a copy of the integrity information from another storage device that did not provide the received encoded data slice;

comparing, by the processing module, the at least a portion of the copy of the integrity information with a corresponding at least a portion of the received integrity information to determine if the integrity value from two different locations for the received encoded data slice are same; and

facilitating, by the processing module, storage of the encoded data slice in memory of the storage device when the comparison is the same.

8. The method of claim 7 further comprises:

generating, by the processing module, an integrity value for the encoded data slice;

obtaining, via a request, a retrieved integrity value of the encoded data slice from the other storage device, wherein the other storage device produced the retrieved integrity value from the copy of the integrity information; and

comparing the integrity value as the corresponding at least a portion of the received integrity information with the retrieved integrity value as the at least a portion of the copy of the integrity information.

9. The method of claim 7 further comprises:

obtaining, by the processing module, the copy of the integrity information from the other storage device; and

comparing, by the processing module, the copy of the integrity information with the received integrity information.

10. The method of claim 7 further comprises:

receiving the encoded data slice as part of a rebuilding process, wherein the encoded data slice is a rebuilt encoded data slice corresponding to one of a corrupt encoded data slice of the set of encoded data slices.

11. A dispersed storage (DS) module of a storage device, the DS module comprises:

a first module, when operable within a computing device, causes the computing device to;

receive, from a requesting entity, an encoded data slice of a set of encoded data slices, wherein a data segment is encoded using a dispersed storage error coding function to produce the set of encoded data slices, in which only a threshold number of the set of encoded data slices are needed to reconstruct the data segment, the threshold number being less than all of the set of encoded data slices, wherein a respective encoded data slice of the set of encoded data slices has associated therewith a respective integrity value, in which integrity information is generated from integrity values corresponding to encoded data slices of the set of encoded data slices, and wherein the set of encoded data slices are separated into individual encoded data slices and distributed to a plurality of devices along with the integrity information; and

generate an integrity value for the encoded data slice received from the requesting entity;

a second module, when operable within the computing device, causes the computing device to;

obtain at least a portion of the integrity information from another storage device that did not provide the received encoded data slice; and

generate a comparative integrity value for the encoded data slice based on the at least a portion of the integrity information obtained from the other storage device; and

a third module, when operable within the computing device, causes the computing device to;

facilitate storage of the encoded data slice in memory of the storage device when the integrity value is same as the comparative integrity value.

12. The DS module of claim 11 further comprises:

the first module further functions to receive the encoded data slice as part of a rebuilding process, wherein the encoded data slice is a rebuilt encoded data slice corresponding to one of a corrupt encoded data slice of the set of encoded data slices.

13. The DS module of claim 11 further comprises:

the second module further functions to;

obtain, via a request, a retrieved integrity value of the encoded data slice from the other storage device, wherein the other storage device produced the retrieved integrity value from the integrity information; and

generate the comparative integrity value by equating the comparative integrity value to the retrieved integrity value.

14. The DS module of claim 11 further comprises:

the second module further functions to;

obtain, via a request, the integrity information from the other storage device;

produce a retrieved integrity value from the integrity information; and

generate the comparative integrity value by equating the comparative integrity value to the retrieved integrity value.

15. The DS module of claim 11 further comprises:

the second module further functions to;

obtain a second at least a portion of the integrity information from a second other storage device; and

generate the comparative integrity value for the encoded data slice based on the at least a portion of the integrity information and the second at least a portion of the integrity information.

16. The DS module of claim 11 further comprises:

the third module further functions to generate an error message when the integrity value is not the same as the comparative integrity value.

17. A dispersed storage (DS) module of a storage device, the DS module comprises:

a first module, when operable within a computing device, causes the computing device to;

receive, from a requesting entity, integrity information and an encoded data slice of a set of encoded data slices, wherein a data segment is encoded using a dispersed storage error coding function to produce the set of encoded data slices, in which only a threshold number of the set of encoded data slices are needed to reconstruct the data segment, the threshold number being less than all of the set of encoded data slices, wherein a respective encoded data slice of the set of encoded data slices has associated therewith a respective integrity value, in which the integrity information is generated from integrity values corresponding to encoded data slices of the set of encoded data slices, and wherein the set of encoded data slices are separated into individual encoded data slices and distributed to a plurality of devices along with the integrity information;

a second module, when operable within the computing device, causes the computing device to;

obtain at least a portion of a copy of the integrity information from another storage device that did not provide the received encoded data slice; and

a third module, when operable within the computing device, causes the computing device to;

compare the at least a portion of the copy of the integrity information with a corresponding at least a portion of the received integrity information to determine if the integrity value from two different locations for the received encoded data slice are same; and

facilitate storage of the encoded data slice in memory of the storage device when the comparison is the same.

18. The DS module of claim 17 further comprises:

the first module further functions to generate an integrity value for the encoded data slice;

the second module further functions to obtain, via a request, a retrieved integrity value of the encoded data slice from the other storage device, wherein the other storage device produced the retrieved integrity value from the copy of the integrity information; and

the third module further functions to compare the integrity value as the corresponding at least a portion of the received integrity information with the retrieved integrity value as the at least a portion of the copy of the integrity information.

19. The DS module of claim 17 further comprises:

the second module further functions to obtain the copy of the integrity information from the other storage device; and

the third module further functions to compare the copy of the integrity information with the received integrity information.

20. The DS module of claim 17 further comprises:

the first module further functions to receive the encoded data slice as part of a rebuilding process, wherein the encoded data slice is a rebuilt encoded data slice corresponding to one of a corrupt encoded data slice of the set of encoded data slices.