Tuesday, January 1, 2013

Go Concurrency Constructs in Clojure, part 1

If you look at the programming languages of today, you'd probably get this idea that the world is object-oriented, but it's not. It's actually parallel.... There's all these things that are happening simultaneously in the world and yet the computing tools we have are really not very good at expressing that kind of world view. And that seems like a failing.

--Rob Pike, 2012 Heroku Waza conference


/* ---[ Go ]--- */

The Go language recently turned 3 years old, so it is about 2 years Clojure's junior. I have only started investigating Go and one of the things that has captured my attention are its primitives for concurrency. Rob Pike, the leading spokesman for Go and one of its co-creators, has done a number of interesting talks on Go concurrency patterns and how it is built into the language. If you haven't watched them, here are two that I recommend:

I'll be referring to the first one through this post.

Pike talks a lot about how Go routines and channels are first class entities in the language, with simple syntax and keywords baked in. Go routines are akin to threads that you kick off to run in "the background". Pike's analogy is to think of them like launching a process on the command line with the ampersand. Staying with the Unix analogy, if you launch a process in the background and then need to communicate with it, what do you do? In Unix/Linux you have a number of options, such as a socket, a pipe or some other form of IPC or to use shared memory.

The Go language creators have chosen the "channel" as a core "inter-routine" communication mechanism. Quoting Pike: "The Go model is not to communicate by sharing memory, but to share memory by communicating".

What is called "inter-routine" here would be called inter-process in Erlang or traditional C/Unix programming or "inter-thread" communication in languages like Java. But for Go it is more appropriate to say "inter-routine". Pike emphasizes that go routines are lighter weight than threads. Go routines can be shared or multiplexed onto multiple running threads over their lifetime, avoiding thread starvation issues. They have their own stack frame, but I believe it is managed on the heap (need to research this more).

The roots of the Go routine and Go channel start in Tony Hoare's Communicating Sequential Processes paper (now book). CSP addresses concurrency interaction patterns - how separate processes (in the Unix or Erlang sense), threads or routines communicate and coordinate with each other via message passing. We want constructs that reduce the complexity of inter-process/inter-thread communication using primitives that are easy to use and reason about. This means not having to be a deep expert in a system's memory model in order to do concurrent programming. Instead, it hides semaphores, mutexes, barriers and other low level concurrency constructs in higher-level abstractions.


/* ---[ Go-style CSP in Clojure? ]--- */

My primary interest here is in what support for Go-like CSP patterns exist, or can be made to exist, in Clojure. Clojure, after all, promises to bring sanity to concurrent programming by means of efficient immutable data structures and software transaction memory for mutable state.

Go channels come in two forms: synchronous blocking channels that cannot hold multiple entries and non-synchronous buffered channels that can have multiple entries. I'll explain the nuances of synchronous here in a moment.

The Go spec says: A channel provides a mechanism for two concurrently executing functions to synchronize execution and communicate by passing a value of a specified element type.

Does Clojure have this? There are two things in Clojure or Java we can potentially use to emulate Go channels:

  • Java concurrency queues. In particular, SynchronousQueue, BlockingQueue and TransferQueue.
  • Zach Tellman's Clojure lamina library, whose primary focus is asynchronous event-based programming.

In this blog series, I will introduce the go-lightly Clojure library I built to have Go concurrency constructs. The GitHub repo for it also has many examples, some of which use Java concurrent queues directly, some of which use the lamina library and many of which use the go-lightly library.

Note: I also ran across the Java CSP (JCSP) project, which I haven't investigated yet, but might be something to build a Clojure library around.


/* ---[ "boring" basics ]--- */

In his initial examples to show how Go channels work, Pike uses a background process that is, as he calls it, "boring" - it just prints its name or the word "boring" at random intervals. After listening for a while, the "main" process gets tired and wants to leave or end the conversation.

Here are the first two examples in Go from his 2012 Google IO talk, modified slightly to work from one main function:

Here is the output from each option (single vs. multiple):

$ ./boring-generators single
You say: "boring! 0"
You say: "boring! 1"
You say: "boring! 2"
You say: "boring! 3"
You say: "boring! 4"
You're boring: I'm leaving.

