假設有個項目有比較高的并發(fā)量,要用到多級緩存,如下:
站在用戶的角度思考問題,與客戶深入溝通,找到科爾沁左翼網(wǎng)站設計與科爾沁左翼網(wǎng)站推廣的解決方案,憑借多年的經(jīng)驗,讓設計與互聯(lián)網(wǎng)技術結合,創(chuàng)造個性化、用戶體驗好的作品,建站類型包括:網(wǎng)站設計、做網(wǎng)站、企業(yè)官網(wǎng)、英文網(wǎng)站、手機端網(wǎng)站、網(wǎng)站推廣、域名注冊、網(wǎng)頁空間、企業(yè)郵箱。業(yè)務覆蓋科爾沁左翼地區(qū)。
在實際設計一個內(nèi)存緩存前,需要考慮的問題:
1:內(nèi)存與redis的數(shù)據(jù)置換,盡可能在內(nèi)存中提高數(shù)據(jù)命中率,減少下一級的壓力。
2:內(nèi)存容量的限制,需要控制緩存數(shù)量。
3:熱點數(shù)據(jù)更新不同,需要可配置單個key過期時間。
4:良好的緩存過期刪除策略。
5:緩存數(shù)據(jù)結構的復雜度盡可能的低。
關于置換及命中率:采用LRU算法,因為它實現(xiàn)簡單,緩存key命中率也很好。
LRU即是:把最近最少訪問的數(shù)據(jù)給淘汰掉,經(jīng)常被訪問到即是熱點數(shù)據(jù)。
關于LRU數(shù)據(jù)結構:因為key優(yōu)先級提升和key淘汰,所以需要順序結構,網(wǎng)上大多實現(xiàn)都采用的這種鏈表結構。
即新數(shù)據(jù)插入到鏈表頭部、被命中時的數(shù)據(jù)移動到頭部,添加復雜度O(1),移動和獲取復雜度O(N)。
有沒復雜度更低的呢? 有Dictionary,復雜度為O(1),性能最好。 那如何保證緩存的優(yōu)先級提升呢?
定義個LRUCache<TValue>類,構造參數(shù)maxKeySize 來控制緩存最大數(shù)量。
使用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個自增值參數(shù),作用是標記緩存列表中各個key的新舊程度。
實現(xiàn)步驟如下:
每次添加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>
在添加時,如超過最大數(shù)量,檢查字典里是否有ageToDiscard年齡的key,如沒有循環(huán)自增檢查,有則刪除、添加成功。
其ageToDiscard+maxSize=?currentAge?,這樣設計就能在O(1)下保證可以淘汰舊數(shù)據(jù),而不是使用鏈表移動。?
<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>
大多數(shù)情況下,LRU算法對熱點數(shù)據(jù)命中率是很高的。 但如果突然大量偶發(fā)性的數(shù)據(jù)訪問,會讓內(nèi)存中存放大量冷數(shù)據(jù),也即是緩存污染。
會引起LRU無法命中熱點數(shù)據(jù),導致緩存系統(tǒng)命中率急劇下降,也可以使用LRU-K、2Q、MQ等變種算法來提高命中率。
通過設定最大過期時間來盡量避免冷數(shù)據(jù)常駐內(nèi)存。
多數(shù)情況每個數(shù)據(jù)緩存的時間要求不一致的,所以需要再增加單個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增加創(chuàng)建時間和過期時間
public readonly DateTime CreateTime;
public readonly TimeSpan ExpireTime;
</pre>
關于key過期刪除,最好的方式是使用定時刪除,這樣可以最快的釋放被占用的內(nèi)存,但很明顯大量的定時器對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>
惰性刪除雖然性能最好,但對于冷數(shù)據(jù)來說還是沒解決緩存污染的問題,所以還需增加個定期清理和惰性刪除配合使用。
比如單開個線程每5分鐘去遍歷檢查key是否過期,這個時間策略是可配置的,如果緩存數(shù)量較多可分批遍歷檢查。
<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>
惰性刪除配合定期刪除基本上能滿足絕大多數(shù)要求了。
本篇參考了redis、Orleans的相關實現(xiàn)。
如果繼續(xù)完善下去就是內(nèi)存數(shù)據(jù)庫的雛形,類似redis,比如增加刪除key的通知回調(diào),支持更多的數(shù)據(jù)類型存儲。
針對于上面所涉及到的知識點我總結出了有1到5年開發(fā)經(jīng)驗的程序員在面試中涉及到的絕大部分架構面試題及答案做成了文檔和架構視頻資料免費分享給大家(包括Dubbo、Redis、Netty、zookeeper、Spring cloud、分布式、高并發(fā)等架構技術資料),希望能幫助到您面試前的復習且找到一個好的工作,也節(jié)省大家在網(wǎng)上搜索資料的時間來學習,也可以關注我一下以后會有更多干貨分享。
網(wǎng)頁名稱:淺談緩存寫法(三):內(nèi)存緩存該如何設計
網(wǎng)址分享:http://www.rwnh.cn/article32/jipssc.html
成都網(wǎng)站建設公司_創(chuàng)新互聯(lián),為您提供服務器托管、網(wǎng)站設計公司、軟件開發(fā)、品牌網(wǎng)站建設、網(wǎng)站策劃、搜索引擎優(yōu)化
聲明:本網(wǎng)站發(fā)布的內(nèi)容(圖片、視頻和文字)以用戶投稿、用戶轉載內(nèi)容為主,如果涉及侵權請盡快告知,我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場,如需處理請聯(lián)系客服。電話:028-86922220;郵箱:631063699@qq.com。內(nèi)容未經(jīng)允許不得轉載,或轉載時需注明來源: 創(chuàng)新互聯(lián)