返回文章列表

用 Rust 从零实现 LRU 缓存:难点从来不是淘汰算法

297 字·3 分钟阅读
Rust从零造轮子缓存

"LRU 就是淘汰最久没用的那个。" —— 这句话谁都会说,但写出来就会发现处处别扭。

别扭的地方在于:既要能 O(1) 定位一个 key,又要能 O(1) 找到"最久未使用"的元素,还要能 O(1) 把任意元素挪到队首。没有一个单独的数据结构能同时满足这三点。

答案是把两个结构焊在一起:哈希表负责"找到",双向链表负责"排序"。


为什么必须是双向链表

先用排除法。

数组行不行? 定位要 O(n) 或者哈希+下标;把元素挪到队首意味着移动后面所有元素,O(n)。淘汰看似容易(删最后一个),但前面两条已经否了它。

单向链表行不行? 定位要靠哈希表存指针,这没问题。但要把一个中间节点挪到队首,你需要它的前驱来断链。单向链表拿不到前驱,除非再遍历一遍。

双向链表可以:每个节点同时知道前后邻居,摘除和插入都是常数操作。

use std::collections::HashMap;
 
struct Node<K, V> {
    key: K,
    value: V,
    prev: *mut Node<K, V>,
    next: *mut Node<K, V>,
}
 
pub struct LruCache<K, V> {
    map: HashMap<K, *mut Node<K, V>>,
    head: *mut Node<K, V>, // 最近使用
    tail: *mut Node<K, V>, // 最久未使用
    capacity: usize,
    len: usize,
}

用双向链表 + 裸指针,和上一个轮子(跳表)是同样的理由:节点同时被两个邻居引用,用 Rc<RefCell> 能写,但每次访问都要动引用计数。

哨兵节点省掉一半边界判断

直接管理 head/tail,插入删除时要判断"链表是不是空的""是不是删的头/尾",代码里全是 if。

老练的写法是加两个哨兵节点,它们不存数据,永远存在。空链表就是 head.next == tail。

impl<K, V> LruCache<K, V> {
    fn new_node(key: K, value: V) -> *mut Node<K, V> {
        Box::into_raw(Box::new(Node {
            key,
            value,
            prev: std::ptr::null_mut(),
            next: std::ptr::null_mut(),
        }))
    }
 
    pub fn new(capacity: usize) -> Self {
        assert!(capacity > 0);
        let head = Self::new_node_sentinel();
        let tail = Self::new_node_sentinel();
        unsafe {
            (*head).next = tail;
            (*tail).prev = head;
        }
        Self {
            map: HashMap::with_capacity(capacity),
            head,
            tail,
            capacity,
            len: 0,
        }
    }
}

有了哨兵,insert_front 和 unlink 都不用再判空:

    unsafe fn insert_front(&mut self, node: *mut Node<K, V>) {
        let first = (*self.head).next;
        (*node).prev = self.head;
        (*node).next = first;
        (*first).prev = node;
        (*self.head).next = node;
    }
 
    unsafe fn unlink(&mut self, node: *mut Node<K, V>) {
        let (p, n) = ((*node).prev, (*node).next);
        (*p).next = n;
        (*n).prev = p;
    }

哨兵节点是链表实现里性价比最高的技巧:它把"空表""头尾"这些边界情况变成了普通情况。

get:命中就要挪到队首

    pub fn get(&mut self, key: &K) -> Option<&V> {
        let node = *self.map.get(key)?;
        unsafe {
            self.unlink(node);
            self.insert_front(node);
            Some(&(*node).value)
        }
    }

注意 get 需要 &mut self,因为它要调整链表顺序。这是 LRU 和普通 HashMap 在接口上的第一个区别——读操作有副作用。

如果不想让读带写副作用,就得用 RefCell 或者内部可变性。但那样在多线程下会更麻烦,后面讲。

put:满了就砍尾巴

    pub fn put(&mut self, key: K, value: V) -> Option<V> {
        if let Some(&node) = self.map.get(&key) {
            unsafe {
                let old = std::mem::replace(&mut (*node).value, value);
                self.unlink(node);
                self.insert_front(node);
                return Some(old);
            }
        }
 
        let node = Self::new_node(key, value);
        unsafe {
            self.insert_front(node);
            let k: K = std::ptr::read(&(*node).key);
            self.map.insert(k, node);
        }
        self.len += 1;
 
        if self.len > self.capacity {
            self.evict();
        }
        None
    }
 
    unsafe fn evict(&mut self) {
        let victim = (*self.tail).prev;
        if victim == self.head {
            return;
        }
        self.unlink(victim);
        let key: K = std::ptr::read(&(*victim).key);
        self.map.remove(&key);
        drop(Box::from_raw(victim)); // 释放节点
        self.len -= 1;
    }

