Highly autonomous dispersed storage system retrieval method

• US 9,195,408 B2
• Filed: 05/29/2014
• Issued: 11/24/2015
• Est. Priority Date: 10/30/2009
• Status: Expired due to Fees

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Grube, Gary W., Markison, Timothy W.
• Primary Examiner(s): GUYTON, PHILIP A
• Application Number:
  US14/290,549
• Publication Number:
  US 20140281066A1
• Time in Patent Office: 544 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: G06F 13/1668 Details of memory controller
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: G06F 3/061 Improving I/O performance
• CPC Class Codes: G06F 3/0631 by allocating resources to storage systems
• 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/09 Error detection only, e.g. using cyclic redundancy check [CRC] codes or single parity bit
• CPC Class Codes: H03M 13/15 Cyclic codes, i.e. cyclic shifts of codewords produce other codewords, e.g. codes defined by a generator polynomial, Bose-Chaudhuri-Hocquenghem [BCH] codes H03M13/17 takes precedence
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/23 using convolutional codes, e.g. unit memory codes
• CPC Class Codes: H04L 12/1432 Metric aspects
• CPC Class Codes: H04L 43/0817 by checking functioning
• 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]

Abstract

A method for accessing data in a directory-less dispersed storage (DS) network. In various embodiments, the method begins when a DS processing unit receives a read request for data stored in accordance with a dispersed storage error encoding function. Estimated storage metadata is determined based on the identity of the data, the identity of the requesting unit, and data storage preferences of the requesting unit. The estimated storage metadata is used to determine a target set of storage units. Next, a retrieval request is sent to one or more storage units of the target set. If a favorable response is received (e.g., a read threshold number of storage units return encoded data slices), the data is decoded and forwarded to the requestor. Otherwise, the storage metadata is re-estimated and used to determine a second target set of storage units for solicitation. This process continues until a favorable response is received.

Claims

1. A method for accessing data in a directory-less dispersed storage network, the method comprises:

receiving a read request for the data, the data stored in the directory-less dispersed storage network and previously encoded in accordance with a dispersed storage error encoding function to produce a plurality of sets of encoded data slices, wherein the read request includes the identity of a requesting unit and the identity of the data;

estimating storage metadata regarding the data based on the identity of the data, the identity of the requesting unit, and data storage preferences of the requesting unit;

determining a first target set of storage units of the dispersed storage network based on the estimated storage metadata;

sending a retrieval request to a storage unit of the first target set of storage units, wherein the retrieval request is regarding at least one encoded data slice of the plurality of sets of encoded data slices; and

when an unfavorable response is received from the storage unit of the first target set of storage units;

re-estimating the storage metadata based on the identity of the data, the identity of the requesting unit, the data storage preferences of the requesting unit, and the unfavorable response;

determining a second target set of storage units of the dispersed storage network based on the re-estimated storage metadata;

sending a new retrieval request to a storage unit of the second target set of storage units regarding at least one encoded data slice of the plurality of sets of encoded data slices; and

when a favorable response is received from the storage unit of the second target set of storage units, decoding at least a portion of the plurality of sets of encoded data slices to reproduce the data.

2. The method of claim 1, wherein sending the retrieval request to the storage unit of the first target set of storage units further includes sending a retrieval request to each storage unit of the first target set of storage units, further comprises:

determining if a read threshold number of favorable responses has been received from the first target set of storage units; and

when a read threshold number of favorable responses is not received, re-estimating the storage metadata based on the identity of the data, the identity of the requesting unit, the data storage preferences of the requesting unit, and the lack of a read threshold number of favorable responses.

3. The method of claim 1 further comprises:

when a favorable response is received from the storage unit of the first target set of storage units;

sending a retrieval request to additional storage units of the first target set of storage units; and

decoding at least a portion of the plurality of sets of encoded data slices to reproduce the data.

4. The method of claim 1 further comprises:

when a favorable response is received from the storage unit of the second target set of storage units, decoding at least a portion of the plurality of sets of encoded data slices to reproduce the data further includes sending retrieval requests to additional storage units of the second target set of storage units.

5. The method of claim 1 further comprises:

when an unfavorable response is received from the storage unit of the second target set of storage units, re-estimating the storage metadata based on the identity of the data, the identity of the requesting unit, the data storage preferences of the requesting unit, and the unfavorable response from the storage unit of the second target set of storage units.

6. The method of claim 1, wherein the storage metadata is based on one or more of:

metadata received in conjunction with the read request;

a user identification;

a data object name;

a data type indicator;

a previously calculated hash value of a data object;

a priority indicator;

a security indicator;

a performance requirement;

a command;

a user vault lookup;

a geographical location of a user device;

a location requirement; and

a predetermination.

7. The method of claim 1, wherein an unfavorable response received from the storage unit of the first target set of storage units is determined by the lack of a response in a given time period.

