Redis 常用的缓存淘汰策略

LRU（Least Recently Used，最近最少使用）

Redis原生支持，通过设置maxmemory-policy为allkeys-lru或volatile-lru。

package main

import (
 "container/list"
 "fmt"
)

// LRUCache 实现了最近最少使用缓存策略
type LRUCache struct {
 capacity int                      // 缓存容量
 cache    map[string]*list.Element // 哈希表存储键到链表节点的映射
 list     *list.List               // 双向链表按访问顺序存储元素
}

// entry 表示缓存中的键值对
type entry struct {
 key   string
 value interface{}
}

// NewLRUCache 创建指定容量的LRU缓存
func NewLRUCache(capacity int) *LRUCache {
 return &LRUCache{
  capacity: capacity,
  cache:    make(map[string]*list.Element),
  list:     list.New(),
 }
}

// Get 获取键对应的值，同时将该键移到最近使用位置
// 返回值和是否命中缓存
func (c *LRUCache) Get(key string) (interface{}, bool) {
 if element, found := c.cache[key]; found {
  // 将访问的元素移动到链表头部，表示最近使用
  c.list.MoveToFront(element)
  return element.Value.(*entry).value, true
 }
 return nil, false // 缓存未命中
}

// Put 向缓存添加或更新键值对
func (c *LRUCache) Put(key string, value interface{}) {
 // 如果键已存在，更新值并移到最近使用位置
 if element, found := c.cache[key]; found {
  c.list.MoveToFront(element)
  element.Value.(*entry).value = value
  return
 }

 // 如果缓存已满，删除最久未使用的元素（链表尾部）
 if c.list.Len() >= c.capacity {
  oldest := c.list.Back()
  if oldest != nil {
   delete(c.cache, oldest.Value.(*entry).key)
   c.list.Remove(oldest)
  }
 }

 // 添加新元素到链表头部
 element := c.list.PushFront(&entry{key, value})
 c.cache[key] = element
}

LFU（Least Frequently Used，最不经常使用）

Redis 4.0+原生支持，设置maxmemory-policy为allkeys-lfu或volatile-lfu。

package main

import (
 "container/heap"
 "fmt"
)

// freqEntry 表示带有访问频率的缓存项
type freqEntry struct {
 key      string      // 键
 value    interface{} // 值
 freq     int         // 访问频率
 heapIdx  int         // 在堆中的索引位置
}

// freqHeap 实现一个最小堆，按频率排序
type freqHeap []*freqEntry

// 实现heap.Interface需要的方法
func (h freqHeap) Len() int { return len(h) }
func (h freqHeap) Less(i, j int) bool { return h[i].freq < h[j].freq } // 按频率升序
func (h freqHeap) Swap(i, j int) {
 h[i], h[j] = h[j], h[i]
 h[i].heapIdx = i // 更新索引位置
 h[j].heapIdx = j
}
func (h *freqHeap) Push(x interface{}) { *h = append(*h, x.(*freqEntry)) }
func (h *freqHeap) Pop() interface{} {
 old := *h
 n := len(old)
 x := old[n-1]
 *h = old[0 : n-1]
 return x
}

// LFUCache 实现了最不经常使用缓存策略
type LFUCache struct {
 capacity int                  // 缓存容量
 cache    map[string]*freqEntry // 哈希表存储键到缓存项的映射
 heap     freqHeap              // 最小堆维护频率顺序
}

// NewLFUCache 创建指定容量的LFU缓存
func NewLFUCache(capacity int) *LFUCache {
 return &LFUCache{
  capacity: capacity,
  cache:    make(map[string]*freqEntry),
  heap:     make(freqHeap, 0),
 }
}

// Get 获取键对应的值，同时增加访问频率
// 返回值和是否命中缓存
func (c *LFUCache) Get(key string) (interface{}, bool) {
 if entry, found := c.cache[key]; found {
  entry.freq++ // 增加访问频率
  heap.Fix(&c.heap, entry.heapIdx) // 调整堆以维持正确顺序
  return entry.value, true
 }
 return nil, false // 缓存未命中
}

// Put 向缓存添加或更新键值对
func (c *LFUCache) Put(key string, value interface{}) {
 // 如果键已存在，更新值并增加频率
 if entry, found := c.cache[key]; found {
  entry.value = value
  entry.freq++
  heap.Fix(&c.heap, entry.heapIdx) // 调整堆位置
  return
 }

 // 如果缓存已满，删除访问频率最低的元素
 if len(c.cache) >= c.capacity {
  evicted := heap.Pop(&c.heap).(*freqEntry)
  delete(c.cache, evicted.key)
 }

 // 添加新元素，初始频率为1
 entry := &freqEntry{key: key, value: value, freq: 1}
 c.cache[key] = entry
 heap.Push(&c.heap, entry)
 entry.heapIdx = len(c.heap) - 1 // 更新堆索引
}