Scalable network object caching

• US 6,154,811 A
• Filed: 12/04/1998
• Issued: 11/28/2000
• 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): Yoo, Do Hyun
• Assistant Examiner(s): Namazi, Mehdi
• Application Number:
  US09/204,343
• Time in Patent Office: 725 Days
• Field of Search: 711/124, 711/123, 711/130, 711/118, 707/205, 395/200.46
• 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 scalable distributed caching system for users on a network with data objects having network addresses, comprising a receiving cache that receives a request for an object from a user, said receiving cache comprising a data bus connecting a receiving cache processor, a receiving cache computer readable memory and a receiving cache port adapted to be coupled to a network, wherein said receiving cache carries out a directory locator function that uses the user request for a data object as an input and provides a pointer to a directory cache as an output, said directory cache comprising a directory cache data bus connecting a directory cache processor, a directory cache computer readable memory and a directory cache port adapted to be coupled to a network, wherein said directory cache stores a directory list for the requested object in said directory cache computer readable memory, said directory list comprising the network address of the requested object and a network address of an object cache on the network, said object cache comprising an object cache data bus connecting an object cache processor, an object cache computer readable memory and an object cache port adapted to be coupled to a network, and wherein said object cache is adapted to store a copy of the requested object in said object cache computer readable memory of said object cache.

2. The system of claim 1, wherein said receiving cache, directory cache and object cache are logically grouped on a first level on the network in a hierarchy of levels on the network, and further comprising a second receiving cache, second directory cache and second object cache that are logically grouped on a second level in said hierarchy of levels, and wherein said receiving cache on said first level sends a request for the object requested by the user to said second receiving cache on said second level if said pointer does not indicate the address of a directory cache.

3. 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:

storing a copy of a data object on a first object cache on the network, said object cache having an object cache network address;

storing a directory list on a directory cache on the network, said directory list including the network address of an object and a network address of an object cache on which a copy of the object is purportedly stored;

receiving a request for an object from a user at a receiving cache, wherein the request includes a network address of the object;

performing a locator function at a receiving cache that receives a request for an object from a user, the request including a network address of the object, the locator function using the network address of the object as an input and providing a pointer to the directory cache as an output, wherein the directory cache stores a directory list for the object, where the directory list is a list of addresses of object caches that purport to store a copy of the object; and

sending a request for the object to an object cache on the directory list.

4. The method of claim 3, further comprising the step of sending an object request message from the receiving cache to the directory cache whose address is indicated by the pointer, wherein the object request message includes a request for a copy of the data object.

5. The method of claim 4, further comprising the step of sending an object cache location message from the directory cache to the receiving cache, wherein the object cache location message includes the location of an object cache included on the directory list for the object.

6. The method of claim 4, further comprising the step of sending an object storage status request from the directory cache to an object cache whose address is on the directory list for the object, the object storage status request requesting the object cache to send an object storage status response to the directory cache indicating if the object cache stores a copy of the object.

7. The method of claim 5, further comprising the step of sending an object storage status request from the receiving cache to an object cache whose address is included in the object cache location message from the directory cache to the receiving cache, the object storage status request requesting the object cache to send an object store status response to the receiving cache indicating if the object cache stores a copy of the object.

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

receiving an object storage status response at the directory cache from an object cache indicating that the object cache stores a copy of the object;

sending an object request message from the directory cache to the object cache requesting the object cache to send a copy of the object to the directory cache; and

sending a copy of the object from the object cache to the directory cache.

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

receiving an object storage status response at the receiving cache from an object cache indicating that the object cache stores a copy of the object;

sending an object request message from the receiving cache to the object cache requesting the object cache to send a copy of the object to the receiving cache; and

sending a copy of the requested object from the object cache to the receiving cache.

10. The method of claim 8, further comprising the step of storing a copy of the object at the directory cache.

11. The method of claim 9, further comprising the step of storing a copy of the object at the receiving cache.

12. The method of claim 10, further comprising the steps of adding the address of the directory cache to the directory list for the requested object, a copy of which is stored on the directory cache.

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

a. sending a message from the receiving cache to the directory cache storing the directory list for the object to add the address of the receiving cache to the directory list for the object; and

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

14. The method of claim 10, further comprising the step of sending a copy of the object from the directory cache to the user that requested the object.

15. The method of claim 11, further comprising the step of sending a copy of the object from the receiving cache to the user that requested the object.

16. A scalable distributed caching system on a network, comprising:

a. means for storing a copy of a data object;

b. means for storing a directory list for the object, the directory list identifying the network locations at which copies of the object are purportedly stored;

c. means for determining the network location at which the directory list for an object is stored;

d. means for selecting a location from which a copy of the object is to be requested; and

e. means for sending to a user a copy of the object from a selected location at which the copy is stored.

17. The system of claim 16, further comprising means for adding a new network locations at which an object is stored to the directory list for the object.

18. The system of claim 16, further comprising means for determine when a network location on a directory list for an object is outdated and means for deleting the outdated network location from the directory list for the object.

19. The system of claim 16, further comprising means for deleting a stored copy an object.

20. The system of claim 16, further comprising means for deleting a directory list for an object.

21. The system of claim 16, further comprising means for obtaining a copy of an object from the original source of the object.