前言

Redis内存淘汰指的是用户存储的一些键被可以被Redis主动地从实例中删除，从而产生读miss的情况，那么Redis为什么要有这种功能？这就是我们需要探究的设计初衷。Redis最常见的两种应用场景为缓存和持久存储，首先要明确的一个问题是内存淘汰策略更适合于那种场景？是持久存储还是缓存？

内存的淘汰机制的初衷是为了更好地使用内存，用一定的缓存miss来换取内存的使用效率。

在研究Redislru之前，我们先看下操作系统内存页面置换算法

1. 最佳置换算法(OPT)

最佳(Optimal, OPT)置换算法所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率。但由于人们目前无法预知进程在内存下的若千页面中哪个是未来最长时间内不再被访问的，因而该算法无法实现。

2. 先进先出(FIFO)页面置换算法

优先淘汰最早进入内存的页面，亦即在内存中驻留时间最久的页面。该算法实现简单，只需把调入内存的页面根据先后次序链接成队列，设置一个指针总指向最早的页面。但该算法与进程实际运行时的规律不适应，因为在进程中，有的页面经常被访问。

3.最近最久未使用(LRU)置换算法

选择最近最长时间未访问过的页面予以淘汰，它认为过去一段时间内未访问过的页面，在最近的将来可能也不会被访问。该算法为每个页面设置一个访问字段，来记录页面自上次被访问以来所经历的时间，淘汰页面时选择现有页面中值最大的予以淘汰。

再对上面的实例釆用LRU算法进行页面置换，如图3-29所示。进程第一次对页面2访问时，将最近最久未被访问的页面7置换出去。然后访问页面3时，将最近最久未使用的页面1换出。

时钟(CLOCK)置换算法

LRU算法的性能接近于OPT,但是实现起来比较困难，且开销大；FIFO算法实现简单，但性能差。所以操作系统的设计者尝试了很多算法，试图用比较小的开销接近LRU的性能，这类算法都是CLOCK算法的变体。

简单的CLOCK算法是给每一帧关联一个附加位，称为使用位。当某一页首次装入主存时，该帧的使用位设置为1;当该页随后再被访问到时，它的使用位也被置为1。对于页替换算法，用于替换的候选帧集合看做一个循环缓冲区，并且有一个指针与之相关联。当某一页被替换时，该指针被设置成指向缓冲区中的下一帧。当需要替换一页时，操作系统扫描缓冲区，以查找使用位被置为0的一帧。每当遇到一个使用位为1的帧时，操作系统就将该位重新置为0；如果在这个过程开始时，缓冲区中所有帧的使用位均为0，则选择遇到的第一个帧替换；如果所有帧的使用位均为1,则指针在缓冲区中完整地循环一周，把所有使用位都置为0，并且停留在最初的位置上，替换该帧中的页。由于该算法循环地检查各页面的情况，故称为CLOCK算法，又称为最近未用(Not Recently Used, NRU)算法。

传统的淘汰算法：

FIFO：First In First Out，先进先出。判断被存储的时间，离目前最远的数据优先被淘汰。

LRU：Least Recently Used，最近最少使用。判断最近被使用的时间，目前最远的数据优先被淘汰。

LFU：Least Frequently Used，最不经常使用。在一段时间内，数据被使用次数最少的，优先被淘汰。

REDIS淘汰策略

Redis提供了下面几种淘汰策略供用户选择，其中默认的策略为noeviction策略：

· noeviction：当内存使用达到阈值的时候，所有引起申请内存的命令会报错。

· allkeys-lru：在主键空间中，优先移除最近未使用的key。

· volatile-lru：在设置了过期时间的键空间中，优先移除最近未使用的key。

· allkeys-random：在主键空间中，随机移除某个key。

· volatile-random：在设置了过期时间的键空间中，随机移除某个key。

· volatile-ttl：在设置了过期时间的键空间中，具有更早过期时间的key优先移除。

下面看看几种淘汰策略策略的适用场景：

· allkeys-lru：如果我们的应用对缓存的访问符合幂律分布（也就是存在相对热点数据），或者我们不太清楚我们应用的缓存访问分布状况，我们可以选择allkeys-lru策略。

· allkeys-random：如果我们的应用对于缓存key的访问概率相等，则可以使用这个策略。

· volatile-ttl：这种策略使得我们可以向Redis提示哪些key更适合被eviction。

手写最近最久未使用(LRU)置换算法

距离现在最早使用的会被我们替换掉。不够形象的话我们看下面的例子。

插入1234231

位置11112342

位置2null223423

位置3nullnull34231

…

位置1始终是最早进来的元素，是淘汰位置。新进来的元素如果是新元素直接放在位置3，然后将位置1弹出。如果是已有元素则将其放在位置3并删除之前位置上的已有元素，保持其他元素相对位置不变。

这里的例子就是一个size=3的缓存淘汰实现。

利用LinkedHashMap实现的简单LRU

对于Java.util.LinkedHashMap我们的认识仅仅只是停留在该map可以按照插入的顺序保存，那是不够的。 linkedHashMap还可以实现按照访问顺序保存元素。

先看看如何利用它实现LRU的吧

public class UseLinkedHashMapCache extends LinkedHashMap{
 private int cacheSize;
 public UseLinkedHashMapCache(int cacheSize){

//构造函数一定要放在第一行

super(16,0.75f,true); //那个f如果不加 就是double类型，然后该构造没有该类型的入参。 然后最为关键的就是那个入参 true

this.cacheSize = cacheSize;

}

@Override

protected boolean removeEldestEntry(Map.Entry eldest){ //重写LinkedHashMap原方法

return size()>cacheSize; //临界条件不能有等于，否则会让缓存尺寸小1

}

}

