程式設計技術快取寫法(三)

上次我們說了多層緩存，本章詳細介紹下記憶體緩存該如何設計。

一：分析設計

假設有個項目有一定並發量，要用到多級緩存，如下：

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

1：內存與Redis的資料置換，盡可能在記憶體中提高資料命中率，減少下一級的壓力。

2：記憶體容量的限制，需要控制快取數量。

3：熱點資料更新不同，需要可設定單一key過期時間。

4：良好的快取過期刪除策略。

5：快取資料結構的複雜度盡可能的低。

關於置換及命中率：我們採用LRU演算法，因為它實作簡單，快取key命中率也很好。

LRU即是：把最近最少存取的資料給淘汰掉，經常被存取到即是熱點資料。

關於LRU資料結構：因為key優先權提升和key淘汰，所以需要順序結構。我看到大多實現，都採用鍊錶結構、

即：新資料插入到鍊錶頭部、被命中時的資料移動到頭部。 加入複雜度O(1) 移動和取得複雜度O(N)。

有沒複雜度更低的呢？ 有Dictionary，複雜度為O(1)，效能最好。 那如何保證快取的優先權提升呢？

二：O(1)LRU實作

我們定義個LRUCache類，建構參數maxKeySize 來控制快取最大數量。

使用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個自加值參數，作用是：標記快取清單中各個key的新舊程度。

核心實作步驟如下：

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：在添加時，如超過最大數量。檢查字典裡是否有ageToDiscard年齡的key，如沒有循環自增檢查，有則刪除、添加成功。

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

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);
            }
        }

過期刪除策略

大多數情況下，LRU演算法對熱點資料命中率是很高的。 但如果突然大量的偶發性數據訪問，會讓記憶體存放大量冷數據，也就是快取污染。

會造成LRU無法命中熱點數據，導致快取系統命中率急遽下降。也可以使用LRU-K、2Q、MQ等變種演算法來提高命中率。

過期配置

1：我們透過設定、最大過期時間來盡量避免冷資料常駐記憶體。

2：大多數情況每個快取的時間要求不一致的，所以在增加單一key的過期時間。

private TimeSpan maxTime;
public LRUCache(int maxKeySize,TimeSpan maxExpireTime){}
 
 //TrackValue增加创建时间和过期时间
public readonly DateTime CreateTime;
public readonly TimeSpan ExpireTime;

刪除策略

1：關於key過期刪除，最好使用定時刪除了。 這樣可以最快釋放被佔用的內存，但很明顯，大量的定時器對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：惰性删除虽然性能最好，对于冷数据来说，还是没解决缓存污染问题。 所以我们还需定期清理。

比如：开个线程，5分钟去遍历检查key一次。这个策略根据实际场景可配置。

public void Inspection()
        {
            foreach (var item in this)
            {
                CheckExpire(item.Key);
            }
        }

惰性删除+定期删除基本能满足我们需求了。

总结

如果继续完善下去，就是内存数据库的雏形，类似redis。

比如：增加删除key的通知，增加更多数据类型。 本篇也是参考了redis、Orleans的实现。