SEDA on .NET

I ran across an architectural model called staged event-driven architecture (SEDA), which purports to make it easier to build dynamically scalable, high-performance systems. The idea is similar to message-passing systems: each stage receives a message on it’s queue, works on it and sends messages to other stages. The difference is that each stage is actually a thread pool rather than a single thread. The extra trick with SEDA, which I haven’t implemented yet, is that each stage monitors its own performance and tunes its execution behavior. If a stage gets backed up, it will reject attempts to put new work on its queue. The senders must be written to intelligently back off by waiting, rejecting new clients or sending easier work items.

This is fairly easy to write in .NET. The problem, however, is I want to use the Parallel library in .NET 4, including the new thread pool. There is only one thread pool in .NET, so I have to simulate the idea of multiple thread pools. I do this by manually restricting each stage from sending too much work into the thread pool. I don’t want a single stage to flood the thread pool with tons of work, thus starving the other stages of threads to make progress on their work. So I set a limit on how much work a single stage can submit concurrently. This limit can be adjusted by the stage as it monitors performance. I’ve attached a prototype of a Stage in C#.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics.Contracts;
using System.Collections.Concurrent;
using System.Threading;
using System.Threading.Tasks;

namespace SEDA
{
    public class Stage : IDisposable
    {
        Thread engine;
        bool stayAlive = true;
        ConcurrentQueue eventQueue;
        SemaphoreSlim resources;
        int resourceAvailable;
        Action eventHandler;
        Timer controllerTimer;

        int maxBatchSize = 10;

        void Worker()
        {
            T item;

            while (stayAlive) {
                if (resources.Wait(10)) {
                    int size = 0;
                    List items = new List(maxBatchSize);
                    while (eventQueue.TryDequeue(out item) && size  { eventHandler(items.ToArray()); resources.Release(); };
                    Task.Factory.StartNew(stageEvent);
                }
            }

            Console.WriteLine("Worker thread is done.");
        }

        protected virtual bool Admission(T item)
        {
            return true;
        }

        // TODO: How will the controller monitor and adjust resources (threads, batch size, etc)?
        protected virtual void Controller(object state)
        {
        }

        public virtual bool Send(T item)
        {
            if (Admission(item)) {
                //Console.WriteLine("Enqueueing {0}", item);
                eventQueue.Enqueue(item);
                return true;
            } else
                return false;
        }

        public Stage(Action eventHandler, int minThreads = 5, int maxThreads = 20)
        {
            Contract.Requires(eventHandler != null);
            Contract.Requires(minThreads < maxThreads);

            eventQueue = new ConcurrentQueue();
            this.eventHandler = eventHandler;
            resources = new SemaphoreSlim(minThreads, maxThreads);
            resourceAvailable = maxThreads - minThreads;

            controllerTimer = new Timer(Controller);

            engine = new Thread(Worker);
            engine.IsBackground = true;
            engine.Name = this.ToString();
            engine.Start();
        }

        bool _disposed = false;

        void IDisposable.Dispose()
        {
            if (_disposed) throw new ObjectDisposedException(this.ToString());

            if (engine != null)
            {
                stayAlive = false;
                if (!engine.Join(5))
                {
                    engine.Interrupt();
                    if (!engine.Join(5))
                        engine.Abort();
                }
            }

            controllerTimer.Dispose();
            _disposed = true;
        }
    }
}

Advertisements

2 comments

  1. Ade Miller

    SEDA looks really interesting. Several of Welsh’s papers are well worth reading.

    The code here has a little too much Handwaving, it doesn’t compile 🙂

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s