关键点:

继承了LinkedHashMap并使用

public LinkedHashMap(int initialCapacity,

float loadFactor,

boolean accessOrder) {

super(initialCapacity, loadFactor);

this.accessOrder = accessOrder;

}

构造函数

重写了

 protected boolean removeEldestEntry(Map.Entry eldest) {
 return false;
 }

看看如何使用

public static void main(String[]args){

 UseLinkedHashMapCache<integer> cache = new UseLinkedHashMapCache<integer>(4);
 cache.put(1, "one"); 

 cache.put(2, "two");
 cache.put(3, "three");
 cache.put(4, "four");
 cache.put(2, "two");
 cache.put(3, "three");
 Iterator<map.entry>> it = cache.entrySet().iterator();
 while(it.hasNext()){
 Map.Entry<integer> entry = it.next();
 Integer key = entry.getKey();
 System.out.print("Key:\t"+key);
 String Value = entry.getValue(); //这个无需打印...
 System.out.println();
 }
 }
/<integer>/<map.entry>/<integer>/<integer>

结果是:

Key: 1

Key: 4

Key: 2

Key: 3

与我们表格中的结果一致。

手写LRU（利用数组）

/**

* 用数组写了一个

*

* 有个疑问， 比如当缓存大小为5 这时候1、2、3、4、4 请问最后一个4是应该插入还是不处理呢？

*

* 我个人觉得如果这里理解为缓存的key ，那么就应该是不插入 结果应该还是1、2、3、4、null

* */

public class HandMakeCache {

//添加次数 计数器

static int count =0;

//数组元素 计数器

 static int size=0;
 //最大长度
 int maxSize;
 //对象数组
 int [] listArray; //为了简略比较
 //顺序表的初始化方法
 public HandMakeCache(int maxSize)
 {
 listArray = new int [maxSize];
 this.maxSize = maxSize;
 }
 public int getSize(){
 return size;
 }
 public void insert(int obj) throws Exception {
 // 插入过程不应该指定下标，对于用户来讲这应该是透明的，只需要暴露插入的顺序
 boolean exist = false; // 每次insert校验一下是否存在
 int location = 0; // 对于已有元素，记录其已存在的位置
 for (int i = 0; i < maxSize; i++) {
 if (obj == listArray[i]) {
 exist = true;
 location = i; // 记录已存在的位置
 }
 } // 遍历看是否已有，每次插入都要遍历，感觉性能很差
 if (size < this.maxSize) { // 当插入次数小于缓存大小的时候随意插入 

 if (exist) {
 if (location == 0) {
 moveArrayElements(listArray,0,size-2);
 } else if (location < size - 1) { // 已存在元素不在最新的位置
 moveArrayElements(listArray,location,size-2);
 }
 listArray[size - 1] = obj; // 由于已存在
 } else {
 listArray[size] = obj;
 size++; // 数组未满时才计数
 }
 } else { // 此时缓存为满，这时候要保留最末端元素先
 if (!exist || obj == listArray[0]) { // 新元素添加进来，和最远元素添加进来效果一样
 moveArrayElements(listArray,0,maxSize-2);
 } else if (obj != listArray[maxSize - 1]) {
 moveArrayElements(listArray,location,maxSize-2);
 } // 如果添加的是上次添加的元素，则不管了。。
 listArray[maxSize - 1] = obj;
 }
 count++; // 计数
 }
 public Object get(int index) throws Exception {
 return listArray[index];
 }
 /**
 * 平移数组的方法，start是要移动至的头位置，end为最后被移动的位置。
 * */
 public void moveArrayElements(int [] arr, int start, int end){
 for(int i=start;i<=end;i++){
 arr[i] = arr[i+1];
 }
 }
 public static void main(String[] args) {
 int cacheSize = 5;
 HandMakeCache list = new HandMakeCache(cacheSize);
 try
 {
 list.insert(1);
 list.insert(2); 

 list.insert(3);
 list.insert(1);
 list.insert(3);
 list.insert(4);
 list.insert(4);
 list.insert(5);
// list.insert(3);
 for(int i=0;i<cachesize> {
 System.out.println(list.get(i));
 }
 System.out.println("成功插入"+count+"次元素.");
 }
 catch(Exception ex)
 {
 ex.printStackTrace();
 }
 }
}
/<cachesize>

非常重要的一点~ 写LRU之前你一定要知道LRU的正确的含义。。

这里分为几种情况吧..

1. 当数组未满的情况下，随便插

2. 数组满了之后，插入介于头和尾的元素，需要记录其之前存在的下标，然后将大于该下标的元素整体前移。

3. 数组满了之后，插入最新的元素等于什么操作也没有。保持原样

3. 数组满了之后，插入一个不存在的元素 等同于 插入数组最开始的元素。

比如 1、2、3、4 之后插入5 和 1、2、3、4 之后插入1 结果分别为 2、3、4、5和 2、3、4、1。

缺点:

如果利用数组来存储的话，当我们缓存的大小非常大的时候。比如10W，那么假设我们需要淘汰最远的元素，就需要将99999个元素整体往前移一位，这样还仅仅只是替换一次。大量这样的操作是非常低效的，所以我们还是考虑用链表来实现↓。

閱讀更多 青峰科技 的文章

關鍵字: 详解 内存 NoSQL