想进大厂、想提升底层功力、想搞懂LRU缓存，这一篇就够了！

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

class LRUCache
{
//01-定义数据结构
private:
    int MaxCapacity; // 缓冲区的最大容量
    int size;        // 缓冲区使用的大小
    struct DoubleListNode {
        int key;
        int value;
        DoubleListNode* prev;
        DoubleListNode* next;
        DoubleListNode(int k,int v) : key(k), value(v),   prev(nullptr), next(nullptr) {}

    };

    map<int,DoubleListNode*> cache; // 缓存，key为数据的key，value为双向链表节点
    DoubleListNode* phead; // 头结点
    DoubleListNode* ptail; // 尾结点

//02 定义算法
public:
    LRUCache(int capacity)
    {
        MaxCapacity = capacity;

        size = 0;

        phead =new DoubleListNode(0, 0); // 初始化头结点

        ptail = new DoubleListNode(0, 0); // 初始化尾结点

        phead->next =ptail; // 头结点的下一个指向尾结点

        ptail->prev =phead; // 尾结点的前一个指向头结点

        //这样设计好处，不用判断是否空节点

    }

    int get(int key)
    {
      if (cache.find(key) == cache.end())
      {
        return -1; // 如果key不存在，返回-1

      } else {
        DoubleListNode *node = cache[key]; // 获取节点

        deleteNode(node);

        insertToHead(node);

        return node->value; // 返回节点的值
      } //思考如何避免频繁的移动节点

    }

    void put(int key, int value) {

     //判断key存在

      if (cache.find(key) != cache.end()) {

            DoubleListNode *node = cache[key]; // 获取节点

            node->value = value; // 更新节点的值

            deleteNode(node);

            insertToHead(node);

            return ;

      }
      //超过最大容量,删除不经常使用的节点

      //链表最后最后一个节点是不经常使用的节点

      if (size >= MaxCapacity) {

        DoubleListNode *pcur = ptail->prev; // 获取尾结点的前一个节点

        deleteNode(pcur);

        cache.erase(pcur->key);

        delete pcur; // 删除节点

        size--; // 缓冲区大小减1

      }

      //插入一个元素

      DoubleListNode *ptemp = new DoubleListNode(key,value);

      cache[key] = ptemp; // 将新节点加入缓存

      //将新节点插入到头结点后面

      insertToHead(ptemp);

      size++; // 缓冲区大小加1

    }
private:

      void deleteNode(DoubleListNode* cur) {

        if (nullptr == cur) return;

        cur->prev->next  = cur->next;

        cur->next->prev = cur->prev;

        // cache.erase(cur->key); // 从缓存中删除

        // delete cur; // 删除节点

        // size--; // 缓冲区大小减1

      }
      void insertToHead(DoubleListNode* cur) {

        cur->next = phead->next; // 新节点的下一个指向头结点的下一个

        phead->next->prev = cur; // 头结点的下一个的前一个指向新节点

        phead->next = cur; // 头结点的下一个指向新

        cur->prev = phead; // 新节点的前一个指向头结点

        // size++; // 缓冲区大小加1

      }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

#include <list>
#include <unordered_map>
using namespace std;

class LRUCache {
    int capacity;
    list<pair<int, int>> cache; // {key, value}
    unordered_map<int, list<pair<int, int>>::iterator> map; 
    // key -> list迭代器
    //https://en.cppreference.com/w/cpp/container/list.html
    //std：：list 是一个容器，
    //它支持从容器中的任何位置插入和删除元素的恒定时间。
    //不支持快速随机访问。它通常实现为双向链表
public:
    LRUCache(int capacity) : capacity(capacity) {}

    int get(int key) {
        auto it = map.find(key);
        if (it == map.end()) return -1;
        // 移动到头部
        cache.splice(cache.begin(), cache, it->second);
        return it->second->second;
    }

    void put(int key, int value) {
        auto it = map.find(key);
        if (it != map.end()) {
            // 更新并移到头部
            it->second->second = value;
            cache.splice(cache.begin(), cache, it->second);
        } else {
            if (cache.size() == capacity) {
                // 淘汰尾部
                int oldKey = cache.back().first;
                cache.pop_back();
                map.erase(oldKey);
            }
            cache.emplace_front(key, value);
            map[key] = cache.begin();
        }
    }
};
https://www.nextptr.com/tutorial/ta1576645374/stdlist-splice-for-implementing-lru-cache

https://leetcode.cn/problems/lru-cache-lcci/solutions/3617249/clrushi-xian-by-ooo-4h-5qff/

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

struct Node {
    Key key;
    Value value;
    std::atomic<Node*> prev, next;
    std::atomic<bool> valid;
};

std::atomic<Node*> head, tail;
std::unordered_map<Key, Node*> index; // 需要替换成 lock-free map

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

// ...existing code...
typedef struct redisDb {
    dict *dict;                 /* The keyspace for this DB */
    // ...existing code...
} redisDb;
 C 语言没有这种数据结构， 需要自定义

typedef struct dictEntry {
    void *key;               // 指向 key 的指针（通常是 sds 类型）
    void *val;               // 指向 value 的指针
    struct dictEntry *next;  // 用于处理哈希冲突的链表指针
} dictEntry;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

struct redisObject 
{

