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

• US 7,565,423 B1
• Filed: 06/30/2004
• Issued: 07/21/2009
• Est. Priority Date: 06/30/2004
• Status: Active Grant

• Current Assignee: Google LLC (Alphabet Inc.)
• Original Assignee: Google Inc. (Alphabet Inc.)
• Inventors: Fredricksen, Eric Russell
• Primary Examiner(s): Jacobs; Lashonda T
• Application Number:
  US10/882,792
• Time in Patent Office: 1,847 Days
• Field of Search: 709/217, 709/219, 709/220, 709/223, 709/224, 709/229, 711/118, 711/119, 711/216
• US Class Current: 709/223
• CPC Class Codes: H04L 61/4511 using domain name system [DNS]
• CPC Class Codes: H04L 61/58 Caching of addresses or names
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching
• CPC Class Codes: H04L 69/28 Timers or timing mechanisms used in protocols

Abstract

The present invention is directed to a system and method of performing a lookup, self-refreshing and prefetching against a DNS provider that includes a DNS cache and a DNS master. The DNS cache includes a set of address records which are presumptively fresh and the DNS master includes another set of address records which may be updated if their respective IP addresses are not deemed fresh or identified for update based on other factors. A hostname resolution request is first processed by the DNS cache and then by the DNS master to identify a valid IP address for a hostname. If no valid IP address is found, the DNS master retrieves a new IP address for the hostname from a third-party DNS server and then updates the addresses records in the DNS cache and master with the new IP address. Entries in the DNS master are updated from time to time increasing the likelihood that fresh addresses are predominately present and to update the DNS cache.

Claims

1. A system for providing IP addresses, comprising:

at a server;

a master cache containing;

a first plurality of first address records, each of the first address records including a hostname, an associated IP address, and freshness parameters;

a second cache containing a second plurality of second address records, wherein a respective second address record includes the hostname and the associated IP address that is included in a respective first address record; and

instructions, which when executed by the server, cause the server to obtain an updated associated IP address for the hostname in only the master cache when a first condition is satisfied and to update the corresponding entries in the master cache and the second cache when a second condition is satisfied.

2. The system of claim 1, further comprising satisfying the first condition when the associated IP address for the hostname in the master cache is no longer valid and satisfying the second condition when the updated associated IP address is different from the associated IP address.

3. A method of updating IP address caches, comprising:

at a server;

identifying a first address record in a master cache which satisfies a first condition, the first address record associating a hostname with an IP address and including freshness parameters;

obtaining from a hostname resolution system an updated IP address associated with the hostname when the first condition is satisfied;

updating only the first address record with the updated IP address when the first condition is satisfied; and

updating the first address record and a second address record in a second cache with the updated IP address when the second condition is satisfied, the second address record including the hostname and the updated IP address that is included in the first address record.

4. The method of claim 3, further comprising determining whether the first condition is satisfied by examining the freshness parameters associated with the IP address.

5. The method of claim 4, further comprising satisfying the first condition when the IP address is stale.

6. The method of claim 4, further comprising satisfying the first condition if the IP address will become stale within a predetermined time period.

7. The method of claim 3, further comprising satisfying the second condition when the IP address is different from the updated IP address.

8. A method of responding to an IP resolution request, comprising:

at a server;

receiving the IP resolution request, the IP resolution request including a hostname;

in response to receiving the IP resolution request;

identifying a first address record in a first cache matching the IP resolution request, the first address record including an IP address and the hostname;

returning the IP address associated with the hostname; and

in accordance with a determination that a predefined condition is satisfied, updating only a second address record in a master cache, the second address record including the hostname and the IP address that is included in the first address record in the first cache, the second address record including the IP address, the hostname, and access parameters, wherein the predefined condition is a staleness condition of the second address record.

9. The method of claim 8, further comprising providing the first cache in a main memory of a server and the master cache in a secondary memory of the server.

10. The method of claim 8, further comprising:

repeating said receiving, identifying, returning and updating for each of a set of hostnames embedded in a document.

