LRU缓存

        有人从网络读数据，有人从磁盘读数据，机智的人懂得合理利用缓存加速数据的读取效率，提升程序的性能，搏得上司的赏识，赢得白富美的青睐，进一步走向人生巅峰~

LRU假说

        LRU缓存（Least Recently Used Cache）即最近最少使用缓存算法，是一种常用的缓存淘汰策略，它基于这样一个假设：

如果数据最近被访问过，那么它在未来被访问的可能性也更高。

        因此，当缓存空间不足时，LRU缓存会优先移除最长时间未被访问的数据项。        

LRU是怎么干活的

新访问的数据添加到缓存

        当一个数据项被访问时，它会被添加到缓存中。如果该数据项已经在缓存中，它会被更新，并且移动到缓存的最前面，表示最近被访问过。

缓存满时移除最老的数据

        如果缓存已满（达到预设的容量限制），最久未被访问的数据项（位于缓存的最后面）会被移除，以便为新的数据项腾出空间。

维护访问顺序

        缓存需要维护数据项的访问顺序，以便快速确定哪些数据项是最近被访问的，哪些是最久未被访问的。

为了有效地实现LRU缓存，通常需要以下两种数据结构：         双向链表：用于维护数据项的访问顺序。最近访问的数据项位于链表一头，最久未访问的数据项位于链表另一头。当数据项被访问时，它会被移动到链表最近访问那一头。当需要移除数据项时，最久未访问的末尾数据项会被移除。         哈希表：用于存储键和指向双向链表中相应节点的指针，以便快速定位缓存中的数据项。这样可以在O(1)时间复杂度内访问缓存项。

LRU的简单示例

如下是一个简单的LRU实现：

#include <iostream> #include <list> #include <string> #include <unordered_map> #include <vector> using namespace std; template <typename K, typename V> class LRUCache { public: LRUCache(int capacity) { cap = capacity; } V get(const K& key) { auto it = hash.find(key); if (it == hash.end()) { return V(); } auto val = it->second->second; put(key, val); return val; } void put(const K& key, const V& value) { auto it = hash.find(key); if (it == hash.end()) { if (hash.size() >= cap) { auto d_it = data_list.begin(); auto h_it = d_it->first; data_list.erase(d_it); hash.erase(h_it); } } else { auto d_it = it->second; data_list.erase(d_it); hash.erase(it); } data_list.emplace_back(key, value); hash[key] = --data_list.end(); } private: int cap; list<pair<K, V> > data_list; using LIST_IT = typename list<pair<K, V> >::iterator; unordered_map<K, LIST_IT> hash; }; int main() { LRUCache<int, int> lru(2); vector<pair<string, vector<int> > > test_case = { {"put", {1, 1}}, {"put", {2, 2}}, {"get", {1}}, {"put", {3, 3}}, {"get", {2}}, {"put", {4, 4}}, {"get", {1}}, {"get", {3}}, {"get", {4}}, }; for (const auto& [opt, param] : test_case) { if (opt == "get") { auto val = lru.get(param.front()); cout << val << endl; } else { lru.put(param.front(), param.back()); } } return 0; }

运行测试用例可以得到如下结果：

code % g++ lru.cpp -std=c++17 code % ./a.out 1 0 0 3 4 code %

        如上，实现一个LRU的代码量并不算多，并且简单易懂，性能也很不错，毕竟时间复杂度为O(1)。但LRU也有其缺点，例如它没有考虑数据的访问频率。这可能会导致一些不经常使用的数据被缓存，而一些经常使用的数据被淘汰。

LRU的改进-LFU

        LFU（Least Frequently Used），即最少使用频率缓存，考虑到访问频率，而不是最近一次访问时间。其可以与LRU结合，形成其他变种，以更好地适应不同的数据访问模式。

LFU的简单示例

        例如，可以通过给LRU缓存数据项加上访问频率，当缓存满需要淘汰时，取尾部的数据选一个访问频次最低的来淘汰：

