关于redis:从零开始手写缓存框架12redis-expire-过期的随机特性详解及实现

前言

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

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

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

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

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

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

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

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

第二节中咱们曾经初步实现了相似 redis 中的 expire 过期性能，不过存在一个问题没有解决，那就是遍历的时候不是随机返回的，会导致每次遍历从头开始，可能导致很多 Keys 处于“饥饿”状态。

能够回顾：

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

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

本节咱们一起来实现一个过期的随机性版本，更近一步体会一下 redis 的奇妙之处。

以前的实现回顾

开始新的旅程之前，咱们先回顾一下原来的实现。

expire 实现原理

其实过期的实思路也比较简单：咱们能够开启一个定时工作，比方 1 秒钟做一次轮训，将过期的信息清空。

过期信息的存储

/**
 * 过期 map
 *
 * 空间换工夫
 * @since 0.0.3
 */
private final Map<K, Long> expireMap = new HashMap<>();

@Override
public void expire(K key, long expireAt) {expireMap.put(key, expireAt);
}

咱们定义一个 map，key 是对应的要过期的信息，value 存储的是过期工夫。

轮询清理

咱们固定 100ms 清理一次，每次最多清理 100 个。

/**
 * 单次清空的数量限度
 * @since 0.0.3
 */
private static final int LIMIT = 100;

/**
 * 缓存实现
 * @since 0.0.3
 */
private final ICache<K,V> cache;
/**
 * 线程执行类
 * @since 0.0.3
 */
private static final ScheduledExecutorService EXECUTOR_SERVICE = Executors.newSingleThreadScheduledExecutor();
public CacheExpire(ICache<K, V> cache) {
    this.cache = cache;
    this.init();}
/**
 * 初始化工作
 * @since 0.0.3
 */
private void init() {EXECUTOR_SERVICE.scheduleAtFixedRate(new ExpireThread(), 100, 100, TimeUnit.MILLISECONDS);
}

这里定义了一个单线程，用于执行清空工作。

清空工作

这个非常简单，遍历过期数据，判断对应的工夫，如果曾经到期了，则执行清空操作。

为了防止单次执行工夫过长，最多只解决 100 条。

/**
 * 定时执行工作
 * @since 0.0.3
 */
private class ExpireThread implements Runnable {
    @Override
    public void run() {
        //1. 判断是否为空
        if(MapUtil.isEmpty(expireMap)) {return;}
        //2. 获取 key 进行解决
        int count = 0;
        for(Map.Entry<K, Long> entry : expireMap.entrySet()) {if(count >= LIMIT) {return;}
            expireKey(entry);
            count++;
        }
    }
}

/**
 * 执行过期操作
 * @param entry 明细
 * @since 0.0.3
 */
private void expireKey(Map.Entry<K, Long> entry) {final K key = entry.getKey();
    final Long expireAt = entry.getValue();
    // 删除的逻辑解决
    long currentTime = System.currentTimeMillis();
    if(currentTime >= expireAt) {expireMap.remove(key);
        // 再移除缓存，后续能够通过惰性删除做弥补
        cache.remove(key);
    }
}

redis 的定时工作

流程

想晓得咱们的流程就什么问题，和 redis 的定时清理工作流程比照一下就晓得了。

Redis 外部保护一个定时工作，默认每秒运行 10 次（通过配置 hz 管制）。

定时工作中删除过期键逻辑采纳了自适应算法，依据键的过期比例、应用快慢两种速率模式回收键，流程如下所示。

流程阐明

1）定时工作在每个数据库空间随机查看 20 个键，当发现过期时删除对应的键。

2）如果超过查看数 25% 的键过期，循环执行回收逻辑直到有余 25% 或运行超时为止，慢模式下超时工夫为 25 毫秒。

3）如果之前回收键逻辑超时，则在 Redis 触发外部事件之前再次以快模式运行回收过期键工作，快模式下超时工夫为 1 毫秒且 2 秒内只能运行 1 次。

