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

• US 8,627,177 B2
• Filed: 05/20/2013
• Issued: 01/07/2014
• 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/897,567
• Publication Number:
  US 20130254624A1
• Time in Patent Office: 232 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 with a processing module determining a retrieval threshold for retrieving a set of encoded data slices from a dispersed storage network (DSN). The set of encoded data slices represents data encoded using a dispersed storage error encoding function having a number of encoded data slices in the set of encoded data slices equal to or greater than a decode threshold and the retrieval threshold is equal to or greater than the decode threshold. 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 encoded data slices from a dispersed storage network (DSN), wherein a set of encoded data slices represents data encoded using a dispersed storage error encoding function, wherein the set of encoded data slices includes a first group of encoded data slices and a second group of encoded data slices, wherein the set of encoded data slices includes a pillar width of encoded data slices and the pillar width is at least twice a decode threshold, wherein each of the first and second groups of encoded data slices includes at least a decode threshold of encoded data slices, and wherein the retrieval threshold is equal to or greater than the decode threshold;

issuing data retrieval requests to the DSN for the first or the second group of encoded data slices;

receiving encoded data slices of the first or the second group 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 further comprises:

the first group of encoded data slices having a revision level; and

the second group of encoded data slices having the revision level.

3. The method of claim 1 further comprises:

the first group of encoded data slices having a first revision level; and

the second group of encoded data slices having a second revision level.

4. The method of claim 1, wherein 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.

5. A computing device comprises:

an interface;

a memory; and

a processing module operably coupled to the memory, wherein the processing module is configured to;

determine a retrieval threshold for retrieving encoded data slices from a dispersed storage network (DSN), wherein a set of encoded data slices represents data encoded using a dispersed storage error encoding function, wherein the set of encoded data slices includes a first group of encoded data slices and a second group of encoded data slices, wherein the set of encoded data slices includes a pillar width of encoded data slices and the pillar width is at least twice a decode threshold, wherein each of the first and second groups of encoded data slices includes at least a decode threshold of encoded data slices, and wherein the retrieval threshold is equal to or greater than the decode threshold;

issue, via the interface, data retrieval requests to the DSN for the first or the second group of encoded data slices;

receive, via the interface, encoded data slices of the first or the second group 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.

6. The computing device of claim 5 further comprises:

the first group of encoded data slices having a revision level; and

the second group of encoded data slices having the revision level.

7. The computing device of claim 5 further comprises:

the first group of encoded data slices having a first revision level; and

the second group of encoded data slices having a second revision level.

8. The computing device of claim 5, wherein the processing module is further operable 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.