SLICE RETRIEVAL IN ACCORDANCE WITH AN ACCESS SEQUENCE IN A DISPERSED STORAGE NETWORK

• US 20110265143A1
• Filed: 02/04/2011
• Published: 10/27/2011
• Est. Priority Date: 04/26/2010
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Markison, Timothy W., Grube, Gary W.
• Granted Patent: US 9,063,881 B2
• Time in Patent Office: Days
• US Class Current: 726/2
• CPC Class Codes: G06F 11/0727 in a storage system, e.g. in a DASD or network based storage system drivers for digital recording or reproducing units G06F3/06; circuits for error detection or correction within digital recording or reproducing units G11B20/18; 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], H04L67/1097
• CPC Class Codes: G06F 11/076 by exceeding a count or rate limit, e.g. word- or bit count limit
• CPC Class Codes: G06F 11/0763 by bit configuration check, e.g. of formats or tags
• 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/1008 in individual solid state devices G06F11/1004 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 11/1464 for networked environments
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 16/27 Replication, distribution or synchronisation of data between databases or within a distributed database system; Distributed database system architectures therefor
• CPC Class Codes: G06F 21/60 Protecting data
• CPC Class Codes: G06F 21/6218 to a system of files or objects, e.g. local or distributed file system or database
• CPC Class Codes: G06F 21/64 Protecting data integrity, e.g. using checksums, certificates or signatures
• CPC Class Codes: G06F 21/70 Protecting specific internal or peripheral components, in which the protection of a component leads to protection of the entire computer
• CPC Class Codes: G06F 2211/1028 Distributed, i.e. distributed RAID systems with parity
• CPC Class Codes: H04L 2209/30 Compression, e.g. Merkle-Damgard construction
• 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/0894 Escrow, recovery or storing of secret information, e.g. secret key escrow or cryptographic key storage

Abstract

A method begins by a processing module receiving a data retrieval request to retrieve data stored as a plurality of sets of encoded data slices in a dispersed storage network memory. The method continues with the processing module determining an access sequence for retrieving the plurality of sets of encoded data slices in accordance with the access sequence, entering a loop to produce recovered decoded data that includes sending a slice retrieval message for a set of encoded data slices of the plurality of sets of encoded data slices, receiving at least a decode threshold number of encoded data slices of the set to produce received encoded data slices, dispersed storage error decoding the received encoded data slices to produce the recovered decoded data, and exiting the loop when a set of encoded data slices is not requested in accordance with a system maintained access sequence.

Claims

1. A method comprises:

receiving a data retrieval request to retrieve data stored as a plurality of sets of encoded data slices in a dispersed storage network (DSN) memory, wherein the data retrieval request includes a data identifier (ID);

determining an access sequence for retrieving the plurality of sets of encoded data slices based on the data ID; and

in accordance with the access sequence, entering a loop that includes;

sending a slice retrieval message for a set of encoded data slices of the plurality of sets of encoded data slices;

when the set of encoded data slices or a previous set of encoded data slices is requested in accordance with a system maintained access sequence, receiving at least a decode threshold number of encoded data slices of the set to produce received encoded data slices;

dispersed storage error decoding the received encoded data slices to produce recovered decoded data;

exiting the loop when the set of encoded data slices is a last set of the plurality of sets of encoded data slices or when the set of encoded data slices or the previous set of encoded data slices is not requested in accordance with the system maintained access sequence; and

repeating the loop when the set of encoded data slices is not the last set of the plurality of sets of encoded data slices and when request of the set of encoded data slices and the previous set of encoded data slices are requested in accordance with the system maintained access sequence.

2. The method of claim 1 further comprises:

when the loop is exited as a result of the set of encoded data slices being the last set of the plurality of sets of encoded data slices, combining the recovered decoded data to produce a data file.

3. The method of claim 2, wherein the set of encoded data slices comprises at least one of:

encoded data slices of a data segment of a plurality of data segments of the data file; and

encoded data slices of the plurality of data segments having a common pillar number.

4. The method of claim 1, wherein the determining the access sequence is based on at least one of:

the data ID;

a requester ID;

a source name;

a data type indicator;

a vault lookup;

a predetermination;

a command;

a message;

a dispersed storage (DS) processing unit ID;

a priority indicator;

a performance indicator; and

a reliability indicator.

5. The method of claim 1, wherein the access sequence comprises at least one of:

a series of ordered slice names of the plurality of sets of slice names;

a series of ordered segment identification codes; and

a series of ordered pillar identification codes.

6. A method comprises:

detecting a data retrieval request regarding retrieval of data stored as a plurality of sets of encoded data slices in a dispersed storage network (DSN) memory;

determining a system maintained access sequence for retrieving the plurality of sets of encoded data slices based on the data retrieval request; and

in accordance with a sequence of retrieving the plurality of sets of encoded data slices, entering a loop that includes;

detecting a slice retrieval message for a set of encoded data slices of the plurality of sets of encoded data slices;

determining whether the set of encoded data slices or a previous set of encoded data slices is requested in accordance with the system maintained access sequence;

when the set of encoded data slices or the previous set of encoded data slices is not retrieved in accordance with the system maintained access sequence, sending a retrieval termination message to the DSN memory and exiting the loop; and

repeating the loop when the set of encoded data slices is not a last set of the plurality of sets of encoded data slices and when request of the set of encoded data slices and the previous set of encoded data slices are retrieved in accordance with the system maintained access sequence.

7. The method of claim 6, wherein the set of encoded data slices comprises at least one of:

encoded data slices of a data segment of a plurality of data segments of the data file; and

encoded data slices of the plurality of data segments having a common pillar number.

8. The method of claim 6, wherein the determining the system maintained access sequence is based on at least one of:

the data ID;

a requester ID;

a source name;