这里有个细节值得说:淘汰时要先把 key 从链表节点里读出来,才能去 map 里删。 因为节点一旦释放,key 就没了,而 map 需要它来定位。

std::ptr::read 而不是 move,是因为我们只是"看一眼 key",节点的所有权还在链表手里。

内存释放

裸指针必须手动兜底,否则一定漏:

impl<K, V> Drop for LruCache<K, V> {
    fn drop(&mut self) {
        unsafe {
            let mut cur = (*self.head).next;
            while cur != self.tail {
                let next = (*cur).next;
                drop(Box::from_raw(cur));
                cur = next;
            }
            drop(Box::from_raw(self.head));
            drop(Box::from_raw(self.tail));
        }
    }
}

单线程版够用吗?看场景

如果缓存只在单个任务里用,上面的版本就够了。但服务端缓存通常是多线程共享的,直接套 Mutex 会立刻遇到瓶颈:

// 能跑,但不推荐
pub struct SharedCache<K, V>(Mutex<LruCache<K, V>>);

问题在于:每一次 get 都要拿全局锁,而且 get 有副作用(要改链表)。热点 key 一多,所有线程都在同一把锁上排队,QPS 反而低于单线程。

更糟的是,Mutex 的临界区里还包含了内存分配和链表操作——持锁时间长,锁竞争更严重。

正确的方向:分片锁

工业级实现(比如 Caffeine、Ristretto)的做法是分片(sharding):把一个大缓存拆成 N 个小缓存,每个有独立容量和独立锁。

use std::hash::{Hash, Hasher};
 
pub struct ShardedCache<K, V> {
    shards: Vec<Mutex<LruCache<K, V>>>,
}
 
impl<K: Hash + Eq, V> ShardedCache<K, V> {
    pub fn new(capacity: usize, shards: usize) -> Self {
        let per = (capacity / shards).max(1);
        let shards = (0..shards)
            .map(|_| Mutex::new(LruCache::new(per)))
            .collect();
        Self { shards }
    }
 
    fn shard_of(&self, key: &K) -> usize {
        let mut h = std::collections::hash_map::DefaultHasher::new();
        key.hash(&mut h);
        (h.finish() as usize) % self.shards.len()
    }
 
    pub fn get(&self, key: &K) -> Option<V>
    where
        V: Clone,
    {
        self.shards[self.shard_of(key)].lock().unwrap().get(key).cloned()
    }
 
    pub fn put(&self, key: K, value: V)
    where
        K: Clone,
    {
        self.shards[self.shard_of(&key)].lock().unwrap().put(key, value);
    }
}

分片把锁竞争降低到 1/N。只要哈希分布均匀,不同 key 大概率落到不同分片,互不阻塞。

分片不是"更好的 LRU",而是"用近似换并发"。 代价是全局容量不再精确——某个分片可能早已淘汰,而另一个分片还空着。

这个折中值不值,取决于你的场景:读多写少、命中率要求不那么苛刻的缓存,分片 LRU 几乎总是比全局锁好。

LRU 本身的一个毛病:它太"守旧"

LRU 有个众所周知的弱点:一次全表扫描就会把所有热点数据冲掉。因为扫描的 key 都"刚访问过",它们会挤满队首。

改进方案有两个方向:

  • LRU-K:记录最后一次和倒数第二次访问时间,只看一次的不算"热"
  • TinyLFU + LRU:用频率过滤器做准入,只有比待淘汰元素更热的新元素才能进来

Ristretto 和 Caffeine 走的是第二条路。但那是另一个轮子的体量了,先把 LRU 写扎实。

结论

LRU 缓存是"看起来简单,写起来全是细节"的典型:

哈希表定位元素,双向链表维护顺序,哨兵节点消灭边界判断;淘汰前要先从节点读回 key;多线程下优先分片而不是全局锁。

把它写一遍的价值不在于以后不用 lru crate,而在于你下次遇到缓存命中率异常时,能判断出是容量问题、锁竞争问题,还是访问模式问题。