Retrieving data from a dispersed storage network in accordance with a retrieval threshold

• US 8,448,044 B2
• Filed: 04/29/2011
• Issued: 05/21/2013
• Est. Priority Date: 05/19/2010
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Dhuse, Greg, Volvovski, Ilya, Baptist, Andrew, Vas, Sebastien, Mark, Zachary J.
• Primary Examiner(s): Tabone, Jr., John J
• Application Number:
  US13/097,357
• Publication Number:
  US 20110289383A1
• Time in Patent Office: 753 Days
• Field of Search: 714/763, 714/769, 714/770, 714/773, 714/6.24, 714/6.11, 714/47.2, 711/100, 711/101, 711/111, 711/114, 365/184, 365/200
• US Class Current: 714/763
• 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/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• 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: H04L 2209/04 Masking or blinding
• CPC Class Codes: H04L 2209/24 Key scheduling, i.e. generating round keys or sub-keys for block encryption
• CPC Class Codes: H04L 2209/34 Encoding or coding, e.g. Huffman coding or error correction
• 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/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/0863 involving passwords or one-time passwords network architectures or network communication protocols for using one-time keys in a packet data network H04L63/067
• CPC Class Codes: H04L 9/0869 involving random numbers or seeds
• CPC Class Codes: H04L 9/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage
• CPC Class Codes: H04L 9/14 using a plurality of keys or algorithms

Abstract

A method begins by a processing module determining a retrieval threshold for retrieving a set of encoded data slices from a dispersed storage network (DSN), wherein the set of encoded data slices represents data encoded using a dispersed storage error encoding function having a pillar width of “n”, a decode threshold of “k”, and an encoding ratio of n−k>k and wherein the retrieval threshold is in accordance with the encoding ratio. The method continues with the processing module issuing data retrieval requests to the DSN for the set of encoded data slices and receiving encoded data slices of the set of encoded data slices to produce received encoded data slices. The method continues with the processing module decoding the received encoded data slices to recapture the data when a number of received encoded data slices compares favorably to the retrieval threshold.

Claims

1. A method comprises:

determining a retrieval threshold for retrieving a set of encoded data slices from a dispersed storage network (DSN), wherein the set of encoded data slices represents data encoded using a dispersed storage error encoding function having a pillar width of “

n”

, a decode threshold of “

k”

, and an encoding ratio of n−

k>

k and wherein the retrieval threshold is in accordance with the encoding ratio;

issuing data retrieval requests to the DSN for the set of encoded data slices;

receiving encoded data slices of the set of encoded data slices to produce received encoded data slices; and

when a number of received encoded data slices compares favorably to the retrieval threshold, decoding the received encoded data slices to recapture the data.

2. The method of claim 1, where the determining the retrieval threshold comprises:

determining whether at least a write threshold number of the set of encoded data slices have a desired revision level;

when the at least the write threshold number of the set of encoded data slices have the desired revision level, establishing the retrieval threshold based on the pillar width, the write threshold, and a first constant; and

when the at least the write threshold number of the set of encoded data slices does not have the desired revision level, establishing the retrieval threshold based on the pillar width, the decode threshold, and a second constant.

3. The method of claim 1 further comprises:

determining that the number of received encoded data slices compares favorably to the retrieval threshold by;

determining whether at least a decode threshold number of the received encoded data slices have a revision number corresponding to a desired revision level; and

when the at least the decode threshold number of the received encoded data slices have the revision number corresponding to the desired revision level, indicating a favorable comparison.

4. The method of claim 3 further comprises:

when the at least the decode threshold number of the received encoded data slices does not have the revision number corresponding to the desired revision level, determining whether the at least the decode threshold number of the received encoded data slices have a revision number corresponding to a second desired revision level; and

when the at least the decode threshold number of the received encoded data slices have the revision number corresponding to the second desired revision level, indicating a favorable comparison.

5. The method of claim 3 further comprises:

when the at least the decode threshold number of the received encoded data slices does not have the revision number corresponding to the desired revision level, determining whether at least one encoded data slice of the set of encoded data slices is unreceived and accessible;

when the at least one encoded data slice of the set of encoded data slices is unreceived and accessible, reissuing the data retrieval requests to the DSN for the at least one encoded data slice;

