一個基于Java簡單的 Cache 淘汰策略

Smart 框架一切都圍繞著輕量、簡單、實用的方向在努力，對于 Cache 插件也不例外。最近忙著拉項目，所以投入在 Smart 的精力就不多了。前幾天有朋友想讓我寫一個 Cache 淘汰策略，當時腦海里有幾個算法，例如：

• LRU（Least Recently Used）：最近最少使用算法，淘汰最近一段時間內未被使用的。
• LFU（Least Frequently Used）：最近最不常使用算法，淘汰最近一定時間內使用最少的。
• FIFO（First In First Out）：先進先出算法，淘汰最早使用的。

當然還有其他更加優秀的算法，我目前只想選擇一種最簡單的作為缺省的實現，對于特定的需求，將來還可以進行擴展。

以上前兩種比較類似，都是針對是使用性來進行淘汰，稍許有些復雜，所以我選擇了類似 FIFO 的算法，通過時間來判斷是否淘汰。具體來說，在放入 Cache 的時候指定一個過期時間（1分鐘、10分鐘、1個小時、1天等），再用一個線程去輪詢放在 Cache 里的過期時間，若已過期，則直接從 Cache 中移除。

這種策略往往實現起來比較簡單，也非常實用，不妨先實現這種算法吧。

第一步：定義一個 Expiry 常量接口

public interface Expiry {

    long ETERNAL = -1;
    long ZERO = 0;
    long ONE_MINUTE = 60 * 1000;
    long FIVE_MINUTES = 5 * ONE_MINUTE;
    long TEN_MINUTES = 10 * ONE_MINUTE;
    long TWENTY_MINUTES = 20 * ONE_MINUTE;
    long THIRTY_MINUTES = 30 * ONE_MINUTE;
    long ONE_HOUR = 60 * ONE_MINUTE;
    long ONE_DAY = 24 * ONE_HOUR;
}

該接口里面有許多常用的時間選項。該接口的定義參考了 JSR 107 規范。

第二步：定義一個 Duration 類

public class Duration {

    private long start;  // 當前時間
    private long expiry; // 過期時間（毫秒）

    public Duration(long start, long expiry) {
        this.start = start;
        this.expiry = expiry;
    }

    public long getStart() {
        return start;
    }

    public long getExpiry() {
        return expiry;
    }
}

其中包括了當前時間，是指放入 Cache 的時間。此外還包括一個過期時間，用毫秒表示，這個字段可以使用 Expiry 常量接口中的選項。

第三步：為 CachePut 注解添加一個 expiry 屬性

@Target(ElementType.METHOD)
@Retention(RetentionPolicy.RUNTIME)
public @interface CachePut {

    String value();

    long expiry() default Expiry.ETERNAL;
}

默認過期時間為 Expiry.ETERNAL，也就是永不過期的意思。

第四步：擴展幾個 Cache 相關類

Cache 接口：

public interface Cache<K, V> {

    // 從 Cache 中獲取數據
    V get(K key);

    // 將數據放入 Cache 中
    void put(K key, V value);

    // 將數據放入 Cache 中，指定有效期（ms）
    void put(K key, V value, long expiry);

    // 從 Cache 中移除數據
    boolean remove(K key);

    // 清空 Cache
    void clear();

    // 獲取所有的 Duration
    Map<K, Duration> getDurations();
}

添加了兩個方法：

void put(K key, V value, long expiry); 當初始化 Cache 的時候可以傳入一個過期時間。
Map<K, Duration> getDurations(); 返回所有的過期對象，也就是一組 Cache key 與 Duration 的映射關系。

CacheManager 接口：

public interface CacheManager {

    // 獲取所有的 Cache
    Iterable<Cache> getCaches();

    // 創建 Cache
    <K, V> Cache<K, V> createCache(String cacheName);

    // 獲取 Cache
    <K, V> Cache<K, V> getCache(String cacheName);

