Mutex map data structure

Question

the problem

• I have a directory D that I want to put (K, V) pairs into
• void save(K, V) saves file name K with contents V to directory D
  • Has "fire and forget" semantics - function may return before it actually saves the file to disk
• Directory D is a field of the class C defining the save function
• Calls to void save(K, V) should run concurrently
  • Using tbb::task for concurrency
  • No two file writes for the same key can be run concurrently
  • That is, if two threads call save(K, V1) and save(K, V2) at the same time, the result should be a file in D named K that has contents equal to either V1 or V2 (but not corrupted)

planned approach

• Pick a hash function H that maps K to a std::size_t
• Pick an integer N > 1
• Give class C an array of mutexes tbb::mutex mutex_map[N]
• void save(K, V) waits to acquire a lock on mutex_map[H(K) % N] to perform its file write

questions

• Is this a sensible approach?
• Can you think of an alternative that might have advantages over this?
• Is there some tbb data structure that already encapsulates this concept of a mutex map?
  • Think something like a std::map<TKey, tbb::mutex> but where the interface gives the appearance of every possible key simultaneously having an associated mutex.

Answer 1

Yes, that is a very sensible approach. I can not think of an alternative (except for trivial alternatives like using std::mutex instead of tbb:mutex.)

You should pick N large compared to the number of mutexes that you think will be simultaneously locked. The birthday paradox says that if you expect to have k threads simultaneously trying to lock then the probability of having at least one spurious hash collision is greater than 50% until you get N > o(k²).

I don't know of a tbb data structure that is like a map of mutexes. But internally I believe that tbb::malloc uses the trick you are suggesting (threads are randomly assigned to independent malloc data-structures), and the tbb::concurrent_hash_map is implemented such that there is a mutex per hash-bucket.