$ ./boring-generators multiples
Joe 0
Ann 0
Joe 1
Ann 1
Joe 2
Ann 2
Joe 3
Ann 3
Joe 4
Ann 4
Joe 5
Ann 5
Joe 6
Ann 6
Joe 7
Ann 7
Joe 8
Ann 8
Joe 9
Ann 9
You're boring: I'm leaving.

See appendix 1 if you would like to compile and run this on your system. I'll frequently list the outputs during this blog series, but it helps to see the latency between print statements to get a better feel for how these examples work.

See appendix 2 for links my GitHub project with this code and to other gists with related code examples.


Pike calls this the generator pattern because the invoked "boring" function creates a (synchronous) channel, then creates a closure that references that channel, launches that closure as a go routine and immediately returns the channel to the calling function.

The go routine sends messages to the channel with the <- operator.
For example, c <- "hello kitty" sends the feline greeting into the channel.

The other function receives messages from the channel with the same operator, by putting the channel on the right side of the operator: <- c.

These are blocking operations with a synchronous channel. If the sender sends a message to the channel when there is no receiver waiting, it will block until a receiver comes and grabs its message off the channel. And, conversely, a receiver will block waiting for a sender if there isn't already one pushing to the channel.

In the multipleGenerators version, two go routines are created, each with its own channel. The receiving "main" function now receives from each channel consecutively in a defined order, which is why you always get Joe's output first, then Ann's.

One final thing to note: we don't explicitly do any work to shutdown the go routines. Go routines will automatically stop operation when the main function exits. Thus, go routines are like daemon threads in the JVM (well, except for the "thread" part ...)


/* ---[ "boring" in Clojure ]--- */

Java has two analogs of a Go synchronous channel: the SynchronousQueue and the TransferQueue.

The SynchronousQueue has the same specs I mentioned above: it allows one sender at a time that will block waiting for a receiver and one receiver at a time that will block waiting for a sender. The "queue", despite its name, has no internal storage. It's size method always returns 0 and its peek method always returns null. If you use just the put method to send and the take function to receive, it behaves like the Go channel in the first example.

The TransferQueue is a more liberal - you can use it like a SynchronousQueue or more like a BlockingQueue where you can put multiple messages on the queue and only block if you try to put onto a full queue (if it is bounded) or take from an empty queue. To use it like a SynchronousQueue, use transfer and take. The API is rich enough that you can find other uses also, such as non-blocking offer and poll methods to send and receive without blocking.

In the go-lightly code base examples, I use both, but here I'm going to stick with the TransferQueue for reasons that will become clear when we get to the Go select statement in the next blog entry.

OK, so the channel will be a Java TransferQueue. How do we implement a go routine in Clojure?

Clojure's future function is similar to a go routine in that it launches a new "routine" (Java thread) with its own stack and flow of execution. The interface is similar too: in Go you give an invoked function to the go statement. You do the same to the Clojure future function.

// launch a go routine in Go
go func() { fmt.Println ("hello kitty") }()

;; launch a thread that returns a future in Clojure
(future (println "sayonara"))

But Clojure futures differ from a go routine in at least two important ways:

  1. A Clojure future launches a new thread (or rather obtains a thread from the Clojure thread agent pool), whereas, as mentioned before, a Go routine is lighter weight than a Java thread. I don't know of any Clojure or Java facilities for creating something equally lightweight, so I will use threads.

  2. Clojure futures are not daemon threads and I don't think there is any way to tell them to be daemon threads. Thus, you cannot give a future an infinite loop and expect your program to close down. If you launch such a future, you would have to either:

    1. Call (future-cancel myfut) on the future, which means you have to retain a reference to the future. You can't just fork-and-forget.
    2. Set a flag, either through shared memory or a message via a channel, that the future will check periodically to see if it should stop. However, if this future is stuck in a blocking call trying to read from or push onto the blocking queue, this approach won't work.

In addition, you also need to call (shutdown-agents) at the end of your Clojure program to shut down the agent/future Thread pool.

Thus, Clojure's future requires more bookkeeping than Go's go.

