操作系统lru算法_【Redis】LRU算法和Redis的LRU实现

LRU原理

在一般标准的操作系统教材里&＃xff0c;会用下面的方式来演示 LRU 原理&＃xff0c;假设内存只能容纳3个页大小&＃xff0c;按照 7 0 1 2 0 3 0 4 的次序访问页。假设内存按照栈的方式来描述访问时间&＃xff0c;在上面的&＃xff0c;是最近访问的&＃xff0c;在下面的是&＃xff0c;最远时间访问的&＃xff0c;LRU就是这样工作的。

但是如果让我们自己设计一个基于 LRU 的缓存&＃xff0c;这样设计可能问题很多&＃xff0c;这段内存按照访问时间进行了排序&＃xff0c;会有大量的内存拷贝操作&＃xff0c;所以性能肯定是不能接受的。

那么如何设计一个LRU缓存&＃xff0c;使得放入和移除都是 O(1) 的&＃xff0c;我们需要把访问次序维护起来&＃xff0c;但是不能通过内存中的真实排序来反应&＃xff0c;有一种方案就是使用双向链表。 

实现LRU

1.用一个数组来存储数据&＃xff0c;给每一个数据项标记一个访问时间戳&＃xff0c;每次插入新数据项的时候&＃xff0c;先把数组中存在的数据项的时间戳自增&＃xff0c;并将新数据项的时间戳置为0并插入到数组中。每次访问数组中的数据项的时候&＃xff0c;将被访问的数据项的时间戳置为0。当数组空间已满时&＃xff0c;将时间戳最大的数据项淘汰。

2.利用一个链表来实现&＃xff0c;每次新插入数据的时候将新数据插到链表的头部&＃xff1b;每次缓存命中(即数据被访问)&＃xff0c;则将数据移到链表头部&＃xff1b;那么当链表满的时候&＃xff0c;就将链表尾部的数据丢弃。

3.利用链表和hashmap。当需要插入新的数据项的时候&＃xff0c;如果新数据项在链表中存在(一般称为命中)&＃xff0c;则把该节点移到链表头部&＃xff0c;如果不存在&＃xff0c;则新建一个节点&＃xff0c;放到链表头部&＃xff0c;若缓存满了&＃xff0c;则把链表最后一个节点删除即可。在访问数据的时候&＃xff0c;如果数据项在链表中存在&＃xff0c;则把该节点移到链表头部&＃xff0c;否则返回-1。这样一来在链表尾部的节点就是最近最久未访问的数据项。

对于第一种方法&＃xff0c;需要不停地维护数据项的访问时间戳&＃xff0c;另外&＃xff0c;在插入数据、删除数据以及访问数据时&＃xff0c;时间复杂度都是O(n)。对于第二种方法&＃xff0c;链表在定位数据的时候时间复杂度为O(n)。所以在一般使用第三种方式来是实现LRU算法。

基于 HashMap 和 双向链表实现 LRU 的

整体的设计思路是&＃xff0c;可以使用 HashMap 存储 key&＃xff0c;这样可以做到 save 和 get key的时间都是 O(1)&＃xff0c;而 HashMap 的 Value 指向双向链表实现的 LRU 的 Node 节点&＃xff0c;如图所示。

LRU 存储是基于双向链表实现的&＃xff0c;下面的图演示了它的原理。其中 head 代表双向链表的表头&＃xff0c;tail 代表尾部。首先预先设置 LRU 的容量&＃xff0c;如果存储满了&＃xff0c;可以通过 O(1) 的时间淘汰掉双向链表的尾部&＃xff0c;每次新增和访问数据&＃xff0c;都可以通过 O(1)的效率把新的节点增加到对头&＃xff0c;或者把已经存在的节点移动到队头。

下面展示了&＃xff0c;预设大小是 3 的&＃xff0c;LRU存储的在存储和访问过程中的变化。为了简化图复杂度&＃xff0c;图中没有展示 HashMap部分的变化&＃xff0c;仅仅演示了上图 LRU 双向链表的变化。我们对这个LRU缓存的操作序列如下&＃xff1a;

save("key1", 7)

save("key2", 0)

save("key3", 1)

save("key4", 2)

get("key2")

save("key5", 3)

get("key2")

save("key6", 4)

相应的 LRU 双向链表部分变化如下&＃xff1a;

总结一下核心操作的步骤:

1. save(key, value)&＃xff0c;首先在 HashMap 找到 Key 对应的节点&＃xff0c;如果节点存在&＃xff0c;更新节点的值&＃xff0c;并把这个节点移动队头。如果不存在&＃xff0c;需要构造新的节点&＃xff0c;并且尝试把节点塞到队头&＃xff0c;如果LRU空间不足&＃xff0c;则通过 tail 淘汰掉队尾的节点&＃xff0c;同时在 HashMap 中移除 Key。

2. get(key)&＃xff0c;通过 HashMap 找到 LRU 链表节点&＃xff0c;因为根据LRU 原理&＃xff0c;这个节点是最新访问的&＃xff0c;所以要把节点插入到队头&＃xff0c;然后返回缓存的值。

 完整基于 Java 的代码参考如下

class DLinkedNode { String key; int value; DLinkedNode pre; DLinkedNode post;}

LRU Cache

