Crate cnr[][src]

Expand description

Concurrent Node Replication (CNR) is a library which can be used to implement a NUMA-aware version of any concurrent data structure. It takes in 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 the Dispatch trait for it. To map the operation to a log, each operation (ReadOperation and WriteOperation) needs to implement LogMapper trait. The following snippet implements Dispatch for concurrent HashMap as an example. A complete example (using Replica and Log) can be found in the examples folder.

use cnr::Dispatch;
use cnr::LogMapper;
use chashmap::CHashMap;

/// 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),
}

/// Application developer implements LogMapper for each mutable operation.
/// It is used to map the operation to one of the many logs. Commutative
/// operations can map to same or different log and conflicting operations
/// must map to same log.
impl LogMapper for Modify {
   fn hash(&self, nlogs: usize, logs: &mut Vec<usize>) {
      logs.clear();
      match self {
         Modify::Put(key, _val) => logs.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),
}

/// Application developer implements LogMapper for each immutable operation. It
/// is used to map the operation to one of the many log. Commutative operations
/// can go to same or different log and conflicts operations must map to same log.
impl LogMapper for Access {
   fn hash(&self, nlogs: usize, logs: &mut Vec<usize>) {
      logs.clear();
      match self {
         Access::Get(key) => logs.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),
       }
   }
}

Structs

Log

A log of operations that is typically accessed by multiple Replica.

Replica

An instance of a replicated data structure. Uses one or more shared logs to scale operations on the data structure across cores and processors.

ReplicaToken

A token handed out to threads registered with replicas.

Constants

MAX_REPLICAS_PER_LOG

The maximum number of replicas that can be registered with the log.

MAX_THREADS_PER_REPLICA

The maximum number of threads that can be registered with a replica. If more than this number of threads try to register, the register() function will return None.

Traits

Dispatch

Trait that a data structure must implement to be usable with this library.

LogMapper

Every data structure must implement LogMapper trait for ReadOperation and WriteOperation.