plru

伪LRU缓存跟踪的并发实现。

从 TFS 迁移而来。

lib.rs:

并发（无锁）PLRU缓存替换策略的高效实现。

缓存替换

缓存替换策略用于确定哪些缓存行（缓冲区）需要替换，因为这些缓存行不再“热”（可能在不久的将来被使用）。存在多种不同的方法。

LRU是缓存替换策略的名称，它将替换最久未被使用的缓存行。

PLRU是LRU派生出来的缓存替换策略的名称，但它使用的是最近使用行的近似度量，而不是精确度量。这允许在缓存策略可能更差的情况下，进行更有效的缓存管理（LRU缓存管理速度非常慢）。PLRU缓存被许多主要CPU用于维护CPU缓存行。

我们使用PLRU的一个特定版本：BPLRU或位PLRU。树PLRU是一个替代方案，但它不易于实现并发。

用法

运行时定义的缓存行数量

这可以通过plru::create()来实现，除非启用了no_std特性。

如何处理固定大小的数组

我们的实现是泛型的，适用于固定大小的数组（或堆分配的向量），不依赖于任何外部库。我们通过抽象AsRef<[AtomicU64]>来允许广泛的数组形式。

为了方便，我们定义了一组类型别名，用于不同大小的缓存。

实现细节

这个BPLRU的实现使用原子整数来存储位标志，因此构成一个具有出色性能的并发且完全无锁的缓存管理器。

缓存行被组织成64位整数，存储位标志（“热”和“冷”）。每个这些标志都称为“块”。每当缓存行被访问（使用）时，其位标志就会被设置。

找到要替换的缓存行很简单，只需在某个块中找到一个未设置的位。如果块中的所有缓存行都是热的，它们就会被翻转，使它们都变成冷的。这个过程称为缓存膨胀。

为了避免重复缓存替换，我们使用一个计数器，该计数器用于最大化相同批量（bulk）用于查找缓存行替换的时间。

算法的详细描述在每个方法的文档中。

简而言之...

简而言之，算法的工作原理是缓存行在它们的槽位（批量）填满之前保留一个条目，这将（在缓存替换时）导致该批量中的每个缓存行都被假定为不活跃，直到它们恢复位置。

这是一个类比停车场。我们只在停车场被填满时关心停车位（如果没有被填满，我们只需放置我们的车，就可以了）。当它被填满时，我们需要确保每辆车的车主在过去的N小时内（或者：自从停车场被填满以来）都曾在那里，以避免车主永久占据位置。当新车到来并且一辆车停放足够长的时间时，它必须被强制移除以腾出新的空间。

现在，想象每个停车场都是一个批量。每辆车代表一个缓存行。

代码质量

✔ 经过充分测试

✔ 有良好的文档

✔ 有示例

✔ 符合Rust的风格指南

✔ 符合Rust的语言习惯

✔ 适合生产环境