3種堆內緩存算法，贈源碼和設計思路
作者：小姐姐養的狗
要說計算機系統里，什么技術把tradeoff體現的淋漓盡致，那肯定是緩存無疑。為了協調高速部件和低速部件的速度差異，加入一個中間緩存層，是解決這種沖突最有效的方案。
要說計算機系統里，什么技術把tradeoff體現的淋漓盡致，那肯定是緩存無疑。為了協調高速部件和低速部件的速度差異，加入一個中間緩存層，是解決這種沖突最有效的方案。
其中，JVM堆內緩存是緩存體系中重要的一環，最常用的有FIFO/LRU/LFU三種算法。
- FIFO是簡單的隊列，先進先出。
- LRU是最近最少使用，優先移除最久未使用的數據。是時間維度。
- LFU是最近最不常用，優先移除訪問次數最少的數據。是統計維度。
由于過期也是緩存的一個重要特點。所有在設計這三種緩存算法時，需要額外的存儲空間去存儲這個過期時間。
以下將討論這三種緩存算法的操作和設計要點，但暫未考慮高并發環境。
FIFO
先進先出，如果緩存容量滿，則優先移出最早加入緩存的數據;其內部可以使用隊列實現。
操作
- Object get(key) ：獲取保存的數據，如果數據不存在或者已經過期，則返回null。
- void put(key,value,expireTime)：加入緩存。 無論此key是否已存在，均作為新key處理(移除舊key);如果空間不足，則移除已過期的key，如果沒有，則移除最早加入緩存的key。過期時間未指定，則表示永不自動過期。
- 注意 ，我們允許key是有過期時間的，這一點與普通的FIFO有所區別，所以在設計此題時需要注意。(也是面試考察點，偏設計而非算法)
普通的FIFO或許大家都能很簡單的寫出，增加了過期時間的考慮之后，在設計時需要多考慮。如下示例，為暫未考慮并發環境的FIFO設計。
設計思路
1)用普通的hashMap保存緩存數據。
2)需要額外的map用來保存key的過期特性，例子中使用了TreeMap，將“剩余存活時間”作為key，利用TreeMap的排序特性。
- public class FIFOCache {
- //按照訪問時間排序,保存所有key-value
- private final Map<String,Value> CACHE = new LinkedHashMap<>();
- //過期數據，只保存有過期時間的key
- //暫不考慮并發，我們認為同一個時間內沒有重復的key，如果改造的話，可以將value換成set
- private final TreeMap<Long, String> EXPIRED = new TreeMap<>();
- private final int capacity;
- public FIFOCache(int capacity) {
- this.capacity = capacity;
- }
- public Object get(String key) {
- //
- Value value = CACHE.get(key);
- if (value == null) {
- return null;
- }
- //如果不包含過期時間
- long expired = value.expired;
- long now = System.nanoTime();
- //已過期
- if (expired > 0 && expired <= now) {
- CACHE.remove(key);
- EXPIRED.remove(expired);
- return null;
- }
- return value.value;
- }
- public void put(String key,Object value) {
- put(key,value,-1);
- }
- public void put(String key,Object value,int seconds) {
- //如果容量不足，移除過期數據
- if (capacity < CACHE.size()) {
- long now = System.nanoTime();
- //有過期的,全部移除
- Iterator<Long> iterator = EXPIRED.keySet().iterator();
- while (iterator.hasNext()) {
- long _key = iterator.next();
- //如果已過期，或者容量仍然溢出，則刪除
- if (_key > now) {
- break;
- }
- //一次移除所有過期key
- String _value = EXPIRED.get(_key);
- CACHE.remove(_value);
- iterator.remove();
- }
- }
- //如果仍然容量不足，則移除最早訪問的數據
- if (capacity < CACHE.size()) {
- Iterator<String> iterator = CACHE.keySet().iterator();
- while (iterator.hasNext() && capacity < CACHE.size()) {
- String _key = iterator.next();
- Value _value = CACHE.get(_key);
- long expired = _value.expired;
- if (expired > 0) {
- EXPIRED.remove(expired);
- }
- iterator.remove();
- }
- }
- //如果此key已存在,移除舊數據
- Value current = CACHE.remove(key);
- if (current != null && current.expired > 0) {
- EXPIRED.remove(current.expired);
- }
- //如果指定了過期時間
- if(seconds > 0) {
- long expireTime = expiredTime(seconds);
- EXPIRED.put(expireTime,key);
- CACHE.put(key,new Value(expireTime,value));
- } else {
- CACHE.put(key,new Value(-1,value));
- }
- }
- private long expiredTime(int expired) {
- return System.nanoTime() + TimeUnit.SECONDS.toNanos(expired);
- }
- public void remove(String key) {
- Value value = CACHE.remove(key);
- if(value == null) {
- return;
- }
- long expired = value.expired;
- if (expired > 0) {
- EXPIRED.remove(expired);
- }
- }
- class Value {
- long expired; //過期時間,納秒
- Object value;
- Value(long expired,Object value) {
- this.expired = expired;
- this.value = value;
- }
- }
- }
LRU
least recently used，最近最少使用，是目前最常用的緩存算法和設計方案之一，其移除策略為“當緩存(頁)滿時，優先移除最近最久未使用的數據”，優點是易于設計和使用，適用場景廣泛。算法可以參考leetcode 146 (LRU Cache)。
操作
- Object get(key)：從cache中獲取key對應的數據，如果此key已過期，移除此key，并則返回null。
- void put(key,value,expired)：設置k-v，如果容量不足，則根據LRU置換算法移除“最久未被使用的key”。 需要注意，根據LRU優先移除已過期的keys，如果沒有，則根據LRU移除未過期的key。如果未設定過期時間，則認為永不自動過期。
- 這里的設計關鍵是過期時間特性，這與常規的LRU有所不同。
設計思路
- LRU的基礎算法，需要了解;每次put、get時需要更新key對應的訪問時間，我們需要一個數據結構能夠保存key最近的訪問時間且能夠排序。
- 既然包含過期時間特性，那么帶有過期時間的key需要額外的數據結構保存。
- 暫時不考慮并發操作;盡量兼顧空間復雜度和時間復雜度。
- 此題仍然偏向于設計題，而非純粹的算法題。
此題代碼與FIFO基本相同，唯一不同點為get()方法，對于LRU而言，get方法需要重設訪問時間(即調整所在cache中順序)
- public Object get(String key) {
- //
- Value value = CACHE.get(key);
- if (value == null) {
- return null;
- }
- //如果不包含過期時間
- long expired = value.expired;
- long now = System.nanoTime();
- //已過期
- if (expired > 0 && expired <= now) {
- CACHE.remove(key);
- EXPIRED.remove(expired);
- return null;
- }
- //相對于FIFO，增加順序重置
- CACHE.remove(key);
- CACHE.put(key,value);
- return value.value;
- }
LFU
最近最不常用，當緩存容量滿時，移除 訪問次數 最少的元素，如果訪問次數相同的元素有多個，則移除最久訪問的那個。設計要求參見leetcode 460( LFU Cache)
- public class LFUCache {
- //主要容器，用于保存k-v
- private Map<String, Object> keyToValue = new HashMap<>();
- //記錄每個k被訪問的次數
- private Map<String, Integer> keyToCount = new HashMap<>();
- //訪問相同次數的key列表，按照訪問次數排序，value為相同訪問次數到key列表。
- private TreeMap<Integer, LinkedHashSet<String>> countToLRUKeys = new TreeMap<>();
- private int capacity;
- public LFUCache(int capacity) {
- this.capacity = capacity;
- //初始化，默認訪問1次，主要是解決下文
- }
- public Object get(String key) {
- if (!keyToValue.containsKey(key)) {
- return null;
- }
- touch(key);
- return keyToValue.get(key);
- }
- /**
- * 如果一個key被訪問，應該將其訪問次數調整。
- * @param key
- */
- private void touch(String key) {
- int count = keyToCount.get(key);
- keyToCount.put(key, count + 1);//訪問次數增加
- //從原有訪問次數統計列表中移除
- countToLRUKeys.get(count).remove(key);
- //如果符合最少調用次數到key統計列表為空，則移除此調用次數到統計
- if (countToLRUKeys.get(count).size() == 0) {
- countToLRUKeys.remove(count);
- }
- //然后將此key的統計信息加入到管理列表中
- LinkedHashSet<String> countKeys = countToLRUKeys.get(count + 1);
- if (countKeys == null) {
- countKeys = new LinkedHashSet<>();
- countToLRUKeys.put(count + 1,countKeys);
- }
- countKeys.add(key);
- }
- public void put(String key, Object value) {
- if (capacity <= 0) {
- return;
- }
- if (keyToValue.containsKey(key)) {
- keyToValue.put(key, value);
- touch(key);
- return;
- }
- //容量超額之后，移除訪問次數最少的元素
- if (keyToValue.size() >= capacity) {
- Map.Entry<Integer,LinkedHashSet<String>> entry = countToLRUKeys.firstEntry();
- Iterator<String> it = entry.getValue().iterator();
- String evictKey = it.next();
- it.remove();
- if (!it.hasNext()) {
- countToLRUKeys.remove(entry.getKey());
- }
- keyToCount.remove(evictKey);
- keyToValue.remove(evictKey);
- }
- keyToValue.put(key, value);
- keyToCount.put(key, 1);
- LinkedHashSet<String> keys = countToLRUKeys.get(1);
- if (keys == null) {
- keys = new LinkedHashSet<>();
- countToLRUKeys.put(1,keys);
- }
- keys.add(key);
- }
- }
End本文力求比較三個基本的緩存算法，以便對緩存建設之路有一個比較籠統的感覺。
更加易用的cache，可以參考guava的實現。謹希望這三個代碼模版，能夠對你有所幫助。
作者簡介：小姐姐味道 (xjjdog)，一個不允許程序員走彎路的公眾號。聚焦基礎架構和Linux。十年架構，日百億流量，與你探討高并發世界，給你不一樣的味道。
責任編輯：武曉燕
來源：
小姐姐味道
