node-replication

基于针对NUMA架构的黑色盒并发数据结构的Node Replication库。

此库可以用来实现任何单线程数据结构的并发版本：它接受该数据结构的一个单线程实现，并通过结合三种技术（读者-写者锁、操作日志和扁平组合）将其扩展到多个核心和NUMA节点。

它是如何工作的

为了复制一个单线程数据结构，需要实现Dispatch（来自node-replication）。例如，我们为来自std的单线程HashMap实现了Dispatch。

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

/// The node-replicated hashmap uses a std hashmap internally.
#[derive(Default)]
struct NrHashMap {
    storage: HashMap<u64, u64>,
}

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

/// We support an immutable read operation to lookup a key from the hashmap.
#[derive(Clone, Debug, PartialEq)]
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),
        }
    }
}

完整示例（使用HashMap作为底层数据结构）可以在这里找到。要运行，请执行：cargo run --example hashmap

它的性能如何

该库通常可以让您的单线程实现比相同数据结构的细粒度锁定或无锁实现表现得更好或具有竞争力。

如果以下条件成立，它工作得特别出色：

• 您的数据结构超过系统L3缓存的容量（如果您的数据始终可以保留在缓存中，复制可能不会带来任何收益）。
• 所有线程都需要发出混合的、可变和不可变操作（如果不是，像RCU这样的替代技术可能表现更好）。
• 您有足够的DRAM来利用复制（即，通常最好为每个NUMA节点使用一个副本，这意味着您的原始内存占用会乘以系统中的NUMA节点数量）。

以下基准测试使用Rust的哈希表，并采用上文提到的Dispatch实现（nr），将其与来自crates.io（chashmap、dashmap、flurry）的并发哈希表实现、由RwLock（std）保护的HashMap以及urcu进行了比较。

图表显示了使用预先填充了6700万个条目（8字节键和值）的哈希表进行的基准测试，并使用均匀的键分布进行操作。在左侧图表中，显示了不同的写入比率（0%、10%和80%）。在右侧图表中，我们使用192个线程改变写入比率（x轴）。系统有4个NUMA节点，因此使用4个副本（在x=96时，每24个核心就添加一个副本）。在x=96之后，剩余的超线程将被使用。

cargo build

cargo build --features unstable

node-replication = "*"