node_replication/
lib.rs

1// Copyright © 2019-2020 VMware, Inc. All Rights Reserved.
2// SPDX-License-Identifier: Apache-2.0 OR MIT
3
4//! Node Replication (NR) is a library which can be used to implement a
5//! concurrent version of any single threaded data structure. It takes in a
6//! single threaded implementation of said data structure, and scales it out to
7//! multiple cores and NUMA nodes by combining three techniques: reader-writer
8//! locks, operation logging and flat combining.
9//!
10//! # How does it work
11//! To replicate a single-threaded data structure, one needs to implement the
12//! [Dispatch](trait.Dispatch.html) trait for it. The following snippet
13//! implements [Dispatch](trait.Dispatch.html) for
14//! [HashMap](https://doc.rust-lang.org/std/collections/struct.HashMap.html)
15//! as an example. A complete example
16//! (using [Replica](struct.Replica.html) and [Log](struct.Log.html)) can be found in the
17//! [examples](https://github.com/vmware/node-replication/tree/master/examples/hashmap.rs)
18//! folder.
19//!
20//! ```
21//! use node_replication::Dispatch;
22//! use std::collections::HashMap;
23//!
24//! /// The node-replicated hashmap uses a std hashmap internally.
25//! pub struct NrHashMap {
26//!    storage: HashMap<u64, u64>,
27//! }
28//!
29//! /// We support a mutable put operation on the hashmap.
30//! #[derive(Debug, PartialEq, Clone)]
31//! pub enum Modify {
32//!    Put(u64, u64),
33//! }
34//!
35//! /// We support an immutable read operation to lookup a key from the hashmap.
36//! #[derive(Debug, PartialEq, Clone)]
37//! pub enum Access {
38//!    Get(u64),
39//! }
40//!
41//! /// The Dispatch traits executes `ReadOperation` (our Access enum)
42//! /// and `WriteOperation` (our Modify enum) against the replicated
43//! /// data-structure.
44//! impl Dispatch for NrHashMap {
45//!    type ReadOperation = Access;
46//!    type WriteOperation = Modify;
47//!    type Response = Option<u64>;
48//!
49//!    /// The `dispatch` function applies the immutable operations.
50//!    fn dispatch(&self, op: Self::ReadOperation) -> Self::Response {
51//!        match op {
52//!            Access::Get(key) => self.storage.get(&key).map(|v| *v),
53//!        }
54//!    }
55//!
56//!    /// The `dispatch_mut` function applies the mutable operations.
57//!    fn dispatch_mut(
58//!        &mut self,
59//!        op: Self::WriteOperation,
60//!    ) -> Self::Response {
61//!        match op {
62//!            Modify::Put(key, value) => self.storage.insert(key, value),
63//!        }
64//!    }
65//! }
66//! ```
67#![no_std]
68#![cfg_attr(
69    feature = "unstable",
70    feature(new_uninit, get_mut_unchecked, negative_impls)
71)]
72
73#[cfg(test)]
74extern crate std;
75
76extern crate alloc;
77extern crate core;
78
79extern crate crossbeam_utils;
80
81#[macro_use]
82extern crate log as logging;
83
84#[macro_use]
85extern crate static_assertions;
86
87mod context;
88mod log;
89mod replica;
90
91#[cfg(not(loom))]
92#[path = "rwlock.rs"]
93pub mod rwlock;
94#[cfg(loom)]
95#[path = "loom_rwlock.rs"]
96pub mod rwlock;
97
98pub use crate::log::{Log, MAX_REPLICAS_PER_LOG};
99pub use replica::{Replica, ReplicaToken, MAX_THREADS_PER_REPLICA};
100
101use core::fmt::Debug;
102
103/// Trait that a data structure must implement to be usable with this library.
104///
105/// When this library executes a read-only operation against the data structure,
106/// it invokes the `dispatch()` method with the operation as an argument.
107///
108/// When this library executes a write operation against the data structure, it
109/// invokes the `dispatch_mut()` method with the operation as an argument.
110pub trait Dispatch {
111    /// A read-only operation. When executed against the data structure, an operation
112    /// of this type must not mutate the data structure in anyway. Otherwise, the
113    /// assumptions made by this library no longer hold.
114    type ReadOperation: Sized + Clone + PartialEq + Debug;
115
116    /// A write operation. When executed against the data structure, an operation of
117    /// this type is allowed to mutate state. The library ensures that this is done so
118    /// in a thread-safe manner.
119    type WriteOperation: Sized + Clone + PartialEq + Debug + Send;
120
121    /// The type on the value returned by the data structure when a `ReadOperation` or a
122    /// `WriteOperation` successfully executes against it.
123    type Response: Sized + Clone;
124
125    /// Method on the data structure that allows a read-only operation to be
126    /// executed against it.
127    fn dispatch(&self, op: Self::ReadOperation) -> Self::Response;
128
129    /// Method on the data structure that allows a write operation to be
130    /// executed against it.
131    fn dispatch_mut(&mut self, op: Self::WriteOperation) -> Self::Response;
132}
133
134#[cfg(doctest)]
135mod test_readme {
136    macro_rules! external_doc_test {
137        ($x:expr) => {
138            #[doc = $x]
139            extern "C" {}
140        };
141    }
142
143    external_doc_test!(include_str!("../README.md"));
144}
node_replication/lib.rs

node_replication/
lib.rs
