MAINTAINING STRONG CACHE CONSISTENCY MECHANISM FOR WEB

NEENA GUPTA¹*, MAHESH MANCHANDA²*, MANISH SINGH³*
¹Department of Computer Application, Kanya Gurukul Mahavidyalaya, Dehradun, Uttarakhand
²Department of Computer Application, Graphic Era University, Dehradun, Uttarakhand
³Department of Computer Application, Graphic Era University, Dehradun, Uttarakhand
* Corresponding Author : manishsingh12@rediffmail.com

Received : 12-12-2011     Accepted : 15-01-2012     Published : 28-02-2012
Volume : 3     Issue : 1       Pages : 206 - 209
J Inform Oper Manag 3.1 (2012):206-209

Internet, the World Wide Web can be considered as a large distributed information system that provides access to shared data objects; growing exponentially, which results in network congestion and server overloading. Web caching has been recognized as one of the effective schemes to improve the service bottleneck and reduce the network traffic, thereby minimize the user access latency. Web caching is a mechanism to store Web objects at certain locations for convenient future access. However, caching of objects at various points on the Web raises cache consistency as a high-flying issue. Cache consistency mechanisms ensure that cached copies of data are eventually updated to reflect changes to the original data. In this paper, we discuss several strong web cache consistency mechanisms currently in use at different level of web.

Caching consistency, TTL Fields, Client Pooling, Invalidation Protocols, Strong Consistency, Weak Consistency.

The World Wide Web can be considered as a large distributed information system that provides access to shared data objects. As one of the most popular applications currently running on the Internet, The World Wide Web is of an exponential growth in size, which results in network congestion and server overloading. Web caching has been recognized as one of the effective schemes to improve the service bottleneck and reduce the network traffic, thereby minimize the user access latency.
Web caching is the temporary storage of web objects (such as HTML documents) for later retrieval. Generally speaking, Web caching is a mechanism to store Web objects (such as HTML pages and image files) at certain locations for convenient future access.
• There are three significant advantages to web caching
• Reduced bandwidth consumption (fewer requests and responses that need to go over the network),
• Reduced server load (fewer requests for a server to handle),
• And reduced latency (since responses for cached requests are available immediately and closer to the client being served). Together, they make the web less expensive and better performing.
The value of caching is greatly reduced, however, if cached copies are not updated when the original data change. A major issue with caching is stale data access, i.e., the potential of using an out-of-date object stored in the cache instead of fetching the current object from the origin server.
However, caching of objects at various locations on the Web raises cache consistency as a high-flying issue. If the original object on server is changed while the end user keeps accessing an out-of-date copy from its local cache, out-dated or stale data would be accessed.
Cache consistency mechanisms ensure that cached copies of data are eventually updated to reflect changes to the original data. Always keeping the cached copies updated is possible if we keep contacting the server to validate their freshness. However, this means more control messages sent over the network, which consumes bandwidth and adds to server load, not to mention that the client might experience longer response time (usually referred to as client latency).
Therefore, the tradeoffs is, either sacrifice document freshness for faster response time or fewer control messages, or enforce the consistency of cached objects with their original copies on the server by sending control messages, using other time-based mechanisms, or making the origin server to take full responsibility. The first is known as weak cache consistency, while the second is referred to as strong cache consistency.
There are several cache consistency mechanisms currently in use on the Internet: time-to-live fields, client polling, and invalidation protocols.
Based on the role of the client and the server in the cache consistency control processing, we could have three categories of consistency mechanism or algorithms: Client Validation, Server Invalidation, and Client/Server (C/S) Interaction. In client validation approach, it is the client (or proxy) cache manager that is responsible for verifying the validity/freshness of its cached objects. With server invalidation, caches always assume the freshness of the objects they cache, and whenever an object is changed on a Web server, it is the server’s responsibility to notify all the caches who cache that object to delete their stale copies. However, the way that the server invalidates stale copy could vary. In the C/S interaction category, the client and the server work interactively to enforce consistency to certain level as required by application. From another point of view, based on how strict the caches are kept consistent, algorithms could be classified into two categories: strong cache consistency and weak cache consistency.
Here we discuss only the strong cache consistency mechanism or algorithms at Client Validation and Server Validation in more detail in this paper, since these are the focus or our work.

Our work is motivated by recent work on web caching and maintaining Strong web cache consistency. In particular, Chengjie Liu and Pei Cao [1] and L.Y. CAO and M.T. OZSU [2] gave an excellent comparison of cache consistency mechanisms and algorithms via simulation using TPC-W tool, and conclude that weak cache-consistency approach such adaptive TTL would be best for web caching. They evaluate the performance of different categories of cache consistency algorithms using a standard benchmark: TPC-W, which is the Web commerce benchmark. Our analysis totally based on the result of TPC-W, which is the Web commerce benchmark. These results show that we could still enforce strong cache consistency without much overhead, and Invalidation, as an event-driven strong cache consistency algorithm, is most suitable for online e-business. We also evaluate the optimum deployment of caches and find that proxy-side cache has a 30–35% performance advantage over client-side cache with regard to system throughput.

