关于redis:java-从零开始手写-redis九LRU-缓存淘汰算法如何避免缓存污染

前言

java从零手写实现redis（一）如何实现固定大小的缓存？

java从零手写实现redis（三）redis expire 过期原理

java从零手写实现redis（三）内存数据如何重启不失落？

java从零手写实现redis（四）增加监听器

java从零手写实现redis（五）过期策略的另一种实现思路

java从零手写实现redis（六）AOF 长久化原理详解及实现

java从零手写实现redis（七）LRU 缓存淘汰策略详解

从零开始手写 redis（八）奢侈 LRU 淘汰算法性能优化

前两节咱们别离实现了 LRU 算法，并且进行了性能优化。

本节作为 LRU 算法的最初一节，次要解决一下缓存净化的问题。

LRU 基础知识

是什么

LRU算法全称是最近起码应用算法（Least Recently Use），宽泛的利用于缓存机制中。

当缓存应用的空间达到下限后，就须要从已有的数据中淘汰一部分以维持缓存的可用性，而淘汰数据的抉择就是通过LRU算法实现的。

LRU算法的根本思维是基于局部性原理的工夫局部性：

如果一个信息项正在被拜访，那么在近期它很可能还会被再次拜访。

拓展浏览

Apache Commons LRUMAP 源码详解

Redis 当做 LRU MAP 应用

java 从零开始手写 redis（七）redis LRU 驱除策略详解及实现

奢侈 LRU 算法的有余

当存在热点数据时，LRU的效率很好，但偶发性的、周期性的批量操作会导致LRU命中率急剧下降，缓存净化状况比较严重。

扩大算法

1. LRU-K

LRU-K中的K代表最近应用的次数，因而LRU能够认为是LRU-1。

LRU-K的次要目标是为了解决LRU算法“缓存净化”的问题，其核心思想是将“最近应用过1次”的判断规范扩大为“最近应用过K次”。

相比LRU，LRU-K须要多保护一个队列，用于记录所有缓存数据被拜访的历史。只有当数据的拜访次数达到K次的时候，才将数据放入缓存。

当须要淘汰数据时，LRU-K会淘汰第K次访问工夫距以后工夫最大的数据。

数据第一次被拜访时，退出到历史拜访列表，如果数据在拜访历史列表中没有达到K次访问，则依照肯定的规定（FIFO,LRU）淘汰；

当拜访历史队列中的数据拜访次数达到K次后，将数据索引从历史队列中删除，将数据移到缓存队列中，并缓存数据，缓存队列从新依照工夫排序；

缓存数据队列中被再次拜访后，从新排序，须要淘汰数据时，淘汰缓存队列中排在开端的数据，即“淘汰倒数K次访问离当初最久的数据”。

LRU-K具备LRU的长处，同时还能防止LRU的毛病，理论利用中LRU-2是综合最优的抉择。

因为LRU-K还须要记录那些被拜访过、但还没有放入缓存的对象，因而内存耗费会比LRU要多。

2. two queue

Two queues（以下应用2Q代替）算法相似于LRU-2，不同点在于2Q将LRU-2算法中的拜访历史队列（留神这不是缓存数据的）改为一个FIFO缓存队列，即：2Q算法有两个缓存队列，一个是FIFO队列，一个是LRU队列。

当数据第一次拜访时，2Q算法将数据缓存在FIFO队列外面，当数据第二次被拜访时，则将数据从FIFO队列移到LRU队列外面，两个队列各自依照本人的办法淘汰数据。

新拜访的数据插入到FIFO队列中，如果数据在FIFO队列中始终没有被再次拜访，则最终依照FIFO规定淘汰；

如果数据在FIFO队列中再次被拜访到，则将数据移到LRU队列头部，如果数据在LRU队列中再次被拜访，则将数据挪动LRU队列头部，LRU队列淘汰开端的数据。

3. Multi Queue(MQ)

MQ算法依据拜访频率将数据划分为多个队列，不同的队列具备不同的拜访优先级，其核心思想是：优先缓存拜访次数多的数据。

