Capriccio: scalable threads for internet services

ABSTRACT

This paper presents Capriccio, a scalable thread package for use with high-concurrency servers. While recent work has advocated event-based systems, we believe that thread-based systems can provide a simpler programming model that achieves equivalent or superior performance.By implementing Capriccio as a user-level thread package, we have decoupled the thread package implementation from the underlying operating system. As a result, we can take advantage of cooperative threading, new asynchronous I/O mechanisms, and compiler support. Using this approach, we are able to provide three key features: (1) scalability to 100,000 threads, (2) efficient stack management, and (3) resource-aware scheduling.We introduce linked stack management, which minimizes the amount of wasted stack space by providing safe, small, and non-contiguous stacks that can grow or shrink at run time. A compiler analysis makes our stack implementation efficient and sound. We also present resource-aware scheduling, which allows thread scheduling and admission control to adapt to the system's current resource usage. This technique uses a blocking graph that is automatically derived from the application to describe the flow of control between blocking points in a cooperative thread package. We have applied our techniques to the Apache 2.0.44 web server, demonstrating that we can achieve high performance and scalability despite using a simple threaded programming model.

REFERENCES

• 1: Atul Adya , Jon Howell , Marvin Theimer , William J. Bolosky , John R. Douceur, Cooperative Task Management Without Manual Stack Management, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.289-302, June 10-15, 2002
• 2: Thomas E. Anderson , Brian N. Bershad , Edward D. Lazowska , Henry M. Levy, Scheduler activations: effective kernel support for the user-level management of parallelism, ACM Transactions on Computer Systems (TOCS), v.10 n.1, p.53-79, Feb. 1992 [doi>10.1145/146941.146944]
• 3: A. W. Appel and D. B. MacQueen. Standard ML of New Jersey. In Proceedings of the 3rd International Symposium on Programming Language Implementation and Logic Programming, pages 1--13, 1991.
• 4: A. W. Appel and Z. Shao. An empirical and analytic study of stack vs. heap cost for languages with closures. Journal of Functional Programming, 6(1):47--74, Jan 1996.
• 5: Brian N. Bershad , Craig Chambers , Susan Eggers , Chris Maeda , Dylan McNamee , Przemyslaw Pardyak , Stefan Savage , Emin Gün Sirer, SPIN: an extensible microkernel for application-specific operating system services, Proceedings of the 6th workshop on ACM SIGOPS European workshop: Matching operating systems to application needs, September 12-14, 1994, Wadern, Germany [doi>10.1145/504390.504408]
• 6: Mike Blasgen , Jim Gray , Mike Mitoma , Tom Price, The convoy phenomenon, ACM SIGOPS Operating Systems Review, v.13 n.2, p.20-25, April 1979 [doi>10.1145/850657.850659]
• 7: Robert D. Blumofe , Christopher F. Joerg , Bradley C. Kuszmaul , Charles E. Leiserson , Keith H. Randall , Yuli Zhou, Cilk: an efficient multithreaded runtime system, Journal of Parallel and Distributed Computing, v.37 n.1, p.55-69, Aug. 25, 1996 [doi>10.1006/jpdc.1996.0107]
• 8: Daniel G. Bobrow , Ben Wegbreit, A model and stack implementation of multiple environments, Communications of the ACM, v.16 n.10, p.591-603, Oct. 1973 [doi>10.1145/362375.362379]
• 9: Martin C. Carlisle , Anne Rogers , John H. Reppy , Laurie J. Hendren, Early Experiences with Olden, Proceedings of the 6th International Workshop on Languages and Compilers for Parallel Computing, p.1-20, August 12-14, 1993
• 10: A. Chankhunthod, P. B. Danzig, C. Neerdaels, M. F. Schwartz, and K. J. Worrell. A Hierarchical Internet Object Cache. In Proceedings of the 1996 Usenix Annual Technical Conference, January 1996.
• 11: Perry Cheng , Guy E. Blelloch, A parallel, real-time garbage collector, Proceedings of the ACM SIGPLAN 2001 conference on Programming language design and implementation, p.125-136, June 2001, Snowbird, Utah, United States
• 12: J. Cordina. Fast multithreading on shared memory multiprocessors. Technical report, University of Malta, June 2000.
• 13: D. R. Engler , M. F. Kaashoek , J. O'Toole, Jr., Exokernel: an operating system architecture for application-level resource management, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.251-266, December 03-06, 1995, Copper Mountain, Colorado, United States
• 14: David Gay , Philip Levis , Robert von Behren , Matt Welsh , Eric Brewer , David Culler, The nesC language: A holistic approach to networked embedded systems, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 15: S. C. Goldstein, K. E. Schauser, and D. E. Culler. Lazy Threads, Stacklets, and Synchronizers: Enabling primitives for compiling parallel languages. In Third Workshop on Langauges, Compilers, and Run-Time Systems for Scalable Computers, 1995.
• 16: T. Hun. Minimal Context Thread 0.7 manual. http://www.aranetwork.com/docs/mct-manual.pdf, 2002.
• 17: B. LaHaise. Linux AIO home page. http://www.kvack.org/blah/aio/.
• 18: H. C. Lauer and R. M. Needham. On the duality of operating system structures. In Second Inernational Symposium on Operating Systems, IR1A, October 1978.
• 19: Jonathan Lemon, Kqueue - A Generic and Scalable Event Notification Facility, Proceedings of the FREENIX Track: 2001 USENIX Annual Technical Conference, p.141-153, June 25-30, 2001
• 20: D. Libenzi. Linux epoll patch. http://www.xmailserver.org/linux-patches/nio-improve.html.
• 21: D. McNamee and K. Armstrong. Extending the Mach external pager interface to accommodate user-level page replacement policies. Technical Report TR-90-09-05, University of Washington, 1990.
• 22: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 23: George C. Necula , Scott McPeak , Shree Prakash Rahul , Westley Weimer, CIL: Intermediate Language and Tools for Analysis and Transformation of C Programs, Proceedings of the 11th International Conference on Compiler Construction, p.213-228, April 08-12, 2002
• 24: George C. Necula , Scott McPeak , Westley Weimer, CCured: type-safe retrofitting of legacy code, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.128-139, January 16-18, 2002, Portland, Oregon
• 25: J. K. Ousterhout. Why Threads Are A Bad Idea (for most purposes). Presentation given at the 1996 Usenix Annual Technical Conference, January 1996.
• 26: V. S. Pai, P. Druschel, and W. Zwaenepoel. Flash: An Efficient and Portable Web Server. In Proceedings of the 1999 Annual Usenix Technical Conference, June 1999.
• 27: Hemant D. Pande , Barbara G. Ryder, Data-Flow-Based Virtual Function Resolution, Proceedings of the Third International Symposium on Static Analysis, p.238-254, September 24-26, 1996
• 28: W. Pang and S. D. Goodwin. An algorithm for solving constraint-satisfaction problems.
• 29: Margo I. Seltzer , Yasuhiro Endo , Christopher Small , Keith A. Smith, Dealing with disaster: surviving misbehaved kernel extensions, Proceedings of the second USENIX symposium on Operating systems design and implementation, p.213-227, October 29-November 01, 1996, Seattle, Washington, United States
• 30: Mehul A. Shah , Michael J. Franklin , Samuel Madden , Joseph M. Hellerstein, Java support for data-intensive systems: experiences building the telegraph dataflow system, ACM SIGMOD Record, v.30 n.4, December 2001 [doi>10.1145/604264.604282]
• 31: Olin Grigsby Shivers, Control-flow analysis of higher-order languages of taming lambda, Carnegie Mellon University, Pittsburgh, PA, 1991
• 32: E. Toernig. Coroutine library source. http://www.goron.de/froese/coro/.
• 33: Unknown. Accellerating Apache project. http://aap.sourceforge.net/.
• 34: Unknown. State threads for Internet applications. http://state-threads.sourceforge.net/docs/st.html.
• 35: 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
• 36: R. von Behren, J. Condit, and E. Brewer. Why events are a bad idea (for high-concurrency servers). In Proceedings of the 2003 HotOS Workshop, May 2003.
• 37: T. von Eicken , A. Basu , V. Buch , W. Vogels, U-Net: a user-level network interface for parallel and distributed computing (includes URL), Proceedings of the fifteenth ACM symposium on Operating systems principles, p.40-53, December 03-06, 1995, Copper Mountain, Colorado, United States
• 38: Matt Welsh , David Culler , Eric Brewer, SEDA: an architecture for well-conditioned, scalable internet services, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Threads

General Terms:
Algorithms, Design, Performance

Keywords:
blocking graph, dynamic stack growth, linked stack management, resource-aware scheduling, user-level threads