concurrent-kv

License

concurrent-kv is licensed under the MIT license. See LICENSE for details.

lib.rs:

generic, thread safe, in-memory, key-value data store

As indicated by the name, the Library struct is the main export of this module. Some supporting types and traits are also exported.

The Library structure supports two operations: get and insert, which fill similar roles to their counter parts in the HashMap collection. get accepts a key and returns a value. insert updates provided key in the data store with the provided value.

The thread safety property of the Library is the result of wrapping multiple concurrency primitives; Arc, ArcCell, and Mutex.

Mutex and Arc are part of the standard library. We use mutex to prevent multiple writers from adding a new key simultaneously. Note: this is subtly, but significantly, different from preventing multiple insertions of the same key.

Insertion

There are two different scenarios to consider: inserting a new value under a new key and inserting a new value for an existing key and

New value under new key

Inserting a value with a new key requires allocating additional space in the HashMap and potentially rearranging the underlying data. To prevent consistency errors the Library has an internal Mutex (Library.insert_mutex) which must be obtained before inserting a key.

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());

New value under existing key

Since the key already exists the HashMap does not need to allocate any additional storage (we are just swapping the contents of an ArcCell). So we can short-circuit the insertion process, and thus skipping lock acquisition, by providing a reference to the ArcCell and swapping directly.

This tradeoff for performance is what introduces the "Last Writer Wins" behavior for multiple insertions to the same key.

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 is provided by the crossbeam crate. The naming and documentation are atrocious, so we attempt to provide an explaination here.

As the figure below attempts to depict, The defining feature of this type is the ability to swap out the contents of the heap allocated value (i.e. Cell) atomically. So a more accurate name would be 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

Caveats

It is up to the user of Library to ensure that only a single update to an individual key happens concurrently. Otherwise the Library will default to the "Last Writer Wins" conflict resolution strategy (hardly ever the desired behavior from an end user perspective).