System and method of accessing a document efficiently through multi-tier web caching

• US 7,587,398 B1
• Filed: 06/30/2004
• Issued: 09/08/2009
• Est. Priority Date: 06/30/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Ghemawat, Sanjay, Fredricksen, Eric Russell, Schneider, Fritz John, Dean, Jeffrey Adgate
• Primary Examiner(s): Rones; Charles
• Assistant Examiner(s): CAO, PHUONG THAO
• Application Number:
  US10/882,794
• Time in Patent Office: 1,896 Days
• Field of Search: 707/10, 707/2, 707/3, 707/203
• US Class Current: 1/1
• CPC Class Codes: G06F 16/957 Browsing optimisation, e.g. caching or content distillation
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99953 Recoverability

Abstract

The present invention is directed to a client-server network system implementing a multi-tier caching strategy for a user to access a document efficiently. The system comprises a client cache assistant serving as proxy for web browsers, a remote cache server managing user-requested documents and a search engine repository storing a huge number of documents as a backup for the remote cache server. Upon receipt of a document request, the client cache assistant examines its client cache to identify the requested document. If not successful, the remote cache server then identifies a copy of the requested document in its own cache and transmits a content difference between the two copies to the client cache assistant. If the server copy is still not fresh or not found, the remote cache server seeks another copy of the requested document from the search engine repository and transmits another content difference to the client cache assistant. The client cache assistant merges the content differences and the original copy into a new copy of the requested document.

Claims

1. A method for returning a document to a requesting user at a client, comprising:

on a server system having one or more processors and memory storing programs executed by the one or more processors;

receiving from a client a request comprising a URL of a requested document, a first value that identifies a first content of the requested document, wherein the first value identifies a stale version of the requested document that is stored at the client, the first value calculated as a function of the first content, and a second value, the second value calculated as a function of a second document content of another document that has a URL distinct from the URL of the requested document;

identifying a current content of the requested document using the URL of the requested document; and

transmitting a response to the client;

wherein the method includes;

when a first condition is satisfied;

identifying the first content of the requested document using the first value,

generating a first content difference between the current and first contents if the current content is different from the first content, and

transmitting a first response to the client, the first response comprising the first content difference, wherein the first content difference is to be combined with the first content of the requested document at the client to generate the current content of the requested document and the generated current content of the requested document is to be provided to a requesting user at the client; and

when a second condition is satisfied;

identifying the second document content using the second value,

generating a second content difference between the current and second document contents if the current content is different from the second document content, and

transmitting a second response to the client, the second response comprising the second content difference, wherein the second content difference is to be combined with the second document content at the client to generate the current content of the requested document and the generated current content of the requested document is to be provided to the requesting user at the client; and

wherein the first condition is satisfied when the first content is found and the second condition is satisfied when the first content is not found.

2. The method of claim 1, wherein the second document is a last page visited at the host indicated in the URL of the requested document.

3. The method of claim 1, wherein the second document is a home page of the host indicated in the URL of the requested document.

4. The method of claim 1, wherein the request further comprises a third value, the third value calculated as a function of a third document content, and

when a third condition is satisfied:

identifying the third document content using the third value,

generating a third content difference between the current and third document contents if the current content is different from the third document content, and

transmitting a third response to the client, the third response comprising the third content difference, and

wherein the third condition is satisfied when the first content is not found and the second document content is not found.

5. The method of claim 4, wherein the third document is a home page of the host indicated in the URL of the requested document.

6. The method of claim 1, wherein the first value is a content fingerprint of the first content.

7. The method of claim 1, wherein the second value is a content fingerprint of the second document content.

8. The method of claim 1, further comprising caching a plurality of documents and associating information about the plurality of documents.

9. The method of claim 8, wherein the associated information comprises at least two distinct data structures, a first data structure that stores a mapping from a respective URL fingerprint to a corresponding document content fingerprint and a set of content freshness parameters, and a second data structure that stores a mapping from the respective document content fingerprint to a corresponding copy of a respective document content.

10. A computer readable medium storing one or more computer programs, the one or more computer programs including instructions that, when executed by a computer system having one or more processors and memory, cause the computer system to:

receive from a client a request comprising a URL of a requested document, a first value that identifies a first content of the requested document, wherein the first value identifies a stale version of the requested document that is stored at the client, the first value calculated as a function of the first content, and a second value, the second value calculated as a function of a second document content of another document that has a URL distinct from the URL of the requested document;

identify a current content of the requested document using the URL of the requested document; and

transmit a response to the client;

when a first condition is satisfied,

identify the first content of the requested document using the first value,

generate a first content difference between the current and first contents if the current content is different from the first content, and

transmit a first response to the client, the first response comprising the first content difference, wherein the first content difference is to be combined with the first content of the requested document at the client to generate the current content of the requested document and the generated current content of the requested document is to be provided to a requesting user at the client; and

when a second condition is satisfied,

identify the second document content using the second value,

generate a second content difference between the current and second document contents if the current content is different from the second document content, and

transmit a second response to the client, the second response comprising the second content difference, wherein the second content difference is to be combined with the second document content at the client to generate the current content of the requested document and the generated current content of the requested document is to be provided to the requesting user at the client; and

wherein the first condition is satisfied when the first content is found and the second condition is satisfied when the first content is not found.

11. The computer readable medium of claim 10, wherein the second document is a last page visited at the host indicated in the URL of the requested document.

12. The computer readable medium of claim 10, wherein the second document is a home page of the host indicated in the URL of the requested document.

13. The computer readable medium of claim 10, wherein the request further comprises a third value, the third value calculated as a function of a third document content, and

the one or more computer programs include instructions that, when executed by the computer system, cause the computer system, when a third condition is satisfied, to:

identify the third document content using the third value,

generate a third content difference between the current and third document contents if the current content is different from the third document content, and

transmit a third response to the client, the third response comprising the third content difference, and

wherein the third condition is satisfied when the first content is not found and the second document content is not found.

14. The computer readable medium of claim 13, wherein the third document is a home page of the host indicated in the URL of the requested document.

15. The computer readable medium of claim 10, wherein the first value is a content fingerprint of the first content.

16. The computer readable medium of claim 10, wherein the second value is a content fingerprint of the second document content.

17. The computer readable medium of claim 10, further comprising instructions for caching a plurality of documents and instructions for associating information about the plurality of documents.

18. The computer readable medium of claim 17, wherein the associated information comprises at least two distinct data structures, a first data structure that stores a mapping from a respective URL fingerprint to a corresponding document content fingerprint and a set of content freshness parameters, and a second data structure that stores a mapping from the respective document content fingerprint to a corresponding copy of a respective document content.