Self-optimizing read-ahead

• US 10,409,678 B2
• Filed: 11/27/2017
• Issued: 09/10/2019
• Est. Priority Date: 08/31/2012
• Status: Active Grant

• Current Assignee: Pure Storage, Inc.
• Original Assignee: Pure Storage, Inc.
• Inventors: Leggette, Wesley B., Resch, Jason K.
• Primary Examiner(s): Decady, Albert
• Assistant Examiner(s): Alshack, Osman M
• Application Number:
  US15/823,251
• Publication Number:
  US 20180081758A1
• Time in Patent Office: 652 Days
• Field of Search: 714752, 714759, 714766, 714770
• CPC Class Codes: G06F 11/0712 in a virtual computing platform, e.g. logically partitioned systems
• CPC Class Codes: G06F 11/0784 Routing of error reports, e.g. with a specific transmission path or data flow
• CPC Class Codes: G06F 11/0787 Storage of error reports, e.g. persistent data storage, storage using memory protection
• 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/1044 with specific ECC/EDC distribution
• 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/142 Reconfiguring to eliminate the error group management mechanisms in a peer-to-peer network H04L67/1044
• CPC Class Codes: G06F 11/2094 Redundant storage or storage space G06F11/2056 takes precedence
• CPC Class Codes: G06F 21/10 Protecting distributed programs or content, e.g. vending or licensing of copyrighted material protection in video systems or pay television H04N7/16 ; Digital rights management [DRM]
• CPC Class Codes: G06F 21/60 Protecting data
• CPC Class Codes: G06F 21/6272 by registering files or documents with a third party
• CPC Class Codes: H03M 13/1515 Reed-Solomon codes
• CPC Class Codes: H03M 13/611 Specific encoding aspects, e.g. encoding by means of decoding
• CPC Class Codes: H03M 13/616 Matrix operations, especially for generator matrices or check matrices, e.g. column or row permutations
• 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/0861 Generation of secret information including derivation or calculation of cryptographic keys or passwords
• 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 receiving a first read request of a plurality of read requests, from a user device of a plurality of user devices of a dispersed storage network, for a first data segment. The method continues by determining, for each read request, a read ahead scheme based on one or more read ahead parameters to produce a plurality of read ahead schemes. The method continues by determining a data retrieval scheme based on the plurality of read ahead schemes and retrieving, for each read request, one or more read ahead sets of encoded data slices. The method continues by receiving a second read request for a second data segment and verifying that read ahead data includes the second data segment. When the read ahead data includes the second data segment, the method continues by sending a representation of the read ahead data to the user device.

Claims

1. A method comprises:

receiving, by a dispersed storage (DS) processing unit of a dispersed storage network (DSN), a plurality of read requests from a plurality of user devices of the DSN, wherein a read request of the plurality of read requests is from a user device of the plurality of user devices and is regarding a first data segment of a plurality of data segments of a first data object of a plurality of data objects, wherein pluralities of data segments of the plurality of data objects are dispersed storage error encoded into pluralities of sets of encoded data slices, wherein the pluralities of sets of encoded data slices are stored in a set of storage units of the DSN;

for each read request of the plurality of read requests, determining a read ahead scheme based on one or more read ahead parameters to produce a plurality of read ahead schemes;

determining a data retrieval scheme based on the plurality of read ahead schemes;

for each read request of at least some read requests of the plurality of read requests, retrieving, by the DS processing unit from at least a decode threshold number of storage units of the set of storage units, one or more read ahead sets of encoded data slices in accordance with the data retrieval scheme and based on a corresponding read ahead scheme of the plurality of read ahead schemes to produce a plurality of one or more read ahead sets of encoded data slices;

receiving, by the DS processing unit from the user device, a second read request for a second data segment of the first data object; and

verifying, by the DS processing unit, that read ahead data includes the second data segment, wherein a corresponding one of the plurality of one or more read ahead sets of encoded data slices is decoded into the read ahead data; and

when the read ahead data includes the second data segment, sending, by the DS processing unit, a representation of the read ahead data to the user device.

2. The method of claim 1, wherein a read ahead parameter of the one or more read ahead parameters comprises:

historical data of user devices;

a requester identifier;

bandwidth of storage units;

latency of storage units;

a data consumption rate;

network bandwidth;

network reliability; and

a type of data.

3. The method of claim 1, wherein the determining the read ahead scheme comprises one or more of:

determining an amount of read ahead data;

determining a rate for the read ahead data; and

determining retrieval timing for the read ahead data.

4. The method of claim 1, wherein the determining the data retrieval scheme comprises:

determining individual read ahead data amounts for the at least some read requests;

determining a total amount of read ahead data for the at least some read requests;

determining available processing capabilities of the set of storage units; and

establishing, as the data retrieval scheme, a read ahead request pattern for the at least some of the read requests based on the individual read ahead data amounts, the total amount of read ahead data, and the available processing capabilities of the set of storage units.

5. The method of claim 4, wherein the establishing the read ahead request pattern comprises:

on a set by set basis, determining a decode threshold pattern for accessing the set of storage units for the plurality of one or more read ahead sets of encoded data slices.

6. The method of claim 1, wherein the representation of the read ahead data comprises one of:

the read ahead data; and

the corresponding one of the plurality of one or more read ahead sets of encoded data slices.

7. A dispersed storage (DS) processing unit of a dispersed storage network (DSN) comprises:

memory;

an interface; and

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

receive, via the interface, a plurality of read requests from a plurality of user devices of the DSN, wherein a read request of the plurality of read requests is from a user device of the plurality of user devices and is regarding a first data segment of a plurality of data segments of a first data object of a plurality of data objects, wherein pluralities of data segments of the plurality of data objects are dispersed storage error encoded into pluralities of sets of encoded data slices, wherein the pluralities of sets of encoded data slices are stored in a set of storage units of the DSN;

