美文网首页缓存cache
go实现LRU缓存淘汰算法

go实现LRU缓存淘汰算法

作者: 哥斯拉啊啊啊哦 | 来源:发表于2020-09-10 16:14 被阅读0次
    注:以下的缓存淘汰算法实现,不考虑 并发 和 GC(垃圾回收) 问题

    本文讨论的是 进程内缓存,是存放在内存中的,因此容量有限。当缓存容量达到某个阈值时,应该删除一条或多条数据。至于移出哪些数据?答案是移出那些 "无用" 的数据。而如何判断数据是否 "无用",就设计到 缓存淘汰算法

    常见的缓存淘汰算法有以下三种:

    1. FIFO(first in first )先进先出算法
      《go实现FIFO缓存淘汰算法》
    2. LFU(least frequently used)最少使用算法
      《go实现LFU缓存淘汰算法》
    3. LRU(least recently used)最近最少使用算法
      看本文


    LRU缓存淘汰算法的实现
    如上图示,实现 lru算法 的缓存架构图:
    
    lru算法 是相对平衡的一种算法。
    核心原则是:如果数据最近被访问过,那么将来被访问的概率会更高
    如上图,用双链表来实现的话,如果某条数据被访问了,则把该条数据移动到链表尾部,
    队尾是最少使用的元素,内存超出限制时,淘汰队尾元素即可
    
    1. map 用来存储键值对。这是实现缓存最简单直接的数据结构,因为它的查找记录和增加记录时间复杂度都是 O(1)
    
    2. list.List 是go标准库提供的双链表。
    通过这个双链表存放具体的值,移动任意记录到队首的时间复杂度都是 O(1),
    在队首增加记录的时间复杂度是 O(1),删除任意一条记录的时间复杂度是 O(1)
    
    如下,fifo算法的代码实现
    // 定义cache接口
    type Cache interface {
        // 设置/添加一个缓存,如果key存在,则用新值覆盖旧值
        Set(key string, value interface{})
        // 通过key获取一个缓存值
        Get(key string) interface{}
        // 通过key删除一个缓存值
        Del(key string)
        // 删除 '最无用' 的一个缓存值
        DelOldest()
        // 获取缓存已存在的元素个数
        Len() int
        // 缓存中 元素 已经所占用内存的大小
        UseBytes() int
    }
    
    // 结构体,数组,切片,map,要求实现 Value 接口,该接口只有1个 Len 方法,返回占用内存的字节数
    type Value interface {
        Len() int
    }
    
    // 定义key,value 结构
    type entry struct {
        key   string
        value interface{}
    }
    
    // 计算出元素占用内存字节数
    func (e *entry) Len() int {
        return CalcLen(e.value)
    }
    
    // 计算value占用内存大小
    func CalcLen(value interface{}) int {
        var n int
        switch v := value.(type) {
        case Value: // 结构体,数组,切片,map,要求实现 Value 接口,该接口只有1个 Len 方法,返回占用的内存字节数,如果没有实现该接口,则panic
            n = v.Len()
        case string:
            if runtime.GOARCH == "amd64" {
                n = 16 + len(v)
            } else {
                n = 8 + len(v)
            }
        case bool, int8, uint8:
            n = 1
        case int16, uint16:
            n = 2
        case int32, uint32, float32:
            n = 4
        case int64, uint64, float64:
            n = 8
        case int, uint:
            if runtime.GOARCH == "amd64" {
                n = 8
            } else {
                n = 4
            }
        case complex64:
            n = 8
        case complex128:
            n = 16
        default:
            panic(fmt.Sprintf("%T is not implement cache.value", value))
        }
    
        return n
    }
    
    type lru struct {
        // 缓存最大容量,单位字节,这里值最大存放的 元素 的容量,key不算
        maxBytes int
    
        // 已使用的字节数,只包括value, key不算
        usedBytes int
    
        // 双链表
        ll *list.List
        // map的key是字符串,value是双链表中对应节点的指针
        cache map[string]*list.Element
    }
    
    // 创建一个新 Cache,如果 maxBytes 是0,则表示没有容量限制
    func NewLruCache(maxBytes int) Cache {
        return &fifo{
            maxBytes: maxBytes,
            ll:       list.New(),
            cache:    make(map[string]*list.Element),
        }
    }
    
    // 通过 Set 方法往 Cache 头部增加一个元素,如果已经存在,则移到头部,并更新值
    func (l *lru) Set(key string, value interface{}) {
        if element, ok := l.cache[key]; ok {
            // 移动到头部
            l.ll.MoveToFront(element)
            eVal := element.Value.(*entry)
            // 重新计算内存占用
            l.usedBytes = l.usedBytes - CalcLen(eVal.value) + CalcLen(value)
            // 更新value
            element.Value = value
        } else {
            element := &entry{
                key:   key,
                value: value,
            }
    
            e := l.ll.PushFront(element) // 头部插入一个元素并返回该元素
            l.cache[key] = e
            // 计算内存占用
            l.usedBytes += element.Len()
        }
    
        // 如果超出内存长度,则删除队首的节点. 0表示无内存限制
        for l.maxBytes > 0 && l.maxBytes < l.usedBytes {
            l.DelOldest()
        }
    }
    
    // 获取指定元素(有访问要将该元素移动到头部)
    func (l *lru) Get(key string) interface{} {
        if e, ok := l.cache[key]; ok {
            // 移动到头部
            l.ll.MoveToFront(e)
            return e.Value.(*entry).value
        }
    
        return nil
    }
    
    // 删除指定元素
    func (l *lru) Del(key string) {
        if e, ok := l.cache[key]; ok {
            l.removeElement(e)
        }
    }
    
    // 删除最 '无用' 元素,链表尾部为最无用元素
    func (l *lru) DelOldest() {
        l.removeElement(l.ll.Back())
    }
    
    // 删除元素并更新内存占用大小
    func (l *lru) removeElement(e *list.Element) {
        if e == nil {
            return
        }
    
        l.ll.Remove(e)
        en := e.Value.(*entry)
        l.usedBytes -= en.Len()
        delete(l.cache, en.key)
    }
    
    // 缓存池元素数量
    func (l *lru) Len() int {
        return l.ll.Len()
    }
    
    // 缓存池已经占用的内存大小
    func (l *lru) UseBytes() int {
        return l.usedBytes
    }
    
    测试:
    func TestLruCache(t *testing.T) {
        cache := NewLruCache(512)
    
        key := "k1"
        cache.Set(key, 1)
        fmt.Printf("cache 元素个数:%d, 占用内存 %d 字节\n\n", cache.Len(), cache.UseBytes())
    
        val := cache.Get(key)
        fmt.Println(cmp.Equal(val, 1))
        cache.DelOldest()
        fmt.Printf("cache 元素个数:%d, 占用内存 %d 字节\n\n", cache.Len(), cache.UseBytes())
    }
    ----------------------------------------------------------------------------------------------------------
    结果:
    === RUN   TestLruCache
    cache 元素个数:1, 占用内存 8 字节
    
    true
    cache 元素个数:0, 占用内存 0 字节
    
    --- PASS: TestLruCache (0.00s)
    PASS
    

    相关文章

      网友评论

        本文标题:go实现LRU缓存淘汰算法

        本文链接:https://www.haomeiwen.com/subject/uoupektx.html