Cited By
View all- Tan JQuan GJi KShroff N(2018)On Resource Pooling and Separation for LRU CachingProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/31794082:1(1-31)Online publication date: 3-Apr-2018
Miss behavior for caching with lease
Authors: 
Jian Tan, 
Li Zhang, Yandong WangAuthors Info & Claims
Pages 60 - 62
Abstract
Caching with lease is to evict the data record from cache after its associated lease term expires. This policy differs from the traditional caching algorithms, e.g., LRU, by introducing a dimension of time to the data record stored in the cache. This model has recently attracted increasing interest not only from a theoretical perspective, but also in real system implementation. For the related theoretical studies, lease of each data record, also known as cache characteristic time and Time-To-Live (TTL), provides a convenient approximation that can simplify the complexity in analyzing popular caching algorithms such as LRU. This approach ignores the finite capacity of the cache size and assumes the lease term to be a known parameter that matches with the measurements. Recently, with new development in system engineering, caching with lease has been shown to be an efficient way to improve the performance of RDMA based key-value stores. This engineering practice imposes new challenges for designing caching algorithms based on lease. It calls for further theoretical investigation on the lease term in presence of a finite cache capacity. To this end, we derive the miss probabilities for caching with lease compared to LRU, when the frequency of requesting a data record is equal to the generalized Zipf's law. Based on the miss probability depending on the lease term, we also discuss adaptive algorithms that can optimally determine the lease term.
References
[1]
Memcached. http://memcached.org/.
[2]
Redis. http://redis.io/.
[3]
O. Bahat and A. M. Makowski. Measuring consistency in ttl-based caches. Performance Evaluation, 62(1- 4):439--455, October 2005.
[4]
D. S. Berger, P. Gland, S. Singla, and F. Ciucu. Exact analysis of ttl cache networks. pages 2--23, Turin, Italy, October 2014.
[5]
H. Che, Y. Tung, and Z. Wang. Hierarchical Web caching systems: modeling, design and experimental results. Selected Areas in Communications, IEEE Journal on, 20(7):1305--1314, September 2002.
[6]
N. E. Choungmo Fofack, D. Towsley,M. Badov,M. Dehghan, and D. L. Goeckel. An approximate analysis of heterogeneous and general cache networks. INRIA Research Report RR-8516, April 2014.
[7]
E. Cohen, E. Halperin, and H. Kaplan. Performance aspects of distributed caches using, ttl-based consistency. Theoretical Computer Science, 331(1):73--96, February 2005.
[8]
A. Dan and D. Towsley. An approximate analysis of the lru and fifo buffer replacement schemes. In Proceedings of the 1990 ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, SIGMETRICS '90, pages 143--152, University of Colorado, Boulder, Colorado, USA, 1990. ACM.
[9]
B. Fan, D. G. Andersen, and M. Kaminsky. Memc3: Compact and concurrent memcache with dumber caching and smarter hashing. In Proceedings of the 10th USENIX Conference on Networked Systems Design and Implementation, NSDI'13, pages 371--384, Lombard, IL, 2013. USENIX Association.
[10]
J. Fill. An exact formula for the move-to-front rule for self-organizing lists. Journal of Theoretical Probability, 9(1):113--160, 1996.
[11]
P. Flajolet, D. Gardy, and L. Thimonier. Birthday paradox, coupon collectors, caching algorithms and self-organizing search. Discrete Applied Mathematics, 39(3):207--229, November 1992.
[12]
N. Fofack, P. Nain, G. Neglia, and D. Towsley. Analysis of ttl-based cache networks. In Performance Evaluation Methodologies and Tools (VALUETOOLS), 6th International Conference on, pages 1--10, October 2012.
[13]
Y. T. Hou, J. Pan, B. L. 0001, and S. S. Panwar. On expiration-based hierarchical caching systems. IEEE Journal on Selected Areas in Communications, 22(1):134--150, 2004.
[14]
P. R. Jelenković. Asymptotic approximation of the move-to-front search cost distribution and leastrecently- used caching fault probabilities. The Annals of Applied Probability, (2):430--464, 1999.
[15]
P. R. Jelenković and A. Radovanović. Least-recentlyused caching with dependent requests. Theoretical Computer Science, 326(1-3):293--327, Oct. 2004.
[16]
V. Martina, M. Garetto, and E. Leonardi. A unified approach to the performance analysis of caching systems. In Proceedings of IEEE INFOCOM, Toronto, Canada, 2014.
[17]
E. J. Rosensweig, J. Kurose, and D. Towsley. Approximate models for general cache networks. In Proceedings of the 29th Conference on Information Communications, INFOCOM'10, pages 1100--1108, San Diego, California, USA, 2010. IEEE Press.
[18]
Y. Wang, X. Meng, L. Zhang, and J. Tan. C-hint: An effective and reliable cache management for rdmaaccelerated key-value stores. In Proceedings of the ACM Symposium on Cloud Computing, SOCC '14, pages 23:1--23:13, Seattle, WA, USA, 2014. ACM.
Index Terms
- Miss behavior for caching with lease
Recommendations
Cache miss behavior: is it √2?
CF '06: Proceedings of the 3rd conference on Computing frontiersIt has long been empirically observed that the cache miss rate decreased as a power law of cache size, where the power was approximately -1/2. In this paper, we examine the dependence of the cache miss rate on cache size both theoretically and through ...
Selective Victim Caching: A Method to Improve the Performance of Direct-Mapped Caches
Although direct-mapped caches suffer from higher miss ratios as compared to set-associative caches, they are attractive for today's high-speed pipelined processors that require very low access times. Victim caching was proposed by Jouppi [1] as an ...
Miss-Correlation Folding: Encoding Per-Block Miss Correlations in Compressed DRAM for Data Prefetching
IPDPS '12: Proceedings of the 2012 IEEE 26th International Parallel and Distributed Processing SymposiumCache misses frequently exhibit repeated streaming behavior, i.e. a sequence of cache misses has a high tendency of being repeated. Correlation-based prefetchers record the missing streams in a history table for accurate prefetching. Saving a large miss ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
September 2015
79 pages
Copyright © 2015 Authors.
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 16 September 2015
Published in SIGMETRICS Volume 43, Issue 2
Check for updates
Qualifiers
- Short-paper
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 56Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 12 Nov 2024
Other Metrics
Citations
Cited By
View all- Tan JQuan GJi KShroff N(2018)On Resource Pooling and Separation for LRU CachingProceedings of the ACM on Measurement and Analysis of Computing Systems10.1145/31794082:1(1-31)Online publication date: 3-Apr-2018
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in