Previous: Getting rid of state machines (I)
Next: Structured Concurrency
So, as explained in the previous article, with green threads every state machine can be rephrased as a simple imperative function.
Nice. So we are done, aren't we?
Well, kind of. It's useful to do a reality check though.
And it turns out that in the reality state machines have an unfortunate tendency to spontaneously emerge in the code that was never meant to be a state machine.
Here's an example in pseudo-Go (I am too lazy to try to compile it). This example gets events from two distinct sources, A and B and counts them:
func count(chanA chan string, chanB chan string) {
sumA := 0
sumB := 0
for {
select {
case <- chanA:
sumA++
case <- chanB:
sumB++
}
}
}
Now imagine that communication with A becomes more complex. Let's say that the message from A is composed from a header and a body which are sent to the channel as two separate messages:
func count(chanA chan string, chanB chan string) {
sumA := 0
sumB := 0
for {
select {
case <- chanA:
<- chanA
sumA++
case <- chanB:
sumB++
}
}
}
I assume you already see a problem with that: Receiving the body may block for unlimited amount of time. While it is blocked, no messages from B can be processed.
And here's a fix:
func count(chanA chan string, chanB chan string) {
sumA := 0
sumB := 0
hasHeader boolean := false
for {
select {
case <- chanA:
if !hasHeader {
<- chanA
hasHeader = true
}
else {
sumA++
hasHeader = false
}
case <- chanB:
sumB++
}
}
}
Do you see the state machine? If has a single bit of state (hasHeader) and two steps. The code is slightly ugly but it takes only a little bit more complexity in interaction with A or B to morph it into something really, really hideous.
What we see here is one state machine expressed as a goroutine (entire 'count' function) and another, hand-written and barely visible state machine that receives pair of messages from A. The two are tightly interwoven which is what makes the code look bad.
And of course, there's an easy solution. Just rip out the implicit state machine and turn it into a separate goroutine:
func messageParser(chanIn chan string, chanOut chan string) {
for {
<- chanIn
<- chanIn
chanOut <- "message"
}
}
func count(chanA chan string, chanB chan string) {
chanParser := make(chan string)
go messageParser(chanA, chanParser)
sumA := 0
sumB := 0
hasHeader boolean := false
for {
select {
case <- chanParser:
sumA++
case <- chanB:
sumB++
}
}
}
It would be nice if this technique was completely generic. In other words, if meticulous effort to split any interwoven state into separate green threads would result in a code with no overt or hidden state machines.
Unfortunately, that's not the case.
Specifically, this technique doesn't work when canceling green threads. Imagine that one of the channels in the example is used to cancel the goroutine:
func count(chanA chan string, chanB chan string) {
sumA := 0
for {
select {
case <- chanA:
sumA++
case <- chanB:
return
}
}
}
You can split handling of chanB into a separate goroutine, but that would mean that original goroutine will never get canceled! If you add cancellation mechanism to it, you are back to step one. Uh, oh.
Now I am going to make a strong claim based only on intuition, not on any theoretical insight. I believe it to be true but feel free to attack it (and don't forget to bring counterexamples with you):
"If a language has efficient green threads and built in support for cancellation, every program can be decomposed into set of simple functions containing no implicit or explicit state machines."
To be clear, the built in cancellation mechanism must support wide array of use cases:
- Cancel entire program leaving no resource leaks behind.
- Cancel a subsystem without any leaks.
- Cancel a subsystem when a timeout expires. No leaks.
- Give subsystem a grace period to finish its work before canceling it.
- Grace period should be omitted if the subsystem has no work to do anyway.
- Allow for interwoven cancellation when cancellation of a supersystem happens while cancellation of a subsystem is in progress.
If the cancellation mechanism is not this generic users would have to implement these use cases by hand which will in turn lead to introduction of state machines into the code.
I've been trying to design such a cancellation mechanism for several years and I have repeatedly failed. Finally, I believe I have a solution that may work. I am going to describe it in the next article.
Martin Sústrik, January 25th, 2016
Previous: Getting rid of state machines (I)
Next: Structured Concurrency
I do not understand your problem of cancellation. I haven't worked with goroutines, maybe that is why.
If we look though at the introduction of the messageParser goroutine, I have some comments on it.
In the count function there are two code parts.
a) The first deals with the structure of the program itself. It creates a new goroutine and it passes the responsibility of a job. The first part has zero code on the logic itself. Not only that, if the dependencies are many and the structure is complicated, the code will be difficult to read.
This is called spaggeti code. Spagetti code will arise because of the complexity of the problem itself, not the abilities of the programmer.
The reason of the spaggeti code is that we are trying to write down in sequential mode, writing is sequencial, what is not sequential. The correct representation of the dependencies is a graph.
b) The second part deals with the logic.
The fact that those two types of code can coexist and even intermingle with each other is the worst nightmare one might have.
Secondly, there are two types of interdependencies.
A) Those known at compile time. They are static, thus they do not change.
B) Those that need to change dynamically as the program is executed.
For the first case, static analysis can show which parts of the code need to be executed asynchronously.
Anything that has an external asynchronous input needs to be asynchronously executed from each other.
The second case is trickier because it requires to do what you do here with goroutines. You are transforming the structure of the program itself while you are executing code.
For this case, I am still not sure what is the best way to do it. Certainly, a separation between logic and this code. Maybe there should be more restrictions.
Here's the simplest possible exercise to demonstrate the problem:
Write a goroutine with two arguments, both of them being channels. If it gets a message (N bytes long) on the first channel it writes it to a TCP socket. If it gets a message on the second channel it terminates immediately. Take care to handle the case when there's pushback going on in the TCP socket.
I wouldn't use two channels. I would use only one. And I would close the channel from the creator goroutine.
Anything that is already sent to the channel will be processed. Immediately after, it will close.
https://gobyexample.com/closing-channels
The main question is what you mean by immediately. In my solution, the goroutine immediately stops receiving new input but it processes all the input it received.
But as I said, I have no experience with goroutines.
In your solution a malevolent TCP peer could cause pushback which will in turn block the goroutine in send() function. The goroutine will never exit, creating a resource leak. The behaviour can be used to conduct a DoS attack.
The requirement is to close the goroutine immediately, not later on, when the send() succeeds.
Siliar situation happens when malevolent client opens a connection to server and doesn't send anything. If there's no cancelation mechanism, server will wait for protocol header indefinitely, leaking goroutine, file descriptor, memory et c.
Good point. So there needs to be an out of band cancellation mechanism.
What is of concern to me is how to revert changes that happened if one part of it needs to be cancelled.
If a state change has already been applied by part of the code and then one cancels the remaining process, we are left with inconsistent data.
Exactly. I am going to cover the question of atomicity in the next post(s).
Thank you for the great topic.
I assume there is an extra line "<- chanA" below "if !hasHeader {"
No need for it. The select statement itself reads the first part of the message.
Martin, you need to delete the <-chanA that is below if!isHeader
Hi I think you should delete the <-chanA inside !isHeader
Post preview:
Close preview