Reading list

Some documents that we've found interesting and inspiring. Feel free to add to this list, and please include a short blurb to give us a general idea of what you found interesting.

• Some thoughts on asynchronous API design in a post async/await world – The blog post that started it all.

• More theoretically-oriented threads on our issue tracker:

  • Alternative scheduling models
  • Should our locks (and semaphores, queues, etc.) be fair?

• Asynchronous Everything (Joe Duffy) – Discusses the design of and experiences with async/await in "Midori", an experimental language and OS developed at Microsoft (and AFAICT where async/await started before jumping into C#! but it turns out that their design is actually more similar to Python than C#'s in some key ways...). Don't miss the "challenges" section at the end – I thought the discussion of scheduling was particularly interesting.

• .NET 4 Cancellation – discusses an approach to cancellation based on reified "cancellation tokens", which allows interesting kinds of flexibility. There are definite echoes of this in Trio's current "cancellation scope" design. (Also of interest: how the CLR deals with multiple exceptions from parallel tasks – compare to trio.MultiError – and the the CLR concepts of attached and detached tasks, which have some parallels with our nursery concept.)

• The Go context pattern is also an obvious influence on Trio's cancellation design.

• Erlang and supervisors and "let it crash":

  • The Zen of Erlang – Excellent overview of the "Erlang philosophy" for building concurrent systems, and how the different design ideas fit together.

  • Who supervises the supervisors? (Learn you some Erlang for great good) – A tutorial introduction to Erlang supervisors that goes into more detail about how the actual APIs look and are used. Extremely worthwhile, and Erlang supervisors are obviously a huge influence on Trio's task spawning APIs.

  • Riak and Erlang/OTP (The Architecture of Open-Source Applications) – Riak is a robust distributed database written in Erlang; this article talks about how its put together. Good example of how the ideas described in the papers above are applied in practice.

  • Proposal to add backoff to Erlang supervisor restarts

  • It's about the guarantees – an argument for why they shouldn't add backoff. It doesn't make much sense to me, but maybe I don't get it.

  • Supervisor docs 1, Supervisor docs 2

• Locking in WebKit; parking_lot.rs – the inspiration for trio.lowlevel.ParkingLot.

• Callbacks, synchronous and asynchronous (Havoc Pennington): Argues that in callback-style APIs, every function that takes a callback should document whether it will be called synchronously (immediately on the current callstack) or asynchronously (from the event loop at some later tick), and that every function should pick exactly one of these, never "it depends". Good concrete examples of real systems where synchronous callbacks led to deadlocks. The terminology is a bit confusing, but this is closely analogous to trio's rule that "notification" functions should be synchronous (from the perspective of the caller, so they correspond to Havoc's "asynchronous callbacks"), and somewhat related to trio's rule that blocking functions should always yield.

• Marketplace: Network-aware programming – A theoretical model + implementation of an approach to extending the classic actor model with a richer system for organizing complex collections of concurrent tasks. I haven't really had a chance to dig into this yet, but hopefully soon. (If you do then I'd love a summary :-).)

• Inside Macintosh: Thread Manager – technical documentation for the cooperative scheduling in classic MacOS. It looks like their default scheduling policy was FIFO except that at schedule points the scheduler would peek into the message queue that fed system events into the main thread, and if it was non-empty then the main thread would always be scheduled next. In addition to this, threads could specifically pick which thread to run next, and it was possible for a program to register a custom scheduler callback (!) that would run at schedule points and could pick what thread to run next. You could also disable scheduling for a specific period. Interesting note: the amazing Figure 1-6 showing the hoops you had to jump through to call an async I/O routine from a cooperative thread.

• How Erlang does scheduling – discussion of erlang's scheduling strategy for achieving low-latency operation.

• Asynchronous Exceptions in Practice – short article about asynchronous cancellation in Haskell. Not very directly relevant, because Python doesn't have async cancellation (except for KeyboardInterrupt) and isn't functional/pure, but an interesting perspective from another part of the computing universe.

• Rich Felker's blog posts on pthread cancellation: 1, 2, 3, 4. The details are all totally different because C, but the overall semantics and issues are remarkably similar.

• go channels are bad and you should feel bad – ignore the name, it's an interesting critique of go channels from the perspective of Hoare's CSP

• Andy Wingo's posts on concurrency from a Guile Scheme perspective: an incomplete history of language facilities for concurrency, growing fibers, a new concurrent ml. The core fibers stuff ends up being extremely similar to trio's task model. The Concurrent ML stuff is super cool – essentially it's a version of golang-style CSP where your select primitive is extensible, so you can select on arbitrary blocking calls. Or at least, arbitrary atomic ones, I guess. This post is also useful. There is some temptation to rewrite a bunch of stuff in trio to get rid of _nowait etc. by making them all operations. See #242.

• If we're reviewing communication models, then I guess tuple spaces should get a mention. (Brief overview.) I'm less immediately enamored of them than Greg though... in practice I think you need to use a single entry in the tuple as a key to enable efficient matching (IIUC this was a common restriction in practical systems), and then at that point they become... not very different than a set of channels, except with a weird global namespace thing going on and no backpressure? QIX is also interesting. Maybe I should look a little harder to figure out if that's actually true.

• Kill-Safe Synchronization Abstractions: haven't read this yet, but it seems potentially very relevant to some issues we run into around cancellation.

• Deconstructing Deferred: Guido's review+critique of twisted Deferreds

• Independent re-inventions of some of the core "nursery" ideas (both predate Trio, but I wasn't aware of them):

  • rayon::scope
  • Structured Concurrency – Martin Sústrik (his other blog posts around then are also interesting and relevant, though I think he overestimates the value of channels – he notes somewhere he hasn't actually used them, and is trusting the Go docs: Getting rid of state machines (I), Getting rid of state machines (II), Select statement considered harmful, Footnotes to "select statement considered harmful")

• Pull > Push: Please stop polluting our imperative languages with pure concepts, or: Monads considered harmful – interesting talk by Ron Pressler arguing that use of monadic tricks like futures are a poor match to imperative languages

• Volatile and Decentralized: A Retrospective on SEDA – This one's a bit further afield, but still interesting I think. SEDA is an influential architecture for building servers, that emphasizes observability and graceful degradation when overloaded. This blog post is a retrospective on the idea, by the original creator.