系统内存紧张的时候，就会进行回收内存的工作。主要有文件页和匿名页两种内存可以回收。文件页和匿名页的回收都是基于 LRU 算法，也就是优先回收不常访问的内存。

LRU (最近最少使用) 缓存

LRU 的实现是一个哈希表加上一个双链表。

具体实现

我个人觉得最核心的一点是 records.remove(removedNode.key); 这一行代码，要从哈希表中删除被淘汰的元素。

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
// LRU 的 Java 实现
// https://leetcode.cn/problems/lru-cache/

class LRUCache {

    int size;  // 真实大小
    int capacity;  // 最大容量
    Node head;
    Node tail;

    Map<Integer, Node> records;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.size = 0;
        this.head = new Node();
        this.tail = new Node();
        this.head.next = this.tail;
        this.tail.prev = this.head;

        this.records = new HashMap<>();
    }
    
    public int get(int key) {
        if (!records.containsKey(key)) {
            return -1;
        }
        Node node = records.get(key);
        moveToHead(node);
        return node.val;
    }
    
    public void put(int key, int value) {
        if (!records.containsKey(key)) {
            // 节点不存在
            Node node = new Node(key, value);
            records.put(key, node);
            size++;
            addToHead(node);
            if (size > capacity) {
                Node removedNode = removeTail();
                records.remove(removedNode.key);
                size--;
            }
        } else {
            // 节点存在
            Node node = records.get(key);
            node.val = value;
            moveToHead(node);
        }
    }

    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }

    private void removeNode(Node node) {
        node.next.prev = node.prev;
        node.prev.next = node.next;
    }

    private void addToHead(Node node) {
        node.next = this.head.next;
        node.prev = this.head;
        this.head.next = node;
        node.next.prev = node;
    }

    private Node removeTail() {
        Node node = this.tail.prev;
        this.tail.prev = node.prev;
        node.prev.next = this.tail;
        return node;
    }
}

class Node {
    int key;
    int val;

    Node prev;
    Node next;
    
    public Node() { }
    public Node(int key, int value) {
        this.key = key;
        this.val = value;
    }
}

如何改进 LRU 算法

传统的 LRU 算法存在这两个问题：

  • 「预读失效」导致缓存命中率下降。（OS 在读磁盘时会额外多读一些数据，但是最后这些数据并没有被用到）
  • 「缓存污染」导致缓存命中率下降。（批量读数据可能会把热点数据挤出去）
    Redis 的缓存淘汰算法则是通过实现 LFU 算法来避免「缓存污染」而导致缓存命中率下降的问题（Redis 没有预读机制）。

MySQL 和 Linux 操作系统是通过改进 LRU 算法来避免「预读失效和缓存污染」而导致缓存命中率下降的问题。

本节重点讲讲 MySQL 和 Linux 操作系统是如何改进 LRU 算法的。

预读失效

预读机制使得内核从磁盘加载页时，会提前把它相邻的页一并加载进来，目的是为了减少磁盘 IO。

预读失效是如果这些被提前加载进来的页，并没有被访问。

要避免预读失效带来影响，最好就是让预读页停留在内存里的时间要尽可能的短，让真正被访问的页才移动到 LRU 链表的头部，从而保证真正被读取的热数据留在内存里的时间尽可能长。

Linux 操作系统实现两个了 LRU 链表：活跃 LRU 链表（active_list）和非活跃 LRU 链表（inactive_list）；从而将数据分为了冷数据和热数据，然后分别进行 LRU 算法。

  • active list 活跃内存页链表，这里存放的是最近被访问过（活跃）的内存页；
  • inactive list 不活跃内存页链表，这里存放的是很少被访问（非活跃）的内存页；

缓存污染

如果还是使用「只要数据被访问一次，就将数据加入到活跃 LRU 链表头部（或者 young 区域）」这种方式的话，那么还存在缓存污染的问题。

例如，当我们在批量读取数据的时候，由于数据被访问了一次，这些大量数据都会被加入到「活跃 LRU 链表」里，然后之前缓存在活跃 LRU 链表（或者 young 区域）里的热点数据全部都被淘汰了，如果这些大量的数据在很长一段时间都不会被访问的话，那么整个活跃 LRU 链表（或者 young 区域）就被污染了。

注意， 缓存污染并不只是查询语句查询出了大量的数据才出现的问题，即使查询出来的结果集很小，也会造成缓存污染。

例如，MySQL 在进行全表扫描查询（结果集很小）的时候，从磁盘中读到页并加载到 LRU 链表中，替换掉了热点数据，造成缓存污染。

所以，只要我们提高进入到活跃 LRU 链表（或者 young 区域）的门槛，就能有效地保证活跃 LRU 链表（或者 young 区域）里的热点数据不会被轻易替换掉。

