Pre-fetching data segments stored in a dispersed storage network

• US 8,874,990 B2
• Filed: 03/06/2012
• Issued: 10/28/2014
• Est. Priority Date: 04/01/2011
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Cleversafe Incorporated (International Business Machines Corporation)
• Inventors: Leggette, Wesley, Volvovski, Ilya, Baptist, Andrew, Resch, Jason K.
• Primary Examiner(s): Bhatia, Ajay
• Assistant Examiner(s): GANDHI, DIPAKKUMAR B
• Application Number:
  US13/413,261
• Publication Number:
  US 20120254687A1
• Time in Patent Office: 966 Days
• US Class Current: 714/763
• CPC Class Codes: G06F 11/1076 Parity data used in redundant arrays of independent storages, e.g. in RAID systems
• CPC Class Codes: H04L 2209/34 Encoding or coding, e.g. Huffman coding or error correction
• CPC Class Codes: H04L 67/1004 Server selection for load balancing
• 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 67/5681 Pre-fetching or pre-delivering data based on network characteristics
• CPC Class Codes: H04L 9/085 Secret sharing or secret splitting, e.g. threshold schemes
• CPC Class Codes: H04L 9/0891 Revocation or update of secret information, e.g. encryption key update or rekeying
• 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/3247 involving digital signatures
• CPC Class Codes: H04N 21/8358 involving watermark protecting executable software by watermarking G06F21/16; image watermarking in general G06T1/0021; watermarks inserted in still images for transmission purposes H04N1/32144; inserting watermarks during video coding H04N19/467

Abstract

A method begins by a processing module receiving a data segment retrieval request regarding a data segment, which is stored in a dispersed storage network (DSN) memory. The method continues with the processing module processing the data segment retrieval request, determining pre-fetch segment buffering information, and when the pre-fetch segment buffering information indicates pre-fetching one or more other data segments, generating one or more pre-fetch segment retrieval requests for the one or more other data segments, receiving, one or more sets of at least a decode threshold number of encoded data slices, decoding, in accordance with a dispersed storage error coding function, the one or more sets of at least a decode threshold number of encoded data slices to reproduce the one or more other data segments, and updating a pre-fetch segment buffer with the one or more other data segments.

Claims

1. A method comprises:

receiving a data segment retrieval request regarding a data segment of a plurality of data segments, wherein the data segment is encoded in accordance with a dispersed storage error coding function to produce a set of encoded data slices, which is stored in a set of dispersed storage (DS) units of a dispersed storage network (DSN) memory; and

in response to the data segment retrieval request;

processing the data segment retrieval request;

determining pre-fetch segment buffering information based on the data segment, content of a pre-fetch segment buffer, a data consumption rate, and DS unit response rate; and

when the pre-fetch segment buffering information indicates pre-fetching one or more other data segments of the plurality of data segments;

generating one or more pre-fetch segment retrieval requests for the one or more other data segments;

receiving, in response to the one or more pre-fetch segment retrieval requests, one or more sets of at least a decode threshold number of encoded data slices;

decoding, in accordance with the dispersed storage error coding function, the one or more sets of at least the decode threshold number of encoded data slices to reproduce the one or more other data segments; and

updating the pre-fetch segment buffer with the one or more other data segments.

2. The method of claim 1, wherein the processing the data segment retrieval request comprises:

determining whether the data segment is stored in the pre-fetch segment buffer; and

when the data segment is not stored in the pre-fetch segment buffer;

determining whether the data segment is identified in previous pre-fetch segment buffering information;

when the data segment is identified in the previous pre-fetch segment buffering information, retrieving the data segment from the pre-fetch segment buffer when the data segment is stored in the pre-fetch segment buffer; and

when the data segment is not identified in the previous pre-fetch segment buffering information;

generating a set of at least a decode threshold number of encoded data slice retrieval requests regarding at least a decode threshold number of the set of encoded data slices; and

decoding the at least the decode threshold number of the set of encoded data slices to reproduce the data segment.

3. The method of claim 1, wherein the processing the data segment retrieval request comprises:

determining whether the data segment is stored in the pre-fetch segment buffer; and

when the data segment is stored in the pre-fetch segment buffer, retrieving the data segment from the pre-fetch segment buffer.

4. The method of claim 1, wherein the pre-fetch segment buffering information comprises one or more of:

