关于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<>();@Overridepublic 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