前言

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-2 > MQ(2) > 2Q > LRU
复杂度LRU-2 > MQ(2) > 2Q > LRU
代价LRU-2 > MQ(2) > 2Q > 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 中的数据信息。

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

@Overrideprotected 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 */@Overridepublic 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 */@Overridepublic 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");// 拜访一次Acache.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 中的数据信息。

@Overrideprotected 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 */@Overridepublic 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 */@Overridepublic 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");// 拜访一次Acache.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

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

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

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