具体的算法结构图如下，Q0，Q1….Qk代表不同的优先级队列，Q-history代表从缓存中淘汰数据，但记录了数据的索引和援用次数的队列：

新插入的数据放入Q0，每个队列依照LRU进行治理，当数据的拜访次数达到肯定次数，须要晋升优先级时，将数据从以后队列中删除，退出到高一级队列的头部；为了避免高优先级数据永远不会被淘汰，当数据在指定的工夫里没有被拜访时，须要升高优先级，将数据从以后队列删除，退出到低一级的队列头部；须要淘汰数据时，从最低一级队列开始依照LRU淘汰，每个队列淘汰数据时，将数据从缓存中删除，将数据索引退出Q-history头部。

如果数据在Q-history中被从新拜访，则从新计算其优先级，移到指标队列头部。

Q-history依照LRU淘汰数据的索引。

MQ须要保护多个队列，且须要保护每个数据的拜访工夫，复杂度比LRU高。

LRU算法比照

集体了解

实际上下面的几个算法，思维上大同小异。

外围目标：解决批量操作导致热点数据生效，缓存被净化的问题。

实现形式：减少一个队列，用来保留只拜访一次的数据，而后依据次数不同，放入到 LRU 中。

只拜访一次的队列，能够是 FIFO 队列，能够是 LRU，咱们来实现一下 2Q 和 LRU-2 两种实现。

2Q

实现思路

实际上就是咱们以前的 FIFO + LRU 二者的联合。

代码实现

根本属性

public class CacheEvictLru2Q<K,V> extends AbstractCacheEvict<K,V> {

    private static final Log log = LogFactory.getLog(CacheEvictLru2Q.class);

    /**
     * 队列大小限度
     *
     * 升高 O(n) 的耗费，防止耗时过长。
     * @since 0.0.13
     */
    private static final int LIMIT_QUEUE_SIZE = 1024;

    /**
     * 第一次拜访的队列
     * @since 0.0.13
     */
    private Queue<K> firstQueue;

    /**
     * 头结点
     * @since 0.0.13
     */
    private DoubleListNode<K,V> head;

    /**
     * 尾巴结点
     * @since 0.0.13
     */
    private DoubleListNode<K,V> tail;

    /**
     * map 信息
     *
     * key: 元素信息
     * value: 元素在 list 中对应的节点信息
     * @since 0.0.13
     */
    private Map<K, DoubleListNode<K,V>> lruIndexMap;

    public CacheEvictLru2Q() {
        this.firstQueue = new LinkedList<>();
        this.lruIndexMap = new HashMap<>();
        this.head = new DoubleListNode<>();
        this.tail = new DoubleListNode<>();

        this.head.next(this.tail);
        this.tail.pre(this.head);
    }

}

数据淘汰

数据淘汰的逻辑：

当缓存大小，曾经达到最大限度时执行：

（1）优先淘汰 firstQueue 中的数据

（2）如果 firstQueue 中数据为空，则淘汰 lruMap 中的数据信息。

这里有一个假如：咱们认为被屡次拜访的数据，重要性高于被只拜访了一次的数据。

@Override
protected ICacheEntry<K, V> doEvict(ICacheEvictContext<K, V> context) {
    ICacheEntry<K, V> result = null;
    final ICache<K,V> cache = context.cache();
    // 超过限度，移除队尾的元素
    if(cache.size() >= context.size()) {
        K evictKey = null;
        //1. firstQueue 不为空，优先移除队列中元素
        if(!firstQueue.isEmpty()) {
            evictKey = firstQueue.remove();
        } else {
            // 获取尾巴节点的前一个元素
            DoubleListNode<K,V> tailPre = this.tail.pre();
            if(tailPre == this.head) {
                log.error("以后列表为空，无奈进行删除");
                throw new CacheRuntimeException("不可删除头结点!");
            }
            evictKey = tailPre.key();
        }
        // 执行移除操作
        V evictValue = cache.remove(evictKey);
        result = new CacheEntry<>(evictKey, evictValue);
    }
    return result;
}

数据删除

当数据被删除时调用：

这个逻辑和以前相似，只是多了一个 FIFO 队列的移除。

