是否有可能线程之间共享一个HashMap没有锁定整个HashMap的？

Question

我想有线程之间共享的结构。该结构有许多领域是决不会被修改和HashMap，这就是生活。我不想锁定整个HashMap单个更新/删除，所以我HashMap看起来像HashMap<u8, Mutex<u8>>。这工作，但它没有任何意义，因为该线程将反正锁定整个地图。

下面是这个工作版本，不包含线程;我不认为，对于例如是必要的。

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，或类似的东西）。

Answer 1

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

在以往的工作中，我使用了RwLock<HashMap<K, Mutex<V>>>。当插入值，哈希，你会得到一个短周期的排它锁。的剩下的时间，你可以有读者锁定在HashMap，从而给定元素的多个线程。如果他们需要变异数据，他们可以得到的Mutex独占访问。

下面是一个例子：

use std::collections::HashMap;
use std::sync::{Mutex, RwLock, Arc};
use std::thread;
use std::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");

        // Assume that no other thread will be inserting the same key,
        // otherwise we need to recheck to see if it exists
        thread::sleep(Duration::from_millis(50));
        map.insert(id, Mutex::new(0));
        // Let the loop start us over to try again
    }
}

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

该解决方案也不是没有问题，但是。当有一个巨大的争夺是一个主锁的数量，得到一个写锁可能需要一段时间，完全杀死并行。

我经常提倡执行某种聪明的算法。例如，你可以旋转起来各有各的HashMap N个线程。然后，分片当中的工作。对于上面的简单的例子，你可以使用id % N_THREADS，例如。也有依赖于你的数据分片复杂的方案。

作为围棋做传福音的工作：不要通过共享内存通信;相反，通过通信共享内存。

Answer 2

也许你要考虑rust-evmap：

无锁，最终一致，并发多值映射。

权衡的是最终一致性：读者看不出变化，直到作家刷新地图。刷新是原子和作家决定何时做和暴露的新数据，以飨读者。