Precomputation of web documents

[0001] This application claims the benefit of U.S. Provisional Application No. 60/390,651, filed Jun. 20, 2002.

[0002] This patent relates generally to accelerating the serving of content, and/or reducing delays, in a networked computer environment. More specifically, this patent relates to serving generated web documents by precomputing certain dynamic content therein, without compromising freshness of the content.

[0003] It is commonly required to serve fresh content to web users, for example, in the form of web pages that are dynamically generated by formatting the latest content retrieved from a database. Examples of such content might include stock quotes, financial transaction data, price lists, news headlines, computer code, and still more. For instance, consider the case where a user visits an online bank. The user logs in, and after looking at his overall position, he might choose to look at his last ten transactions. The bank's server must retrieve the relevant content from its databases or other memory and construct a formatted response for the user to view. Since such archived content is typically (partly or wholly) unique to the user, even with modern database technology, a bank with millions of users would typically incur many seconds of delay in executing the database queries. Indeed, it is typical of each such query to take five seconds or more, even when the servers and the network are lightly loaded. Such delays are a result of latencies in the back-end infrastructure of the networked system, and are inherent in any large-scale system. As a result, users see poor performance.

[0004] In order to improve performance, caches are often installed in tandem with the content server. A cache is server or other mechanism that stores and provides content for re-use. By combining a server and a cache, static content that does not change with time can be offloaded to the cache, freeing up the content server to focus primarily on dynamic content. However, since dynamic content (such as transactional and personalized information) changes frequently and across users, it cannot readily be cached and re-used.

[0005] One known technique for improving performance of dynamic content involves pre-fetching of web content. For example, pre-fetching has been offered in a commercial implementation by Fireclick (see www.fireclick.com). In Fireclick's implementation, as soon as a user visits a web site, the web server downloads to the user's browser a small piece of software that contains the most popular browsing patterns at the web site. The software is typically a Java applet that executes on the browser in a transparent fashion. The applet downloads popular web content to the user's browser, in anticipation of the user's next request. The downloaded content may be that which other users most frequently download from the page which is currently displayed on the user's browser. For example, if the front page of a newspaper is being displayed, the stories behind the top headlines might also be downloaded. However, because such content has no guaranteed relation to the individual user's actual browsing habits, the network resources connecting the user's browser to the server, and the memory at the user's browser, are loaded with content that the user may not request.

[0010] We disclose techniques for anticipating a user's request for documents or other content from a server (typically via a URL), precomputing the anticipated content, and caching the precomputed information at a cache in proximity to the content server. The cache stores the response to the anticipated request, until the user requests the same content. The anticipated requests can be precomputed based on triggers reflecting users' historical access patterns.

[0011] The content can be computed on a user-by-user basis—rather than on a “most popular” basis across all users—on the basis of that user's history. The user's history can be dynamic, allowing the system can track the subsequent URLs most commonly requested by the user, from any given starting URL and/or at any given point in time.

[0012] We also disclose techniques for managing the freshness of the cached precomputed content. Thus, in another exemplary aspect, the cache can be configured so that precomputed content responsive to an anticipated URL request is stored only while such content is valid. Validity can be enforced by a variety of schemes such as a predetermined freshness interval set by the system administrator, or by the use of configurable triggers that allow cached content to be invalidated by other events.

[0013] Depending on configuration and implementation needs, the proposed system can (but need not) be deployed in a transparent manner, without necessarily requiring that changes be made to already deployed content servers, content, networks and/or browsers.

[0014] These and other aspects are described in greater detail below.

I. Operating Environment

[0015] FIG. 1 illustrates an exemplary environment including a user browser 110 connected over a network 120 to, and accessing content from, a content server 130. In an exemplary embodiment, the proposed system is deployed as a transparent proxy server 200 located on the network 120 in front of the content server 130. When the user 110 requests content from the content server 130, the request is first received by the proxy server 200, processed at the proxy server, and then sent to the content server 130. The proxy server 200 and/or content server 130 provide a response, which is processed and then returned to the user.

[0016] FIG. 2 illustrates an exemplary overview of proxy server 200 in schematic form. The proxy server may be a stand-alone server, or it may be an integral part of content server 130. If implemented as a stand-alone front end, the proxy server 200 can be deployed in a transparent manner, avoiding the necessity of making changes to already deployed content servers, content, networks and/or browsers.

[0017] In an exemplary embodiment, the functionality of proxy server 200 is deployed in updating, response, and caching module or subsystem 210 (or vice versa), which communicates with user browser 110 and content server 130. Module 210 (and other system components) may be implemented in an operating environment comprising software installed on a computer, in hardware, or in a combination of software and hardware. The software and/or hardware would typically include some type of computer-readable media which can store data and logic instructions that are accessible by the computer or the processing logic within the hardware. Such media might include, without limitation, hard disks, floppy discs, CDs, digital video discs, magnetic cassettes, tape cartridges, flash memory cards, random access memories (RAMs), read only memories (ROMs), and the like.

