TinyLFU: A Highly Efficient Cache Admission Policy

Abstract

This article proposes to use a frequency-based cache admission policy in order to boost the effectiveness of caches subject to skewed access distributions. Given a newly accessed item and an eviction candidate from the cache, our scheme decides, based on the recent access history, whether it is worth admitting the new item into the cache at the expense of the eviction candidate.

This concept is enabled through a novel approximate LFU structure called TinyLFU, which maintains an approximate representation of the access frequency of a large sample of recently accessed items. TinyLFU is very compact and lightweight as it builds upon Bloom filter theory.

We study the properties of TinyLFU through simulations of both synthetic workloads and multiple real traces from several sources. These simulations demonstrate the performance boost obtained by enhancing various replacement policies with the TinyLFU admission policy. Also, a new combined replacement and eviction policy scheme nicknamed W-TinyLFU is presented. W-TinyLFU is demonstrated to obtain equal or better hit ratios than other state-of-the-art replacement policies on these traces. It is the only scheme to obtain such good results on all traces.

References

1. Ismail Ari, Melanie Gottwals, and Dick Henze. 2006. Performance boosting and workload isolation in storage area networks with SANCache. In Proceedings of the 23rd IEEE/14th NASA Goddard Conference on Mass Storage Systems and Technologies (MSST’06). 263--273.
2. Martin Arlitt, Ludmila Cherkasova, John Dilley, Rich Friedrich, and Tai Jin. 1999. Evaluating content management techniques for web proxy caches. In Proceedings of the 2nd Workshop on Internet Server Performance.
3. Martin Arlitt, Rich Friedrich, and Tai Jin. 2000. Performance evaluation of web proxy cache replacement policies. Perform. Eval. 39, 1--4 (Feb. 2000), 149--164.
4. Hilla Atzmon, Roy Friedman, and Roman Vitenberg. 2002. Replacement policies for a distributed object caching service. In Confederated Int. Conf. DOA, CoopIS and ODBASE. 661--674.
5. Sorav Bansal and Dharmendra S. Modha. 2004. CAR: Clock with adaptive replacement. In Proceedings of the 3rd USENIX Conference on File and Storage Technologies (FAST’04). 187--200.
6. László Belady. 1966. A study of replacement algorithms for a virtual storage computer. IBM Syst. J. 5, 2 (1966), 78--101.
7. Giuseppe Bianchi, Elisa Boschi, Simone Teofili, and Brian Trammell. 2010. Measurement data reduction through variation rate metering. In Proceedings IEEE INFOCOM.
8. Giuseppe Bianchi, Nico d’Heureuse, and Saverio Niccolini. 2011. On-demand time-decaying Bloom filters for telemarketer detection. SIGCOMM Comput. Commun. Rev. 41, 5 (Oct. 2011), 5--12.
9. G. Bianchi, S. Teofili, E. Boschi, B. Trammell, and C. Greco. 2010. Scalable and fast approximate excess rate detection. In Proceedings of the Future Network and Mobile Summit.
10. Allan Borodin and Ran El-Yaniv. 1998. Online Computation and Competitive Analysis. Cambridge University Press.
11. Lee Breslau, Pei Cao, Li Fan, Graham Phillips, and Scott Shenker. 1999. Web caching and zipf-like distributions: Evidence and implications. In INFOCOM. 126--134.
12. Yu Jin Cao, Jing, Aiyou Chen, Tian Bu, and Zhi-Li Zhang. 2009. Identifying high cardinality internet hosts. In IEEE INFOCOM. 810--818.
13. Wei Koong Chai, Diliang He, Ioannis Psaras, and George Pavlou. 2012. Cache “less for more” in information-centric networks. In Proceedings of the 11th International IFIP TC 6 Conference on Networking. Springer-Verlag, 27--40.
14. Kai Cheng and Yahiko Kambayashi. 2000. LRU-SP: A size-adjusted and popularity-aware LRU replacement algorithm for web caching. In Proceedings of the 24th IEEE International Computer Software and Applications Conference (COMPSAC’00). 48--53.
15. Xu Cheng, C. Dale, and Jiangchuan Liu. 2008. Statistics and social network of youtube videos. In Proceedings of the 16th International Workshop on Quality of Service (IWQoS’08). 229--238.
16. Ludmila Cherkasova. 1998. Improving WWW Proxies Performance with Greedy-Dual-Size-Frequency Caching Policy. HP Technical Report.
17. Gregory Chockler, Guy Laden, and Ymir Vigfusson. 2010. Data caching as a cloud service. In Proceedings of the 4th ACM International Workshop on Large Scale Distributed Systems and Middleware (LADIS’10). ACM, 18--21.
18. Gregory Chockler, Guy Laden, and Ymir Vigfusson. 2011. Design and implementation of caching services in the cloud. IBM J. Res. Devel. 55, 6 (2011), 9:1--9:11.
19. Baek-Young Choi, Jaesung Park, and Zhi-Li Zhang. 2002. Adaptive random sampling for load change detection. SIGMETRICS Perform. Eval. Rev. 30, 1 ( June 2002), 272--273.
20. Edith Cohen, Haim Kaplan, and Uri Zwick. 2002. Competitive analysis of the LRFU paging algorithm. Algorithmica 33, 4 (2002), 511--516.
21. Saar Cohen and Yossi Matias. 2003. Spectral bloom filters. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 241--252.
22. F. J. Corbato. 1968. A Paging Experiment with the Multics System. Technical Report Project MAC Report MAC-M-384. MIT.
23. Graham Cormode and S. Muthukrishnan. 2004. An improved data stream summary: The count-min sketch and its applications. J. Algorithms 55 (2004), 29--38.
24. Xenofontas Dimitropoulos, Marc Stoecklin, Paul Hurley, and Andreas Kind. 2008. The eternal sunshine of the sketch data structure. Comput. Netw. 52, 17 (Dec. 2008), 3248--3257.
25. Gil Einziger, Benny Fellman, and Yaron Kassner. 2015. Independent counter estimation buckets. In Proceedings of the IEEE Conference on Computer Communications (INFOCOM’15). 2560--2568.
26. Gil Einziger and Roy Friedman. 2015a. A formal analysis of conservative update based approximate counting. In Proceedings of the International Conference on Computing, Networking and Communications (ICNC’15). 255--259.
27. Gil Einziger and Roy Friedman. 2015b. TinySet - An access efficient self adjusting bloom filter construction. In Proceedings of the 24th International Conference on Computer Communication and Networks (ICCCN’15).
28. Gil Einziger and Roy Friedman. 2016. Counting with TinyTable: Every bit counts! In Proceedings of the 17th International Conference on Distributed Computing and Networking (ICDCN’16).
29. Gil Einziger, Roy Friedman, and Yoav Kantor. 2016. Shades: Expediting Kademlias lookup process. Comput. Netw. 99 (April 2016), 37--50.
30. Cristian Estan, Ken Keys, David Moore, and George Varghese. 2004. Building a better netflow. SIGCOMM Comput. Commun. Rev. 34, 4 (Aug. 2004), 323–336.
31. Cristian Estan and George Varghese. 2002. New directions in traffic measurement and accounting. SIGCOMM Comput. Commun. Rev. 32, 4 (Aug. 2002), 323--336.
32. Li Fan, Pei Cao, Jussara Almeida, and Andrei Z. Broder. 2000. Summary cache: A scalable wide-area web cache sharing protocol. IEEE/ACM Trans. Netw. 8, 3 ( June 2000), 281--293.
33. Brad Fitzpatrick. 2004. Distributed caching with memcached. Linux J. 2004, 124 (Aug. 2004), 5.
34. Phillipa Gill, Martin Arlitt, Zongpeng Li, and Anirban Mahanti. 2007. Youtube traffic characterization: A view from the edge. In Proceedings of the 7th ACM SIGCOMM Conference on Internet Measurement (IMC’07). 15--28.
35. Amit Goyal, Hal Daumé, and Graham Cormode. 2012. Sketch algorithms for estimating point queries in NLP. In Proceedings of the Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning. 1093--1103.
36. Amit Goyal and Hal Daumeaé. 2011. Lossy conservative update (LCU) sketch: Succinct approximate count storage. In Proceedings of the 25th AAAI Conference on Artificial Intelligence.
37. Amit Goyal, Jagadeesh Jagarlamudi, Hal Daumé III, and Suresh Venkatasubramanian. 2010. Sketching techniques for large scale NLP. In Proceedings of the 6th NAACL HLT Web as Corpus Workshop (WAC’10). 17--25.
38. John L. Hennessy and David A. Patterson. 2012. Computer Architecture - A Quantitative Approach. 5th ed. Morgan Kaufmann.
39. Chengchen Hu, Bin Liu, Hongbo Zhao, Kai Chen, Yan Chen, Chunming Wu, and Yu Cheng. 2010. DISCO: Memory efficient and accurate flow statistics for network measurement. In Proceedings of the 30th IEEE International Conference on Distributed Computing Systems (ICDCS’10). 665--674.
40. Chengchen Hu, Sheng Wang, Jia Tian, Bin Liu, Yu Cheng, and Yan Chen. 2008. Accurate and efficient traffic monitoring using adaptive non-linear sampling method. In INFOCOM. IEEE, 26--30.
41. Qi Huang, Ken Birman, Robbert van Renesse, Wyatt Lloyd, Sanjeev Kumar, and Harry C. Li. 2013. An analysis of Facebook photo caching. In Proceedings of the 24th ACM Symposium on Operating Systems Principles (SOSP’13). 167--181.
42. Song Jiang, Feng Chen, and Xiaodong Zhang. 2005. CLOCK-Pro: An effective improvement of the CLOCK replacement. In Proceedings of the Annual Conference on USENIX Annual Technical Conference (ATEC’05). 35--35.
43. Song Jiang and Xiaodong Zhang. 2002. LIRS: An efficient low inter-reference recency set replacement policy to improve buffer cache performance. ACM SIGMETRICS (2002), 31--42.
44. Theodore Johnson and Dennis Shasha. 1994. 2Q: A low overhead high performance buffer management replacement algorithm. In Proceedings of the 20th International Conference on Very Large Data Bases (VLDB’94). 439--450.
45. George Karakostas and Dimitrios Serpanos. 2002. Exploitation of different types of locality for web caches. In Proceedings of the 7th International Symposium on Computers and Communications (ISCC’02).
46. Ramakrishna Karedla, J. Spencer Love, and Bradley G. Wherry. 1994. Caching strategies to improve disk system performance. IEEE Computer 27, 3 (1994), 38–46.
47. Anirban Ketan Shah and Mitra Dhruv Matani. 2010. An O(1) Algorithm for Implementing the LFU Cache Eviction Scheme. Technical Report. Retrieved from http://dhruvbird.com/lfu.pdf.
48. Piotr Kolaczkowski. 2007. Memory efficient algorithm for mining recent frequent items in a stream. In Proceedings of the International Conference on Rough Sets and Intelligent Systems Paradigms (RSEISP’07). 485--494.
49. Marc Liberatore and Prashant Shenoy. 2016. UMass Trace Repository. Retrieved from http://traces.cs.umass.edu/index.php/Main/About.
50. Yi Lu, Andrea Montanari, Balaji Prabhakar, Sarang Dharmapurikar, and Abdul Kabbani. 2008. Counter braids: A novel counter architecture for per-flow measurement. In Proceedings of the ACM SIGMETRICS International Conference on Measurement and Modeling of Computer Systems. 121--132.
51. Ben Manes. 2016. Caffeine: A High Performance Caching Library for Java 8. Retrieved from https://github.com/ben-manes/caffeine.
52. Nimrod Megiddo and Dharmendra S. Modha. 2003. ARC: A self-tuning, low overhead replacement cache. In Proceedings of the 2nd USENIX Conference on File and Storage Technologies (FAST’03). 115--130.
53. Nimrod Megiddo and Dharmendra S. Modha. 2006. System and method for implementing an adaptive replacement cache policy. US Patent 6996676, February 7.
54. Satish Narayanasamy, Timothy Sherwood, Suleyman Sair, Brad Calder, and George Varghese. 2003. Catching accurate profiles in hardware. In Proceedings of the 9th International Symposium on High-Performance Computer Architecture (HPCA’03). 269--280.
55. Elizabeth J. O’Neil, Patrick E. O’Neil, and Gerhard Weikum. 1993. The LRU-K page replacement algorithm for database disk buffering. ACM SIGMOD Rec. 22, 2 ( June 1993), 297--306.
56. OpenBSD. 2014. TuQueue. Retrieved from https://www.tedunangst.com/flak/post/2Q-buffer-cache-algorithm.
57. Stefan Podlipnig and Laszlo Böszörmenyi. 2003. A survey of web cache replacement strategies. ACM Comput. Surv. 35, 4 (Dec. 2003), 374--398.
58. Ioannis Psaras, Wei Koong Chai, and George Pavlou. 2012. Probabilistic in-network caching for information-centric networks. In Proceedings of the 2nd Edition of the ICN Workshop on Information-Centric Networking. ACM, 55--60.
59. Konstantinos Psounis and Balaji Prabhakar. 2002. Efficient randomized web-cache replacement schemes using samples from past eviction times. IEEE/ACM Trans. Netw. 10, 4 (Aug. 2002), 441--455.
60. Frederic Raspall and Sebastia Sallent. 2008. Adaptive shared-state sampling. In Proceedings of the 8th ACM SIGCOMM Conference on Internet Measurement (IMC’08). 271--284.
61. Dimitrios N. Serpanos and Wayne H. Wolf. 2000. Caching web objects using zipf’s law. In Proceedings of the IEEE International Conference on Multimedia and Expo. 727–730.
62. Rade Stanojevic. 2007. Small active counters. In Proceedings of the 26th IEEE International Conference on Computer Communications (INFOCOM’07). 2153--2161.
63. Geetika Tewari and Kim Hazelwood. 2004. Adaptive Web Proxy Caching Algorithms. Technical Report TR-13-04. Harvard University.
64. Erez Tsidon, Iddo Hanniel, and Isaac Keslassy. 2012. Estimators also need shared values to grow together. In INFOCOM. 1889--1897.
65. Guido Urdaneta, Guillaume Pierre, and Maarten van Steen. 2009. Wikipedia workload analysis for decentralized hosting. Elsevier Comput. Netw. 53, 11 ( July 2009), 1830--1845.
66. Stephen Williams, Marc Abrams, and Charles R. Standridge. 1996. Removal Policies in Network Caches for World-Wide Web Documents. In Proceedings of the ACM SIGCOMM Conference. 293–305.
67. Neal Young. 1991. On-line caching as cache size varies. In Proceedings of the 2nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’91). 241--250.
68. Yuanyuan Zhou, James Philbin, and Kai Li. 2001. The multi-queue replacement algorithm for second level buffer caches. In Proceedings of the USENIX Annual Technical Conference. 91--104.

Index Terms

• Information systems

  • Information storage systems

    • Storage management

      • Hierarchical storage management