Speculative reads

• US 8,539,163 B1
• Filed: 12/17/2010
• Issued: 09/17/2013
• 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 E., Certain, Tate Andrew, Maniscalco, Nicholas J.
• Primary Examiner(s): Bertram, Ryan
• Application Number:
  US12/972,187
• Time in Patent Office: 1,005 Days
• Field of Search: 711/137, 711/204, 711/213, 709202-203, 709/219
• US Class Current: 711/137
• 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/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 of performing speculative read requests, comprising:

under control of one or more computer systems configured with executable instructions,

capturing information for a plurality of read requests, received over a first period of time from at least one source, to be executed against at least one data store associated with a storage entity;

analyzing the captured information to determine one or more access patterns associated with the at least one source and the at least one data store;

storing information for the one or more access patterns to persistent storage;

receiving at least one subsequent read request from the at least one source to the storage entity, the at least one subsequent read request to be executed against the at least one data store during a second period of time; and

when the at least one subsequent read request is determined by the storage entity to match the information stored for at least one of the one or more access patterns,

causing, by the storage entity, at least one speculative read request to be executed against the at least one data store based at least in part upon the matching one or more access patterns; and

temporarily storing data for the at least one speculative read request to temporary storage, the data being available such that if a subsequent read request is received for the data, the data can be provided without having to execute the subsequent read request against the at least one data store subsequent to the request,

wherein a latency value of providing the data from a speculative read request is less than a latency value of providing the data by executing a received subsequent read request against the data store for the data after the subsequent read request is received; and

wherein a location of the temporary storage is determined based at least in part upon at least one usage aspect of a network containing the data store.

2. The computer-implemented method of claim 1, further comprising:

determining at least one aspect of at least one network resource between the data store and the at least one source;

storing the data for the at least one speculative read request at a host managing the data store when the at least one aspect of the at least one network resource does not meet a minimum availability value; and

sending the data for the at least one speculative read request to a data cache between the data store and the at least one source when the at least one aspect of the at least one network resource at least meets a minimum availability value.

3. The computer-implemented method of claim 1, wherein the data for the at least one speculative read request is sent to a cache on a host machine executing an application, the application being one of the at least one source.

4. The computer-implemented method of claim 1, wherein the at least one data store includes network-attached storage.

5. A computer-implemented method of pre-fetching data, comprising:

under control of one or more computer systems configured with executable instructions,

receiving a read request from a source for data stored in a data store associated with a storage entity;

obtaining data for the read request from the data store and sending the data to the source;

comparing, at the storage entity, information associated with the read request against at least one access pattern persistently stored for at least one of the source or the data store, the at least one access pattern being determined based at least in part upon prior read requests; and

performing, under direction of the storage entity, at least one speculative read to pre-fetch additional data from the data store when the information associated with the read request matches at least one access pattern, the additional data being identified using the at least one matching access pattern and a location of the data obtained for the read request,

wherein the additional data is stored to temporary storage such that the data can be provided to the source without having to execute a subsequent read request against the data store subsequent to receiving the subsequent read request; and

wherein a location of the temporary storage is determined based at least in part upon at least one usage aspect of a network containing the data store.

6. The computer-implemented method of claim 5, wherein the data store is a block data storage system.

7. The computer-implemented method of claim 5, wherein the source is at least one of a user, client, or application.

8. The computer-implemented method of claim 5, wherein the at least one usage aspect of the network includes at least one of bandwidth, latency, throughput, and available memory.

9. The computer-implemented method of claim 5, wherein the data store further comprises at least one of network-attached storage or virtualized operating system instances utilizing attached network storage.

10. The computer-implemented method of claim 5, wherein the at least one access pattern is determined based at least in part upon prior read requests received for at least one of multiple sources and multiple data stores.

11. The computer-implemented method of claim 5, further comprising:

determining whether to perform the at least one speculative read based at least in part upon at least one network performance criterion.

12. The computer-implemented method of claim 5, wherein the read request is received for a first user, and the at least one access pattern is determined based at least in part upon prior read requests from at least one second user.

