| 标题 | 那些年我们一起追过的缓存写法 |
| 内容 | 假设有个项目有一定并发量，要用到多级缓存，如下： 在实际设计一个内存缓存前，我们需要考虑的问题： 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的新旧程度。 核心实现步骤如下： 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); } } 惰性删除+定期删除基本能满足我们需求了。 |
| 随便看 |
|
在线学习网考试资料包含高考、自考、专升本考试、人事考试、公务员考试、大学生村官考试、特岗教师招聘考试、事业单位招聘考试、企业人才招聘、银行招聘、教师招聘、农村信用社招聘、各类资格证书考试等各类考试资料。