a data type indicator;

a vault lookup;

a predetermination;

a command;

a message;

a dispersed storage (DS) processing unit ID;

a priority indicator;

a performance indicator; and

a reliability indicator.

9. The method of claim 6, wherein the system maintained access sequence comprises at least one of:

a series of ordered slice names of the plurality of sets of slice names;

a series of ordered segment identification codes; and

a series of ordered pillar identification codes.

10. The method of claim 6, wherein the sending the retrieval termination message to the DSN memory comprises at least one of:

sending the retrieval termination message to one or more dispersed storage (DS) units;

sending the retrieval termination message to a DS processing unit; and

sending the retrieval termination message to a DS managing unit.

11. The method of claim 6, wherein the determining whether the set of encoded data slices or the previous set of encoded data slices is requested in accordance with the system maintained access sequence comprises:

extracting temporal retrieval information of the set of encoded data slices and the previous set of encoded data slices;

ordering the set of encoded data slices and the previous set of encoded data slice in accordance with the temporal retrieval information to produce an actual access sequence; and

comparing the system maintained access sequence with the actual access sequence.

12. A computer comprises:

an interface;

a memory; and

a processing module operable to;

receive, via the interface, a data retrieval request to retrieve data stored as a plurality of sets of encoded data slices in a dispersed storage network (DSN) memory, wherein the data retrieval request includes a data identifier (ID);

determine an access sequence for retrieving the plurality of sets of encoded data slices based on the data ID; and

in accordance with the access sequence, enter a loop that includes;

sending, via the interface, a slice retrieval message for a set of encoded data slices of the plurality of sets of encoded data slices;

when the set of encoded data slices or a previous set of encoded data slices is requested in accordance with a system maintained access sequence, receiving, via the interface, at least a decode threshold number of encoded data slices of the set to produce received encoded data slices;

dispersed storage error decoding the received encoded data slices to produce recovered decoded data;

exiting the loop when the set of encoded data slices is a last set of the plurality of sets of encoded data slices or when the set of encoded data slices or the previous set of encoded data slices is not requested in accordance with the system maintained access sequence; and

repeating the loop when the set of encoded data slices is not the last set of the plurality of sets of encoded data slices and when request of the set of encoded data slices and the previous set of encoded data slices are requested in accordance with the system maintained access sequence.

13. The computer of claim 12, wherein the processing module further functions to:

when the loop is exited as a result of the set of encoded data slices being the last set of the plurality of sets of encoded data slices, combine the recovered decoded data to produce a data file.

14. The computer of claim 13, wherein the set of encoded data slices comprises at least one of:

encoded data slices of a data segment of a plurality of data segments of the data file; and

encoded data slices of the plurality of data segments having a common pillar number.

15. The computer of claim 12, wherein the processing module functions to determine the access sequence based on at least one of:

the data ID;

a requester ID;

a source name;

a data type indicator;

a vault lookup;

a predetermination;

a command;

a message;

a dispersed storage (DS) processing unit ID;

a priority indicator;

a performance indicator; and

a reliability indicator.

16. The computer of claim 12, wherein the access sequence comprises at least one of:

a series of ordered slice names of the plurality of sets of slice names;

a series of ordered segment identification codes; and

a series of ordered pillar identification codes.

17. A computer comprises:

an interface;

a memory; and

a processing module operable to;

detect a data retrieval request regarding retrieval of data stored as a plurality of sets of encoded data slices in a dispersed storage network (DSN) memory;

determine a system maintained access sequence for retrieving the plurality of sets of encoded data slices based on the data retrieval request; and

in accordance with a sequence of retrieving the plurality of sets of encoded data slices, enter a loop that includes;

detecting a slice retrieval message for a set of encoded data slices of the plurality of sets of encoded data slices;

determining whether the set of encoded data slices or a previous set of encoded data slices is requested in accordance with the system maintained access sequence;

when the set of encoded data slices or the previous set of encoded data slices is not retrieved in accordance with the system maintained access sequence, sending, via the interface, a retrieval termination message to the DSN memory and exiting the loop; and

repeating the loop when the set of encoded data slices is not a last set of the plurality of sets of encoded data slices and when request of the set of encoded data slices and the previous set of encoded data slices are retrieved in accordance with the system maintained access sequence.

18. The computer of claim 17, wherein the set of encoded data slices comprises at least one of:

encoded data slices of a data segment of a plurality of data segments of the data file; and

encoded data slices of the plurality of data segments having a common pillar number.

19. The computer of claim 17, wherein the processing module functions to determine the system maintained access sequence based on at least one of:

the data ID;

a requester ID;

a source name;

a data type indicator;

a vault lookup;

a predetermination;

a command;

a message;

a dispersed storage (DS) processing unit ID;

a priority indicator;

a performance indicator; and

a reliability indicator.

20. The computer of claim 17, wherein the system maintained access sequence comprises at least one of:

a series of ordered slice names of the plurality of sets of slice names;

a series of ordered segment identification codes; and

a series of ordered pillar identification codes.

21. The computer of claim 17, wherein the processing module further functions to send the retrieval termination message to the DSN memory by at least one of:

sending, via the interface, the retrieval termination message to one or more dispersed storage (DS) units;

sending, via the interface, the retrieval termination message to a DS processing unit; and

sending, via the interface, the retrieval termination message to a DS managing unit.

22. The computer of claim 17, wherein the processing module further functions to determine whether the set of encoded data slices or the previous set of encoded data slices is requested in accordance with the system maintained access sequence by:

extracting temporal retrieval information of the set of encoded data slices and the previous set of encoded data slices;

ordering the set of encoded data slices and the previous set of encoded data slice in accordance with the temporal retrieval information to produce an actual access sequence; and

comparing the system maintained access sequence with the actual access sequence.