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

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

阅读目录:

  1. 分析设计
  2. O(1)LRU实现
  3. 过期删除策略
  4. 总结

分析设计

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

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

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的通知回调,支持更多的数据类型存储。

系列目录:

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

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

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

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏技术博客

设计模式之四(抽象工厂模式第一回合)

首先关于抽象工厂模式的学习,我们需要慢慢的,由浅入深的进入。不能单刀直入,否则可能达不到预期学明白的目标。

11910
来自专栏orientlu

FreeRTOS 软定时器实现

考虑平台硬件定时器个数限制的, FreeRTOS 通过一个 Daemon 任务(启动调度器时自动创建)管理软定时器, 满足用户定时需求. Daemon 任务会在...

25620
来自专栏Python攻城狮

十一假期即将结束 不如复习下Python基础

博客地址:https://ask.hellobi.com/blog/zhiji 欢迎大家来交流学习。

9210
来自专栏大内老A

通过扩展改善ASP.NET MVC的验证机制[使用篇]

ASP.NET MVC提供一种基于元数据的验证方式是我们可以将相应的验证特性应用到作为Model实体的类型或者属性/字段上,但是这依然具有很多的不足。在这篇文章...

20150
来自专栏蓝天

Linux系统面面观 PROC文件系统详细介绍

什么是proc文件系统? proc文件系统是一个伪文件系统,它只存在内存当中,而不占用外存空间。它以文件系统的方式为访问系统内核数据的操作提供接口。用户和应用...

14220
来自专栏别先生

基于jsp+servlet图书管理系统之后台用户信息插入操作

前奏:   刚开始接触博客园写博客,就是写写平时学的基础知识,慢慢发现大神写的博客思路很清晰,知识很丰富,非常又价值,反思自己写的,顿时感觉非常low,有相当长...

43460
来自专栏码洞

Java高阶必备之Netty基础原理

Netty是Java程序员通向高阶之路必须要过的门槛之一。干了几年的Java程序员发现业务开发似乎就是在SSH的世界里摸滚打爬的时候,会开始感到迷茫,难道程序员...

11520
来自专栏博客园

.NET面试题解析(07)-多线程编程与线程同步

转自:http://www.cnblogs.com/anding/p/5301754.html

15740
来自专栏一个会写诗的程序员的博客

CAS指令与MESI缓存一致性协议、 “轻量级锁” 与原子操作CAS指令与MESI缓存一致性协议、 “轻量级锁” 与原子操作

CAS指令,在Intel CPU上称为CMPXCHG。最常见的原子操作有Compare and Exchange,Self Increase/Decrease等...

27950
来自专栏更流畅、简洁的软件开发方式

【实体类变形】—— 元数据(另类ORM) 描述字段的数据

     放假了,不知道有没有加班的,先祝大家国庆节快乐!      上次说得有点乱,“行列转换”这个词可能误导了大家,那么把这个词扔掉吧。我们重新开始。假设我...

230100

扫码关注云+社区

领取腾讯云代金券