从LRU原理与实现到Redis的LRU策略

缓存是提高性能一种有效手段,从处理器的L1,L2,L3缓存,到各种内存缓存,再到分布式缓存、CDN等,无不是通过增加缓存层,提高数据访问的速度。然而缓存是宝贵的,也是稀有的,必然涉及缓存满了,需要淘汰部分内容的问题。LRU(Least Recently Used), 是其中较为经典的一种算法,翻译过来就是最近最少使用策略。

LRU缓存算法的核心逻辑如下:

  1. 缓存的大小是有限的;
  2. 缓存中的项目按照最近访问时间排序,这里用一个链表来描述,最近访问过的在队头,最久没访问过的在队尾;
  3. 当缓存命中时,将命中的项目挪到队头;
  4. 更新缓存内容时,将更新后的节点挪到对头
  5. 向缓存写添加项目时,如果缓存未满,将加载的内容放在队头;如果队列已满,将队尾的节点移除,然后将新数据添加到队头;

下面是基于Java的LinkedHashMap实现的一个最简单的LRUCache:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
package cc.databus.cache;
import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache<K, V> extends LinkedHashMap<K, V> {

private final int cacheSize;

public LRUCache(int cacheSize) {
super(cacheSize, 0.75f, true);
this.cacheSize = cacheSize;
}

@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > cacheSize;
}
}

下面的代码可以测试LRU的几个操作的行为:

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
package cc.databus.cache.test;

import cc.databus.cache.LRUCache;
import org.junit.Test;

import java.util.Iterator;

public class TestLRUCache {
@Test
public void test() {
LRUCache<String, Integer> lru = new LRUCache<>(3);

lru.put("test1", 1);
lru.put("test2", 2);
lru.put("test3", 3);

System.out.println("old --------------> new");
printCache(lru);
System.out.println("=======================");
lru.get("test2");
printCache(lru);
System.out.println("=======================");
lru.put("test4", 4);
printCache(lru);
}

private static void printCache(LRUCache cache) {
for (Object o : cache.entrySet()) {
System.out.print(o + " ");
}
System.out.print("\n");
}
}

测试代码运行的输出:

1
2
3
4
5
6
old --------------> new
test1=1 test2=2 test3=3
=======================
test1=1 test3=3 test2=2
=======================
test3=3 test2=2 test4=4

至于这里为什么用LinkedHashMap,原因是LinkedHashMap具有LRU算法需要的特性,所以我这里就偷个懒。如果不用LinkedHasMap,常规的实现是使用LinkedList加HashMap的方式,LinkedList用来维系LRU的最近最久访问关系,并能做到O(1)的节点调整,HashMap用来快速查询节点。

Redis的LRU机制

上面的实现可以看到,Java版本的实现利用到链表和Hash,在数据量很大的情况下必然导致空间的浪费,且当存储的数据是int这些类型时,浪费比较高,所以Redis的LRU采用的是一种”近似”LRU的策略,利用采样的方法来进行内存释放。下面是Redis的部分代码:

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
/* volatile-lru and allkeys-lru policy */
else if (server.maxmemory_policy == REDIS_MAXMEMORY_ALLKEYS_LRU ||
server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
{
for (k = 0; k < server.maxmemory_samples; k++) {
sds thiskey;
long thisval;
robj *o;

de = dictGetRandomKey(dict);
thiskey = dictGetKey(de);
/* When policy is volatile-lru we need an additional lookup
* to locate the real key, as dict is set to db->expires. */
if (server.maxmemory_policy == REDIS_MAXMEMORY_VOLATILE_LRU)
de = dictFind(db->dict, thiskey);
o = dictGetVal(de);
thisval = estimateObjectIdleTime(o);

/* Higher idle time is better candidate for deletion */
if (bestkey == NULL || thisval > bestval) {
bestkey = thiskey;
bestval = thisval;
}
}
}

Redis会基于server.maxmemory_samples配置采样固定数目的key,然后比较它们的lru访问时间,然后淘汰最近最久没有访问的key,maxmemory_samples的值越大,Redis的近似LRU算法就越接近于严格LRU算法,但是相应消耗也变高,对性能有一定影响,样本值默认为5。下面是一张关于Redis近似LRU算法性能的对比:

image

总结

Redis为了追求内存的高效实用,并没有采用链表+Hash的数据结构来实现LRU,而是在现有数据结构的基础上,通过采样的方式实现了一种近似LRU的算法,从而避免了空间的浪费。从性能对比来看,近似LRU能够达到和绝对LRU算法相匹配的效果。
当然LRU也有其缺点,比如在淘汰策略执行之前,某个很久没有被访问的缓存项刚好被访问,而使得其他缓存命中概率更高的项目被淘汰,有失公允。所以有一些针对LRU的改进算法,比如LFU(Least Frequently Used),最近最不频繁访问策略,这种策略会优先淘汰命中率低的项目。

Redis持久化策略 skiplist介绍

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×