[0018] As a matter of convenience, the techniques of this patent will be disclosed in the exemplary context of a web-based system in which the user accesses content identified by URLs from a browser. However, those skilled in the art will readily appreciate that other user access devices, and content identifiers, may also be used. For example, instead of URLs, content may also be identified via other unique identifiers of an object, for example and without limitation, identifiers that identify the object as an entity per se, as opposed to a mere attribute (e.g., a web address) of an object.

[0019] Similarly, it should be appreciated that the disclosed techniques will operate on any networked computer, including without limitation, wireless networks, handheld devices, and personal computers. Therefore, exemplary terms such as web, browser, URL and the like should be interpreted broadly to include known substitutes and other equivalents, counterparts, and extensions thereof.

II. Proxy Server Functionality

[0020] Module 210 is in communication with a history file 230, which records the user's browsing habits. History file 230 may either comprise a stand-alone file specific to the proxy server, and/or a remote file located on the network and accessed by the proxy server (e.g., at the user's browser). Module 210 is also in communication with a cache 220, a “trigger class” file 240 and an “anticipation class” file 250. The operation of module 210 will be described in greater detail below with respect to FIGS. 3 and 4.

[0021] FIG. 3 schematically illustrates the content of an exemplary trigger class file 240 and anticipation class file 250. Although these have been shown as separate entities for the sake of illustration, they can also be combined into a single memory or database, as a matter of implementation choice.

1. Trigger and Anticipation Classes

[0022] The trigger class file 240 represents those URLs that are known or believed likely to be associated with subsequent requests for other URLs. The trigger class URLs may be determined in any desired fashion. For example, they can be statically specified by a system administrator and/or updated dynamically depending on the actual web access characteristics of the relevant user(s).

[0023] Each URL in the trigger class has an associated set of URLs representing known or otherwise anticipated follow-on requests associated with the triggering URL. These other URLs are known collectively as the anticipation class for the URL in the trigger class. The anticipation class may be determined in any desired fashion. For example, they can be statically specified by a system administrator and/or updated dynamically depending on the actual web access characteristics of the relevant user(s).

2. Exemplary Trigger and Anticipation Classes

[0024] Refer now to the meta-examples shown in FIG. 3. In this exemplary embodiment, both the trigger class file and the anticipation class file are user-specific. In other embodiments, of course, such files could be specific to classes of users, or to all users generally.

[0025] In the first meta-example shown in row 1 of the chart, the entry in column 1 (the trigger class) might include a home or login URL (e.g., www.homepage.com) where the user typically begins browsing content on content server 130. The entries in column 2 (the anticipation class) might represent the top other URLs typically visited by the user from the home URL (e.g., upon login). For example, assuming that system is configured to store the top three URLs, these might include a sub-page of the content server (e.g., www.homepage.com/level_j_page), a third party page (e.g., www.thirdpartypage.com) and even non-HTML content (e.g., downloadable content accessible via ftp from ftp.homepage.com).

[0026] In another meta-example shown in row 2 of the chart, the entry in column 1 (the trigger class) might include a sub-page of the content server (e.g., www.homepage.com/level_j_page), and the entries in column 2 (the anticipation class) might represent the other URLs typically visited by the user from the triggering URL. For example, these might include a different sub-page of the content server (e.g., www.homepage.com/level_k_page), a third party page (e.g., www.thirdpartypage.com), the home page (www.homepage.com), etc.

3. Updating Trigger and Anticipation Classes

[0027] The trigger and anticipation classes would typically be updated over time to reflect the evolving browsing preferences of the user. Thus, in the first meta-example above, when a user logs into a site for the first time, both the trigger class 240 and its associated anticipation classes 250 might be empty, since there are no data for that particular user. (Alternatively, default entries could be provided from browsing habits of similar users, or from all users generally).

[0028] As the user frequents the site, the system (via module 210 and data accumulating in history file 230) could update the trigger class with those visited URLs which typically spawn other URL requests (sometimes referred to as root URLs), and also update the anticipation class for each triggering URL with the URLs most frequently accessed therefrom.

[0029] For example, suppose that the current request for a URL makes the aggregate number of requests for that URL exceed a predetermined threshold. In that case, the requested URL may replace another URL as a member of the trigger class. The threshold may be absolute (i.e., such so that all URLs requested in excess of the threshold become trigger classes) or relative (e.g., such that the top n URL requests in any given period of time become the trigger classes).

[0030] Similarly, by comparing the requested URL with one (or more) previously requested URL(s), the proxy server can determine if any existing anticipation class should be updated with the currently requested URL.

4. Caching Anticipation Classes

