Autonomous dispersed storage system retrieval method

• US 9,262,288 B2
• Filed: 06/12/2014
• Issued: 02/16/2016
• Est. Priority Date: 10/30/2009
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: International Business Machines Corporation
• Inventors: Grube, Gary W., Markison, Timothy W.
• Primary Examiner(s): GUYTON, PHILIP A
• Application Number:
  US14/302,772
• Publication Number:
  US 20140289555A1
• Time in Patent Office: 614 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 11/2089 Redundant storage control functionality
• CPC Class Codes: G06F 12/0802 Addressing of a memory level in which the access to the desired data or data block requires associative addressing means, e.g. caches
• CPC Class Codes: G06F 12/1009 using page tables, e.g. page table structures
• CPC Class Codes: G06F 12/1045 associated with a data cache
• CPC Class Codes: G06F 13/1668 Details of memory controller
• CPC Class Codes: G06F 2212/401 Compressed data
• CPC Class Codes: G06F 3/0604 Improving or facilitating administration, e.g. storage management
• CPC Class Codes: G06F 3/0619 in relation to data integrity, e.g. data losses, bit errors
• CPC Class Codes: G06F 3/0629 Configuration or reconfiguration of storage systems
• CPC Class Codes: G06F 3/0659 Command handling arrangements, e.g. command buffers, queues, command scheduling
• CPC Class Codes: G06F 3/067 Distributed or networked storage systems, e.g. storage area networks [SAN], network attached storage [NAS]
• CPC Class Codes: G06F 3/0683 Plurality of storage devices
• 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 41/06 Management of faults, events, alarms or notifications
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 67/06 specially adapted for file transfer, e.g. file transfer protocol [FTP]
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• 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 execution by a storage unit in a directory-less distributed storage network (DSN) begins by receiving a read request regarding a data segment of data. The method continues by determining, based on the read request, whether an encoded data slice of a set of encoded data slices is locally stored, wherein the data segment was dispersed storage error encoded to produce the set of encoded data slices. When the encoded data slices are locally stored, the method continues by generating a read response. The method continues by determining whether to forward the read request to another storage unit of the directory-less DSN. When the read request is to be forwarded, the method continues by identifying one or more storage units to which the read request is to be forwarded and the read request is then forwarded to the one or more identified storage units.

Claims

1. A method for execution by a storage unit in a directory-less distributed storage network (DSN), the method comprises:

receiving a read request regarding a data segment of data;

determining, based on the read request, whether an encoded data slice of a set of encoded data slices is locally stored, wherein the data segment was dispersed storage error encoded to produce the set of encoded data slices;

when the encoded data slice is locally stored, generating a read response;

outputting the read response;

determining whether to forward the read request to another storage unit of the directory-less DSN;

when the read request is to be forwarded;

identifying one or more storage units of the directory-less DSN to which the read request is to be forwarded, wherein the identifying one or more storage units includes one or more of;

accessing a table of localized mapping regarding one or more neighboring storage units to identify the one or more storage units; and

receiving a message from a network management unit; and

forwarding the read request to the one or more identified storage units.

2. The method of claim 1 further comprises:

receiving a data object identifier within the read request;

determining whether slices names of stored encoded data slices within the storage unit include a corresponding portion that substantially matches the data object identifier; and

when one or more of the slices names of the stored encoded data slices has the corresponding portion that substantially matches the data object identifier, indicating that the encoded data slice is locally stored.

3. The method of claim 1 further comprises:

generating the read response to include the encoded data slice; and

outputting the read response to a request entity that sent the read request.

4. The method of claim 1 further comprises:

generating the read response to include a slice name of the encoded data slice;

outputting the read response to a request entity that sent the read request;

receiving a slice read request from the request entity, wherein the slice read request includes the slice name; and

generating a second read response to include the encoded data slice; and

outputting the second read response to the request entity.

5. The method of claim 1 further comprises:

generating the read response to include the encoded data slice; and

outputting the read response to the identified one or more storage units.