    // 銷毀指定 Cache
    void destroyCache(String cacheName);
}

為該接口添加了一個方法：

Iterable<Cache> getCaches(); 返回 CacheManager 中所管理的所有 Cache 對象。為了在循環中迭代，所以返回了 Iterable 接口。

CacheFactory 工廠類：

public class CacheFactory {

    // 定義一個 CacheManager Map，用于存放目標類與 CacheManager 的對應關系（一個目標類對應一個 CacheManager），目標類一般為 Service 類
    private static final Map<Class<?>, CacheManager> cacheManagerMap = new HashMap<Class<?>, CacheManager>();

    public static Iterable<CacheManager> getCacheManagers() {
        return cacheManagerMap.values();
    }
...
}

對外提供了一個 getCacheManagers 方法，便于訪問 CacheFactory 中的私有成員 cacheManagerMap。

第五步：提供一個 CacheThread，用于實現淘汰算法

public class CacheThread extends Thread {

    @Override
    @SuppressWarnings("unchecked")
    public void run() {
        try {
            while (true) {
                // 遍歷所有的 Cache Manager
                Iterable<CacheManager> cacheManagers = CacheFactory.getCacheManagers();
                for (CacheManager cacheManager : cacheManagers) {
                    // 遍歷所有的 Cache
                    Iterable<Cache> caches = cacheManager.getCaches();
                    for (Cache cache : caches) {
                        // 遍歷所有的 Duration Map
                        Map<Object, Duration> durationMap = cache.getDurations();
                        for (Object entrySet : durationMap.entrySet()) {
                            // 獲取 Duration Map 中的 key 與 value
                            Map.Entry<Object, Duration> entry = (Map.Entry<Object, Duration>) entrySet;
                            Object cacheKey = entry.getKey();
                            Duration duration = entry.getValue();
                            // 獲取 Duration 中的相關數據
                            long start = duration.getStart();   // 開始時間
                            long expiry = duration.getExpiry(); // 過期時間
                            // 獲取當前時間
                            long current = System.currentTimeMillis();
                            // 判斷是否已過期
                            if (current - start >= expiry) {
                                // 若已過期，則首先移除 Cache，然后移除 Duration Map 中的 entry
                                cache.remove(cacheKey);
                                durationMap.remove(cacheKey);
                            }
                        }
                    }
                }
                // 使線程休眠 5 秒鐘
                sleep(5000);
            }
        } catch (InterruptedException e) {
            throw new CacheException("錯誤：運行 CacheThead 出現異常！", e);
        }
    }
}

以上代碼從 CacheManager 開始進行遍歷，最終獲取相應的 Cache，并從中獲取 Duration，通過很簡單的方法就能判斷出 Cache 是否已過期，過期了就從 Cache 中移除，同時也要移除 Duration Map 中相應的條目。

這個線程如何才能開啟呢？需要找個地方初始化。

第六步：創建一個 CachePlugin 類并實現 Plugin 接口

public class CachePlugin implements Plugin {

    @Override
    public void init() {
        new CacheThread().start();
    }
}

Plugin 接口由 Smart 框架提供，此時只需實現該接口，在 init 方法中完成初始化工作即可，也就是開啟 CacheThread 這個線程。

還差什么呢？那就是如何去使用這個新的特性了！

最后一步：配置 Cache 過期時間

不妨使用注解的方式來配置過期時間，當然也可以通過 API 的方式來設置。

@Bean
@Cachable
public class CustomerServiceCacheAnnotationImpl extends BaseService implements CustomerService {

    @Override
    @CachePut(value = "customer_list_cache", expiry = Expiry.ONE_MINUTE)
    public List<Customer> getCustomerList() {
        return DataSet.selectList(Customer.class, "", "");
    }
...
}

這里將 customer_list_cache 這個名稱的 Cache 的過期時間設置為 1 分鐘。

來自：http://my.oschina.net/huangyong/blog/177559