public class LRUCache { private Hashtable cache &＃61; new Hashtable(); private int count; private int capacity; private DLinkedNode head, tail; public LRUCache(int capacity) { this.count &＃61; 0;        this.capacity &＃61; capacity; head &＃61; new DLinkedNode();        head.pre &＃61; null; tail &＃61; new DLinkedNode();        tail.post &＃61; null; head.post &＃61; tail; tail.pre &＃61; head; }    public int get(String key) { DLinkedNode node &＃61; cache.get(key); if(node &＃61;&＃61; 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 &＃61; cache.get(key);        if(node &＃61;&＃61; null){ DLinkedNode newNode &＃61; new DLinkedNode(); newNode.key &＃61; key;            newNode.value &＃61; value; this.cache.put(key, newNode);            this.addNode(newNode);            &＃43;&＃43;count; if(count > capacity){ // pop the tail DLinkedNode tail &＃61; this.popTail(); this.cache.remove(tail.key); --count; } }else{ // update the value. node.value &＃61; value; this.moveToHead(node); } } /** * Always add the new node right after head; */ private void addNode(DLinkedNode node){ node.pre &＃61; head;        node.post &＃61; head.post; head.post.pre &＃61; node; head.post &＃61; node; } /** * Remove an existing node from the linked list. */ private void removeNode(DLinkedNode node){ DLinkedNode pre &＃61; node.pre;        DLinkedNode post &＃61; node.post; pre.post &＃61; post; post.pre &＃61; 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 &＃61; tail.pre; this.removeNode(res); return res; }}

继承LinkedHashMap的简单实现&＃xff1a;

LinkedHashMap底层就是用的HashMap加双链表实现的&＃xff0c;而且本身已经实现了按照访问顺序的存储。此外&＃xff0c;LinkedHashMap中本身就实现了一个方法removeEldestEntry用于判断是否需要移除最不常读取的数&＃xff0c;方法默认是直接返回false&＃xff0c;不会移除元素&＃xff0c;所以需要重写该方法。即当缓存满后就移除最不常用的数。

public class LRUCache extends LinkedHashMap {    private final int CACHE_SIZE; // 这里就是传递进来最多能缓存多少数据 public LRUCache(int cacheSize) { // 设置一个hashmap的初始大小&＃xff0c;最后一个true指的是让linkedhashmap按照访问顺序来进行排序&＃xff0c;最近访问的放在头&＃xff0c;最老访问的就在尾 super((int) Math.ceil(cacheSize / 0.75) &＃43; 1, 0.75f, true); CACHE_SIZE &＃61; cacheSize; } &＃64;Override protected boolean removeEldestEntry(Map.Entry eldest) { // 当map中的数据量大于指定的缓存个数的时候&＃xff0c;就自动删除最老的数据 return size() > CACHE_SIZE; }}

那么问题的后半部分&＃xff0c;是 Redis 如何实现&＃xff0c;这个问题这么问肯定是有坑的&＃xff0c;那就是redis肯定不是这样实现的。

Redis的LRU实现

如果按照HashMap和双向链表实现&＃xff0c;需要额外的存储存放 next 和 prev 指针&＃xff0c;牺牲比较大的存储空间&＃xff0c;显然是不划算的。所以Redis采用了一个近似的做法&＃xff0c;就是随机取出若干个key&＃xff0c;然后按照访问时间排序后&＃xff0c;淘汰掉最不经常使用的&＃xff0c;具体分析如下&＃xff1a;

为了支持LRU&＃xff0c;Redis 2.8.19中使用了一个全局的LRU时钟&＃xff0c;server.lruclock&＃xff0c;定义如下&＃xff0c;

#define REDIS_LRU_BITS 24unsigned lruclock:REDIS_LRU_BITS; /* Clock for LRU eviction */

默认的LRU时钟的分辨率是1秒&＃xff0c;可以通过改变REDIS_LRU_CLOCK_RESOLUTION宏的值来改变&＃xff0c;Redis会在serverCron()中调用updateLRUClock定期的更新LRU时钟&＃xff0c;更新的频率和hz参数有关&＃xff0c;默认为100ms一次&＃xff0c;如下&＃xff0c;

#define REDIS_LRU_CLOCK_MAX ((1

server.unixtime是系统当前的unix时间戳&＃xff0c;当 lruclock 的值超出REDIS_LRU_CLOCK_MAX时&＃xff0c;会从头开始计算&＃xff0c;所以在计算一个key的最长没有访问时间时&＃xff0c;可能key本身保存的lru访问时间会比当前的lrulock还要大&＃xff0c;这个时候需要计算额外时间&＃xff0c;如下&＃xff0c;

/* 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 >&＃61; o->lru) { return (server.lruclock - o->lru) * REDIS_LRU_CLOCK_RESOLUTION; } else { return ((REDIS_LRU_CLOCK_MAX - o->lru) &＃43; server.lruclock) * REDIS_LRU_CLOCK_RESOLUTION; }}

Redis支持和LRU相关淘汰策略包括&＃xff0c;

• volatile-lru 设置了过期时间的key参与近似的lru淘汰策略

• allkeys-lru 所有的key均参与近似的lru淘汰策略

当进行LRU淘汰时&＃xff0c;Redis按如下方式进行的&＃xff0c;

...... /* volatile-lru and allkeys-lru policy */ else if (server.maxmemory_policy &＃61;&＃61; REDIS_MAXMEMORY_ALLKEYS_LRU || server.maxmemory_policy &＃61;&＃61; REDIS_MAXMEMORY_VOLATILE_LRU) { for (k &＃61; 0; k expires. */ if (server.maxmemory_policy &＃61;&＃61; REDIS_MAXMEMORY_VOLATILE_LRU) de &＃61; dictFind(db->dict, thiskey); o &＃61; dictGetVal(de); thisval &＃61; estimateObjectIdleTime(o); /* Higher idle time is better candidate for deletion */ if (bestkey &＃61;&＃61; NULL || thisval > bestval) { bestkey &＃61; thiskey; bestval &＃61; thisval; } } } ......

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

出处&＃xff1a;https://www.cnblogs.com/weknow619/p/10730653.html