HashLRU

HashLRU 是一个使用 Rust 实现的 LRU 缓存。

它试图遵循 标准 Rust HashMap 暴露的 API，同时通过限制键的数量（使用 LRU（最近最少使用）策略）来强制限制内存占用，这是一种相当 常见的缓存替换策略。

它受到了 lru（由 Jerome Froelich 实现）的极大启发。底层逻辑类似，使用指针实现的指针双向链表，并结合哈希表。HashLRU 在某些方面略逊一筹，但 API 在某些方面更为丰富。

通常，在常见的 LRU 实现之上，HashLRU 有

• (反)序列化支持
• 各种导入/导出/迭代器/转储以及其他好东西
• 一个可在线程间共享的同步版本

• DiskLRU 在设计上非常相似，作为一个持久存储，而 HashLRU 是一个内存缓存。
• MenhirKV 解决了 DiskLRU 解决的相同问题，即“存储东西，保留最常用的值，丢弃其余的”。它以一种不那么严格和精确的方式完成，但效率更高。

状态

HashLRU 处于玩具项目和可用于生产之间。它附带一个相当完整的测试框架，并试图提供合理的文档，所以这是一个加分项。然而，它相当年轻，据我所知，尚未用于任何生产环境。

此外，还有许多其他库你可以使用

• lru 更快，并且具有更底层的 API。请参阅 文档 和 源代码。
• cached 包含了电池，不仅支持 LRU，还支持许多其他功能。请参阅文档和源码。
• caches 实现了多种不同类型的缓存。请参阅文档和源码。

用法

use hashlru::Cache;

let mut cache = Cache::new(4);
cache.insert("key1", 10);
cache.insert("key2", 20);
cache.insert("key3", 30);
cache.insert("key4", 40);
cache.insert("key5", 50);
// key1 has been dropped, size is limited to 4
assert_eq!(Some("key2"), cache.lru());
assert_eq!(Some(&20), cache.get(&"key2"));
// getting key2 has made key3 the least recently used item
assert_eq!(Some("key3"), cache.lru());
assert_eq!(Some(&40), cache.get(&"key4"));
// getting key4 makes it the most recently used item
assert_eq!("[key3: 30, key5: 50, key2: 20, key4: 40]", format!("{}", cache));

基准测试

来自一个随机的 CI 任务

running 10 tests
test tests::bench_read_usize_builtin_hashmap     ... bench:          34 ns/iter (+/- 1)
test tests::bench_read_usize_extern_caches       ... bench:          58 ns/iter (+/- 30)
test tests::bench_read_usize_extern_lru          ... bench:          24 ns/iter (+/- 5)
test tests::bench_read_usize_hashlru_cache       ... bench:          25 ns/iter (+/- 3)
test tests::bench_read_usize_hashlru_sync_cache  ... bench:          61 ns/iter (+/- 18)
test tests::bench_write_usize_builtin_hashmap    ... bench:         104 ns/iter (+/- 19)
test tests::bench_write_usize_extern_caches      ... bench:         116 ns/iter (+/- 46)
test tests::bench_write_usize_extern_lru         ... bench:          62 ns/iter (+/- 32)
test tests::bench_write_usize_hashlru_cache      ... bench:          64 ns/iter (+/- 34)
test tests::bench_write_usize_hashlru_sync_cache ... bench:         100 ns/iter (+/- 42)
test result: ok. 0 passed; 0 failed; 0 ignored; 10 measured; 0 filtered out; finished in 43.16s

这些是在一个 100k 项的缓存中完成的。

这并非全面深入的基准测试结果，但这里有一些事实

• 使用hasbrown 哈希图可以加快速度，这也是为什么 hashlru 和 lru 在这些基准测试中比普通的 HashMap 表现更好的主要原因。
• hashlru 并不是最快的，lru 总是表现最好，它有一些有趣的边缘情况优化。如果你追求的是原始速度，请使用 lru。

要运行基准测试

cd bench
rustup default nightly
cargo bench

链接

• crate 在 crates.io
• doc 在 docs.rs
• source 在 gitlab.com
• DiskLRU，一个类似的持久存储
• SQueue，一个丢弃旧项的 FIFO 队列（存在于 0.10.0 版本中）
• Rust 双向链表实现 解释了如何使用 RefCell
• 在 Rust 中实现 LRU 缓存 使用基于数组的存储
• lru 的源代码，它是一个非常好的灵感来源
• Rust 0.12.0 中 lru 的早期实现，也是一个非常好的灵感来源

许可证

HashLRU 采用 MIT 许可。