要說(shuō)計(jì)算機(jī)系統(tǒng)里，什么技術(shù)把 tradeoff 體現(xiàn)的淋漓盡致，那肯定是緩存無(wú)疑。為了協(xié)調(diào)高速部件和低速部件的速度差異，加入一個(gè)中間緩存層，是解決這種沖突最有效的方案。
其中，JVM堆內(nèi)緩存是緩存體系中重要的一環(huán)，最常用的有 FIFO / LRU / LFU 三種算法。
- FIFO 是簡(jiǎn)單的隊(duì)列，先進(jìn)先出。
- LRU 是最近最少使用，優(yōu)先移除最久未使用的數(shù)據(jù)。是 時(shí)間維度 。
- LFU 是最近最不常用，優(yōu)先移除訪問(wèn)次數(shù)最少的數(shù)據(jù)。是 統(tǒng)計(jì)維度 。
由于過(guò)期也是緩存的一個(gè)重要特點(diǎn)。所有在設(shè)計(jì)這三種緩存算法時(shí)，需要額外的存儲(chǔ)空間去存儲(chǔ)這個(gè)過(guò)期時(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)過(guò)期，則返回null。
- void put(key,value,expireTime)：加入緩存。 無(wú)論此key是否已存在，均作為新key處理（移除舊key）；如果空間不足，則移除已過(guò)期的key，如果沒有，則移除最早加入緩存的key。過(guò)期時(shí)間未指定，則表示永不自動(dòng)過(guò)期。
- 注意，我們?cè)试Skey是有過(guò)期時(shí)間的，這一點(diǎn)與普通的FIFO有所區(qū)別，所以在設(shè)計(jì)此題時(shí)需要注意。（也是面試考察點(diǎn)，偏設(shè)計(jì)而非算法）
普通的FIFO或許大家都能很簡(jiǎn)單的寫出，增加了過(guò)期時(shí)間的考慮之后，在設(shè)計(jì)時(shí)需要多考慮。如下示例，為暫未考慮并發(fā)環(huán)境的FIFO設(shè)計(jì)。
設(shè)計(jì)思路
1）用普通的hashMap保存緩存數(shù)據(jù)。
2）需要額外的map用來(lái)保存key的過(guò)期特性，例子中使用了TreeMap，將“剩余存活時(shí)間”作為key，利用TreeMap的排序特性。
public class FIFOCache {
//按照訪問(wèn)時(shí)間排序,保存所有key-value
private final Map<String,Value> CACHE = new LinkedHashMap<>();
//過(guò)期數(shù)據(jù)，只保存有過(guò)期時(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;
}
//如果不包含過(guò)期時(shí)間
long expired = value.expired;
long now = System.nanoTime();
//已過(guò)期
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) {
//如果容量不足，移除過(guò)期數(shù)據(jù)
if (capacity < CACHE.size()) {
long now = System.nanoTime();
//有過(guò)期的,全部移除
Iterator<Long> iterator = EXPIRED.keySet().iterator();
while (iterator.hasNext()) {
long _key = iterator.next();
//如果已過(guò)期，或者容量仍然溢出，則刪除
if (_key > now) {
break;
}
//一次移除所有過(guò)期key
String _value = EXPIRED.get(_key);
CACHE.remove(_value);
iterator.remove();
}
}
//如果仍然容量不足，則移除最早訪問(wèn)的數(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);
}
//如果指定了過(guò)期時(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; //過(guò)期時(shí)間,納秒
Object value;
Value(long expired,Object value) {
this.expired = expired;
this.value = value;
}
}
}
LRU
least recently used，最近最少使用，是目前最常用的緩存算法和設(shè)計(jì)方案之一，其移除策略為“當(dāng)緩存（頁(yè)）滿時(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已過(guò)期，移除此key，并則返回null。
- void put(key,value,expired)：設(shè)置k-v，如果容量不足，則根據(jù)LRU置換算法移除“最久未被使用的key”。 需要注意，根據(jù)LRU優(yōu)先移除已過(guò)期的keys，如果沒有，則根據(jù)LRU移除未過(guò)期的key。如果未設(shè)定過(guò)期時(shí)間，則認(rèn)為永不自動(dòng)過(guò)期。
- 這里的設(shè)計(jì)關(guān)鍵是過(guò)期時(shí)間特性，這與常規(guī)的LRU有所不同。
設(shè)計(jì)思路
- LRU的基礎(chǔ)算法，需要了解；每次put、get時(shí)需要更新key對(duì)應(yīng)的訪問(wèn)時(shí)間，我們需要一個(gè)數(shù)據(jù)結(jié)構(gòu)能夠保存key最近的訪問(wèn)時(shí)間且能夠排序。
- 既然包含過(guò)期時(shí)間特性，那么帶有過(guò)期時(shí)間的key需要額外的數(shù)據(jù)結(jié)構(gòu)保存。
- 暫時(shí)不考慮并發(fā)操作；盡量兼顧空間復(fù)雜度和時(shí)間復(fù)雜度。
- 此題仍然偏向于設(shè)計(jì)題，而非純粹的算法題。
此題代碼與FIFO基本相同，唯一不同點(diǎn)為get()方法，對(duì)于LRU而言，get方法需要重設(shè)訪問(wèn)時(shí)間（即調(diào)整所在cache中順序）
public Object get(String key) {
//
Value value = CACHE.get(key);
if (value == null) {
return null;
}
//如果不包含過(guò)期時(shí)間
long expired = value.expired;
long now = System.nanoTime();
//已過(guò)期
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í)，移除 訪問(wèn)次數(shù) 最少的元素，如果訪問(wèn)次數(shù)相同的元素有多個(gè)，則移除最久訪問(wèn)的那個(gè)。設(shè)計(jì)要求參見leetcode 460（ LFU Cache）
public class LFUCache {
//主要容器，用于保存k-v
private Map<String, Object> keyToValue = new HashMap<>();
//記錄每個(gè)k被訪問(wèn)的次數(shù)
private Map<String, Integer> keyToCount = new HashMap<>();
//訪問(wèn)相同次數(shù)的key列表，按照訪問(wèn)次數(shù)排序，value為相同訪問(wèn)次數(shù)到key列表。
private TreeMap<Integer, LinkedHashSet<String>> countToLRUKeys = new TreeMap<>();
private int capacity;
public LFUCache(int capacity) {
this.capacity = capacity;
//初始化，默認(rèn)訪問(wèn)1次，主要是解決下文
}
public Object get(String key) {
if (!keyToValue.containsKey(key)) {
return null;
}
touch(key);
return keyToValue.get(key);
}
/**
* 如果一個(gè)key被訪問(wèn)，應(yīng)該將其訪問(wèn)次數(shù)調(diào)整。
* @param key
*/
private void touch(String key) {
int count = keyToCount.get(key);
keyToCount.put(key, count + 1);//訪問(wèn)次數(shù)增加
//從原有訪問(wèn)次數(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;
}
//容量超額之后，移除訪問(wèn)次數(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>
