multithreading - 是否可以在不锁定整个 HashMap 的情况下在线程之间共享一个 HashMap？

Question

我想在线程之间有一个共享结构。该结构有许多从未修改过的字段和一个 HashMap ，这是。我不想锁定整个 HashMap对于单个更新/删除，所以我的 HashMap看起来像 HashMap<u8, Mutex<u8>> .这行得通，但没有任何意义，因为线程无论如何都会锁定整个 map 。

这是这个工作版本，没有线程；我认为该示例没有必要这样做。

use std::collections::HashMap;
use std::sync::{Arc, Mutex};

fn main() {
    let s = Arc::new(Mutex::new(S::new()));
    let z = s.clone();
    let _ = z.lock().unwrap();
}

struct S {
    x: HashMap<u8, Mutex<u8>>, // other non-mutable fields
}

impl S {
    pub fn new() -> S {
        S {
            x: HashMap::default(),
        }
    }
}

Playground

这有可能吗？我在文档中遗漏了什么明显的东西吗？

我一直在努力让它工作，但我不确定如何。基本上我看到的每个例子都有一个 Mutex (或 RwLock 或类似的东西)保护内在值(value)。

Answer 1

我不明白你的请求怎么可能，至少在没有一些非常聪明的无锁数据结构的情况下是不可能的；如果多个线程需要插入散列到同一位置的新值，会发生什么情况？

在之前的工作中，我使用了 RwLock<HashMap<K, Mutex<V>>> .当向散列中插入一个值时，您将获得一个短时间的独占锁。其余时间，您可以拥有多个线程，并锁定 HashMap。从而对给定的元素。如果他们需要改变数据，他们可以获得对 Mutex 的独占访问权。 .

这是一个例子:

use std::{
    collections::HashMap,
    sync::{Arc, Mutex, RwLock},
    thread,
    time::Duration,
};

fn main() {
    let data = Arc::new(RwLock::new(HashMap::new()));

    let threads: Vec<_> = (0..10)
        .map(|i| {
            let data = Arc::clone(&data);
            thread::spawn(move || worker_thread(i, data))
        })
        .collect();

    for t in threads {
        t.join().expect("Thread panicked");
    }

    println!("{:?}", data);
}

fn worker_thread(id: u8, data: Arc<RwLock<HashMap<u8, Mutex<i32>>>>) {
    loop {
        // Assume that the element already exists
        let map = data.read().expect("RwLock poisoned");

        if let Some(element) = map.get(&id) {
            let mut element = element.lock().expect("Mutex poisoned");

            // Perform our normal work updating a specific element.
            // The entire HashMap only has a read lock, which
            // means that other threads can access it.
            *element += 1;
            thread::sleep(Duration::from_secs(1));

            return;
        }

        // If we got this far, the element doesn't exist

        // Get rid of our read lock and switch to a write lock
        // You want to minimize the time we hold the writer lock
        drop(map);
        let mut map = data.write().expect("RwLock poisoned");

        // We use HashMap::entry to handle the case where another thread 
        // inserted the same key while where were unlocked.
        thread::sleep(Duration::from_millis(50));
        map.entry(id).or_insert_with(|| Mutex::new(0));
        // Let the loop start us over to try again
    }
}

这在我的机器上运行大约需要 2.7 秒，即使它启动了 10 个线程，每个线程等待 1 秒，同时保持对元素数据的独占锁。

但是，此解决方案并非没有问题。当对一个主锁存在大量争用时，获得写锁可能需要一段时间并完全破坏并行性。

在这种情况下，您可以切换到 RwLock<HashMap<K, Arc<Mutex<V>>>> .一旦你有了读锁或写锁，你就可以克隆 Arc的值(value)，返回它并解锁散列图。

下一步是使用像 arc-swap 这样的 crate ，它说:

Then one would lock, clone the [RwLock<Arc<T>>] and unlock. This suffers from CPU-level contention (on the lock and on the reference count of the Arc) which makes it relatively slow. Depending on the implementation, an update may be blocked for arbitrary long time by a steady inflow of readers.

The ArcSwap can be used instead, which solves the above problems and has better performance characteristics than the RwLock, both in contended and non-contended scenarios.

我经常提倡执行某种更智能的算法。例如，您可以启动 N 个线程，每个线程都有自己的 HashMap。 .然后您分片在它们之间工作。对于上面的简单示例，您可以使用 id % N_THREADS ， 例如。还有一些复杂的分片方案取决于您的数据。

由于 Go 在宣传方面做得很好:不要通过共享内存进行通信；相反，通过通信共享内存。