go实现LRU cache

Jackwoo 发布于2019-08-06 13:31 / 2440人阅读

摘要：简介概述缓存资源通常比较昂贵通常数据量较大时会竟可能从较少的缓存满足尽可能多访问这里有一种假设通常最近被访问的数据那么它就有可能会被后续继续访问基于这种假设将所有的数据按访问时间进行排序并按驱逐出旧数据那么存在缓存的数据就为热点数据这样既节

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...

服务器托管专线服务 lru用c语言实现 LRU redis LRU LRU机制

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/61971.html

剥开比原看代码12：比原是如何通过/create-account-receiver创建地址的？

摘要：继续看生成地址的方法由于这个方法里传过来的是而不是对象，所以还需要再用查一遍，然后，再调用这个私有方法创建地址该方法可以分成部分在第块中主要关注的是返回值。作者：freewind 比原项目仓库： Github地址：https://github.com/Bytom/bytom Gitee地址：https://gitee.com/BytomBlockc... 在比原的dashboard中...

oneasp 2019-06-27 18:34 评论0 收藏0
一个线程安全的 lrucache 实现 --- 读 leveldb 源码

摘要：在阅读的源代码的时候，发现其中的类正是一个线程安全的实现，代码非常优雅。至此一个线程安全的类就已经全部实现，在中使用的缓存是，其实就是聚合多个实例，真正的逻辑都在类中。缓存是计算机的每一个层次中都是一个非常重要的概念，缓存的存在可以大大提高软件的运行速度。Least Recently Used(lru) cache 即最近最久未使用的缓存，多见与页面置换算法，lru 缓存算法在缓存的...

widuu 2019-08-06 13:30 评论0 收藏0
剑指offer/LeetCode146/LintCode134_LRU缓存实现

摘要：剑指缓存实现声明文章均为本人技术笔记，转载请注明出处解题思路缓存两种功能获取的对应，不存在返回版本版本设置缓存已满，删除最近最久未被使用的节点，添加新节点进缓存缓存未满，节点存在，修改节点不存在，添加新节点进缓存解题思路由于缓存插入和删除剑指offer/LeetCode146/LintCode134_LRU缓存实现声明文章均为本人技术笔记，转载请注明出处[1] https://s...

you_De 2019-08-14 18:08 评论0 收藏0
NPM酷库：lru-cache 基于内存的缓存管理

摘要：酷库，每天两分钟，了解一个流行库。而直接将数据保存在程序变量中，最经济快捷。但是这样就会带来一些其他问题，比如缓存更新缓存过期等。用于在内存中管理缓存数据，并且支持算法。可以让程序不依赖任何外部数据库实现缓存管理。 NPM酷库，每天两分钟，了解一个流行NPM库。为了优化程序性能，我们常常需要奖数据缓存起来，根据实际情况，我们可以将数据存储到磁盘、数据库、redis等。但是有时候要缓...

Yumenokanata 2019-08-06 13:29 评论0 收藏0