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

3次阅读

共计 11966 个字符，预计需要花费 30 分钟才能阅读完成。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Apache Commons LRUMAP 源码详解

Redis 当做 LRU MAP 应用

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

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

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 要多。

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

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

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

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

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

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

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

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

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

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

比照点	比照
命中率	LRU-2 > MQ(2) > 2Q > LRU
复杂度	LRU-2 > MQ(2) > 2Q > LRU
代价	LRU-2 > MQ(2) > 2Q > LRU

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

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

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

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

实际上就是咱们以前的 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]

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

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

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

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

正文完

redis

发表至： redis

2020-10-05

0

关于redis:Redis-实战篇巧用数据类型实现亿级数据统计

关于redis:redis-延迟队列

关于redis:LeetCode高频算法面试题-003-无重复字符的最长子串

关于redis:Redis-单机哨兵集群搭建

关于leetcode:leetcode栈之比较含退格的字符串

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

前言

LRU 基础知识

是什么

拓展浏览

奢侈 LRU 算法的有余

扩大算法

1. LRU-K

2. two queue

3. Multi Queue(MQ)

LRU 算法比照

集体了解

2Q

实现思路

代码实现

根本属性

数据淘汰

数据删除

数据的更新

测试

代码

成果

LRU-2 实现

阐明

筹备工作

节点

接口

实现

实现思路

实现

根本属性

淘汰实现

删除

更新

测试

代码

日志

小结

站内搜索