Least Recently Used (LRU) is a very popular caching replacement policy. It is very easy to implement and offers good performance, especially when data requests are temporally correlated, as in the case of web traffic. When the data content can change during time, as in the case of dynamic websites or within databases, there is the need to prevent the cache to serve stale data. This is usually done by triggering an invalidation event in the cache, to purge all the previously cached data concerning the invalidated data item. The invalidation process tends to worsen the caching performance, since stored items can be invalidated after a short time, thus wasting storage space. Several models in the literature allow quantifying the cache hit probability of an LRU cache, but, to the best of our knowledge, the presence of invalidation events has not been taken into account so far. In this paper, we present an analytical performance evaluation of LRU caches that takes into account data requests and invalidation events, both modeled as independent renewal processes. Simulation results show the accuracy of our model. Moreover, we apply our model to evaluate the LRU performance in the case of a real application, Wikipedia. Finally, we evaluate by means of simulations the effect of invalidation in hierarchical caching. Our work allows us to conclude that the presence of invalidation events does not severely impact the LRU performance in single caches. As a matter of fact, invalidation effects can be ignored there, unless the invalidation rate is comparable with the request rate and the per-object invalidation rate and request rate are highly correlated. However, in the case of hierarchical caching, even a limited effect of invalidation on first-level caches is sufficient to noticeably affect the performance of second level/downstream caches.

Detti, A., Bracciale, L., Loreti, P., & Melazzi, N.b. (2018). Modeling LRU cache with invalidation. COMPUTER NETWORKS, 134(7 April 2018), 55-65 [10.1016/j.comnet.2018.01.029].

Modeling LRU cache with invalidation

Detti, Andrea;Bracciale, Lorenzo;Loreti, Pierpaolo;Melazzi, Nicola Blefari
2018

Abstract

Least Recently Used (LRU) is a very popular caching replacement policy. It is very easy to implement and offers good performance, especially when data requests are temporally correlated, as in the case of web traffic. When the data content can change during time, as in the case of dynamic websites or within databases, there is the need to prevent the cache to serve stale data. This is usually done by triggering an invalidation event in the cache, to purge all the previously cached data concerning the invalidated data item. The invalidation process tends to worsen the caching performance, since stored items can be invalidated after a short time, thus wasting storage space. Several models in the literature allow quantifying the cache hit probability of an LRU cache, but, to the best of our knowledge, the presence of invalidation events has not been taken into account so far. In this paper, we present an analytical performance evaluation of LRU caches that takes into account data requests and invalidation events, both modeled as independent renewal processes. Simulation results show the accuracy of our model. Moreover, we apply our model to evaluate the LRU performance in the case of a real application, Wikipedia. Finally, we evaluate by means of simulations the effect of invalidation in hierarchical caching. Our work allows us to conclude that the presence of invalidation events does not severely impact the LRU performance in single caches. As a matter of fact, invalidation effects can be ignored there, unless the invalidation rate is comparable with the request rate and the per-object invalidation rate and request rate are highly correlated. However, in the case of hierarchical caching, even a limited effect of invalidation on first-level caches is sufficient to noticeably affect the performance of second level/downstream caches.
Pubblicato
Rilevanza internazionale
Articolo
Esperti anonimi
Settore ING-INF/03 - Telecomunicazioni
English
Caching; Invalidation; LRU; Wikipedia; Computer Networks and Communications
http://www.journals.elsevier.com/computer-networks/
Detti, A., Bracciale, L., Loreti, P., & Melazzi, N.b. (2018). Modeling LRU cache with invalidation. COMPUTER NETWORKS, 134(7 April 2018), 55-65 [10.1016/j.comnet.2018.01.029].
Detti, A; Bracciale, L; Loreti, P; Melazzi, Nb
Articolo su rivista
File in questo prodotto:
File Dimensione Formato  
cc_inv_rev2.pdf

non disponibili

Licenza: Copyright dell'editore
Dimensione 3.42 MB
Formato Adobe PDF
3.42 MB Adobe PDF   Visualizza/Apri   Richiedi una copia

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2108/194948
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 10
  • ???jsp.display-item.citation.isi??? 8
social impact