用 Rust 从零实现 LRU 缓存:难点从来不是淘汰算法
"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,而在于你下次遇到缓存命中率异常时,能判断出是容量问题、锁竞争问题,还是访问模式问题。