/**
 * 移除元素
 *
 * 1. 获取 map 中的元素
 * 2. 不存在间接返回，存在执行以下步骤：
 * 2.1 删除双向链表中的元素
 * 2.2 删除 map 中的元素
 *
 * @param key 元素
 * @since 0.0.13
 */
@Override
public void removeKey(final K key) {
    DoubleListNode<K,V> node = lruIndexMap.get(key);
    //1. LRU 删除逻辑
    if(ObjectUtil.isNotNull(node)) {
        // A<->B<->C
        // 删除 B，须要变成： A<->C
        DoubleListNode<K,V> pre = node.pre();
        DoubleListNode<K,V> next = node.next();
        pre.next(next);
        next.pre(pre);
        // 删除 map 中对应信息
        this.lruIndexMap.remove(node.key());
    } else {
        //2. FIFO 删除逻辑（O(n) 工夫复杂度）
        firstQueue.remove(key);
    }
}

数据的更新

当数据被拜访时，晋升数据的优先级。

（1）如果在 lruMap 中，则首先移除，而后放入到头部

（2）如果不在 lruMap 中，然而在 FIFO 队列，则从 FIFO 队列中移除，增加到 LRU map 中。

（3）如果都不在，间接退出到 FIFO 队列中即可。

/**
 * 放入元素
 * 1. 如果 lruIndexMap 曾经存在，则解决 lru 队列，先删除，再插入。
 * 2. 如果 firstQueue 中曾经存在，则解决 first 队列，先删除 firstQueue，而后插入 Lru。
 * 1 和 2 是不同的场景，然而代码实际上是一样的，删除逻辑中做了二种场景的兼容。
 *
 * 3. 如果不在1、2中，阐明是新元素，直接插入到 firstQueue 的开始即可。
 *
 * @param key 元素
 * @since 0.0.13
 */
@Override
public void updateKey(final K key) {
    //1.1 是否在 LRU MAP 中
    //1.2 是否在 firstQueue 中
    DoubleListNode<K,V> node = lruIndexMap.get(key);
    if(ObjectUtil.isNotNull(node)
        || firstQueue.contains(key)) {
        //1.3 删除信息
        this.removeKey(key);
        //1.4 退出到 LRU 中
        this.addToLruMapHead(key);
        return;
    }
    //2. 间接退出到 firstQueue 队尾
    //        if(firstQueue.size() >= LIMIT_QUEUE_SIZE) {
//            // 防止第一次拜访的列表始终增长，移除队头的元素
//            firstQueue.remove();
//        }
    firstQueue.add(key);
}

这里我想到了一个优化点，限度 firstQueue 的始终增长，因为遍历的工夫复杂度为 O(n)，所以限度最大的大小为 1024。

如果超过了，则把 FIFO 中的元素先移除掉。

不过只移除 FIFO，不移除 cache，会导致二者的沉闷水平不统一；

如果同时移除，然而 cache 的大小还没有满足，可能会导致超出用户的预期，这个能够作为一个优化点，临时正文掉。

测试

代码

ICache<String, String> cache = CacheBs.<String,String>newInstance()
        .size(3)
        .evict(CacheEvicts.<String, String>lru2Q())
        .build();

cache.put("A", "hello");
cache.put("B", "world");
cache.put("C", "FIFO");

// 拜访一次A
cache.get("A");
cache.put("D", "LRU");

Assert.assertEquals(3, cache.size());
System.out.println(cache.keySet());

成果

[DEBUG] [2020-10-03 13:15:50.670] [main] [c.g.h.c.c.s.l.r.CacheRemoveListener.listen] - Remove key: B, value: world, type: evict
[D, A, C]

LRU-2 实现

阐明

FIFO 中的毛病还是比拟显著的，须要 O(n) 的工夫复杂度做遍历。

而且命中率和 LRU-2 比起来还是会差一点。

筹备工作

这里 LRU map 呈现了屡次，咱们为了不便，将 LRU map 简略的封装为一个数据结构。

咱们应用双向链表+HashMap 实现一个简略版本的。

节点

node 节点和以前统一：

public class DoubleListNode<K,V> {