But Clojure has macros to help, so I've written two macros and some helper functions to lessen the bookkeeping.

The first macro is simply called go and has accompanying stop and shutdown functions. The second macro, go&, is meant for fork-and-forget use so I give it the Unix ampersand in the name. It has the least amount of ceremony, but cannot be controlled through the Java Executor framework like the future and agents threads can be.

And here's my implementation of the boring-generator using it. To match the Go terminology, Finally, I also define the function channel to simply return a LinkedTransferQueue.

While the go& macro is easier to use and more like the actual Go go-routine launcher, it has one downside: it is not REPL-friendly if your go routine doesn't shutdown naturally. In this case it will block on the (.transfer ch) call on line 39 and hang around in memory. And each time you invoke the function in the REPL it creates another daemon, draining JVM resources and memory over time.

Since Go language development is not REPL-based they can get away with it. If you create a main function:

(defn -main [& args]
  (thornydev.go-lightly.boring.generator-tq/multiple-generator&))

and run it from the command line:

lein run

it will behave just like the Go version. You'll get the same output as the Go example above and it will shutdown gracefully instead of hanging.

But to be REPL friendly, I'll typically use go and stop rather than go&.

Another way to handle this in Go would be to close the channel and have the go-routine check whether the channel is closed before continuing.

Unfortunately, this is not possible with the Java concurrency classes mentioned above - they are not Closeable resources.

However, the go-lightly library and the Clojure lamina libraries both provide the notion of a closeable channel, which leads to our next implementation.


/* ---[ A "boring" lamina implementation ]--- */

The lamina library created by Zach Tellman provides constructs for handling evented asynchronous programming. It defines a channel whose purpose is to be a event-driven data structure that represents a stream of messages or events. A lamina channel has basic send (enqueue) and receive (receive or read-channel) functionality, but also is composable with other channels using classic functional programming constructs, such as map, reduce and filter. It also provides very useful fork/join operators.

For the "boring" example, we only need the ability to enqueue, read, and close the channel and check whether the channel is closed.

Since the "boring" go routine stops when the channel is closed, this use of the go& macro is REPL-friendly and works as expected when run standalone from the command line.


/* ---[ More macro goodness ]--- */

Finally, let's add one more macro to clean up that last example. If you've done much Clojure or Lisp programming, you know that a common macro pattern is a with-xxx binding macro that cleans up resources for you.

Clojure in fact has a with-open binding macro that will call "close" on all the things specified in the bindings. So that should work here, right? Well, the devil being in the details, it doesn't. with-open actually calls the Java Closeable interface method .close, not "close". And lamina channels do not implement Java's Closeable interface - they do not have a .close. So I grabbed the source for clojure.core/with-open and made my own (and put it in the go-lightly.util namespace):

