分析設計
假設有個項目有比較高的并發量,要用到多級緩存,如下:
在實際設計一個記憶體緩存前,需要考慮的問題:
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來作為我們的緩存容器,并能保證線程安全。
<pre style="margin:0px;
padding:0px;
white-space:pre-wrap;
overflow-wrap:break-word;
font-family:"
Courier New"
!important;
font-size:12px !important;
"> public class LRUCache<TValue>:IEnumerable<KeyValuePair<string,TValue>> {
private long ageToDiscard = 0;
//淘汰的年齡起點
private long currentAge = 0;
//目前緩存最新年齡
private int maxSize = 0;
//緩存最大容量
private readonly ConcurrentDictionary<string,TrackValue> cache;
public LRUCache(int maxKeySize) {
cache = new ConcurrentDictionary<string,TrackValue>();
maxSize = maxKeySize;
}
}
</pre>
上面定義了 ageToDiscard、currentAge 這2個自增值參數,作用是标記緩存清單中各個key的新舊程度。
實作步驟如下:
每次添加key時,currentAge自增并将currentAge值配置設定給這個緩存值的age,currentAge一直自增。
<pre style="margin:0px;
padding:0px;
white-space:pre-wrap;
overflow-wrap:break-word;
font-family:"
Courier New"
!important;
font-size:12px !important;
"> 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;
}
}
</pre>
在添加時,如超過最大數量,檢查字典裡是否有ageToDiscard年齡的key,如沒有循環自增檢查,有則删除、添加成功。
其ageToDiscard+maxSize= currentAge ,這樣設計就能在O(1)下保證可以淘汰舊資料,而不是使用連結清單移動。
<pre style="margin:0px;
padding:0px;
white-space:pre-wrap;
overflow-wrap:break-word;
font-family:"
Courier New"
!important;
font-size:12px !important;
"> 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);
}
}</pre>
擷取key的時候表示它又被人通路,将最新的currentAge指派給它,增加它的年齡:
<pre style="margin:0px;
padding:0px;
white-space:pre-wrap;
overflow-wrap:break-word;
font-family:"
Courier New"
!important;
font-size:12px !important;
"> public TValue Get(string key) {
TrackValue value=null;
if (cache.TryGetValue(key,out value)) {
value.Age = Interlocked.Increment(ref currentAge);
}
return value.Value;}
</pre>
過期删除政策
大多數情況下,LRU算法對熱點資料命中率是很高的。 但如果突然大量偶發性的資料通路,會讓記憶體中存放大量冷資料,也即是緩存污染。
會引起LRU無法命中熱點資料,導緻緩存系統命中率急劇下降,也可以使用LRU-K、2Q、MQ等變種算法來提高命中率。
過期配置
通過設定最大過期時間來盡量避免冷資料常駐記憶體。
多數情況每個資料緩存的時間要求不一緻的,是以需要再增加單個key的過期時間字段。
<pre style="margin:0px;
padding:0px;
white-space:pre-wrap;
overflow-wrap:break-word;
font-family:"
Courier New"
!important;
font-size:12px !important;
"> private TimeSpan maxTime;
public LRUCache(int maxKeySize,TimeSpan maxExpireTime) {
}//TrackValue增加建立時間和過期時間
public readonly DateTime CreateTime;
public readonly TimeSpan ExpireTime;
</pre>
删除政策
關于key過期删除,最好的方式是使用定時删除,這樣可以最快的釋放被占用的記憶體,但很明顯大量的定時器對CPU來說是非常不友好的。
是以需要采用惰性删除、在擷取key的時檢查是否過期,過期直接删除。
<pre style="margin:0px;
padding:0px;
white-space:pre-wrap;
overflow-wrap:break-word;
font-family:"
Courier New"
!important;
font-size:12px !important;
">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);}
</pre>
惰性删除雖然性能最好,但對于冷資料來說還是沒解決緩存污染的問題,是以還需增加個定期清理和惰性删除配合使用。
比如單開個線程每5分鐘去周遊檢查key是否過期,這個時間政策是可配置的,如果緩存數量較多可分批周遊檢查。
<pre style="margin:0px;
padding:0px;
white-space:pre-wrap;
overflow-wrap:break-word;
font-family:"
Courier New"
!important;
font-size:12px !important;
">public void Inspection() {
foreach (var item in this) {
CheckExpire(item.Key);
}
}
</pre>
惰性删除配合定期删除基本上能滿足絕大多數要求了。
總結
本篇參考了redis、Orleans的相關實作。