Initialize costly value in map with minimum lock contention (C++)

Question

Suppose we have a map that is shared between multiple threads. It represents a node in some hierarchical structure (say, a directory in a file system) that is stored on disk. Constructing a Value is expensive both in time and in memory. This is the classic 'initialize on demand' problem, with a twist: we're initializing values in a map when there's lookup request, but we don't want to lock the entire map while we're doing this in order to let other threads access already constructed values. In this application, lookups of existing Values will be much more common then non-existing ones.

Attempt 1: Grab write lock on map, check for presence of Key, return if present, otherwise, construct Value, put in map.

Evaluation: This prevents other threads from accessing the map while we're constructing the Value. Since reads are very common and very fast, this will manifest itself as an ugly jump in latency: not good.

Attempt 2: Grab read lock on map, check for presence of Key, return if present, otherwise release read lock, construct Value, grab write lock, check for presence, if not present, put in map, if present delete newly constructed Value.

Evaluation: Now we don't incur the jump in read latency, but we might end up needlessly constructing several in memory representations of the same Value (when multiple threads try to look up the same yet-unconstructed Value simultaneously). Problem is, we don't want this: these Values are really expensive to create. Besides, they might start firing events or doing I/O, which means that now we have to deal with a design that allows ephemeral yet heavyweight Value instances to exist: an additional headache better avoided.

Attempt 3: Use two-levels of locks. Grab read lock on map, lookup Key, return if present, otherwise, release read lock on map, grab write lock on map, check for placeholder, grab placeholder's read lock, if present, otherwise, create placeholder, grab its write lock, insert into map, release write lock on map, create Value, replace placeholder with Value, release placeholder's write lock.

Evaluation: Inserting a placeholder into the map while constructing the Value guarantees that only one thread will attempt it, thus addressing the problems of Attempt 2. However, this design leaves open the question: what form this placeholder should take? The answer is not trivial. First, if it contains a lock and threads wait on it, it becomes hard to delete it (How do you know nobody's holding the placeholder's lock? You can grab it, sure, but then you are holding it so, again, you cannot delete it). Second, there can be lookups of Keys for which no Value exists on disk. If we insert a placeholder for every lookup attempt (even for ones that will eventually fail) then who's going to clean these up? Finally, with two levels of locks, the code becomes quite ugly: we first grab read lock, check, then acquire write lock, re-check, and we need to do this both at the map level, and the individual placeholder level (easy to create deadlocks, I can attest to it).

This little baby keeps popping up and I can't seem to find an elegant solution. Attempt 3 is the closest I got to satisfying my performance conditions, but it's ugly and error prone once you get down to the dirty details. I would really appreciate any insights or suggestions.

Answer 1

It appears the goal is enable fast turnaround on lookup of existing objects at the expense of creating new objects. Here is a solution which will do this for you.

You need to maintain two maps in memory, both will ultimately have the same contents. You'll also need a mutex for writing and reading: - curReadMap * - curWriteMap * - writeMutex - readMutex

Those two pointers are important, we'll be swapping those. Now to read a value you have (rough pseudo-code):

  lock( readMutex )
  value = checkValueIn( curReadMap, key )
  unlock()
  if( value ) return value

If you don't find the value then you can enter the writing section

  lock( writeMutex )
  value = checkValueIn( curWriteMap, key ) //double check now
  if( value ) return value

  value = createNewValue()
  putIn( curWriteMap, key, value )

  lock( readMutex )
  swap( curWriteMap, curReadMap )
  unlock( readMutex )

  putIn( curWriteMap, key, value ) //update old map now as well
  unlock( writeMutex )

In this scheme the typical reader bears only the cost of the one mutex lock and a lookup in the map. They only ever bear creation cost if the object is not found. The swapping of the map pointers also ensures a very minimal lock time on the readMutex.

Answer 2

Your trouble with scheme #3 is how to keep track of the placeholder objects. If you're willing to give up a bit of parallelism, you can do it more easily - allocate a single lock which will serialize value creation with each map. Then it goes:

lookup(map, key):
  1. Grab read lock on map
  2. lookup key in map, unlock & return if present
  3. grab lock on map.create_serializer
  4. lookup key in map, unlock & return if present
  5. release read lock on map
  6. create value for key
  7. grab write lock on map
  8. insert (key,value) into map
  9. release write lock on map
 10. release lock on map.create_serializer

The create_serializer makes sure that no more than one thread is creating objects to put into this map at any one time. Multiple threads looking up the same missing key at the same time will serialize at step 3 - the first will continue to build the value and the rest will find that value already built in step 4.

This will (unnecessarily) serialize different value creations for the same map, but otherwise satisfies your criteria.