Searching for a lock-free possibility to swap two associative containers

Question

I'm trying to implement the feature toggle pattern. To do that, I load the contents of a configuration file containing the feature toggles into a map. After that, there is a function where you can check whether a feature toggle is set or not. Now, parts of our development want a function to re-initialize the map so that they can change the toggle while the application is running (edit the file, call re-initialize).

Since the toggle mechanism should be fast, I'd like to implement the fastest possible way to read the toggles. Re-initializing the map can be slow - that is no problem. Reading without writing would be thread-safe, but with the re-initialize function, I need to care about threading issues.

My current solution uses reader locks in the read function and exclusive locks in the write function. But my goal would be to live without locks in the read functions. Any ideas?

Regards Tobias

Answer 1

The only unsafe operations should be those that modify the structure of the tree. Simply updating the value in a node is safe. Therefore, when "re-initializing", simply visit each node in the "old" tree, and if the new configuration has no setting, either leave it untouched or change the value to an "unknown" state. If the new configuration has a setting for a node in the existing tree, simply update it and move on.

If you really, really need to be able to add new feature toggles on the fly (why?), you could make a second data structure which is just a dumb, flat list of "added" features, and only ever append there. Then, when a reader queries for a feature, look in the tree first (fast), and then if needed in the list (slow, but uncommon).

Finally, you could do something like "z buffering" where you keep two complete trees and a pointer to the "active" one. You only update the "inactive" one and then flip the pointer to make it active. This might require a simple reference counting operation when readers are using the active tree (so you don't update a second time while some readers exist on the old-old tree), but that should be inexpensive.