要說計(jì)算機(jī)系統(tǒng)里，什么技術(shù)把tradeoff體現(xiàn)的淋漓盡致，那肯定是緩存無疑。為了協(xié)調(diào)高速部件和低速部件的速度差異，加入一個(gè)中間緩存層，是解決這種沖突最有效的方案。

[[325756]]

其中，JVM堆內(nèi)緩存是緩存體系中重要的一環(huán)，最常用的有FIFO/LRU/LFU三種算法。

1. FIFO是簡(jiǎn)單的隊(duì)列，先進(jìn)先出。
2. LRU是最近最少使用，優(yōu)先移除最久未使用的數(shù)據(jù)。是時(shí)間維度。
3. LFU是最近最不常用，優(yōu)先移除訪問次數(shù)最少的數(shù)據(jù)。是統(tǒng)計(jì)維度。

由于過期也是緩存的一個(gè)重要特點(diǎn)。所有在設(shè)計(jì)這三種緩存算法時(shí)，需要額外的存儲(chǔ)空間去存儲(chǔ)這個(gè)過期時(shí)間。

以下將討論這三種緩存算法的操作和設(shè)計(jì)要點(diǎn)，但暫未考慮高并發(fā)環(huán)境。

FIFO

先進(jìn)先出，如果緩存容量滿，則優(yōu)先移出最早加入緩存的數(shù)據(jù);其內(nèi)部可以使用隊(duì)列實(shí)現(xiàn)。

操作

• Object get(key) ：獲取保存的數(shù)據(jù)，如果數(shù)據(jù)不存在或者已經(jīng)過期，則返回null。
• void put(key,value,expireTime)：加入緩存。 無論此key是否已存在，均作為新key處理(移除舊key);如果空間不足，則移除已過期的key，如果沒有，則移除最早加入緩存的key。過期時(shí)間未指定，則表示永不自動(dòng)過期。
• 注意 ，我們?cè)试Skey是有過期時(shí)間的，這一點(diǎn)與普通的FIFO有所區(qū)別，所以在設(shè)計(jì)此題時(shí)需要注意。(也是面試考察點(diǎn)，偏設(shè)計(jì)而非算法)

普通的FIFO或許大家都能很簡(jiǎn)單的寫出，增加了過期時(shí)間的考慮之后，在設(shè)計(jì)時(shí)需要多考慮。如下示例，為暫未考慮并發(fā)環(huán)境的FIFO設(shè)計(jì)。

設(shè)計(jì)思路

1)用普通的hashMap保存緩存數(shù)據(jù)。

2)需要額外的map用來保存key的過期特性，例子中使用了TreeMap，將“剩余存活時(shí)間”作為key，利用TreeMap的排序特性。

public class FIFOCache { 
   
    //按照訪問時(shí)間排序,保存所有key-value 
    private final Map<String,Value> CACHE = new LinkedHashMap<>(); 
   
    //過期數(shù)據(jù)，只保存有過期時(shí)間的key 
    //暫不考慮并發(fā)，我們認(rèn)為同一個(gè)時(shí)間內(nèi)沒有重復(fù)的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; 
        } 
   
        //如果不包含過期時(shí)間 
        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) { 
        //如果容量不足，移除過期數(shù)據(jù) 
        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(); 
            } 
        } 
   
        //如果仍然容量不足，則移除最早訪問的數(shù)據(jù) 
        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已存在,移除舊數(shù)據(jù) 
        Value current = CACHE.remove(key); 
        if (current != null && current.expired > 0) { 
            EXPIRED.remove(current.expired); 
        } 
        //如果指定了過期時(shí)間 
        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; //過期時(shí)間,納秒 
        Object value; 
        Value(long expired,Object value) { 
            this.expired = expired; 
            this.value = value; 
        } 
    } 
} 

LRU

least recently used，最近最少使用，是目前最常用的緩存算法和設(shè)計(jì)方案之一，其移除策略為“當(dāng)緩存(頁)滿時(shí)，優(yōu)先移除最近最久未使用的數(shù)據(jù)”，優(yōu)點(diǎn)是易于設(shè)計(jì)和使用，適用場(chǎng)景廣泛。算法可以參考leetcode 146 (LRU Cache)。

操作

• Object get(key)：從cache中獲取key對(duì)應(yīng)的數(shù)據(jù)，如果此key已過期，移除此key，并則返回null。
• void put(key,value,expired)：設(shè)置k-v，如果容量不足，則根據(jù)LRU置換算法移除“最久未被使用的key”。 需要注意，根據(jù)LRU優(yōu)先移除已過期的keys，如果沒有，則根據(jù)LRU移除未過期的key。如果未設(shè)定過期時(shí)間，則認(rèn)為永不自動(dòng)過期。
• 這里的設(shè)計(jì)關(guān)鍵是過期時(shí)間特性，這與常規(guī)的LRU有所不同。

