How to ensure that the messages will be enqueued in chronological order on multithreaded Asio io_service?

Question

Following Michael Caisse's cppcon talk I created a connection handler MyUserConnection which has a sendMessage method. sendMessage method adds a message to the queue similarly to the send() in the cppcon talk. My sendMessage method is called from multiple threads outside of the connection handler in high intervals. The messages must be enqueued chronologically.

When I run my code with only one Asio io_service::run call (aka one io_service thread) it async_write's and empties my queue as expected (FIFO), however, the problem occurs when there are, for example, 4 io_service::run calls, then the queue is not filled or the send calls are not called chronologically.

class MyUserConnection : public std::enable_shared_from_this<MyUserConnection> {
public:
  MyUserConnection(asio::io_service& io_service, SslSocket socket) :
      service_(io_service),
      socket_(std::move(socket)),
      strand_(io_service) {
  }

  void sendMessage(std::string msg) {
    auto self(shared_from_this());
    service_.post(strand_.wrap([self, msg]() {
      self->queueMessage(msg);
    }));
  }
  
private:
  void queueMessage(const std::string& msg) {
    bool writeInProgress = !sendPacketQueue_.empty();
    sendPacketQueue_.push_back(msg);
    if (!writeInProgress) {
      startPacketSend();
    }
  }

  void startPacketSend() {
    auto self(shared_from_this());
    asio::async_write(socket_,
                      asio::buffer(sendPacketQueue_.front().data(), sendPacketQueue_.front().length()),
                      strand_.wrap([self](const std::error_code& ec, std::size_t /*n*/) {
                        self->packetSendDone(ec);
                      }));
  }

  void packetSendDone(const std::error_code& ec) {
    if (!ec) {
      sendPacketQueue_.pop_front();
      if (!sendPacketQueue_.empty()) { startPacketSend(); }
    } else {
      // end(); // My end call 
    }
  }
  
  asio::io_service& service_;
  SslSocket socket_;
  asio::io_service::strand strand_;
  std::deque<std::string> sendPacketQueue_;
};

I'm quite sure that I misinterpreted the strand and io_service::post when running the connection handler on multithreaded io_service. I'm also quite sure that the messages are not enqueued chronologically instead of messages not being async_write chronologically. How to ensure that the messages will be enqueued in chronological order in sendMessage call on multithreaded io_service?

Answer 1

On a multi core or even on a single core preemptive OS, you cannot truly feed messages into a queue in strictly chronological order. Even if you use a mutex to synchronize write access to the queue, the strict order is no longer guaranteed once multiple writers wait on the mutex and the mutex becomes free. At best, the order, in which the waiting write threads acquire the mutex, is implementation dependent (OS code dependent), but it is best to assume it is just random.

With that being said, the strict chronological order is a matter of definition in the first place. To explain that, imagine your PC has some digital output bits (1 for each writer thread) and you connected a logic analyzer to those bits.... and imagine, you pick some spot in the code, where you toggle such a respective bit in your enqueue function. Even if that bit toggle takes place just one assembly instruction prior to acquiring the mutex, it is possible, that the order had been changed, while the writer code approached that point. You could also set it to other arbirtrary points prior (e.g. when you enter the enqueue function). But then, the same reasoning applies. Hence, the strict chronological order is in itself a matter of definition.

There is an analogy to a case, where a CPUs interrupt controller has multiple inputs and you tried to build a system which processes those interrupts in strictly chronological order. Even if all interrupt inputs were signaled exactly at the same moment (a switch, pulling them all to signaled state simultaneously), some order would occur (e.g. caused by hardware logic or just by noise at the input pins or by the systems interrupt dispatcher function (some CPUs (e.g. MIPS 4102) have a single interrupt vector and assembly code checks the possible interrupt sources and dispatches to dedicated interrupt handlers).

This analogy helps see the pattern: It comes down to asynchronous inputs on a synchronous system. Which is a notoriously hard problem in itself.

So, the best you could possibly do, is to make a suitable definition of your applications "strict ordering" and live with it.

Then, to avoid violations of your definition, you could use a priority queue instead of a normal FIFO data type and use as priority some atomic counter:

• At your chosen point in the code, atomically read and increment the counter. This is your messages sequence number.
• Assemble your message and enqueue it into the priority queue, using your sequence number as priority.

Another possible approach is to define a notion of "simultaneous", which is detectable on the other side of the queue (and thus, the reader cannot assume strict ordering for a set of "simultaneous" messages). This could be implemented by reading some high frequency tick count and all those messages, which have the same "time stamp" are to be considered simultaneous on reader side.