How/why do functional languages (specifically Erlang) scale well?

Solution 1:

A functional language doesn't (in general) rely on mutating a variable. Because of this, we don't have to protect the "shared state" of a variable, because the value is fixed. This in turn avoids the majority of the hoop jumping that traditional languages have to go through to implement an algorithm across processors or machines.

Erlang takes it further than traditional functional languages by baking in a message passing system that allows everything to operate on an event based system where a piece of code only worries about receiving messages and sending messages, not worrying about a bigger picture.

What this means is that the programmer is (nominally) unconcerned that the message will be handled on another processor or machine: simply sending the message is good enough for it to continue. If it cares about a response, it will wait for it as another message.

The end result of this is that each snippet is independent of every other snippet. No shared code, no shared state and all interactions coming from a a message system that can be distributed among many pieces of hardware (or not).

Contrast this with a traditional system: we have to place mutexes and semaphores around "protected" variables and code execution. We have tight binding in a function call via the stack (waiting for the return to occur). All of this creates bottlenecks that are less of a problem in a shared nothing system like Erlang.

EDIT: I should also point out that Erlang is asynchronous. You send your message and maybe/someday another message arrives back. Or not.

Spencer's point about out of order execution is also important and well answered.

Solution 2:

The message queue system is cool because it effectively produces a "fire-and-wait-for-result" effect which is the synchronous part you're reading about. What makes this incredibly awesome is that it means lines do not need to be executed sequentially. Consider the following code:

r = methodWithALotOfDiskProcessing();
x = r + 1;
y = methodWithALotOfNetworkProcessing();
w = x * y

Consider for a moment that methodWithALotOfDiskProcessing() takes about 2 seconds to complete and that methodWithALotOfNetworkProcessing() takes about 1 second to complete. In a procedural language this code would take about 3 seconds to run because the lines would be executed sequentially. We're wasting time waiting for one method to complete that could run concurrently with the other without competing for a single resource. In a functional language lines of code don't dictate when the processor will attempt them. A functional language would try something like the following:

Execute line 1 ... wait.
Execute line 2 ... wait for r value.
Execute line 3 ... wait.
Execute line 4 ... wait for x and y value.
Line 3 returned ... y value set, message line 4.
Line 1 returned ... r value set, message line 2.
Line 2 returned ... x value set, message line 4.
Line 4 returned ... done.

How cool is that? By going ahead with the code and only waiting where necessary we've reduced the waiting time to two seconds automagically! :D So yes, while the code is synchronous it tends to have a different meaning than in procedural languages.

EDIT:

Once you grasp this concept in conjunction with Godeke's post it's easy to imagine how simple it becomes to take advantage of multiple processors, server farms, redundant data stores and who knows what else.

Solution 3:

It's likely that you're mixing up synchronous with sequential.

The body of a function in erlang is being processed sequentially. So what Spencer said about this "automagical effect" doesn't hold true for erlang. You could model this behaviour with erlang though.

For example you could spawn a process that calculates the number of words in a line. As we're having several lines, we spawn one such process for each line and receive the answers to calculate a sum from it.

That way, we spawn processes that do the "heavy" computations (utilizing additional cores if available) and later we collect the results.

-module(countwords).
-export([count_words_in_lines/1]).

count_words_in_lines(Lines) ->
    % For each line in lines run spawn_summarizer with the process id (pid)
    % and a line to work on as arguments.
    % This is a list comprehension and spawn_summarizer will return the pid
    % of the process that was created. So the variable Pids will hold a list
    % of process ids.
    Pids = [spawn_summarizer(self(), Line) || Line <- Lines], 
    % For each pid receive the answer. This will happen in the same order in
    % which the processes were created, because we saved [pid1, pid2, ...] in
    % the variable Pids and now we consume this list.
    Results = [receive_result(Pid) || Pid <- Pids],
    % Sum up the results.
    WordCount = lists:sum(Results),
    io:format("We've got ~p words, Sir!~n", [WordCount]).

spawn_summarizer(S, Line) ->
    % Create a anonymous function and save it in the variable F.
    F = fun() ->
        % Split line into words.
        ListOfWords = string:tokens(Line, " "),
        Length = length(ListOfWords),
        io:format("process ~p calculated ~p words~n", [self(), Length]),
        % Send a tuple containing our pid and Length to S.
        S ! {self(), Length}
    end,
    % There is no return in erlang, instead the last value in a function is
    % returned implicitly.
    % Spawn the anonymous function and return the pid of the new process.
    spawn(F).

% The Variable Pid gets bound in the function head.
% In erlang, you can only assign to a variable once.
receive_result(Pid) ->
    receive
        % Pattern-matching: the block behind "->" will execute only if we receive
        % a tuple that matches the one below. The variable Pid is already bound,
        % so we are waiting here for the answer of a specific process.
        % N is unbound so we accept any value.
        {Pid, N} ->
            io:format("Received \"~p\" from process ~p~n", [N, Pid]),
            N
    end.

And this is what it looks like, when we run this in the shell:

Eshell V5.6.5  (abort with ^G)
1> Lines = ["This is a string of text", "and this is another", "and yet another", "it's getting boring now"].
["This is a string of text","and this is another",
 "and yet another","it's getting boring now"]
2> c(countwords).
{ok,countwords}
3> countwords:count_words_in_lines(Lines).
process <0.39.0> calculated 6 words
process <0.40.0> calculated 4 words
process <0.41.0> calculated 3 words
process <0.42.0> calculated 4 words
Received "6" from process <0.39.0>
Received "4" from process <0.40.0>
Received "3" from process <0.41.0>
Received "4" from process <0.42.0>
We've got 17 words, Sir!
ok
4> 

Solution 4:

The key thing that enables Erlang to scale is related to concurrency.

An operating system provides concurrency by two mechanisms:

  • operating system processes
  • operating system threads

Processes don't share state – one process can't crash another by design.

Threads share state – one thread can crash another by design – that's your problem.

With Erlang – one operating system process is used by the virtual machine and the VM provides concurrency to Erlang programme not by using operating system threads but by providing Erlang processes – that is Erlang implements its own timeslicer.

These Erlang process talk to each other by sending messages (handled by the Erlang VM not the operating system). The Erlang processes address each other using a process ID (PID) which has a three-part address <<N3.N2.N1>>:

  • process no N1 on
  • VM N2 on
  • physical machine N3

Two processes on the same VM, on different VM's on the same machine or two machines communicate in the same way – your scaling is therefore independent of the number of physical machines you deploy your application on (in the first approximation).

Erlang is only threadsafe in a trivial sense – it doesn't have threads. (The language that is, the SMP/multi-core VM uses one operating system thread per core).

Solution 5:

You may have a misunderstanding of how Erlang works. The Erlang runtime minimizes context-switching on a CPU, but if there are multiple CPUs available, then all are used to process messages. You don't have "threads" in the sense that you do in other languages, but you can have a lot of messages being processed concurrently.