SEDA

The last time I looked into web server architecture was six or seven years ago, when someone pointed me at Dan Kegel's C10K paper. I'm pleased to see that he tried for a while to keep that paper up to date, although it looks like it's been a few years since it was updated.

Recently, I followed some links and ended up at Matt Welsh's SEDA work. Welsh appears to have moved on to other projects, but the SEDA work remains live at SourceForge.

I read through the SOSP 2001 paper and enjoyed it; it's quite readable and well-written, and explains the basic principles clearly.

The primary focus of SEDA is on helping software developers build what Welsh calls "well-conditioned services":

The key property of a well-conditioned service is graceful degradation: as offered load exceeds capacity, the service maintains high throughput with a linear response-time penaly that impacts all clients equally, or at least predictably according to some service-specific policy. Note that this is not the typical Web experience; rather, as load increases, throughput decreases and response time increases dramatically, creating the impression that the service has crashed.

Modern network servers tend to use one of two basic programming techniques: thread-based concurrency, or event-driven programming. Welsh compares and contrasts the two models:

The most commonly used design for server applications is the thread-per-request model. ... In this model, each accepted request consumes a thread to process it, with synchronization operations protecting shared resources. The operaitng system overlaps computation and I/O by transparently switching among threads. ...
When each request is handled by a single thread, it is difficult to identify internal performance bottlenecks in order to perform tuning and load conditioning.

...

The scalability limits of threads have led many developers to eschew them almost entirely and employ an event-driven approach to managing concurrency. In this approach, a server consists of a small number of threads (typically one per CPU) that loop continuously, processing events of different types from a queue. ... Event-driven systems tend to be robust to load, with little degradation in throughput as offered load increases beyond saturation. ... The choice of an event scheduling algorithm is often tailored to the specific application, and introduction of new functionality may require the algorithm to be redesigned. Also, modularity is difficult to achieve, as the code implementing each state must be trusted not to block or consume a large number of resources that can stall the event-handling thread.

To overcome the problems of the two basic approaches, the SEDA work proposes a synthesis and unification:

The staged event-driven architecture (SEDA) ... decomposes an application into a network of stages separated by event queues and introduces the notion of dynamic resource controllers to allow applications to adjust dynamically to changing load.

...

A stage is a self-contained application component consisting of an event handler, an incoming event queue, and a thread pool. ... Each stage is managed by a controller that affects scheduling and thread allocation. ... Stage threads operate by pulling a batch of events off of the incoming event queue and invoking the application-supplied event handler. The event handler processes each batch of events, and dispatches zero or more events by enqueuing them on the event queues of other stages.

The paper goes on to work through many of the details, and to demonstrate a variety of different resource controller implementations, showing how the alternate controllers can provide elegant implementations of adaptive load shedding without forcing complexity into the system developer's core logic.

It's quite a nice presentation, and I liked the way it was all pulled together. I was intimately familiar with the basic techniques and approaches, but it was very helpful to see them pulled together and structured in this fashion.

If you're at all interested in how to build scalable and robust network services that perform reliably under extreme conditions, it's worth spending some time with this work.