從零開始手寫緩存之如何實現固定緩存大小

# 程式設計師的三高

前段時間有一位同事體檢，體檢醫生說他三高。

我打趣道，程式設計師三高不是高性能、高並發、高可用嗎？你是哪三高？

每一個追求性能的開發者，都對高性能孜孜不倦地追求著，而緩存是我們踏上這條高性能大道的必經之路。

小到 cpu 設計，大到服務分布式緩存，我們每時每刻都在接觸緩存，今天我們就一起學習下緩存的發展之路，以及如何如何手寫一個可以指定大小的 cache。

# cache 發展之路

## 古代社會 - HashMap

當我們應用有一定流量之後或者查詢資料庫特別頻繁，這個時候就可以祭出我們的java中自帶的HashMap或者ConcurrentHashMap。

我們可以在代碼中這麼寫:

```java

public class CustomerService {

private HashMap<String,String> hashMap = new HashMap<>();

private CustomerMapper customerMapper;

public String getCustomer(String name){

String customer = hashMap.get(name);

if ( customer == null){

customer = customerMapper.get(name);

hashMap.put(name,customer);

}

return customer;

}

}

```

但是這樣做就有個問題HashMap無法進行數據淘汰，內存會無限制的增長，所以hashMap很快也被淘汰了。

比如以前查詢，查詢 redis，但是希望可以本地緩存放一些熱點數據，使用 HashMap 顯然無法滿足這種需求。

當然，此處可以使用弱引用解決內存一直增長的問題。

當然並不是說他完全就沒用，就像我們古代社會也不是所有的東西都是過時的，比如我們中華名族的傳統美德是永不過時的，

就像這個hashMap一樣的可以在某些場景下作為緩存，當不需要淘汰機制的時候，比如我們利用反射，如果我們每次都通過反射去搜索 Method, Field，性能必定低效，這時我們用HashMap將其緩存起來，性能能提升很多。

## 近代社會 - LRUHashMap

在古代社會中難住我們的問題無法進行數據淘汰，這樣會導致我們內存無限膨脹,顯然我們是不可以接受的。

有人就說我把一些數據給淘汰掉唄，這樣不就對了，但是怎麼淘汰呢？隨機淘汰嗎？

當然不行，試想一下你剛把A裝載進緩存，下一次要訪問的時候就被淘汰了，那又會訪問我們的資料庫了，那我們要緩存幹嘛呢？

所以聰明的人們就發明了幾種淘汰算法，下面列舉下常見的三種FIFO,LRU,LFU（還有一些ARC,MRU感興趣的可以自行搜索）:

### FIFO

先進先出，在這種淘汰算法中，先進入緩存的會先被淘汰。這種可謂是最簡單的了，但是會導致我們命中率很低。

試想一下我們如果有個訪問頻率很高的數據是所有數據第一個訪問的，而那些不是很高的是後面再訪問的，那這樣就會把我們的首個數據但是他的訪問頻率很高給擠出。

### LRU

最近最少使用算法。

在這種算法中避免了上面的問題，每次訪問數據都會將其放在我們的隊尾，如果需要淘汰數據，就只需要淘汰隊首即可。

但是這個依然有個問題，如果有個數據在1個小時的前59分鐘訪問了1萬次(可見這是個熱點數據),再後一分鐘沒有訪問這個數據，但是有其他的數據訪問，就導致了我們這個熱點數據被淘汰。

### LFU

最近最少頻率使用。

在這種算法中又對上面進行了優化，利用額外的空間記錄每個數據的使用頻率，然後選出頻率最低進行淘汰。這樣就避免了LRU不能處理時間段的問題。

上面列舉了三種淘汰策略，對於這三種，實現成本是一個比一個高，同樣的命中率也是一個比一個好。

而我們一般來說選擇的方案居中即可，即實現成本不是太高，而命中率也還行的LRU,如何實現一個LRUMap呢？

