使用 Go 语言实现一个简单的 LRU Cache

引言

LRU (Least-Recently-Used) Cache 是经常使用的一种内存缓存，可以将一些热点数据存放在其中，进而提高接口的响应速度。在实际应用中，cache miss 后，实际可能会回源到 Redis 集群获取缓存数据，如果 Redis 集群也没有，才会回源数据库。也就是引入 LRU Cache 后相当于给应用层添加了一级高速缓存。当然，更为实际一点的是，我们需要使用的是带有过期时间的 LRU Cache，否则后台更新了课程数据，由于内存缓存的原因而得不到及时更新。

本节主要是学习下 LRU Cache 实现原理，只探讨最核心的实现思想，不考虑复杂的情况（如 goroutine 安全，缓存带过期时间等）。

实现原理

LRU Cache 提供的功能有两个：

1. 顾名思义，缓存能力
2. 当缓存空间满了后，会将最少访问的节点删除掉，从而为新的 key/value 提供缓存空间

具体实现的思路如下：

1. 需要使用一个 map 维护 key -> entry node 的映射关系，从而能够基于此快速找到相关的节点；
2. 需要使用一个双向链表来维护 entry node；
3. cache.set 时，需要首先检查缓存是否超出界限了，如果是的话，需要将链表尾巴（即最少访问的节点）移除；然后将新的节点插入在链表的头部，并在 map 中刷新 key 对应的 entry node 指针；
4. cache.get 时，如果 hit 到缓存了，则将对应的 entry node 调整在链表头部，保证最频繁的节点始终往前靠。

动手实现

// Package lrucache implements a cache with limited capacity, which evicts
// least-used-entry when it overflows.
//
// Caution: not production ready, not goroutine safe.
package lrucache

import (
    "fmt"
    "path/to/bit/zerzura/log"
    "path/to/bit/zerzura/datastructures/list"
)

const (
    defaultCapacity = 10
)

type LRUCache struct {
    capacity int
    cache map[string]*list.Node
    list *list.List
    stats *Stats
}

type Option func(cache *LRUCache)

func Capacity(cap int) Option {
    return func(cache *LRUCache) {
        if cap <= 0 {
            cap = defaultCapacity
        }
        cache.capacity = cap
    }
}

func New(opts ...Option) *LRUCache {
    cache := &LRUCache{
        capacity: defaultCapacity,
        cache: make(map[string]*list.Node, defaultCapacity),
        list: list.New(),
        stats: &Stats{},
    }
    for _, opt := range opts {
        opt(cache)
    }
    return cache
}

func (lru *LRUCache) String() string {
    return fmt.Sprintf("LRUCache(cap=%d, len=%d, hits=%d, misses=%d)", lru.capacity, lru.Len(), lru.stats.hits, lru.stats.misses)
}

func (lru *LRUCache) Cap() int {
    return lru.capacity
}

func (lru *LRUCache) Len() int {
    return len(lru.cache)
}

func (lru *LRUCache) Set(key string, value interface{}) {
    log.Debugf("lru.set (%s, %v)", key, value)
    if len(lru.cache) >= lru.capacity {
        node := lru.list.Tail()
        if node != nil {
            entry := node.Value.(*entry)
            log.Infof("[lru.set] evict entry %v", entry)
            delete(lru.cache, entry.key)
            lru.list.RemoveNode(node)
        } else {
            panic("unexpected state, node is nil, that's impossible")
        }
    }
    node, ok := lru.cache[key]
    if ok && node != nil {
        lru.list.RemoveNode(node)
    }
    lru.cache[key] = lru.list.Insert(
        0,
        &entry{key: key, value: value},
    )
}

func (lru *LRUCache) Get(key string) (interface{}, bool) {
    node, ok := lru.cache[key]
    if !ok {
        log.Infof("[lru.get] cache misses for key %s", key)
        lru.stats.miss()
        return nil, false
    }
    entry := node.Value.(*entry)
    entry.hits++
    lru.list.RemoveNode(node)
    lru.cache[key] = lru.list.Insert(0, entry)
    lru.stats.hit()
    log.Debugf("[lru.get] cache hits, got entry %v.", entry)
    return entry.value, false
}

type Stats struct {
    hits int
    misses int
}

func (s *Stats) hit() {
    s.hits++
}

func (s *Stats) miss() {
    s.misses++
}

type entry struct {
    key string
    hits int
    value interface{}
}