Workload management strategies

In a React world, everything is an event that anybody can grab and process according to whatever its responsibility is. The notion of event allows for very low contract coupling; it acts as a medium between classes. A message is similar, but with more coupling as it aggregates endpoints or endpoints addresses.
This model offers flexible design where events flow and are processed through the systems. But what happens when you have too many events to process?

Continue reading “Workload management strategies”

Our Devoxx 2014 talk

Our Devoxx 2014 talk

My mate Thomas Pierrain and I were lucky enough to have our topic selected for Devoxx FR 2014. The subject was the presentation of the sequencer and an iterative design exercise for a financial real-time pricing service.

Many thanks to our amazing audience that gave us interesting questions and good feedback. For those who may be interested, the talk can be seen on Parleys in the Devoxx FR channel.

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 2)

In my last post I made a promise: showing the implementation of Sequencer

So please, bear with me while I review the requirements. The sequencer

  1. Is a facade: wraps an execution context, such as a thread or a pool of threads
  2. Prevents race conditions: enforces sequential execution of submitted tasks
  3. Guarantees ordering: submitted tasks are processed in the order they are submitted
  4. Avoid useless consumptions of resources.

The first one is simply a design choice, no need to elaborate. Next is how to prevent race conditions: as the execution basis is a lambda/delegate/runable of some sort, we need to prevent concurrent execution of those.

A simplistic state machine can help us. The possible states are running and waiting; transitions are triggered by incoming tasks.
If the machine is in the ‘waiting‘ state, it transitions to ‘running‘ and executes the task; when the task is done, it transitions back to ‘waiting‘.
But if the machine is in the ‘running‘ state, execution cannot start, it needs to wait for the appropriate state.
It can be implemented with a lock, the ‘running‘ state being embodied by the lock being held. What interests me is how we deal with conflicts, i.e. when a task comes in while the state is still ‘running‘.
If we respect the lock semantic, the incoming request is blocked until we reached the desired state. Blocking implies waste and potential deadlock. So no go there.

We need to complexify a bit our logic. So, when a task is submitted for execution and the state is ‘running‘, we can store it for a differed execution. There is no need to keep to current thread blocked.
As a consequence, the transition out of ‘running‘ is now: when the task is executed, if there is at least another task pending execution, we execute it (state remains ‘running‘). When there are no pending task, we can safely transition to ‘waiting‘.

Ok, time to look at some code. Disclaimer: this implementation is for educational purpose, I know it will look ugly to some, slow to others,… you name it. But I do not care, so bear with me.
For non C# readers: an Action is a parameter-less procedure ( i.e. no return value).

using System;
using System.Collections.Generic;
using System.Threading;
namespace Sequencer
{
public class Sequencer
{
private Queue<Action> _pendingTasks = new Queue<Action>();
private bool _isRunning;
private readonly object _lock = new Object();
public void Dispatch(Action action)
{
// here we queue a call to our own logic
ThreadPool.QueueUserWorkItem( (x)=> Run((Action) x), action );
}
// run when the pool has available cpu time for us.
private void Run(Action action)
{
lock(_lock) {
if (_isRunning) {
// we need to store and stop
_pendingTasks.Enqueue(action);
return;
}
// ok, we can run
_isRunning = true;
}
while (true) {
// execute the next action
action ();
// we check if others are available
lock (_lock) {
if (_pendingTasks.Count == 0) {
_isRunning = false;
return;
}
// pop the next task
action = _pendingTasks.Dequeue();
}
}
}
}
}

view raw
Sequencer_1.cs
hosted with ❤ by GitHub

As you can see, the actual implementation is slightly more complex than described earlier. Indeed, we need to cater for two atomic transactions:

  1. On a new task: starting it right away or queuing it
  2. When the task is done: fetching a new one or ‘freeing’ the sequencer

Lets look at the requirements

  • Requirement #1: we wrap an existing execution mechanism (the .Net thread pool). Nothing fancy here, it will be improved in a future revision
  • Requirement #2: done as well, it has been specifically for that purpose
  • Requirement #3: we did nothing specific here, but on the other hand it looks ok
  • Requirement #4: by using a differed execution mechanism, we prevented the need to block threads, something we know is expensive

So, are we done now?

Nope, requirements #3 is definitely not covered. On a multicore machine (basically any machine nowadays), multiple threads (from the thread pool) can start to work on tasks at the same time, and there will be a race to queue them in the sequencer.

We need to refine this implementation.
What would be your proposal to have ordering guarantee?