# TinyLFU -- A Highly Efficient Cache Admission Policy

## TinyLFU: A Highly Efficient Cache Admission Policy

### 0x01 基本思路

​ 虽然论文长达31页，但是我们这里只关注其中的两个部分:

Let us emphasize that we face two main challenges. The first is to maintain a freshness mechanism in order to keep the history recent and remove old events. The second is the memory consumption overhead that should significantly be improved upon in order to be considered a practical cache management technique.

• 如何保存访问信息；
• 如何减少内存使用；

### 0x02 保存访问信息

  Every time we add an item to the approximation sketch, we increment a global counter S. Once the value of this counter S reaches the sample size (W), we divide S and all other coun- ters in the approximation sketch by two. Notice that immediately after the reset, S = W /2.

This division has two interesting merits. First, it does not require much extra space as its only added memory cost is a single counter of Loд(W ) bits. Second, this method increases the accuracy of high-frequency items as we show both analytically and experimentally.


### 0x03 减少内存使用

First, we reduce the size of each of the counters in the approximation sketch. Second, we reduce the total number of counters allocated by the sketch.


#### Small Counters

If a sketch holds W unique requests, it is required to allow counters to count until W (since in principle an item could be accessed W times in such a sample), resulting in Loд(W ) bits per counter, which can be prohibitively costly. Luckily, the combination of the reset operation and the following observation significantly reduces the size of the counters.


#### reduce the total number of counters

Doorkeeper是approximate counting scheme前面的一个bloom filter，一个元素添加的时候，如果不在这个里面，则先添加到Doorkeeper里面，如果存在，则直接添加到主结构里面。每次访问元素时，如果在Doorkeeper里面，那么就是主结构里面的数值加上1，如果不存在就只使用主结构里面的数据。这么做的原因是可以减少主结构的大小。每一次reset操作会清空Doorkeeper。

### 0x04 W-TinyLFU

W-TinyLFU近似在Tiny-LFU前面添加了小的LRU，大约只占1%的数据。用来解决突发的稀疏流量：

we employ the SLRU eviction policy (Karedla et al. 1994). The A1 and A2 regions of the SLRU policy in the main cache are divided such that 80% of the space is allocated to hot items (A2) and the victim is picked from the 20% nonhot items (A1), as recommended by (Karedla et al. 1994).


The Caffeine simulator implements the following schemes: Belady’s optimal (Belady 1966), an unbounded cache, LRU, MRU, LFU, MFU, FIFO, Random, TinyLFU, W-TinyLFU, Clock (Corbato 1968), S4LRU (Huang et al. 2013), SLRU (Karedla et al. 1994), MultiQueue (Zhou et al. 2001), Sampled LRU (Psounis and Prabhakar 2002), Sampled MRU (Psounis and Prabhakar 2002), Sampled LFU (Psounis and Prabhakar 2002), Sampled MFU (Psounis and Prabhakar 2002), Sampled FIFO (Psounis and Prabhakar 2002), 2Q (Johnson and Shasha 1994), TuQueue (OpenBSD 2014), LIRS (Jiang and Zhang 2002), Clock-Pro (Jiang et al. 2005), ARC (Megiddo and Modha 2003, 2006), CAR (Bansal and Modha 2004), and CART (Bansal and Modha 2004).


## 参考

1. Gil Einziger, Roy Friedman, and Ben Manes. 2017. TinyLFU: A Highly Efficient Cache Admission Policy. ACM Trans. Storage 13, 4, Article 35 (November 2017), 31 pages. https://doi.org/10.1145/3149371 .