|
 ABSTRACT
We propose a new design for highly concurrent Internet services, which we call the staged event-driven architecture (SEDA). SEDA is intended to support massive concurrency demands and simplify the construction of well-conditioned services. In SEDA, applications consist of a network of event-driven stages connected by explicit queues. This architecture allows services to be well-conditioned to load, preventing resources from being overcommitted when demand exceeds service capacity. SEDA makes use of a set of dynamic resource controllers to keep stages within their operating regime despite large fluctuations in load. We describe several control mechanisms for automatic tuning and load conditioning, including thread pool sizing, event batching, and adaptive load shedding. We present the SEDA design and an implementation of an Internet services platform based on this architecture. We evaluate the use of SEDA through two applications: a high-performance HTTP server and a packet router for the Gnutella peer-to-peer file sharing network. These results show that SEDA applications exhibit higher performance than traditional service designs, and are robust to huge variations in load.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
1
|
Akamai, Inc. h t t p : //www. akamai, coma
|
| |
2
|
America Online Press Data Points. http ://corp.aol,com /press/ press datapoints.html.
|
| |
3
|
Digital Island, Inc. http : //www. digitalisland, com/.
|
| |
4
|
Acme Labs. thttpd: Tiny/Turbo{rhrottling HTrP Server. http : //www. acrae, com/software/tht tpd/.
|
 |
5
|
|
| |
6
|
Apache Software Foundation. The Apache web server, http : //www. apache, org.
|
| |
7
|
|
| |
8
|
G.BangaandJ. C. Mogul. Scalable kernel performance for lnternet servers under realistic loads. In Prec. 1998 Annual Usenix Technical Conference, New Orleans, LA, June 1998.
|
| |
9
|
G. Banga, J. C. Mogul, and P. Druscbel. A scalable and explicit event delivery mechanism for UNIX. In Prec. USENIX 1999 Annual Technical Conference, Monterey, CA, June 1999.
|
| |
10
|
BEA Systems. BEA WebLogic. http://www.beasys.com/ product s/weblogic/.
|
| |
11
|
B. N. Bershad , S. Savage , P. Pardyak , E. G. Sirer , M. E. Fiuczynski , D. Becker , C. Chambers , S. Eggers, Extensibility safety and performance in the SPIN operating system, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.267-283, December 03-06, 1995, Copper Mountain, Colorado, United States
|
| |
12
|
A. Chankhunthod, P. B. Danzig, C. Neerdaels, M. E Schwartz, and K. J. Worrell. A hierarchical Internet object cache. In Prec. 1996 Usenix Annual Technical Conference, pages 153-163, January 1996.
|
| |
13
|
Yuan Chen , Jan Edler , Andrew Goldberg , Allan Gottlieb , Sumeet Sobti , Peter Yianilos, A prototype implementation of archival Intermemory, Proceedings of the fourth ACM conference on Digital libraries, p.28-37, August 11-14, 1999, Berkeley, California, United States
[doi> 10.1145/313238.313249]
|
| |
14
|
Ian Clarke , Oskar Sandberg , Brandon Wiley , Theodore W. Hong, Freenet: a distributed anonymous information storage and retrieval system, International workshop on Designing privacy enhancing technologies: design issues in anonymity and unobservability, p.46-66, January 2001, Berkeley, California, United States
|
| |
15
|
M. Crovella, R. Frangioso, and M. Harchol-Balter. Connection scheduling in Web servers. In Prec. 1999 USENIX Symposium on lnternet Technologies and Systems ( USITS "99), October 1999.
|
| |
16
|
M.L. Dertouzos. The future of computing. Scientific American, July 1999.
|
| |
17
|
|
| |
18
|
Armando Fox , Steven D. Gribble , Yatin Chawathe , Eric A. Brewer , Paul Gauthier, Cluster-based scalable network services, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.78-91, October 05-08, 1997, Saint Malo, France
|
| |
19
|
Gnutella. http : //gnutella .wego. com.
|
| |
20
|
S. Oribble, E. Brewer, J. Hellersteln, and D. Culler. Scalable, distributed data structures for interact service construction. In Prec. Fourth Symposium on Operating Systems Design and Implementation ( OSD12000), October 2000.
|
| |
21
|
S. Gribble, M. Welsh, R. yon Behren, E. Brewer, D. Culler, N. Borisov, S. Czerwinski, R. Gummadi, J. Hill, A. Joseph, R. Katz, Z. Mao, S. Ross, and B. Zhao. The Ninja architecture for robust Intemet-scale systems and services. Computer Networks, June 2000. Special Issue on Pervasive Computing.
|
| |
22
|
Hewlett-Packard Corporation. e-speak Open Services Platform. http: //www. e- speak, net/.
|
| |
23
|
J. Hu, S. Mungee, and D. Schmidt. Techniques for developing and measuring high-performance Web servers over ATM networks. In Prec. IN- FOCOM '98, March/April 1998.
|
| |
24
|
J. C. Hu, I. Pyarali, and D. C. Schmidt. High performance Web servers on Windows NT: Design and performance. In Prec. USENIX Windows NT Workshop 1997, August 1997.
|
| |
25
|
IBM Corporation. IBM WebSphere Application Server. http :// www-4, ibm. com/so f tware/webservers/.
|
| |
26
|
S. M. Inc. Java Server Pages API. http://java.sun.com/ product s /jsp.
|
| |
27
|
R. Jain, D. Chiu, and W. Hawe. A quantitative measure of fairness and discrimination for resource allocation in shared computer systems. Technical Report TR-301, DEC Research, September 1984.
|
| |
28
|
M. Frans Kaashoek , Dawson R. Engler , Gregory R. Ganger , Hector M. Briceño , Russell Hunt , David Mazières , Thomas Pinckney , Robert Grimm , John Jannotti , Kenneth Mackenzie, Application performance and flexibility on exokernel systems, Proceedings of the sixteenth ACM symposium on Operating systems principles, p.52-65, October 05-08, 1997, Saint Malo, France
|
| |
29
|
D. Kegel. The C10K problem, http://www.kegel .com/cl0k. html.
|
| |
30
|
John Kubiatowicz , David Bindel , Yan Chen , Steven Czerwinski , Patrick Eaton , Dennis Geels , Ramakrishna Gummadi , Sean Rhea , Hakim Weatherspoon , Chris Wells , Ben Zhao, OceanStore: an architecture for global-scale persistent storage, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.190-201, November 2000, Cambridge, Massachusetts, United States
|
| |
31
|
J. Larus and M. Parkes. Using cohort scheduling to enhance server performance. Technical Report MSR-TR-2001-39, Microsoft Research, March 2001.
|
| |
32
|
H. Lauer and R. Needhant On the duality of operating system structures. In Proc. Second International Symposium on Operating Systems, IRIA, October 1978.
|
| |
33
|
J. Lemon. FreeBSD kernel event queue patch, http://www. flugsvamp,com/~jlemon/fbsd/.
|
| |
34
|
I. Leslie, D. McAuley, R. Black, T. Roscoe, E Barbara, D. Evers, R. Fairbairns, and E. Hyden. The design and implementation of an operating system to support distributed multimedia applications. IEEE Journal on Selected Areas in Communications, 14:1280-1297, September 1996.
|
| |
35
|
A. S. Lett and W L. Konigsford. TSS/360: A time-shared operating system. In Proc. Fall Joint Computer Conference, Volume 33, Part 1, pages 15-28, 1968.
|
| |
36
|
|
| |
37
|
Microsoft Corporation. DCOM Technical Overview. h t t p : //msdn. mi croso ft. com/I ibrary/backgrnd/html/msdn_ dcomt ec. htm.
|
| |
38
|
Microsoft Corporation. IIS 5.0 Overview. http ://w. microsoft, com/windows2000 / i ibrary/howitworks / iis / iis5techove%rview, asp.
|
| |
39
|
Jeffrey C. Mogul, The case for persistent-connection HTTP, Proceedings of the conference on Applications, technologies, architectures, and protocols for computer communication, p.299-313, August 28-September 01, 1995, Cambridge, Massachusetts, United States
|
| |
40
|
Robert Morris , Eddie Kohler , John Jannotti , M. Frans Kaashoek, The Click modular router, Proceedings of the seventeenth ACM symposium on Operating systems principles, p.217-231, December 12-15, 1999, Charleston, South Carolina, United States
|
| |
41
|
|
| |
42
|
Netscape Corporation. Netscape Enterprise Server. http: //home. net scape, com/enterprise/v3.6 / index, html.
|
| |
43
|
|
| |
44
|
V.S. Pal, P. Druschel, and W. Zwaenepoel. Flash: An efficient and portable Web server. In Proc. 1999 Annual Usenix Technical Conference, June 1999.
|
| |
45
|
S. Parekh, N. Gandhi, J. L. Hellerstein, D. Tilbury, T. Jayram, and J. Bigus. Using control theory to achieve service level objectives in performance management. In Proc. IFIP/IEEE International Symposium on Integrated Network Management, Seattle, WA, May 2001.
|
| |
46
|
N. Provos and C. Lever. Scalable network I/O in Linux. Technical Report CITI-TR-00-4, University of Michigan Center for Information Technology Integration, May 2000.
|
| |
47
|
Xiaohu Qie , Andy Bavier , Larry Peterson , Scott Karlin, Scheduling computations on a software-based router, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.13-24, June 2001, Cambridge, Massachusetts, United States
|
| |
48
|
M. Russinovich. Inside lgO completion ports, http://www. sysinternals, com/comport, htm.
|
| |
49
|
|
| |
50
|
Standard Performance Evaluation Corporation. The SPECweb99 benchmark. http : //www. spec. org/osg/web99/.
|
| |
51
|
David C. Steere , Ashvin Goel , Joshua Gruenberg , Dylan McNamee , Calton Pu , Jonathan Walpole, A feedback-driven proportion allocator for real-rate scheduling, Proceedings of the third symposium on Operating systems design and implementation, p.145-158, February 1999, New Orleans, Louisiana, United States
|
| |
52
|
Sun Microsystems. RPC: Remote Procedure Call Protocol Specification Version 2. Internet Network Working Group RFC1057, June 1988.
|
| |
53
|
Sun Microsysterns Inc. Enterprise Java Beans Technology. http :// java. sun. com/products/ejb/.
|
| |
54
|
Sun Microsystems, Inc. Java Remote Method Invocation. http:// java.sun.com/products/jdk/rmi/.
|
| |
55
|
Sun Microsysterns Inc. Jini Connection Technology. http: //www. sun. com/j ini/.
|
| |
56
|
M. Vandevoorde and E. Roberts. Work crows: An abstraction for controlling parallelism. Technical Report Research Report 42, Digital Equipment Corporation Systems Research Center, February 1988.
|
| |
57
|
|
| |
58
|
L. A. Wald and S. Schwarz. The 1999 Southern California Seismic Network Bulletin. Seismological Research Letters, 71(4), July/August 2000.
|
| |
59
|
Deborah A. Wallach , Dawson R. Engler , M. Frans Kaashoek, ASHs: Application-specific handlers for high-performance messaging, Conference proceedings on Applications, technologies, architectures, and protocols for computer communications, p.40-52, August 28-30, 1996, Palo Alto, California, United States
|
| |
60
|
M. Welsh. NBIO: Nonhlocking I/O for Java. http: //www.cs. berkeley, edu/~mdw/pro j / java- nbio.
|
| |
61
|
|
| |
62
|
Yahoo! Inc. Yahoo! reports Second Quarter 2001 financial results, http : //docs. yahoo, com/docs/pr / rel ease794, html.
|
| |
63
|
Zeus Technology. Zeus Web Server. http://www.zeus.co.uk/ products/ws/.
|
CITED BY 116
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Amol Shukla , Lily Li , Anand Subramanian , Paul A. S. Ward , Tim Brecht, Evaluating the performance of user-space and kernel-space web servers, Proceedings of the 2004 conference of the Centre for Advanced Studies on Collaborative research, p.189-201, October 04-07, 2004, Markham, Ontario, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Bratin Saha , Ali-Reza Adl-Tabatabai , Anwar Ghuloum , Mohan Rajagopalan , Richard L. Hudson , Leaf Petersen , Vijay Menon , Brian Murphy , Tatiana Shpeisman , Eric Sprangle , Anwar Rohillah , Doug Carmean , Jesse Fang, Enabling scalability and performance in a large scale CMP environment, ACM SIGOPS Operating Systems Review, v.41 n.3, June 2007
|
|
|
|
|
|
|
|
|
Khaled Elmeleegy , Anupam Chanda , Alan L. Cox , Willy Zwaenepoel, Lazy asynchronous I/O for event-driven servers, Proceedings of the USENIX Annual Technical Conference 2004 on USENIX Annual Technical Conference, p.21-21, June 27-July 02, 2004, Boston, MA
|
|
|
|
|
|
|
|
|
Frank Dabek , Nickolai Zeldovich , Frans Kaashoek , David Mazières , Robert Morris, Event-driven programming for robust software, Proceedings of the 10th workshop on ACM SIGOPS European workshop: beyond the PC, July 01-01, 2002, Saint-Emilion, France
|
|
|
|
|
|
Yan Chen , Xinyuan Fan , Wenjun Yang , Kai Chen , Guozhi Xu, Stage based parallel programming model for high concurrency, stateful network services: internals and design principles, International Journal of High Performance Computing and Networking, v.3 n.1, p.33-44, September 2005
|
|
|
Felix Hupfeld , Björn Kolbeck , Jan Stender , Mikael Högqvist , Toni Cortes , Jonathan Marti , Jesús Malo, FaTLease: scalable fault-tolerant lease negotiation with paxos, Proceedings of the 17th international symposium on High performance distributed computing, June 23-27, 2008, Boston, MA, USA
|
|
|
|
|
|
|
|
|
Jordi Guitart , David Carrera , Vicenç Beltran , Jordi Torres , Eduard Ayguadé, Dynamic CPU provisioning for self-managed secure web applications in SMP hosting platforms, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.52 n.7, p.1390-1409, May, 2008
|
|
|
Pankaj K. Garg , Ming Hao , Cipriano Santos , Hsiu-Khuern Tang , Alex Zhang, Web transaction analysis and optimization (TAO), Proceedings of the 3rd international workshop on Software and performance, July 24-26, 2002, Rome, Italy
|
|
|
|
|
|
|
|
|
Arun Raghunath , Aaron Kunze , Erik J. Johnson , Vinod Balakrishnan, Framework for supporting multi-service edge packet processing on network processors, Proceedings of the 2005 symposium on Architecture for networking and communications systems, October 26-28, 2005, Princeton, NJ, USA
|
|
|
Ira Cohen , Steve Zhang , Moises Goldszmidt , Julie Symons , Terence Kelly , Armando Fox, Capturing, indexing, clustering, and retrieving system history, ACM SIGOPS Operating Systems Review, v.39 n.5, December 2005
|
|
|
|
|
|
|
|
|
Patrick Reynolds , Janet L. Wiener , Jeffrey C. Mogul , Marcos K. Aguilera , Amin Vahdat, WAP5: black-box performance debugging for wide-area systems, Proceedings of the 15th international conference on World Wide Web, May 23-26, 2006, Edinburgh, Scotland
|
|
|
|
|
|
Zhanwen Li , David Levy , Shiping Chen , John Zic, Auto-tune design and evaluation on staged event-driven architecture, Proceedings of the 1st workshop on MOdel Driven Development for Middleware (MODDM '06), p.1-6, November 27-December 01, 2006, Melbourne, Australia
|
|
|
Matthieu Leclercq , Vivien Quéma , Jean-Bernard Stefani, DREAM: a component framework for the construction of resource-aware, reconfigurable MOMs, Proceedings of the 3rd workshop on Adaptive and reflective middleware, p.250-255, October 19-19, 2004, Toronto, Ontario, Canada
|
|
|
Girish B. Chafle , Sunil Chandra , Vijay Mann , Mangala Gowri Nanda, Decentralized orchestration of composite web services, Proceedings of the 13th international World Wide Web conference on Alternate track papers & posters, May 19-21, 2004, New York, NY, USA
|
|
|
Kiran Nagaraja , Fábio Oliveira , Ricardo Bianchini , Richard P. Martin , Thu D. Nguyen, Understanding and dealing with operator mistakes in internet services, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.5-5, December 06-08, 2004, San Francisco, CA
|
|
|
|
|
|
|
|
|
|
|
|
Sam Michiels , Lieven Desmet , Nico Janssens , Tom Mahieu , Pierre Verbaeten DistriNet, Self-adapting concurrency: the DMonA architecture, Proceedings of the first workshop on Self-healing systems, November 18-19, 2002, Charleston, South Carolina
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Pere Barlet-Ros , Gianluca Iannaccone , Josep Sanjuàs-Cuxart , Diego Amores-López , Josep Solé-Pareta, Load shedding in network monitoring applications, 2007 USENIX Annual Technical Conference on Proceedings of the USENIX Annual Technical Conference, p.1-14, June 17-22, 2007, Santa Clara, CA
|
|
|
|
|
|
|
|
|
Giuseppe DeCandia , Deniz Hastorun , Madan Jampani , Gunavardhan Kakulapati , Avinash Lakshman , Alex Pilchin , Swaminathan Sivasubramanian , Peter Vosshall , Werner Vogels, Dynamo: amazon's highly available key-value store, ACM SIGOPS Operating Systems Review, v.41 n.6, December 2007
|
|
|
A. Stephen McGough , Asif Akram , Li Guo , Marko Krznaric , Luke Dickens , David Colling , Janusz Martyniak , Roger Powell , Paul Kyberd , Chenxi Huang , Constantinos Kotsokalis , Panayiotis Tsanakas, GRIDCC: A Real-time Grid workflow system with QoS, Scientific Programming, v.15 n.4, p.213-234, December 2007
|
|
|
|
|
|
|
|
|
|
|
|
Paul Barham , Rebecca Isaacs , Richard Mortier , Dushyanth Narayanan, Magpie: online modelling and performance-aware systems, Proceedings of the 9th conference on Hot Topics in Operating Systems, p.15-15, May 18-21, 2003, Lihue, Hawaii
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Shigeru Kusakabe , Mitsuhiro Aono , Masaaki Izumi , Satoshi Amamiya , Yoshinari Nomura , Hideo Taniguchi , Makoto Amamiya, Scalability of continuation-based fine-grained multithreading in handling multiple I/O requests on FUCE, Proceedings of the 4th international conference on Computing frontiers, May 07-09, 2007, Ischia, Italy
|
|
|
J. Robert von Behren , Eric A. Brewer , Nikita Borisov , Michael Chen , Matt Welsh , Josh MacDonald , Jeremy Lau , David E. Culler, Ninja: A Framework for Network Services, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.87-102, June 10-15, 2002
|
|
|
|
|
|
|
|
|
Adrian Paschke , Harold Boley , Alexander Kozlenkov , Benjamin Craig, Rule responder: RuleML-based agents for distributed collaboration on the pragmatic web, Proceedings of the 2nd international conference on Pragmatic web, p.17-28, October 22-23, 2007, Tilburg, The Netherlands
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
John Giacomoni , John K. Bennett , Antonio Carzaniga , Douglas C. Sicker , Manish Vachharajani , Alexander L. Wolf, Frame shared memory: line-rate networking on commodity hardware, Proceedings of the 3rd ACM/IEEE Symposium on Architecture for networking and communications systems, December 03-04, 2007, Orlando, Florida, USA
|
|
|
|
|
|
|
|
|
|
|
|
Jordi Guitart , David Carrera , Vicenç Beltran , Jordi Torres , Eduard Ayguadé, Designing an overload control strategy for secure e-commerce applications, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.51 n.15, p.4492-4510, October, 2007
|
|
|
|
|
|
Ronald P. Doyle , Jeffrey S. Chase , Omer M. Asad , Wei Jin , Amin M. Vahdat, Model-based resource provisioning in a web service utility, Proceedings of the 4th conference on USENIX Symposium on Internet Technologies and Systems, p.5-5, March 26-28, 2003, Seattle, WA
|
|
|
Rob von Behren , Jeremy Condit , Feng Zhou , George C. Necula , Eric Brewer, Capriccio: scalable threads for internet services, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Sean Rhea , Patrick Eaton , Dennis Geels , Hakim Weatherspoon , Ben Zhao , John Kubiatowicz, Awarded Best Student Paper! - Pond: The OceanStore Prototype, Proceedings of the 2nd USENIX Conference on File and Storage Technologies, March 31-31, 2003, San Francisco, CA
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Alexandros Batsakis , Randal Burns , Arkady Kanevsky , James Lentini , Thomas Talpey, CA-NFS: a congestion-aware network file system, Proccedings of the 7th conference on File and stroage technologies, p.99-110, February 24-27, 2009, San Francisco, California
|
|
|
|
|
|
Petros Efstathopoulos , Maxwell Krohn , Steve VanDeBogart , Cliff Frey , David Ziegler , Eddie Kohler , David Mazières , Frans Kaashoek , Robert Morris, Labels and event processes in the asbestos operating system, ACM SIGOPS Operating Systems Review, v.39 n.5, December 2005
|
|
|
Sameh Elnikety , Erich Nahum , John Tracey , Willy Zwaenepoel, A method for transparent admission control and request scheduling in e-commerce web sites, Proceedings of the 13th international conference on World Wide Web, May 17-20, 2004, New York, NY, USA
|
|
|
|
|
|
|
|
|
|
|
|
Jian Yin , Jean-Philippe Martin , Arun Venkataramani , Lorenzo Alvisi , Mike Dahlin, Separating agreement from execution for byzantine fault tolerant services, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
|
|
|
Ömer Erdem Demir , Prémkumar Dévanbu , Eric Wohlstadter , Stefan Tai, An aspect-oriented approach to bypassing middleware layers, Proceedings of the 6th international conference on Aspect-oriented software development, March 12-16, 2007, Vancouver, British Columbia, Canada
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Peter Sewell , Gareth Stoyle , Michael Hicks , Gavin Bierman , Keith Wansbrough, Dynamic rebinding for marshalling and update, via redex-time and destruct-time reduction, Journal of Functional Programming, v.18 n.4, p.437-502, July 2008
|
|
|
|
|
|
Robert Grimm , Janet Davis , Eric Lemar , Adam Macbeth , Steven Swanson , Thomas Anderson , Brian Bershad , Gaetano Borriello , Steven Gribble , David Wetherall, System support for pervasive applications, ACM Transactions on Computer Systems (TOCS), v.22 n.4, p.421-486, November 2004
|
|
|
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
D.4