Command-Query-Separation and multithreading safe interfaces

Question

I like the command query separation pattern (from OOSC / Eiffel - basically you either return a value or you change the state of the class - but not both). This makes reasoning about the class easier and it is easier to write exception safe classes.

Now, with multi threading, I run into a major problem: the separation of the query and the command basically invalidates the result from the query as anything can happen between those 2.

So my question is: how do you handle command query separation in an multi-threaded environment?

---

Clarification example:

A stack with command query separation would have the following methods:

• push (command)
• pop (command - but does not return a value)
• top (query - returns the value)
• empty (query)

The problem here is - I can get empty as status, but then I can not rely on top really retrieving an element since between the call of empty and the call of top, the stack might have been emptied. Same goes for pop & top. If I get an item using top, I can not be sure that the item that I pop is the same.

This can be solved using external locks - but that's not exactly what I call threadsafe design.

Answer 1

With multithreading, you just can't separate queries and commands, unless you have an external lock which serializes calls.

The usual approach looks like this:

// query + command
// moves value at top into external thread-local storage `value`
// may fail and return `false`
bool ThreadSafeStack::try_pop(Value& value) 
{
    lock_guard guard(m_lock); // or `using(m_lock)`, `with m_lock:`

    if (m_stack.empty())
       return false;

    value = m_stack.top();
    m_stack.pop();
    return true;
}

But, you can use a hack: you can turn value into a member of the class.
Assume you have a data structure like this:

struct StackAndLock {
   Stack stack;
   Mutex lock;
}; 

Then you can create a ThreadSafeStack class:

class ThreadSafeStack
{
    Stack& m_stack;
    Mutex& m_lock;

    Value m_value;
public:
    ThreadSafeStack(StackAndLock& stackAndLock);

    void push(Value value); // command
    bool try_pop() // command, may fail
    {
        ...
        m_value = m_stack.top();
    }
    Value get_last() { return m_value; } // query
    bool empty(); // query
};

So you have one shared StackAndLock object, and multiple ThreadSafeStack objects, one per thread:

void thread_proc(StackAndLock& bundle)
{
     ThreadSafeStack stack(bundle);

     ...
     if (stack.try_pop())
     {
         ... stack.get_last() ...
     }
}

I can't say that it's such a great idea, but definitely it is Command-Query separation.

Answer 2

there are 2 main approaches

1. external read/write locks as I said in the comments

2. "failable" commands like the classic CompareAndSwap

   bool CaS(from,to){
       if(from==state){
           state=to;
           return true;
       }
       return false;
   }
   

   however this can result very large functions for non-trivial problem flow

Answer 3

Your comments have helped. I'll try a new perspective. New answer has two parts: 1. Some commands must return success or failure. I understand that traditionally commands should not return values, but things get really awkward if you don't allow at least a boolean success result. 2. Documentation. You must explain to users of your API that a value returned from a query simply means that value existed at the time of the query, and it may have been invalidated immediately after the query. Thus a query can be considered an absolute fact about the past, but only a hint about the future.

For the stack example, the API might look like,

• push(value) (command, always succeeds)
• pop(value) (command, succeeds if value could be popped)
• top() (query, returns two things: top value and empty boolean. value is undefined if empty = true)

That's not a conventional pop command, but a pop command with no value specified or with no success result would be pointless. It would be a command to make a change to the stack without the caller having any way to know for sure what change, if any, was made. Also, top() must return some status about whether there was a top value.

Your implementation of the API is responsible for data synchronization. "External" locking (I wasn't appreciating what you meant by external before) is not required by users of your API. In your implementation, you can use whatever synchronization is available to you in your language.

Answer 4

Short answer is use synchronization for all access to shared data.

Locks allow synchronization and using locks is a threadsafe design. It's not a design that does the locking for you or that prevents errors in your locking code, but it is a design that allows you to write correct multithreaded code.

Note that synchronization isn't just needed to sequence commands. A query can return a corrupt value, or a command can corrupt your data structure. In a multithreaded situation, all accesses to shared data should be synchronized. Locking is a valid way to do this and Aybx's StackAndLock struct is a standard technique. There are lower-level techniques, such as CAS, but even with locks, you have to write code that uses the locks correctly. Higher level techniques involve using libraries (or better yet, languages) that implement things like STM, Actors, CSP, or other sorts of message passing.