(defmacro with-channel-open
  "bindings => [name init ...]

  Evaluates body in a try expression with names bound to the values
  of the inits, and a finally clause that calls (close name) on each
  name in reverse order."
  [bindings & body]
  (assert (vector? bindings) "a vector for its binding")
  (assert (even? (count bindings)) "an even number of forms in binding vector")
  (cond
    (= (count bindings) 0) `(do ~@body)
    (symbol? (bindings 0)) `(let ~(subvec bindings 0 2)
                              (try
                                (with-channel-open ~(subvec bindings 2) ~@body)
                                (finally
                                  (~'close ~(bindings 0)))))
    :else (throw (IllegalArgumentException.
                   "with-open only allows Symbols in bindings"))))

So with that in place we can revise the "boring" lamina implementation:


/* ---[ Looking ahead ]--- */

In the next installment we'll dig into the Go select statement, and further evaluate how to use the Java concurrency queues and the lamina libraries as Go channels.



/* ---[ Appendix 1: Compile and run Go examples ]--- */

If you don't have Go installed, see the golang install guide. On Ubuntu, it is as simple as:

sudo apt-get install golang-go

Next, decide where you want your go projects to live (mine are in $HOME/lang/go/projects). cd to that directory and do:

$ export GOPATH=$HOME/lang/go/projects  # change to yours
$ mkdir src
$ mkdir src/boring-generators  # your Go project name here
$ cd boring-generators
$ emacs boring-generators.go   # or whatever editor you like
$ go build   # this invokes the compiler

You will then have a boring-generators executable that you can run:

$ ./boring-generators

(Note: I didn't find that setting GOPATH was really necessary, but it is in the instructions, so YMMV).



/* ---[ Appendix 2: Resources ]--- */

Alexey Kachayev wrote down the Go code that Pike used in the 2012 Google IO presentation, which doesn't seem to have been made available. Alexey published them as gists. They won't compile out of the box, so I've been modifying them, but wanted to link to his gists: https://gist.github.com/3124594.

Alexey also then brainstormed on ways to implement these examples in Clojure using the lamina library. Those gists are at: https://gist.github.com/3146759

My code for working through these ideas are in my go-lightly project on GitHub.

Links to this blog series:

6 comments:

  1. Michael, this is absolutely fascinating reading!

    I recently had to choose between Go and Clojure for my current project, and although I decided to use Clojure, I pined for the simple concurrency model that Go provides. I've been actively searching for some kind of goroutine implementation for Clojure, and this is the first that I've seen that is even remotely workable.

    Naively, I would have thought that the jvm's stack model made it fundamentally impossible to implement goroutines efficiently (because goroutines rely on Go's segmented stack). If you have any commentary about this, I'd love to hear it. Also, if you have any performance benchmarks I would be very excited to see the comparison.

    Please keep up the great work, your writing is much appreciated.

    ReplyDelete
    Replies
    1. Hi John,

      Thanks for the feedback and I'm hopeful this approach will be useful for you and others. I have at least two more blog entries in the works as I think through the structure and functionality of the (very alpha) go-lightly library. After that, I'll be doing a wiki how-to on the GitHub page.

      To date I have only done a few minor benchmarks of some of the example programs I've written, but nothing of high scale with lots of "go routines". I plan to do more benchmarks later this month and will write those up. Java threads are more expensive than Go routines and you definitely cannot create as many. Right now my Clojure "go routines" are simply threads or Clojure futures. We need to research what is already available in the broader Java/JVM landscape to remedy this or figure out how feasible implementing this ourselves would be.

      My initial focus is just to get the channel, routine and select idioms translated to Clojure idioms and see what it looks and feels like. How do we make it more functional and less imperative?

      Thus, for now it means remembering that go-lightly Clojure routines are threads and should not be abused, but the go-lightly library will provide channel-based concurrency primitives to help program in this style when it makes sense for an application.

      I welcome feedback, critiques and pull requests :-)

      Delete
  2. With the release of core.async, we're getting go-like constructs more idiomatically: http://clojure.com/blog/2013/06/28/clojure-core-async-channels.html

    ReplyDelete
    Replies
    1. Sorry for the delay in responding. Some glitch in Blogger wouldn't let me post comments to my own blog for nearly a week.

      I was actually at the "reveal" of core.async that Rich Hickey did at the TriClojure meetup at Relevance in Durham in late June and spoke to Rich about it afterwards. I would not say that core.async is more idiomatic than go-lightly. In fact, I was pleased how similar they are in API (both having the same take on porting the Go model to Clojure). What core.async delivers that go-lightly does not is true "go routines" that are tied to individual threads, but rather multiplexed onto threads.

      It's great to have a blessed robust CSP model based on Go in Clojure now. Though a little sad to put my library into the archives.

      Delete
  3. Michael, despite core.async relegating go-lightly to history, I hope you feel mighty proud of our accomplishment. You've demonstrated some serious insight and initiative, and the similarities between go-lightly and core.async are nothing but testament to the quality of your thinking. Though I have only just stumbled onto your blog I am really impressed. Well done!

    ReplyDelete
    Replies
    1. Paul - thanks very much for the kind words. I learned a lot by doing the go-lightly library, which was my main goal and was pretty happy with the overall outcome and API. In the end I think it was production worthy, but in a more limited way certainly than core.async, which is a pretty awesome feat of software engineering. One works in the company of great minds in the land of Clojure.

      Delete