US20010000083A1 - Shared cache parsing and pre-fetch - Google Patents

Abstract

The invention provides a method and system for reducing latency in reviewing and presenting web documents to the user. A cache coupled to one or more web clients request web documents from web servers on behalf of those web clients and communicates those web documents to the web clients for display. The cache parses the web documents as they are received from the web server, identifies references to any embedded objects, and determines if those embedded objects are already maintained in the cache. If those embedded objects are not in the cache, the cache automatically pre-fetches those embedded objects from the web server without need for a command from the web client. The cache maintains a two-level memory including primary memory and secondary mass storage. At the time the web document is received, the cache determines if any embedded objects are maintained in the cache but are not in primary memory. If those embedded objects are not in primary memory, the cache automatically pre-fetches those embedded objects from secondary mass storage to primary memory without need for a request from the web client. Web documents maintained in the cache are periodically refreshed, so as to assure those web documents are not stale. The invention is applied both to original requests to communicate web documents and their embedded objects from the web server to the web client, and to refresh requests to communicate web documents and their embedded objects from the web server to the cache.

Description

BACKGROUND OF THE INVENTION
• 1. 1. Field of the Invention
• 2. This invention relates to caches.
• 3. 2. Related Art
• 4. When presenting and reviewing data using a web browser or web client, that is, a client program for the web (the “World Wide Web”) such as Netscape Corporation's “Navigator” product or Microsoft Corporation's “Internet Explorer” product, it is desirable to present the data with as little delay as possible. If the user of the web client has to wait too long for the data to be displayed, this can lead to user dissatisfaction.
• 5. Some web clients access the web using a proxy cache, that is, a device for requesting web documents on behalf of the web client and for caching those web documents for possible later use. The proxy cache acts to reduce the amount of communication bandwidth used between the web client and web servers. A proxy cache can be shared by more than one web client, in which case it acts to reduce the total amount of communication bandwidth used between all of its web clients and web servers. One advantage of the proxy cache is that web documents stored in cache can be accessed more quickly than re-requesting those web documents from their originating web server.
• 6. One problem in the art is that a document requested by the web client (a “web document”) can include, in addition to text and directions for display, embedded objects which are to be displayed with the web document. Embedded objects can include pictures, such as data in GIF or JPEG format, other multimedia data, such as animation, audio (such as streaming audio), movies, video (such as streaming video), program fragments, such as Java, Javascript, or ActiveX, or other web documents, such as when using frames. The web client must parse the web document to determine the embedded objects, and then request the embedded objects from the web server.
• 7. While using a proxy cache ameliorates this problem somewhat, the problem persists. If there are many embedded objects in the web document, it can take substantial time to identify, request, communicate, and display all of them. Parsing and requesting embedded objects by the web client is serial, and most web clients are set to request only a small number of embedded objects at a time. Web clients requesting embedded objects perform this task in parallel with rendering those objects for display, further slowing operation.
• 8. Moreover, known proxy caches use a two-level memory having both primary memory and secondary mass storage. Even those embedded objects already maintained in the cache, and thus accessible by the web client without requesting them from the web server, might have been dropped out of the primary memory to secondary mass storage, possibly delaying communication of the embedded objects from the proxy cache to the web client and thus delaying display of those embedded objects to the user.
• 9. Accordingly, it would be advantageous to provide a method and system for reducing latency in reviewing and presenting web documents to the user. This advantage is achieved in a system in which web documents are parsed by a cache for references to embedded objects, and those embedded objects are pre-fetched from the web server or pre-loaded from secondary mass storage by the cache before they are requested by the web client.
• 10. Teachings of the art include (1) the known principle of computer science that devices work better when they are indifferent to the nature of the data they process, and (2) the known principle of client-server systems that it is advantageous to assign processing-intensive tasks to clients, rather than to servers, whenever possible. The invention is counter to the first teaching, as the cache alters its behavior in response to its parsing of the web documents it receives for communication to the client. The invention is also counter to the second teaching, as the cache takes on the additional processing tasks of parsing the web document for embedded objects and, if necessary, independently requesting those embedded objects from the web server.
SUMMARY OF THE INVENTION
• 11. The invention provides a method and system for reducing latency in reviewing and presenting web documents to the user. A cache coupled to one or more web clients request web documents from web servers on behalf of those web clients and communicates those web documents to the web clients for display. The cache parses the web documents as they are received from the web server, identifies references to any embedded objects, and determines if those embedded objects are already maintained in the cache. If those embedded objects are not in the cache, the cache automatically pre-fetches those embedded objects from the web server without need for a command from the web client.
• 12. In a preferred embodiment, the cache maintains a two-level memory including primary memory and secondary mass storage. At the time the web document is received, the cache determines if any embedded objects are maintained in the cache but are not in primary memory. If those embedded objects are not in primary memory, the cache automatically pre-loads those embedded objects from secondary mass storage to primary memory without need for a request from the web client.
• 13. In a preferred embodiment, web documents maintained in the cache are periodically refreshed, so as to assure those web documents are not “stale” (changed at the web server but not at the cache). The invention is applied both to original requests to communicate web documents and their embedded objects from the web server to the web client, and to refresh requests to communicate web documents and their embedded objects from the web server to the cache.
BRIEF DESCRIPTION OF THE DRAWINGS
• 14.FIG. 1 shows a block diagram of a system for shared cache parsing and pre-fetch.
• 15.FIG. 2 shows a flow diagram of a method for shared cache parsing and pre-fetch.
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT
• 16. In the following description, a preferred embodiment of the invention is described with regard to preferred process steps and data structures. Those skilled in the art would recognize after perusal of this application that embodiments of the invention can be implemented using one or more general purpose processors or special purpose processors or other circuits adapted to particular process steps and data structures described herein, and that implementation of the process steps and data structures described herein would not require undue experimentation or further invention.
• 17. Inventions disclosed herein can be used in conjunction with inventions disclosed in one or more of the following patent applications:
• 18. Provisional U.S. Application 60/048,986, filed Jun. 9, 1997, in the name of inventors Michael Malcolm and Robert Zarnke, titled “Network Object Cache Engine”, assigned to CacheFlow, Inc., attorney docket number CASH-001.
• 19. U.S. application Ser. No. 08/959,058, filed this same day, in the name of inventors Michael Malcolm and Ian Telford, titled “Adaptive Active Cache Refresh”, assigned to CacheFlow, Inc., attorney docket number CASH-003.
• 20. These applications are referred to herein as the “Cache Disclosures,” and are hereby incorporated by reference as if fully set forth herein.
• 21. System Elements
• 22.FIG. 1 shows a block diagram of a system for shared cache parsing and pre-fetch.
• 23. A system100 includes acache110, at least one client device120, and at least oneserver device130. Each client device120 is coupled to thecache110 using a client communication path121, such as a dial-up connection, a LAN (local area network), a WAN (wide area network), or some combination thereof. Similarly, eachserver device130 is also coupled to thecache110 using aserver communication path131, such as a dial-up connection, a LAN (local area network), a WAN (wide area network), or some combination thereof. In a preferred embodiment, the client communication path121 includes a LAN, while theserver communication path131 includes a network of networks such as an internet or intranet.
• 24. As used herein, the terms “client” and “server” refer to a relationship between the client or server and thecache110, not necessarily to particular physical devices. As used herein, one “client device”120 or one “server device”130 can comprise any of the following: (a) a single physical device capable of executing software which bears a client or server relationship to thecache110; (b) a portion of a physical device, such as a software process or set of software processes capable of executing on one hardware device, which portion of the physical device bears a client or server relationship to thecache110; or (c) a plurality of physical devices, or portions thereof, capable of cooperating to form a logical entity which bears a client or server relationship to thecache110. The phrases “client device”120 and “server device”130 refer to such logical entities and not necessarily to particular individual physical devices.
• 25. Theserver device130 includes memory or storage132 having aweb document133, theweb document133 including references to at least one embeddedobject134. In a preferred embodiment, theweb document133 can include text and directions for display. The embeddedobject134 can include pictures, such as data in GIF or JPEG format, other multimedia data, such as animation, audio (such as streaming audio), movies, video (such as streaming video), program fragments, such as Java, Javascript, or ActiveX, or other web documents, such as when using frames.
• 26. Thecache110 includes a processor111, program anddata memory112, andmass storage113. Thecache110 maintains a first set of web objects114 in thememory112 and a second set of web objects114 in thestorage113. (Web objects114 can compriseweb documents133 or embeddedobjects134 or both.)
• 27. In a preferred embodiment, thecache110 includes a cache device such as described in the Cache Disclosures defined herein, hereby incorporated by reference as if fully set forth therein.
• 28. Thecache110 receives requests from the client device120 for a web object114 and determines if that web object114 is present at thecache110, either in thememory112 or in thestorage113. If the web object114 is present in thememory112, thecache110 transmits the web object114 to the client device120 using the client communication path121. If the web object114 is present in thestorage113 but not in thememory112, thecache110 loads the web object114 into thememory112 from thestorage113, and proceeds as in the case when the web object114 was originally present in thememory112. If the web object114 is not present in either thememory112 or thestorage113, thecache110 retrieves the web object114 from theappropriate server device130, places the web object114 in thememory112 and thestorage113, and proceeds as in the case when the web object114 was originally present in thememory112.
• 29. Due to the principle of locality of reference, it is expected that thecache110 will achieve a substantial “hit rate,” in which many requests from the client device120 for web objects114 will be for those web objects114 already maintained by thecache110, reducing the need for requests to theserver device130 using theserver communication path131.
• 30. Thecache110 parses each web object114 as it is received from theserver device130, separately and in parallel to any web client program operating at the client device120. If the web object114 is aweb document133 that includes at least one reference to embeddedobjects134, thecache110 identifies those references and those embeddedobjects134, and determines if those embeddedobjects134 are already maintained in thecache110, either in thememory112 or thestorage113.
• 31. If those embeddedobjects134 are not in thecache110 at all, thecache110 automatically, without need for a command from the web client, requests those embeddedobjects134 from theserver device130.
• 32. Thecache110 has a relatively numerous set of connections to theserver communication path131, and so is able to request a relatively numerous set of embeddedobjects134 in parallel from theserver device130. Moreover, thecache110 parses theweb document133 and requests embeddedobjects134 in parallel with the web client at the client device120 also parsing theweb document133 and requesting embeddedobjects134. The embedded objects134 are available to thecache110, and thus to the client device120, much more quickly.
• 33. If those embeddedobjects134 are maintained in thecache110, but they are in thestorage113 and not in thememory112, thecache110 automatically, without need for a command from the web client, loads those embeddedobjects134 from thestorage113 into thememory112.
• 34. In a preferred embodiment, those web objects114 maintained in thecache110 are periodically refreshed, so as to assure those web objects114 are not “stale” (changed at theserver device130 but not at the cache110). To refresh web objects114, thecache110 selects one web object114 for refresh and transmits a request to theserver device130 for that web object114. Theserver device130 can respond with a copy of the web object114, or can respond with a message that the web object114 has not changed since the most recent copy of the web object114 was placed in thecache110. If the web object114 has in fact changed, thecache110 proceeds as in the case when a client device120 requested a new web object114 not maintained in thecache110 at all. If the web object114 has in fact not changed, thecache110 updates its information on the relative freshness of the web object114, as further described in the Cache Disclosures.
• 35. Method of Operation
• 36.FIG. 2 shows a flow diagram of a method for shared cache parsing and pre-fetch.
• 37. Amethod200 includes a set of flow points to be noted, and steps to be executed, cooperatively by the system100, including thecache110, the client device120, and theserver device130.
• 38. At a flow point210, the client device120 is ready to request aweb document133 from theserver device130. For example, theweb document133 can comprise an HTML page having a set of embeddedobjects134.
• 39. At a step221, the client device120 transmits a request for theweb document133, using the client communication path121, to thecache110.
• 40. At astep222, thecache110 determines if thatweb document133 is located in thememory112 at thecache110. If so, thecache110 proceeds with thestep225. Otherwise, thecache110 proceeds with thestep223.
• 41. At astep223, thecache110 determines if thatweb document133 is located in thestorage113 at the cache110 (but not in the memory112). If so, thecache110 loads theweb document133 from thestorage113 into thememory112, and proceeds with thestep225. Otherwise, thecache110 proceeds with thestep224.
• 42. At astep224, thecache110 transmits a request to theserver device130 for theweb document133. Theserver device130 receives the request and transmits theweb document133 to thecache110. Thecache110 stores theweb document133 in thememory112 and thestorage113 and proceeds with thestep225.
• 43. At astep225, thecache110 transmits theweb document133 to the client device120 for display. In parallel, thecache110 parses theweb document133 and determines if there are any references to embeddedobjects134. If not, thecache110 proceeds with the flow point230. Otherwise, the cache proceeds with thestep226.
• 44. At astep226, thecache110 identifies the embeddeddocuments134 and repeats thesteps222 through226 inclusive (including repeating this step226) for each such embeddeddocument134.Web documents133 in “frame” format can refer to embeddeddocuments134 that are themselvesweb documents133 and themselves refer to embeddeddocuments134, and so on. There is no prospect of an infinite loop ifweb document133 is self-referential because thecache110 will simply discover at the second reference that theweb document133 is already maintained in thecache110.
• 45. At a flow point230, theweb document133 and all its embeddedobjects134 have been transmitted to the client device120 for display.
• 46. When thecache110 refreshes a web object114, thecache110 performs thesteps222 through226 inclusive (including repeating the step226) for the web object114 and for each identified embeddedobject134 associated with the web object114.
• 47. Alternative Embodiments
• 48. Although preferred embodiments are disclosed herein, many variations are possible which remain within the concept, scope, and spirit of the invention, and these variations would become clear to those skilled in the art after perusal of this application.