6. The method of claim 1 further comprises:

generating the read response to include a slice name of the encoded data slice; and

outputting the read response to the identified one or more storage units.

7. The method of claim 1, wherein the determining whether to forward the read request to another storage unit comprises:

receiving the read request for a second other storage unit as a forward read request, wherein the forward read request includes propagated response information regarding a number of encoded data slices of the set of encoded data slices that have been identified in response to the read request;

when the number of encoded data slices that have been identified in response to the request plus the encoded data slice is equal to or greater than a decode threshold, indicating that the read request does not require forwarding; and

when the number of encoded data slices that have been identified in response to the request plus the encoded data slice is less than the decode threshold, indicating that the read request is to be forwarded.

8. The method of claim 1, wherein the identifying one or more storage units further comprises:

determining whether slices names of stored encoded data slices within the storage unit include a corresponding portion that substantially matches a data object identifier;

when a slice name of the slice names includes a corresponding portion that substantially matches the data object identifier, generating slices names of other slices of the set of encoded data slices; and

identifying the one more storage units based on one or more of the generated slices names of the other slices.

9. A storage unit operable in a directory-less distributed storage network (DSN) comprises:

an interface;

memory; and

a processing module operably coupled to the interface and to the memory, wherein the processing module is operable to;

receive, via the interface, a read request regarding a data segment of data;

determine, based on the read request, whether an encoded data slice of a set of encoded data slices is locally stored, wherein the data segment was dispersed storage error encoded to produce the set of encoded data slices;

when the encoded data slices is locally stored, generate a read response;

output, via the interface, the read response;

determine whether to forward the read request to another storage unit of the directory-less DSN;

when the read request is to be forwarded;

identify one or more storage units of the directory-less DSN to which the read request is to be forwarded, wherein the identifying one or more storage units includes one or more of;

accessing a table of localized mapping regarding one or more neighboring storage units to identify the one or more storage units; and

receiving a message from a network management unit; and

forward, via the interface, the read request to the one or more identified storage units.

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

receive a data object identifier within the read request;

determine whether slice names of stored encoded data slices within the storage unit include a corresponding portion that substantially matches the data object identifier; and

when one or more of the slice names of the stored encoded data slices has the corresponding portion that substantially matches the data object identifier, indicate that the encoded data slice is locally stored.

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

generate the read response to include the encoded data slice; and

output the read response to a request entity that sent the read request.

12. The storage unit of claim 9, wherein the processing module further functions to:

generate the read response to include a slice name of the encoded data slice;

output the read response to a request entity that sent the read request;

receive a slice read request from the request entity, wherein the slice read request includes the slice name; and

generate a second read response to include the encoded data slice; and

output the second read response to the request entity.

13. The storage unit of claim 9, wherein the processing module further functions to:

generate the read response to include the encoded data slice; and

output the read response to the identified one or more storage units.

14. The storage unit of claim 9, wherein the processing module further functions to:

generate the read response to include a slice name of the encoded data slice; and

output the read response to the identified one or more storage units.

15. The storage unit of claim 9, wherein the processing module in the determining whether to forward the read request to another storage unit further functions to:

receive the read request for a second other storage unit as a forward read request, wherein the forward read request includes propagated response information regarding a number of encoded data slices of the set of encoded data slices that have been identified in response to the read request;

when the number of encoded data slices that have been identified in response to the request plus the encoded data slice is equal to or greater than a decode threshold, indicate that the read request does not require forwarding; and

when the number of encoded data slices that have been identified in response to the request plus the encoded data slice is less than the decode threshold, indicate that the read request is to be forwarded.

16. The storage unit of claim 9, wherein the processing module in the identifying the one or more storage units further functions to:

determine whether slice names of stored encoded data slices within the storage unit include a corresponding portion that substantially matches a data object identifier;

when a slice name of the slice names includes a corresponding portion that substantially matches the data object identifier, generate slice names of other slices of the set of encoded data slices; and

identify the one more storage units based on one or more of the generated slice names of the other slices.