7 个版本
| 0.3.0 | 2024 年 8 月 2 日 |
|---|---|
| 0.2.3 | 2024 年 7 月 17 日 |
| 0.2.2 | 2024 年 6 月 17 日 |
| 0.2.0 | 2024 年 5 月 20 日 |
| 0.1.1 | 2024 年 4 月 15 日 |
#114 in 并发
每月 514 次下载
62KB
863 行
高效的并发 ID 到对象解析器
IDR (标识符解析器) 提供了一种高效并发地将整数 ID 映射到对象引用的方法。这在需要快速根据 ID 查找对象的情况下特别有用。
- ID 在多台机器之间共享或在文件系统上存储
- ID 被用作比
Weak智能指针更经济的替代品 - ID 用于与不可信代码的 FFI
该 crate 的主要目标是提供一个结构，以便快速通过 ID 获取对象。解决此问题的最流行方法是并发 slab。然而，并发集合处理的一个有趣问题来自移除操作。假设一个线程在另一个线程同时读取同一元素时从某个无锁 slab 中移除一个元素。第一个线程必须等待第二个线程停止读取该元素。只有在那时，销毁它才是安全的。因此，每个读取操作实际上都应该修改内存，以便告诉其他线程该条目目前正在被访问。这可能导致高竞争，从而带来巨大的性能损失（请参阅下面的基准测试），即使许多线程主要读取而不更改数据。
针对此问题的现代解决方案是 EBR (基于周期的内存回收)。该 crate 基于 sdd crate 的 EBR，而不是 crossbeam-epoch，因为它更高效。
每次插入都会分配一个新的 EBR 容器。因此，如果插入频繁，最好使用一个强大的现代分配器（例如 mimalloc）。
注意：此 crate 未针对插入/删除操作进行优化（尽管可以），如果这是你的情况，请检查 sharded-slab，它是并发 slab 的有效且经过良好测试的实现。
示例
将项目插入 IDR 并返回密钥
use idr_ebr::{Idr, EbrGuard};
let idr = Idr::default();
let key = idr.insert("foo").unwrap();
let guard = EbrGuard::new();
assert_eq!(idr.get(key, &guard).unwrap(), "foo");
安全性和正确性
在Rust中，大多数无等待和无锁数据结构的实现都需要一些不安全代码，这个crate也不例外。
因此，测试应该是尽可能完整的，这也是为什么使用了许多工具来验证正确性的原因
为了防止ABA问题，这个crate使用了代际索引。底层slab中的每个槽位跟踪一个代际计数器，每次从这个槽位中移除值时，计数器都会增加，而由Idr::insert()返回的键包括当值被插入时的槽位代际，打包到键的高位。这确保了如果值被插入、移除，然后在底层slab中相同的槽位插入新值，第一次调用insert返回的键不会映射到新值。
由于为存储代际计数器留出了固定数量的位，计数器在增加一定次数后会回绕。为了避免返回索引存在的时间足够长以至于看到代际计数器回绕到相同的值的情况，配置键位分配时应该相当慷慨。
性能
这些图表是由使用基准测试生成的，使用criterion crate。
第一个显示了read_only基准测试的结果，其中越来越多的线程访问相同的槽位，这导致高竞争。它比较了IDR与sharded-slab和简单的std::sync::Weak::upgrade()的性能
idr-pin-once：所有访问都使用一个EbrGuard::new()idr-repin：每次访问都使用一个新的EbrGuard::new()weak：使用std::sync::Weak::upgrade()sharded-slab：使用sharded-slabcrate中的默认参数的Slab
这个基准测试表明，IDR在get()上根本不会产生任何竞争。
第二个图显示了insert_remove基准测试的结果，其中越来越多的线程向IDR中插入和移除条目。如前所述，这不是这个crate的目标，也没有为此进行优化。
idr：来自此库的IDR结构sharded-slab：来自sharded-slab库的Slab
实现
IDR基于slab，每个槽位包含EBR容器的链接。因此，每次调用Idr::insert()时都会调用分配器来创建该容器。
容器可以被多个线程临时使用（Idr::get()或Idr::iter()）以及永久使用（Idr::get_owned()），即使IDR已经被丢弃或者条目从IDR中删除。
IDR结构
IDR pages slots
#─►┌───────────┐ ┌───►┌──────────┐
│ page #0 │ │ ┌►│ next │
├───────────┤ │ │ ├──────────┤
│ page #1 │ │ │ │generation│
│ slots ─┼──┘ │ ├──────────┤
│ free head ┼──┐ │ │ vacant │
├───────────┤ │ │ ╞══════════╡
│ page #2 │ │ │ │ next │
└───────────┘ │ │ ├──────────┤ EBR-protected
... │ │ │generation│ container
... │ │ ├──────────┤ ┌───────────┐
┌───────────┐ │ │ │ occupied ├─────►│ strong │
│ page #M-1 │ │ │ ╞══════════╡ │ reference │
└───────────┘ │ └─┼─ next │ │ counter │
└───►├──────────┤ ├───────────┤
(pages are │generation│ │ │
lazily ├──────────┤ │ value │
allocated) │ vacant │ │ │
└──────────┘ └───────────┘
每个分片的第一页的大小总是2的幂，并且在第一页之后添加的每一页都比前一页大两倍
pages slots capacity
┌────┐ ┌─┬─┐
│ #0 ├───▶ │x│ 1IPS
├────┤ ├─┼─┼─┬─┐
│ #1 ├───▶ │x│x│ │ 2IPS
├────┤ ├─┼─┼─┼─┼─┬─┬─┬─┐
│ #2 ├───▶ │x│ │x│x│x│ │ │ 4IPS
├────┤ ├─┼─┼─┼─┼─┼─┼─┼─┼─┬─┬─┬─┬─┬─┬─┬─┐
│#M-1├───▶ │ │x│ │x│x│x│ │ │x│ │x│x│x│ │ │ 8IPS
└────┘ └─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘
其中
IPS是Config::INITIAL_PAGE_SIZE（默认为32）M是Config::MAX_PAGES（默认为27）x是占用槽位
Key结构
Key Structure (64b)
┌──────────┬────────────┬───────────┐
│ reserved │ generation │ page+slot │
│ ≤32b │ ≤32b │ ≤32b │
│ def=0b │ def=32b │ def=32b │
└──────────┴────────────┴───────────┘
请查看Config文档以了解如何配置这些部分。
依赖关系
~0.1–25MB
~339K SLoC