假設有個項目有一定并發(fā)量，要用到多級緩存，如下：

在實際設計一個內(nèi)存緩存前，我們需要考慮的問題：

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

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

3：熱點數(shù)據(jù)更新不同，需要可配置單個key過期時間。

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

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

關(guān)于置換及命中率：我們采用LRU算法，因為它實現(xiàn)簡單，緩存key命中率也很好。

LRU即是：把最近最少訪問的數(shù)據(jù)給淘汰掉，經(jīng)常被訪問到即是熱點數(shù)據(jù)。

關(guān)于LRU數(shù)據(jù)結(jié)構(gòu)：因為key優(yōu)先級提升和key淘汰，所以需要順序結(jié)構(gòu)。我看到大多實現(xiàn)，都采用鏈表結(jié)構(gòu)、

即：新數(shù)據(jù)插入到鏈表頭部、被命中時的數(shù)據(jù)移動到頭部。 添加復雜度O(1) 移動和獲取復雜度O(N)。

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

二：O(1)LRU實現(xiàn)

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

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

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;

}

}

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

核心實現(xiàn)步驟如下：

1：每次添加key時，currentAge自增并將currentAge值分配給這個緩存值的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ù)量。檢查字典里是否有ageToDiscard年齡的key，如沒有循環(huán)自增檢查，有則刪除、添加成功。

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

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算法對熱點數(shù)據(jù)命中率是很高的。 但如果突然大量偶發(fā)性的數(shù)據(jù)訪問，會讓內(nèi)存中存放大量冷數(shù)據(jù)，也就是緩存污染。

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

過期配置

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

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

private TimeSpan maxTime;

public LRUCache(int maxKeySize,TimeSpan maxExpireTime){}

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

public readonly DateTime CreateTime;

public readonly TimeSpan ExpireTime;

刪除策略

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

2：所以我們采用惰性刪除、在獲取key的時檢查是否過期，過期直接刪除。

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：惰性刪除雖然性能最好，對于冷數(shù)據(jù)來說，還是沒解決緩存污染問題。 所以我們還需定期清理。

比如：開個線程，5分鐘去遍歷檢查key一次。這個策略根據(jù)實際場景可配置。

public void Inspection()

{

foreach (var item in this)

{

CheckExpire(item.Key);

}

}

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

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