Crate concurrent_kv [−] [src]
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.
Library structure supports two operations:
insert, which fill similar roles to
their counter parts in the
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.
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
Inserting a value with a new key requires allocating additional space in the
potentially rearranging the underlying data. To prevent consistency errors the
Library has an
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());
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 is provided by
the crossbeam crate. The naming and documentation are atrocious, so we attempt to provide an
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
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
It is up to the user of
Library to ensure that only a single update to an individual key happens concurrently.
Library will default to the "Last Writer Wins" conflict resolution strategy (hardly ever the
desired behavior from an end user perspective).