Concurrent Node Replication

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.

How does it work

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.

/// The replicated hashmap uses a concurrent hashmap internally.
pub struct CNRHashMap {
   storage: CHashMap<usize, usize>,
}

/// We support a mutable put operation on the hashmap.
#[derive(Debug, PartialEq, Clone)]
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<usize>) {
      logs.clear();
      match self {
         Modify::Put(key, _val) => log.push(*key % nlogs),
      }
   }
}

/// We support an immutable read operation to lookup a key from the hashmap.
#[derive(Debug, PartialEq, Clone)]
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<usize>) {
      logs.clear();
      match self {
         Access::Get(key) => log.push(*key % nlogs),
      }
   }
}

/// 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<usize>;

   /// 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

Compile the library

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.

rustup toolchain install nightly
rustup default nightly
cargo build

As a dependency in your Cargo.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).

Testing

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

Benchmarks

The benchmarks (and how to execute them) are explained in more detail in the benches folder.