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

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

一:分析设计

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

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

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

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来作为我们的缓存容器,并能保证线程安全。

1
2
3
4
5
6
7
8
9
10
11
12
publicclassLRUCache<TValue> : IEnumerable<KeyValuePair<string, TValue>>
   {
       privatelongageToDiscard =0; //淘汰的年龄起点
       privatelongcurrentAge =0;       //当前缓存最新年龄
       privateintmaxSize =0;         //缓存最大容量
       privatereadonly ConcurrentDictionary<string, TrackValue> cache;
       publicLRUCache(intmaxKeySize)
       {
           cache =newConcurrentDictionary<string, TrackValue>();
           maxSize = maxKeySize;
       }
   }

上面定义了 ageToDiscard、currentAge 这2个自增值参数,作用是:标记缓存列表中各个key的新旧程度。

核心实现步骤如下:

1:每次添加key时,currentAge自增并将currentAge值分配给这个缓存值的Age,currentAge始终增加。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
publicvoidAdd(string key, TValue value)
       {
           Adjust(key);
           var result =newTrackValue(this, value);
           cache.AddOrUpdate(key, result, (k, o) => result);
       }
       publicclassTrackValue
       {
           publicreadonly TValue Value;
           publiclongAge;
           publicTrackValue(LRUCache<TValue> lv, TValue tv)
           {
               Age = Interlocked.Increment(ref lv.currentAge);
               Value = tv;
           }
       }

2:在添加时,如超过最大数量。检查字典里是否有ageToDiscard年龄的key,如没有循环自增检查,有则删除、添加成功。

ageToDiscard+maxSize= currentAge ,这样设计就能在O(1)下保证可以淘汰旧数据,而不是使用链表移动。

1
2
3
4
5
6
7
8
9
10
11
12
13
publicvoidAdjust(string key)
        {
            while(cache.Count >= maxSize)
            {
                longageToDelete = 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的过期时间。

1
2
3
4
5
6
privateTimeSpan maxTime;
publicLRUCache(intmaxKeySize,TimeSpan maxExpireTime){}
 
 //TrackValue增加创建时间和过期时间
publicreadonly DateTime CreateTime;
publicreadonly TimeSpan ExpireTime;

删除策略

1:关于key过期删除,最好使用定时删除了。 这样可以最快释放被占用的内存,但很明显,大量的定时器对CPU吃不消的。

2:所以我们采用惰性删除、在获取key的时检查是否过期,过期直接删除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
publicTuple<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);
                    returnTuple.Create(default(TrackValue),false);
                }
            }
            returnTuple.Create(result,true);
        }

3:惰性删除虽然性能最好,对于冷数据来说,还是没解决缓存污染问题。  所以我们还需定期清理。

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

1
2
3
4
5
6
7
publicvoidInspection()
        {
            foreach (var item inthis)
            {
                CheckExpire(item.Key);
            }
        }

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

总结

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

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

原创文章,作者:stanley,如若转载,请注明出处:http://www.178linux.com/688

(0)
上一篇 2015-03-04 13:29
下一篇 2015-03-04 14:56

相关推荐

  • 马哥教育网络班20期+第6周课程练习

    请详细总结vim编辑器的使用并完成以下练习题 vim三种模式: 用法:vim [option…] FILE 编辑模式:     字符跳转:         h:向左移动一个字符     &…

    系统运维 2016-07-22
  • first

    计算机可分为硬件(CPU ,存储器 ,输入设备 ,输出设备),软件(操作系统 ) 两大部份; CPU:Central Processing Unit 中央处理器 ,内部由运算器,控制器,寄存器,缓存器组成 ; 存储器 :(RAM:Random Access Memory 随机存储器)进行数据 暂存,断电后其内信息会丢失,如内存 ;(ROM:Read Only…

    Linux干货 2016-12-05
  • bash中的变量

        对任何一门编程语言来说,最基础的部分就是变量。那什么事变量呢?变量就是把一个已知的可以变动的值,赋给一个固定名字的,用固定的名字代表这个可变动的值。在bash中也不例外,跟大多数编程语言一样,它也有一些自己的语法和规则 bash变量:     1.规则设置:变量和变量的值中间用=连接,=的两…

    Linux干货 2016-08-15
  • Linux内核编译以及自制Linux系统

    内核编译 单内核体系设计、但充分借鉴了微内核设计体系的优点,为内核引入模块化机制。   内核组成部分: kernel: 内核核心,一般为bzImage,通常在/boot目录下,名称为vmlinuz-VERSION-RELEASE; kernel object: 内核对象,一般放置于/lib/modules/VERSION-RELEASE/ [ ]:…

    2016-09-21
  • 马哥教育网络班22期+第2周课程练习

    1、Linux上文件/目录相关命令有哪些? 1)目录管理类命令:mkdir、rmdir (1)mkdir:make directorise 创建文件夹  使用格式:      mkdir [OPTION]… DIRECTORY…    &nb…

    Linux干货 2016-09-08
  • Linux的哲学思想第二篇

    Linux的哲学思想 一切皆文件 物理终端 物理终端指的是显示器等硬件终端设备,文件存在于 /dev/console 这个路径下 虚拟终端 虚拟终端指的是在linux命令行连接的终端,文件存在于 /dev/tty# [1,6] 这个路径下 串行终端 指的是使用计算机串行端口连接的终端设备,文件存在于 /dev/ttyS# 这个路径下 伪终端 指的是在Xshe…

    2018-02-26