    /**
     * 键
     * @since 0.0.12
     */
    private K key;

    /**
     * 值
     * @since 0.0.12
     */
    private V value;

    /**
     * 前一个节点
     * @since 0.0.12
     */
    private DoubleListNode<K,V> pre;

    /**
     * 后一个节点
     * @since 0.0.12
     */
    private DoubleListNode<K,V> next;

    //fluent getter & setter
}

接口

咱们依据本人的须要，临时定义 3 个最重要的办法。

/**
 * LRU map 接口
 * @author binbin.hou
 * @since 0.0.13
 */
public interface ILruMap<K,V> {

    /**
     * 移除最老的元素
     * @return 移除的明细
     * @since 0.0.13
     */
    ICacheEntry<K, V> removeEldest();

    /**
     * 更新 key 的信息
     * @param key key
     * @since 0.0.13
     */
    void updateKey(final K key);

    /**
     * 移除对应的 key 信息
     * @param key key
     * @since 0.0.13
     */
    void removeKey(final K key);

    /**
     * 是否为空
     * @return 是否
     * @since 0.0.13
     */
    boolean isEmpty();

    /**
     * 是否蕴含元素
     * @param key 元素
     * @return 后果
     * @since 0.0.13
     */
    boolean contains(final K key);
}

实现

咱们基于 DoubleLinkedList + HashMap 实现。

就是把上一节中的实现整顿一下即可。

import com.github.houbb.cache.api.ICacheEntry;
import com.github.houbb.cache.core.exception.CacheRuntimeException;
import com.github.houbb.cache.core.model.CacheEntry;
import com.github.houbb.cache.core.model.DoubleListNode;
import com.github.houbb.cache.core.support.struct.lru.ILruMap;
import com.github.houbb.heaven.util.lang.ObjectUtil;
import com.github.houbb.log.integration.core.Log;
import com.github.houbb.log.integration.core.LogFactory;

import java.util.HashMap;
import java.util.Map;

/**
 * 基于双向列表的实现
 * @author binbin.hou
 * @since 0.0.13
 */
public class LruMapDoubleList<K,V> implements ILruMap<K,V> {

    private static final Log log = LogFactory.getLog(LruMapDoubleList.class);

    /**
     * 头结点
     * @since 0.0.13
     */
    private DoubleListNode<K,V> head;

    /**
     * 尾巴结点
     * @since 0.0.13
     */
    private DoubleListNode<K,V> tail;

    /**
     * map 信息
     *
     * key: 元素信息
     * value: 元素在 list 中对应的节点信息
     * @since 0.0.13
     */
    private Map<K, DoubleListNode<K,V>> indexMap;

    public LruMapDoubleList() {
        this.indexMap = new HashMap<>();
        this.head = new DoubleListNode<>();
        this.tail = new DoubleListNode<>();

        this.head.next(this.tail);
        this.tail.pre(this.head);
    }

    @Override
    public ICacheEntry<K, V> removeEldest() {
        // 获取尾巴节点的前一个元素
        DoubleListNode<K,V> tailPre = this.tail.pre();
        if(tailPre == this.head) {
            log.error("以后列表为空，无奈进行删除");
            throw new CacheRuntimeException("不可删除头结点!");
        }

        K evictKey = tailPre.key();
        V evictValue = tailPre.value();

        return CacheEntry.of(evictKey, evictValue);
    }

    /**
     * 放入元素
     *
     * （1）删除曾经存在的
     * （2）新元素放到元素头部
     *
     * @param key 元素
     * @since 0.0.12
     */
    @Override
    public void updateKey(final K key) {
        //1. 执行删除
        this.removeKey(key);

        //2. 新元素插入到头部
        //head<->next
        //变成：head<->new<->next
        DoubleListNode<K,V> newNode = new DoubleListNode<>();
        newNode.key(key);

        DoubleListNode<K,V> next = this.head.next();
        this.head.next(newNode);
        newNode.pre(this.head);
        next.pre(newNode);
        newNode.next(next);

        //2.2 插入到 map 中
        indexMap.put(key, newNode);
    }