我們可以通過繼承 LinkedHashMap，重寫 removeEldestEntry 方法，即可完成一個簡單的 LRUMap。

```java

class LRUMap extends LinkedHashMap {

private final int max;

private Object lock;

public LRUMap(int max, Object lock) {

//無需擴容

super((int) (max * 1.4f), 0.75f, true);

this.max = max;

this.lock = lock;

}

/**

* 重寫LinkedHashMap的removeEldestEntry方法即可

* 在Put的時候判斷，如果為true，就會刪除最老的

* @param eldest

* @return

*/

@Override

protected boolean removeEldestEntry(Map.Entry eldest) {

return size() > max;

}

public Object getValue(Object key) {

synchronized (lock) {

return get(key);

}

}

public void putValue(Object key, Object value) {

synchronized (lock) {

put(key, value);

}

}

public boolean removeValue(Object key) {

synchronized (lock) {

return remove(key) != null;

}

}

public boolean removeAll(){

clear();

return true;

}

}

```

在LinkedHashMap中維護了一個entry(用來放key和value的對象)鍊表。在每一次get或者put的時候都會把插入的新entry，或查詢到的老entry放在我們鍊表末尾。

可以注意到我們在構造方法中，設置的大小特意設置到max*1.4，

在下面的removeEldestEntry方法中只需要size>max就淘汰，這樣我們這個map永遠也走不到擴容的邏輯了，

通過重寫LinkedHashMap，幾個簡單的方法我們實現了我們的LruMap。

## 現代社會 - Guava cache

在近代社會中已經發明出來了LRUMap,用來進行緩存數據的淘汰，但是有幾個問題:

- 鎖競爭嚴重，可以看見我的代碼中，Lock是全局鎖，在方法級別上面的，當調用量較大時，性能必然會比較低。

- 不支持過期時間

- 不支持自動刷新

所以谷歌的大佬們對於這些問題，按捺不住了，發明了Guava cache，在Guava cache中你可以如下面的代碼一樣，輕鬆使用:

```java

public static void main(String[] args) throws ExecutionException {

LoadingCache<String, String> cache = CacheBuilder.newBuilder()

.maximumSize(100)

//寫之後30ms過期

.expireAfterWrite(30L, TimeUnit.MILLISECONDS)

//訪問之後30ms過期

.expireAfterAccess(30L, TimeUnit.MILLISECONDS)

//20ms之後刷新

.refreshAfterWrite(20L, TimeUnit.MILLISECONDS)

//開啟weakKey key 當啟動垃圾回收時，該緩存也被回收

.weakKeys()

.build(createCacheLoader());

System.out.println(cache.get("hello"));

cache.put("hello1", "我是hello1");

System.out.println(cache.get("hello1"));

cache.put("hello1", "我是hello2");

System.out.println(cache.get("hello1"));

}

public static com.google.common.cache.CacheLoader<String, String> createCacheLoader() {

return new com.google.common.cache.CacheLoader<String, String>() {

@Override

public String load(String key) throws Exception {

return key;

}

};

}

```

當然，對於性能的追求是無極限的。

還有：

