关于缓存:从零开始手写缓存框架二redis-expire-过期原理及实现

咱们在从零手写 cache 框架（一）实现固定大小的缓存中曾经初步实现了咱们的 cache。

本节，让咱们来一起学习一下如何实现相似 redis 中的 expire 过期性能。

过期是一个十分有用的个性，比方我心愿登录信息放到 redis 中，30min 之后生效；或者单日的累计信息放在 redis 中，在每天的凌晨主动清空。

咱们首先来定义一下接口。

次要有两个：一个是多久之后过期，一个是在什么时候过期。

public interface ICache<K, V> extends Map<K, V> {

    /**
     * 设置过期工夫
     *（1）如果 key 不存在，则什么都不做。*（2）临时不提供新建 key 指定过期工夫的形式，会毁坏原来的办法。*
     * 会做什么：* 相似于 redis
     *（1）惰性删除。* 在执行上面的办法时，如果过期则进行删除。* {@link ICache#get(Object)} 获取
     * {@link ICache#values()} 获取所有值
     * {@link ICache#entrySet()} 获取所有明细
     *
     *【数据的不一致性】* 调用其余办法，可能失去的不是使用者的预期后果，因为此时的 expire 信息可能没有被及时更新。* 比方
     * {@link ICache#isEmpty()} 是否为空
     * {@link ICache#size()} 以后大小
     * 同时会导致以 size() 作为过期条件的问题。*
     * 解决方案：思考增加 refresh 等办法，临时不做一致性的思考。* 对于理论的应用，咱们更关怀 K/V 的信息。*
     *（2）定时删除
     * 启动一个定时工作。每次随机抉择指定大小的 key 进行是否过期判断。* 相似于 redis，为了简化，能够思考设定超时工夫，频率与超时工夫成反比。*
     * 其余拓展性思考：* 前期思考提供原子性操作，保障事务性。临时不做思考。* 此处默认应用 TTL 作为比拟的基准，临时不想反对 LastAccessTime 的淘汰策略。会减少复杂度。* 如果减少 lastAccessTime 过期，本办法能够不做批改。*
     * @param key         key
     * @param timeInMills 毫秒工夫之后过期
     * @return this
     * @since 0.0.3
     */
    ICache<K, V> expire(final K key, final long timeInMills);

    /**
     * 在指定的工夫过期
     * @param key key
     * @param timeInMills 工夫戳
     * @return this
     * @since 0.0.3
     */
    ICache<K, V> expireAt(final K key, final long timeInMills);

}

为了便于解决，咱们将多久之后过期，进行计算。将两个问题变成同一个问题，在什么时候过期的问题。

外围的代码，次要还是看 cacheExpire 接口。

@Override
public ICache<K, V> expire(K key, long timeInMills) {long expireTime = System.currentTimeMillis() + timeInMills;
    return this.expireAt(key, expireTime);
}

@Override
public ICache<K, V> expireAt(K key, long timeInMills) {this.cacheExpire.expire(key, timeInMills);
    return this;
}

这里为了便于前期拓展，对于过期的解决定义为接口，便于前期灵便替换。

其中 expire(final K key, final long expireAt); 就是咱们办法中调用的中央。

refershExpire 属于惰性删除，须要进行刷新时才思考，咱们前面解说。

public interface ICacheExpire<K,V> {

    /**
     * 指定过期信息
     * @param key key
     * @param expireAt 什么时候过期
     * @since 0.0.3
     */
    void expire(final K key, final long expireAt);

    /**
     * 惰性删除中须要解决的 keys
     * @param keyList keys
     * @since 0.0.3
     */
    void refreshExpire(final Collection<K> keyList);

}

其实过期的实思路也比较简单：咱们能够开启一个定时工作，比方 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);
    }
}

如果过期的利用场景不多，那么常常轮训的意义理论不大。

比方咱们的工作 99% 都是在凌晨清空数据，白天无论怎么轮询，纯正是浪费资源。

那有没有什么办法，能够疾速的判断有没有须要解决的过期元素呢？

答案是有的，那就是排序的 MAP。

咱们换一种思路，让过期的工夫做 key，雷同工夫的须要过期的信息放在一个列表中，作为 value。