Claims (9)

What is claimed is:

1. A method, including the steps of

receiving web documents at a shared cache from a web server or mass storage for communicating said web documents to a web client for display;

parsing said web documents for references to embedded objects;

determining if said embedded objects are already maintained in said shared cache; and

conditionally pre-fetching said embedded objects from said web server in response to said step of determining, without need for a command from said web client.

2. A method as in

claim 1

, including the steps of

maintaining at said shared cache a two-level memory including primary memory and secondary mass storage;

locating said embedded objects in said shared cache but not in said primary memory;

conditionally pre-loading said embedded objects from said secondary mass storage into said primary memory in response to said step of locating, without need for a request from said web client.

3. A method as in

claim 1

, wherein said web documents include refresh copies of said web documents requested by said shared cache from said web server.

4. A system, including

a shared cache coupled to at least one web server and coupled to a plurality of web clients, said shared cache being capable of receiving requests for web documents from said web clients, requesting said web documents from said web server or mass storage, receiving said web documents from said web server or mass storage, and communicating said web documents to said web clients;

said shared cache including

means for parsing said web documents for references to embedded objects;

means for determining if said embedded objects are already maintained in said shared cache; and

means for conditionally pre-fetching said embedded objects from said web server in response to said means for determining, without need for a command from said web client.

5. A system as in

claim 4

, including

a two-level memory at said shared cache, said two-level memory including primary memory and secondary mass storage;

means for locating said embedded objects in said shared cache but not in said primary memory; and

means for conditionally pre-loading said embedded objects from said secondary mass storage into said primary memory in response to said means for locating, without need for a request from said web client.

6. A system as in

claim 4

, wherein said web documents include refresh copies of said web documents requested by said shared cache from said web server.

7. A shared cache, including

means for parsing said web documents, said web documents being received from a web server or from mass storage, for references to embedded objects;

means for determining if said embedded objects are already maintained in said shared cache; and

means for conditionally pre-fetching said embedded objects from said web server in response to said means for determining, without need for a command from said web client.

8. A cache as in

claim 7

, including

a two-level memory at said shared cache, said two-level memory including primary memory and secondary mass storage;

means for locating said embedded objects in said shared cache but not in said primary memory; and

means for conditionally pre-loading said embedded objects from said secondary mass storage into said primary memory in response to said means for locating, without need for a request from said web client.

9. A cache as in

claim 7

, wherein said web documents include refresh copies of said web documents requested by said shared cache from said web server.

Images