分析設(shè)計(jì)

假設(shè)有個(gè)項(xiàng)目有比較高的并發(fā)量，要用到多級(jí)緩存，如下：

站在用戶的角度思考問(wèn)題，與客戶深入溝通，找到全州網(wǎng)站設(shè)計(jì)與全州網(wǎng)站推廣的解決方案，憑借多年的經(jīng)驗(yàn)，讓設(shè)計(jì)與互聯(lián)網(wǎng)技術(shù)結(jié)合，創(chuàng)造個(gè)性化、用戶體驗(yàn)好的作品，建站類(lèi)型包括：網(wǎng)站設(shè)計(jì)、網(wǎng)站制作、企業(yè)官網(wǎng)、英文網(wǎng)站、手機(jī)端網(wǎng)站、網(wǎng)站推廣、主機(jī)域名、網(wǎng)絡(luò)空間、企業(yè)郵箱。業(yè)務(wù)覆蓋全州地區(qū)。

在實(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)，網(wǎng)上大多實(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>類(lèi)，構(gòu)造參數(shù)maxKeySize 來(lái)控制緩存大數(shù)量。

使用ConcurrentDictionary來(lái)作為我們的緩存容器，并能保證線程安全。

<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;
    //淘汰的年齡起點(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;
}
}
</pre>

上面定義了?ageToDiscard、currentAge?這2個(gè)自增值參數(shù)，作用是標(biāo)記緩存列表中各個(gè)key的新舊程度。

實(shí)現(xiàn)步驟如下：

每次添加key時(shí)，currentAge自增并將currentAge值分配給這個(gè)緩存值的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í)，如超過(guò)大數(shù)量，檢查字典里是否有ageToDiscard年齡的key，如沒(méi)有循環(huán)自增檢查，有則刪除、添加成功。

其ageToDiscard+maxSize=?currentAge?，這樣設(shè)計(jì)就能在O(1)下保證可以淘汰舊數(shù)據(jù)，而不是使用鏈表移動(dòng)。?

<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的時(shí)候表示它又被人訪問(wèn)，將最新的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>

過(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ò)期配置

通過(guò)設(shè)定大過(guò)期時(shí)間來(lái)盡量避免冷數(shù)據(jù)常駐內(nèi)存。

多數(shù)情況每個(gè)數(shù)據(jù)緩存的時(shí)間要求不一致的，所以需要再增加單個(gè)key的過(guò)期時(shí)間字段。

<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)建時(shí)間和過(guò)期時(shí)間
public readonly DateTime CreateTime;
    public readonly TimeSpan ExpireTime;
    </pre>

刪除策略

關(guān)于key過(guò)期刪除，最好的方式是使用定時(shí)刪除，這樣可以最快的釋放被占用的內(nèi)存，但很明顯大量的定時(shí)器對(duì)CPU來(lái)說(shuō)是非常不友好的。

所以需要采用惰性刪除、在獲取key的時(shí)檢查是否過(guò)期，過(guò)期直接刪除。

<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>

惰性刪除雖然性能最好，但對(duì)于冷數(shù)據(jù)來(lái)說(shuō)還是沒(méi)解決緩存污染的問(wèn)題，所以還需增加個(gè)定期清理和惰性刪除配合使用。

比如單開(kāi)個(gè)線程每5分鐘去遍歷檢查key是否過(guò)期，這個(gè)時(shí)間策略是可配置的，如果緩存數(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ù)要求了。

總結(jié)

本篇參考了redis、Orleans的相關(guān)實(shí)現(xiàn)。

如果繼續(xù)完善下去就是內(nèi)存數(shù)據(jù)庫(kù)的雛形，類(lèi)似redis，比如增加刪除key的通知回調(diào)，支持更多的數(shù)據(jù)類(lèi)型存儲(chǔ)。

---

文末彩蛋

針對(duì)于上面所涉及到的知識(shí)點(diǎn)我總結(jié)出了有1到5年開(kāi)發(fā)經(jīng)驗(yàn)的程序員在面試中涉及到的絕大部分架構(gòu)面試題及答案做成了文檔和架構(gòu)視頻資料免費(fèi)分享給大家（包括Dubbo、Redis、Netty、zookeeper、Spring cloud、分布式、高并發(fā)等架構(gòu)技術(shù)資料），希望能幫助到您面試前的復(fù)習(xí)且找到一個(gè)好的工作，也節(jié)省大家在網(wǎng)上搜索資料的時(shí)間來(lái)學(xué)習(xí)，也可以關(guān)注我一下以后會(huì)有更多干貨分享。

資料獲取方式 QQ群搜索“708-701-457” 即可免費(fèi)領(lǐng)取

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)scvps.cn，海內(nèi)外云服務(wù)器15元起步，三天無(wú)理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國(guó)服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡(jiǎn)單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢(shì)，專(zhuān)為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場(chǎng)景需求。

新聞名稱(chēng)：淺談緩存寫(xiě)法（三）：內(nèi)存緩存該如何設(shè)計(jì)-創(chuàng)新互聯(lián)
文章鏈接：http://aaarwkj.com/article12/dpjegc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供ChatGPT、網(wǎng)站排名、服務(wù)器托管、手機(jī)網(wǎng)站建設(shè)、App設(shè)計(jì)、網(wǎng)站導(dǎo)航

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)