expire 仿Redis优化

Redis的定时任务

Redis的内部维护一个定时任务，会每隔10S 检查一次数据库【可撇配置】，先从过期字典中随机抽取20个key，检查这20个key是否过期。

这里默认会采用慢模式，如果key的过期数量大于25%，或者运行超时25ms，继续重复进行检查；反之停止继续删除。

此时会切换成快模式，快模式的超时时间为1ms，2s内只运行一次。

仿Redis

• 实现思路

  保持原来的expireMap不变，直接把keys转换为collection，然后随机获取。

定时删除实现

先写出一些基础的属性：

public class CacheExpireRandom<K,V> implements ICacheExpire<K,V> {

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

    /**
     * 单次清空的数量限制
     */
    private static final int COUNT_LIMIT = 100;

    /**
     * 过期 map
     *
     * 空间换时间
     */
    private final Map<K, Long> expireMap = new HashMap<>();

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

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

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

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

    /**
     * 初始化任务
     */
    private void init() {
        EXECUTOR_SERVICE.scheduleAtFixedRate(new ExpireThreadRandom(), 10, 10, TimeUnit.SECONDS);
    }

}

执行定时任务，这里和Redis保持一致，同样支持快模式和慢模式，快模式时间为10ms，慢模式为100ms

/**
 * 定时执行任务
 */
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);
    }
}

接下来就是过期删除的核心实现

/**
 * 过期信息
 * @param timeoutMills 超时时间
 */
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

这里我们创建了一个List，把需要过期的key全部放入该list中，之后使用random来随机获取下标。

/**
 * 随机获取一个 key 信息
 * @return 随机返回的 keys
 */
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的代价也很大，并且空间复杂度也会高很多。

优化方向1：防止空间浪费

我们想要的就是一个随机的key下标，其实可以直接得到一个随机的下标【也就是随机的大小】，然后遍历expireMap，每遍历一次大小 + 1，找到那个随机的大小，就是我们要找的随机key。

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("对应信息不存在");
}

优化方向2：批处理

上面的方法避免了创建list，优化了空间复杂度，但是从头遍历到1随机的size，时间复杂度也是O(n)。这还只是去一个key，100个key就是100 * O(n)

可以使用批处理的思想，每次指定要处理的key的个数，然后随机一个位置index，那么将index位置后面的key全部取出来，直到取出来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("对应信息不存在");
}

小结

其实就是空间 / 时间的一种均衡，如果我们对于空间不那么看重，就是用List的方式也可以。

如果对时间的要求比较高，使用批处理的方式也挺好的。