[0031] The URLs in the anticipation class could then be cached at the proxy server in anticipation of future requests based on the corresponding URL in the trigger class. In this manner, the system may be able to respond from its cache 220, rather than always returning to the content server 130, for commonly requested content, thereby improving response time.

5. Precomputing Documents

[0032] If the responses corresponding to the URLs in the anticipation class are not yet cached, (e.g., because they represent personalized content, other forms of dynamic content, or otherwise have not yet been computed), they can be computed as necessary prior to caching.

[0033] Known techniques in which caches simply reuse responses from prior requests are not considered precomputing. Of course, this is not to say that such techniques can not be used in conjunction with precomputing. Depending on the situation, reusing prior responses may be a useful adjunct to precomputing.

6. Improving Cache Freshness

[0034] Because the anticipated URLs may change frequently, particularly for dynamic content, another element of the anticipation class specifies a cache lifetime (or validity interval) for each URL in the anticipation class. For example, as shown in column 3 of FIG. 3, these cache lifetimes might range hours to months, or otherwise.

[0035] Depending on implementation choices, a particular cache entry could either be purged, or ignored, or independently checked for freshness, once its cache lifetime has been reached. Thus, the system can (as necessary) fall back on the content server 130 to provide fresh responses.

[0036] The foregoing illustrates the use of a predetermined freshness interval set by the system administrator. However, many other techniques for ensuring validity can also be used. For example, the cache lifetime for a particular entry could be dynamic, if based on a configurable trigger that reflects the occurrence of other events. Still other validity enforcement techniques are disclosed co-pending U.S. patent application Ser. No. 10/287,364, filed on Nov. 4, 2002, which is hereby incorporated by reference in its entirety.

7. Improving Performance Under Load

[0037] Another aspect relates to performance under load. When the content server is under heavy load, precomputing anticipated URL's will add further load to the content server, thereby affecting performance adversely. To prevent such, the proxy server can monitor the load on the content server, and prorate the amount of precomputation accordingly. Specifically, the proxy server could measure the load on the content server: (a) by comparing the response time of the content server with an absolute and predetermined desired response time; (b) by comparing a short term moving average of the content server with a long-term moving average of the response time; or (c) using still other techniques. A full description of means for measuring the load on the content server is presented in co-pending application co-pending U.S. patent application Ser. No. 10/287,364, filed on Nov. 4, 2002, which is incorporated by reference in its entirety.

8. Remote History Storage

[0038] Some or all of a user's history file, including trigger classes and/or anticipation classes, may be stored in a database. In the case there are large number of users, the latency of such a database might in itself become significant. In such case, the user's history might be stored in compressed or indexed form as a cookie in the user's browser. As a result, the user presents the proxy server with the history cookie at each request, thereby making it readily available.

III. Exemplary Process Flow

[0039] FIG. 4 illustrates an exemplary process flow illustrating use of the exemplary proxy server of FIG. 2 with the exemplary files of FIG. 3.

[0040] At step 410, the proxy server 200 receives (e.g., intercepts) a user-requested URL. At step 420, the proxy server determines whether a valid copy of the desired URL is available from cache 220. If so, at step 430, the proxy server responds with the cached copy. If not, at step 440, the proxy server forwards the user's request to the content server 440. The content server responds with the requested URL, which is returned to the user at step 450. The foregoing paragraph illustrates basic cache operation, either with or without trigger and anticipation classes.

[0041] At steps 460-480, the use of trigger and anticipation classes facilitates the cache being efficiently loaded with content that is likely to satisfy future user requests. In this sense, the proxy server may be thought of as precomputing responses to user requests.

[0042] At step 460, if the user-requested URL falls within a trigger class (i.e., in trigger class file 240), the proxy server looks up the associated anticipation class (e.g., from anticipation class file 250), obtains the URLs in the anticipation class from the content server 130, and stores them in the cache. Depending on implementation choice, the proxy server could be configured to: (1) always request and store the URLs; (2) always request the URLs but only store them if they are not already in the cache; or (3) only request and store them if they are not already in the cache. In any event, the cache is thus updated based on a current browsing session with content that is likely to be useful in a future browsing session.

[0043] In addition to updating the cache, the user's browsing activity may also be updated and/or used to update the trigger and/or anticipatory classes. For example, at step 470, the user's request for a URL could be logged into history file 230. In one exemplary embodiment, the user's overall browsing history is used to determine the trigger class and associated anticipation classes. Thus, the updated browsing history is processed to determine any necessary changes in the URLs constituting the trigger class and anticipation classes, as described above in Section II.3.

[0044] When the user finishes accessing the current URL, and requests another URL, the process of FIG. 4 is repeated with the new URL. Depending on configuration choice, this could be done every time, or intermittently. If intermittently, suitable criteria for re-performing the process of FIG. 4 could include exceeding a threshold time, frequency, or other characteristic of the access session, or still other criteria specified according to a particular system configuration.