Scalable distributed caching system and method

• US 5,933,849 A
• Filed: 04/10/1997
• Issued: 08/03/1999
• Est. Priority Date: 04/10/1997
• Status: Expired due to Term

• Current Assignee: AT&T Intellectual Property I LP (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Srbljic, Sinisa, Dutta, Partha P., London, Thomas B., Vrsalovic, Dalibor F., Chiang, John J.
• Primary Examiner(s): Cabeca, John W.
• Assistant Examiner(s): Namazi, Mehdi
• Application Number:
  US08/827,763
• Time in Patent Office: 845 Days
• Field of Search: 711/141, 711/3, 711/144, 711/118, 711/122, 711/124, 395/200.46, 707/205
• US Class Current: 711/118
• CPC Class Codes: G06F 12/0813 with a network or matrix configuration
• CPC Class Codes: G06F 12/0815 Cache consistency protocols
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: Y10S 707/99953 Recoverability
• CPC Class Codes: Y10S 707/99956 File allocation

Abstract

A scalable distributed caching system on a network receives a request for a data object from a user. The caching system carries out a locator function that locates a directory cache for the object. The directory cache stores a directory list that identifies the locations of object caches that purport to store copies of the object requested by the user. The object caches on the object directory list are polled, and in response send messages to the cache that received the user request indicating if each object cache stores a copy of the requested object. The receiving cache sends a message requesting a copy of the object to the object cache that sent the message first received by the receiving cache indicating that an object cache stores the requested object. The object cache that sent the first received message then sends a copy of the object to the receiving cache, which stores a copy and then sends a copy to the user. The directory list for the object is then updated by adding the network address of the receiving cache. Outdated copies of objects stored on object caches are deleted in a distributed fashion to maintain the coherence of the cached copies. This is further reinforced by the association of time-to-live parameters with the each copy and each object cache address on directory lists.

Claims

1. A method for implementing a scalable distributed caching system on a network that receives a request from a user for a data object stored on the network, comprising the steps of:

a. storing a copy of a data object on an object cache on the network;

b. storing a plurality of directory lists on a plurality of directory caches on the network, each said directory list including the network address of a certain object and at least one network address of an object cache on which a copy of the certain object is purportedly stored;

c. carrying out a locator function on a receiving cache that receives a request for a given object from a user, the request including a network address of the given object, the locator function using the user request as an input and providing a pointer as an output, wherein the pointer indicates a network of a particular directory cache that stores a directory list for the given object;

d. sending an object request message for the given object from the receiving cache to the particular directory cache whose address is indicated by the pointer;

e. receiving a directory list for the given object from the particular directory cache, the directory list for the given object including an address of an object cache at which a copy of the given object is purportedly stored;

f. selecting alpha object cache network addresses from the directory list for the given object;

g. sending a message from the particular directory cache to each selected object cache, requesting each selected object cache to send a message to the receiving cache indicating if the selected object cache stores a copy of the given object;

h. sending a message from each selected object cache to the receiving cache indicating if the selected object cache stores a copy of the given object;

i. identifying a prime object cache as the object cache that sent the first message received by the receiving cache indicating that an object cache stores a copy of the given object; and

j. sending a message from the receiving cache to the prime object cache requesting that the prime object cache send a copy of the given object to the receiving cache.

2. The method of claim 1, wherein alpha is equal to the number of object cache addresses on the directory list for the given object.

3. The method of claim 1, wherein alpha is less than the number of object cache addresses on the directory list for the given object if there is more than one object cache address on the directory list for the given object.

4. The method of claim 1, wherein alpha is equal to the number of object cache addresses on the directory list for the given object.

5. The method of claim 1, wherein alpha is less than the number of object cache addresses on the directory list for the given object if there is more than one object cache address on the directory list for the given object.

6. The method of claim 1, further comprising the steps of:

k. sending a copy of the given object from the prime object cache to the receiving cache; and

l. storing a copy of the given object on the receiving cache.

7. The method of claim 6, further comprising the steps of:

m. sending a message from the receiving cache to the particular directory cache requesting that the particular directory cache add the address of the receiving cache to the directory list for the given object; and

n. adding the address of the receiving cache to the directory list for the given object.

8. The method of claim 1, wherein a copy of the given object is not received by the receiving cache from the prime object cache, and wherein a plurality of messages are received at the receiving cache indicating that a plurality of object caches purportedly store copies of the given object, further comprising the steps of:

k. identifying as an alternative cache an object cache from which the receiving cache received a message indicating that the object cache stores a copy of the given object, said alternative cache being distinct from said prime cache;

l. sending a message from the receiving cache to the alternative cache requesting that the alternative cache send a copy of the given object to the receiving cache.

9. The method of claim 8, further comprising the steps of:

m. sending a copy of the given object from the alternative cache to the receiving cache; and

n. sending a copy of the given object from the receiving cache to the user that requested the object.

10. The method of claim 8, further comprising the steps of:

m. sending a copy of the given object from the alternative cache to the receiving cache; and

n. storing a copy of the given object on the receiving cache.

11. The method of claim 10, further comprising the steps of:

o. sending a message from the receiving cache to the directory cache requesting that the receiving cache add the address of the receiving cache to the directory list for the given object; and

p. adding the address of the receiving cache to the directory list for the given object.

12. The method of claim 1, wherein a copy of the given object is not received by the receiving cache from the prime object cache, further comprising the steps of:

k. sending a message from the receiving cache to the directory cache to delete the network address of the prime object cache from the directory list for the given object; and

l. deleting the network address of the prime object cache from the directory list for the given object.

13. The method of claim 1, wherein a copy of the given object is not received by the receiving cache from the prime object cache, further comprising the steps of:

k. sending a message from the receiving cache to the server at the network address of the given object requesting that the server send a copy of the given object to the receiving cache; and

l. receiving a copy of the given object at the receiving cache.

14. The method of claim 13, further comprising the steps of:

m. sending a message to each object cache on the directory list for the given object, the message requesting that the object cache delete its stored copy of the given object;

n. sending a message to the particular directory cache for the given object requesting that the particular directory cache delete the addresses of the object caches from the directory list for the given object and add the address of the receiving cache to the directory list for the given object; and

o. deleting the addresses of the object caches from the directory list for the given object and adding the network address of the receiving cache to the directory list for the given object.

15. The method of claim 1, further comprising the steps of:

k. associating a time-to-live parameter with each copy of an object stored on an object cache, the time-to-live parameter determining a time at which the copy is to be deleted; and

l. deleting the object from the object cache at the time determined by the time-to-live parameter of the copy.

16. The method of claim 1, further comprising the steps of:

k. associating a time-to-live parameter with each object cache address on the directory list for an object, the time-to-live parameter determining a time at which the address is to be deleted; and

l. deleting an object cache address on the directory list for the object at the time determined by the time-to-live parameter associated with the object cache address.