SEDA: An Architecture for Highly Concurrent Server Applications at http://www.eecs.harvard.edu/mdw/proj/seda/.
SEDA is an acronym for staged event-driven architecture, and decomposes a complex, event-driven application into a set of stages connected by queues. This design avoids the high overhead associated with thread-based concurrency models, and decouples event and thread scheduling from application logic. By performing admission control on each event queue, the service can be well-conditioned to load, preventing resources from being overcommitted when demand exceeds service capacity. SEDA employs dynamic control to automatically tune runtime parameters (such as the scheduling parameters of each stage), as well as to manage load, for example, by performing adaptive load shedding. Decomposing services into a set of stages also enables modularity and code reuse, as well as the development of debugging tools for complex event-driven applications.
Our current prototype of a SEDA-based services platform is called Sandstorm. Sandstorm is implemented entirely in Java and uses the NBIO package to provide nonblocking I/O support. Support for the JDK 1.4 java.nio package is included as well. Despite using Java, we have achieved performance that rivals (and sometimes exceeds) that of C/C++. We have also implemented a SEDA-based asynchronous SSL and TLS protocol library, called aTLS. All of this software is available for download below.
We have built a number of applications to demonstrate the SEDA framework. Haboob is a a high-performance Web server including support for both static and dynamic pages that outperforms both Apache and Flash (which are implemented in C) on a SPECWeb99-like benchmark. Other applications include a Gnutella packet router and Arashi, a Web-based email service similar to Yahoo! Mail.
The best place to start for more information is the SOSP'01 paper on SEDA and the corresponding talk slides. My Ph.D. thesis has much more information as well. If you have questions, comments, or are interested in collaborations, please feel free to contact me by e-mail (see my home page).
A number of open source and commercial systems are based on SEDA and NBIO. These include:
- LimeWire runs its massively scalable Gnutella servers on NBIO.
- TerraLycos runs its chat servers on NBIO, supporting over 30,000 simultaneous users
- Rimfaxe Web Server
- Apache Excalibur Event Package
- SwiftMQ, a JMS Enterprise Messaging Server
- OceanStore, a global, secure, peer-to-peer filesystem
- Various companies, both large and small, are building projects based on SEDA/NBIO.
Rules for Creating Stages
From Quartz at http://jcyclone.org/ :
- unless -all- used APIs are asynchronous, you won"t be able to avoid blocking threads. But you can hack the TM settings to avoid cpu balancing for those blocking stages. (example: min=init=max in the thread pool)
- jdbc is not asynchronous. The best I could do is have about 80 threads and connections to service quickly the requests (that stage has a fixed thread pool size).
- the control flow from one class to another could well not require a thread wait. For proper OO design, you might want to isolate the classes in separate stages. Of course, going too far in that direction may lead to more stages than you need.
- I also stage my tasks relatively to the CPU "bandwidth" they require, for the TM to do a good thread pool size/priority balancing. Ex: parsing task is separated from calculations, because one is more i/o and memory bound while the other is mostly CPU and floating point calculus. That is very good for hyperthreaded CPU.
- Matt Welsh Ph.D thesis mentions the code locality as another factor. CPUs love small reapeatable code because the level 2 cache gets exploited better. That usually on multi-cpu machines. See original SEDA white papers and thesis. (a "must read")
Other than that, a small amount of stages can implements one task as the parts before and after blocking calls. But beware, unless the blocking call is a native i/o pure event-driven asynchronous function, (in jdk, there is only selectable socket channels, keyboard and mouse events (gui or stdin) and maybe printjobs and serial ports through javacomm api), you won"t get any benefit from implementing a wait() with queuing events; you will actually waste cpu and memory by passing the control flow from one thread to another.