我要评论lru原理
在一般标准的操作系统教材里，会用下面的方式来演示 lru 原理，假设内存只能容纳3个页大小，按照 7 0 1 2 0 3 0 4 的次序访问页。假设内存按照栈的方式来描述访问时间，在上面的，是最近访问的，在下面的是，最远时间访问的，lru就是这样工作的。
但是如果让我们自己设计一个基于 lru 的缓存，这样设计可能问题很多，这段内存按照访问时间进行了排序，会有大量的内存拷贝操作，所以性能肯定是不能接受的。
那么如何设计一个lru缓存，使得放入和移除都是 o(1) 的，我们需要把访问次序维护起来，但是不能通过内存中的真实排序来反应，有一种方案就是使用双向链表。
实现lru
1.用一个数组来存储数据，给每一个数据项标记一个访问时间戳，每次插入新数据项的时候，先把数组中存在的数据项的时间戳自增，并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候，将被访问的数据项的时间戳置为0。当数组空间已满时，将时间戳最大的数据项淘汰。
2.利用一个链表来实现，每次新插入数据的时候将新数据插到链表的头部；每次缓存命中（即数据被访问），则将数据移到链表头部；那么当链表满的时候，就将链表尾部的数据丢弃。
3.利用链表和hashmap。当需要插入新的数据项的时候，如果新数据项在链表中存在（一般称为命中），则把该节点移到链表头部，如果不存在，则新建一个节点，放到链表头部，若缓存满了，则把链表最后一个节点删除即可。在访问数据的时候，如果数据项在链表中存在，则把该节点移到链表头部，否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项。
对于第一种方法，需要不停地维护数据项的访问时间戳，另外，在插入数据、删除数据以及访问数据时，时间复杂度都是o(n)。对于第二种方法，链表在定位数据的时候时间复杂度为o(n)。所以在一般使用第三种方式来是实现lru算法。
基于 hashmap 和 双向链表实现 lru 的
整体的设计思路是，可以使用 hashmap 存储 key，这样可以做到 save 和 get key的时间都是 o(1)，而 hashmap 的 value 指向双向链表实现的 lru 的 node 节点，如图所示。
lru 存储是基于双向链表实现的，下面的图演示了它的原理。其中 head 代表双向链表的表头，tail 代表尾部。首先预先设置 lru 的容量，如果存储满了，可以通过 o(1) 的时间淘汰掉双向链表的尾部，每次新增和访问数据，都可以通过 o(1)的效率把新的节点增加到对头，或者把已经存在的节点移动到队头。
下面展示了，预设大小是 3 的，lru存储的在存储和访问过程中的变化。为了简化图复杂度，图中没有展示 hashmap部分的变化，仅仅演示了上图 lru 双向链表的变化。我们对这个lru缓存的操作序列如下：
save("key1", 7)
save("key2", 0)
save("key3", 1)
save("key4", 2)
get("key2")
save("key5", 3)
get("key2")
save("key6", 4)
相应的 lru 双向链表部分变化如下：
总结一下核心操作的步骤:
- save(key, value)，首先在 hashmap 找到 key 对应的节点，如果节点存在，更新节点的值，并把这个节点移动队头。如果不存在，需要构造新的节点，并且尝试把节点塞到队头，如果lru空间不足，则通过 tail 淘汰掉队尾的节点，同时在 hashmap 中移除 key。
- get(key)，通过 hashmap 找到 lru 链表节点，因为根据lru 原理，这个节点是最新访问的，所以要把节点插入到队头，然后返回缓存的值。
完整基于 java 的代码参考如下
class dlinkednode {
string key;
int value;
dlinkednode pre;
dlinkednode post;
}
lru cache
public class lrucache {
private hashtable<integer, dlinkednode>
cache = new hashtable<integer, dlinkednode>();
private int count;
private int capacity;
private dlinkednode head, tail;
public lrucache(int capacity) {
this.count = 0;
this.capacity = capacity;
head = new dlinkednode();
head.pre = null;
tail = new dlinkednode();
tail.post = null;
head.post = tail;
tail.pre = head;
}
public int get(string key) {
dlinkednode node = cache.get(key);
if(node == null){
return -1; // should raise exception here.
}
// move the accessed node to the head;
this.movetohead(node);
return node.value;
}
public void set(string key, int value) {
dlinkednode node = cache.get(key);
if(node == null){
dlinkednode newnode = new dlinkednode();
newnode.key = key;
newnode.value = value;
this.cache.put(key, newnode);
this.addnode(newnode);
++count;
if(count > capacity){
// pop the tail
dlinkednode tail = this.poptail();
this.cache.remove(tail.key);
--count;
}
}else{
// update the value.
node.value = value;
this.movetohead(node);
}
}
/**
* always add the new node right after head;
*/
private void addnode(dlinkednode node){
node.pre = head;
node.post = head.post;
head.post.pre = node;
head.post = node;
}
/**
* remove an existing node from the linked list.
*/
private void removenode(dlinkednode node){
dlinkednode pre = node.pre;
dlinkednode post = node.post;
pre.post = post;
post.pre = pre;
}
/**
* move certain node in between to the head.
*/
private void movetohead(dlinkednode node){
this.removenode(node);
this.addnode(node);
}
// pop the current tail.
private dlinkednode poptail(){
dlinkednode res = tail.pre;
this.removenode(res);
return res;
}
}
继承linkedhashmap的简单实现：
linkedhashmap底层就是用的hashmap加双链表实现的，而且本身已经实现了按照访问顺序的存储。此外，linkedhashmap中本身就实现了一个方法removeeldestentry用于判断是否需要移除最不常读取的数，方法默认是直接返回false，不会移除元素，所以需要重写该方法。即当缓存满后就移除最不常用的数。
public class lrucache<k, v> extends linkedhashmap<k, v> {
private final int cache_size;
// 这里就是传递进来最多能缓存多少数据
public lrucache(int cachesize) {
// 设置一个hashmap的初始大小，最后一个true指的是让linkedhashmap按照访问顺序来进行排序，最近访问的放在头，最老访问的就在尾
super((int) math.ceil(cachesize / 0.75) + 1, 0.75f, true);
cache_size = cachesize;
}
@override
protected boolean removeeldestentry(map.entry eldest) {
// 当map中的数据量大于指定的缓存个数的时候，就自动删除最老的数据
return size() > cache_size;
}
}
那么问题的后半部分，是 redis 如何实现，这个问题这么问肯定是有坑的，那就是redis肯定不是这样实现的。
redis的lru实现
如果按照hashmap和双向链表实现，需要额外的存储存放 next 和 prev 指针，牺牲比较大的存储空间，显然是不划算的。所以redis采用了一个近似的做法，就是随机取出若干个key，然后按照访问时间排序后，淘汰掉最不经常使用的，具体分析如下：
为了支持lru，redis 2.8.19中使用了一个全局的lru时钟，server.lruclock，定义如下，
#define redis_lru_bits 24 unsigned lruclock:redis_lru_bits; /* clock for lru eviction */
默认的lru时钟的分辨率是1秒，可以通过改变redis_lru_clock_resolution宏的值来改变，redis会在servercron()中调用updatelruclock定期的更新lru时钟，更新的频率和hz参数有关，默认为100ms一次，如下，
#define redis_lru_clock_max ((1<<redis_lru_bits)-1) /* max value of obj->lru */
#define redis_lru_clock_resolution 1 /* lru clock resolution in seconds */
void updatelruclock(void) {
server.lruclock = (server.unixtime / redis_lru_clock_resolution) &
redis_lru_clock_max;
}
server.unixtime是系统当前的unix时间戳，当 lruclock 的值超出redis_lru_clock_max时，会从头开始计算，所以在计算一个key的最长没有访问时间时，可能key本身保存的lru访问时间会比当前的lrulock还要大，这个时候需要计算额外时间，如下，
/* given an object returns the min number of seconds the object was never
* requested, using an approximated lru algorithm. */
unsigned long estimateobjectidletime(robj *o) {
if (server.lruclock >= o->lru) {
return (server.lruclock - o->lru) * redis_lru_clock_resolution;
} else {
return ((redis_lru_clock_max - o->lru) + server.lruclock) *
redis_lru_clock_resolution;
}
}
redis支持和lru相关淘汰策略包括，
volatile-lru设置了过期时间的key参与近似的lru淘汰策略allkeys-lru所有的key均参与近似的lru淘汰策略
当进行lru淘汰时，redis按如下方式进行的，
......
/* 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。
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请 点击进行留言回复，万千网友为您解惑！
网友评论