前言

咱们在 从零手写 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 接口。

@Overridepublic ICache<K, V> expire(K key, long timeInMills) {    long expireTime = System.currentTimeMillis() + timeInMills;    return this.expireAt(key, expireTime);}@Overridepublic 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);}

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);    }}

清空的优化思路

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

比方咱们的工作 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);

@Overridepublic 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 过期实现原理