11. The method of claim 8, further comprising:

repeating said receiving, identifying, returning and updating for each of a set of hostnames embedded in a document that is prefetched from a document server.

12. A system for responding to an IP resolution request, comprising:

at a server;

one or more processors and memory storing one or more programs to be executed by the one or more processors;

instructions, which when executed by the server, cause the server to receive the IP resolution request, the IP resolution request including a hostname;

instructions, which when executed by the server, cause the server to identify a first address record in a first cache matching the IP resolution request, the first address record including an IP address and the hostname;

instructions, which when executed by the server, cause the server to return the IP address associated with the hostname;

instructions, which when executed by the server, cause the server to update only second address records in a master cache, a respective second address record including the hostname and the IP address that is included in the first address record in the first cache, the second address record including the IP address, the hostname, and access parameters.

13. The system of claim 12, wherein the first cache is resident a main memory of a server and the master cache is resident in a secondary memory of the server.

14. The system of claim 12, further comprising instructions which when executed by the server, cause the server to repeat said receiving, identifying, returning and updating for each of a set of hostnames embedded in a document that is prefetched from a document server.

15. A self-refreshing domain name service (DNS) system, comprising:

at a server;

a DNS cache, the DNS cache including a first set of address records, each address record including a hostname and an IP address;

a DNS master, the DNS master including a second set of address records, each address record including a hostname, an IP address and a plurality of parameters indicative of the freshness of the IP address, wherein a respective first address record in the first set of address records includes the hostname and the IP address of a respective second address record in the second set of address records; and

the DNS master further including

a cache updating logic for updating the first set of address records in the DNS cache; and

a self-refreshing logic for identifying and refreshing only address records in the second set of address records.

16. The system of claim 15, wherein the IP addresses in the first set of address records are deemed fresh.

17. The system of claim 15, wherein the self-refreshing logic examines the second set of address records and identifies one or more address records which have respective freshness parameters that meet predefined criteria.

18. The system of claim 17, wherein the predefined criteria include that the parameter of time to live of an IP address is below a predefined threshold.

19. The system of claim 17, wherein, for the identified address records, the self-refreshing logic submits a hostname resolution request with respect to the hostname to a third-party hostname resolution system;

receives a new IP address associated with the hostname; and

updates the identified address record using the new IP address.

20. The system of claim 18, wherein, for each identified address record, the cache updating logic updates an address record in the first set, if any, using the new IP address.

21. A computer program product, for use in conjunction with a server, comprising:

instructions for identifying a first address record in a master cache in the server which satisfies a first condition, the first address record associating a hostname with an IP address and including freshness parameters;

instructions for obtaining from a hostname resolution system an updated IP address associated with the hostname when the first condition is satisfied;

instructions for updating only the first address record with the updated IP address when the first condition is satisfied; and

instructions for updating the first address record and a second address record in a second cache in the server with the updated IP address when the second condition is satisfied, the second address record including the hostname and the updated IP address that is included in the first address record.

22. The computer program product of claim 21, further comprising instructions for determining whether the first condition is satisfied by examining the freshness parameters associated with the IP address.

23. The computer program product of claim 22, wherein the first condition is satisfied when the IP address is stale.

24. The computer program product of claim 22, wherein the first condition is satisfied if the IP address will become stale within a predetermined time period.

25. The computer program product of claim 21, wherein the second condition is satisfied when the IP address is different from the updated IP address.

26. A system of updating IP address caches, comprising:

a server having one or more processors, and memory storing one or more programs to be executed by the one or more processors, the server including;

means for identifying a first address record in a master cache which satisfies a first condition, the first address record associating a hostname with an IP address and including freshness parameters;

means for obtaining from a hostname resolution system an updated IP address associated with the hostname when the first condition is satisfied;

means for updating only the first address record with the updated IP address when the first condition is satisfied; and

means for updating the first address record and a second address record in a second cache with the updated IP address when the second condition is satisfied, the second address record corresponding to including the hostname and the updated IP address that is included in the first address record.