Linux 操作系统在内存页被访问第二次的时候，才将页从 inactive list 升级到 active list 里。这样做很好地避免缓存污染带来的影响。

LFU (最不经常使用缓存算法)

缓存的淘汰算法：

  • LRU(Least Recently Used) 最近最少使用算法，它是根据时间维度来选择将要淘汰的元素，即删除掉最长时间没被访问的元素。
  • LFU(Least Frequently Used) 最近最不常用算法，它是根据频率维度来选择将要淘汰的元素，即删除访问频率最低的元素。如果两个元素的访问频率相同，则淘汰最久没被访问的元素。

也就是说LFU淘汰的时候会选择两个维度，先比较频率，选择访问频率最小的元素；如果频率相同，则按时间维度淘汰掉最久远的那个元素。

LFU 的实现是基于两个哈希表

LRU的实现是一个哈希表加上一个双链表；而LFU则要复杂多了，需要用两个哈希表再加上N个双链表才能实现。

  • 第一个哈希表是key-value的哈希表
    • key: 输入的key
    • value: 节点对象Node包含了key，value，以及频率
  • 第二张哈希表是频率哈希表
    • key：频率，即节点被访问的次数
    • value: 双向链表

get 操作

get操作的具体逻辑大致是这样：

  • 如果key不存在则返回-1
  • 如果key存在，则返回对应的value，同时:
    • 将元素的访问频率+1
      • 将元素从访问频率i的链表中移除，放到频率i+1的链表中
      • 如果频率i的链表为空，则从频率哈希表中移除这个链表

put 操作

put操作就要复杂多了，大致包括下面几种情况

  • 如果key已经存在，修改对应的value，并将访问频率+1
    • 将元素从访问频率i的链表中移除，放到频率i+1的链表中
    • 如果频率i的链表为空，则从频率哈希表中移除这个链表
  • 如果key不存在
    • 缓存超过最大容量，则先删除访问频率最低的元素，再插入新元素
      • 新元素的访问频率为1，如果频率哈希表中不存在对应的链表需要创建
    • 缓存没有超过最大容量，则插入新元素
      • 新元素的访问频率为1，如果频率哈希表中不存在对应的链表需要创建

我们在代码实现中还需要维护一个minFreq的变量，用来记录LFU缓存中频率最小的元素，在缓存满的时候，可以快速定位到最小频繁的链表，以达到 O(1) 时间复杂度删除一个元素。 具体做法是:

  • 更新/查找的时候，将元素频率+1，之后如果minFreq不在频率哈希表中了，说明频率哈希表中已经没有元素了，那么minFreq需要+1，否则minFreq不变。
  • 插入的时候，这个简单，因为新元素的频率都是1，所以只需要将minFreq改为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
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
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
import java.util.HashMap;
import java.util.Map;

/**
 *    自定义的LFU缓存类 
 */
public class LFUCache {
    /**
     *    双链表中的链表节点对象
    */
    protected static class Node{
        //对应输入的key
        private final int key;
		
        //对应输入的value
        private int value;
		
        //被访问的频率
        private int freq;
		
        //指向前一个节点的指针
        protected Node pre;
		
        //指向后一个节点的指针
        protected Node next;
		
        public Node(int key, int value, int freq) {
            this.key = key;
            this.value = value;
            this.freq = freq;
        }
		
        public Node(int key, int value, int freq, Node pre, Node next) {
            this.key = key;
            this.value = value;
            this.freq = freq;
            this.pre = null;
            this.next = null;
        }
		
        public void updateValue(int value) {
            this.value = value;
        }
		
        public void incrFreq() {
            ++this.freq;
        }
		
        public int getKey() {
            return this.key;
        }
		
        public int getValue() {
            return this.value;
        }
		
        public int getFreq() {
            return this.freq;
        }
		
        public static final Node createEmptyNode() {
            return new Node(-1,-1,-1,null,null);
        }
    }

    /**
     *  自定义的双向链表类
    */
    protected static class LinkedList {
        //双向链表的头结点
        private final Node head;
		
        //双向链表的尾节点
        private final Node tail;
        public LinkedList() {
            this.head = Node.createEmptyNode();
            this.tail = Node.createEmptyNode();
            this.head.next = this.tail;
            this.tail.pre = this.head;
        }
		
        /**
         * 将指定的节点插入到链表的第一个位置
         * @param node 将要插入的节点
        */
        public void insertFirst(Node node) {
            if(node==null) {
                throw new IllegalArgumentException();
            }
            node.next = this.head.next;
            this.head.next.pre = node;
            node.pre = this.head;
            this.head.next = node;
        }
		
