Threshold decoding of data based on trust levels

• US 9,311,179 B2
• Filed: 09/16/2013
• Issued: 04/12/2016
• Est. Priority Date: 10/30/2012
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Kazi, Asimuddin, Resch, Jason K.
• Primary Examiner(s): Chung, Phung M
• Application Number:
  US14/027,538
• Publication Number:
  US 20140122968A1
• Time in Patent Office: 939 Days
• Field of Search: 714/763, 711/163, 707/687
• US Class Current: 1/1
• 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/1004 to protect a block of data words, e.g. CRC or checksum G06F11/1076 takes precedence; security arrangements for protecting computers or computer systems against unauthorized activity G06F21/00
• CPC Class Codes: G06F 11/1012 using codes or arrangements adapted for a specific type of error G06F11/1048 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 12/14 Protection against unauthorised use of memory or access to memory
• CPC Class Codes: H03M 13/616 Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations

Abstract

A method begins by a set of storage units of a dispersed storage network (DSN) receiving a plurality of read requests regarding a plurality of sets of encoded data slices from a requesting device of the DSN and outputting a plurality of read responses that includes encoded data slices and corresponding trust level indicators. The method continues with the requesting device arranging the encoded data slices of the plurality of read responses into received sets of encoded data slices. The method continues with the requesting device selecting a decode threshold number of encoded data slices from each received set of encoded data slices based on the corresponding trust level indicators to produce selected sets of encoded data slices and decoding the selected sets of encoded data slices to recapture data segments of a data object.

Claims

1. A method for execution by one or more processing modules of one or more computing devices of a dispersed storage network (DSN), the method comprises:

receiving, by a set of storage units of the DSN, a plurality of read requests regarding a plurality of sets of encoded data slices from a requesting device of the DSN, wherein a data object is dispersed storage error encoded to produce the plurality of sets of encoded data slices, wherein the set of storage units stores at least some of the plurality of sets of encoded data slices, and wherein at least some encoded data slices of the plurality of sets of encoded data slices have associated therewith a trust level indicator;

outputting, by the set of storage units, a plurality of read responses, wherein a read response of the plurality of read responses includes a corresponding one or more encoded data slices of the plurality of sets of encoded data slices and, for each of the corresponding one or more encoded data slices having an associated trust level indicator, a corresponding trust level indicator;

receiving, by the requesting device, the plurality of read responses;

arranging, by the requesting device, the corresponding one or more encoded data slices of the plurality of read responses into a received plurality of sets of encoded data slices; and

on a set by set basis for the received plurality of sets of encoded data slices;

selecting, by the requesting device, a decode threshold number of encoded data slices from the set of encoded data slices based on corresponding trust level indicators of the set of encoded data slices to produce a selected set of encoded data slices; and

decoding, by the requesting device, the selected set of encoded data slices to recapture a data segment of the data object.

2. The method of claim 1 further comprises:

assigning, by the set of storage units, associated trust level indicators to encoded data slices of the at least some of the plurality of sets of encoded data slices based on identity of a source issuing one or more write requests regarding the encoded data slices and an established trust with the source.

3. The method of claim 2 further comprises:

assigning an originator trust level to an encoded data slice of the at least some of the plurality of sets of encoded data slices when the source is an originator of the data object;

assigning an editor trust level to the encoded data slice of the at least some of the plurality of sets of encoded data slices when the source is an editor of the data object;

assigning a rebuilder trust level to the encoded data slice of the at least some of the plurality of sets of encoded data slices when the source is a rebuilder of the encoded data slice; and

assigning a migrator trust level to the encoded data slice of the at least some of the plurality of sets of encoded data slices when the source has requested migration of the encoded data slice from one storage unit to another storage unit of the set of storage units.

4. The method of claim 1 further comprises:

receiving, by the set of storage units, the corresponding trust level indicators for the at least some of the plurality of sets of encoded data slices from one or more source issuing write requests regarding encoded data slices of the at least some of the plurality of sets of encoded data slices.

5. The method of claim 1, wherein the plurality of read requests comprises one of:

requests for a decode threshold number plus one encoded data slice per set of encoded data slices of the plurality of sets of encoded data slices;

requests for a read threshold number of encoded data slices per set of encoded data slices of the plurality of sets of encoded data slices; and

requests for a coded number of encoded data slices per set of encoded data slices of the plurality of sets of encoded data slices.

6. The method of claim 1, wherein the read response further comprises at least one of:

a per data segment read response that includes an encoded data slice of a set of the plurality of sets of encoded data slices and the corresponding trust level indicator; and

a batch read response that includes encoded data slices from each of the sets of the plurality of sets of encoded data slices and the corresponding trust level indicators.

7. The method of claim 1, wherein the selecting the decode threshold number of encoded data slices comprises:

determining whether the set of encoded data slices includes the decode threshold number of encoded data slices having a first trust level indicator;

when the set of encoded data slices includes the decode threshold number of encoded data slices having the first trust level indicator, utilizing the decode threshold number of encoded data slices having the first trust level indicator as the selected set of encoded data slices;

when the set of encoded data slices does not include the decode threshold number of encoded data slices having the first trust level indicator, determining whether the set of encoded data slices includes the decode threshold number of encoded data slices having the first trust level indicator or a second trust level indicator; and

