Sunday, June 21, 2009

Pondering Actor Design Trades

There's been a lot of discussion of the Scala actors library lately, much of it critical, and a recent flurry of alternate implementations.  The alternate implementations (except my languishing state-based one ;-) all have one thing in common:  They are several orders of magnitude simpler.  Writing a basic actor implementation is actually pretty trivial, especially given java.util.concurrent classes that provide a decent chunk of the functionality in Scala actors, all for free on JDK5+.  So this begs the question few questions:

  1. Why is the standard Scala actor implementation so complex when others have done it in a such simpler fashion?
  2. Is it better to have one, big actor library that supports a wide variety of use cases, or a bunch of smaller ones targeted at specific niches and programming styles?
  3. If there are to be a bunch, should they just be conceptually similar (e.g. all based on the actor model), or should there be interoperability among them?

I'm not going to answer these questions now.  Instead, I'm going to try to start laying out some of what I believe to be the key characteristics of an actor implementation, and how they detract or enforce one another.  So here it goes:

  1. Guarantees
  2. Expressivity
  3. Extensibility
  4. Performance
  5. Scalability

Guarantees

The purpose of a concurrency framework is to make concurrency easier.  Concurrency is hard largely because it is extremely difficult to reason about, and thus concurrent code tends to be hard to write, laden with bugs, and subject to various odd pitfalls.  By providing various guarantees, a concurrency framework makes it easier to reason about concurrent code.  Actors are intended to free the programmer from worrying about things like locks, semaphores, thread management, etc. by encapsulating all that complexity behind a simple interface, assuming the programmer follows some basic rules like "no shared mutable state among actors."

The problem with guarantees is that in they tend to break down in the presence of limited CPU and memory resources.

Expressivity

Expressivity is difficult to define.  For purposes here, I'm going to define it as the degree to which a concise, natural expression of the programmer's intent is supported, and illustrate it by comparing Scala Actor to Lift Actor.  Scala Actors allow you to execute logic independent of message processing (note: this a violation of the theoretical model for actors) by simply placing it in the act method.  Lift Actors, on the other hand, are only triggered when they receive of message (this is consistent with the theoretical model).  For example, this makes it so that Scala Actors can do things such as perform possibly costly setup operations in their own thread before they start listening for messages.  In order to accomplish this in the Lift model, the programmer must create the actor and then send it some sort of "init" message.  The same effect can be achieved with both implementations, but it is more naturally supported by Scala Actors.  Of course there is a tradeoff here, as deviating from the theoretical model potentially weakens any guarantees that the model may provide.  The Scala Actor way also implies that an Actor has an explicit lifecycle, which as we'll see later has other significant implications.

Another example is what I'll call the "nested react pattern."  It is relatively common to want an actor to take on a different behavior after processing a message, thus altering which messages are ignored and how the received messages are processed.

loop {
 react {
    case 'foo => { 
      // do some stuff...
      react {
        case 'bar => // do some other stuff... 
      } 
    } 
  } 
}

The code above alternates between processing 'foo messages and 'bar messages.  This can be done with Lift Actor as well, but the expression is a little less natural:

class MyActor extends LiftActor {
  private val fooMode: PartialFunction[Any, Unit] = {
    case 'foo => {
      // do some stuff
      mode = barMode
    }
  }
  private val barMode: PartialFunction[Any, Unit] = {
    case 'bar => {
      // do some other stuff...
      mode = fooMode
    }
  }
  private var mode = fooMode
  protected def messageHandler = mode
}

Finally, Lift Actors exclusively use an event-based model and have no support for blocking on a thread while waiting for a message, and thus looses the ability to express patterns such as the following:

loop {
  react {
    case 'converToNumber => {
      val i: Int = receive {
        case 'one => 1
        case 'two => 2
        case 'three => 3
      }
      reply(i)
    }
  }
}

Extensibility

For purposes here, I'm going to use "extensible" to mean that a piece of software is extensible if capabilities can be added without modifying the core or breaking its semantics in a amount of effort proportional to the size of the extension.  This is narrower than the traditional definition of extensibility, which also covers the ability of a system to evolve internally.  A good example of extensibility is the ability of both Scala Actors and Lift Actors to allow the user to specify a custom scheduler.  Other examples could include adding control structures, using a different data structure for a mailbox.

The challenge with extensibility is that in order to enable it, what could otherwise be treated as the internal bits of the library must instead have well defined interfaces for components along with appropriate hooks for inserting them.  For example, a while ago I did some work to make the MessageQueue used for the mailbox overrideable (it has temporarily been overcome-by-events due to other changes).  This is a small example, but it shows how extensibility requires a greater degree of forethought.

