Predictive prefetching to improve parallelization of document generation subtasks

• US 7,331,038 B1
• Filed: 07/02/2003
• Issued: 02/12/2008
• Est. Priority Date: 07/02/2003
• Status: Active Grant

• Current Assignee: Amazon Technologies, Inc. (Amazon.com, Inc.)
• Original Assignee: Amazon.com, Inc.
• Inventors: Lazier, Colin L., Snodgrass, Ryan J.
• Primary Examiner(s): Dam; Tuan
• Assistant Examiner(s): TECKLU, ISAAC TUKU
• Application Number:
  US10/612,529
• Time in Patent Office: 1,686 Days
• Field of Search: 717/106, 709/223, 709/217, 715/501.1
• US Class Current: 717/123
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: G06F 16/972 Access to data in other repository systems, e.g. legacy data or dynamic Web page generation
• CPC Class Codes: H04L 43/08 Monitoring or testing based on specific metrics, e.g. QoS, energy consumption or environmental parameters
• CPC Class Codes: H04L 67/02 based on web technology, e.g. hypertext transfer protocol [HTTP]
• CPC Class Codes: H04L 67/5681 Pre-fetching or pre-delivering data based on network characteristics

Abstract

In a system in which documents are generated dynamically in response to user requests, historical data is collected regarding data retrieval subtasks, such as service requests, that are performed to generate such documents. This data is used to predict the specific subtasks that will be performed to respond to specific document requests, such that these subtasks may be initiated preemptively at or near the outset of the associated page generation task. A subtask that would ordinarily be postponed pending the outcome of a prior subtask can therefore be performed in parallel with the prior subtask, reducing document generation times. In one embodiment, the historical data is included within, or is used to generate, a mapping table that maps document generation tasks (which may correspond to specific URLs) to the data retrieval subtasks that are frequently performed within such tasks.

Claims

1. A dynamic web page generation system, comprising:

a template processor that generates dynamic web pages according to corresponding web page templates in response to page requests from browsers, wherein the template processor or generates service requests to request content from a set of services, and uses the content returned by such services to generate the web pages according to corresponding web page templates;

a monitoring component that monitors the operation of the template processor over time and generates a mapping of page generation tasks to corresponding service calls that are made as part of such page generation tasks; and

a prefetch component that is responsive to a page request from a browser by using the mapping to identify a set of service requests to be made preemptively, such that service content that is deemed likely to be used by the template processor to generate the requested page is prefetched.

2. The dynamic web page generation system of claim 1, wherein the mapping comprises a table that maps URLs to service requests frequently used to respond to requests for such URLs.

3. The dynamic web page generation system of claim 1, wherein the monitoring component updates the mapping substantially in real time to reflect service requests actually used to generate requested web pages, such that service request predictions made by the prefetch component adapt automatically in response to page generation events.

4. The dynamic web page generation system of claim 1, wherein the prefetch and monitoring components include a prefetch client component that communicates with a prefetch service component, wherein the prefetch client component is responsive to the page request by retrieving from the prefetch service component a listing of service requests associated with the page request, as reflected in the mapping.

5. The dynamic web page generation system of claim 4, wherein the prefetch client is configured to send feedback messages to the prefetch service component identifying the service requests actually used to generate requested pages, and the prefetch service component updates the mapping to reflect the feedback messages.

6. The dynamic web page generation system of claim 1, wherein the monitoring component comprises an off-line analysis component that analyzes service request activity data collected over time to regenerate and/or update said mapping.

7. The dynamic web page generation system of claim 1, wherein the monitoring component and the prefetch component collectively operate so as to allow a second service request that is dependent upon a result of a first service request to be performed in parallel with the first service request, such that a latency caused by the chaining of dependent service requests is substantially reduced.

8. The dynamic web page generation system of claim 1, wherein the prefetch component takes service load conditions into consideration in determining whether to make the service requests preemptively, so that unnecessary service requests are reduced during heavy service load conditions.

9. The dynamic web page generation system of claim 1, wherein, by identifying service requests to be made preemptively, the prefetch component enables web page generation delays caused by service request dependencies to be reduced.

10. The dynamic web page generation system of claim 1, wherein, by identifying the set of service requests to be made preemptively, the system enables service requests that would otherwise be performed sequentially to be performed in parallel, such that a page generation time is reduced.

11. A method of dynamically generating web pages, comprising:

