A caching proxy server, or simply a "cache", receives an HTTP request from a client, fetches the data requested either from its own cache or from another cache or the origin server, and forwards the response back to the client. Proxy servers are also commonly used to grant access to the web for users behind network firewalls, but we are interested only in those proxy servers that are caches.
A web site that serves documents that it originates is called an origin server, and each such site is considered to have a single collection of all its documents. More generally, a collection corresponds to any URI prefix ending with '/' (in our terminology at least), so a single server has possibly many nested collections, and each may have different usage characteristics. The replication system is designed to support caching of documents from multiple nested collections and documents served by multiple servers. But it is helpful for understanding the system to simplify the problem by considering only a single collection from a single server; this approach is taken in this paper.
We plan to demonstrate that it is possible to implement a system of caches that distribute web content and metadata between a large number of caches in a scalable manner. Furthermore, by minimally extending the relevant protocols and by extending the functionality of popular cache servers, we hope to make it easier to install this new software and therefore increase the likelihood of deployment to a larger number of caches.
We are primarily concerned in this paper with how new or changed documents are efficiently propagated through this system of caches. We are also concerned with how clients find the nearest cache, and how a client or cache proceeds to find a document when it is not found in a cache. But even though these latter concerns are relevant in a fully integrated cache support system, they are somewhat secondary to our emphasis on efficient propagation.
This paper explores one possible design for such a system. To achieve the goal of scalability, the design is motivated by one fundamental principle: the avoidance of any centralized management; instead we depend on each cache to manage its own local knowledge of neighboring caches. Another principle is almost as important: the avoidance of any manual management. Instead, each cache should automatically reconfigure its set of known neighboring caches, to incrementally optimize the propagation of documents that are likely to be of interest to current and future users. In addition to replicating actual documents via this propagation mechanism, we believe it is even more important to replicate the resolution-related metadata about documents. Therefore, we intend to support the replication and use of resolution hint data to further optimize the cache lookup process.
One might reasonably ask "Why bother with the complexity of the system being proposed here? Why are existing caches not enough?" In fact, this system is not urgently needed right now since network capacity and processor speeds are increasing dramatically even as the web user population is also increasing. Also, as the number of servers grows, users will on average tend to distribute their requests across more servers. So the caching that people now do, on ISPs or local work groups, is usually sufficient. But there will continue to be more problems with "hot spots" as certain sites become very popular for short periods of time. Also the average distance between clients and the servers they use may tend to grow, increasing the load on intermediate network routers. Therefore, the system we are developing will become more relevant as large-scale replication itself becomes necessary to offset the negative effects of general network growth.
To facilitate deployment, it is also desirable for the system to offer advantages even at very small scales, on the order of 2 or 3 caches for one server, and incrementally grow as more caches and servers are added to meet growing needs. Thus the overhead of the cache system in terms of increased load on servers and the network should be negligible.
We also don't want to depend on manual configuration and periodic reconfiguration of each cache by its administrator. The problem is the amount of work that would be required of administrators, not just once, but repeatedly as other caches in the network change, and as the interests of the user base changes. This problem is compounded when we consider configuration of caches for not just one origin server but any number of servers each with any number of collections. The automatic reconfiguration mechanism that we are designing should be able to do a much more thorough job of continuously reoptimizing the propagation of documents and metadata through the cache network.
We approach the problem by requiring the origin server and each cache to maintain its own list of "neighborhood" caches, which are other caches that it will communicate with. Since each cache has only local, partial knowledge of the network, the management of the overall system is not done in any single place. Although the result will very likely not be optimal performance, we contend that reasonable efficiency can emerge from the combined actions of the individual caches.
In order to experience the benefits of this system, users must configure their web browsers to use one of the caches in the system, probably one that is the most convenient or closest to them. If such a cache is unknown to a user, the browser could contact the origin server normally. But if the user's browser supported a new resolution metadata feature, we could use the network of caches to help the browser automatically find a nearby cache. The HTTP 1.1 extension mechanism could be used to provide this resolution metadata to new browsers in a backward compatible way. Instead of returning a requested document, the server would return a list of URIs for proxy caches that might also return the document. This process would be repeated at each proxy cache until a reasonably close cache is found.
Just as for browsers, each cache that is added to the system could start off with a small list of other caches already in the system, or it could ask the origin server for such a list. This autoconfiguration is desirable for ease of deployment, as mentioned above.
It is important to note that caches in the system do not generally poll other caches or the origin server for the existence of new or changed documents, unless a browser has made a specific request for a document. Instead, each cache in our system waits to be notified about the existence of a document from either the origin server or another cache. After being notified, if the cache anticipates future use of the document (based on demand for similar documents), it might then request it.
Instead of always replicating the documents themselves, we also want to support replication of hints about the existence of documents and the caches on which they can be found. The decision about whether to locally cache a particular document should therefore be based not only on the availability of a document, but also on how quickly that document can be retrieved from another cache if needed, and how full the local cache is currently.
One possibility is to require cryptographic signatures for all documents transferred through unknown caches. A public-private key pair system would be quite suitable. Each document has an associated origin server and each origin server has a public key that it serves to the caches in a secure manner. All documents in the system are signed by the private key of the document's origin server, and the signatures can then be verified by caches or clients using the corresponding public keys. Of course, the public keys must also be reliably and scalably transferred from the origin servers, possibly using the same replication architecture, but where does this circularity stop? Ultimately, we must rely on some implicitly trusted relationship as the foundation upon which to build all the rest.
Another possibility is to somehow limit participation in the system to only trustworthy caches. Trustworthiness might be based on referrals from other trusted caches, for example.
It might also be sufficient that each cache that handles a document must sign it before passing it on; if a discrepancy is discovered by some other means (such as by a human reader, or using a signature from the origin server), the perpatrator could at least be identified. But this mechanism does not add any other value to the system and it costs more in terms of creating and verifying additional signatures.
[Need to discuss ACL issues - encryption of documents under access control.]
If a document does not have an authoritative origin server associated with it, as is the case with anonymous distribution of files or messages, then we have a considerably more difficult problem of automatically ensuring the integrity of the document. It seems we must rely on the integrity of the source of the information, but if the source also wishes to remain anonymous, we have the same problem at a higher level.
However, there may be a solution that involves some form of anonymous trust credits that people accumulate over time as they make use of the system. Each time you receive data that appears to be authentic, you provide feedback to the system so that the source of that information, and each intermediary back to the source, would receive some trust credits. And if everyone agrees with you, then you also receive some trust credits. Working out the trust credit economy could be an interesting research project.
At any one time, the system of caches will consist of several cache servers that are more or less densely connected to one another and to the origin server. Over time, each cache will discover additional caches through its negotiations with the caches it already knows about. It can do this by explicitly asking any known cache for its list of known caches. Or it can ask any other origin servers that it knows of from other documents it has.
Another promising way to inform caches of the existence of each other is by way of the replication process itself; as a document is pushed from one cache to the next, it would add its own identity to a list of caches that the document was previously transferred through.
Each cache keeps a table of the other caches that it knows about, and it associates (at least) two weights with each cache: an Incoming weight and an Outgoing weight. A higher Incoming weight or Outgoing weight generally indicates that documents and notifications about documents have been delivered more "efficiently" from that cache (for the Incoming weight) or to that cache (for the Outgoing weight) as compared with the other caches. In addition to adding caches to its list of known caches, each cache should also generally drop some caches that are of lesser value compared to this cache, particularly when it has "too many" in its list. The process of incrementally adding caches and selectively dropping those of lesser value will, over time, result in a list of caches with increasingly higher value. Since each cache optimizes it connections to other caches, you might guess that the overall network of caches will also be optimized, but this is not necessarily the case, as discussed below.
There are many possible variations in the details of this general process, and we plan to explore some of these variations during the course of our research. Here we suggest a couple possibilities.
Initially, each cache in the list of neighboring caches is given the same incoming and outgoing weights, say zero. Every time a notification about a document is received from a neighboring cache that was not already received via some other route, the Incoming weight for that cache should be incremented. Other caches that offer the same document later might have their Incoming weights incremented a lesser amount or, if there are too many incoming caches, the weight should be decremented.
The process of adjusting the Outgoing weights is quite different from that of Incoming weights. This is because a cache actively chooses to notify other caches in contrast to waiting to be notified, so we can't use the order in which notifications occur to adjust the weights. Furthermore, the order in which the outgoing caches are used could make a difference in how they are valued, so the caches should be used in some order that is fair to each, such as a random order or a round robin rotation.
There are two factors that might be used to adjust an outgoing weight. One factor is the degree to which a notification is needed by the outgoing cache compared to the other incoming caches of that outgoing cache. This factor is essentially equivalent to the corresponding Incoming weight for the outgoing cache, and as such, it is not necessary as a separate weight; we might as well just rely on that Incoming weight. Consequently, it doesn't provide an independent way to judge the value of outgoing caches relative to each other. But using this measure, we would at least be assured of preferring to send notifications to caches that tend to need them.
The other factor is the degree to which a notification is needed by an outgoing cache compared to the other outgoing caches. To adjust the weight based on this factor, every time a cache attempts to notify a neighoring cache about a document, it should increment the Outgoing weight for that cache if the notification was not previously received by another route. Otherwise, the weight should be incremented a lesser amount or decremented, depending on the order in which the outgoing caches are used.
As a cache learns of other caches (e.g. by asking known caches for their lists of caches), it should occasionally take the time to "prune" the list by removing the least reliable or least valuable caches from its list, as measured by the weights. The ideal number of neighboring caches might be a relatively small constant, referred to as N. We don't know what the value of N should be, and perhaps the value should vary depending on changing circumstances. Studies should be conducted to determine the consequences of various values, or the algorithm itself should be able to dynamically determine the value automatically.
More specifics of the incremental weight adjustments follow.
As new documents are propagated from one cache to the next, the first N caches who offer the new document to the cache should have their Incoming weights incremented and the rest get decremented.
Each cache announces new documents to the top N neighboring caches with the highest Outgoing weight, or it randomly picks N of the neighboring caches with a bias towards those with the highest Outgoing weight.
A cache might request updates from neighboring caches even before it knows of the existence of new documents. It could make update requests of the top M caches with the highest Incoming weight, similar to how Outgoing weights are used.
The evaluation criteria for determining how to reconfigure is based ultimately on the degree of satisfaction of user requests for resources.
After a cache drops a cache from its list because it has become less desirable than the others on its list, it might soon be added again. But because it is now an unknown cache, it will be given a more neutral initial weight that is relatively higher than that of some other caches which were previously weighted higher. If the previously higher cache gets dropped as a result, that seems unfair. But if the previously dropped cache gets dropped yet again, that seems wasteful. However, if they all have relatively lower weights, there is no great loss, other than the wasted time. It would be better to maintain a longer memory of the past performance of more caches, but only use the better caches.
A more serious problem is that a new cache might have a difficult time getting established in an already well optimized network. It may take a while to find the best places to be connected, but in the meantime, the caches it does try to connect with won't be very satisfied with this newcomer. Furthermore, even if it does find good connections, it starts with the disadvantage of being unknown. If each cache that the new cache is added to gives it an initial weight that is lower than all the other caches, then it will tend to be dropped quickly without being given a chance to prove its value. If instead of giving an initial weight that is lower than the others, it is given an average value, or perhaps somewhat below average, then it has a better chance, but at the risk of dropping some other caches that really should have a higher value than the new cache.
A distant cache might be less well connected to any other cache in the network than they are to each other. A consequence might be that such distant caches would be excluded since no cache would find them desirable. Also related to this is that a group of interconnected caches might become weakly connected to the rest, or even disconnected from the rest, if they are all closer to each other than they are to the rest. To counter this over-clustering effect, individual caches need to have a better sense of how documents are propagated through the network. One way to do this is to keep track of the path that each document (or its metadata) takes as it is propagated. So the path should be a consideration in addition to the speed of propagation. Generally, the more varied the paths, the better, since that variety corresponds to robustness. To keep this scalable, only the last few hops, say three hops, need to be transferred to neighboring caches. Thus each cache only needs to be responsible for maintaining its local part of the network and no cache or server needs to be responsible for the whole network.
Long cycles might still be a problem because they would appear to be novel if the cycle is longer than the number of hops that are transferred. However, any cycle will be stopped as soon as a cache detects that it has seen a notification previously, whether it is due to a cycle or not. But cycles could still occur if a cache forwards notifications but forgets too quickly that it has done so. To counter this, the total number of hops should also be transferred along with the last few hops, and anything with a hop count that has reached some threshold should simply be dropped.
Caches probably also should make use of more outgoing caches than incoming caches, perhaps twice as many, and caches should be tolerant of bad connections, both outgoing and incoming, as long as the cache on the other end still finds the connection desirable.
When documents in a collection can originate from more than one cache, we might have more possibilities for disconnections since we might have the appearance of being well connected to one origin server while excluding others. Thus, the variety of propagation paths across the documents in the same collection should also be a factor.
Rather than blindly adding or dropping caches to achieve the desired number, there should either be a range of OK numbers, or the pressure to add or drop caches should be a function of the difference between the current actual number of caches and the desired number. This tolerance would tend to smooth out the discontinuities of variance over time.
Some caches may have bad days, or may be infrequently or periodically well connected. This instability may or may not be a criteria that counts against a cache. If long-term desirability should count for more, than we need to compute an average weight over time rather than merely a single weight for a short period of term. To some extent, the incremental adjustment of the weight can accumulate a higher or lower weight based on long term performance. But the lack of any indication of the strength of the weight means we don't know how much the weight should be adjusted based on its past performance. To improve on this, we might adjust the weight more when it is near zero (the initial value) and less when it is far from zero.
But we also want the network to adjust quickly to changing circumstances, so that what used to be a good connection could get dropped quickly if it really has turned into a bad connection. So history seems to conflict with currency. Redundancy in the varieties of propagation paths should help here by building and maintaining enough variety to give the system more resilience and overall stability.
For example, assume that Cache A has a new document. Cache A may notify Cache B that it has this document using an HTTP POST request with a special URI that indicates this is a notification and embeds the identification information of the new document, including the URI and entity tag. After this notification, Cache B can make a GET request to Cache A for the new document.
A document transfer actually consists of three pieces of information: the document content, the system-wide URL for the document, and the signature as signed by the public key of the origin server.