Under Time-To-Live (TTL) approach, each object (document, image file, etc.) is assigned by origin server a time-to-live (TTL) value, which could be any value that is reasonable to the object itself, or to the content provider. This value is an estimate of the cached object’s lifetime, after which it is regarded as invalid. When the TTL expires, the next request for the object will cause it to be requested from the origin server. A slight improvement to this basic mechanism is that when a request for an expired object is sent to the cache, instead of requesting file transfer from the server, the cache first sends an If-Modified-Since (IMS) control message to the server to check whether a file transfer is necessary. TTL-based strategies are simple to implement, by using the “expires” header field in HTTP response or explicitly specifying it at object creation time. HTTP protocol version 1.1 contains header keywords such as “expires” and “max-age” to notify the cache manager how long the object could be deemed valid. However, a large number of HTTP responses do not have any expiry information [4] , which forces the cache manager to use heuristics to determine the object lifetime.
The challenge in this approach lies in selecting an appropriate TTL value, which reflects a tradeoff between object consistency on the one hand, and network bandwidth consumption and client latency on the other. If the value is too small, after every short period of time the cached copy will be considered stale. Therefore, many IMS messages will be sent to origin server frequently for validity check, which results in extra network traffic (although it might be trivial compared to the actual file transfer, if the file size is big) and server overhead. By choosing a large TTL value, a cache will make fewer external requests to origin server and can respond to user requests more quickly. Cached objects are retrieved as updated versions although their original copies are already changed on the server, thus, out-of-date document may be returned to the end-user. In [3] , the authors initially use a flat lifetime assumption for their simulation, which means that they assign all objects equal TTL values. This is also called explicit TTL, which results in poor performance. This has later been modified with the assignment of the TTL value based on the popularity of the file. This method is also mentioned in [2] , where this improved approach is termed adaptive TTL. Adaptive TTL takes advantage of the fact that file lifetime distribution is not flat. If a file has not been modified for a long time, it tends to stay unchanged. This heuristic estimation traces back to the Alex file system [3] . Gwertzman and Seltzer also mention that globally popular files are the least likely to change. By using adaptive TTL, the probability of stale documents is kept within reasonable bounds (<5%) [3] . TTL algorithm and its variations all enforce weak cache consistency, since it is possible that the cachemanager satisfies client requests with stale objects. Once an object is cached, it can be used as the fresh version until its time-to-live value expires. The cache manager assumes its validity during the TTL period. The origin server does not guarantee that the server copy of an object will remain unchanged before the object’s TTL expires. In other words, server is free to update the object even though its time-to-live value has not expired yet, thus making it possible for user to get out-of-date objects. On the other hand, applying TTL algorithm has the advantage that the origin server does not need to notify caches when the objects are changed on server.
One important improvement of TTL is to modify it so that each communication with the server updates the validity of the cached objects. Piggyback Client Validation (PCV) [7] achieves this by attaching to each message to the server, a list of cached objects whose original copies are on that server. These objects are not necessarily requested by end user at the time, instead they are in the piggyback list because their TTL values have expired.
Therefore, the validity of these objects are checked in advance, which reduces the possible stale hit ratio. Meanwhile, using a batch of validation messages could reduce the control message overhead.

Client polling is a technique where clients periodically check back with the server to determine if cached objects are still valid. The specific variant of client polling in which we are interested originated with the Alex FTP cache [3] and is based on the assumptions that young files are modified more frequently than old files and that the older a file is the less likely it is to be modified. Adopting these assumptions implies that clients need to poll less frequently for older objects. The particular protocol adopted by the Alex system uses an update threshold to determine how frequently to poll the server. The update threshold is expressed as a percentage of the object's age. An object is invalidated when the time since last validation exceeds the update threshold times the object's age. For example, consider a cached file whose age is one month (30 days) and whose validity was checked yesterday (one day ago). If the update threshold is set to 10%, then the object should be marked invalid after three days (10% * 30 days). Since the object was checked yesterday, requests that occur during the next two days will be satisfied locally, and there will be no communication with the server. After the two days have elapsed, the file will be marked invalid, and the next request for the file will cause the cache to retrieve a new copy of the file.
There are two important points to note with respect to client polling: it is possible that the cache will return stale data (if the data change during the time when the cached copy is considered valid) and it is possible that the cache will invalidate data that are still valid. The latter is a performance issue, but the former means that, like TTL fields, client polling does not support perfect consistency.
Like TTL, client polling can be implemented easily in HTTP today. The "if-modified-since" request header field indicates that the server should only return the requested document if the document has changed since the specified date. Most web proxies today are already using this field.