4）快慢两种模式外部删除逻辑雷同，只是执行的超时工夫不同。

ps: 这里的快慢模式设计的也比拟奇妙，依据过期信息的比例，调整对应的工作超时工夫。

这里的随机也十分重要，能够比拟主观的清理掉过期信息，而不是从头遍历，导致前面的数据无奈被拜访。

咱们接下来次要实现下随机抽取这个个性。

间接通过 Map#keys 转汇合

实现思路

放弃原来的 expireMap 不变，间接对 keys 转换为 collection，而后随机获取。

这个也是网上最多的一种答案。

java 代码实现

根本属性

public class CacheExpireRandom<K,V> implements ICacheExpire<K,V> {private static final Log log = LogFactory.getLog(CacheExpireRandom.class);

    /**
     * 单次清空的数量限度
     * @since 0.0.16
     */
    private static final int COUNT_LIMIT = 100;

    /**
     * 过期 map
     *
     * 空间换工夫
     * @since 0.0.16
     */
    private final Map<K, Long> expireMap = new HashMap<>();

    /**
     * 缓存实现
     * @since 0.0.16
     */
    private final ICache<K,V> cache;

    /**
     * 是否启用快模式
     * @since 0.0.16
     */
    private volatile boolean fastMode = false;

    /**
     * 线程执行类
     * @since 0.0.16
     */
    private static final ScheduledExecutorService EXECUTOR_SERVICE = Executors.newSingleThreadScheduledExecutor();

    public CacheExpireRandom(ICache<K, V> cache) {
        this.cache = cache;
        this.init();}

    /**
     * 初始化工作
     * @since 0.0.16
     */
    private void init() {EXECUTOR_SERVICE.scheduleAtFixedRate(new ExpireThreadRandom(), 10, 10, TimeUnit.SECONDS);
    }

}

定时工作

这里咱们和 redis 保持一致，反对 fastMode。

实际上 fastMode 和慢模式的逻辑是齐全一样的，只是超时的工夫不同。

这里的超时工夫我依据集体了解做了一点调整，整体流程不变。

/**
 * 定时执行工作
 * @since 0.0.16
 */
private class ExpireThreadRandom implements Runnable {
    @Override
    public void run() {
        //1. 判断是否为空
        if(MapUtil.isEmpty(expireMap)) {log.info("expireMap 信息为空，间接跳过本次解决。");
            return;
        }
        //2. 是否启用快模式
        if(fastMode) {expireKeys(10L);
        }
        //3. 迟缓模式
        expireKeys(100L);
    }
}

过期信息外围实现

咱们执行过期的时候，首先会记录超时工夫，用于超出时间接中断执行。

默认复原 fastMode=false，当执行超时的时候设置 fastMode=true。

/**
 * 过期信息
 * @param timeoutMills 超时工夫
 * @since 0.0.16
 */
private void expireKeys(final long timeoutMills) {
    // 设置超时工夫 100ms
    final long timeLimit = System.currentTimeMillis() + timeoutMills;
    // 复原 fastMode
    this.fastMode = false;
    //2. 获取 key 进行解决
    int count = 0;
    while (true) {
        //2.1 返回判断
        if(count >= COUNT_LIMIT) {log.info("过期淘汰次数曾经达到最大次数: {}，实现本次执行。", COUNT_LIMIT);
            return;
        }
        if(System.currentTimeMillis() >= timeLimit) {
            this.fastMode = true;
            log.info("过期淘汰曾经达到限度工夫，中断本次执行，设置 fastMode=true;");
            return;
        }
        //2.2 随机过期
        K key = getRandomKey();
        Long expireAt = expireMap.get(key);
        boolean expireFlag = expireKey(key, expireAt);
        log.debug("key: {} 过期执行后果 {}", key, expireFlag);
        //2.3 信息更新
        count++;
    }
}

随机获取过期 key

/**
 * 随机获取一个 key 信息
 * @return 随机返回的 keys
 * @since 0.0.16
 */