identity of the one or more other data segments;

a number of encoded data slices to retrieve for each of the one or more other data segments;

pillar identifiers (IDs) corresponding to encoded data slices of the number of encoded data slices to retrieve;

a set of DS unit IDs associated with the pillar IDs; and

a data segment retrieval performance goal.

5. The method of claim 1, wherein generating one or more pre-fetch segment retrieval requests comprises:

for a pre-fetch segment retrieval request of the one or more pre-fetch segment retrieval requests, generating at least a decode threshold number of encoded data slices retrieval requests.

6. The method of claim 1, wherein the DS unit response rate comprises:

a plurality of DS response characteristics for a plurality of DS units, wherein the plurality of DS units includes the set of DS units and wherein a DS response characteristic includes one or more of;

a pillar identifier (ID), response latency information, processing consumption, network traffic, response history, and reliability information.

7. The method of claim 1, wherein the determining the pre-fetch segment buffering information further comprises:

determining a data segment retrieval trend of the plurality of data segments; and

determining the pre-fetch segment buffering information further based on the data segment retrieval trend.

8. A module comprises:

a first module operable to receive a data segment retrieval request regarding a data segment of a plurality of data segments, wherein the data segment is encoded in accordance with a dispersed storage error coding function to produce a set of encoded data slices, which is stored in a set of dispersed storage (DS) units of a dispersed storage network (DSN) memory; and

in response to the data segment retrieval request;

a second module operable to process the data segment retrieval request;

a third module operable to determine pre-fetch segment buffering information based on the data segment, content of a pre-fetch segment buffer, a data consumption rate, and DS unit response rate; and

when the pre-fetch segment buffering information indicates pre-fetching one or more other data segments of the plurality of data segments, a fourth module operable to;

generate one or more pre-fetch segment retrieval requests for the one or more other data segments;

receive, in response to the one or more pre-fetch segment retrieval requests, one or more sets of at least a decode threshold number of encoded data slices;

decode, in accordance with the dispersed storage error coding function, the one or more sets of at least the decode threshold number of encoded data slices to reproduce the one or more other data segments; and

update the pre-fetch segment buffer with the one or more other data segments.

9. The module of claim 8, wherein the second module functions to process the data segment retrieval request by:

determining whether the data segment is stored in the pre-fetch segment buffer; and

when the data segment is not stored in the pre-fetch segment buffer;

determining whether the data segment is identified in previous pre-fetch segment buffering information;

when the data segment is identified in the previous pre-fetch segment buffering information, retrieving the data segment from the pre-fetch segment buffer when the data segment is stored in the pre-fetch segment buffer; and

when the data segment is not identified in the previous pre-fetch segment buffering information;

generating a set of at least a decode threshold number of encoded data slice retrieval requests regarding at least a decode threshold number of the set of encoded data slices; and

decoding the at least the decode threshold number of the set of encoded data slices to reproduce the data segment.

10. The module of claim 8, wherein the second module further functions to process the data segment retrieval request by:

determining whether the data segment is stored in the pre-fetch segment buffer; and

when the data segment is stored in the pre-fetch segment buffer, retrieving the data segment from the pre-fetch segment buffer.

11. The module of claim 8, wherein the pre-fetch segment buffering information comprises one or more of:

identity of the one or more other data segments;

a number of encoded data slices to retrieve for each of the one or more other data segments;

pillar identifiers (IDs) corresponding to encoded data slices of the number of encoded data slices to retrieve;

a set of DS unit IDs associated with the pillar IDs; and

a data segment retrieval performance goal.

12. The module of claim 8, wherein the fourth module functions to generate one or more pre-fetch segment retrieval requests by:

for a pre-fetch segment retrieval request of the one or more pre-fetch segment retrieval requests, generating at least a decode threshold number of encoded data slices retrieval requests.

13. The module of claim 8, wherein the DS unit response rate comprises:

a plurality of DS response characteristics for a plurality of DS units, wherein the plurality of DS units includes the set of DS units and wherein a DS response characteristic includes one or more of;

a pillar identifier (ID), response latency information, processing consumption, network traffic, response history, and reliability information.

14. The module of claim 8, wherein the third module functions to determine the pre-fetch segment buffering information further by:

determining a data segment retrieval trend of the plurality of data segments; and

determining the pre-fetch segment buffering information further based on the data segment retrieval trend.