CNR (Concurrent Node Replication) library is an extension over regular NR.
Unlike NR, this library is used to implement a NUMA-aware concurrent version of a concurrent or partitioned data structure. It takes a concurrent implementation of said data structure, and scales it out to multiple cores and NUMA nodes by combining three techniques: commutativity based work partitioning, operation logging, and flat combining.
To replicate a concurrent data structure, one needs to implement Dispatch and
LogMapper (from cnr). LogMapper implementation dictates the work
partitioning across multiple logs for concurrent execution.
LogMapper implementation is used to map an operation to a log. Two commutative
operations can be mapped to same or different log; however, two conflicting
operations must map to the same log. As an example, we implement Dispatch for
the CHashMap and LogMapper for the
supported operations.
```rust
/// The replicated hashmap uses a concurrent hashmap internally.
pub struct CNRHashMap {
storage: CHashMap
/// We support a mutable put operation on the hashmap.
pub enum Modify { Put(usize, usize), }
/// This LogMapper implementation distributes the keys amoung multiple logs
/// in a round-robin fashion. One can change the implementation to improve the
/// data locality based on the data sturucture layout in the memory.
impl LogMapper for Modify {
fn hash(&self, _nlogs: usize, logs: &mut Vec
/// We support an immutable read operation to lookup a key from the hashmap.
pub enum Access { Get(usize), }
/// Access follows the same operation to log mapping as the Modify. This
/// ensures that the read and write operations for a particular key go to
/// the same log.
impl LogMapper for Access {
fn hash(&self, nlogs: usize, logs: &mut Vec
/// The Dispatch traits executes ReadOperation (our Access enum)
/// and WriteOperation (our Modify enum) against the replicated
/// data-structure.
impl Dispatch for CNRHashMap {
type ReadOperation = Access;
type WriteOperation = Modify;
type Response = Option
/// The dispatch function applies the immutable operations.
fn dispatch(&self, op: Self::ReadOperation) -> Self::Response {
match op {
Access::Get(key) => self.storage.get(&key).map(|v| *v),
}
}
/// The dispatch_mut function applies the mutable operations.
fn dispatch_mut(&self, op: Self::WriteOperation) -> Self::Response {
match op {
Modify::Put(key, value) => self.storage.insert(key, value),
}
}
}
```
The full example (using HashMap as the underlying data-structure) can be found
here. To run, execute: cargo run --example hashmap
The library currently requires a nightly rust compiler (due to the use of
new_uninit, and get_mut_unchecked, negative_impls API). The library works
with no_std.
bash
rustup toolchain install nightly
rustup default nightly
cargo build
As a dependency in your Cargo.toml:
toml
cnr = "*"
The code should currently be treated as an early release and is still work in progress. In its current form, the library is only known to work on x86 platforms (other platforms will require some changes and are untested).
There are a series of unit tests as part of the implementation and a few integration tests that check various aspects of the implementation using a stack.
You can run the tests by executing: cargo test
The benchmarks (and how to execute them) are explained in more detail in the benches folder.