具有 LRU 过期和并发访问的内存中的 Key/Value 存储

描述

项目存储在 N 个分片/桶化的 HashMap 中以提高并发性。每个项目都始终位于 RwLock 后面。查询项目将返回与该锁关联的守卫。未锁定的项目保留在列表中以实现最近最少使用过期策略。锁定项目从该 lru 列表中删除并放入 lru 列表，当它们解锁时。锁定项目不会阻止宿主 HashMap。

lib.rs:

LRU 列表和过期配置

未使用的项目被推送到最近最少使用列表的末尾。每当 CacheDb 决定过期项目时，它们将从 lru 列表的头部取出并丢弃。

有一些配置选项可以调整缓存行为。这些配置都是按桶设置的，而不是全局的。因此，在配置 cachedb 时必须考虑桶的数量。当需要精确计算（例如，对于 'highwater'）时，必须使用单个桶 cachedb。

重要的是要知道，最小/最大容量配置针对的是底层容器的 容量，而不是已使用条目数。这允许在容器调整大小后更好地利用内存，但应尊重缓存不会使容器过度增大的方式。

默认配置是为了创建一个相当通用的缓存，可以长得相当大，并对过期条目持保守态度。因此，它应该适用于许多用例。如果需要，则 max_capacity_limit 或 highwater 是首先调整的旋钮。

实现讨论

存储项目的 HashMap 使用包装条目。条目通过 RwLock 保护实际项目。API 允许通过这些锁访问项目，并返回其包装守卫。由于并发访问条目不应阻止 HashMap，因此需要一些 'unsafe' 代码来实现手动锁定，这些锁定隐藏在安全的 API 后面。

新项目以原子方式构建，通过传递生成项目的闭包到相应的查找函数。在项目构建过程中，它有一个写锁，这确保了在并发构建/查询时只有一个构建者获胜，其他任何构建者都将获得新构建的项目。

证明没有违反生命周期保证

实际上很简单，返回的守护者有一个与CacheDB对象绑定的Rust生命周期。因此，没有任何访问可以超出宿主集合。

证明不存在数据竞争

在大多数部分，Mutex和RwLock确保不会发生数据竞争，这是由Rust验证的。

实现中的不安全部分从宿主集合中分离出一个LockGuard来释放HashMap上的互斥锁。这可能导致潜在的未定义行为（UB），当HashMap丢弃仍在使用/锁定中的值时。然而，这永远不会发生，因为没有一种方式可以无控制地丢弃条目。守护者的生命周期绑定到宿主哈希表，不能超出它。从哈希表中删除项目仅从LRU列表中执行，该列表永远不会包含锁定（因此正在使用）的条目。'remove(key)'成员函数会显式检查条目是否未在使用或延迟删除，直到所有对项目的锁都释放。

当HashMap可能重新分配表并将包含条目的Box移动到其他地方时，这并不是问题，因为锁守护者直接包含对条目的引用，而不是对外部Box的引用。

证明锁定是死锁免费的

以相同顺序获取的锁永远不会发生死锁。死锁仅发生在两个或更多线程等待资源，而另一个线程正在尝试获取它所持有的资源时。

在查找时，HashMap将被锁定。当元素被找到时，LRU列表将被锁定，并且元素可能被从其中删除（如果它未被使用）。一旦完成LRU列表，其锁定将被释放。

值得一提的是，使用cachedb的代码在以不良顺序获取锁时仍然可能会发生死锁。最简单的建议是在每个线程中始终只有一个单一的独占锁。如果不切实际，需要仔细考虑锁定顺序或采用其他策略来防止死锁。

测试

'test::multithreaded_stress'测试可以通过环境变量来控制。

• 'STRESS_THREADS'设置要启动的线程数。默认为10。
• 'STRESS_WAIT'线程随机等待最多这么多毫秒以模拟一些工作。默认为5。
• 'STRESS_ITERATIONS'每个线程应执行多少次迭代。默认为100。
• 'STRESS_RANGE'测试使用的唯一键的数量。默认为1000。

默认值相对较小，以便测试套件可以在短时间内完成。对于专门的压力测试，至少需要将STRESS_ITERATIONS和STRESS_THREADS显著增加。尝试'STRESS_ITERATIONS=10000 STRESS_RANGE=10000 STRESS_THREADS=10000'进行一些更困难的测试。