Cache.rs

我一直在考虑在 Rust 中实现一个低延迟、可预测的缓存库。从几个角度来看，这很有趣：一方面，我们可以对内存布局进行低级控制，同时尊重 Rust 的类型系统和其保证；另一方面，尝试在效率保证和控制级别之间取得平衡，可能支持可插拔的驱逐算法，同时不影响性能。我认为后者实际上是不可能的：即在性能祭坛上对设计进行一些牺牲将永远需要，这将与可插拔驱逐相矛盾。但我仍然想挑战一下。

警告：现在这些都只是我在玩。我只是在尝试得到一个能工作并暴露出某种合理 API 的东西。一旦我整理好这些，我就会迭代实现，开始让它更快...

初始功能

• 通过 API 缓存
• 一次加载
• 时钟驱逐
• 线程安全，具有内部可变性
• 分段存储，利用 std::hash
• 细粒度锁定（即在填充时不锁定整个 Cache/Segment，因为填充可能需要一段时间）

路线图

v0.1.0

• 基本 API
• API 的最小和原始实现

v0.2.0

• 细粒度锁定
• 适当的分段
• 第一次性能改进

v0.3.0

• 对 CacheThrough 的性能优化
• 开始添加其他缓存 API（即除了 CacheThrough 之外，也许是一个缓存-aside）

v0.4.0

• 更多的驱逐算法？
• 可组合性？... 缓存和驱逐器的可组合性？

v1.0.0

• 当我们拥有一个不错的工具箱时 :)

我认为 v0.x 版本应该说明如何解决 API 和性能之间的紧张关系。

实现细节

我认为这个项目的关键部分，即能够以 CPU 缓存友好的方式移动时钟指针。可能需要将时钟位信息存储在不同于缓存条目本身的不同数据结构中。这将在缓存命中时对位进行更新带来一些开销。

另一个有趣的方面是如何以乐观的方式处理协调原语。因此，我们提出了使用内部可变性来处理缓存条目的想法，但在处理淘汰数据时采取不同的策略；可能降低对这些的保证。

最后，尝试引入另一个淘汰算法（可能是LRU，它需要不同的存储淘汰数据的方法）并看看这对设计有何影响。

当前API提案

[来源，Rust]

let cache = cachers::CacheThrough::new(size); // <1>
let value: Option<Arc<V>> = cache.get(key, populating_fn); // <2>
let updated: Option<Arc<V>> = cache.udpate(key, updating_fn); // <3>
cache.remove(key); // <4>

<1> cache 不是 mut，并且 <K, V> 是推断的；缓存最多包含 size 个条目；<2> 在此情况下，key 将导致未命中，只调用一次 populating_fn，即使 cache 被多个线程共享并且它们都试图访问同一个 key。 populating_fn 返回一个值 Some<V> 来填充 key: K 的条目。然后 .get 返回一个 Option<Arc<V>>，如果 populating_fn 返回 None 则返回 None <3> .udpate 强制更新 key，无论它是否已经存在。 updating_fn 接收键，但与 populating_fn 不同，它还接收一个表示如果存在则之前值的 Option<Arc<V>>；然后 .update 返回更新的 V <4> remove 使 key 的映射无效，而不提出新的值。这实际上相当于一个 .update(key, |_, _| None)。我想知道这是否真的有必要... 但它确实在这里！