LRU + Expired Map

目前博客的很多地方都需要有一个临时的缓存机制，比如:

Markdown 渲染部分如果内容未改变，可以重用之前渲染的结果
评论区发布部分添加一个定时过期记录，可以避免短时间内发出重复的评论
头像获取接口，可以缓存一定数量的头像，避免每次都重新获取

这里对应的应该是两种删除机制

通过 LRU 限定存储上限，如果超出上限则删除最近未被访问的内容
设置过期时间，如果超过过期时间则删除

两种机制本质上都是一个最小堆，通过比较 LRU 的计数器或是时间戳即可

最小堆

借助 Go 自带的 container/heap 可以实现一个最小堆，在这里除去常规的内容外，还需要维护每个元素的下标。有了下标后，就可以实现删除指定的元素了。

插入时间复杂度为 $O(logn)$ ，删除时间复杂度为 $O(logn)$ ，POP 时间复杂度为 $O(1)$

在使用时，只需要将时间戳或是计数器作为最小堆的排序标准即可

package lru

import (
	"container/heap"
	"math/rand"
)

type keyValue struct {
	key   string
	value int64
	pos   int
}

type keyValueHeap []*keyValue

var _ heap.Interface = (*keyValueHeap)(nil)

func newKeyValueHeap(l int) *keyValueHeap {
	e := keyValueHeap(make([]*keyValue, 0, l))
	return &e
}
func (h keyValueHeap) At(i int) int64 { return h[i].value }
func (h keyValueHeap) Len() int       { return len(h) }
func (h keyValueHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
	h[i].pos = i
	h[j].pos = j
}
func (h keyValueHeap) Less(i, j int) bool { return h[i].value < h[j].value }
func (h *keyValueHeap) Push(item interface{}) {
	*h = append(*h, item.(*keyValue))
	l := h.Len()
	(*h)[l-1].pos = l - 1
}
func (h *keyValueHeap) Pop() interface{} {
	l := h.Len()
	t := (*h)[l-1]
	(*h) = (*h)[:l-1]
	t.pos = -1
	return t
}

type Heap struct {
	heap *keyValueHeap
	m    map[string]*keyValue
}

func NewHeap() *Heap {
	return &Heap{
		heap: newKeyValueHeap(0),
		m:    make(map[string]*keyValue),
	}
}
func (h *Heap) Len() int {
	return len(h.m)
}

func (h *Heap) Push(key string, value int64) {
	if item, exists := h.m[key]; exists {
		item.value = value
		heap.Fix(h.heap, item.pos)
		return
	}

	item := &keyValue{
		key:   key,
		value: value,
	}
	h.m[key] = item
	heap.Push(h.heap, item)
}

func (h *Heap) Pop() string {
	if h.heap.Len() == 0 {
		return ""
	}
	item := heap.Pop(h.heap).(*keyValue)
	delete(h.m, item.key)
	h.gc()
	return item.key
}

func (h *Heap) Has(key string) bool {
	_, exists := h.m[key]
	return exists
}

func (h *Heap) Remove(key string) {
	item, exist := h.m[key]
	if exist {
		heap.Remove(h.heap, item.pos)
		delete(h.m, key)
	}
}

func (h *Heap) PopUntil(value int64) []string {
	keys := make([]string, 0)
	for h.Len() > 0 && h.heap.At(0) <= value {
		keys = append(keys, h.Pop())
	}
	return keys
}

func (h *Heap) gc() {
	// 10% 概率执行一次 gc
	if rand.Float64() > 0.1 {
		return
	}

	temp := h.m
	h.m = make(map[string]*keyValue)
	for k, v := range temp {
		h.m[k] = v
	}
}

LRU

由于 LRU 还需要维护一个计数器，因此需要再封装一层

实现一个可以自增的计数器就可以记录每个元素的访问顺序，数越小则在最小堆中更前，更早会被移除

package lru

import (
	"sync/atomic"
)

type LRU struct {
	heap    *Heap
	counter int64
	cap     int
}

func NewLRU(cap int) *LRU {
	return &LRU{
		counter: 0,
		heap:    NewHeap(),
		cap:     cap,
	}
}

func (l *LRU) Push(key string) string {
	id := atomic.AddInt64(&l.counter, 1)

	poped := ""
	for l.heap.Len() >= l.cap && !l.Has(key) {
		poped = l.Pop()
	}

	l.heap.Push(key, id)
	return poped
}

func (l *LRU) Pop() string {
	return l.heap.Pop()
}

func (l *LRU) Has(key string) bool {
	return l.heap.Has(key)
}

func (l *LRU) Remove(key string) {
	l.heap.Remove(key)
}

Map

将上述的内容封装入 Map 中，插入的时候检查 LRU，访问的时候检查 Expired 即可。

package lru

import (
	"math/rand"
	"time"
)

type Map struct {
	m map[string]interface{}
	e *Heap
	l *LRU
}

func NewMap() *Map {
	return &Map{
		m: make(map[string]interface{}),
		e: nil,
		l: nil,
	}
}

func (m *Map) WithLRU(cap int) *Map {
	m.l = NewLRU(cap)
	return m
}

func (m *Map) WithExpired() *Map {
	m.e = NewHeap()
	return m
}

func (m *Map) Put(key string, value interface{}) {
	if m.l != nil {
		poped := m.l.Push(key)
		if poped != "" {
			m.remove(poped)
		}
	}
	m.m[key] = value
}

func (m *Map) PutWithExpired(key string, value interface{}, duration time.Duration) {
	m.Put(key, value)
	if m.e != nil {
		m.e.Push(key, time.Now().Add(duration).Unix())
	}
}

func (m *Map) Get(key string) (value interface{}, exists bool) {
	m.removeExpired()
	value, exists = m.m[key]
	return
}

func (m *Map) Len() int {
	m.removeExpired()
	return len(m.m)
}

func (m *Map) Keys() []string {
	m.removeExpired()
	keys := make([]string, 0, len(m.m))
	for k := range m.m {
		keys = append(keys, k)
	}
	return keys
}

func (m *Map) Delete(key string) {
	m.removeExpired()
	m.remove(key)
}

func (m *Map) gc() {
	// 10% 概率执行一次 gc
	if rand.Float64() > 0.1 {
		return
	}

	temp := m.m
	m.m = make(map[string]interface{})
	for k, v := range temp {
		m.m[k] = v
	}
}

func (m *Map) remove(key string) {
	if m.l != nil {
		m.l.Remove(key)
	}
	if m.e != nil {
		m.e.Remove(key)
	}
	delete(m.m, key)
	m.gc()
}

func (m *Map) removeExpired() {
	if m.e != nil {
		now := time.Now()
		keys := m.e.PopUntil(now.Unix())
		for _, k := range keys {
			m.remove(k)
		}
	}
}

一些其他问题

根据 runtime: shrink map as elements are deleted · Issue #20135 · golang/go，这里 Map 可能不会被 gc，这就违背了 LRU 和 Expired 的意义

因此参照 Issue 中的代码，以 10% 的概率触发一次 map 的拷贝，释放掉不再需要的空间