    /**
     * 移除元素
     *
     * 1. 获取 map 中的元素
     * 2. 不存在间接返回，存在执行以下步骤：
     * 2.1 删除双向链表中的元素
     * 2.2 删除 map 中的元素
     *
     * @param key 元素
     * @since 0.0.13
     */
    @Override
    public void removeKey(final K key) {
        DoubleListNode<K,V> node = indexMap.get(key);

        if(ObjectUtil.isNull(node)) {
            return;
        }

        // 删除 list node
        // A<->B<->C
        // 删除 B，须要变成： A<->C
        DoubleListNode<K,V> pre = node.pre();
        DoubleListNode<K,V> next = node.next();

        pre.next(next);
        next.pre(pre);

        // 删除 map 中对应信息
        this.indexMap.remove(key);
    }

    @Override
    public boolean isEmpty() {
        return indexMap.isEmpty();
    }

    @Override
    public boolean contains(K key) {
        return indexMap.containsKey(key);
    }
}

实现思路

LRU 的实现放弃不变。咱们间接将 FIFO 替换为 LRU map 即可。

为了便于了解，咱们将 FIFO 对应为 firstLruMap，用来寄存用户只拜访了一次的元素。

将原来的 LRU 中存入拜访了 2 次及其以上的元素。

其余逻辑和 2Q 保持一致。

实现

根本属性

定义两个 LRU，用来别离存储拜访的信息

public class CacheEvictLru2<K,V> extends AbstractCacheEvict<K,V> {

    private static final Log log = LogFactory.getLog(CacheEvictLru2.class);

    /**
     * 第一次拜访的 lru
     * @since 0.0.13
     */
    private final ILruMap<K,V> firstLruMap;

    /**
     * 2次及其以上的 lru
     * @since 0.0.13
     */
    private final ILruMap<K,V> moreLruMap;

    public CacheEvictLru2() {
        this.firstLruMap = new LruMapDoubleList<>();
        this.moreLruMap = new LruMapDoubleList<>();
    }

}

淘汰实现

和 lru 2Q 模式相似，这里咱们优先淘汰 firstLruMap 中的数据信息。

@Override
protected ICacheEntry<K, V> doEvict(ICacheEvictContext<K, V> context) {
    ICacheEntry<K, V> result = null;
    final ICache<K,V> cache = context.cache();
    // 超过限度，移除队尾的元素
    if(cache.size() >= context.size()) {
        ICacheEntry<K,V>  evictEntry = null;
        //1. firstLruMap 不为空，优先移除队列中元素
        if(!firstLruMap.isEmpty()) {
            evictEntry = firstLruMap.removeEldest();
            log.debug("从 firstLruMap 中淘汰数据：{}", evictEntry);
        } else {
            //2. 否则从 moreLruMap 中淘汰数据
            evictEntry = moreLruMap.removeEldest();
            log.debug("从 moreLruMap 中淘汰数据：{}", evictEntry);
        }
        // 执行缓存移除操作
        final K evictKey = evictEntry.key();
        V evictValue = cache.remove(evictKey);
        result = new CacheEntry<>(evictKey, evictValue);
    }
    return result;
}

删除

/**
 * 移除元素
 *
 * 1. 屡次 lru 中存在，删除
 * 2. 首次 lru 中存在，删除
 *
 * @param key 元素
 * @since 0.0.13
 */
@Override
public void removeKey(final K key) {
    //1. 屡次LRU 删除逻辑
    if(moreLruMap.contains(key)) {
        moreLruMap.removeKey(key);
        log.debug("key: {} 从 moreLruMap 中移除", key);
    } else {
        firstLruMap.removeKey(key);
        log.debug("key: {} 从 firstLruMap 中移除", key);
    }
}

更新

/**
 * 更新信息
 * 1. 如果 moreLruMap 曾经存在，则解决 more 队列，先删除，再插入。
 * 2. 如果 firstLruMap 中曾经存在，则解决 first 队列，先删除 firstLruMap，而后插入 Lru。
 * 1 和 2 是不同的场景，然而代码实际上是一样的，删除逻辑中做了二种场景的兼容。
 *
 * 3. 如果不在1、2中，阐明是新元素，直接插入到 firstLruMap 的开始即可。
 *
 * @param key 元素
 * @since 0.0.13
 */
