Where to implement thread-safety logic for my queue data structure?

Question

I will immediately confess that I do very little multithreading, so questions of style and organization in this domain a little fresh to me.

I've written a data structure (in Python, if that matters) which implements a special kind of a queue. I'd like to use this queue to pass messages between threads. Currently, the only logic I have has nothing to do with threads, and simply implements the "special sauce" of organizing messages in this queue.

I like having this queue as a data structure that has nothing to do with threads, just like any other data structure. However, I need to use mutexes, condition variables, etc. to implement the thread safety logic. The question is, where does this logic go?

Do I write a class, say, SpecialQueueConcurrent derived from SpecialQueue? Do I write a class that wraps SpecialQueue instead of deriving from it? Do I provide an option to make it concurrent in the constructor?

How is this usually done?

Answer 1

It depends on the use-cases of the data structure, and any restrictions of that use you need to comply to (about that latter).

The use-cases

There are a few use cases that could determine the correct approach in choosing or implementing a concurrent data structure yourself. You need to consider:

• The concurrency implementation supported by the structure:

  • Strict locking could guarantee supreme data consistency at the price of locks and can create performance bottlenecks.
  • Lock-free concurrent collections are special implementations that work without locks, but have (in most cases acceptable) possibility of one thread not reading the changes of the other. These are not the same as the case of using a standard collection without locks, as the lock-free collection would not allow the collection itself to become corrupted. With lock-free collections, the disadvantage is that multiple threads could perform the same operation, while only one of them would actually be taken into account. Depending on the context, this is often justified and acceptable, for these collections are introducing the best performance in concurrent processing, compared to lock usage, such repetitive processing situations are relatively rare to occur, and would usually not lead to corruption of the entire data/state.
  • Independent buckets that have their own locks is another approach that attempts to allow simultaneous use of the collection. In this approach the collection is internally split into multiple buckets with their own locks, that can be used by multiple threads. An example is a concurrent dictionary that would use internally an array of dictionaries. Based on the hash-code of the key the dictionary would decide which child dictionary to use from the corresponding thread, and will limit the lock to that child dictionary only. Another thread that would target another child dictionary will not be blocked. Alternatively, an array of lock objects can be used along a single container with quite the same effect. The problem with this approach is that the collection itself decides which bucket the current thread works on (and locks), so you do not have control of whether certain operations will really be concurrent (if manipulating by multiple buckets) or not (if they appear to affect the same bucket).

• The number of threads dealing with a single instance of the structure simultaneously. This will determine the possibility of potential simultaneous uses that could cause blocking.

• The ratio between read and write operations. This could help you decide which concurrent behavior from the listed above is suitable. For instance a collection that is more often being read from, than updated, would be more performant if it has a lock-free implementation, or if a read-write lock is used. The read-write lock is a special lock that allows you to control if it should block reads when a write is being performed, but to allow simultaneous reads.
• The importance of data consistency within the structure. This is affected by the different approaches of such structure's implementation, as discussed above.

The restrictions

By restrictions I am referring to the code you are using. If you interact with a 3rd party API, or are somewhat restricted by the type of collection/structure you have to use (if you must pass it to the API's method), or you are enforced to implement certain interface, you need to find out the potential uses of this code and a suitable implementation that will fit. Most existing concurrent collection implementations would be compatible with at least the iterable and collection interfaces though.

Implementation notes

If you are going to base your structure on an existing collection, I recommend wrapping it, rather than using inheritance. Wrapping will guarantee you won't miss a method that needs to be synchronized, and will give you freedom to choose your locking behavior. You can always implement a standard collection interface in order to make your collection usable by other APIs (see restrictions section above)