for at least one web page generation task, monitoring the performance of the task over time to generate a mapping reflective of frequencies with which specific data retrieval subtasks are performed as part of the web page generation task;

receiving a page request that corresponds to the web page generation task;

in response to receiving the page request, using said mapping to identify a set of data retrieval subtasks that are deemed likely to be performed as part of the web page generation task to generate a requested web page;

initiating at least some of the data retrieval subtasks in said set before they are initiated as the result of the performance of the web page generation task, to thereby prefetch data that is deemed likely to be used to generate the requested web page; and

with a template processor, generating the web page according to a template such that at least some of the prefetched data is used to generate the web page.

12. The method of claim 11, wherein the mapping comprises a table that maps web page generation tasks to respective sets of subtasks.

13. The method of claim 11, wherein the step of using the mapping to identify a set of data retrieval subtasks comprises looking up said set of data retrieval subtasks from a table that maps web page generation tasks to corresponding subtasks.

14. The method of claim 11, wherein the method comprises performing a second data retrieval subtask that is dependent upon a result of a first data retrieval subtask without waiting for the first data retrieval subtask to be completed.

15. The method of claim 11, wherein at least some of the data retrieval subtasks in said set are service requests.

16. The method of claim 11, wherein the web page generation task corresponds to a particular dynamically generated web page.

17. The method of claim 11, wherein the web page generation task corresponds to a plurality of related web pages.

18. The method of claim 11, wherein the step of initiating at least some of the data retrieval subtasks comprises selecting subtasks to perform preemptively based at least in-part on current load conditions.

19. The method of claim 11, wherein the method enables a web page generation delay caused by data retrieval subtask dependencies to be reduced.

20. The method of claim 11, wherein, by identifying the set of data retrieval subtasks that are deemed likely to be performed as part of the web page generation task, the method enables data retrieval subtasks that would otherwise be performed sequentially to be performed in parallel, such that a web page generation time is reduced.

21. The method of claim 11, wherein the template processor additionally uses non-prefetched data to generate the requested web page.

22. A dynamic document generation system, comprising:

a template processor that generates according to corresponding document templates in response to document requests from client computers, wherein the template processor performs data retrieval subtasks to retrieve data used to dynamically generate the documents;

a monitoring component that monitors the template processor over time and generates a mapping of document generation tasks to corresponding subtasks that are performed as part of such document generation tasks; and

a prefetch component that is responsive to a document request from a client computer by using the mapping to identify a set of data retrieval subtasks to be performed preemptively, such that data retrieval subtasks that are otherwise performed sequentially may be performed in parallel.

23. The dynamic document generation system of claim 22, wherein the mapping comprises a table that maps URLs to data retrieval subtasks frequently used to respond to requests for such URLs.

24. The dynamic document generation system of claim 23, wherein at least some of the data retrieval subtasks that are performed preemptively are service requests.

25. The dynamic document generation system of claim 22, wherein the monitoring component updates the mapping in real time to reflect data retrieval subtasks actually used to generate requested components.

26. The dynamic document generation system of claim 22, wherein the prefetch component comprises a prefetch client component that communicates with a prefetch service component, wherein the prefetch client component is responsive to the document request by retrieving from the prefetch service component a listing of data retrieval subtasks that are deemed likely to be used to respond to the document request, as reflected in the mapping.

27. The dynamic document generation system of claim 22, wherein the monitoring component comprises a prefetch client component that communicates with a prefetch service component, wherein the prefetch client component is configured to send feedback messages to the prefetch service component identifying the data retrieval subtasks actually used to generate requested documents, and the prefetch service component updates the mapping to reflect the feedback messages.

28. The dynamic document generation system of claim 22, wherein the monitoring component comprises an off-line analysis component that analyzes task activity data collected over time to generate and/or update said mapping.

29. The dynamic document generation system of claim 22, wherein the prefetch component determines whether to perform a data retrieval subtask preemptively based at least in part on current load conditions.

30. The dynamic document generation system of claim 22, wherein, by identifying data retrieval subtasks to be performed preemptively, the prefetch component causes document generation delays caused by data retrieval subtask dependencies to be reduced.

31. The dynamic document generation system of claim 22, wherein, by identifying the set of data retrieval subtasks to be performed preemptively, the system causes data retrieval subtasks that would otherwise be performed sequentially to be performed in parallel, such that a document generation time is reduced.