Monday, March 12, 2012

My Actor Epiphany

One of the great strengths of Scala is that is contains support for multiple different forms of parallelism. You have access to the Java thread libraries for anything that you want to do at a low level. However, you also have built-in data parallelism through the parallel collections and support for the actor model as well. At a certain level, the actor model is fairly simple, an actor is like an object that can have a thread associated with it so that different actors can be doing things at the same time. It was a model that I had imagined using without really knowing about it. However, having a description of something isn't the same as really understanding it. A few weeks ago, while working on project descriptions for my book, the real implications finally clicked.

Before going into the details of the moment of epiphany, let's dig a bit deeper into the actor model. With normal objects, you make the object do something by calling a method. For actors, you send a message. The syntax can be similar, and they sound very similar, but there is a huge difference in semantics. When you call a method on an object, the current thread moves over to run the code in that method. When you send a message to an actor, the current thread stays with the current actor. The message will be processed by another thread. Typically, messages do not have "return values." They can, but this impairs the parallelism so you want to avoid it is possible. The message gets placed on a queue for the actor and that actor will get to the message in the order of the messages it has received. If a response is needed, a message can be sent back to the original actor.

To make the actor model work, one of the key aspects is that if you are going to have mutable data, it exists in a single actor. You never allow two separate actors to mutate the same data at the same time. That way you avoid race conditions. In Scala this is often done by making sure that all messages are immutable and you never call methods on other actors. Actors only interact by sending immutable messages (typically case classes).

This was all in my head, and it all made sense. However, I can say that I didn't really grok it until I started picturing the MUD project using actors. For those who are not old enough or weren't geeky enough when they were younger, a MUD (Multi-User Dungeon) is multi-user text-based RPG. Normally a MUD was pretty hack-and-slash. There were other things like MOOs that were more about the role-playing part. Think of World of Warcraft with text instead of graphics.

The normal object-decomposition of a MUD has characters, rooms, items. Characters move between rooms and pick up items. The simplest implementation of this uses one thread to handle the networking part of logging in and a second thread to run the game loop. You keep a sequence of characters and run through them. You could also have a priority queue and use events for scheduling. The bottom line of this approach is that it has one very busy thread and one thread that is mostly asleep. It does not scale up.

So my naive thought on making it actor based was to make the characters into actors. After all, they are the things moving around and doing stuff. If they are actors, they each get their own thread and things start happening in parallel. There is only one problem, what happens when two players do something at the same time that deals with the room they are in? For example, they both go to pick up the same object at the same time. That is a classic race condition. Now, it really isn't a problem when one character or the other gets the item. In fact, threads are probably more fair than the normal loop where the order of the sequence will determine who actually gets the item. The problem is that if you make normal method calls on the room, then you can have a situation where both characters get the item because the race condition overlaps the activities. That is not acceptable. Putting in standard synchronization seems the wrong way to go. Actors are supposed to have to prevent you from doing that.

The answer is, of course, very simple. make the rooms into actors as well. This isn't mind blowing, but when the full implications sunk in for me, it really helped me see how the actor model works in general. Now when two characters go to pick up the same items, they send messages to the room. Those messages get queued in a particular order. When the first is handled, it removes the item from the room and sends a message back to that character saying they got the item. When the second message is handled, it finds that item is no longer present and sends back a message to that effect. The end result is exactly what we want. All threading problems go away and the system can now scale to very high concurrency. The key idea here is that you need to broaden the image of what should be an actor. Actors are not just the things that are active. They are also anything that might be acted upon by two actors at once.

I'm still trying to figure out if I can do rings simulations using actors. Perhaps I'll try that some this summer using Akka 2.0. If I find anything that works, I will definitely blog on it.