那些年我們一起追過的緩存寫法
來源:易賢網(wǎng) 閱讀:1220 次 日期:2015-04-02 14:58:51
溫馨提示:易賢網(wǎng)小編為您整理了“那些年我們一起追過的緩存寫法”,方便廣大網(wǎng)友查閱!

假設(shè)有個(gè)項(xiàng)目有一定并發(fā)量,要用到多級(jí)緩存,如下:

在實(shí)際設(shè)計(jì)一個(gè)內(nèi)存緩存前,我們需要考慮的問題:

1:內(nèi)存與Redis的數(shù)據(jù)置換,盡可能在內(nèi)存中提高數(shù)據(jù)命中率,減少下一級(jí)的壓力。

2:內(nèi)存容量的限制,需要控制緩存數(shù)量。

3:熱點(diǎn)數(shù)據(jù)更新不同,需要可配置單個(gè)key過期時(shí)間。

4:良好的緩存過期刪除策略。

5:緩存數(shù)據(jù)結(jié)構(gòu)的復(fù)雜度盡可能的低。

關(guān)于置換及命中率:我們采用LRU算法,因?yàn)樗鼘?shí)現(xiàn)簡(jiǎn)單,緩存key命中率也很好。

LRU即是:把最近最少訪問的數(shù)據(jù)給淘汰掉,經(jīng)常被訪問到即是熱點(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)。

有沒復(fù)雜度更低的呢? 有Dictionary,復(fù)雜度為O(1),性能最好。 那如何保證緩存的優(yōu)先級(jí)提升呢?

二:O(1)LRU實(shí)現(xiàn)

我們定義個(gè)LRUCache<TValue>類,構(gòu)造參數(shù)maxKeySize 來控制緩存最大數(shù)量。

使用ConcurrentDictionary來作為我們的緩存容器,并能保證線程安全。

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í),如超過最大數(shù)量。檢查字典里是否有ageToDiscard年齡的key,如沒有循環(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);

}

}

過期刪除策略

大多數(shù)情況下,LRU算法對(duì)熱點(diǎn)數(shù)據(jù)命中率是很高的。 但如果突然大量偶發(fā)性的數(shù)據(jù)訪問,會(huì)讓內(nèi)存中存放大量冷數(shù)據(jù),也就是緩存污染。

會(huì)引起LRU無法命中熱點(diǎn)數(shù)據(jù),導(dǎo)致緩存系統(tǒng)命中率急劇下降。也可以使用LRU-K、2Q、MQ等變種算法來提高命中率。

過期配置

1:我們通過設(shè)定、最大過期時(shí)間來盡量避免冷數(shù)據(jù)常駐內(nèi)存。

2:大多數(shù)情況每個(gè)緩存的時(shí)間要求不一致的,所以在增加單個(gè)key的過期時(shí)間。

private TimeSpan maxTime;

public LRUCache(int maxKeySize,TimeSpan maxExpireTime){}

//TrackValue增加創(chuàng)建時(shí)間和過期時(shí)間

public readonly DateTime CreateTime;

public readonly TimeSpan ExpireTime;

刪除策略

1:關(guān)于key過期刪除,最好使用定時(shí)刪除了。 這樣可以最快釋放被占用的內(nèi)存,但很明顯,大量的定時(shí)器對(duì)CPU吃不消的。

2:所以我們采用惰性刪除、在獲取key的時(shí)檢查是否過期,過期直接刪除。

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ù)來說,還是沒解決緩存污染問題。 所以我們還需定期清理。

比如:開個(gè)線程,5分鐘去遍歷檢查key一次。這個(gè)策略根據(jù)實(shí)際場(chǎng)景可配置。

public void Inspection()

{

foreach (var item in this)

{

CheckExpire(item.Key);

}

}

惰性刪除+定期刪除基本能滿足我們需求了。

更多信息請(qǐng)查看IT技術(shù)專欄

更多信息請(qǐng)查看技術(shù)文章
易賢網(wǎng)手機(jī)網(wǎng)站地址:那些年我們一起追過的緩存寫法
由于各方面情況的不斷調(diào)整與變化,易賢網(wǎng)提供的所有考試信息和咨詢回復(fù)僅供參考,敬請(qǐng)考生以權(quán)威部門公布的正式信息和咨詢?yōu)闇?zhǔn)!

2025國考·省考課程試聽報(bào)名

  • 報(bào)班類型
  • 姓名
  • 手機(jī)號(hào)
  • 驗(yàn)證碼
關(guān)于我們 | 聯(lián)系我們 | 人才招聘 | 網(wǎng)站聲明 | 網(wǎng)站幫助 | 非正式的簡(jiǎn)要咨詢 | 簡(jiǎn)要咨詢須知 | 加入群交流 | 手機(jī)站點(diǎn) | 投訴建議
工業(yè)和信息化部備案號(hào):滇ICP備2023014141號(hào)-1 云南省教育廳備案號(hào):云教ICP備0901021 滇公網(wǎng)安備53010202001879號(hào) 人力資源服務(wù)許可證:(云)人服證字(2023)第0102001523號(hào)
云南網(wǎng)警備案專用圖標(biāo)
聯(lián)系電話:0871-65099533/13759567129 獲取招聘考試信息及咨詢關(guān)注公眾號(hào):hfpxwx
咨詢QQ:526150442(9:00—18:00)版權(quán)所有:易賢網(wǎng)
云南網(wǎng)警報(bào)警專用圖標(biāo)