1. Field of the Invention
This invention relates to caches.
2. Related Art
In a computer system in which client devices request information from one or more server devices, it is sometimes desirable to provide a cache; that is, a device that maintains copies of requested information so multiple requests for the same information can be satisfied at the cache. When requests for information are satisfied at the cache, the server devices need not receive the requests, process them, and retransmit the same information over a communication channel that links the client devices and the server devices. For example, the server devices can be web servers, the client devices can be web clients, the communication channel can be an IP network such as the Internet, and the requested information can be web objects.
Some information requested from the server devices is considered not cacheable, for one or more of several reasons. As examples, the server can refuse to allow the information to be cached, or the information can be a result of a dynamic process that can provide differing results for the same request (so caching would obviate the operation of that dynamic process). An example of dynamically processed information could include advertisements, database searches, or output from CGI scripts.
However, it often occurs that non-cacheable information is requested a second time without having changed, so the second request to the server results in identical information being returned. In a system with multiple communicating caches, transmitting the same information from a first cache to a second cache (when each already has a copy) is an inefficient use of communication resources.
Accordingly, it would be desirable to provide a method and system for operating a set of multiple communicating caches, in which transmission of repeated information is substantially reduced or eliminated. A first aspect of the invention is to maintain information at each cache to improve the collective operation of multiple communicating caches. A second aspect of the invention is to substantially reduce the amount of information transmitted between multiple communicating caches. A third aspect of the invention is to refrain from unnecessarily transmitting the same data from a first cache to a second cache when the latter already has a copy.
The invention provides a method and system for operating a set of multiple communicating caches. Between caches, unnecessary transmission of repeated information is substantially reduced.
In a first aspect of the invention, each cache maintains information to improve the collective operation of the system of multiple communicating caches. This can include information about the likely contents of each other cache, or about the behavior of client devices or server devices coupled to other caches in the system.
In a second aspect of the invention, pairs of communicating caches substantially compress transmitted information. This includes both compression in which the receiving cache can reliably identify the compressed information in response to the message, and compression in which the receiving cache will sometimes be unable to identify the compressed information.
In a third aspect of the invention, a first cache refrains from unnecessarily transmitting the same information to a second cache when each already has a copy. This includes both maintaining a record at a first cache of information likely to be stored at a second cache, and transmitting a relatively short identifier for that information in place of the information itself.
In a preferred embodiment, a set of caches are disposed in a directed graph. structure, with a set of root caches disposed for coupling to server devices and a set of leaf caches disposed for coupling to client devices. Both root caches and leaf caches store non-cacheable objects beyond their initial use, along with relatively short identifiers for the non-cacheable objects. When a server device returns identical information to a root cache in response to a request for a non-cacheable object, that root cache transmits only the identifier of the non-cacheable object to the requesting leaf cache, avoiding re-transmitting the entire object if the leaf cache still has the object.