SEDA: an architecture for well-conditioned, scalable internet services

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

1. 1.Akamai, Inc. h t t p : //www. akamai, coma]]
2. 2.America Online Press Data Points. http ://corp.aol,com /press/ press datapoints.html.]]
3. 3.Digital Island, Inc. http : //www. digitalisland, com/.]]
4. 4.Acme Labs. thttpd: Tiny/Turbo{rhrottling HTrP Server. http : //www. acrae, com/software/tht tpd/.]]
5. 5.T. Anderson, B. Bershad, E. Lazowska, and H. Levy. Scheduler activations: Effective kernel support for the user-level management of parallelism. ACM Transactions on Computer Systems, 10(1):53-79, February 1992.]]
6. 6.Apache Software Foundation. The Apache web server, http : //www. apache, org.]]
7. 7.G. Banga, E Druschel, and J. Mogul. Resource containers: A new facility for resource management in server systems. In Prec. Third Symposium on Operating Systems Design and Implementation ( OSDI '99), February 1999.]]
8. 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. 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. 10.BEA Systems. BEA WebLogic. http://www.beasys.com/ product s/weblogic/.]]
11. 11.B. Bershad, S. Savage, R Pardyak, E. G. Sirer, D. Becker, M. Fiuczynski, C. Chambers, and S. Eggers. Extensibility, safety and performance in the SPIN operating system. In Prec. 15th ACM Symposium on Operating System Principles (SOSP-15), 1995.]]
12. 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. 13.Y. Chen, J. Edler, A. Goldberg, A. Gottlieb, S. Sobti, and P. Yianilos. A prototype implementation of archival Intermemory. In Prec. Fourth ACM Conference on Digital Libraries (DL "99), Berkeley, CA, 1999.]]
14. 14.I. Clarke, O. Sandberg, B. Wiley, , and T. W. Hong. Freenet: A distributed anonymous information storage and retrieval system in designing privacy enhancing technologies. In Prec. ICSI Workshop on Design Issues in Anonymity and Unobservability, Berkeley, CA, 2000.]]
15. 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. 16.M.L. Dertouzos. The future of computing. Scientific American, July 1999.]]
17. 17.S. Floyd and V. Jacobsen. Random early detection gateways for congestion avoidance. IEEE/ACM Transactions on Networking, 1(4):397-413, August 1993.]]
18. 18.A. Fox, S. D. Gribble, Y. Chawathe, E. A. Brewer, andP. Gauthier. Clusterbased scalable network services. In Prec. 16th ACM Symposium on Operating Systems Principles, St.-Male, France, October 1997.]]
19. 19.Gnutella. http : //gnutella .wego. com.]]
20. 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. 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. 22.Hewlett-Packard Corporation. e-speak Open Services Platform. http: //www. e- speak, net/.]]
23. 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. 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. 25.IBM Corporation. IBM WebSphere Application Server. http :// www-4, ibm. com/so f tware/webservers/.]]
26. 26.S. M. Inc. Java Server Pages API. http://java.sun.com/ product s /jsp.]]
27. 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. 28.M. E Kaashoek, D. R. Engler, G. R. Ganger, H. M. Briceflo, R. Hunt, D. Mazieres, T. Pinckney, R. Grimm, J. Jannotti, and K. Mackenzie. Application performance and flexibility on Exokernel systems. In Prec. 16th ACM Symposium on Operating Systems Principles (SOSP '97), October 1997.]]
29. 29.D. Kegel. The C10K problem, http://www.kegel .com/cl0k. html.]]
30. 30.J. Kubiatowicz, D. Bindel, Y. Chen, S. Czervinski, R Eaton, D. Geels, R. Gummadi, S. Rhea, H. Weatherspoon, W. Weimer, C. Wells, and B. Zhao. OceanStore: An architecture for global-scale persistent storage. In Proc. Ninth international Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS 2000), November 2000.]]
31. 31.J. Larus and M. Parkes. Using cohort scheduling to enhance server performance. Technical Report MSR-TR-2001-39, Microsoft Research, March 2001.]]
32. 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. 33.J. Lemon. FreeBSD kernel event queue patch, http://www. flugsvamp,com/~jlemon/fbsd/.]]
34. 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. 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. 36.M. Lutz. Programming Python. O'Reilly and Associates, March 2001.]]
37. 37.Microsoft Corporation. DCOM Technical Overview. h t t p : //msdn. mi croso ft. com/I ibrary/backgrnd/html/msdn_ dcomt ec. htm.]]
38. 38.Microsoft Corporation. IIS 5.0 Overview. http ://w. microsoft, com/windows2000 / i ibrary/howitworks / iis / iis5techove%rview, asp.]]
39. 39.J. C. Mogul. The case for persistent-connection HTrP. In Prec. ACM SIGCOMM'95, October 1995.]]
40. 40.R. Morris, E. Kohler, J. Jannotti, and M. E Kaashoek. The Click modular router. In Proc. 17th ACM Symposium on Operating Systems Principles (SOSP '99), pages 217-231, Kiawah Island, South Carolina, December 1999.]]
41. 41.D. Mosberger and L. Peterson. Making paths explicit in the Scout operating system. In Proc. OSDI '96, October 1996.]]
42. 42.Netscape Corporation. Netscape Enterprise Server. http: //home. net scape, com/enterprise/v3.6 / index, html.]]
43. 43.K. Ogata. Modern Control Engineering. Prentice Hall, 1997.]]
44. 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. 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. 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. 47.X. Qie, A. Bavier, L. Peterson, and S. Karlin. Scheduling computations on a software-based router. In Proc. SIGMETRICS 2001, June 2001.]]
48. 48.M. Russinovich. Inside lgO completion ports, http://www. sysinternals, com/comport, htm.]]
49. 49.O. Spatscheck and L. Petersen. Defending against denial of service attacks in Scout. In Proc. 3rd Symposium on Operating Systems Design and Implementation, February 1999.]]
50. 50.Standard Performance Evaluation Corporation. The SPECweb99 benchmark. http : //www. spec. org/osg/web99/.]]
51. 51.D.C. Steere, A. Goel, J. Gruenberg, D. McNamee, C. Pu, and J. Walpole. A feedback-driven proportion allocator for real-rate scheduling. In Proc. 3rd Usenix Symposium on Operating Systems Design and Implementation (0SD1'99), pages 145-158, 1999.]]
52. 52.Sun Microsystems. RPC: Remote Procedure Call Protocol Specification Version 2. Internet Network Working Group RFC1057, June 1988.]]
53. 53.Sun Microsysterns Inc. Enterprise Java Beans Technology. http :// java. sun. com/products/ejb/.]]
54. 54.Sun Microsystems, Inc. Java Remote Method Invocation. http:// java.sun.com/products/jdk/rmi/.]]
55. 55.Sun Microsysterns Inc. Jini Connection Technology. http: //www. sun. com/j ini/.]]
56. 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. 57.T. Voigt, R. Tewari, D. Freimuth, and A. Mehra. Kernel mechanisms for service differentiation in overloaded Web servers. In Proc. 2001 USENIX Annual Technical Conference, Boston, June 2001.]]
58. 58.L. A. Wald and S. Schwarz. The 1999 Southern California Seismic Network Bulletin. Seismological Research Letters, 71(4), July/August 2000.]]
59. 59.D. A. Wallach, D. R. Engler, and M. E Kaashoek. ASHs: Applicationspecific handlers for high-performance messaging. In Proc. ACM SIG- COMM '96 Conference: Applications, Technologies, Architectures, and Protocols for Computer Communication, pages 40-52, Stanford, California, August 1996.]]
60. 60.M. Welsh. NBIO: Nonhlocking I/O for Java. http: //www.cs. berkeley, edu/~mdw/pro j / java- nbio.]]
61. 61.M. Welsh and D. Culler. Virtualization considered harmful: OS design directions for well-conditioned services. In Proc. 8th Workshop on Hot Topics in Operating Systems (HotOS VIII), Schloss Elmau, Germany, May 2001.]]
62. 62.Yahoo! Inc. Yahoo! reports Second Quarter 2001 financial results, http : //docs. yahoo, com/docs/pr / rel ease794, html.]]
63. 63.Zeus Technology. Zeus Web Server. http://www.zeus.co.uk/ products/ws/.]]

Index Terms

• Networks

  • Network architectures

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • Process management

          • Concurrency control

          • Scheduling