    unsigned type:4;

    unsigned encoding:4;

    unsigned lru:LRU_BITS; /* LRU time (relative to global lru_clock) or

                            * LFU data (least significant 8 bits frequency

                            * and most significant 16 bits access time). */

    unsigned iskvobj : 1;   /* 1 if this struct serves as a kvobj base */

    unsigned expirable : 1; /* 1 if this key has expiration time attached.

                             * If set, then this object is of type kvobj */

    unsigned refcount : OBJ_REFCOUNT_BITS;

    void *ptr;

};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

// 伪代码，实际实现更复杂
dictEntry *dictGetFairRandomKey(dict *d) {
    dictEntry *entry = NULL;
    int tries = 100; // 最多尝试次数
    while (tries--) {
        // 随机选一个哈希桶
        unsigned long idx = random() % d->ht[0].size;
        entry = d->ht[0].table[idx];
        if (entry) break;
    }
    // 如果没采到，fallback 到 dictGetRandomKey
    if (!entry) return dictGetRandomKey(d);
    // 桶内有冲突链表，随机选一个
    int listlen = 0;
    dictEntry *e = entry;
    while (e) { listlen++; e = e->next; }
    int skip = random() % listlen;
    e = entry;
    while (skip--) e = e->next;
    return e;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

1. 系统启动
 → Buffer Pool 初始化
 → LRU 链表为空，old/young 未构建成功

2. 访问数据页 P
 → 不存在缓冲中，加载到内存
 → 插入 Old 区头
 → LRU 链表增长

3. 重复大表扫描
 → 访问各页，均插到 Old 区头
 → 1 秒内访问同页多次也不晋升
 → LRU 震荡在 Old 区

4. 内存满了，触发淘汰
 → 淘汰 Old 区尾部页
 → Hot 页留在 Young，未被影响

5. 热点访问重现
 → 访问 Young 或晋升 Old 页
 → Hot 页集中，系统恢复响应率

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

struct LRUHandle {
  // 存储的 value 对象的指针，可以存储任意类型的值
  void* value;
  
  // 当引用计数 `refs` 降为 0 时的清理函数
  void (*deleter)(const Slice&, void* value);
  
  // 哈希表通过链地址法解决哈希冲突，发生哈希冲突时指向下一个 entry
  LRUHandle* next_hash;
  
  // LRU 链表双向指针
  LRUHandle* next;
  LRUHandle* prev;
  
  // 分配的可以消耗的内存量
  size_t charge;
  
  // key 的字节数
  size_t key_length;
  
  // entry 是否存在缓存中
  bool in_cache; 
  
  // 引用计数，记录 entry 被不同缓存的引用，用于 entry 删除
  uint32_t refs;
  
  // `key()` 对应的哈希，用于快速分区和比较
  uint32_t hash;
  
  // 存储 key 的开始地址，结合 `key_length` 获取真正的 key 
  // GCC 支持 C99 标准，允许定义 char key_data[] 这样的柔性数组（Flexible Array)。
  // C++ 标准并不支持柔性数组的实现，这里定义为 key_data[1]，这也是 c++ 中的标准做法。
  char key_data[1];
  Slice key() const {
    // 只有当当前节点是空链表头时，`next` 才会等于 `this`
    // 链表是循环双向链表，空链表的头节点 next 和 prev 都指向自己构成环
    // 链表头是冗余的 handle，不存储数据，只利用它的 next 和 prev
    assert(next != this);
    return Slice(key_data, key_length);
  }
};

参考：https://blog.mrcroxx.com/posts/code-reading/leveldb-made-simple/7-cache/

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

LRU算法的实现
class LUR
{
	using LRUList = xlist<LRUObject*>;
	LRUList top, bottom, pintail;  //定义三个链表，而不是一个链表
}
 `top`链表代表最近访问的对象链表。当缓存对象被插入/访问时，这个对象会被放到`top`链表的头部。
`bottom`链表代表较早之前访问过的对象列表。当`top`链表满了或达到某这阈值，就会把`top`链表尾部的对象添加到`bottom`链表的头部。从缓存中淘汰对象时，从`bottom`尾部开始淘汰。


 // insert at top of lru

  void lru_insert_top(LRUObject *o) 
  {
    o->lru = this; //class LUR
    top.push_front(&o->lru_link);
  }
 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class LRUObject {
public:
  friend class LRU;
private:
  class LRU *lru; // LRU算法的真正实现者
  xlist<LRUObject *>::item lru_link; // 记录自己在双向链表里的位置，移动或删除对象时，操作会很快
  bool lru_pinned;
  
  inline LRUObject::~LRUObject() 
  {
	  if (lru) {
	    lru->lru_remove(this);
	  }
   }//# c++ new(this)
};