8. The method of claim 1, wherein the directory-less dispersed storage network includes a plurality of sets of storage units which are arranged based on storage unit attributes.

9. The method of claim 8, wherein the storage unit attributes include one or more of:

geographic location of the storage unit(s);

storage capacity;

network bandwidth;

link latency;

encoding parameters;

a memory status indicator;

a memory performance indicator;

domain;

cost; and

a solicitation response history indicator.

10. A method for execution by a distributed storage processing unit to access data in a directory-less dispersed storage network, the method comprises:

receiving a read request for the data, the data stored in the directory-less dispersed storage network and previously encoded in accordance with a dispersed storage error encoding function to produce a plurality of sets of encoded data slices, wherein the read request includes the identity of a requesting unit and the identity of the data;

estimating storage metadata regarding the data based on the identity of the data, the identity of the requesting unit, and data storage preferences of the requesting unit;

determining a target set of storage units of the dispersed storage network based on the estimated storage metadata;

sending a retrieval request to at least one storage unit of the target set of storage units, wherein the retrieval request is regarding at least one encoded data slice of the plurality of sets of encoded data slices;

determining if a read threshold number of favorable responses to the retrieval request has been received from the target set of storage units; and

when a read threshold number of favorable responses is received, decoding at least a portion of the plurality of sets of encoded data slices to reproduce the data.

11. The method of claim 10 further comprises:

forwarding the reproduced data to the requesting unit.

12. The method of claim 10, wherein the read threshold number corresponds to the number of encoded data slices of a set of the plurality of sets of encoded data slices that is required to recover a data segment of data, and wherein an individual encoded data slice of the set of encoded data slices yields substantially no information regarding the data segment.

13. The method of claim 10 further comprises:

when less than a read threshold number of favorable responses is received from the target set of storage units;

re-estimating the storage metadata based at least in part on the response from the at least one storage unit of the target set of storage units;

determining a second target set of storage units of the dispersed storage network based on the re-estimated storage metadata;

sending a new retrieval request to at least one storage unit of the second target set of storage units regarding at least one encoded data slice of the plurality of sets of encoded data slices; and

when a read threshold number of favorable responses to the new retrieval request is received from the second target set of storage units, decoding at least a portion of the plurality of sets of encoded data slices to reproduce the data.

14. The method of claim 13, wherein sending a new retrieval request to at least one storage unit of the second target set of storage units includes sending the new retrieval request to at least a read threshold number of the storage units of the second target set of storage units.

15. The method of claim 13, wherein the target set of storage units and the second target set of storage units include at least one common storage unit.

16. The method of claim 15, wherein the at least one common storage unit includes a storage unit that failed to provide a favorable response to the retrieval request.

17. A dispersed storage processing unit comprises:

at least one interface; and

a processing module configured to;

receive, via the at least one interface, a read request for data stored in a directory-less dispersed storage network, the data encoded in accordance with a dispersed storage error encoding function to produce a plurality of sets of encoded data slices, wherein the read request includes the identity of a requesting unit and the identity of the data;

estimate storage metadata regarding the data based on the identity of the data, the identity of the requesting unit, and data storage preferences of the requesting unit;

determine a first target set of storage units of a dispersed storage network based on the estimated storage metadata;

send, via the at least one interface, a retrieval request to a storage unit of the first target set of storage units, wherein the retrieval request is regarding at least one encoded data slice of the plurality of sets of encoded data slices; and

when an unfavorable response is received, via the at least one interface, from the storage unit of the first target set of storage units;

re-estimate the storage metadata based on the identity of the data, the identity of the requesting unit, the data storage preferences of the requesting unit, and the unfavorable response;

determine a second target set of storage units of the dispersed storage network based on the re-estimated storage metadata;

send, via the at least one interface, a new retrieval request to a storage unit of the second target set of storage units regarding at least one encoded data slice of the plurality of sets of encoded data slices; and

when a favorable response is received, via the at least one interface, from the storage unit of the second target set of storage units, decode at least a portion of the plurality of sets of encoded data slices to reproduce the data.

18. The dispersed storage processing unit of claim 17, the processing module further configured to:

when a favorable response is received, via the at least one interface, from the storage unit of the first target set of storage units;

send, via the at least one interface, a retrieval request to additional storage units of the first target set of storage units; and

decode at least a portion of the plurality of sets of encoded data slices to reproduce the data.

19. The dispersed storage processing unit of claim 17, the processing module further configured to:

forward, via the at least one interface, the reproduced data to the requesting unit.

20. The dispersed storage processing unit of claim 17, the processing module further configured to:

send, via the at least one interface, the new retrieval request to additional storage units of the second target set of storage units when a favorable response is received from the storage unit of the second target set of storage unit.