缓存淘汰算法的实现与应用介绍（LRU、LFU）

1. 梗概

LRU：时间；每次将访问的key放到链表的最前面，若需要删除一个key，则删除的是链表最末尾的节点。

LFU：频率；每访问一次key1，就给key1使用频率加一，频率越高，越排在链表的前面，越不容易被删除；若两个key访问频率一致，则最近访问的key排在前面。

缺点：LFU容易饿，若有一种情况：某一段时间某一个key被访问了很多次，但后面几乎不被访问，但还是占据着链表的前面位置

LRU：当存在热点数据时,LRU的效率很好,但偶发性的,周期性的批量操作会导致LRU命中率急剧下降,缓存污染情况比较严重。

2. 背景

在互联网应用中，玩家的数据都被存储在数据库中，但是对于很多访问频繁的服务，如果每次都直接读写数据库，数据的性能远远达不到要求。于是需要将尽可能多的常用的数据缓存在服务器的内存中。需要访问数据时，直接存取内存中的缓存数据，只有当内存中的数据不存在时，才需要从数据库拉取，并将新拉取的数据放入缓存中。

随着被放入缓存中的数据越来越多，占用的内存也就越大，最终内存会被耗光。因此需要给缓存设置一个上限，当达到这个上限的时候，每当需要添加一条新的数据，就需要按照一定的规则淘汰掉一条旧的数据。

淘汰哪一条数据呢？相关的策略就叫缓存淘汰算法(Cache Eviction Algorithm或Cache Replacement Algorithm)，缓存淘汰算法有很多种，本文介绍两个，LRU和LFU。

LRU全称Least recently used，意思为淘汰掉最久未使用（即最老）的一条数据；LFU全称Least-frequently used，意思为淘汰掉过去被访问次数最少的一条数据。LRU在服务器缓存中经常有用武之地，它有非常成熟的O(1)复杂度的实现方法；LFU也有O(1)的实现方法，它的实现方法是受到LRU实现方法的启发。

LRU/LFU的实现也可以回答很多初学编程的人关于链表的一个疑惑：链表到底有何用？只能用来做题面试吗？ 其实链表在很多应用中都有不可替代的作用。在LRU/LFU的O(1)实现中就是如此。

在本文中，名词hashmap指的就是STL中的unordered_map。

1. LRU(Least recently used)

先来看LRU。要对每个数据实现O(1)的访问，肯定需要将每条数据保存在hashmap中。另一个需要实现的功能，是要快速区分哪条数据是最老的。

区分新老数据用的是一条双向链表，链表的头部为最老数据、尾部为最新数据（也可以反过来，只要代码的实现和这个规则统一即可）。如下图所示：

hashmap的value除了保存数据的值，还保存了该对应的key在双向链表中的指针（可以直接用list的iterator）。双向链表中，头节点（即最左边的节点）为最老的数据，尾节点（即最右边的节点）为最新的数据。

可以这样定义hashmap的value：

struct MapValue {   	int value;   	list
   
