Commits

Bryan O'Sullivan committed 97e4e78

Initial draft of slides

  • Participants
  • Parent commits 9968e1d

Comments (0)

Files changed (3)

 ~$
 \.(aux|bbl|blg|dvi|eps|log|out|pdf|ps|tex)$
 ^auto$
+^slides.html$
-all: hs2010.pdf hask17ape-sullivan.ps
+all: hs2010.pdf hask17ape-sullivan.ps slides.html
+
+slides.html: slides.md
+	pandoc --offline -o $@ -s -t slidy $<
 
 hs2010.pdf: hs2010.tex biblio.bib graphs.gnuplot *.dat
 	gnuplot graphs.gnuplot
+% Scalable I/O Event Handling for GHC
+% Bryan O'Sullivan, Linden Lab
+% Johan Tibell, Google
+
+# Demands of the modern networked environment
+
+- Networked apps have to cope with a wide range of load
+
+- Fast, ephemeral clients (traditional HTTP)
+
+- Slow, long-lived peers (Comet, instant messaging, IMAP)
+
+# Surviving the onslaught
+
+- Buggy clients
+
+- Flaky networks
+
+- DDoS attacks
+
+- Use timeouts and rate limits to add robustness
+
+# Implications for code
+
+- We need to respond quickly to events, even with many idle connections
+
+- Cheap timeouts let us deal with flaky/malicious clients
+
+- "C10K" dates back to 1999
+
+- Next horizon: $10^7$ concurrent connections per server
+
+# Programming models: events
+
+- Both sends and receives return immediately
+
+- Events include "received a message", "finished a send"
+
+- On event, find, update, save state, maybe perform an action
+
+- Examples: Twisted (Python), Node.js (Javascript)
+
+# Event-based programming
+
+- _Yay!_ Can be cheap to implement
+
+- _Yay!_ May handle high concurrency
+
+- _Boo!_ Explicit saving of state is a pain
+
+- _Boo!_ Application code tends to sprawl out of control
+
+# Programming models: threads
+
+- Sends and receives block until complete
+
+- Much state is managed implicitly
+
+- Examples: NIO (Java), Eventlet (Python)
+
+# Threaded programming
+
+- _Yay!_ implicit management of local state
+
+- _Boo!_ A poor threading system limits concurrency
+
+- _Boo!_ Managing shared state can be _very_ hard
+
+# Modern Haskell
+
+- Lightweight, powerful, mature concurrency model (< 200 bytes per thread)
+
+- Blocking I/O
+
+- Good state sharing (e.g. STM)
+
+- Timeout management
+
+- Large family of useful libraries
+
+- Native code performance
+
+# So where is (was?) the catch?
+
+- GHC's old I/O manager had some key scaling limits
+
+- `select` system call limited us to ~1000 file descriptors
+
+- Open files/sockets managed via a list
+
+- Timeouts managed as a sorted list
+
+# Our work
+
+- We rewrote GHC's I/O manager
+
+- Better OS integration
+
+- More appropriate data structures
+
+# What does this mean for you?
+
+- We left public APIs untouched
+
+- You get better scalability for free!
+
+- Ships in GHC 7
+
+(Oh, and a new event API for masochists)
+
+# Better OS integration
+
+- Use `epoll` and `kqueue` instead of `select`
+
+- Remove array size limit imposed by `select`
+
+- Drop cost from O($n^2$) to O($n$)
+
+# Connection management
+
+- Big-endian Patricia tree to manage file descriptors (Okasaki, Gill,
+  Leijen)
+
+- Drop cost from O($n^2$) to O($n\ \log\ n$)
+
+# Timeout management
+
+- Use priority search queue to manage timeouts (Hinze)
+
+- Why a PSQ?
+
+- Priority: get/remove the next timeout
+
+- Search: remove arbitrary timeout
+
+- Drop cost from O($n^2$) to O($n\ \log\ n$)
+
+# Performance: event handling
+
+- Long poll benchmark: 64 active clients, $n$ idle
+
+- At low concurrency, GHC 7 almost identical to GHC 6
+
+- GHC 6: crash (`select` limit) at $n = 1,000$
+
+- GHC 7: slowdown starts around $n = 25,000$
+
+- GHC 7: my laptop can still keep up at $n = 300,000$
+
+# Performance: timeout handling
+
+- How many timeouts can we process in 10 seconds?
+
+- GHC 6: 15,000
+
+- GHC 7: 1.5 million
+
+- In 20 seconds?
+
+- GHC 6: 17,000
+
+- GHC 7: 2.7 million
+
+# Future work
+
+- Got a 10gig network? We need one to stress the code enough to tune
+  it further!
+
+- Per-CPU event managers
+
+- May be room for constant-factor improvements in low-level OS code
+
+- Better performance analysis tools
+
+- Windows support (sorry, we're Unix-only right now)
+
+# Thanks!
+
+- Especially to Simon Marlow, for fixing, and finding workarounds for,
+  some exciting RTS bugs
+
+- And to John MacFarlane, for his pandoc tool
+
+
+I can't recommend pandoc enough:
+
+    cabal install -fhighlighting pandoc
+
+I wrote these slides using Emacs, pandoc, and `make`:
+
+    slides.html: slides.md
+        pandoc --offline -o $@ -s -t slidy $<