前言

java從零手寫實現redis（一）如何實現固定大小的緩存？

java從零手寫實現redis（三）redis expire 過期原理

java從零手寫實現redis（三）內存數據如何重啓不丟失？

java從零手寫實現redis（四）添加監聽器

前面實現了 redis 的幾個基本特性，其中在 expire 過期原理時，提到了另外一種實現方式。

這裏將其記錄下來，可以拓展一下自己的思路。

以前的實現方式

核心思路

原來的實現方式見：

java從零手寫實現redis（三）redis expire 過期原理

https://mp.weixin.qq.com/s/BW...

不足

以前的設計非常簡單，符合最基本的思路，就是將過期的信息放在一個 map 中，然後去遍歷清空。

為了避免單次操作時間過長，類似 redis，單次操作 100 個元素之後，直接返回。

不過定時任務之心時，其實存在兩個不足：

（1）keys 的選擇不夠隨機，可能會導致每次循環 100 個結束時，真正需要過期的沒有被遍歷到。

不過 map 的隨機比較蠢，就是將 map 的 keys 全部轉為集合，然後通過 random 返回。

轉的過程就是一個時間複雜度為 O(n) 的遍歷，所以一開始沒有去實現。

還有一種方式，就是用空間換區時間，存儲的時候，同時存儲在 list 中，然後隨機返回處理，這個後續優化。

（2）keys 的遍歷可能大部分都是無效的。

我們每次都是根據 keys 從前往後遍歷，但是沒有關心對應的過期時間，所以導致很多無效遍歷。

本文主要提供一種以過期時間為維度的實現方式，僅供參考，因為這種方式也存在缺陷。

基於時間的遍歷

思路

我們每次 put 放入過期元素時，根據過期時間對元素進行排序，相同的過期時間的 Keys 放在一起。

優點：定時遍歷的時候，如果時間不到當前時間，就可以直接返回了，大大降低無效遍歷。

缺點：考慮到惰性刪除問題，還是需要存儲以刪除信息作為 key 的 map 關係，這樣內存基本翻倍。

基本屬性定義

我們這裏使用 TreeMap 幫助我們進行過期時間的排序，這個集合後續有時間可以詳細講解了，我大概看了下 jdk1.8 的源碼，主要是通過紅黑樹實現的。

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;

}

放入元素時

每次存入新元素時，同時放入 sortMap 和 expireMap。

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

定時任務的執行

定義

我們定義一個定時任務，100ms 執行一次。

/**
 * 線程執行類
 * @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(), 100, 100, TimeUnit.MILLISECONDS);
}

執行任務

實現源碼如下：

/**
 * 定時執行任務
 * @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;
            }
        }
    }
}

這裏直接遍歷 sortMap，對應的 key 就是過期時間，然後和當前時間對比即可。

刪除的時候，需要刪除 expireMap/sortMap/cache。

惰性刪除刷新

惰性刪除刷新時，就會用到 expireMap。

因為有時候刷新的 key 就一個，如果沒有 expireMap 映射關係，可能要把 sortMap 全部遍歷一遍才能找到對應的過期時間。

就是一個時間複雜度與空間複雜度衡量的問題。

@Override
public void refreshExpire(Collection<K> keyList) {
    if(CollectionUtil.isEmpty(keyList)) {
        return;
    }
    // 這樣維護兩套的代價太大，後續優化，暫時不用。
    // 判斷大小，小的作為外循環
    final int expireSize = expireMap.size();
    if(expireSize <= keyList.size()) {
        // 一般過期的數量都是較少的
        for(Map.Entry<K,Long> entry : expireMap.entrySet()) {
            K key = entry.getKey();
            // 這裏直接執行過期處理，不再判斷是否存在於集合中。
            // 因為基於集合的判斷，時間複雜度為 O(n)
            this.removeExpireKey(key);
        }
    } else {
        for(K key : keyList) {
            this.removeExpireKey(key);
        }
    }
}

/**
 * 移除過期信息
 * @param key key
 * @since 0.0.10
 */
private void removeExpireKey(final K key) {
    Long expireTime = expireMap.get(key);
    if(expireTime != null) {
        final long currentTime = System.currentTimeMillis();
        if(currentTime >= expireTime) {
            expireMap.remove(key);
            List<K> expireKeys = sortMap.get(expireTime);
            expireKeys.remove(key);
            sortMap.put(expireTime, expireKeys);
        }
    }
}

小結

實現過期的方法有很多種，目前我們提供的兩種方案，都各有優缺點，我相信會有更加優秀的方式。

程序 = 數據結構 + 算法

redis 之所以性能這麼優異，其實和其中的數據結構與算法用的合理是分不開的，優秀的框架值得反覆學習和思考。

文中主要講述了思路，實現部分因為篇幅限制，沒有全部貼出來。

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

覺得本文對你有幫助的話，歡迎點贊評論收藏關注一波~

你的鼓勵，是我最大的動力~