    ::iterator node_list_iter; };LRU的定义如下：class LRU { 	public:   		LRU(size_t capacity):capacity_(capacity) {}   		optional
    
      Get(int key) {  //查找数据，如果查到，则也需要置为最新   }   		void Set(int key, int value) {     //添加或修改value   }     private:            const size_t capacity_;     //LRU最多缓存多少条数据            unordered_map
     
       map_;            list
      
        list_;             // 链表，存储每个节点的key。头节点为最老的节点，尾节点为最新 };

将数据添加到hashmap中时，因为该数据肯定是最新，所以同时将该key放到双向链表的尾部，并将hashmap中的value的iterator设置为刚刚添加的尾节点。

void LRU::Set(int key, int value) {       // 先查找该节点是否存在      auto it = map_.find(key);       if(it == map_.end()) { // 不存在，插入数据             // 插入数据之前，要看看数据是否已满，如果已满，需要淘汰最老数据             if(map_.size() >= capacity_) {                   map_.erase(list_.front());                   list_.erase(list_.begin());             }             auto&& [it2, b] = map_.insert(make_pair(key, MapValue{value}));             assert(b);             it = it2;       } else {         // 存在             list_.erase(it->second.node_list_iter);       }   // 将该key对应的value设置为新的值，并将该key设置为最新(既放入链表末尾)       it->second.node_list_iter = list_.insert(list_.end(), key);       it->second.value = value; }

查询数据时，注意任何一个key被访问，表示也需要将它设置为最新。先通过hashmap的key查到MapValue，然后通过MapValue中的iterator值查到它在链表中的位置，再根据这个iterator将该key从链表中删除，最后重新添加到链表的末尾。

optional
   
     LRU::Get(int key) {   	auto it = map_.find(key);   	if(it == map_.end()) {     		return {};   }   		// 找到了，因为本次访问，该key对应的数据变为最新   	list_.erase(it->second.node_list_iter);   	it->second.node_list_iter = list_.insert(list_.end(), key);   	return it->second.value; }

还有一个知识点就是淘汰节点的算法(在上面的Set函数中)，向LRU中添加数据时，如果当前的缓存已满（即当前缓存的数据条数达到指定的值），需要淘汰最老的数据，即删除链表的头节点，同时从hashmap中删除头结点对应的key。

以上3个操作均为O(1)，因此，LRU的复杂度为O(1)。

2. LFU(Least-frequently used)

再来看LFU，它的实现稍微复杂一些。对于每个访问次数相同的所有节点，分别用一条链表串起来，头部为最老、尾部为最新，和LRU一样。也就是说，如果当前有N个不同的访问次数，则有N条这样的链表。

同时，将每一条链表对象以及对应的访问次数用另一个链表串起来，我把这条链表叫CountList。如下图所示：

CountList的头节点存储访问次数最少的数据，需要淘汰时，在这个节点里面去找相关的数据。这个节点对应的链表中，按照从旧到新存储每个数据，这个和LRU一样，该链表的头结点就是需要淘汰的数据。

struct ListNode; // CountList对应的节点数据struct CountListNode {   	int count;   	list
   
     node_list; }; // CountList每个节点对应的链表所存储的数据类型 struct ListNode {   	int key;   	list
    
     ::iterator count_list_iter; }; // hashmap每个value的数据类型 struct MapValue {   	int value;   	list
     
      ::iterator node_list_iter; };

LFU定义如下：

class LFU {     private:       	unordered_map
   
     map_;       	list
    
      count_list_; // CountList      		const size_t max_size_; // 缓存数据的最大上限     public:       	LFU(size_t size):max_size_(size) { }       	void Put(int k, int v) {             	// 添加或修改数据             	// 若是添加，将其count设置为1             	// 如果是修改，则将其count加1   }           	optional
     
       Get(int k) {     // 查找数据，如果找到，则需要将该数据的count加1   } };

CountList中的节点是按照count从小到大排序的，尾节点访问次数最多。

新添加数据时，该数据的访问次数是1，直接添加到count=1的链表中。

当每个数据被访问时，需要将它的访问次数加1，即从count=n的链表中删除，然后添加到count=n+1的链表尾部。

以上每个操作都是O(1)的复杂度，因此整个LFU的复杂度为O(1)。

3. 后记

在服务器开发中，但是到底缓存多少数据？如果不能说什么越多越好的话，以什么为参考呢？

互联网中有一个名词DAU(Daily Active User)，即日活跃用户数量，即每天至少使用过一次该产品的用户数量。每个产品的DAU可以在上线前预估、在上线后统计。

假设某个产品的DAU是200万，则可以缓存200万条数据。此后每天每个用户的数据最多被从数据库中拉取一次，将数据库的压力大大减小。

当然，对于数据的修改，需要将缓存中发生变化的数据定时回写到数据库中。至于多久回写一次，需要在数据的重要性和数据库的性能之间作一个平衡。一般几分钟回写一次就可以。

LRU和LFU都展示了链表的威力!

https://github//franktea//treehouse

转载地址：http://rmwki.baihongyu.com/

你可能感兴趣的文章