        /**
         * 从链表中删除指定的节点
         * @param node 将要删除的节点
        */
        public void deleteNode(Node node) {
            if(node==null) {
                throw new IllegalArgumentException();
            }
            node.pre.next = node.next;
            node.next.pre = node.pre;
            node.pre = null;
            node.next = null;
        }
		
        /**
         * 从链表中获取最后一个节点
         * @return 双向链表中的最后一个节点，如果是空链表则返回None
        */
        public Node getLastNode() {
            if(this.head.next==this.tail) {
                return Node.createEmptyNode();
            }
            return this.tail.pre;
        }
		
        /**
         * 判断链表是否为空，除了head和tail没有其他节点即为空链表
         * @return 链表不空返回True，否则返回False
        */
        public boolean isEmpty() {
            return this.head.next==this.tail;
        }
    }	
	
    //key->Node 这种结构的哈希表
    private final Map<Integer,Node> keyMap = new HashMap<Integer,Node>();
	
    //freq->LinkedList 这种结构的哈希表
    private final Map<Integer,LinkedList> freqMap = new HashMap<Integer,LinkedList>();
	
    //缓存的最大容量
    private final int capacity;
	
    //记录缓存中最低频率
    private int minFreq = 0;
	
    public LFUCache(int capacity) {
//		if(capacity<=0) {
//			throw new IllegalArgumentException();
//		}
        this.capacity = capacity;
    }
    
    /**
     * 获取一个元素，如果key不存在则返回-1，否则返回对应的value，同时更新被访问元素的频率
     * @param key 要查找的关键字
     * @return 如果没找到则返回-1，否则返回对应的value
     */
    public int get(int key) {
        if(!this.keyMap.containsKey(key)) {
            return -1;
        }
        Node node = this.keyMap.get(key);
        this.increment(node);
        return node.getValue();
    }
    
    /**
     * 插入指定的key和value，如果key存在则更新value，同时更新频率，
     * 如果key不存并且缓存满了，则删除频率最低的元素，并插入新元素。否则，直接插入新元素
     * @param key 要插入的关键字
     * @param value 要插入的值
     */
    public void put(int key, int value) {
        if(this.keyMap.containsKey(key)) {
            Node node = this.keyMap.get(key);
            node.updateValue(value);
            this.increment(node);
        }
        else {
            if(this.capacity==0) {
                return;
            }
            if(this.keyMap.size()==this.capacity) {
                this.remoteMinFreqNode();
            }
            Node node = new Node(key,value,1);
            this.increment(node,true);
            this.keyMap.put(key, node);
        }
    }
    

    /**
     * 更新节点的访问频率
     * @param node 要更新的节点
     */
    private void increment(Node node) {
        increment(node,false);
    }
    
    /**
     * 更新节点的访问频率
     * @param node 要更新的节点
     * @param isNewNode 是否是新节点，新插入的节点和非新插入节点更新逻辑不同
     */
    private void increment(Node node,boolean isNewNode) {
        if(isNewNode) {
            this.minFreq = 1;
            this.insertToLinkedList(node);
        }
        else {
            this.deleteNode(node);
            node.incrFreq();
            this.insertToLinkedList(node);
            if(!this.freqMap.containsKey(this.minFreq)) {
                ++this.minFreq;
            }
        }
    }
    
    /**
     * 根据节点的频率，插入到对应的LinkedList中，如果LinkedList不存在则创建
     * @param node 将要插入到LinkedList的节点
     */
    private void insertToLinkedList(Node node) {
        if(!this.freqMap.containsKey(node.getFreq())) {
            this.freqMap.put(node.getFreq(), new LinkedList());
        }
        LinkedList linkedList = this.freqMap.get(node.getFreq());
        linkedList.insertFirst(node);
    }
    
    /**
     * 删除指定的节点，如果节点删除后，对应的双链表为空，则从__freqMap中删除这个链表
     * @param node 将要删除的节点
     */
    private void deleteNode(Node node) {
        LinkedList linkedList = this.freqMap.get(node.getFreq());
        linkedList.deleteNode(node);
        if(linkedList.isEmpty()) {
            this.freqMap.remove(node.getFreq());
        }
    }
    
    /**
     * 删除频率最低的元素，从freqMap和keyMap中都要删除这个节点，
     * 如果节点删除后对应的链表为空，则要从__freqMap中删除这个链表
     */
    private void remoteMinFreqNode() {
        LinkedList linkedList = this.freqMap.get(this.minFreq);
        Node node = linkedList.getLastNode();
        linkedList.deleteNode(node);
        this.keyMap.remove(node.getKey());
        if(linkedList.isEmpty()) {
            this.freqMap.remove(node.getFreq());
        }
    }
}

// https://leetcode.cn/problems/lfu-cache/solutions/210980/chao-xiang-xi-tu-jie-dong-tu-yan-shi-460-lfuhuan-c/

参考