Speculative reads

• US 9,483,407 B2
• Filed: 08/25/2014
• Issued: 11/01/2016
• Est. Priority Date: 12/17/2010
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Inventors: Sivasubramanian, Swaminathan, Marshall, Bradley Eugene, Certain, Tate Andrew, Maniscalco, Nicholas J.
• Primary Examiner(s): Bertram, Ryan
• Application Number:
  US14/468,270
• Publication Number:
  US 20140365732A1
• Time in Patent Office: 799 Days
• US Class Current: 1/1
• CPC Class Codes: G06F 12/0862 with prefetch
• CPC Class Codes: G06F 12/0866 for peripheral storage systems, e.g. disk cache
• CPC Class Codes: G06F 2212/6026 Prefetching based on access pattern detection, e.g. stride based prefetch
• CPC Class Codes: G06F 9/38 Concurrent instruction execution, e.g. pipeline or look ahead
• CPC Class Codes: G06F 9/3832 Value prediction for operands; operand history buffers
• CPC Class Codes: G06F 9/3863 using multiple copies of the architectural state, e.g. shadow registers

Abstract

Patterns of access and/or behavior can be analyzed and persisted for use in pre-fetching data from a physical storage device. In at least some embodiments, data can be aggregated across volumes, instances, users, applications, or other such entities, and that data can be analyzed to attempt to determine patterns for any of those entities. The patterns and/or analysis can be persisted such that the information is not lost in the event of a reboot or other such occurrence. Further, aspects such as load and availability across the network can be analyzed to determine where to send and/or store data that is pre-fetched from disk or other such storage in order to reduce latency while preventing bottlenecks or other such issues with resource availability.

Claims

1. A computer-implemented method, comprising:

receiving, from a source, a plurality of read requests for data stored in a data store, the plurality of read requests having been received over a period of time;

analyzing information describing the plurality of read requests to identify at least one pattern of accessing data stored in the data store;

determining that a level of certainty for the at least one pattern of accessing data satisfies a threshold certainty; and

associating the at least one pattern of accessing data and at least one network or resource constraint with the source, wherein the at least one network or resource constraint is to be satisfied before the at least one pattern is able to be applied to at least one subsequent read request that is received from the source.

2. The computer-implemented method of claim 1, wherein the source is a user operating a computing device, and wherein associating the at least one pattern of accessing data further comprises:

associating the at least one pattern of accessing data with the user, wherein the at least one pattern is able to be applied to at least one subsequent read request that is initiated by the user.

3. The computer-implemented method of claim 1, wherein the source is an application running on a computing device, and wherein associating the at least one pattern of accessing data further comprises:

associating the at least one pattern of accessing data with the application, wherein the at least one pattern is able to be applied to at least one subsequent read request that is initiated by the application.

4. A computer-implemented method, comprising:

receiving a read request for data from a computing device;

obtaining the data to satisfy the read request;

determining that a data access pattern corresponding to the read request matches at least one known access pattern associated with the computing device;

determining that a status of at least one performance criterion is verified before the at least one known pattern is able to be applied to the read request; and

performing at least one speculative read to pre-fetch additional data based at least in part on the at least one known access pattern.

5. The computer-implemented method of claim 4, wherein performing at least one speculative read to pre-fetch additional data based at least in part on the at least one known access pattern further comprises:

determining, based on the at least one known access pattern, at least one block of data that is likely to be requested in a subsequent read request.

6. The computer-implemented method of claim 4, further comprising:

receiving a second read request for data from the computing device;

determining that a data access pattern corresponding to the second read request matches a plurality of known access patterns;

selecting an access pattern from the plurality of known access patterns based at least in part on the status of the at least one network performance criterion; and

performing at least one speculative read to pre-fetch additional data based at least in part on the selected access pattern.

7. The computer-implemented method of claim 4, wherein determining that the status of the at least one performance criterion is verified further comprises:

determining that at least one network path between at least one data volume storing the additional data and the computing device has a threshold amount of available bandwidth.

8. The computer-implemented method of claim 4, wherein determining that the status of the at least one performance criterion is verified further comprises:

determining that the computing device has enough memory to store the additional data to be pre-fetched.

9. The computer-implemented method of claim 4, further comprising:

associating the at least one known access pattern with a user operating the computing device, wherein the at least one known access pattern is able to be applied to at least one subsequent read request that is initiated by the user.

10. The computer-implemented method of claim 4, further comprising:

associating the at least one known access pattern with an application running on the computing device, wherein the at least one known access pattern is able to be applied to at least one subsequent read request that is initiated by the application.

11. The computer-implemented method of claim 4, wherein determining that a data access pattern corresponding to the read request matches at least one known access pattern further comprises:

determining that a user operating the computing device matches a user associated with the at least one known access pattern.

12. The computer-implemented method of claim 4, wherein determining that a data access pattern corresponding to the read request matches at least one known access pattern further comprises:

determining that an application running on the computing device matches an application associated with the at least one known access pattern.

13. The computer-implemented method of claim 4, wherein determining that a data access pattern corresponding to the read request matches at least one known access pattern further comprises:

determining that a device identifier referencing the computing device matches a device identifier associated with the at least one known access pattern.

14. The computer-implemented method of claim 4, wherein the at least one known access pattern describes at least a particular order of in which blocks of data are accessed.

15. A system, comprising:

at least one processor; and

memory including instructions that, when executed by the at least one processor, cause the system to perform the operations of;

obtaining data to satisfy a read request received from a source;

determining that information associated with the read request matches at least one access pattern associated with the source, the at least one access pattern having been determined based at least in part on evaluating previously received read requests;

determining that a status of at least one performance condition associated with the at least one access pattern satisfies a threshold before the at least one access pattern is able to be applied to the read request; and

obtaining, based at least in part on the at least one access pattern, additional data that is likely to be requested by the source in a subsequent read request.

16. The system of claim 15, wherein the operations further comprise:

determining to store the additional data to temporary storage based at least in part on the status of the at least one performance condition;

receiving a subsequent read request from the source for the additional data; and

obtaining the additional data to satisfy the subsequent read request from the temporary storage.

17. The system of claim 15, wherein the operations further comprise:

obtaining the additional data before the additional data is requested by the source; and

sending the additional data to the source.

18. The system of claim 15, wherein the operations of determining the status of at least one performance condition associated with the at least one access pattern satisfies the threshold further comprise:

verifying at least one of a bandwidth, latency, or throughput of a network containing a data store in which the additional data is stored.

19. The system of claim 15, wherein the operations of determining the status of at least one performance condition associated with the at least one access pattern satisfies the threshold further comprise:

determining that a count of I/O operations performed by the system is within a threshold rate of I/O operations for a period of time.