Multiple cache communication and uncacheable objects
View Patent ↗The invention provides a method and system for operating multiple communicating caches. Between caches, unnecessary transmission of repeated information is substantially reduced. 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. Pairs of communicating caches substantially compress transmitted information. This includes both reliable compression, in which the receiving cache can reliably identify the compressed information in response to the message, and unreliable compression, in which the receiving cache will sometimes be unable to identify the compressed information. 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. 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 maintain non-cacheable objects beyond their initial use, along with digests of the non-cacheable objects. When a server device returns identical information to a root cache, root caches can transmit only associated digests to leaf caches, avoiding re-transmitting the entire non-cacheable object.
1. A memory storing information including instructions, the instructions executable by a processor, the instructions including
determining a first signature, an uncacheable object stored at a first cache, said uncacheable object having been requested by a client coupled to a network from a server coupled to said network, wherein said first cache is configured so as to be coupled to said network in a location that is remote from both said client and said server, and said uncacheable object is dynamically generated by said server in response to a URL;
sending said first signature from said first cache to a second cache;
comparing said first signature at said second cache with a second signature for said uncacheable object stored at said second cache; and
sending said uncacheable object to said second cache only if said first signature and said second signature do not match.
2. A memory as in claim 1 wherein said second cache can only recover said uncacheable object from said second signature in response to a contents of said second memory associated with said second cache.
3. A memory as in claim 1 , wherein said second cache can recover said uncacheable object from said second signature without further information.
4. A memory as in claim 1 , wherein
said instructions for determining a first signature include instructions for
determining a known function of a first object at said first cache;
said determining said first signature includes a result of said known function;
said instructions for matching include instructions for determining said known function of said uncachable object at said second cache and comparing said first signature with a result of said known function of said uncacheable object.
5. A memory as in claim 4 , wherein said known function is irreversible.
6. A memory storing information including instructions, the instructions executable by a processor, the instructions including
determining, at a first cache, a first object signature responsive to a first uncacheable object, said first uncacheable object having been requested by a client coupled to a network from a server coupled to said network, wherein said first cache is configured so as to be coupled to said network in a location that is remote from both said client and said server, and said uncacheable object is dynamically generated by said server in response to a URL;
sending said first object signature to a second cache, wherein said second cache is configured so as to be coupled to said network in a location that is remote from both said client and said server;
comparing, at said second cache, said first object signature with a function of at least one first uncacheable object; and
refraining from sending said first uncacheable object in response to said steps for comparing only if said first object signature does not match said function of said first uncacheable object.
7. A memory as in claim 6 , including instructions for
coupling a result of said steps for comparing to said first cache; and
coupling said first object to said second cache responsive to said comparison result.
8. A memory as in claim 6 , including instructions for
storing at said first cache information whether said first object is likely to be stored at said second cache;
wherein said steps for transmitting said object signature are responsive to said information.
9. A memory storing information including instructions, the instructions executable by a processor, the instructions including
storing an uncacheable object at a first cache, said uncacheable object having been requested by a client coupled to a network from a server coupled to said network, wherein said first cache is configured so as to be coupled to said network in a location that is remote from both said client and said server, and said uncacheable object is dynamically generated by said server in response to a URL;
determining an object signature at said first cache in response to said uncacheable object;
sending said object signature to a second cache, wherein said second cache is configured so as to be coupled to said network in a location that is remote from both said client and said server;
comparing said object signature with a function of at least one said uncacheable object stored at said second cache; and
sending said uncacheable object to said second cache in response to said steps for comparing if said object signature does not match said function.
10. A memory as in claim 9 ,
including instructions for storing at said first cache information whether first object is likely to be stored at said second cache;
wherein said instructions for sending said object signature are responsive to said information.
11. A memory as in claim 9 , including instructions for transmitting a result from performing said instructions for comparing to said first cache.
12. A memory storing information including instructions, the instructions executable by a processor, the instructions including
storing, at a first cache, a first uncacheable object and first information including a date stamp that is used to ascertain the staleness of said first uncacheable object, said first uncacheable object having been requested by a client coupled to a network from a server coupled to said network, wherein said first cache is configured so as to be coupled to said network in a location that is remote from both said client and said server and said first uncacheable object is dynamically generated by said server in response to a URL;
storing, at a second cache, a second uncacheable object and second information including a date stamp that is used to ascertain the staleness of said second uncacheable object, wherein said second cache is configured so as to be coupled to said network in a location that is remote from both said client and said server and said second uncacheable object is dynamically generated by said server in response to a URL;
comparing said first information with said second information;
sending said first information to said second cache; and
discarding said second uncacheable object if said first information does not match said second information.
13. A memory as in claim 12 , including an instruction for
sending said second information to said first cache; and
discarding said first uncacheable object in response to said first information and in response to said second information.
14. A memory as in claim 12 , wherein said first information includes a likelihood of said first uncacheable object being stored at said second cache.
15. A memory storing information including instructions, the instructions executable by a processor, the instructions including
storing, at a first cache, an uncacheable object from a server and first information regarding the probability said uncacheable object will be stale, said uncacheable object having been requested by a client coupled to a network from said server coupled to said network, wherein said first cache is configured so as to be coupled to said network in a location that is remote from both said client and said server, and said uncacheable object is dynamically generated by said server in response to a URL;
storing, at a second cache, a second uncacheable object for delivery to a client and second information regarding the probability that said second uncacheable object will be requested by said client, wherein said second cache is configured so as to be coupled to said network in a location that is remote from both said client and said server;
sending said first information from said first cache to said second cache;
sending said second information from said second cache to said first cache, and
comparing said first information with said second information; and
determining whether to discard said uncacheable object from said first cache in response to a result of said comparing step;
wherein said first cache and said second cache operate together.
16. A memory storing information including instructions, the instructions executable by a processor, the instructions including
providing a set of associations, at both a first cache and a second cache, such that each association in said set of associations includes a tag value and a dictionary element, wherein said set of associations concerns an uncacheable object having been requested by a client coupled to a network from a server coupled to said network, wherein said first cache and said second cache are configured so as to be coupled to said network in a location that is remote from both said client and said server and said uncacheable object is dynamically generated by said server in response to a URL;
comparing at least one of said set of associations from said first cache with at least one of said set of associations from said second cache;
discarding one or more of said set of associations at said second cache if one association included in said set of associations at said second cache matches one of said set of associations at said first cache; and
sending from said first cache to said second cache said tag value or said dictionary element, in response to said steps for discarding, wherein said dictionary element and said tag value are associated with a web object.
17. A memory as in claim 16 , including instructions for
transmitting, from said destination to said source, an indication responsive to said instruction for possibly discarding;
wherein if said dictionary element is still present at said destination, said source does not need to transmit said dictionary element to said destination.
18. A memory storing information including instructions, the instructions executable by a processor, the instructions including
sending a dictionary element from a source to a destination, said source and said destination being coupled to a communication link;
associating, at both said source and said destination, a first and second tag value with said dictionary element;
comparing said first tag value with said second tag value;
discarding said dictionary element at said destination if said first tag value for said dictionary element matches a second tag value for said dictionary element at said destination; and
sending, from said source to said destination, said tag value or said dictionary element in response to said steps for discarding,
wherein said dictionary element and said tag value concern an uncacheable object requested by a client coupled to a network from a server coupled to said network, wherein said source and said destination are configured so as to be coupled to said network in a location that is remote from both said client and said server and said uncacheable object is dynamically generated by said server in response to a URL.
19. A memory as in claim 18 , including instructions for
transmitting, from said destination to said source, an indication responsive to said steps for possible discarding;
wherein if said dictionary element is still present at said destination, said source does not deed to transmit said dictionary element to said destination.
20. A memory as in claim 18 , wherein said set of dictionary elements each include an entire object deliverable from a first cache to a second cache.
21. A memory as in claim 18 , wherein said set of dictionary elements for said method includes at least one object large than one kilobyte.