private K getRandomKey() {Random random = ThreadLocalRandom.current();
    Set<K> keySet = expireMap.keySet();
    List<K> list = new ArrayList<>(keySet);
    int randomIndex = random.nextInt(list.size());
    return list.get(randomIndex);
}

这个就是网上最常见的实现办法，间接所有 keys 转换为 list，而后通过 random 获取一个元素。

性能改良

办法的缺点

getRandomKey() 办法为了获取一个随机的信息，代价还是太大了。

如果 keys 的数量十分大，那么咱们要创立一个 list，这个自身就是十分耗时的，而且空间复杂度间接翻倍。

所以不太分明为什么早晨最多的是这一种解法。

优化思路 - 防止空间节约

最简略的思路是咱们应该防止 list 的创立。

咱们所要的只是一个基于 size 的随机值而已，咱们能够遍历获取：

private K getRandomKey2() {Random random = ThreadLocalRandom.current();
    int randomIndex = random.nextInt(expireMap.size());
    // 遍历 keys
    Iterator<K> iterator = expireMap.keySet().iterator();
    int count = 0;
    while (iterator.hasNext()) {K key = iterator.next();
        if(count == randomIndex) {return key;}
        count++;
    }
    // 失常逻辑不会到这里
    throw new CacheRuntimeException("对应信息不存在");
}

优化思路 - 批量操作

上述的办法防止了 list 的创立，同时也合乎随机的条件。

然而从头遍历到随机的 size 数值，这也是一个比较慢的过程（O(N) 工夫复杂度）。

如果咱们取 100 次，乐观的话就是 100 * O(N)。

咱们能够使用批量的思维，比方一次取 100 个，升高工夫复杂度：

/**
 * 批量获取多个 key 信息
 * @param sizeLimit 大小限度
 * @return 随机返回的 keys
 * @since 0.0.16
 */
private Set<K> getRandomKeyBatch(final int sizeLimit) {Random random = ThreadLocalRandom.current();
    int randomIndex = random.nextInt(expireMap.size());
    // 遍历 keys
    Iterator<K> iterator = expireMap.keySet().iterator();
    int count = 0;
    Set<K> keySet = new HashSet<>();
    while (iterator.hasNext()) {
        // 判断列表大小
        if(keySet.size() >= sizeLimit) {return keySet;}
        K key = iterator.next();
        // index 向后的地位，全副放进来。if(count >= randomIndex) {keySet.add(key);
        }
        count++;
    }
    // 失常逻辑不会到这里
    throw new CacheRuntimeException("对应信息不存在");
}

咱们传入一个列表的大小限度，能够一次获取多个。

优化思路 -O(1) 的工夫复杂度

一开始想到随机，我的第一想法是同时冗余一个 list 寄存 keys，而后能够随机返回 key，解决问题。

然而对于 list 的更新，的确 O(N) 的，空间复杂度多出了 list 这一部分，感觉不太值当。

如果应用后面的 map 存储双向链表节点也能够解决，然而绝对比拟麻烦，后面也都实现过，此处就不赘述了。

其实这里的随机还是有些有余

（1）比方随机如果数据反复了怎么解决？

当然目前的解法就是间接 count，个别数据量较大时这种概率比拟低，而且有惰性删除兜底，所以无伤大雅。

（2）随机到的信息很大可能过期工夫没到

这里最好采纳咱们原来的基于过期工夫的 map 分类形式，这样能够保障获取到的信息过期工夫在咱们的把握之中。

当然各种办法各有利弊，看咱们如何依据理论状况取舍。

小结

到这里，一个相似于 redis 的 expire 过期性能，算是根本实现了。

对于 redis 过期的实现，到这里也根本告一段落了。当然，还有很多优化的中央，心愿你在评论区写下本人的办法。

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

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

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

原文地址

Cache Travel-09- 从零手写 cache 之 redis expire 过期实现原理

参考资料

JAVA 随机选出 MAP 中的键

Selecting random key and value sets from a Map in Java