In my previous post, I mentioned that I had actually 4 implementations proposal and I commented two of them, which were within the drafted requirements but had an issue with fairness: in both cases, one could bypass the thread pool queue altogether.

Let’s turn our attention to the other two, which are interesting because they share a common issue while having radically different approach.

C#, very short one

Java, long implementation

Clearly, the .Net version benefits from the TPL features. That being said, they are actually very close as they share the same algorithm: ordering is secured by creating a private queue, and non concurrency is ensured by making sure at most one task is enqueued or executing in the .net threadpool.

Contract is fulfilled, albeit with a steep price in terms of performance, or more precisely latency. As a task is actually dispatched only after the previous one have been executed, there is a minimum delay between two tasks. So, once again there is a fairness issue. It is obvious that non sequenced tasks would be executed faster than sequenced ones.

Continue reading “The Sequencer (part 2.2)” →

Several years ago, I was lead on a new mass market making system. One of the objectives of the project was to have low latencies and controlled throughput, target latency was < 1 ms isolated event latency and have a 99 percentile below 10 ms.

Throughput had to be controlled because downstream bandwidth was reduced to a trickle, a mere 50 updates/sec while the inputs were in the order of 2000 updates/sec. So the system required an arbitration algorithm for this output decisions.

At that time, I still had a burning memory of my time as a lead C++ dev on a in house multithreaded fat client app: I basically spent the best part of two years rebuilding the threading model from scratch, a long and painful process. This definitely was an apprentice journey towards multithreading craftsmanship.

Sadly, I ultimately came to the conclusion that, at that time, building and maintaining a multi threaded app was a daunting task.

Therefore I decided to push for a radically different approach: managing concurrency without any locks.

When you think about it, what is the best way to manage concurrency?

First of all by realizing there is no concurrency per se. 99.99% of the time you’ll have locks that enforce mutual exclusion. Managing concurrency means preventing actual concurrency from happening in the first place.

And then was born the ‘Sequencer’.

The ‘Sequencer’ is a design pattern that has been created in C# and replicated in Java and C++. The contract is simple:

The Sequencer:

• Is a facade: wraps an execution context, such as a thread or a pool of threads
• Prevents race conditions: enforces sequential execution of submitted tasks
• Guarantees sequentiality: submitted tasks are processed in the order they are submitted

And that’s it. The Sequencer was coupled with another simpler pattern: the ‘Dispatcher’ in charge of providing actual execution capacity. There are several variant implementations of IDispatcher but I will present them on a future post.

Actually, the Sequencer is a specific implementation of an IDispatcher.

It looks a lot like an actor without the messaging infrastructure.

Let’s talk implementation.

Behind its apparent simplicity, the Sequencer hides moderate complexity. But I’ll talk further about it in an upcoming post.