設(shè)計(jì)思路

• LRU的基礎(chǔ)算法，需要了解;每次put、get時(shí)需要更新key對(duì)應(yīng)的訪問時(shí)間，我們需要一個(gè)數(shù)據(jù)結(jié)構(gòu)能夠保存key最近的訪問時(shí)間且能夠排序。
• 既然包含過期時(shí)間特性，那么帶有過期時(shí)間的key需要額外的數(shù)據(jù)結(jié)構(gòu)保存。
• 暫時(shí)不考慮并發(fā)操作;盡量兼顧空間復(fù)雜度和時(shí)間復(fù)雜度。
• 此題仍然偏向于設(shè)計(jì)題，而非純粹的算法題。

此題代碼與FIFO基本相同，唯一不同點(diǎn)為get()方法，對(duì)于LRU而言，get方法需要重設(shè)訪問時(shí)間(即調(diào)整所在cache中順序)

public Object get(String key) { 
    // 
    Value value = CACHE.get(key); 
    if (value == null) { 
        return null; 
    } 
   
    //如果不包含過期時(shí)間 
    long expired = value.expired; 
    long now = System.nanoTime(); 
    //已過期 
    if (expired > 0 && expired <= now) { 
        CACHE.remove(key); 
        EXPIRED.remove(expired); 
        return null; 
    } 
    //相對(duì)于FIFO，增加順序重置 
    CACHE.remove(key); 
    CACHE.put(key,value); 
    return value.value; 
} 

LFU

最近最不常用，當(dāng)緩存容量滿時(shí)，移除 訪問次數(shù) 最少的元素，如果訪問次數(shù)相同的元素有多個(gè)，則移除最久訪問的那個(gè)。設(shè)計(jì)要求參見leetcode 460( LFU Cache)

public class LFUCache { 
   
    //主要容器，用于保存k-v 
    private Map<String, Object> keyToValue = new HashMap<>(); 
   
    //記錄每個(gè)k被訪問的次數(shù) 
    private Map<String, Integer> keyToCount = new HashMap<>(); 
   
    //訪問相同次數(shù)的key列表，按照訪問次數(shù)排序，value為相同訪問次數(shù)到key列表。 
    private TreeMap<Integer, LinkedHashSet<String>> countToLRUKeys = new TreeMap<>(); 
   
    private int capacity; 
   
    public LFUCache(int capacity) { 
        this.capacity = capacity; 
        //初始化，默認(rèn)訪問1次，主要是解決下文 
    } 
   
    public Object get(String key) { 
        if (!keyToValue.containsKey(key)) { 
            return null; 
        } 
   
        touch(key); 
        return keyToValue.get(key); 
    } 
   
    /** 
     * 如果一個(gè)key被訪問，應(yīng)該將其訪問次數(shù)調(diào)整。 
     * @param key 
     */   
    private void touch(String key) { 
        int count = keyToCount.get(key); 
        keyToCount.put(key, count + 1);//訪問次數(shù)增加 
        //從原有訪問次數(shù)統(tǒng)計(jì)列表中移除 
        countToLRUKeys.get(count).remove(key); 
   
        //如果符合最少調(diào)用次數(shù)到key統(tǒng)計(jì)列表為空，則移除此調(diào)用次數(shù)到統(tǒng)計(jì) 
        if (countToLRUKeys.get(count).size() == 0) { 
            countToLRUKeys.remove(count); 
        } 
   
        //然后將此key的統(tǒng)計(jì)信息加入到管理列表中 
        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; 
        } 
        //容量超額之后，移除訪問次數(shù)最少的元素 
        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本文力求比較三個(gè)基本的緩存算法，以便對(duì)緩存建設(shè)之路有一個(gè)比較籠統(tǒng)的感覺。

更加易用的cache，可以參考guava的實(shí)現(xiàn)。謹(jǐn)希望這三個(gè)代碼模版，能夠?qū)δ阌兴鶐椭?/p>

作者簡(jiǎn)介：小姐姐味道 (xjjdog)，一個(gè)不允許程序員走彎路的公眾號(hào)。聚焦基礎(chǔ)架構(gòu)和Linux。十年架構(gòu)，日百億流量，與你探討高并發(fā)世界，給你不一樣的味道。