LRU及其变体

Posted on

什么是LRU

​ LRU: Least Recent Used。意即：最近最少使用。写代码好几年，我一直这么以为的。

​ 重读wiki，我觉着当初这个名字，起的真不怎么样。具体实现中，实际上要淘汰的是，当前最久未被访问数据。如果一定要换个名字，我觉着 “最近最久未被访问” 策略更合适。

###基本实现

统计最长未被访问，一般有两种方式。

  1. 记录上次访问时间（淘汰掉，访问时间最早的）
  2. 记录上次访问后，访问了多少次其他缓存（淘汰掉未被访问次数最多的）

​ wiki基准实现描述的上述第二种方式。以node对象为载体，记录。

1
2
3
4
5
6
7
8
9
10
11
public class Node {
  private String key;
  private Object value;
  private int unAccessCount;
  
  public Object get(String key){
    // 省略
    unAccessCount = 0
    // 其他node unAccessCount++
  }
}

​ 当缓存空间占满，需要淘汰内存页时，选择unAccessCount最大的节点，丢弃之。

​ 对应操作系统虚拟内存来说，如果node是具体内存页，那么我们还需要一个内存表来辅助查询。例如，添加一个map，处理key与node的引用。加速key的检索过程。

缺陷：

  • 每次访问一个随机key A，其他所有key需要加 1

LRU变体

1. 变体 - 基准实现的优化

​ 使用一个固定长度的双向链表存储node。A端为最新访问数据，B端为最久未访问数据。

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
public class LruCache {
  // 当前最新插入或访问的缓存
  private Node first;
  // 需要时，被过期的缓存
  private Node last;
  // 缓存容量
  private int capitalSize;
  // 存储缓存数据(双向链表) -- 增删快
  private Node nodes;
  // 提供缓存命中查询 -- 查询快
  private ConcurrentHashMap<String, Node> cache;
  
  public value get(String key){
    Object value = cache.get(key);
    if (value != null) {
      removeNode(key);
      addFirstNode(key, value);
    }
    return value;
  }
  
  public void put(String key, Object value){
    Object oldValue = cache.get(key);
    if (oldValue != null){
      removeNode(key);
      addFirstNode(key, value);
    }
    
    if (cache.size() >= capitalSize){
      removeLastNode();
    }
  }
  
  public vlid addFirstNode(String key, Object value);
  
  public void removeNode(String key);
  
  public void removeLastNode();
}

优点：

  • 相较基础版每次修改accessCount，操作数明显降低

缺点：

  • 与基础版相同，最近访问一次，就会被当作热点数据（LRU均存在该问题）

2. 变体 - redis方案

​ redis自带过期机制，所以，其LRU实现是基于时间的。

早期方案：

​ 缓存容量满时，redis基于 server.maxmemory_samples 随机抽取指定数量的key，过期其中访问时间最早的。

优点：

  • 过期操作快

缺点：

  • 过期key随机性较大，刚存入的数据，也可能被抽中

改进方案：

​ 创建一个指定容量的等待过期队列。

​ 第一步，随机抽取一个key，置入队列；第二步，随机抽取指定个数key，将访问时间小于池中最小访问时间的key置入队列。

​ 缓存容量不足时，过期队列中访问时间最早的key。

优点：

  • 异步维护待过期队列
  • 过期操作快
redis为什么要自定义过期策略
  • redis key数量不固定。如果key数量过多，选择全局最久未访问key耗时高
  • redis为单线程应用，不允许过期策略过度消耗
  • redis本身存在过期策略。配置容器满适用LRU时，需要与LRU策略兼容

LFU

​ Least-frequently used：最小访问频次，频次最低的会被过期。与LRU相似。

​ 记录访问次数，存活时间，可得。

PLRU（CPU缓存过期策略）

​ Pseudo-LRU：伪 - LRU。适用于cpu这样的多级缓存系统。

​ CPU缓存系统，每一级维护LRU策略成本过高；所以，CPU设计者们，采用了近似的LRU算法。例如：L1层级区块L1a，对应L2层级L2a、L2b两个区块，则针对L1a每次过期L2a、L2b两个区块中的一个（而不是针对整个L2层过期最近最久未访问）。