Thursday, January 5, 2012

Ruby and Concurrency: Design with Actors and Akka

In a semi-recent post we looked at how we might define actors in JRuby using a combination of Akka and code blocks. That post was very focused on the process of creating actors; we didn't necessarily consider how to build systems with actors and/or whether Ruby might be helpful in doing so. There are plenty of issues to ponder here, but before we dig in let's take a step back and talk briefly about some of the characteristics of actors.

Actors implement a shared-nothing model for concurrency. Mutable system state should be contained by one or more actors in the system. This state is not exposed to external entities directly; it can only be accessed or modified via messages sent to the actor. Since the actor is the only player in this drama that can access the state it contains there is no need to lock or synchronize state access. It should be fairly clear that an actor consists of some amount of mutable system state and some logic for handling incoming messages... and not much more.

Okay, sounds great... but how does it work in practice? We'll consider this question by way of an alogrithm that by now should be pretty familiar: prime number generation using the Sieve of Eratosthenes. We considered this chestnut (or perhaps you prefer "war horse" at this point) in a previous post discussing an implementation of this algorithm in the Go language. Let's review that implementation and see what else we can do with it.

The support of lightweight goroutines in Go encouraged a pipeline implementation with one goroutine per discovered prime. We can think of the "state" of this system as the total set of discovered primes. Each goroutine knows only about the prime it contains and the channel where candidates should be sent if they "pass" (i.e. do not divide evenly into it's prime number). Once the goroutine is created it's state doesn't change. New state is added by creating a new goroutine for a newly-discovered prime. State is never deleted; once a prime is discovered removing it from consideration is non-sensical. As a consequence state is completely distributed; no entity in the system knows about all discovered primes.

We also note that the algorithm described here isn't very friendly to parallel decomposition [1]. Candidate values are compared to previously discovered primes one at a time: if the candidate passes the test it's allowed to move on, otherwise no further evaluation occurs. This technique is referred to as "fail-fast" behaviour; if a value fails a test it doesn't lead to any wasteful extra work. The concurrent approach is quite different: compare the candidate to all discovered primes at once and return success only if all tests pass. Comparisons are done independently, so even if the "first" [2] comparison fails all other comparisons still execute. We lose our fail-fast behaviour but gain the ability to decompose the entire process into smaller jobs that can execute in parallel. A trade-off in engineering... surprising, I know.

We'll set out to implement the Sieve of Eratosthenes in Ruby using JRuby and Akka. Our new implementation will have more of a bias towards parallelism; this time we're okay with throwing away some work. Clearly we'll need an actor to compare a candidate to one or more discovered primes; that is, after all, why we're here. We can think of these actors as maintaining the state of our system (just like the goroutines in the Go implementation) so we'll borrow a term from MVC and call these "model" actors. Concurrently evaluating candidates against these models implies an organizing actor that is aware of all models; it seems natural to call this the "controller" actor. To keep things simple we don't want to support an unlimited number of models so we create a fixed-size "pool" and distribute system state (i.e. the set of discovered primes) between these models. When a new prime is discovered the controller will be responsible for adding that prime to an existing model.

The implementation in Ruby looks like this:



Ruby offers a number of features which help us out here. As shown in this implementation messages can be as simple as a list with a leading symbol (used to indicate the message "type") and a payload contained in the remainder of the list. This follows a similar convention found in Erlang, although that language uses tuples rather than lists. Support for destructuring/multiple assignment makes working with these messages quite simple.

Our previous work building actors from code blocks doesn't apply here due to an implementation detail so we define both the controller and model actors as distinct classes. As it turns out this change isn't much of a problem; we're able to implement both classes, a helper Enumerable and a second Enumerable wrapping the controller in less than 140 lines with comments. Full code (including tests) can be found on github.

Spend a little time with JRuby and Akka and it becomes clear that they work well together and form a good basis for building concurrent applications in Ruby.

[1] This is a bit of a loaded statement; you will get some parallelism as multiple candidates move through the "stages" (i.e. goroutines) of the pipeline. That said, this notion of parallelism applies to the system as a whole. The process of determining whether a single candidate is or is not a prime number is still very sequential.

[2] "First" here means nothing more than "whichever test happens to complete and return a value first"

2 comments:

  1. Cool!

    Can you rewrite it to avoid blocking?

    ReplyDelete
  2. Viktor,

    You probably could remove the blocking calls, but doing so would change some of the design assumptions. You could change the models to use #tell to send an :isprimeresponse message back to the controller with an attached boolean values. When the controller received enough responses it could send an answer back to the actor that sent the :next message, assuming the address of that actor were preserved.

    Now assume the caller wasn't an actor but some random bit of Ruby code (like the Primes Enumerable instance in the module). This code has no address for the controller to send responses to. Worse yet the semantics of Enumerable#next require that the same method send the :next message and yield a response. The only plausible way to make this happen is with a blocking call like #sendRequestReply, and once that happens the sketch outlined above falls apart. Now the handler for the :next message must return a result before exiting, which means the actor can't exit quickly and act on :isprimeresponse messages as they arrive. We can minimize the pain somewhat via an asynchronous send to the models using #sendRequestReplyFuture and then iteratively checking the returned futures for values, but that's about the best we can do.

    If we only wanted to interact with other actors we'd probably be okay, but as a general purpose utility it's not clear we can remove the blocking semantics.

    ReplyDelete