1. LRU简介
1.1 概述
缓存资源通常比较昂贵,通常数据量较大时,会竟可能从较少的缓存满足尽可能多访问,这里有一种假设,通常最近被访问的数据,那么它就有可能会被后续继续访问,基于这种假设,将所有的数据按访问时间进行排序,并按驱逐出旧数据,那么存在缓存的数据就为热点数据,这样既节省了内存资源,又极大的满足了访问.LRU(Least recently used)算法就是基于这种假设的一直缓存置换算法.
1.2 算法流程
假设缓存大小为4,而写入顺序为A B C D E D F.访问顺序分为写入以及读取两种操作,写入需要更新访问时间,并且当数据到达最大缓存时需要逐出数据,而读取只会更新访问时间,写入置换算法流程如上图所示.
当未到达缓存大小时,所有数据按写入存储,并记录写入次序.
写入E时缓存已经满,且E的值不存在,需要逐出最久未访问的数据A,此时缓存内容为E D C B.
下一个写入D, D在缓存中,直接更新D的访问次序,此时缓存内容为 D E C B
下一个写入F, F不在缓存中,逐出缓存中的末尾C,此时缓存内容为 F D E C
2 go实现
2.1思路
采用go,可以使用list加map实现LRU cache,具体思路为:
写入时,先从map中查询,如果能查询,如果能查询到值,则将该值的在List中移动到最前面.如果查询不到值,则判断当前map是否到达最大值,如果到达最大值则移除List最后面的值,同时删除map中的值,如果map容量未达最大值,则写入map,同时将值放在List最前面.
读取时,从map中查询,如果能查询到值,则直接将List中该值移动到最前面,返回查询结果.
为保证并发安全,需要引入读写锁.
另外,存在读取List中内容反差map的情况,因为声明一个容器对象同时保存key以及value, List中以及map中存储的都是容器对象的引用.
引入原子对象对命中数以及未命中数等指标进行统计
2.2 关键代码
完整代码见: https://github.com/g4zhuj/cache
- Set(写入操作)
func (c *MemCache) Set(key string, value interface{}) {
c.mutex.Lock()
defer c.mutex.Unlock()
if c.cache == nil {
c.cache = make(map[interface{}]*list.Element)
c.cacheList = list.New()
}
//判断是否在map中,如果在map中,则将value从list中移动到前面.
if ele, ok := c.cache[key]; ok {
c.cacheList.MoveToFront(ele)
ele.Value.(*entry).value = value
return
}
//如果不再map中,将值存到List最前面
ele := c.cacheList.PushFront(&entry{key: key, value: value})
c.cache[key] = ele
//判断是否到达容量限制,到达容量限制时删除List中最后面的值.
if c.maxItemSize != 0 && c.cacheList.Len() > c.maxItemSize {
c.RemoveOldest()
}
}
- Get(读取操作)
func (c *MemCache) Get(key string) (interface{}, bool) {
c.mutex.RLock()
defer c.mutex.RUnlock()
c.gets.Add(1)
//如果读取到值,移动在List中位置,并返回value
if ele, hit := c.cache[key]; hit {
c.hits.Add(1)
c.cacheList.MoveToFront(ele)
return ele.Value.(*entry).value, true
}
return nil, false
}3. 参考
https://en.wikipedia.org/wiki...
有疑问加站长微信联系（非本文作者）