receiving one or more of the at least one encoded data slice to produce additionally received encoded data slices; and

when a number of the received encoded data slices and the additionally received encoded data slices compares favorably to the retrieval threshold, decoding the received encoded data slices to recapture the data.

6. The method of claim 5, wherein the determining whether at least one encoded data slice of the set of encoded data slices is unreceived and accessible comprises:

determining a deficiency number of encoded data slices based on a difference between the decode threshold number and a number of the received encoded data slices that have the revision number corresponding to the desired revision level;

determining whether at least the deficiency number of encoded data slices is unreceived and is accessible;

when the at least the deficiency number of encoded data slices is unreceived and is accessible, indicating that the at least one encoded data slice of the set of encoded data slices is unreceived and accessible; and

when the at least the deficiency number of encoded data slices is not unreceived or is not accessible, indicating that the at least one encoded data slice of the set of encoded data slices is not unreceived or is not accessible.

7. A computer comprises:

an interface;

a memory; and

a processing module operable to;

determine a retrieval threshold for retrieving a set of encoded data slices from a dispersed storage network (DSN), wherein the set of encoded data slices represents data encoded using a dispersed storage error encoding function having a pillar width of “

n”

, a decode threshold of “

k”

, and an encoding ratio of n−

k>

k and wherein the retrieval threshold is in accordance with the encoding ratio;

issue, via the interface, data retrieval requests to the DSN for the set of encoded data slices;

receive, via the interface, encoded data slices of the set of encoded data slices to produce received encoded data slices; and

when a number of received encoded data slices compares favorably to the retrieval threshold, decode the received encoded data slices to recapture the data.

8. The computer of claim 7, where the processing module functions to determine the retrieval threshold by:

determining whether at least a write threshold number of the set of encoded data slices have a desired revision level;

when the at least the write threshold number of the set of encoded data slices have the desired revision level, establishing the retrieval threshold based on the pillar width, the write threshold, and a first constant; and

when the at least the write threshold number of the set of encoded data slices does not have the desired revision level, establishing the retrieval threshold based on the pillar width, the decode threshold, and a second constant.

9. The computer of claim 7, wherein the processing module further functions to:

determine that the number of received encoded data slices compares favorably to the retrieval threshold by;

determining whether at least a decode threshold number of the received encoded data slices have a revision number corresponding to a desired revision level; and

when the at least the decode threshold number of the received encoded data slices have the revision number corresponding to the desired revision level, indicating a favorable comparison.

10. The computer of claim 9, wherein the processing module further functions to:

when the at least the decode threshold number of the received encoded data slices does not have the revision number corresponding to the desired revision level, determine whether the at least the decode threshold number of the received encoded data slices have a revision number corresponding to a second desired revision level; and

when the at least the decode threshold number of the received encoded data slices have the revision number corresponding to the second desired revision level, indicate a favorable comparison.

11. The computer of claim 9, wherein the processing module further functions to:

when the at least the decode threshold number of the received encoded data slices does not have the revision number corresponding to the desired revision level, determine whether at least one encoded data slice of the set of encoded data slices is unreceived and accessible;

when the at least one encoded data slice of the set of encoded data slices is unreceived and accessible, reissue, via the interface, the data retrieval requests to the DSN for the at least one encoded data slice;

receive, via the interface, one or more of the at least one encoded data slice to produce additionally received encoded data slices; and

when a number of the received encoded data slices and the additionally received encoded data slices compares favorably to the retrieval threshold, decode the received encoded data slices to recapture the data.

12. The computer of claim 11, wherein the processing module functions to determine whether at least one encoded data slice of the set of encoded data slices is unreceived and accessible by:

determining a deficiency number of encoded data slices based on a difference between the decode threshold number and a number of the received encoded data slices that have the revision number corresponding to the desired revision level;

determining whether at least the deficiency number of encoded data slices is unreceived and is accessible;

when the at least the deficiency number of encoded data slices is unreceived and is accessible, indicating that the at least one encoded data slice of the set of encoded data slices is unreceived and accessible; and

when the at least the deficiency number of encoded data slices is not unreceived or is not accessible, indicating that the at least one encoded data slice of the set of encoded data slices is not unreceived or is not accessible.