when the set of encoded data slices includes the decode threshold number of encoded data slices having the first trust level indicator or the second trust level indicator, utilizing the decode threshold number of encoded data slices having the first trust level indicator or the second trust level indicator as the selected set of encoded data slices.

8. The method of claim 7 further comprises:

when the set of encoded data slices does not include the decode threshold number of encoded data slices having the trust level indicator, flagging a trust issue regarding the data segment.

9. The method of claim 1 further comprises:

generating, by a storage unit of the set of storage units, the read response as a packet having a header and a payload, wherein the header includes a field for the trust level indicator and the payload includes the corresponding one or more encoded data slices of the plurality of sets of encoded data slices.

10. A dispersed storage network (DSN) comprises:

a set of processing modules, when operable within a set of storage units of the DSN, causes the set of storage units to;

receive a plurality of read requests regarding a plurality of sets of encoded data slices from a requesting device of the DSN, wherein a data object is dispersed storage error encoded to produce the plurality of sets of encoded data slices, wherein the set of storage units stores at least some of the plurality of sets of encoded data slices, and wherein at least some encoded data slices of the plurality of sets of encoded data slices have associated therewith a trust level indicator; and

output a plurality of read responses, wherein a read response of the plurality of read responses includes a corresponding one or more encoded data slices of the plurality of sets of encoded data slices and, for each of the corresponding one or more encoded data slices having an associated trust level indicator, a corresponding trust level indicator;

an inbound dispersed storage (DS) processing module, when operable within the requesting device of the DSN, causes the requesting device to;

receive the plurality of read responses;

arrange the corresponding one or more encoded data slices of the plurality of read responses into a received plurality of sets of encoded data slices; and

on a set by set basis for the received plurality of sets of encoded data slices;

select a decode threshold number of encoded data slices from the set of encoded data slices based on corresponding trust level indicators of the set of encoded data slices to produce a selected set of encoded data slices; and

decode the selected set of encoded data slices to recapture a data segment of the data object.

11. The DSN of claim 10 further comprises:

the set of processing modules, when operable within the set of storage units of the DSN, further causes the set of storage units to;

assign associated trust level indicators to encoded data slices of the at least some of the plurality of sets of encoded data slices based on identity of a source issuing one or more write requests regarding the encoded data slices and an established trust with the source.

12. The DSN of claim 11 further comprises:

the set of processing modules, when operable within the set of storage units of the DSN, further causes the set of storage units to;

assign an originator trust level to an encoded data slice of the at least some of the plurality of sets of encoded data slices when the source is an originator of the data object;

assign an editor trust level to the encoded data slice of the at least some of the plurality of sets of encoded data slices when the source is an editor of the data object;

assign a rebuilder trust level to the encoded data slice of the at least some of the plurality of sets of encoded data slices when the source is a rebuilder of the encoded data slice; and

assign a migrator trust level to the encoded data slice of the at least some of the plurality of sets of encoded data slices when the source has requested migration of the encoded data slice from one storage unit to another storage unit of the set of storage units.

13. The DSN of claim 10 further comprises:

the set of processing modules, when operable within the set of storage units of the DSN, further causes the set of storage units to;

receive the corresponding trust level indicators for the at least some of the plurality of sets of encoded data slices from one or more source issuing write requests regarding encoded data slices of the at least some of the plurality of sets of encoded data slices.

14. The DSN of claim 10, wherein the plurality of read requests comprises one of:

requests for a decode threshold number plus one encoded data slice per set of encoded data slices of the plurality of sets of encoded data slices;

requests for a read threshold number of encoded data slices per set of encoded data slices of the plurality of sets of encoded data slices; and

requests for a coded number of encoded data slices per set of encoded data slices of the plurality of sets of encoded data slices.

15. The DSN of claim 10, wherein the read response further comprises at least one of:

a per data segment read response that includes an encoded data slice of a set of the plurality of sets of encoded data slices and the corresponding trust level indicator; and

a batch read response that includes encoded data slices from each of the sets of the plurality of sets of encoded data slices and the corresponding trust level indicators.

16. The DSN of claim 10, wherein the inbound DS processing module functions to select the decode threshold number of encoded data slices by:

determining whether the set of encoded data slices includes the decode threshold number of encoded data slices having a first trust level indicator;

when the set of encoded data slices includes the decode threshold number of encoded data slices having the first trust level indicator, utilizing the decode threshold number of encoded data slices having the first trust level indicator as the selected set of encoded data slices;

when the set of encoded data slices does not include the decode threshold number of encoded data slices having the first trust level indicator, determining whether the set of encoded data slices includes the decode threshold number of encoded data slices having the first trust level indicator or a second trust level indicator; and

when the set of encoded data slices includes the decode threshold number of encoded data slices having the first trust level indicator or the second trust level indicator, utilizing the decode threshold number of encoded data slices having the first trust level indicator or the second trust level indicator as the selected set of encoded data slices.

17. The DSN of claim 16 further comprises:

the inbound DS processing module, when operable within the requesting device of the DSN, further causes the requesting device to;

when the set of encoded data slices does not include the decode threshold number of encoded data slices having the trust level indicator, flag a trust issue regarding the data segment.

18. The DSN of claim 10 further comprises:

a processing module of the set of processing modules, when operable within a storage unit of the set of storage units of the DSN, further causes the storage unit to;

generate the read response as a packet having a header and a payload, wherein the header includes a field for the trust level indicator and the payload includes the corresponding one or more encoded data slices of the plurality of sets of encoded data slices.