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