Key-level guarantees

[viniciusd]

Thanks for the great work! It is very convenient to have a drop-in replacement of std::collections::HashMap that works concurrently.

What are the thread-safety guarantees at the key-level offered by dashmap?

Right at dashmap::DashMap's documentation, I see:

DashMap tries to be very simple to use and to be a direct replacement for RwLock<HashMap<K, V, S>>. To accomplish this, all methods take &self instead of modifying methods taking &mut self. This allows you to put a DashMap in an Arc<T> and share it between threads while being able to modify it.

Which makes me think: okay, great, there is concurrency-control when we are accessing the hashmap as a whole.

What about at the key level?

There is a deadlock warning for some APIs referring to accessing dashmap twice in the same scope, such as:

Locking behaviour: May deadlock if called when holding any sort of reference into the map.

However, if I have two threads, and both of them concurrently call:

dashmap.get(key)

Will one of them get the reference to the key and the other one lock until the first thread frees the reference?
Or do we have a key-level RwLock behavior? I.e., multiple threads can use .get(key) without blocking, but only one .get_mut(key) can be called?

If only one .get_mut(key) can be called, what happens if two threads try to call it concurrently? Will the call of the second thread wait until the first thread releases the reference, or will we be in dangerous terrain?

Same question applies to the entry API. After all, it is also about dashmap::mapref::one::RefMut vs dashmap::mapref::one::Ref

Browsing around the source-code, I see RefMut keeps a lock_api::MappedRwLockWriteGuard (conversely, Ref uses the ReadGuard).

I am not very proficient with the lock_api, but it looks like the guards are tied to the shad's RwLock in the hashmap? Does it mean two or more threads getting mutable references to different keys in the same shard will still block each other?

[Chaoses-Ib]

If #74 is not outdated, the answer is no, there are no key-level guarantees. The lock seems to be at the block level. Since one cannot be sure about which block the key is in, it should be considered a (probabilistic) table-level lock.

[xacrimon]

This is indeed correct. #74 still holds.