tinylfu_cached/cache/lfu/
tiny_lfu.rs

1use log::{debug, info};
2
3use crate::cache::lfu::doorkeeper::DoorKeeper;
4use crate::cache::lfu::frequency_counter::FrequencyCounter;
5use crate::cache::types::{DoorKeeperCapacity, FrequencyEstimate, KeyHash, TotalCounters};
6
7/// TinyLFU maintains determines the key access frequencies.
8/// It contains a `FrequencyCounter` and a `DoorKeeper` where `FrequencyCounter` is an implementation of
9/// count-min sketch data structure and `DoorKeeper` is an implementation of bloom filter.
10/// More on these data structures is available on the following links:
11    /// https://tech-lessons.in/blog/count_min_sketch/
12    /// https://tech-lessons.in/blog/bloom_filter/
13/// Both these data structures work on the hash of the key. All the methods in these abstraction accept `KeyHash` or a `Vec<KeyHash>`.
14pub(crate) struct TinyLFU {
15    key_access_frequency: FrequencyCounter,
16    door_keeper: DoorKeeper,
17    total_increments: u64,
18    reset_counters_at: u64,
19}
20
21impl TinyLFU {
22    pub(crate) fn new(counters: TotalCounters) -> TinyLFU {
23        let tiny_lfu = TinyLFU {
24            key_access_frequency: FrequencyCounter::new(counters),
25            door_keeper: DoorKeeper::new(counters as DoorKeeperCapacity, 0.01),
26            total_increments: 0,
27            reset_counters_at: counters,
28        };
29        info!(
30            "Initialized TinyLFU with total counters {} ,bloom filter capacity {} and reset_counters_at {}",
31            counters, counters, counters);
32
33        tiny_lfu
34    }
35
36    pub(crate) fn increment_access(&mut self, key_hashes: Vec<KeyHash>) {
37        key_hashes.iter().for_each(|key_hash| self.increment_access_for(*key_hash));
38    }
39
40    /// Estimates the frequency of the given key_hash.
41    /// If the doorkeeper already contains the key, the access is incremented by 1.
42    /// [TinyLFU](https://dgraph.io/blog/refs/TinyLFU%20-%20A%20Highly%20Efficient%20Cache%20Admission%20Policy.pdf)
43    /// The key will be added to the doorkeeper if is is accessed.
44    /// That means, if the same key is accessed twice, it will be added to the doorkeeper on the first access.
45    pub(crate) fn estimate(&self, key_hash: KeyHash) -> FrequencyEstimate {
46        let mut estimate = self.key_access_frequency.estimate(key_hash);
47        if self.door_keeper.has(&key_hash) {
48            estimate += 1;
49        }
50        estimate
51    }
52
53    pub(crate) fn clear(&mut self) {
54        debug!("Clearing tinyLFU");
55        self.total_increments = 0;
56        self.key_access_frequency.clear();
57        self.door_keeper.clear();
58    }
59
60    /// Increments the access for the given key_hash.
61    /// The first access of the key will result in an entry in the doorkeeper and
62    /// subsequent accesses will find the key in the doorkeeper and hence increment the access in the `FrequencyCounter`.
63    fn increment_access_for(&mut self, key_hash: KeyHash) {
64        let added = self.door_keeper.add_if_missing(&key_hash);
65        if !added {
66            self.key_access_frequency.increment(key_hash);
67        }
68        self.total_increments += 1;
69        if self.total_increments >= self.reset_counters_at {
70            self.reset();
71        }
72    }
73
74    fn reset(&mut self) {
75        debug!("Resetting tinyLFU");
76        self.total_increments = 0;
77        self.key_access_frequency.reset();
78        self.door_keeper.clear();
79    }
80}
81
82#[cfg(test)]
83mod tests {
84    use crate::cache::lfu::tiny_lfu::TinyLFU;
85
86    #[test]
87    fn increment_frequency_access_for_keys() {
88        let mut tiny_lfu = TinyLFU::new(10);
89        tiny_lfu.increment_access(vec![10, 10, 10, 20]);
90
91        assert_eq!(3, tiny_lfu.estimate(10));
92        assert_eq!(1, tiny_lfu.estimate(20));
93    }
94
95    #[test]
96    fn increment_frequency_access_for_keys_if_doorkeeper_already_has_some_keys() {
97        let mut tiny_lfu = TinyLFU::new(10);
98        tiny_lfu.door_keeper.add_if_missing(&10);
99
100        tiny_lfu.increment_access(vec![10, 10, 10, 20]);
101
102        assert_eq!(4, tiny_lfu.estimate(10));
103        assert_eq!(1, tiny_lfu.estimate(20));
104    }
105
106    #[test]
107    fn total_increments() {
108        let mut tiny_lfu = TinyLFU::new(10);
109        tiny_lfu.increment_access(vec![10, 10, 10, 20]);
110
111        assert_eq!(4, tiny_lfu.total_increments);
112    }
113
114    #[test]
115    fn reset() {
116        let mut tiny_lfu = TinyLFU::new(2);
117        tiny_lfu.increment_access(vec![10, 10]);
118
119        assert_eq!(0, tiny_lfu.total_increments);
120    }
121}
tinylfu_cached/cache/lfu/tiny_lfu.rs

tinylfu_cached/cache/lfu/
tiny_lfu.rs
