Peng Li
ABSTRACT
This paper proposes to combine two seemingly opposed programming models for building massively concurrent network services: the event-driven model and the multithreaded model. The result is a hybrid design that offers the best of both worlds--the ease of use and expressiveness of threads and the flexibility and performance of events.
This paper shows how the hybrid model can be implemented entirely at the application level using concurrency monads in Haskell, which provides type-safe abstractions for both events and threads. This approach simplifies the development of massively concurrent software in a way that scales to real-world network services. The Haskell implementation supports exceptions, symmetrical multiprocessing, software transactional memory, asynchronous I/O mechanisms and application-level network protocol stacks. Experimental results demonstrate that this monad-based approach has good performance: the threads are extremely lightweight (scaling to ten million threads), and the I/O performance compares favorably to that of Linux NPTL. tens of thousands of simultaneous, mostly-idle client connections. Such massively-concurrent programs are difficult to implement, especially when other requirements, such as high performance and strong security, must also be met.
- The ADAPTIVE Communication Environment: Object-Oriented Network Programming Components for Developing Client/Server Applications. 11th and 12th Sun Users Group Conference, December 1993 and June 1994.Google Scholar
- Atul Adya, Jon Howell, Marvin Theimer, William J. Bolosky, and John R. Douceur. Cooperative Task Management without Manual Stack Management. In Proceedings of the 2002 Usenix Annual Technical Conference, 2002. Google ScholarDigital Library
- Andrew Appel. Compiling with Continuations. Cambridge University Press, 1992. Google ScholarDigital Library
- Joe Armstrong, Robert Virding, Claes Wikström, and Mike Williams. Concurrent Programming in Erlang, Second Edition. Prentice-Hall, 1996. Google ScholarDigital Library
- Gerard Berry and Georges Gonthier. The Esterel Synchronous Programming Language: Design, Semantics, Implementation. Science of Computer Programming, 19(2):87--152, 1992. Google ScholarDigital Library
- Steve Bishop, Matthew Fairbairn, Michael Norrish, Peter Sewell, Michael Smith, and Keith Wansbrough. Rigorous specification and conformance testing techniques for network protocols, as applied to TCP, UDP, and sockets. In SIGCOMM '05: Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, pages 265--276, New York, NY, USA, 2005. ACM Press. Google ScholarDigital Library
- Brendan Burns, Kevin Grimaldi, Alexander Kostadinov, Emery D. Berger, and Mark D. Corner. Flux: A language for programming high-performance servers. In 2006 USENIX Annual Technical Conference, pages 129--142, June 2006. Google ScholarDigital Library
- Koen Claessen. A Poor Man's Concurrency Monad. Journal of Functional Programming, 9(3):313--323, 1999. Google ScholarDigital Library
- Kathleen Fisher and John Reppy. Compiler Support for Lightweight Concurrency. Technical memorandum, Bell Labs, March 2002.Google Scholar
- Emden R. Gansner and John H. Reppy. A Multi-threaded Higher-order User Interface Toolkit. In User Interface Software, Bass and Dewan (Eds.), volume 1 of Software Trends, pages 61--80. John Wiley & Sons, 1993. Google ScholarDigital Library
- The Glasgow Haskell Compiler. http://www.haskell.org/ghc.Google Scholar
- Tim Harris, Maurice Herlihy, Simon Marlow, and Simon Peyton-Jones. Composable Memory Transactions. In Proceedings of the ACM Symposium on Principles and Practice of Parallel Programming, June 2005. Google ScholarDigital Library
- Galen C. Hunt, James R. Larus, Martin Abadi, Mark Aiken, Paul Barham, Manuel Fahndrich, Chris Hawblitzel, Orion Hodson, Steven Levi, Nick Murphy, Bjarne Steensgaard, David Tarditi, Ted Wobber, and Brian Zill. An Overview of the Singularity Project. Technical Report MSR-TR-2005-135, Microsoft Research, Redmond, WA, USA, October 2005.Google Scholar
- Simon Peyton Jones, Andrew Gordon, and Sigbjorn Finne. Concurrent Haskell. In POPL '96: The 23 rd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 295--308, St. Petersburg Beach, Florida, 1996. Google ScholarDigital Library
- James R. Larus and Michael Parkes. Using Cohort-Scheduling to Enhance Server Performance. In USENIX Annual Technical Conference, General Track, pages 103--114, 2002. Google ScholarDigital Library
- Hugh C. Lauer and Roger M. Needham. On the Duality of Operating Systems Structures. In Proceedings Second International Symposium on Operating Systems. IRIA, October 1978.Google Scholar
- Simon Marlow. Developing a High-performance Web Server in Concurrent Haskell. Journal of Functional Programming, 12, 2002. Google ScholarDigital Library
- Eugenio Moggi. Computational lambda-calculus and monads. In Proceedings of the Fourth Annual IEEE Symposium on Logic in Computer Science, pages 14- 23, Pacific Grove, California, June 1989. IEEE. Google ScholarDigital Library
- John K. Outsterhout. Why Threads Are A Bad Idea (for most purposes). In Presentation given at the 1996 Usenix Annual Technical Conference, 1996.Google Scholar
- Vivek S. Pai, Peter Druschel, and Willy Zwaenepoel. Flash: An efficient and portable Web server. In Proceedings of the USENIX 1999 Annual Technical Conference, 1999. Google ScholarDigital Library
- Rob Pike. A Concurrent Window System. Computing Systems, 2(2):133--153, Spring 1989.Google Scholar
- John H. Reppy. CML: A Higher Concurrent Language. In PLDI'91: Proceedings of the ACM SIGPLAN 1991 Conference on Programming Language Design and Implementation, pages 293--305, New York, NY, USA, 1991. ACM Press. Google ScholarDigital Library
- Olin Shivers. Continuations and Threads: Expressing Machine Concurrency Directly in Advanced Languages. In Proceedings of the Second ACM SIGPLAN Workshop on Continuations, 1997.Google Scholar
- The Twisted Project. http://twistedmatrix.com/.Google Scholar
- Rob von Behren, Jeremy Condit, and Eric Brewer. Why Events Are A Bad Idea (for high-concurrency servers). In Proceedings of the 10th Workshop on Hot Topics in Operating Systems (HotOS IX), May 2003. Google ScholarDigital Library
- Rob von Behren, Jeremy Condit, Feng Zhou, George C. Necula, and Eric Brewer. Capriccio: Scalable threads for internet services. In Proceedings of the Ninteenth Symposium on Operating System Principles (SOSP), October 2003. Google ScholarDigital Library
- Philip Wadler. Monads for Functional Programming. In Proceedings of the Marktoberdorf Summer School on Program Design Calculi, August 1992.Google Scholar
- Matt Welsh, David E. Culler, and Eric A. Brewer. SEDA: An Architecture for Well-Conditioned, Scalable Internet Services. In Proceedings of the Symposium on Operating System Principles (SOSP), 2001. Google ScholarDigital Library
- Nickolai Zeldovich, Alexander Yip, Frank Dabek, Robert Morris, David Mazières, and Frans Kaashoek. Multiprocessor support for event-driven programs. In Proceedings of the 2003 USENIX Annual Technical Conference (USENIX '03), San Antonio, Texas, June 2003.Google Scholar
Index Terms
- Combining events and threads for scalable network services implementation and evaluation of monadic, application-level concurrency primitives
Recommendations
Combining events and threads for scalable network services implementation and evaluation of monadic, application-level concurrency primitives
Proceedings of the 2007 PLDI conferenceThis paper proposes to combine two seemingly opposed programming models for building massively concurrent network services: the event-driven model and the multithreaded model. The result is a hybrid design that offers the best of both worlds--the ease ...
Lwt: a cooperative thread library
ML '08: Proceedings of the 2008 ACM SIGPLAN workshop on MLWe present a cooperative thread library for Objective Caml. The library is entirely written in Objective Caml and does not rely on any external C function. Programs involving threads are written in a monadic style. This makes it possible to write ...
Lightweight concurrency primitives for GHC
Haskell '07: Proceedings of the ACM SIGPLAN workshop on Haskell workshopThe Glasgow Haskell Compiler (GHC) has quite sophisticated support for concurrency in its runtime system, which is written in low-level C code. As GHC evolves, the runtime system becomes increasingly complex, error-prone, difficult to maintain and ...
Comments