Extensibility also benefits substantially from simplicity.  Scala Actors are almost impossible to extend from outside the scala.actors package because of their heavy reliance on package-private methods and state (mostly fixed here, but I broke remote actors in the process so no patch yet).  Lift Actors, on the other hand, are very extensible, at least within the bounds of their design (purely event-based actors with no explicit lifecyle).  Many of the flow control mechanisms could be implemented on top of the baseline approach.

At this point we see that extensibility has an interesting relationship with expressivity.  I previously claimed that Scala Actors were more expressive because the wide variety of control structures they provide (and I didn't even touch on some of the DSL-like functionality that enables all sorts of interesting things).  However, given Lift Actors far simpler and more extensible foundation, there is much more opportunity to create custom control structures as extensions to Lift Actors without modifying the core.  Thus, if you are willing to do some lower-level programming, it could be argued that Lift Actors are in reality more expressive due to their extensibility.

Performance and Scalability

For purposes here, I'm going to treat performance as the rate a which an actor can receive and process messages at a relatively small, fixed number of simultaneous actors.   This means that improving performance in largely a matter of reducing the time it takes from when a message is initially sent to when user-code within the actor begins processing the message, including minimizing any pause between when an actor finishes processing one message and is available to start processing the next.  For moderate numbers of actors, performance is often maximized by having one thread per actor, and having the actor block while waiting for a message.  Given enough actors, the memory requirements of using a thread for each actor will eventually cause more slowdown than cost of scheduling a new reaction for each message.  This is illustrated in Philipp Haller's paper, "Actors that Unify Threads and Events" in the following graph:

Note that the above graph covers a microbenchmark running a simple, non-memory intensive task, and that the thread line is not a measurement of thread-bound actors, but rather of a simple threaded implementation.  However, my own benchmarking has shown that receive-based (ones that block on a thread) compare to event-based actors in almost the same way as threads to event-based actors in the above graph.  Also, remember that given a real application where heap space is needed for things besides the stacks of thousands of threads the point where the JVM throws an OutOfMemoryError will be much farther to the left.  There are also more subtle issues.  One of my first experiences with the Scala Actors library was creating a deadlock.  I created more thread-bound actors than the scheduler wanted to create threads, and thus actors were stuck blocking on threads waiting for messages from an actor that hadn't started yet because there were no available threads.  In other words, blocking can lead to situations such as deadlock, starvation, and simply extreme forms of unfairness with respect to how much CPU time is allocated each actor.  These all go against highly desirable guarantees that a actor library should provide outside of extreme circumstances.

Ultimately event-based actors make the better model.  For one, part of the reason why event-based Scala Actors are so expensive is that they suspend by throwing an exception to return control from user code to the library.  While exceptions have been heavily optimized in the JVM, especially in recent versions, they are still substantially slower than normal return paths.  Scala Actors need to use exceptions to suspend is a consequence of their expressivity.  Basically, because the library as little or no knowledge of what an actor is doing within a reaction, it cannot rely on traditional returns without introducing special control structures (see reactWhile numbers in one of my previous blogs).  Lift Actors, on the other hand, have do not need to use exceptions for control flow because the message processing cycle is essentially fixed - user code cannot intersperse weird (or even not-so-weird) patterns within it, or mix in blocking receives with event-based ones.  Another potential optimization of event-based actors is to have them block if there are plenty of threads available, and then release it if the thread they are on is needed by the scheduler.  To my knowledge this optimization is not implemented anywhere, but I think it would be relatively straight forward.  The only problem is that the actor becomes more tightly bound to its scheduler.

Parting Thoughts

Ultimately, time and community willing, I'd like to evolve what is here, plus solid treatment of a lot of lower-level details, into a Scala Improvement Document (SID).  There are a lot of subtle trades involved, and I think producing a general-purpose actors library is at least an order-of-magnitude more difficult than producing a special-purpose one.  I also believe that if an actor implementation is part of the standard library, then it should provide the necessary extension points for when users need something special-purpose they can create it and still leverage components of the standard library and interoperate with other actors.  In order words, I think it should define both the interface portion of an API along with providing a solid implementation.  I don't think we'll even get their without a clear and common understanding of the various considerations involved.

Sphere: Related Content

14 comments:

yonkeltron said...

this is a fantastic start and i see no reason why it couldn't get to be a SID. great post.

Brian Burg said...

I've been following your state-based rewrite, but haven't been following as closely since the last big series of discussions about actor implementations on the mailing lists.

I think a SID would be a good idea, if only to bring a more centralized debate to the design discussions happening in various places. You and others have made a lot of salient points towards various designs, but it's hard to summarize all the various points across various threads and lists without having made some of the points.

Furthermore, I'm interested in the design choices which enable various analyses on actor usages (for example, to statically approximate deadlock or stuck-freedom). Your post here is a good starting point for me to investigate further. Keep on posting!

Jonas said...

Great post.
Exactly the trade offs I did when I created my own actors library. Trading expressiveness over configuration and speed.
/Jonas

Patrick Wright said...

One thing I would like to see is a general purpose benchmark that could be applied across the various actors library implementations. Right now I see blog entries pop up with claims about performance and it's difficult to compare them. I'm sure some tests (like ping pong) could be used as a starting point, although it would be important over the long run to build out a more comprehensive test suite.

Thanks for the write-up
Patrick

Dan Chamberlain said...

Hi, I stumbled across this blog and enjoyed reading the post. Would it be possible to get names or links to the various actor implementations?

M said...

Dan,

You may find the following useful

http://www.javaworld.com/javaworld/jw-03-2009/jw-03-actor-concurrency2.html

Tony Morris said...

The problem with Scala's actors can be summed up pretty quickly: "default mutability with endless attempts to tack on immutability". This inflexibility provides no benefit.

Functional Java and Scalaz do it the other (right) way around.

Erik Engbrecht said...

Tony,
Good point, and I agree 100% with the sentiment. Put I'll point out that the Scalaz actor implementation does indeed contain a minimal amount of mutable state.
http://code.google.com/p/scalaz/source/browse/trunk/src/main/scala/scalaz/concurrent/Actor.scala

You see a ConcurrentLinkedQueue in there, which is used for the mailbox, which is mutable. You can't get away from having at least a small amount of mutable state.

For reference:
http://java.sun.com/j2se/1.5.0/docs/api/java/util/concurrent/ConcurrentLinkedQueue.html

Erik Engbrecht said...

Tony,
There's also an AtomicBoolean hiding in there. I was wondering how it kept track of its suspended-or-not state. I think mailbox+suspended-or-not represents the absolute minimal amount of mutability.

I can't say that I 100% grok Scala Actor, but it looks to me like it holds a thread as long as it has messages to process in its mailbox. Given thread pool with a max size and a lot of very busy actors, this can lead to starvation problems because the busy actors never let go of their threads. The starvation problems can then lead to deadlock.

Runar said...

The Scalaz actor doesn't hold threads. It dequeues its mailbox by applying the Strategy to its Effect on messages. The Strategy decides if a thread is held or not.

Erik Engbrecht said...

@Runar - Ahhh...I see that now. Thanks.

Raoul Duke said...

to blur the lines more, i'm curious how Clojure's "agents" play out, as well. certainly Clojure suggests people use non-side-effecting, immutable-persistent approaches.

David Pollak said...

Erik,

I think you missed a couple of pieces of the Lift Actor feature set.

The messageHandler method can be arbitrarily complex which means that it can perform the same kind of operations that the Scala Actor act method can perform in terms of initialization or "between message" processing.

In terms of changing message handling, you gave an example of doing it a very ugly way with LA and a very pretty way with SA. One could very, very easily mix in code to make LA code as pretty as SA code.

Lift Actors support blocking the current thread waiting for a Future to be satisfied or for the response from message send.

As a practical matter, based on the dozen+ projects I've done with Actors, Lift Actors have all the semantics that I've actually used in production code.

Erik Engbrecht said...

@David,
re: arbitrarily complex message processing in LA
I didn't miss this, although perhaps I didn't give it it's full due. It's possibly to layer up pretty much anything on top of LA's message processing. That's my point - the user-programmer has to layer it up. As these layers build up, complexity increases. If it's done right, the layering will probably give you something at least as expressive as SA but considerably more robust and tractable. But done wrong you would get spaghetti.

re: changing message handling
If there's a more elegant way than I showed, which I don't doubt, then please share. I'm sure it could be layered in, but as you layer more stuff in it become much harder to control the complexity.

re: futures vs blocking
I see different intended semantics here but don't doubt you could translate between the two for equivalent behavior.

re: practical matter
Yes. This is undoubtedly true, at least for now, and I think a compelling argument could be made that making more complex patterns commonplace would be a step backward. After all, an individual Agha actor isn't even Turing complete. Only a full configuration achieve Turing completeness. But...there are some really neat things SA's model allows you to do. Some of them are seem dubious, but it's hard to ignore their expressive power.