Scalable distributed caching system and method
First Claim
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.
3 Assignments
0 Petitions
Accused Products
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.
-
Citations
16 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16)
-
Specification