sharded-slab

无锁并发缓存。

缓存提供对单个数据类型多个实例的预先分配存储。当需要大量单个类型的数据时，这比单独分配每个项目更有效。由于分配的项目大小相同，内存碎片化减少，创建和删除新项目可以非常便宜。

这个crate实现了一个基于usize索引的无锁并发缓存。

注意：此crate目前为实验性。请随意将其用于您的项目，但请注意，仍有大量优化空间，并且可能仍存在一些隐藏的bug。

使用方法

首先，将以下内容添加到您的 Cargo.toml

sharded-slab = "0.1.7"

此crate提供了两种类型，Slab 和 Pool，它们提供了使用缓存的不同API。

Slab 实现了一个用于存储小类型、在线程间共享和通过索引访问的缓存。新条目通过 插入 数据来分配，通过值移动。同样，条目可以通过从缓存中 取出 来释放。此API类似于 Vec<Option<T>>，但允许无锁并发插入和删除。

相比之下，Pool 类型提供了一个用于 重用存储 的 对象池 风格的 API。与 Slab 不同，它不是构建值并将它们移动到池中，而是从池中 分配条目 时，提供一个闭包，该闭包带有一个可变引用，用于就地初始化条目。当条目被释放时，它们会在原地被 清除。拥有堆分配的类型可以通过丢弃它们存储的任何 数据 来清除，同时保留之前分配的任何容量。这意味着一个 Pool 可以用于重用一组现有的堆分配，减少分配器的负载。

示例

将项目插入到片段中，返回索引

use sharded_slab::Slab;
let slab = Slab::new();

let key = slab.insert("hello world").unwrap();
assert_eq!(slab.get(key).unwrap(), "hello world");

要跨线程共享片段，它可能被包裹在一个 Arc

use sharded_slab::Slab;
use std::sync::Arc;
let slab = Arc::new(Slab::new());

let slab2 = slab.clone();
let thread2 = std::thread::spawn(move || {
    let key = slab2.insert("hello from thread two").unwrap();
    assert_eq!(slab2.get(key).unwrap(), "hello from thread two");
    key
});

let key1 = slab.insert("hello from thread one").unwrap();
assert_eq!(slab.get(key1).unwrap(), "hello from thread one");

// Wait for thread 2 to complete.
let key2 = thread2.join().unwrap();

// The item inserted by thread 2 remains in the slab.
assert_eq!(slab.get(key2).unwrap(), "hello from thread two");

如果片段中的项目必须被修改，则每个项目可以使用 Mutex 或 RwLock，提供对项目的粒度锁定，而不是对片段的锁定

use sharded_slab::Slab;
use std::sync::{Arc, Mutex};
let slab = Arc::new(Slab::new());

let key = slab.insert(Mutex::new(String::from("hello world"))).unwrap();

let slab2 = slab.clone();
let thread2 = std::thread::spawn(move || {
    let hello = slab2.get(key).expect("item missing");
    let mut hello = hello.lock().expect("mutex poisoned");
    *hello = String::from("hello everyone!");
});

thread2.join().unwrap();

let hello = slab.get(key).expect("item missing");
let mut hello = hello.lock().expect("mutex poisoned");
assert_eq!(hello.as_str(), "hello everyone!");

与类似 Crates 的比较

• slab：Carl Lerche 的 slab crate 提供了一个具有类似 API 的片段实现，通过在单个向量中存储所有数据来实现。

  与 sharded-slab 不同，在片段中插入和删除元素需要可变访问。这意味着如果片段被多个线程并发访问，它必须由 Mutex 或 RwLock 保护。项目不能并发插入或删除（如果使用 Mutex，则不能访问），即使它们是无关的。在许多情况下，锁可能会成为瓶颈。另一方面，sharded-slab 允许并发访问、插入和删除片段中的单独索引，而无需全局锁。因此，当片段在多个线程之间共享时，此 crate 比代码 slab 提供了显著更好的性能。

  然而，无锁片段引入了一些额外的常数因子开销。这意味着在那些片段 不 被多个线程共享且无需加锁的使用案例中，sharded-slab 可能会提供略差一些的性能。

  总结：sharded-slab 在并发使用案例中提供了显著的性能改进，而 slab 应该在单线程使用案例中优先选择。

安全性和正确性

Rust 中大多数无锁数据结构的实现都需要一定量的不安全代码，而这个 crate 也不例外。为了捕获不安全代码中的潜在错误，我们使用了 loom，这是一个并发 Rust 程序的排列测试工具。这个 crate 的所有 unsafe 块都发生在对 loom UnsafeCell 的访问中。这意味着当这些访问在这个 crate 的测试中出现时，loom 将断言它们在多个排列的并发执行测试中符合 C11 内存模型。

为了防止ABA问题，这个crate利用了代际索引。slab中的每个槽位跟踪一个代际计数器，每当向该槽位插入一个值时，计数器就会递增。由Slab::insert返回的索引包含了值插入时的槽位代际，打包在索引的高位。这确保了如果向同一个槽位插入、删除并再次插入新值，第一次调用insert返回的键不会映射到新值。

由于为存储代际计数器预留了固定数量的位，计数器在递增多次后会回绕。为了避免返回的索引存活时间足够长，以至于看到代际计数器回绕到相同的值，配置索引位分配时应该相当慷慨。

性能

这些图表是通过基准测试sharded slab实现产生的，使用了criterioncrate。

第一个图表显示了在五个线程并发地将不断增加的项目插入和从slab中移除时的基准测试结果。它比较了sharded slab实现与RwLock<slab::Slab>的性能。

第二个图表显示了单个线程插入和移除不断增加的项目时的基准测试结果。它比较了sharded slab实现与一个RwLock<slab::Slab>和一个mut slab::Slab的性能。

这些基准测试表明，虽然sharded方法引入了小的常数因子开销，但它提供了跨并发访问的显著更好的性能。

许可证

此项目根据MIT许可证授权。

贡献

除非你明确声明，否则你提交给此项目的任何有意贡献的代码都将按照MIT许可证授权，不附加任何额外条款或条件。