go实现LFU缓存淘汰算法

注：以下的缓存淘汰算法实现，不考虑 并发 和 GC(垃圾回收) 问题

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

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

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

LFU（最少使用）算法会淘汰缓存中访问次数最少的数据。
其核心原则是，如果数据过去被访问多次，那么将来被访问的频率也会更高。
在 LFU 实现中，需要维护一个按照访问次数排序的队列，每次访问时，次数加1,队伍重新排序，淘汰时选择访问次数最少的即可

结构图如下所示：

ps：想详细了解堆数据结构的可以看《二叉堆》

如上图示
'queue'是一个二叉堆实现的队列
'weight'为访问次数

相对FIFO算法，LFU 使用了 堆queue，而不是 双链表。
二叉堆 插入记录，更新记录，删除记录，时间复杂度都是 'O(logN)'
map 用来存储键值对，每次访问键值时，都必须更新weight，因此获取记录时间复杂度也是 'O(logN)'
如下，LFU算法 的代码实现如下
// 最小堆实现的队列
type queue []*entry

// 队列长度
func (q queue) Len() int {
    return len(q)
}

// '<' 是最小堆，'>' 是最大堆
func (q queue) Less(i, j int) bool {
    return q[i].weight < q[j].weight
}

// 交换元素
func (q queue) Swap(i, j int) {
    // 交换元素
    q[i], q[j] = q[j], q[i]
    // 索引不用交换
    q[i].index = i
    q[j].index = j
}

// append ，*q = oldQue[:n-1] 会导致频繁的内存拷贝
// 实际上，如果使用 LFU算法，处于性能考虑，可以将最大内存限制修改为最大记录数限制
// 这样提前分配好 queue 的容量，再使用交换索引和限制索引的方式来实现 Pop 方法，可以免去频繁的内存拷贝，极大提高性能
func (q *queue) Push(v interface{}) {
    n := q.Len()
    en := v.(*entry)
    en.index = n
    *q = append(*q, en) // 这里会重新分配内存，并拷贝数据
}

func (q *queue) Pop() interface{} {
    oldQue := *q
    n := len(oldQue)
    en := oldQue[n-1]
    oldQue[n-1] = nil // 将不再使用的对象置为nil，加快垃圾回收，避免内存泄漏
    *q = oldQue[:n-1] // 这里会重新分配内存，并拷贝数据
    return en
}

// weight更新后，要重新排序，时间复杂度为 O(logN)
func (q *queue) update(en *entry, val interface{}, weight int) {
    en.value = val
    en.weight = weight
    (*q)[en.index] = en
    // 重新排序
    // 分析思路是把 堆(大D) 的树状图画出来，看成一个一个小的堆(小D)，看改变其中一个值，对 大D 有什么影响
    // 可以得出结论，下沉操作和上沉操作分别执行一次能将 queue 排列为堆
    heap.Fix(q, en.index)
}

// 定义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
}

// 定义元素
type entry struct {
    key    string
    value  interface{}
    weight int // 访问次数
    index  int // queue索引
}

// 计算出元素占用内存字节数
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
}

// 定义lfu cache 结构体
type lfu struct {
    // 缓存最大容量，单位字节，这里值最大存放的 元素 的容量，key不算
    maxBytes int

    // 已使用的字节数，只包括value， key不算
    usedBytes int

    // 最小堆实现的队列
    queue *queue
    // map的key是字符串，value是entry
    cache map[string]*entry
}

// 创建一个新 Cache，如果 maxBytes 是0，则表示没有容量限制
func NewLfuCache(maxBytes int) Cache {
    queue := make(queue, 0)
    return &lfu{
        maxBytes: maxBytes,
        queue:    &queue,
        cache:    make(map[string]*entry),
    }
}

