concurrent-kv

许可证

concurrent-kv 使用 MIT 许可证。有关详细信息，请参阅 LICENSE。

lib.rs:

通用的、线程安全的、内存中的键值数据存储

如名称所示，Library 结构体是该模块的主要导出项。一些支持类型和特性也被导出。

Library 结构体支持两种操作：get 和 insert，它们与 HashMap 集合中的对应操作类似。get 接受一个键并返回一个值。insert 使用提供的值更新数据存储中的提供的键。

Library 的线程安全特性是多重并发原语（Arc、ArcCell 和 Mutex）封装的结果。

Mutex 和 Arc 是标准库的一部分。我们使用互斥锁来防止多个写入者同时添加新键。注意：这微妙但显著地不同于防止对相同键的多次插入。

插入

有两种不同的场景需要考虑：在新的键下插入新值，以及在现有的键下插入新值。

新键下的新值

使用新键插入值需要在 HashMap 中分配额外的空间，并可能重新排列底层数据。为了防止一致性错误，Library 有一个内部的互斥锁（Library.insert_mutex），在插入键之前必须获得该锁。

use concurrent_kv::Library;

let lib: Library<String, i64> = Library::new();
lib.insert("qwerty".into(), 12345);
let val0 = lib.get("qwerty").unwrap();
lib.insert("asdfgh".into(), 67890);
let val1 = lib.get("asdfgh").unwrap();
assert_eq!(val0, 12345.into());
assert_eq!(val1, 67890.into());

现有键下的新值

由于键已经存在，HashMap 不需要分配任何额外的存储（我们只是交换 ArcCell 的内容）。因此，我们可以通过提供 ArcCell 的引用并直接交换来短路插入过程，从而跳过锁定获取。

这种为了性能而进行的权衡引入了“最后写入者胜出”的行为，即对同一键的多次插入。

use concurrent_kv::Library;
use std::sync::Arc;

let lib0: Arc<Library<String, i64>> = Library::new().into();
let val0 = lib0.get("abc");
assert_eq!(val0, None.into());
let lib1 = lib0.clone();
lib0.insert("abc".into(), 123);
let val123 = lib1.get("abc");
assert_eq!(val123, lib0.get("abc"));
assert_eq!(val0, None.into());
lib1.insert("abc".into(), 456);
let val456 = lib1.get("abc");
assert_eq!(val456, Some(456.into()));
assert_eq!(val123, Some(123.into()));

ArcCell

ArcCell 由 crossbeam 包提供。命名和文档糟糕透顶，所以我们在这里尝试提供解释。

如图所示，该类型的定义特性是能够原子地交换堆分配值的内容（即 Cell）。因此，一个更准确的名字可能是 AtomicCell。

         A ----> N
  A -\
  A ---> A ----> O
  A --/      /
           A-

         A -\ /- N
  A -\       X
  A ---> A -/ \- > O
  A --/       /
            A-

see: https://internals.rust-lang.org/t/atomic-arc-swap/3588

注意事项

确保单个键的更新只发生一次是 库 的用户的责任。否则，库 将默认采用“最后写入者获胜”的冲突解决策略（这通常不是最终用户期望的行为）。