Concurrency Rant: Different Types of Concurrency and Why Lots of People Already use ‘Erlang’ Concurrency
People talk a lot about concurrency. With the rise of multi-core processors, concurrency becomes more important. It’s sad that developers don’t know much about concurrency – and most of them just parrot what they have read in other blogs. I wanted to write this post for quite some time to shed more light into concurrency.
There are mainly two different types of concurrency
- One Task, many workers: For example parallel Fibonacci Numbers
- Many Tasks, many workers: For example web requests
They have two different characteristics:
- First: Need to share data
- Second: No need to share data (or “not to share in real time”)
Most people think of the first kind, when they discuss concurrency. Although most applications are of the second kind. I wish people would not confuse those two and try to fix the second problem with their solutions, because the second problem is solved sufficiently (think FaceBook). So this post will only discuss the first type of concurrency.
The breakthrough for concurrency of the first kind came with threads and the synchronizd keyword in Java 15 years ago. Before that concurrency was an esoteric topic for niches, with Java it became a topic for every developer. Today most people recognize that threads and synchronized are too low level though and create quite some problems if you don’t know what you do. One half of the blogosphere damns Java for this and favors Erlang style concurrency: Message passing between objects, each object has an inbox (a queue) of messages which it works through and objects send messages to the inbox of other objects, where messages are immutable. The benefits are clear: No shared state, no need to regulate the access to shared state and the freedom to implement the scheduler of the objects the way it works best (not being limited to thread libraries).
This half proposing Erlang over everything usually doesn’t know what the other half does and think they still use synchronized. But this is only the most basic technique (and not even the best basic one with the advent of atomics). Surprise, enterprise Java developers don’t use threads (directly) and synchronized. I’ll tell you what they do.
There are lots of better methods for concurrency nowadays like Futures, Executor Services and especially Doug Leas Fork/Join framework in Java JSR 166y. The FJ framework splits a task into subtasks, distributes them, solves them and joins the result (in a very clever way with queues which are written on one side and read on the other and tasks which can steal work from others). The algorithm for forking and joining looks like this:
Result solve(Problem problem) {
if (problem is small)
directly solve problem
else {
split problem into independent parts
fork new subtasks to solve each part
join all subtasks
compose result from subresults
}
}
As an example to calculate Fibonacci numbers:
class Fib extends FJTask {
static final int threshold = 13;
volatile int number; // arg/result
Fib(int n) { number = n; }
int getAnswer() {
if (!isDone())
throw new IllegalStateException();
return number;
}
public void run() {
int n = number;
if (n <= threshold) // granularity ctl
number = seqFib(n);
else {
Fib f1 = new Fib(n − 1);
Fib f2 = new Fib(n − 2);
coInvoke(f1, f2);
number = f1.number + f2.number;
}
}
}
(you can use threads or a different scheduler for this to work)
A similar approach to concurrent work is MapReduce as implemented by Hadoop. It also splits work into sub tasks, does a mapping step for transforming data and then reduces the result. It works best for data crunching and reducing input data to output data.
Other techniques developers often use instead of concurrency primitives are communication abstractions, like communicating over concurrent access queues, for example java.util.concurrent.ArrayBlockingQueue (ah queues again! or call them inboxes).
Threads talk to each other by adding (hopefully immutable) messages to a queue. Sounds familiar? Those can even be distributed (also see Hazelcast for distributed queues). This is very similar to Erlang concurrency, just imagine input queues for all your workers, aka actors.
Scala has an Erlang like message passing actor concurrency implementation. When looking into the Scala code, Scala uses the Fork/Join Framework of Java, the cirlce closes. And Scala uses different schedulers for it's implementation with one thread per actor only being one option.
We can abstract concurrency even more. Jonas writes an excellent piece about abstractions on top of actors in a piece about fault tolerant, Asynchronous concurrency but misses one crucial point:
Actors can simplify concurrent programming and reasoning immensely and I believe that Scala Actors is a key piece in the future Java concurrency puzzle. However, programming with actors and with explicit message passing and message dispatch loops can feel a bit unnatural and unnecessary verbose for Java developers that are used to regular OO method invocations and synchronous control flow.
As pointed out before, people use queues and are used to work with asynchronous flows. Java enterprise developers in particular as they use Enterprise Service Buses (ESBs). There are many implementations like ServiceMix, OpenESB, Camel, OpenMQ, ActiveMQ, Mule and others. They range from pure message buses to routing and integration solutions. Because ESBs are fault-tolerant, asynchronous concurrency, the developers who use them know about asynchronous flows. Companies like LinkedIn uses ESBs to distribute tasks in a fault tolerant and parallel way. Nothing new there. Java developers think in asynchronous messaging already.
Stand back a thousand feet and ESBs look like the Erlang model. Worker cling to the bus and wait for work. Each is listening to different messages, the waiting messages for each worker are a virtual input queue similar to Erlang. There isn't as much difference between concurrency in different languages as people want you to believe there is!
As a final word: It's interesting that the first and second kind of concurrency start to merge. With applications like Twitter or identi.ca, the second type is sometimes becoming the first type of concurrency because different requests need to share data with each other (hopefully you don't use the database for this as Twitter did in the beginning). One can argue that more and more applications need to share data between sessions. You can use an actor model for this (Lift does this). You could use ESBs. Or you could go a very different way with distributed method calls and objects - Terracotta to the rescue.
Thanks for listening. Hope you've learned something. I did by writing this post. As ever, please do share your thoughts and additional tips in the comments below, or on your own blog (I have trackbacks enabled).
Update: Actors Guild for Java looks also interesting
Update 2: If you find this post offending, go back read it again without you favorite programming language in mind which you need to defend. There is nothing to defend. You've chosen the programming language to the best of your knowledge, as have others (and if they haven't but just chose the language because of some hype or others told them to, well, not a good idea). Spread your knowledge, don't feel offended. Be happy if others find solutions to their problems. This is not some kind of football game which you win if you gain enough points against a different language. If the other one is better, use it. If not then don't. Sounds awfully common sense, but we sometimes seem to forget this. Merry xmas.
You can leave a Reply here. Of course, you should follow me on twitter here.
Sounds like some Java advocate has Erlang envy…
Yes, if you stand back far enough, you start to see common concurrency patterns in a variety of different technologies. That’s a no-brainer; there are only so many ways to do this sort of stuff. But to then draw the conclusion that language X concurrency primitives are therefore really no different than those of language Y is way off the mark. You’re incorrectly mixing very, very different levels of abstraction.