@Override
public void updateKey(final K key) {
    //1. 元素曾经在屡次拜访，或者第一次拜访的 lru 中
    if(moreLruMap.contains(key)
        || firstLruMap.contains(key)) {
        //1.1 删除信息
        this.removeKey(key);
        //1.2 退出到屡次 LRU 中
        moreLruMap.updateKey(key);
        log.debug("key: {} 屡次拜访，退出到 moreLruMap 中", key);
    } else {
        // 2. 退出到第一次拜访 LRU 中
        firstLruMap.updateKey(key);
        log.debug("key: {} 为第一次拜访，退出到 firstLruMap 中", key);
    }
}

实际上应用 LRU-2 的代码逻辑反而变得清晰了一些，次要是因为咱们把 lruMap 作为独立的数据结构抽离了进来。

测试

代码

ICache<String, String> cache = CacheBs.<String,String>newInstance()
        .size(3)
        .evict(CacheEvicts.<String, String>lru2Q())
        .build();
cache.put("A", "hello");
cache.put("B", "world");
cache.put("C", "FIFO");
// 拜访一次A
cache.get("A");
cache.put("D", "LRU");
Assert.assertEquals(3, cache.size());
System.out.println(cache.keySet());

日志

为了便于定位剖析，源代码实现的时候，加了一点日志。

[DEBUG] [2020-10-03 14:39:04.966] [main] [c.g.h.c.c.s.e.CacheEvictLru2.updateKey] - key: A 为第一次拜访，退出到 firstLruMap 中
[DEBUG] [2020-10-03 14:39:04.967] [main] [c.g.h.c.c.s.e.CacheEvictLru2.updateKey] - key: B 为第一次拜访，退出到 firstLruMap 中
[DEBUG] [2020-10-03 14:39:04.968] [main] [c.g.h.c.c.s.e.CacheEvictLru2.updateKey] - key: C 为第一次拜访，退出到 firstLruMap 中
[DEBUG] [2020-10-03 14:39:04.970] [main] [c.g.h.c.c.s.e.CacheEvictLru2.removeKey] - key: A 从 firstLruMap 中移除
[DEBUG] [2020-10-03 14:39:04.970] [main] [c.g.h.c.c.s.e.CacheEvictLru2.updateKey] - key: A 屡次拜访，退出到 moreLruMap 中
[DEBUG] [2020-10-03 14:39:04.972] [main] [c.g.h.c.c.s.e.CacheEvictLru2.doEvict] - 从 firstLruMap 中淘汰数据：EvictEntry{key=B, value=null}
[DEBUG] [2020-10-03 14:39:04.974] [main] [c.g.h.c.c.s.l.r.CacheRemoveListener.listen] - Remove key: B, value: world, type: evict
[DEBUG] [2020-10-03 14:39:04.974] [main] [c.g.h.c.c.s.e.CacheEvictLru2.updateKey] - key: D 为第一次拜访，退出到 firstLruMap 中
[D, A, C]

小结

对于 LRU 算法的改良咱们次要做了两点：

（1）性能的改良，从 O(N) 优化到 O(1)

（2）批量操作的改良，防止缓存净化

其实除了 LRU，咱们还有其余的淘汰策略。

咱们须要思考上面的问题：

A 数据被拜访了 10 次，B 数据被拜访了 2 次。那么二者谁是热点数据呢？

如果你认为必定 A 是热点数据，这里实际上是另一种淘汰算法，基于 LFU 的淘汰算法，认为拜访次数越多，就越是热点数据。

咱们下一节独特学习下 LFU 淘汰算法的实现。

开源地址：https://github.com/houbb/cache

感觉本文对你有帮忙的话，欢送点赞评论珍藏关注一波，你的激励，是我最大的能源~

目前咱们通过两次优化，解决了性能问题，和批量导致的缓存净化问题。

不晓得你有哪些播种呢？或者有其余更多的想法，欢送留言区和我一起探讨，期待与你的思考相遇。