上次我們說了多級緩存，本章詳細介紹下內存緩存該如何設計。
一：分析設計
假設有個項目有一定并發量，要用到多級緩存，如下：
在實際設計一個內存緩存前，我們需要考慮的問題：
1：內存與Redis的數據置換，盡可能在內存中提高數據命中率，減少下一級的壓力。
2：內存容量的限制，需要控制緩存數量。
3：熱點數據更新不同，需要可配置單個key過期時間。
4：良好的緩存過期刪除策略。
5：緩存數據結構的復雜度盡可能的低。
關于置換及命中率：我們采用LRU算法，因為它實現簡單，緩存key命中率也很好。
LRU即是：把最近最少訪問的數據給淘汰掉，經常被訪問到即是熱點數據。
關于LRU數據結構：因為key優先級提升和key淘汰，所以需要順序結構。我看到大多實現，都采用鏈表結構、
即：新數據插入到鏈表頭部、被命中時的數據移動到頭部。 添加復雜度O(1) 移動和獲取復雜度O(N)。
有沒復雜度更低的呢？ 有Dictionary，復雜度為O(1)，性能最好。 那如何保證緩存的優先級提升呢？
二：O(1)LRU實現
我們定義個LRUCache<TValue>類，構造參數maxKeySize 來控制緩存最大數量。
使用ConcurrentDictionary來作為我們的緩存容器，并能保證線程安全。
|
1
2
3
4
5
6
7
8
9
10
11
12
|
publicclassLRUCache<TValue> : IEnumerable<KeyValuePair<string, TValue>>
{
privatelongageToDiscard =0; //淘汰的年齡起點
privatelongcurrentAge =0; //當前緩存最新年齡
privateintmaxSize =0; //緩存最大容量
privatereadonly ConcurrentDictionary<string, TrackValue> cache;
publicLRUCache(intmaxKeySize)
{
cache =newConcurrentDictionary<string, TrackValue>();
maxSize = maxKeySize;
}
}
|
上面定義了 ageToDiscard、currentAge 這2個自增值參數，作用是：標記緩存列表中各個key的新舊程度。
核心實現步驟如下：
1：每次添加key時，currentAge自增并將currentAge值分配給這個緩存值的Age，currentAge始終增加。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
publicvoidAdd(string key, TValue value)
{
Adjust(key);
var result =newTrackValue(this, value);
cache.AddOrUpdate(key, result, (k, o) => result);
}
publicclassTrackValue
{
publicreadonly TValue Value;
publiclongAge;
publicTrackValue(LRUCache<TValue> lv, TValue tv)
{
Age = Interlocked.Increment(ref lv.currentAge);
Value = tv;
}
}
|
2：在添加時，如超過最大數量。檢查字典里是否有ageToDiscard年齡的key，如沒有循環自增檢查，有則刪除、添加成功。
ageToDiscard+maxSize= currentAge ，這樣設計就能在O(1)下保證可以淘汰舊數據，而不是使用鏈表移動。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
publicvoidAdjust(string key)
{
while(cache.Count >= maxSize)
{
longageToDelete = 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);
}
}
|
過期刪除策略
大多數情況下，LRU算法對熱點數據命中率是很高的。 但如果突然大量偶發性的數據訪問，會讓內存中存放大量冷數據，也就是緩存污染。
會引起LRU無法命中熱點數據，導致緩存系統命中率急劇下降。也可以使用LRU-K、2Q、MQ等變種算法來提高命中率。
過期配置
1：我們通過設定、最大過期時間來盡量避免冷數據常駐內存。
2：大多數情況每個緩存的時間要求不一致的，所以在增加單個key的過期時間。
|
1
2
3
4
5
6
|
privateTimeSpan maxTime;
publicLRUCache(intmaxKeySize,TimeSpan maxExpireTime){}
//TrackValue增加創建時間和過期時間
publicreadonly DateTime CreateTime;
publicreadonly TimeSpan ExpireTime;
|
刪除策略
1：關于key過期刪除，最好使用定時刪除了。 這樣可以最快釋放被占用的內存，但很明顯，大量的定時器對CPU吃不消的。
2：所以我們采用惰性刪除、在獲取key的時檢查是否過期，過期直接刪除。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
publicTuple<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);
returnTuple.Create(default(TrackValue),false);
}
}
returnTuple.Create(result,true);
}
|
3：惰性刪除雖然性能最好，對于冷數據來說，還是沒解決緩存污染問題。 所以我們還需定期清理。
比如：開個線程，5分鐘去遍歷檢查key一次。這個策略根據實際場景可配置。
|
1
2
3
4
5
6
7
|
publicvoidInspection()
{
foreach (var item inthis)
{
CheckExpire(item.Key);
}
}
|
惰性刪除+定期刪除基本能滿足我們需求了。
總結
如果繼續完善下去，就是內存數據庫的雛形，類似redis。
比如：增加刪除key的通知，增加更多數據類型。 本篇也是參考了redis、Orleans的實現。
原創文章，作者：stanley，如若轉載，請注明出處：http://www.www58058.com/688
