MyException - 我的异常网
当前位置:我的异常网» 数据结构与算法 » 那些年小弟我们一起追过的缓存写法(三)

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

www.MyException.Cn  网友分享于:2015-02-08  浏览:0次
那些年我们一起追过的缓存写法(三)

目录

一:分析设计

二:O(1)LRU实现

三:过期删除策略

四: 总结

一:分析设计

假设有个项目有一定并发量,要用到多级缓存,如下:

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

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个参数,它是新旧数据的年龄标记

核心实现步骤如下:

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的实现。

系列目录:

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

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

文章评论

Web开发人员为什么越来越懒了?
Web开发人员为什么越来越懒了?
老程序员的下场
老程序员的下场
不懂技术不要对懂技术的人说这很容易实现
不懂技术不要对懂技术的人说这很容易实现
程序员都该阅读的书
程序员都该阅读的书
亲爱的项目经理,我恨你
亲爱的项目经理,我恨你
那些争议最大的编程观点
那些争议最大的编程观点
代码女神横空出世
代码女神横空出世
聊聊HTTPS和SSL/TLS协议
聊聊HTTPS和SSL/TLS协议
我跳槽是因为他们的显示器更大
我跳槽是因为他们的显示器更大
十大编程算法助程序员走上高手之路
十大编程算法助程序员走上高手之路
我是如何打败拖延症的
我是如何打败拖延症的
程序猿的崛起——Growth Hacker
程序猿的崛起——Growth Hacker
旅行,写作,编程
旅行,写作,编程
每天工作4小时的程序员
每天工作4小时的程序员
团队中“技术大拿”并非越多越好
团队中“技术大拿”并非越多越好
 程序员的样子
程序员的样子
做程序猿的老婆应该注意的一些事情
做程序猿的老婆应该注意的一些事情
程序员和编码员之间的区别
程序员和编码员之间的区别
初级 vs 高级开发者 哪个性价比更高?
初级 vs 高级开发者 哪个性价比更高?
老美怎么看待阿里赴美上市
老美怎么看待阿里赴美上市
要嫁就嫁程序猿—钱多话少死的早
要嫁就嫁程序猿—钱多话少死的早
程序员最害怕的5件事 你中招了吗?
程序员最害怕的5件事 你中招了吗?
程序员必看的十大电影
程序员必看的十大电影
写给自己也写给你 自己到底该何去何从
写给自己也写给你 自己到底该何去何从
程序员眼里IE浏览器是什么样的
程序员眼里IE浏览器是什么样的
Google伦敦新总部 犹如星级庄园
Google伦敦新总部 犹如星级庄园
Web开发者需具备的8个好习惯
Web开发者需具备的8个好习惯
Java程序员必看电影
Java程序员必看电影
“肮脏的”IT工作排行榜
“肮脏的”IT工作排行榜
中美印日四国程序员比较
中美印日四国程序员比较
2013年美国开发者薪资调查报告
2013年美国开发者薪资调查报告
我的丈夫是个程序员
我的丈夫是个程序员
程序员的一天:一寸光阴一寸金
程序员的一天:一寸光阴一寸金
5款最佳正则表达式编辑调试器
5款最佳正则表达式编辑调试器
什么才是优秀的用户界面设计
什么才是优秀的用户界面设计
如何成为一名黑客
如何成为一名黑客
漫画:程序员的工作
漫画:程序员的工作
60个开发者不容错过的免费资源库
60个开发者不容错过的免费资源库
一个程序员的时间管理
一个程序员的时间管理
为啥Android手机总会越用越慢?
为啥Android手机总会越用越慢?
程序员应该关注的一些事儿
程序员应该关注的一些事儿
程序员的鄙视链
程序员的鄙视链
看13位CEO、创始人和高管如何提高工作效率
看13位CEO、创始人和高管如何提高工作效率
2013年中国软件开发者薪资调查报告
2013年中国软件开发者薪资调查报告
Java 与 .NET 的平台发展之争
Java 与 .NET 的平台发展之争
10个帮程序员减压放松的网站
10个帮程序员减压放松的网站
鲜为人知的编程真相
鲜为人知的编程真相
10个调试和排错的小建议
10个调试和排错的小建议
科技史上最臭名昭著的13大罪犯
科技史上最臭名昭著的13大罪犯
软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有