The hardware we rely on is changing rapidly as ever-faster chips are replaced by ever-increasing numbers of cores. As a result, concurrency and parallelism, niche features today, will soon be a basic requirement for most software. Application developers seeking concurrency solutions have discovered that shared-state concurrency (employed by Java and other imperative languages) comes up short when compared to functional models that promise better reliability and scalability. In this two-part article Alex Miller introduces the actor concurrency model, which has been popularized by Erlang and more recently adopted by Scala. In Part 1 you'll be introduced to the actor model and its benefits; in Part 2 you'll learn how to use it on the JVM. Level: Intermediate
As programmers we know that our software lives on top of hardware, which for decades has relied on chips getting faster at an unrelenting pace. Moore's Law famously states that the number of transistors on a chip will double approximately every 18 months. This exponential law has held true for nearly four decades. and has even exceeded that pace. Intel chips had a few thousand transistors in the early 1970s. The chip in the computer you're reading this article with probably has hundreds of millions of transistors, and newer quad-core chips have several billion.
Until recently, the increase in chip counts (and reduction in size) has made chips faster, increased the number of pipelines, and dramatically increased the number and size of on-chip caches. But hardware crossed a boundary in the early 2000s: chips got big enough and cycle speed got fast enough that a signal can no longer reach the whole chip in a clock cycle -- a physical and architectural limit that will be difficult to breach. Yet the transistors per chip continue their unrelenting exponential march. Instead of increased speed per core, we are now seeing an increase in the number of cores per chip. CPU speeds are likely to stay relatively flat or possibly even decrease in the near future in the service of reduced heat and power consumption (see Figure 1). The multicore era is well under way, and it will change the way we write programs -- a reality that many software developers have yet to face.
Right now you probably use a dual-core machine for day-to-day work, or maybe a quad-core if you're lucky. You might be deploying your server application to an 8-core machine. The concurrency model that most popular languages use now -- shared-state concurrency -- can make good use of multiple cores and result in fast and efficient software. But if the number of cores doubles every 18 months, in a decade we will be dealing with thousands of cores. (This seems ridiculous, but exponential curves always seem ridiculous to our feeble wetware. Forty years ago, the growth in transistor count to today's levels seemed ridiculous and unsustainable.) The prospect of multicore systems of this magnitude threatens the viability of the shared-state concurrency model. This article introduces you to a robust alternative -- the actor concurrency model -- and explains how it is implemented in a 20+-year-old yet increasingly relevant functional language: Erlang.
Shared-state concurrency
The most popular languages today rely on mutable shared state and locks as a model of concurrency. A typical example of multithreaded code is the Counter class in Listing 1.
Listing 1. A typical synchronized Counter class in Java
public class Counter {
private int count = 0;
public synchronized int increment() {
return ++count;
}
}
Counter is a thread-safe class that maintains a counter (the shared state) and protects access to that state by allowing only one thread at a time to read or modify that state. In Listing 1 that protection is provided by the synchronized block, but it could also be provided by explicit Lock objects.
If you've written programs with shared-state concurrency, you've likely encountered the legions of dragons that can arise. If mutable state is not modified and read under the scope of a lock, you might not see the latest version of the value from another thread. Or threads can obtain multiple locks in differing orders, leading to deadlock. Or the necessity for locking can lead to lock contention.
Perhaps the most difficult aspect of concurrent programming is that it's quite easy to combine several properly written concurrent components and thereby produce a system that either is broken or performs poorly. The composite system can be broken if the independent components modify state under different independent locks but the program requires atomic operations that modify state in both components. You can address this problem in a variety of ways with careful architecture, by exposing the locking semantics of the components, or by adding new layers of locks over the components. However, most of the easiest ways to deal with these issues result in poor performance or unmaintainable code.
Whether shared-state concurrency can scale is an equally important question. Will it scale to 16 cores? 32? 1000? Some parts of your program will naturally scale up. If you've got a thread pool working on a set of parallel tasks, it's entirely feasible to scale that to a larger number of cores. But in general, much of your program does not consist of discrete tasks that can be easily made parallel. Amdahl's Law is commonly used to calculate the maximum benefit from increasing the parallel parts of your program. But the sad fact remains that as you scale, the non-parallel parts of your program are the ones that matter, and you can't parallelize them away.
Actor concurrency
So what's the alternative? The actor model of concurrency has recently gained prominence, largely thanks to some success achieved by its flagship language, Erlang.
The actor model consists of a few key principles:
- No shared state
- Lightweight processes
- Asynchronous message-passing
- Mailboxes to buffer incoming messages
- Mailbox processing with pattern matching
Let's look at these principles in more detail. An actor is a process that executes a function. Here a process is a lightweight user-space thread (not to be confused with a typical heavyweight operating-system process). Actors never share state and thus never need to compete for locks for access to shared data. Instead, actors share data by sending messages that are immutable. Immutable data cannot be modified, so reads do not require a lock.
Messages are sent asynchronously and are buffered in an actor's mailbox. A mailbox is essentially a queue with multiple producers (other actors) and a single consumer. A particular actor is driven by receiving messages from the mailbox based on pattern matching.
Some key assumptions are built into this model:
- Processes are cheap (in memory) and fast to create
- Processes are small and thus large numbers of processes can be created
- Processes are not bound to kernel threads and can be efficiently scheduled in user space
- The scheduler requires the ability to pause and continue process execution
- Messages can be retrieved by efficiently pattern-matching messages in the mailbox
Erlang
The actor model has most famously been associated with Erlang, a functional, dynamically typed language invented in 1986 at Ericsson. Erlang was designed for creating applications (such as telephone switches) that must run nonstop. That requires the code to be hot-swappable, distributed, and robust in the face of errors. Erlang was open-sourced in 1998 and has gained prominence in the last few years as concurrency has become a concern. A complete overview of Erlang is outside this article's scope, but I'll give you a quick introduction to the language's key aspects.
Erlang programs are compiled and run in a virtual machine, but you can also use an interactive shell to explore the basics. Erlang variables, which start with a capital letter or a _ character, can be assigned only once, unlike in most other languages. Listing 2 shows an example trace in the Erlang shell with a Value variable.
Listing 2. Erlang variables
1> Value = 4.
4
2> Value.
4
3> Value = 6.
** exception error: no match of right hand side value 6
In this trace you can see expressions being entered on the lines starting with 1>, 2>, and 3> and the response from the shell on the following lines. Line 1 assigns the value 4 to the Value variable. Line 2 returns the value of Value. Line 3 demonstrates that Value can't be reassigned to a new value because it is already bound to the value 4.
Actually, = is not an assignment operator at all in Erlang. It is really a pattern-matching operator. In the case of an unbound variable on the left-hand side, the pattern is unmatched and will bind a value from the right-hand side. But that's just the beginning of what = can do.
Words starting with lowercase letters are atoms -- fixed symbols that always represent a constant, number, or string of the same name, even across machines. A tuple is a fixed-size set of heterogenous values and is specified with { }. Here we match a variable with a tuple of atoms:
Stooges = {larry, curly, moe}.
You can also put tuples on the left side and use variables and the pattern-matching = to extract values from a tuple on the right side:
{Stooge1, Stooge2, Stooge3} = {larry, curly, moe}.
Here the variables Stooge1, Stooge2, and Stooge3 match the atoms larry, curly, and moe.
Lists contain a variable number of elements and are represented in [ ]. The | (pipe) is used to separate the head element from the rest of the list (similar to car and cdr in Lisp). In Listing 3 we build a list and then extract the list's head and tail with pattern matching.
Listing 3. Lists
1> List=[1,2,3].
[1,2,3]
2> [First | Rest]=List.
[1,2,3]
3> First.
1
4> Rest.
[2,3]
Functions are first-class values, as you would expect in a functional language. They are defined by a function name and the number of parameters, using a simple syntax. Here we match the anonymous function to the Square variable. You can then execute it or even create functions that return functions, like the TimesN function in Listing 4.
Listing 4. Functions
1> Square = fun(X) -> X*X end.
#Fun<erl_eval.6.13229925>
2> Square(5).
25.
3> TimesN = fun(N) -> (fun(X) -> N*X end)
3> end.
#Fun<erl_eval.6.13229925>
4> lists:map(TimesN(10), [1,2,3]).
[10,20,30]
At the end of Listing 4 you can see a call to the function map in one of the most important Erlang modules: lists.
Normally you define Erlang code in source files with the .erl extension. Each source file can declare a module and which functions are exported or imported to that module. For example, Listing 5 is a definition of the mymath module, which has two functions -- square and fib.
Listing 5. The mymath.erl module
-module(mymath).
-export([square/1,fib/1]).
square(Value) -> Value*Value.
fib(0) -> 0;
fib(1) -> 1;
fib(N) when N>1 -> fib(N-1) + fib(N-2).
In Listing 5, fib is defined by three different patterns, and the runtime will decide which pattern to call as appropriate. The when ... is a guard clause that can constrain when a pattern is applicable.
Listing 6 shows how to compile and load this module in the shell.
Listing 6 Compiling a module and executing its functions
1> c(mymath.erl).
2> mymath:square(5).
25
3> mymath:fib(7).
13
Actors in Erlang
Now that you're at least a little bit comfortable with Erlang, we can begin looking at actors. Three basic elements in Erlang form the foundation for concurrency. First, the built-in spawn function creates a new process executing a function and returns the new process's process identifier. Second is a syntax for sending a message to a process with the ! operator. And finally, actors can use a receive...end function to pattern-match messages from the actor's mailbox.
To see how these pieces fit together, we'll create a process that does conversions between Celsius and Fahrenheit temperatures. First we must define the function that the process will run, as shown in Listing 7.
Listing 7. temperature.erl
temperatureConverter() ->
receive
{toF, C} ->
io:format("~p C is ~p F~n", [C, 32+C*9/5]),
temperatureConverter();
{toC, F} ->
io:format("~p F is ~p C~n", [F, (F-32)*5/9]),
temperatureConverter();
{stop} ->
io:format("Stopping~n");
Other ->
io:format("Unknown: ~p~n", [Other]),
temperatureConverter()
end.
This function receives messages in the form of three possible tuple formats. The first format is {toF, C}. In this tuple, the first element is the toF atom, and the second is the temperature in Celsius. In the code the variable C is matched to the value. On match, it prints the answer and calls back to this function again. This is a tail-recursive call. Erlang actor functions often follow this idiom of matching an incoming message, then making a tail-recursive call back to the same function. State can be maintained in the actor by passing it in a function parameter and modifying it on the recursive call.
The {stop} message is a special message to stop the process. The last pattern is just an Other variable that maps to anything, prints an error message, and restarts.