// 通过 Set 方法往 Cache 头部增加一个元素，如果存在则更新值
func (l *lfu) Set(key string, value interface{}) {
    if en, ok := l.cache[key]; ok {
        l.usedBytes = l.usedBytes - en.Len() + CalcLen(value) // 更新占用内存长度
        l.queue.update(en, value, en.weight+1)
    } else {
        en := &entry{
            key:   key,
            value: value,
        }

        heap.Push(l.queue, en)  // 插入queue 并重新排序为堆
        l.cache[key] = en       // 插入 map
        l.usedBytes += en.Len() // 更新内存占用

        // 如果超出内存长度，则删除最 '无用' 的元素，0表示无内存限制
        for l.maxBytes > 0 && l.usedBytes >= l.maxBytes {
            l.DelOldest()
        }
    }
}

// 获取指定元素,访问次数加1
func (l *lfu) Get(key string) interface{} {
    if en, ok := l.cache[key]; ok {
        l.queue.update(en, en.value, en.weight+1)
        return en.value
    }
    return nil
}

// 删除指定元素（删除queue和map中的val）
func (l *lfu) Del(key string) {
    if en, ok := l.cache[key]; ok {
        heap.Remove(l.queue, en.index)
        l.removeElement(en)
    }
}

// 删除最 '无用' 元素（删除queue和map中的val）
func (l *lfu) DelOldest() {
    if l.Len() == 0 {
        return
    }
    val := heap.Pop(l.queue)
    l.removeElement(val)
}

// 删除元素并更新内存占用大小
func (l *lfu) removeElement(v interface{}) {
    if v == nil {
        return
    }

    en := v.(*entry)

    delete(l.cache, en.key)
    l.usedBytes -= en.Len()
}

// 缓存池元素个数
func (l *lfu) Len() int {
    return l.queue.Len()
}

// 缓存池占用内存大小
func (l *lfu) UseBytes() int {
    return l.usedBytes
}


测试：
func TestLfuCache(t *testing.T) {
    cache := NewLfuCache(512)

    for i := 0; i < 10; i++ {
        key := fmt.Sprintf("key-%d", i)
        cache.Set(key, i)
    }
    fmt.Printf("cache 元素个数：%d, 占用内存 %d 字节, key-9 = %v\n\n", cache.Len(), cache.UseBytes(), cache.Get("key-9"))
    for i := 0; i < 3; i++ {
        key := fmt.Sprintf("key-%d", i)
        cache.Set(key, i)
    }
    fmt.Printf("cache 元素个数：%d, 占用内存 %d 字节, key-3 = %v\n\n", cache.Len(), cache.UseBytes(), cache.Get("key-3"))
    cache.Del("key-3")
    fmt.Printf("cache 元素个数：%d, 占用内存 %d 字节, key-3 = %v\n\n", cache.Len(), cache.UseBytes(), cache.Get("key-3"))
    cache.DelOldest()
    fmt.Printf("cache 元素个数：%d, 占用内存 %d 字节, key-9 = %v\n\n", cache.Len(), cache.UseBytes(), cache.Get("key-9"))
}
----------------------------------------------------------------------------------------------------------
结果：
=== RUN   TestLfuCache
cache 元素个数：10, 占用内存 80 字节, key-9 = 9

cache 元素个数：10, 占用内存 80 字节, key-3 = 3

cache 元素个数：9, 占用内存 72 字节, key-3 = <nil>

cache 元素个数：8, 占用内存 64 字节, key-9 = 9

--- PASS: TestLfuCache (0.00s)

代码下载地址：go实现本地缓存的3种算法

最后编辑于 ：
?著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 214,029评论 6赞 493
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 91,238评论 3赞 388
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事?！?“怎么了？”我有些...
    开封第一讲书人阅读 159,576评论 0赞 349
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 57,214评论 1赞 287
  • ?港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 66,324评论 6赞 386
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 50,392评论 1赞 292
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 39,416评论 3赞 412
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 38,196评论 0赞 269
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 44,631评论 1赞 306
  • ?护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,919评论 2赞 328
  • ?白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,090评论 1赞 342
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 34,767评论 4赞 337
  • ?日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 40,410评论 3赞 322
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,090评论 0赞 21
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,328评论 1赞 267
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 46,952评论 2赞 365
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 43,979评论 2赞 351