> Caffeine: [https://houbb.github.io/2018/09/09/cache-caffeine](https://houbb.github.io/2018/09/09/cache-caffeine)

> LevelDB: [https://houbb.github.io/2018/09/06/cache-leveldb-01-start](https://houbb.github.io/2018/09/06/cache-leveldb-01-start)

這些性能更加優越的實現，我們後續可以做一下深入學習。

本文，我們來看一下，如何實現一個固定大小的緩存。

# 代碼實現

## 接口定義

為了兼容 Map，我們定義緩存接口繼承自 Map 接口。

```java

/**

* 緩存接口

* @author binbin.hou

* @since 0.0.1

*/

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

}

```

## 核心實現

我們主要看一下 put 時的實現：

```java

@Override

public V put(K key, V value) {

//1.1 嘗試驅除

CacheEvictContext<K,V> context = new CacheEvictContext<>();

context.key(key).size(sizeLimit).cache(this);

cacheEvict.evict(context);

//2. 判斷驅除後的信息

if(isSizeLimit()) {

throw new CacheRuntimeException("當前隊列已滿，數據添加失敗！");

}

//3. 執行添加

return map.put(key, value);

}

```

這裡我們可以讓用戶動態指定大小，但是指定大小肯就要有對應的淘汰策略。

否則，固定大小的 map 肯定無法放入元素。

## 淘汰策略

淘汰策略可以有多種，比如 LRU/LFU/FIFO 等等，我們此處實現一個最基本的 FIFO。

所有實現以接口的方式實現，便於後期靈活替換。

```java

public class CacheEvictFIFO<K,V> implements ICacheEvict<K,V> {

/**

* queue 信息

* @since 0.0.2

*/

private Queue<K> queue = new LinkedList<>();

@Override

public void evict(ICacheEvictContext<K, V> context) {

final ICache<K,V> cache = context.cache();

// 超過限制，執行移除

if(cache.size() >= context.size()) {

K evictKey = queue.remove();

// 移除最開始的元素

cache.remove(evictKey);

}

// 將新加的元素放入隊尾

final K key = context.key();

queue.add(key);

}

}

```

FIFO 比較簡單，我們使用一個隊列，存儲每一次放入的元素，當隊列超過最大限制時，刪除最早的元素。

## 引導類

為了便於用戶使用，我們實現類似於 guava 的引導類。

所有參數都提供默認值，使用 fluent 流式寫法，提升用戶體驗。

```java

/**

* 緩存引導類

* @author binbin.hou

* @since 0.0.2

*/

public final class CacheBs<K,V> {

private CacheBs(){}

/**

* 創建對象實例

* @param <K> key

* @param <V> value

* @return this

* @since 0.0.2

*/

public static <K,V> CacheBs<K,V> newInstance() {

return new CacheBs<>();

}

/**

* map 實現

* @since 0.0.2

*/

private Map<K,V> map = new HashMap<>();

/**

* 大小限制

* @since 0.0.2

*/

private int size = Integer.MAX_VALUE;

/**

* 驅除策略

* @since 0.0.2

*/

private ICacheEvict<K,V> evict = CacheEvicts.fifo();

/**

* map 實現

* @param map map

* @return this

* @since 0.0.2

*/

public CacheBs<K, V> map(Map<K, V> map) {

ArgUtil.notNull(map, "map");

this.map = map;

return this;

}

/**

* 設置 size 信息

* @param size size

* @return this

* @since 0.0.2

*/

public CacheBs<K, V> size(int size) {

ArgUtil.notNegative(size, "size");

this.size = size;

return this;

}

/**

* 設置驅除策略

* @param evict 驅除策略

* @return this

* @since 0.0.2

*/

public CacheBs<K, V> evict(ICacheEvict<K, V> evict) {

this.evict = evict;

return this;

}

/**

* 構建緩存信息

* @return 緩存信息

* @since 0.0.2

*/

public ICache<K,V> build() {

CacheContext<K,V> context = new CacheContext<>();

context.cacheEvict(evict);

context.map(map);

context.size(size);

return new Cache<>(context);

}

}

```

## 測試使用

```java

ICache<String, String> cache = CacheBs.<String,String>newInstance()

.size(2)

.build();

cache.put("1", "1");

cache.put("2", "2");

cache.put("3", "3");

cache.put("4", "4");

Assert.assertEquals(2, cache.size());

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

```

默認為先進先出的策略，此時輸出 keys，內容如下：

```

[3, 4]

```

# 小結

到這裡，一個簡易版的可以指定大小的緩存就實現了。

完整代碼暫時本項目還沒開源，可以關注【老馬嘯西風】，後臺回復緩存，獲取源碼。

目前為止，這個緩存實現是比較簡單的，顯然難以滿足我們平時更加靈活的應用場景。

我們下一節將一起學習一下如何實現一個可以指定過期的緩存。