1 unstable release
0.1.0 | Jun 23, 2021 |
---|
#818 in Concurrency
140KB
2K
SLoC
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.
Dependencies
~2MB
~41K SLoC