Tag: sequencer

The Sequencer (part 2.2)

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

using System;
using System.Threading.Tasks;
namespace Seq
{
public class Sequencer
{
private readonly object _lock = new object();
private Task _task = Task.FromResult(0);
public void Dispatch(Action action)
{
lock (_lock)
{
_task = _task.ContinueWith(_ => action());
}
}
}
}
view raw Sequencer V1 hosted with ❤ by GitHub

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)” →

The Sequencer (part 2.1)

Update

I received two more proposals I will comment soon.

Original

I closed the last episode with a little exercise for my readers: suggest me how to complete my requirements, namely by ensuring guaranteed ordering for the sequencer.

Alas, only two were skilled or brave enough to face the challenge and try an answer, and I thank them for that.

The two proposal were similar, but freeman did provide a gist, so let’s discuss it


using System;
using System.Collections.Generic;
using System.Threading;
namespace Sequencer
{
using System.Collections.Concurrent;
public class Sequencer
{
private readonly ConcurrentQueue<Action> _pendingTasks = new ConcurrentQueue<Action>();
private readonly object _running = new Object();
public void Dispatch(Action action)
{
// Queue the task
_pendingTasks.Enqueue(action);
// Schedule a processing run (may be a noop)
ThreadPool.QueueUserWorkItem( x=> Run());
}
// run when the pool has available cpu time for us.
private void Run()
{
if (Monitor.TryEnter(_running))
{
try
{
Action taskToRun;
while (_pendingTasks.TryDequeue(out taskToRun))
{
taskToRun();
}
}
finally
{
Monitor.Exit(_running);
}
}
}
}
}

view raw

Sequencer_1.cs

hosted with ❤ by GitHub

Definitely, this will capture and secure the order of execution. And I like the smart use of TryEnter, allowing to get rid of the boolean used to store the state

But, and this is a big but, this solution violates another (implicit) requirement. I have to apologize for this one, as I failed to state it earlier.

But you know customers: they understand what they need when the development is over :-).

That requirement is fairness: fairness between Sequencer instances as well as fairness between Sequencers and other tasks. Fairness is to be understood as the guarantee that all submitted tasks will eventually executed,that they have equivalent access to execution units (i.e. cores), and with similar delays.
It means that no system can gain exclusive access to execution unit(s) ans that tasks are executed roughly in the order they are submitted.

This being defined, this solution is not fair. Can you tell me why?

Note: here is a gist for the first proposal

The Sequencer (part 1)

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:OLYMPUS DIGITAL CAMERA

  • 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.