#include <iostream> #include <list> #include <string> #include <unordered_map> #include <vector> using namespace std; template <typename K, typename V> class LRUCache { public: LRUCache(int capacity) { cap = capacity; } V get(const K& key) { auto it = hash.find(key); if (it == hash.end()) { return V(); } const auto& data_tuple = *(it->second); auto val = std::get<1>(data_tuple); auto cnt = std::get<2>(data_tuple); put(key, val, cnt + 1); return val; } void put(const K& key, const V& value, int cnt = 1) { auto it = hash.find(key); if (it == hash.end()) { if (hash.size() >= cap) { remove_one_elem(); } } else { auto d_it = it->second; data_list.erase(d_it); hash.erase(it); } data_list.emplace_back(key, value, cnt); hash[key] = --data_list.end(); } private: void remove_one_elem() { auto need_rm = data_list.begin(); auto it = need_rm; for (int i = 1; i < 3 && it != data_list.end(); ++i, ++it) { if (std::get<2>(*it) < std::get<2>(*need_rm)) { need_rm = it; } } hash.erase(std::get<0>(*need_rm)); data_list.erase(need_rm); } private: int cap; list<tuple<K, V, int> > data_list; using LIST_IT = typename list<tuple<K, V, int> >::iterator; unordered_map<K, LIST_IT> hash; }; int main() { LRUCache<int, int> lru(2); vector<pair<string, vector<int> > > test_case = { {"put", {1, 1}}, {"put", {2, 2}}, {"get", {1}}, {"put", {3, 3}}, {"get", {2}}, {"put", {4, 4}}, {"get", {1}}, {"get", {3}}, {"get", {4}}, }; for (const auto& [opt, param] : test_case) { if (opt == "get") { auto val = lru.get(param.front()); cout << val << endl; } else { lru.put(param.front(), param.back()); } } return 0; }

运行测试用例可以得到如下结果：

code % g++ lfu.cpp -std=c++17 code % ./a.out 1 0 1 0 4 code %

        与LRU示例的差异点在于，当缓存满时，LFU为从最近未使用的一头，挑选一个访问频次最小的元素进行淘汰。值得注意的是，挑选最少频次并不需要遍历所有的数据，而是针对具体的业务场景，设定一个合适的值即可。

        虽然LRU开销很小，时间复杂度又是O(1)，但毕竟每次访问都需要调整链表，对于一些性能要求高的场景，负担还是有点重的，实际的使用场景中，又会根据具体的业务场景，做一些响应的改变。

衍生一下 Clock算法

        Clock算法是一种用于页面置换的缓存淘汰策略，它是LRU算法的一种近似实现，旨在降低实现LRU的开销。Clock算法有时也被称为Second-Chance算法，因为它给了每个页面一个“第二次机会”来避免被置换。

Clock是怎么干活的

        Clock算法维护一个循环链表：所有的页面都被组织成一个循环链表（或称为时钟结构），每个页面都有一个关联的访问位（通常是一个标志位），用于表示该页面自上次检查以来是否被访问过。

        使用指针指向链表中的一个页面：有一个指针（称为时钟指针）指向循环链表中的某个页面。

        维护访问位：当一个页面被访问时，其访问位被设置为1，表示该页面最近被使用过。

        缓存满时检查访问位：当有新需要加载到缓存中，但缓存已满，算法会检查当前时钟指针指向的页面的访问位。如果访问位为1，则将其清零（给予第二次机会），并将时钟指针移动到下一个页面。如果访问位为0，则选择该页面进行置换。

        Clock算法的优点是实现简单，开销较低，因为它不需要像真正的LRU算法那样在每次页面访问时都对链表进行调整。它只需要在页面置换时检查和更新访问位。这使得Clock算法特别适合于大规模的缓存系统，如操作系统的页面缓存。

        Clock算法的缺点是它不是完全精确的LRU实现，因为它可能会保留一些不太常用的页面（如果它们在时钟指针到达之前刚好被访问过）。然而，对于许多实际应用来说，Clock算法提供了一个很好的折中方案，既保留了LRU的大部分优点，又显著降低了实现的复杂性和开销。