注：以下的缓存淘汰算法实现，不考虑 并发 和 GC(垃圾回收) 问题
本文讨论的是 进程内缓存，是存放在内存中的，因此容量有限。当缓存容量达到某个阈值时，应该删除一条或多条数据。至于移出哪些数据？答案是移出那些 "无用" 的数据。而如何判断数据是否 "无用"，就设计到 缓存淘汰算法
常见的缓存淘汰算法有以下三种：
- FIFO（first in first ）先进先出算法
《go实现FIFO缓存淘汰算法》 - LFU（least frequently used）最少使用算法
看本文 - 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种算法
网友评论