假設(shè)有個(gè)項(xiàng)目有一定并發(fā)量，要用到多級(jí)緩存，如下：
在實(shí)際設(shè)計(jì)一個(gè)內(nèi)存緩存前，我們需要考慮的問(wèn)題：
1：內(nèi)存與Redis的數(shù)據(jù)置換，盡可能在內(nèi)存中提高數(shù)據(jù)命中率，減少下一級(jí)的壓力。
2：內(nèi)存容量的限制，需要控制緩存數(shù)量。
3：熱點(diǎn)數(shù)據(jù)更新不同，需要可配置單個(gè)key過(guò)期時(shí)間。
4：良好的緩存過(guò)期刪除策略。
5：緩存數(shù)據(jù)結(jié)構(gòu)的復(fù)雜度盡可能的低。
關(guān)于置換及命中率：我們采用LRU算法，因?yàn)樗鼘?shí)現(xiàn)簡(jiǎn)單，緩存key命中率也很好。
LRU即是：把最近最少訪問(wèn)的數(shù)據(jù)給淘汰掉，經(jīng)常被訪問(wèn)到即是熱點(diǎn)數(shù)據(jù)。
關(guān)于LRU數(shù)據(jù)結(jié)構(gòu)：因?yàn)閗ey優(yōu)先級(jí)提升和key淘汰，所以需要順序結(jié)構(gòu)。我看到大多實(shí)現(xiàn)，都采用鏈表結(jié)構(gòu)、
即：新數(shù)據(jù)插入到鏈表頭部、被命中時(shí)的數(shù)據(jù)移動(dòng)到頭部。 添加復(fù)雜度O(1) 移動(dòng)和獲取復(fù)雜度O(N)。
有沒(méi)復(fù)雜度更低的呢？ 有Dictionary，復(fù)雜度為O(1)，性能最好。 那如何保證緩存的優(yōu)先級(jí)提升呢？
二：O(1)LRU實(shí)現(xiàn)
我們定義個(gè)LRUCache<TValue>類，構(gòu)造參數(shù)maxKeySize 來(lái)控制緩存最大數(shù)量。
使用ConcurrentDictionary來(lái)作為我們的緩存容器，并能保證線程安全。
public class LRUCache<TValue> : IEnumerable<KeyValuePair<string, TValue>>
{
private long ageToDiscard = 0; //淘汰的年齡起點(diǎn)
private long currentAge = 0; //當(dāng)前緩存最新年齡
private int maxSize = 0; //緩存最大容量
private readonly ConcurrentDictionary<string, TrackValue> cache;
public LRUCache(int maxKeySize)
{
cache = new ConcurrentDictionary<string, TrackValue>();
maxSize = maxKeySize;
}
}
上面定義了 ageToDiscard、currentAge 這2個(gè)自增值參數(shù)，作用是：標(biāo)記緩存列表中各個(gè)key的新舊程度。
核心實(shí)現(xiàn)步驟如下：
1：每次添加key時(shí)，currentAge自增并將currentAge值分配給這個(gè)緩存值的Age，currentAge始終增加。
public void Add(string key, TValue value)
{
Adjust(key);
var result = new TrackValue(this, value);
cache.AddOrUpdate(key, result, (k, o) => result);
}
public class TrackValue
{
public readonly TValue Value;
public long Age;
public TrackValue(LRUCache<TValue> lv, TValue tv)
{
Age = Interlocked.Increment(ref lv.currentAge);
Value = tv;
}
}
2：在添加時(shí)，如超過(guò)最大數(shù)量。檢查字典里是否有ageToDiscard年齡的key，如沒(méi)有循環(huán)自增檢查，有則刪除、添加成功。
ageToDiscard+maxSize= currentAge ，這樣設(shè)計(jì)就能在O(1)下保證可以淘汰舊數(shù)據(jù)，而不是使用鏈表移動(dòng)。
public void Adjust(string key)
{
while (cache.Count >= maxSize)
{
long ageToDelete = Interlocked.Increment(ref ageToDiscard);
var toDiscard =
cache.FirstOrDefault(p => p.Value.Age == ageToDelete);
if (toDiscard.Key == null)
continue;
TrackValue old;
cache.TryRemove(toDiscard.Key, out old);
}
}
過(guò)期刪除策略
大多數(shù)情況下，LRU算法對(duì)熱點(diǎn)數(shù)據(jù)命中率是很高的。 但如果突然大量偶發(fā)性的數(shù)據(jù)訪問(wèn)，會(huì)讓內(nèi)存中存放大量冷數(shù)據(jù)，也就是緩存污染。
會(huì)引起LRU無(wú)法命中熱點(diǎn)數(shù)據(jù)，導(dǎo)致緩存系統(tǒng)命中率急劇下降。也可以使用LRU-K、2Q、MQ等變種算法來(lái)提高命中率。
過(guò)期配置
1：我們通過(guò)設(shè)定、最大過(guò)期時(shí)間來(lái)盡量避免冷數(shù)據(jù)常駐內(nèi)存。
2：大多數(shù)情況每個(gè)緩存的時(shí)間要求不一致的，所以在增加單個(gè)key的過(guò)期時(shí)間。
private TimeSpan maxTime;
public LRUCache(int maxKeySize,TimeSpan maxExpireTime){}
//TrackValue增加創(chuàng)建時(shí)間和過(guò)期時(shí)間
public readonly DateTime CreateTime;
public readonly TimeSpan ExpireTime;
刪除策略
1：關(guān)于key過(guò)期刪除，最好使用定時(shí)刪除了。 這樣可以最快釋放被占用的內(nèi)存，但很明顯，大量的定時(shí)器對(duì)CPU吃不消的。
2：所以我們采用惰性刪除、在獲取key的時(shí)檢查是否過(guò)期，過(guò)期直接刪除。
public Tuple<TrackValue, bool> CheckExpire(string key)
{
TrackValue result;
if (cache.TryGetValue(key, out result))
{
var age = DateTime.Now.Subtract(result.CreateTime);
if (age >= maxTime || age >= result.ExpireTime)
{
TrackValue old;
cache.TryRemove(key, out old);
return Tuple.Create(default(TrackValue), false);
}
}
return Tuple.Create(result, true);
}
3：惰性刪除雖然性能最好，對(duì)于冷數(shù)據(jù)來(lái)說(shuō)，還是沒(méi)解決緩存污染問(wèn)題。 所以我們還需定期清理。
比如：開(kāi)個(gè)線程，5分鐘去遍歷檢查key一次。這個(gè)策略根據(jù)實(shí)際場(chǎng)景可配置。
public void Inspection()
{
foreach (var item in this)
{
CheckExpire(item.Key);
}
}
惰性刪除+定期刪除基本能滿足我們需求了。