Invalidation protocols are required when weak consistency is not sufficient; many distributed file systems rely on invalidation protocols to ensure that cached copies never become stale. Invalidation protocols depend on the server keeping track of cached data; each time an item changes the server notifies caches that their copies are no longer valid. One problem with invalidation protocols is that they are often expensive. Servers must keep track of where their objects are currently cached, introducing scalability problems or necessitating hierarchical caching. Invalidation protocols must also deal with unavailable clients as a special case. If a machine with data cached cannot be notified, the server must continue trying to reach it, since the cache will not know to invalidate the object unless it is notified by the server. Finally, invalidation protocols require modifications to the server while the other protocols can all be implemented at the level of the web-proxy.
The Invalidation algorithm frees client cache manager from the burden of sending IMS messages. To ensure strong consistency, if an object A gets changed on the server, the server must send out an invalidation message right away to all the caches that store a copy of A. In this way, cache managers do not need to worry about object validity. As long as an invalidation message is not received, the object is valid. Invalidation approach requires the server to play a major role in the consistency control process over cached objects. This might be a significant burden for the Web server, because it has to maintain state for each object that has ever been accessed, as well as a list of the addresses of all the requestors. Such a list is likely to grow very fast, especially for popular objects. The server has to maintain at least a big storage space for keeping the lists. On the other hand, although an object is stored in a cache whose address is kept on the server list, this object might be evicted from the cache later on, because it is rarely if ever requested again, or the cache manager needs free space for newly-arrived objects. Therefore, it does not make sense for the server to keep the address of that cache on the list. Even worse, if the object is about to be changed, the server has to send invalidation message to the caches whose addresses are on the list, but they no longer keep the object, which adds unnecessary traffic to the network.
There are possible modifications that improve the problems of invalidation. For example, invalidation messages can be multicast to reduce server burden. The basic idea, as discussed in [4] , is that a multicast group is assigned to each object. When a cache manager requests a certain object, that cache is added to that object’s multicast group. Therefore, there will be a list of cache addresses for each multicast group. Such lists are stored in the multicast membership state maintained by routers. When an object update takes place, the server just sends one invalidation message to the corresponding multicast group, and then it is the router’s job to multicast the invalidation message to all the caches that belong to the multicast group.

Our analysis indicates that proxy side caching improves system performance more than client side caching and Invalidation algorithm performs best regardless of cache location. Based on our analysis, Polling-every-time is the least favorable alternative; it has the longest response time, producing the most message traffic. On the other hand, it is the easiest to implement. The advantages of Invalidation algorithm over TTL and Polling-every-time are twofold. First, Invalidation has the fewest control message transfer, shortest response time, and similar throughput as TTL while keeping cached objects fresh. Secondly, Invalidation protocol mechanism is event-based, which is more suitable for online e-commerce. The reason is that most Web data are not set to be changed at certain time; rather, Web objects get updated because of some event, e.g., client request. Event-based consistency control helps reduce unnecessary control messages while enforcing strong consistency more efficiently.

[1] Cao L.Y. and Özsu M.T (2002) Springer Computer Science, Vol 5 , Issue 2, 95-1.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[2] Chengjie and Pei Cao (2003) IEEE Transactions on Computers 47 (4), 445–457.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[3] Gwertzman J. and Seltzer M. (1996) USENIX Technical Conference, San Diego, CA, pp. 141–152.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[4] Rabinovich M. and Spatscheck O. (2002) Web Caching and Replication, Addison-Wesley.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[5] Cao P. and Liu C (1998) IEEE Transactions on Computers 47(4), 445–457.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[6] Cate V. (1992) USENIX File System Workshop, Ann Arbor, MI, pp. 1–11.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[7] Krishnamurthy B. and Wills C.E. (1997) USENIX Symposium on Internet Technologies and Systems, Monterey,CA, pp. 1–12.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[8] Krishnamurthy B. and Wills C.E. (1998) ComputerNetworks and ISDN Systems, 30(1–7),185–193.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[9] Rabinovich M. and Spatscheck O. (2002) Web Caching and Replication, Addison-Wesley.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[10] TPC specification version 1.4 (2001) Technical report, Transaction Processing Performance Council.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[11] Wessels D. (1995) INET Conference, Honolulu, Hawaii.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[12] Yin J., Alvisi L., Dahlin M. and Lin C. (1998) 18th International Conference on Distributed Computing Systems, pp. 285–294.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[13] Yin J., Alvisi L., Dahlin M. and Lin C. (1999) Knowledge and Data Engineering, 11(4), 563–576.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[14] Yu H., Breslau L. Shenker S. (1999) ACM SIGCOMM’99, Boston, MA, pp. 163–174.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[15] Jia Wang (2000) ACM SIGCOMM.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[16] Anindya Datta, Kaushik Dutta, Helen Thomas, Debra Vandermeer. And Krithi Ramamritham (2004) ACM Transactions on Database Systems, Vol. 29, No. 2, Pages 403–443.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

Table 1- A Classification Of Cache Consistency Algorithms