那些年我们一起追过的缓存写法(三)

编辑：006 时间：2020-03-14

上篇介绍了多级缓存，本章详细介绍下内存缓存该如何设计。

阅读目录:

分析设计

假设有个项目有比较高的并发量，要用到多级缓存，如下：

在实际设计一个内存缓存前，需要考虑的问题：

1：内存与Redis的数据置换，尽可能在内存中提高数据命中率，减少下一级的压力。

2：内存容量的限制，需要控制缓存数量。

3：热点数据更新不同，需要可配置单个key过期时间。

4：良好的缓存过期删除策略。

5：缓存数据结构的复杂度尽可能的低。

关于置换及命中率：采用LRU算法，因为它实现简单，缓存key命中率也很好。

LRU即是：把最近最少访问的数据给淘汰掉，经常被访问到即是热点数据。

关于LRU数据结构：因为key优先级提升和key淘汰，所以需要顺序结构，网上大多实现都采用的这种链表结构。

即新数据插入到链表头部、被命中时的数据移动到头部，添加复杂度O(1)，移动和获取复杂度O(N)。

有没复杂度更低的呢？有Dictionary，复杂度为O(1)，性能最好。那如何保证缓存的优先级提升呢？

O(1)LRU实现

定义个LRUCache<TValue>类，构造参数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的新旧程度。

实现步骤如下：

每次添加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;
            }
        }

在添加时，如超过最大数量，检查字典里是否有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); }
        }

获取key的时候表示它又被人访问，将最新的currentAge赋值给它，增加它的年龄：

  public TValue Get(string key)
        {
            TrackValue value=null; if (cache.TryGetValue(key, out value))
            {
                value.Age = Interlocked.Increment(ref currentAge);
            } return value.Value;
        }

过期删除策略

大多数情况下，LRU算法对热点数据命中率是很高的。但如果突然大量偶发性的数据访问，会让内存中存放大量冷数据，也即是缓存污染。

会引起LRU无法命中热点数据，导致缓存系统命中率急剧下降，也可以使用LRU-K、2Q、MQ等变种算法来提高命中率。

过期配置

通过设定最大过期时间来尽量避免冷数据常驻内存。

多数情况每个数据缓存的时间要求不一致的，所以需要再增加单个key的过期时间字段。

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

删除策略

关于key过期删除，最好的方式是使用定时删除，这样可以最快的释放被占用的内存，但很明显大量的定时器对CPU来说是非常不友好的。

所以需要采用惰性删除、在获取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);
        }

惰性删除虽然性能最好，但对于冷数据来说还是没解决缓存污染的问题，所以还需增加个定期清理和惰性删除配合使用。

比如单开个线程每5分钟去遍历检查key是否过期，这个时间策略是可配置的，如果缓存数量较多可分批遍历检查。

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

惰性删除配合定期删除基本上能满足绝大多数要求了。

总结

本篇参考了redis、Orleans的相关实现。

如果继续完善下去就是内存数据库的雏形，类似redis，比如增加删除key的通知回调，支持更多的数据类型存储。

郑重声明：本文版权归原作者所有，转载文章仅为传播更多信息之目的，如作者信息标记有误，请第一时间联系我们修改或删除，多谢。

上一篇：那些年我们一起追过的缓存写法(二)

下一篇：关于bug分析与异常处理的一些思考

回复列表