Previous: Select Statement Considered Harmful
I believe that "select considered harmful" article is best piece of writing about software design I have ever done. However, I feel it's kind of hard to grasp.
On one hand, the idea looks suspiciously simple, like something one could have thought of over breakfast and then spent 15 minutes writing it down. In other words, something not worth of paying too much attention to. Whereas, in fact, it's the culmination of a decade of implementing and thinking about distributed systems.
On the other hand, lot of people haven't yet fully internalised Go's model of lightweight processes communicating via channels. Inviting them to go one step further and imagine a world where all the inter-process flow control is done via channels, without a need for the crutch that is select statement, is maybe asking for too much, too early.
Finally, I've tried to keep the essay as succinct and simple as possible. I've deliberately omitted all the comments and footnotes that may have otherwise helped with intuitive understanding of the issue.
Let me thus write down a couple of footnotes that may help with understanding the thinking behind the essay.
Scheduling should be done by the system
At certain level of the system stack we kind of expect not to do scheduling by hand. This may not be the case for assembly language and sometimes not even for C (it's a system language after all) but everywhere above that level the problem of scheduling should be transparently solved either by the operating system or by the language runtime.
Except that it's often not. The most visible case is writing networks servers in C where launching a process/thread per TCP connection is too expensive to be an option and programmer thus has to do all the switching between contexts of different TCP connections by hand.
However, the phenomenon it much more common. You may not have though of it that way, but every time you were doing shared-state concurrency (mutexes, semaphores et c.) you were actually writing an implicit scheduler meant to coordinate all the threads in your program.
Every time you have written an event loop you were facing the same problem: It was really a simple scheduler, wasn't it?
All of these things cause huge amount of pain. And I am not speaking of minor inconveniences here. What I mean is that every single programmer must have wasted significant portion of their working life, oftentimes entire man-years, implementing 100 different variations of do-it-yourself scheduling. Plus debugging it when the scheduler — as one would expect — went awry.
I am a big fan of Go language (although I haven't used it much) because, unlike many other languages, it actually tries hard to solve this grave problem. Goroutines are lightweight enough to be used every time a simple asynchronous task has to be done. Yay! No more hand-crafted scheduling between concurrent TCP connections! Channels, on the other hand, make it possible to do without mutexes, condition variables, semaphores and such. Farewell, scheduling access to the shared state! I won't miss you.
All that being said, select{} statement seems to be focused on providing manual scheduling capabilities to the user.
Let me explain.
Imagine the case where you have multiple worker goroutines, all sending messages to the main routine. They can do so via a single channel. To make the point more obvious, let's make the channel unbuffered:
When happens when main routine reads a message from the channel? What looks like a pretty standard I/O operation is in fact translated by the language runtime into a scheduling decision: The channel picks one of the ready worker goroutines and unblocks it. Nice. The scheduling is almost invisible to the user.
Let's consider a different way of implementing the same thing though. Let us have one channel per worker goroutine. Main goroutine will then select{} on those channels to get the messages. In theory, it works the same as the original one channel design. Channels use simple probabilistic scheduler. So does select. The behaviour should therefore be identical:
The difference though is that in the latter case the user is free to manipulate the set of channels to wait for manually and can thus plug into the system scheduler. For example, they can select{} on high-priority channels first and only if no message is available fall back to selecting on all channels, including low-priority ones.
In short, if we use channel, scheduling is done by the system. If we use select{} scheduling may (or may not!) be done by the user.
Having the statement in the language actually makes sense for the same reason it makes sense to have goto in C: At the end of the day, there will still be a small contingent of programmers who do want to do scheduling by hand.
But be aware! Having the statement in the language doesn't mean it's a necessarily good idea to use it. Think of the goto!
A final question is somewhat tangential but interesting nonetheless: Given that Go is supposed to do scheduling for the user, are the scheduling algorithms versatile enough to satisfy all the users?
The answer is almost certainly negative. There are no goroutine priorities, nor prioritised channels. There are no fancy real-time schedulers. Nothing of the sort. However, the scheduling that is available out of the box is sufficient in 99% of cases. If you are unlucky enough to need something more sophisticated, here's your select statement. Go and use it.
Channels vs. Functions
In the original essay I've asserted that using select statement leads to ugly code. While that may sound controversial, rephrasing it as "scheduling by hand makes the code ugly" is unlikely to be challenged by anyone.
However, there are aspects of the problem that are not directly related to scheduling but still contribute to the ugliness of the code.
Imagine an object. It has some functions, some properties and so on. It also contains a running goroutine. The goroutine does useful work based on commands sent to it via a channel. We would like to hide the implementation of the object behing a nice API and so we create some new functions to steer the goroutine. For example, forbnicate() function will create a 'frobnicate' command and send it to the channel. Nice, isn't it?
Except that it doesn't play well with select{}. If the user is doing their own scheduling, they may want to try to frobnicate three different instances of the object in parallel like this:
for {
select {
case channelToInstance1 <- frobnicate:
case channelToInstance2 <- frobnicate:
case channelToInstance3 <- frobnicate:
}
}
No such thing is possible using frobnicate() function. If all you have is the function you can frobnicate at most one instance at a time. No luck.
What that means is that if select{} is expected to be used, we won't have nice object APIs. The channels will dangle out of the open gut of the object making attempts to hide internals of the object behind nice function-based API futile. Object will expose both channels and functions. Each will have its own parameter syntax, its own invocation syntax and so on. Unlike functions, channels don't even allow to specify output parameters. It's ugly:
However, if we get rid of select, the encapsulation suddenly starts working. Sending a message to channel can be hidden inside a function. If there's a reply, the sequence of sending a request through one channel and getting a reply through a different one can be hidden inside a function.
There's certainly more to be said in favour of select-free programming, but these two footnotes should give you at least a starting point for thinking about the problem.
Martin Sústrik, February 23rd, 2016
Previous: Select Statement Considered Harmful
I find that select is most useful in "internal" bits of implementation, that I don't expose to my external API consumers. In mangos, I use it to handle cases like timeouts, and notifications where the object must wait on some condition before proceeding.
Frankly, I'm not a huge fan of select, and coming as I do from kernel programming, I find condition variables both faster and easier to use in many of the circumstances that I care about. But I would generally not like to expose them to my external consumers either.
That said, a few mangos users have requested that mangos offer select()able API. Its easy to build that on top of mangos, and I've done a proof of concept of it, but I wouldn't want to be preferred — both for the reasons you list here, but also because the extra level of asynchronous operation adds a measurable amount of latency. (And I live in a very low latency world.)
Yes, agreed. How bad is the latency impact in Go, btw? With coroutines implemented in C it's seems to be close to zero.
nice ref to memfrob(3) !
Native server implementations have shunned select() for some time. epoll() and kqueue() are typically used instead due to their scalability. For example, UDT is implemented on Linux utilizing epoll().
I am very new to the concurrency model presented by Go, and I have only developed using a Go descendent, Clojure's core.async. Though my impression is naive and evolving, I have yet to find the channel model to be sufficiently general for many specialized concurrency applications. While I enjoy functional Clojure development, and find the language to be immensely expressive, I find core.async to be unusually limiting in contrast. I ascribe these limits mostly to its Go inheritance, but Clojure's STM does also play here. But I should be fair to Go and understand it more directly. Still, I imagine that it would be particularly limiting to use the channel model for interoperability with native multi-threaded APIs. Imagine trying to wrangle an SMB implementation using channels. My point being, that the model that Go presents is perhaps young and quite radical — it suggests an entirely different kind of systems programming. The model currently has a narrow strong suit for encapsulated server development that which does not interface with other code that have their own concurrency models. But admittedly that niche does include much of what backends accomplish today.
I just wanted to say that I really enjoy reading your posts.
These topics are also central to my interests. I just want to share some of
my thoughts.
I've developed linux-based servers in the past and currently I'm working in the more low level
embedded systems domain. The main problem I'm constantly facing is managing concurrency.
The difficulties stem in my opinion from the fact that, looking from the historical point of view,
the main research area was always transformational systems. Nowadays the balance is moved towards
interactive and reactive systems. It always seem strange to me that the ligthweight concurrency support
already exists in the 'kernel-space', but programmers developing 'user-space' applications must invent
their own solutions in order to meet the performance requirements.
The process/thread approach is well suited to partitioning the work into independent parts
like it is the case in traditional time-sharing. A thread is, in most languages, already a simple state machines.
For example Java: http://www.w3resource.com/java-tutorial/java-threadclass-methods-and-threadstates.php
Shared-state concurrency tries to implicitly reshape this basic state machine. Look for example at the classic
Dining Philosophers Problem (DPD). The standard solution is to model the philosophers as independent tasks
with the shared resource access implemented implicitly using locks. Hundreds of papers were dedicated to
analysing all the pitfalls that one could make using this approach. By implementing the scheduler as a separate,
explicit entity, all the concurrency hazards are eliminated (http://www.state-machine.com/doc/AN_DPP.pdf).
Here is my question: is it possible to eliminate the state machine entirely in this example using your approach?
I don't think that it's always possible to eliminate the state machine and we should focus on
making the cooperation points explicit and keeping the tight intertwining
between purely computational and IO domains from becoming overly complex and, in turn, unmanageable.
I was looking at the Haskell way of dealing with these issues - monads,
specifically the IO Monad. It seems that in this approach the two intertwined trees can be separated, replaced and
transformed easily. It is possible for example to test the system in only purely computational environment or generate
code in other language than Haskell - https://github.com/tomahawkins/atom. This approach also addresses the composability issue
you mentioned.
Here's also an interesting article: https://glyph.twistedmatrix.com/2014/02/unyielding.html
Again, I really enjoy your writings and appreciate the knowledge you provide.
Best regards,
Mariusz
We may be speaking of different things, really. What you mean by "state machine" AFAIU is the mechanism to deal with input that's not full available upfront. In that sense, every stack frame is a simple state machine. There's no coding without state machines in that sense.
What I meant was rather more limited: An explicit piece of code where you save your state, switch to a different task to get back to the original task later on.
My argument was that this kind of thing never has to be done by the user. It can by handled transparently by language runtime and/or OS.
I enjoyed the article you've linked to (https://glyph.twistedmatrix.com/2014/02/unyielding.html), if for nothing else then because the author comes from exactly the opposite the direction that I do. I was burned by explicit context switching. They were, so it seems, burned by the implicit one.
Still, one example to keep in mind while reading the article is OS-based preemptive multitasking. Surely, nobody wants to get back to MS-DOS days with a single program running on a machine. Yet, the switching is comletely implicit. And given that there's good process isolation, nobody really complains about it.
I'm little confused right now… Your problems with shared state concurrency using mutexes/semaphores were not connected to non-deterministic behaviours they cause to be observed while combined with implicit context switching? That is exactly the thing which everybody seems to complain about. The main advantage of Hoare's CSP (channels+coroutines) vs. shared state concurrency is believed to be exactly this property - introduce partial order and make the non-determinism non-observable. It doesn't really matter if there is implicit context switching as long it does not make the mutable state evolve in different ways.
You are right that parallelizing work into independent task can be handled transparently. The problem is that real-life task are seldomly truly independent. There is a part that can be parallelized but some of the work must be serialized (the reduce part in MapReduce). The second part is the problematic one.
Best regards,
Mariusz
Post preview:
Close preview