LFU（Least Frequently Used）是一种常见的缓存淘汰算法，其核心思想是淘汰一段时间内被访问次数最少的数据项。与大家更熟悉的LRU（最近最少使用）算法不同，LRU关注“访问的新鲜度”，而LFU则更侧重于数据的“访问频率”。本文将深入探讨如何在 Rust 中实现一个时间复杂度为 O(1) 的高效 LFU 缓存，并详细解析其核心源码与设计考量。
LFU的原理与实现机制
-
基本思想：LFU算法通过记录数据项的访问频次来工作。当缓存容量达到上限时，系统将会淘汰访问频次最低的数据项。这种方法基于一个假设：在一段时间内被访问频次较少的数据，未来被访问的几率同样较小。
-
数据结构选择：为实现 O(1) 的时间复杂度，经典的 LFU 实现通常结合哈希表和双向链表。哈希表用于快速查找节点是否存在，而双向链表则用于根据访问频次组织数据项。在我们的实现中，双向链表被一个功能相似的 LruCache 替代，以便在 remove 或改变频次时能以 O(1) 复杂度操作。最初曾考虑使用 HashSet<Key>，但因其缺乏高效的 pop 操作，在频繁淘汰时随机选择元素的效率太低。
-
节点管理：每个节点除了存储键值对，还需附带访问频次信息。每次数据项被访问时，其对应的节点频次会增加；当需要淘汰时，则寻找频次最低的节点进行移除或替换。
LFU与LRU的对比及适用场景
- 算法侧重点差异：LRU侧重于数据的“访问新鲜度”，即最近未被访问的数据更容易被淘汰；而LFU更关注数据项的“总访问频次”，不频繁访问的数据被认为是低优先级的。
- 适用场景的不同：LRU适合应对具有时间局部性的数据访问模式，例如某些顺序读取的场景；LFU则更适合数据访问模式较为平稳，且各个数据项访问频率差异明显的环境。
- 实现复杂性对比：LRU的实现相对简单，通常只需要维护一个按照时间顺序排列的链表；而LFU需要同时考虑访问频次和时间两个维度，因此实现上更为复杂。这也正是 Rust 实现需要精巧设计的挑战所在。
LFU算法的实际应用案例
- 缓存系统中的应用：许多现代缓存系统，如 Redis，都实现了LFU作为可选的缓存逐出策略。在配置
maxmemory-policy 时，可以选择 volatile-lfu 或 allkeys-lfu 等选项。
- 负载均衡算法：在分布式系统中，LFU也可以作为一种简单的负载均衡策略，将请求分散到不同的服务器上，避免单点过载。
- 数据库查询优化：数据库管理系统中，LFU可以用来优化查询计划的缓存，减少磁盘I/O次数，提高重复查询的性能。
结构设计
与 Lru 的结构类似，键（K）与值（V）均采用指针方式保存，以避免在使用过程中因 Copy 或 Clone 带来性能损耗。需要注意的是，使用指针在 Rust 中会引入许多 unsafe 代码块，因为直接访问指针被认为是 unsafe 操作。作为替代方案，也可以使用数组下标来模拟指针。
节点设计
相较于普通的Lru节点，我们需要额外存储访问次数数据。
/// Lfu节点数据
pub(crate) struct LfuEntry<K, V> {
pub key: mem::MaybeUninit<K>,
pub val: mem::MaybeUninit<V>,
/// 访问总频次
pub counter: usize,
/// 带ttl的过期时间，单位秒
/// 如果为u64::MAX，则表示不过期
#[cfg(feature = "ttl")]
pub expire: u64,
}
类设计
LFU 的实现相对复杂，这里我们维护了最大及最小的访问频次，以便在遍历时能高效定位。
pub struct LfuCache<K, V, S> {
map: HashMap<KeyRef<K>, NonNull<LfuEntry<K, V>>, S>,
/// 因为HashSet的pop耗时太长, 所以取LfuCache暂时做为平替
times_map: HashMap<u8, LruCache<KeyRef<K>, (), DefaultHasher>>,
cap: usize,
/// 最大的访问频次
max_freq: u8,
/// 最小的访问频次
min_freq: u8,
/// 总的访问次数
visit_count: usize,
/// 初始的访问次数
default_count: usize,
/// 每多少次访问进行一次衰减
reduce_count: usize,
/// 下一次检查的时间点，如果大于该时间点则全部检查是否过期
#[cfg(feature = "ttl")]
check_next: u64,
/// 每次大检查点的时间间隔，如果不想启用该特性，可以将该值设成u64::MAX
#[cfg(feature = "ttl")]
check_step: u64,
/// 所有节点中是否存在带ttl的结点，如果均为普通的元素，则过期的将不进行检查
#[cfg(feature = “ttl”)]
has_ttl: bool,
}
频次的设计
这里频次被设计成了 u8 类型，但实际访问次数可能远超 255。因此，我们将总访问次数与频次做了一个映射，以防止数据结构碎片化过高及频次变动过于频繁。其核心原理是：越高的访问频次差异对淘汰策略的影响越小。例如，访问4次和5次差别明显，但100次和101次几乎没差别。通过这种映射，我们可以将很大的访问梯度压缩到较小的范围内，减少操作开销。
/// 避免hash表爆炸， 次数与频次映射
fn get_freq_by_times(times: usize) -> u8 {
lazy_static! {
static ref CACHE_ARR: Vec<u8> = {
let vec = vec![
(0, 0, 0u8),
(1, 1, 1u8),
(2, 3, 2u8),
(4, 4, 3u8),
(5, 5, 4u8),
(6, 7, 5u8),
(8, 9, 6u8),
(10, 12, 7u8),
(13, 16, 8u8),
(16, 21, 9u8),
(22, 40, 10u8),
(41, 79, 11u8),
(80, 159, 12u8),
(160, 499, 13u8),
(500, 999, 14u8),
(999, 1999, 15u8),
];
let mut cache = vec![0; 2000];
for v in vec {
for i in v.0..=v.1 {
cache[i] = v.2;
}
}
cache
};
static ref CACHE_LEN: usize = CACHE_ARR.len();
};
if times < *CACHE_LEN {
return CACHE_ARR[times];
}
if times < 10000 {
return 16;
} else if times < 100000 {
return 17;
} else if times < 1000000 {
return 18;
} else {
return 19;
}
}
这里使用了懒初始化 (lazy_static!)，只有在该函数第一次被调用时才会初始化静态数据，且只会初始化一次，以提升访问速度。
reduce_count 的设计（降权机制）
假设一个元素在短时间内被访问了极多次（例如10万次），之后很长一段时间不再被访问。在普通的LFU规则下，它将永久保持高访问频次，很难被淘汰，从而长期占用缓存空间。针对这种“热点数据冷却”问题，我们设计了降权机制。例如，设置 reduce_count=100000，那么每累计10万次总访问，就对所有存量数据的访问次数进行降权（新次数 = 原次数 / 2）。这样，那个10万次访问的元素权重就会逐渐衰减，如果后续不再被访问，最终将被淘汰。visit_count 用于记录当前累计访问次数，一旦超过 reduce_count 就触发一轮全局降权并重置计数器。
default_count 的设计
由于存在降权机制，历史数据的访问次数可能会变得很低。因此，我们为每个新插入的元素赋予一个初始访问次数（默认为5），以防止新数据刚插入就因为历史数据降权后的极低次数而被立即淘汰。
初始化
首先初始化对象、哈希表及空的双向链表（此处用 LruCache 模拟）：
impl<K, V, S> LfuCache<K, V, S> {
/// 提供hash函数
pub fn with_hasher(cap: usize, hash_builder: S) -> LfuCache<K, V, S> {
let cap = cap.max(1);
let map = HashMap::with_capacity_and_hasher(cap, hash_builder);
Self {
map,
times_map: HashMap::new(),
visit_count: 0,
max_freq: 0,
min_freq: u8::MAX,
reduce_count: cap.saturating_mul(100),
default_count: 4,
cap,
#[cfg(feature = "ttl")]
check_step: DEFAULT_CHECK_STEP,
#[cfg(feature = "ttl")]
check_next: get_milltimestamp() + DEFAULT_CHECK_STEP * 1000,
#[cfg(feature = “ttl”)]
has_ttl: false,
}
}
}
此处 min_freq 初始值大于 max_freq，在后续循环查找时不会进行任何操作，表示缓存为空。
元素插入、访问与淘汰
插入或访问对象时，需处理频次变化，分为两种情况：频次映射未改变和已改变。
fn try_fix_entry(&mut self, entry: *mut LfuEntry<K, V>) {
unsafe {
if get_freq_by_times((*entry).counter) == get_freq_by_times((*entry).counter + 1) {
self.visit_count += 1;
(*entry).counter += 1;
} else {
self.detach(entry);
self.attach(entry);
}
}
}
例如，访问次数从10次变为11次，如果其映射的频次没有变化，我们只需将计数器加1，无需移动元素在频次链表中的位置。这种优化避免了不必要的链表操作。
attach – 将节点附加到对应频次的链表
fn attach(&mut self, entry: *mut LfuEntry<K, V>) {
unsafe {
self.visit_count += 1;
(*entry).counter += 1;
let freq = get_freq_by_times((*entry).counter);
self.max_freq = self.max_freq.max(freq);
self.min_freq = self.min_freq.min(freq);
self.times_map
.entry(freq)
.or_default()
.reserve(1)
.insert((*entry).key_ref(), ());
self.check_reduce();
}
}
附加节点时，我们更新 min_freq 和 max_freq，并将该元素的键放入对应频次的 LruCache 中（预先通过 reserve(1) 预留空间），最后检查是否需要触发降权。
detach – 从队列中剥离节点
/// 从队列中节点剥离
fn detach(&mut self, entry: *mut LfuEntry<K, V>) {
unsafe {
let freq = get_freq_by_times((*entry).counter);
self.times_map.entry(freq).and_modify(|v| {
v.remove(&(*entry).key_ref());
});
}
}
此处我们仅从对应频次的 LruCache 中移除该键。由于使用 LruCache，移除也是 O(1) 时间复杂度。这里不维护 min_freq 和 max_freq，因为不确定当前频次链表是否为空，维护带来的收益较低。
check_reduce – 降权操作
fn check_reduce(&mut self) {
if self.visit_count >= self.reduce_count {
let mut max = 0;
let mut min = u8::MAX;
for (k, v) in self.map.iter() {
unsafe {
let node = v.as_ptr();
let freq = get_freq_by_times((*node).counter);
(*node).counter /= 2;
let next = get_freq_by_times((*node).counter);
max = max.max(next);
min = min.min(next);
if freq != next {
self.times_map.entry(freq).and_modify(|v| {
v.remove(k);
});
self.times_map
.entry(next)
.or_default()
.reserve(1)
.insert((*node).key_ref(), ());
}
}
}
self.max_freq = max;
self.min_freq = min;
self.visit_count = 0;
}
}
降权操作遍历所有节点，将访问次数减半，并重新计算其频次。如果频次发生变化，则将其移动到新的频次链表中。此操作的时间复杂度为 O(n)。降权后，重新初始化 min_freq 和 max_freq。
replace_or_create_node – 替换或创建节点（淘汰逻辑）
fn replace_or_create_node(&mut self, k: K, v: V) -> (Option<(K, V)>, NonNull<LfuEntry<K, V>>) {
if self.len() == self.cap {
for i in self.min_freq..=self.max_freq {
if let Some(val) = self.times_map.get_mut(&i) {
if val.is_empty() {
continue;
}
let key = val.pop_unusual().unwrap().0;
let old_node = self.map.remove(&key).unwrap();
let node_ptr: *mut LfuEntry<K, V> = old_node.as_ptr();
let replaced = unsafe {
(
mem::replace(&mut (*node_ptr).key, mem::MaybeUninit::new(k))
.assume_init(),
mem::replace(&mut (*node_ptr).val, mem::MaybeUninit::new(v))
.assume_init(),
)
};
unsafe {
(*node_ptr).counter = self.default_count;
}
return (Some(replaced), old_node);
}
}
unreachable!()
} else {
(None, unsafe {
NonNull::new_unchecked(Box::into_raw(Box::new(LfuEntry::new_counter(
k,
v,
self.default_count,
))))
})
}
}
当缓存已满时，执行淘汰算法。我们从 min_freq 到 max_freq 遍历，找到第一个非空的频次链表，并移除其尾部的一个元素（即该频次下“最久未访问”的，这融合了LRU的思想，以解决同一频次下的淘汰问题）。如果不维护 min_freq 和 max_freq，最坏情况需要遍历0-255共256个频次桶。
其它操作
该 LFU 缓存实现还提供了丰富的 API：
pop：移除并返回最近访问过的元素（栈顶）。pop_last：移除并返回最久未被访问的元素（栈尾）。contains_key：判断是否包含指定的键。raw_get：直接获取键对应的值，不触发访问频次更新。get：获取键对应的值，并更新其访问频次。get_mut：获取键对应的可变引用，并更新其访问频次。retain：根据闭包条件保留元素。get_or_insert_default：获取键对应的值，若不存在则插入默认值。get_or_insert_mut：获取键对应的可变引用，若不存在则插入给定值。set_ttl：设置元素的生存时间（需启用 ttl 特性）。del_ttl：删除元素的生存时间，使其永不过期。get_ttl：获取元素的剩余生存时间。set_check_step：设置全局过期检查的时间间隔。
如何使用
在 Cargo.toml 中添加依赖：
[dependencies]
algorithm = "0.1"
使用示例
use algorithm::LfuCache;
fn main() {
let mut lru = LfuCache::new(3);
lru.insert(“hello”, “algorithm”);
lru.insert(“this”, “lru”);
lru.set_reduce_count(100);
assert!(lru.get_visit(&“hello”) == Some(5));
assert!(lru.get_visit(&“this”) == Some(5));
for _ in 0..98 {
let _ = lru.get(“this”);
}
lru.insert(“hello”, “new”);
assert!(lru.get_visit(&“this”) == Some(51)); // 经历了降权
assert!(lru.get_visit(&“hello”) == Some(3)); // 插入覆盖重置了次数
let mut keys = lru.keys();
assert!(keys.next() == Some(&“this”));
assert!(keys.next() == Some(&“hello”));
assert!(keys.next() == None);
}
完整项目地址
本项目已开源，如果你想深入研究 Rust 实现的细节或参与贡献，可以访问 GitHub 仓库：https://github.com/tickbh/algorithm-rs 。对于这类 开源实战 项目，阅读源码是理解其 数据结构 与算法精髓的最佳方式。
结语
LFU算法通过跟踪数据项的访问频次来决定淘汰对象，适用于数据访问频率差异较大且模式相对稳定的场景。与LRU相比，LFU更能抵御偶发性“洪峰”访问对缓存长期状态的冲击。然而，其实现也更为复杂，需要精巧的数据结构设计来平衡效率与公平性。本文解析的实现通过频次映射、降权机制以及维护最小/最大频次等优化，在 Rust 中实现了高效的 LFU 缓存。在实际应用中，应当根据具体的数据访问模式和系统需求，灵活选择和调整缓存淘汰策略。
发表于 3 天前
|
查看: 21|
回复: 0