而后对过期工夫排序，轮询的时候就能够疾速判断出是否有过期的信息了。

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

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

    /**
     * 排序缓存存储
     *
     * 应用依照工夫排序的缓存解决。* @since 0.0.3
     */
    private final Map<Long, List<K>> sortMap = new TreeMap<>(new Comparator<Long>() {
        @Override
        public int compare(Long o1, Long o2) {return (int) (o1-o2);
        }
    });

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

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

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

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

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

    /**
     * 定时执行工作
     * @since 0.0.3
     */
    private class ExpireThread implements Runnable {
        @Override
        public void run() {
            //1. 判断是否为空
            if(MapUtil.isEmpty(sortMap)) {return;}

            //2. 获取 key 进行解决
            int count = 0;
            for(Map.Entry<Long, List<K>> entry : sortMap.entrySet()) {final Long expireAt = entry.getKey();
                List<K> expireKeys = entry.getValue();

                // 判断队列是否为空
                if(CollectionUtil.isEmpty(expireKeys)) {sortMap.remove(expireAt);
                    continue;
                }
                if(count >= LIMIT) {return;}

                // 删除的逻辑解决
                long currentTime = System.currentTimeMillis();
                if(currentTime >= expireAt) {Iterator<K> iterator = expireKeys.iterator();
                    while (iterator.hasNext()) {K key = iterator.next();
                        // 先移除自身
                        iterator.remove();
                        expireMap.remove(key);

                        // 再移除缓存，后续能够通过惰性删除做弥补
                        cache.remove(key);

                        count++;
                    }
                } else {
                    // 间接跳过，没有过期的信息
                    return;
                }
            }
        }
    }

    @Override
    public void expire(K key, long expireAt) {List<K> keys = sortMap.get(expireAt);
        if(keys == null) {keys = new ArrayList<>();
        }
        keys.add(key);

        // 设置对应的信息
        sortMap.put(expireAt, keys);
        expireMap.put(key, expireAt);
    }
}

看起来是切实可行的，这样能够升高轮询的压力。

这里其实应用空间换取工夫，感觉前面能够做一下改良，这种办法性能应该还是不错的。

不过我并没有采纳这个计划，次要是思考到惰性删除的问题，这样会麻烦一些，后续思考继续改善下这个计划。

相似于 redis，咱们采纳定时删除的计划，就有一个问题：可能数据清理的不及时。

那当咱们查问时，可能获取到到是脏数据。

于是就有一些人就想了，当咱们关怀某些数据时，才对数据做对应的删除判断操作，这样压力会小很多。

算是一种折中计划。

个别就是各种查询方法，比方咱们获取 key 对应的值时

@Override
@SuppressWarnings("unchecked")
public V get(Object key) {
    //1. 刷新所有过期信息
    K genericKey = (K) key;
    this.cacheExpire.refreshExpire(Collections.singletonList(genericKey));
    return map.get(key);
}

咱们在获取之前，先做一次数据的刷新。

实现原理也非常简单，就是一个循环，而后作删除即可。

这里加了一个小的优化：抉择数量少的作为外循环。

循环汇合的工夫复杂度是 O(n), map.get() 的工夫复杂度是 O(1);

@Override
public void refreshExpire(Collection<K> keyList) {if(CollectionUtil.isEmpty(keyList)) {return;}
    // 判断大小，小的作为外循环。个别都是过期的 keys 比拟小。if(keyList.size() <= expireMap.size()) {for(K key : keyList) {expireKey(key);
        }
    } else {for(Map.Entry<K, Long> entry : expireMap.entrySet()) {this.expireKey(entry);
        }
    }
}

下面的代码写完之后，咱们就能够验证一下了。

ICache<String, String> cache = CacheBs.<String,String>newInstance()
        .size(3)
        .build();
cache.put("1", "1");
cache.put("2", "2");

cache.expire("1", 10);
Assert.assertEquals(2, cache.size());

TimeUnit.MILLISECONDS.sleep(50);
Assert.assertEquals(1, cache.size());

System.out.println(cache.keySet());

后果也合乎咱们的预期。

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

当然，还有很多优化的中央。

比方为了后续增加各种监听器不便，我对所有须要刷新的中央调整为应用字节码 + 注解的形式，而不是在每一个须要的办法中增加刷新办法。

下一节，咱们将独特学习下如何实现各种监听器。

对你有帮忙的话，欢送点赞评论珍藏关注一波走起~

你的激励，是我最大的能源~

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

关于缓存:从零开始手写缓存框架二redis-expire-过期原理及实现

前言

代码实现

接口

代码实现

缓存过期

接口

expire 实现原理

过期信息的存储

轮询清理

清空工作

清空的优化思路

惰性删除

呈现的起因

须要惰性删除的办法

刷新的实现

测试

小结

原文地址