Crate node_replication

Expand description

Node Replication (NR) is a library which can be used to implement a concurrent version of any single threaded data structure. It takes in a single threaded implementation of said data structure, and scales it out to multiple cores and NUMA nodes by combining three techniques: reader-writer locks, operation logging and flat combining.

§How does it work

To replicate a single-threaded data structure, one needs to implement the Dispatch trait for it. The following snippet implements Dispatch for HashMap as an example. A complete example (using Replica and Log) can be found in the examples folder.

use node_replication::Dispatch;
use std::collections::HashMap;

/// The node-replicated hashmap uses a std hashmap internally.
pub struct NrHashMap {
   storage: HashMap<u64, u64>,
}

/// We support a mutable put operation on the hashmap.
#[derive(Debug, PartialEq, Clone)]
pub enum Modify {
   Put(u64, u64),
}

/// We support an immutable read operation to lookup a key from the hashmap.
#[derive(Debug, PartialEq, Clone)]
pub enum Access {
   Get(u64),
}

/// The Dispatch traits executes `ReadOperation` (our Access enum)
/// and `WriteOperation` (our Modify enum) against the replicated
/// data-structure.
impl Dispatch for NrHashMap {
   type ReadOperation = Access;
   type WriteOperation = Modify;
   type Response = Option<u64>;

   /// 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(
       &mut self,
       op: Self::WriteOperation,
   ) -> Self::Response {
       match op {
           Modify::Put(key, value) => self.storage.insert(key, value),
       }
   }
}

Modules§

rwlock: The distributed readers-writer lock used by the replica.

Structs§

Log: A log of operations that is typically accessed by multiple Replica.
Replica: An instance of a replicated data structure. Uses a shared log 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§