for each read request of the plurality of read requests, determine a read ahead scheme based on one or more read ahead parameters to produce a plurality of read ahead schemes;

determine a data retrieval scheme based on the plurality of read ahead schemes;

for each read request of at least some read requests of the plurality of read requests, retrieve from at least a decode threshold number of storage units of the set of storage units, one or more read ahead sets of encoded data slices in accordance with the data retrieval scheme and based on a corresponding read ahead scheme of the plurality of read ahead schemes to produce a plurality of one or more read ahead sets of encoded data slices;

receive, via the interface from the user device, a second read request for a second data segment of the first data object; and

verify that read ahead data includes the second data segment, wherein a corresponding one of the plurality of one or more read ahead sets of encoded data slices is decoded into the read ahead data; and

when the read ahead data includes the second data segment, send, via the interface, a representation of the read ahead data to the user device.

8. The DS processing unit of claim 7, wherein a read ahead parameter of the one or more read ahead parameters comprises:

historical data of user devices;

a requester identifier;

bandwidth of storage units;

latency of storage units;

a data consumption rate;

network bandwidth;

network reliability; and

a type of data.

9. The DS processing unit of claim 7, wherein the processing module determines the read ahead scheme by one or more of:

determining an amount of read ahead data;

determining a rate for the read ahead data; and

determining retrieval timing for the read ahead data.

10. The DS processing unit of claim 7, wherein the processing module determines the data retrieval scheme by:

determining individual read ahead data amounts for the at least some read requests;

determining a total amount of read ahead data for the at least some read requests;

determining available processing capabilities of the set of storage units; and

establishing, as the data retrieval scheme, a read ahead request pattern for the at least some of the read requests based on the individual read ahead data amounts, the total amount of read ahead data, and the available processing capabilities of the set of storage units.

11. The DS processing unit of claim 10, wherein the processing module establishes the read ahead request pattern by:

on a set by set basis, determining a decode threshold pattern for accessing the set of storage units for the plurality of one or more read ahead sets of encoded data slices.

12. The DS processing unit of claim 7, wherein the processing module sends, via the interface, the representation of the read ahead data by one of:

sending the read ahead data; and

sending the corresponding one of the plurality of one or more read ahead sets of encoded data slices.

13. A computer readable memory device of a dispersed storage network (DSN) comprises:

a first memory element for storing operational instructions that, when executed by a dispersed storage (DS) processing unit of the DSN, causes the DS processing unit to;

receive a plurality of read requests from a plurality of user devices of the DSN, wherein a read request of the plurality of read requests is from a user device of the plurality of user devices and is regarding a first data segment of a plurality of data segments of a first data object of a plurality of data objects, wherein pluralities of data segments of the plurality of data objects are dispersed storage error encoded into pluralities of sets of encoded data slices, wherein the pluralities of sets of encoded data slices are stored in a set of storage units of the DSN; and

receive from the user device, a second read request for a second data segment of the first data object;

a second memory element for storing operational instructions that, when executed by the DS processing unit, causes the DS processing unit to;

for each read request of the plurality of read requests, determine a read ahead scheme based on one or more read ahead parameters to produce a plurality of read ahead schemes; and

determine a data retrieval scheme based on the plurality of read ahead schemes;

a third memory element for storing operational instructions that, when executed by the DS processing unit, causes the DS processing unit to;

for each read request of at least some read requests of the plurality of read requests, retrieve from at least a decode threshold number of storage units of the set of storage units, one or more read ahead sets of encoded data slices in accordance with the data retrieval scheme and based on a corresponding read ahead scheme of the plurality of read ahead schemes to produce a plurality of one or more read ahead sets of encoded data slices; and

a fourth memory element for storing operational instructions that, when executed by the DS processing unit, causes the DS processing unit to;

verify that read ahead data includes the second data segment, wherein a corresponding one of the plurality of one or more read ahead sets of encoded data slices is decoded into the read ahead data; and

when the read ahead data includes the second data segment, send a representation of the read ahead data to the user device.

14. The computer readable memory device of claim 13, wherein a read ahead parameter of the one or more read ahead parameters comprises:

historical data of user devices;

a requester identifier;

bandwidth of storage units;

latency of storage units;

a data consumption rate;

network bandwidth;

network reliability; and

a type of data.

15. The computer readable memory device of claim 13, wherein the second memory element stores further operational instructions that, when executed by the DS processing unit, causes the DS processing unit to determine the read ahead scheme by one or more of:

determining an amount of read ahead data;

determining a rate for the read ahead data; and

determining retrieval timing for the read ahead data.

16. The computer readable memory device of claim 13, wherein the second memory element stores further operational instructions that, when executed by the DS processing unit, causes the DS processing unit to determine the data retrieval scheme by:

determining individual read ahead data amounts for the at least some read requests;

determining a total amount of read ahead data for the at least some read requests;

determining available processing capabilities of the set of storage units; and

establishing, as the data retrieval scheme, a read ahead request pattern for the at least some of the read requests based on the individual read ahead data amounts, the total amount of read ahead data, and the available processing capabilities of the set of storage units.

17. The computer readable memory device of claim 16, wherein the second memory element stores further operational instructions that, when executed by the DS processing unit, causes the DS processing unit to establish the read ahead request pattern by:

on a set by set basis, determining a decode threshold pattern for accessing the set of storage units for the plurality of one or more read ahead sets of encoded data slices.

18. The computer readable memory device of claim 13, wherein a fourth memory element stores further operational instructions that, when executed by the DS processing unit, causes the DS processing unit to send the representation of the read ahead data by one of:

sending the read ahead data; and

sending the corresponding one of the plurality of one or more read ahead sets of encoded data slices.