13. The computer-implemented method of claim 5, further comprising:

aggregating read request data from multiple data sources for pattern analysis.

14. The computer-implemented method of claim 5, further comprising:

concurrently testing multiple pattern recognition algorithms against data stored in the data store before selecting an access pattern that matches at least one aspect of the analyzed read requests.

15. The computer-implemented method of claim 5, wherein access pattern information is persistently stored as metadata associated with a block data storage volume.

16. The computer-implemented method of claim 5, further comprising:

storing a single record of every disk block that was read in response to a read request for use in pattern matching.

17. A computer-implemented method of pre-fetching data, comprising:

under control of one or more computer systems configured with executable instructions,

receiving information that a read request was received from a compute node for data stored in a data store associated with a storage node in a network environment;

comparing information associated with the read request against at least one access pattern persistently stored for at least one of the source or the data store, the at least one access pattern being determined based at least in part upon prior read requests; and

performing at least one speculative read to pre-fetch additional data from the data store when the information associated with the read request matches at least one access pattern, the additional data being identified using the at least one matching access pattern and a location of the data obtained for the read request,

wherein an entity other than the compute node and the storage node is operable to perform speculative reads for read requests and store the additional data to temporary storage such that the data can be provided to the compute node without having to contact the storage node; and

wherein a location of the temporary storage is determined based at least in part upon at least one usage aspect of a network containing the data store.

18. The computer-implemented method of claim 17, wherein the entity is operable to store information for the at least one access pattern in a location independent of the compute node and the storage node.

19. The computer-implemented method of claim 17, wherein the at least one access pattern is able to be shared among a plurality of compute nodes and storage nodes.

20. The computer-implemented method of claim 19, wherein the at least one access pattern is able to have a lifetime that exceeds a lifetime of any of the compute nodes and storage nodes.

21. The computer-implemented method of claim 19, wherein the at least one access pattern is able to be used to predict information for future compute nodes and storage nodes.

22. A system for pre-fetching data, comprising:

at least one processor; and

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

receive a read request from a source for data stored in a data store associated with a storage entity;

obtain data for the read request from the data store and send the data to the source;

compare, at the storage entity, information associated with the read request against at least one access pattern persistently stored for at least one of the source or the data store, the at least one access pattern being determined based at least in part upon prior read requests; and

perform, under direction of the storage entity, at least one speculative read to pre-fetch additional data from the data store when the information associated with the read request matches at least one access pattern, the additional data being identified using the at least one matching access pattern and a location of the data obtained for the read request,

wherein the additional data is stored to temporary storage such that the data can be provided to the source without having to execute a subsequent read request against the data store subsequent to receiving the subsequent read request; and

wherein a location of the temporary storage is determined based at least in part upon at least one usage aspect of a network containing the data store.

23. The system according to claim 22, wherein the data store further comprises at least one of network-attached storage or virtualized operating system instances utilizing attached network storage.

24. The system according to claim 22, wherein the at least one access pattern is determined based at least in part upon prior read requests received for at least one of multiple sources and multiple data stores.

25. A non-transitory computer-readable storage medium including instructions for pre-fetching data, the instructions when executed by a processor causing the processor to:

receive a read request from a source for data stored in a data store associated with a storage entity;

obtain data for the read request from the data store and send the data to the source;

compare, at the storage entity, information associated with the read request against at least one access pattern persistently stored for at least one of the source or the data store, the at least one access pattern being determined based at least in part upon prior read requests; and

perform, under direction of the storage entity, at least one speculative read to pre-fetch additional data from the data store when the information associated with the read request matches at least one access pattern, the additional data being identified using the at least one matching access pattern and a location of the data obtained for the read request,

wherein the additional data is stored to temporary storage such that the data can be provided to the source without having to execute a subsequent read request against the data store subsequent to receiving the subsequent read request; and

wherein a location of the temporary storage is determined based at least in part upon at least one usage aspect of a network containing the data store.

26. The non-transitory computer-readable storage medium according to claim 25, wherein the data store further comprises at least one of network-attached storage or virtualized operating system instances utilizing attached network storage.