Showing posts with label erlang. Show all posts
Showing posts with label erlang. Show all posts

Tuesday, June 26, 2012

Where's my cheese

Imperative programming is pretty difficult.

The main problem is that once you've put something somewhere you expect to find it where you put it.

“Hej, who moved my cheese?” you're thinking.

If you put a chunk of cheeses in the fridge, its nice if you can find it where you put it.  You put things in places, and later you expect to find them where you put them.  What this boils down to in terms of programming languages is the notion of variables.

In imperative programming languages, variables are the names of places where you can put things.

If I say

     int x;

In C this means there is a place called x where I can put an integer.

     x = 7;

means put the integer 7 into the place called x. Having put my 7 into my x I'd really like it to stay there forever.

“Why forever?” I can hear you asking.

“Because all other alternatives are worse”

If I can change x later, then my program will be very difficult to understand, the value of x might change many times and I'll have to understand the complete history of the program in order to figure out with the value is.

Even worse, what happens in a concurrent world, suppose several parallel processes can change the value of x at any time - if this could happen things could get really difficult to understand.

Functional programming language don't have this problem. If you say x is 7 then it is 7 for ever and ever and ever and ever.

This is really nice.

Believe me.



Wednesday, December 16, 2009

Comet is dead long live websockets

I've just had a chance to play with the implementation of websockets
in Googles Chrome browser. This post started me off.

After a small amount of experimentation I was able to make Erlang talk to a web page using pure asynchronous message passing.

I think this means the death of the following technologies:
  • comet
  • long-poll
  • AJAX
  • keep-alive sockets
All the above are merely hacks, inadequate ways of programming round the central problem that web-browsers could not simply open a socket and do asynchronous I/O like any other regular application.

Well now things have changed, web sockets are here

It's not a question of if long-poll etc. will die, it's just a question of when.

Once the handshake is over, web sockets work more or less like regular sockets. The important point to note is that the overhead involved in managing a web socket is minimal. In interactive applications, for example, when providing auto-complete of characters that are typed into a buffer, the current AJAX technology imposes an enormous overhead since virtually all the time in the server is spend parsing HTTP headers.
Pushing data to a client has for years been a total mess. Attempts to circumvent this have involved things like long-poll and comet, or even simply just polling the server on a regular basis. All this is now irrelevant.
So let's see what this means with an Erlang example

Sending messages to a region in a browser from Erlang is extremely easy using websockets.

Add this to your web page:
<div id="tag"></div>
Then do this in Erlang:
Browser ! {send, "tag ! XXX"}
XXX will appear in the div

The server code

start() ->
F = fun interact/2,
spawn(fun() -> start(F, 0) end).

interact(Browser, State) ->
receive
{browser, Browser, Str} ->
Str1 = lists:reverse(Str),
Browser ! {send, "out ! " ++ Str1},
interact(Browser, State);
after 100 ->
Browser ! {send, "clock ! tick " ++
integer_to_list(State)},
interact(Browser, State+1)
end.
To send a message to a tagged region tag in the browser I just say Browser ! {send "tag ! message"} this could hardly be easier.

The details

If you want to try this yourself you'll need a version of chrome that supports web sockets. Then two files local_sever.erl and interact.html

They are listed at the end of this article:

To run things you'll need a local web server and Erlang.

Compile local_server.erl and start by evaluating local_server:start(). Then serve the web page interact.html from your local server.

Enjoy

Listings

-module(local_server).
-compile(export_all).

%% start()
%% This should be in another module for clarity
%% but is included here to make the example self-contained

start() ->
F = fun interact/2,
spawn(fun() -> start(F, 0) end).

interact(Browser, State) ->
receive
{browser, Browser, Str} ->
Str1 = lists:reverse(Str),
Browser ! {send, "out ! " ++ Str1},
interact(Browser, State);
after 100 ->
Browser ! {send, "clock ! tick " ++ integer_to_list(State)},
interact(Browser, State+1)
end.

start(F, State0) ->
{ok, Listen} = gen_tcp:listen(1234, [{packet,0},
{reuseaddr,true},
{active, true}]),
par_connect(Listen, F, State0).

par_connect(Listen, F, State0) ->
{ok, Socket} = gen_tcp:accept(Listen),
spawn(fun() -> par_connect(Listen, F, State0) end),
wait(Socket, F, State0).

wait(Socket, F, State0) ->
receive
{tcp, Socket, Data} ->
Handshake =
[
"HTTP/1.1 101 Web Socket Protocol Handshake\r\n",
"Upgrade: WebSocket\r\n",
"Connection: Upgrade\r\n",
"WebSocket-Origin: http://localhost:2246\r\n",
"WebSocket-Location: ",
" ws://localhost:1234/websession\r\n\r\n"
],
gen_tcp:send(Socket, Handshake),
S = self(),
Pid = spawn_link(fun() -> F(S, State0) end),
loop(zero, Socket, Pid);
Any ->
io:format("Received:~p~n",[Any]),
wait(Socket, F, State0)
end.

loop(Buff, Socket, Pid) ->
receive
{tcp, Socket, Data} ->
handle_data(Buff, Data, Socket, Pid);
{tcp_closed, Socket} ->
Pid ! {browser_closed, self()};
{send, Data} ->
gen_tcp:send(Socket, [0,Data,255]),
loop(Buff, Socket, Pid);
Any ->
io:format("Received:~p~n",[Any]),
loop(Buff, Socket, Pid)
end.

handle_data(zero, [0|T], Socket, Pid) ->
handle_data([], T, Socket, Pid);
handle_data(zero, [], Socket, Pid) ->
loop(zero, Socket, Pid);
handle_data(L, [255|T], Socket, Pid) ->
Line = lists:reverse(L),
Pid ! {browser, self(), Line},
handle_data(zero,T, Socket, Pid);
handle_data(L, [H|T], Socket, Pid) ->
handle_data([H|L], T, Socket, Pid);
handle_data([], L, Socket, Pid) ->
loop(L, Socket, Pid).

And the web page interact.html
<script src='/include/jquery-1.3.2.min.js'></script>
<script>
$(document).ready(function(){

var ws;

if ("WebSocket" in window) {
debug("Horray you have web sockets
Trying to connect...");
ws = new WebSocket("ws://localhost:1234/websession");

ws.onopen = function() {
// Web Socket is connected. You can send data by send() method.
debug("connected...");
ws.send("hello from the browser");
ws.send("more from browser");
};

run = function() {
var val=$("#i1").val(); // read the entry
$("#i1").val(""); // and clear it
ws.send(val); // tell erlang
return true; // must do this
};

ws.onmessage = function (evt)
{
var data = evt.data;
var i = data.indexOf("!");
var tag = data.slice(0,i);
var val = data.slice(i+1);
$("#" + tag).html(val);
};

ws.onclose = function()
{
debug(" socket closed");
};
} else {
alert("You have no web sockets");
};

function debug(str){
$("#debug").append("<p>" + str);
};


});




<h1>Interaction experiment</h1>

<h2>Debug</h2>
<div id="debug"></div>

<fieldset>
<legend>Clock</legend>
<div id="clock">I am a clock</div>
</fieldset>

<fieldset>
<legend>out</legend>
<div id="out">Output should appear here</div>
</fieldset>

<p>Enter something in the entry below,
the server will reverse the string and send it to the
out region above</p>

<fieldset>
<legend>entry</legend>
<P>Enter: <input id="i1" onchange="run()" size ="42"></p>
</input>
</fieldset>

</body>

Sunday, February 15, 2009

JSON protocols (part 1)

For a long time I have been interested in describing protocols. In 2002 I published a contract system called UBF for defining protocols. This scheme was never widely adopted - perhaps it was just to strange...

I have revised UBF and recast it in a form which I call JSON Protocols - since JSON is widely implemented, this method of described protocols might be more acceptable.

What's the problem?

Client and server interaction should be regulated by some kind of contract that is independent of both the client and server. If the client-server interaction fails, then it should be evident by examining the contract which of the parts in the system has failed. Is the problem in the client or the server?


To simplify our problem we will assume that the client and server interact by exchanging JSON messages and we will add a form of contact that will allow us to check that the sequence of messages is correct.

The File Server Contract

We'll start with a simple example and build a formal description of a file server. I'll use the familiar notion of a finite state machine to describe the operations of the server.

The behaviour of the server is completely specified by a set of
4-tuples of the form:

State x RequestMessage -> ResponseMessage x StateOut

We'll start our specification of the file server somewhere in the middle of a session. We'll assume that users must be authenticated, but we'll show how they are authenticated later.

Let's assume the server is in the state ready - meaning it is ready to accept a request. We can start by defining two state transitions:

ready x getFile -> file x ready;
ready x getFile -> noFile x stop;

This means that if our machine is in the state ready and receives a getFile message it will respond by either sending a file message and transitioning to the ready state or it will respond with a noFile message and transition to the stop state.

Here getFile and file are messages and ready and stop are states.

Attached to the message is some data structure that accompanies the messages.
We can defined these data structures as follows:

data[getFile] = {fileName:string};
data[file] = {fileName:string, fileData:string};

Having defined the data we turn to the wire protocol - what data is actually sent between the client and the server? To answer this we will give a JSON example.

Suppose we want to fetch a file called "index.txt", assume also that the content of the file is "abc" then our contract says that the following JSON terms must be exchanged:

Request =
{msg:"getFile", data:{fileName:"index.txt"}}


Response =
{msg:"file",
data:{fileName:"index.txt", fileData:"abc"},
state:"ready"}
Note that exactly this interchange must take place. If either of the messages is incorrectly typed the contract checker can detect the error and determine whether the client or server has violated the contract.
There is a simple relation between the format of the message that is actually exchanged on the wire and the, algebraic specification of the messages.

[note - I have taken liberty with JSON notation here and omitted the quote marks preceding the tags in the object name, strictly I should have written {"msg":"file" etc., but I have written msg:"file"]

What happens if a file doesn't exist? We had a rule for this:

ready x getFile -> eNoFile x stop;

The reply message eNoFile has no associated data, so no data description is necessary.

As an example, suppose we request the file "badfile" which does not exist. This is what we would see "on the wire".

Request = {msg:"getFile", data:{fileName:"badfile"}}
Response = {msg:"eNoFile", state:"stop"}

Observe that the eNoFile message has no associated data.

Why do we send the state back in the response message?

This is to avoid the situation where the server performs a silent state change that cannot be observed by the client. Suppose we have two rules:

a x s1 -> c x s2
a x s1 -> c x s3

When we send an a message we always receive a c message, but we cannot tell if the server changed to state s2 or s3. To make things clearer we always include the new state in the reply.

Now that we've seen what happens in the middle of a session, we can include details of the login and authentication phase.

login x start -> challenge x wait;
response x wait -> ok x ready;
response x wait -> badpassword x stop;

data[login] = {name:string};
data[challenge] = {salt:string};
data[response] = {md5:string};

Once we are ready we might want to list files:

ready x listFiles -> files x ready;
ready x logout -> stop;

data[files] = [{filename:string}];

This completely (and formally specifies the behaviour of a file sever)

Adding time

We can easily add time to our specification:

read x getFile -> file x read within 2 seconds;

This means that we must respond within 2 seconds.

What else?

We need some meta-information, the version number and name of the protocol, and an introspection mechanism.

Notation

I've been a bit sloppy with notation here and used a notation that I hope is 'self-evident'. The state machine syntax is trivial:

StateIn x MessageIn -> MessageOut x StateOut;

The data notation is less obvious:

data[XXX] = {tag1: type1, tag2: type2 ...}

denotes a JSON message of the form:

{"msg":"XXX", data:{"tag1":Data1, "tag2": Data2, ...}}

Where Data1 is of type type1 and Data2 is of type type2. Observe I have only
used the type "string" in my examples, but this is easily extended to JSON primitive types, enumerations and sequences of types.

I also used the notation [X] (in the definiton data[files] =
[{filename:string}]. [X] means an array (or sequence) of type X.

Contract Checking

Now what we have our state machines and message we can easily write a contract checker.

Given the state of the finite machine and then next message we can easily check if the client and server are correctly responding to protocol messages as required by the specification. Each message has a data type specification can easily be checked.

Comments on this are welcomed.

In Part 2 I will post Erlang bindings for the protocol specification and code for a contract checker.

Other implementers might like to implement bindings and contract checkers for their favorite languages. having done this we could start writing multi-language applications based on formal and checkable contracts.




Wednesday, January 28, 2009

Micro Lightweight Unit Testing

I'm often asked the question "what unit testing framework do you use?" The answer is usually I don't, but I do use a form of micro testing that is built into Erlang.

In Erlang, every assignment of the form Lhs = Rhs where the Lhs is a ground-term and Rhs is a non-ground term can be viewed as an assertion, or unit test, since it can possibly fail.

So when we write:

    {ok, S} = file:open("filename", [read])
We're writing assertion to the effect that opening "filename" for read will succeed.

So how do I write unit tests?

To answer this question, I'll walk you through how I'd write the code for an efficient Fibonacci function.

I'm actually following the three rules of TDD so Uncle Bob and the agile crowd should approve of this method ...

I'll show you the order in which I implement the code. Often we show the final version of some code, but not the order in which the code was written. This time I'm going to show the precise order in which I wrote the code, and show how and when I tested and ran the code.

I'll start by defining a module, with a unit test.

Step 1) First write a micro-unit test:

-module(fib).
-compile(export_all)

test() ->
0 = fib(1),
1 = fib(2),
2 = fib(3),
6765 = fib(20),
ok.
Where did I get these values from? - I checked on the wikipedia - I was unsure if the Fibonacci series starts 0,1,1,2,.. or 1,1,2,3.

This code won't compile correctly, since the fib function is missing.

Step 2) Write the fib function:

fib(0) -> 0;
fib(1) -> 1;
fib(N) -> fib(N-1) + fib(N-2).
This version of the Fibonacci function is recursive and very inefficient. But I'll implement it first, because I have high confidence that the code is correct, and because I'll use it later to test the efficient version of the code.


Step 3) I compile and test the module


The module now looks like this:

-module(fib).
-compile(export_all).

test() ->
0 = fib(0),
1 = fib(1),
1 = fib(2),
6765 = fib(20),
ok.

fib(0) -> 0;
fib(1) -> 1;
fib(N) -> fib(N-1) + fib(N-2).

I compile and test it:

1> c(fib).
{ok,fib}
2> fib:test().
ok
So now I have something that works.

step 4) Add unit tests for fastfib

test/0 looks like this:

test() ->
0 = fib(0),
1 = fib(1),
1 = fib(2),
6765 = fib(20),
0 = fastfib(0),
1 = fastfib(1),
1 = fastfib(2),
2 = fastfib(3),
K = fib(25),
K = fastfib(25),
ok.
Here I check that fastfib returns the same value as fib with the lines
  K = fib(25),
K = fastfib(25).
Step 5) Write the fastfib function.

The entire module looks like this:

-module(fib).
-compile(export_all).

test() ->
0 = fib(0),
1 = fib(1),
1 = fib(2),
6765 = fib(20),
0 = fastfib(0),
1 = fastfib(1),
1 = fastfib(2),
K = fib(25),
K = fastfib(25),
ok.

fib(0) -> 0;
fib(1) -> 1;
fib(N) -> fib(N-1) + fib(N-2).

fastfib(0) -> 0;
fastfib(N) -> fastfib(N, 1, 0).

fastfib(1, A, _) -> A;
fastfib(N, A, B) -> fastfib(N-1, A+B, A).

Step 6) Compile and test.

I compile and test the module, as in Step 3)

Step 7) I change the exports of the module and change

-compile(export_all). to -export([test/0, fib/1]).

I rename fastfib to fib and fib to slowfib.

Done

Step 8) Quickcheck

I don't have John Hughes Quickcheck on my machine, but If I did, I could write a test case that said "forall integer N >= 0, fib(N) and fastfib(N) compute the same value" - quickcheck would then generate zillions of tests that test this property.

Finally

I have used the convention of exporting a function test/0 in several modules. I also have a simple program which checks a large number of modules. It checks if the module exports the function test/0, and if so evaluates (catch Mod:test()) if this returns ok, then the module has passed its test. If not I print an appropriate error.

Note how when I wrote the module I wrote a test case, then implemented the function it was testing, then wrote another test case, then more code etc. This way I'm interleaving writing test cases with implementing the test case. This way I write the code in a number of small steps, and if something goes wrong I can just reverse the last step.

When I'm finished with the code all the test cases are ready - so I don't write the code then the test cases, I interleave the two.



This is my micro-lightweight unit test framework

This is what I use for my hobby-hacks. For paid work I use the OTP test server.

Thursday, July 10, 2008

UBF and VM opcocde design

UBF is a data encoding that allows structured terms (rather like XML) to be sent over the network. It also includes a protocol checking scheme to automatically determine if sequences of typed messages follow a particular protocol.

This blog entry was stimulated by this posting on the erlang mailing list.

One of the basic ideas of UBF of was to send programs not data structures. The programs were for a byte-coded stack machine. So instead of sending data structures between machines we send tiny programs which when evaluated create data structures.

Each byte is an opcode for a VM. The net-effect of executing a UBF program is to leave a value on the stack.

The trick in UBF was not to start allocating the opcodes in the VM from zero - but to allocate them with loving care.

A common mistake in making byte coded VMs is to allocate the byte codes from zero. If you think about it the byte code for a PLUS operation can only be 43 (why? - easy - this is the ASCII code for "+").
In fact the byte code for PLUS should be 43 in all byte coded VMs - there should be laws that make it a criminal offense for the opcode to be anything other than 43 - thus it is written - there will of course, be a problem with the opcode for TIMES - if you are familiar with your ASCII codes then you should understand why.
I have no idea where I learned this trick - it seems to be in the folk-law of VM design - choose the op codes so that the binary code is readable (if you can). Unfortunately I didn't know this when I designed the first Erlang VM but now I know better.

So this way the byte code for start-of-tuple is 123, end-of-tuple is 125 and element-separator is 44 - unsurprisingly "{", "}" and ",". Thus "{...,...,... }" is a program and NOT a bit of syntax.

With this choice of encoding programs become human readable strings which require zero parsing - you just execute the byte codes.

Contrast XML where the data structures are human readable but require parsing - this is why constructing a term from UBF is far faster than using XML and why the size is far smaller and is human readable.

Why didn't UBF spread?

If you have something that is almost ok - then lots of people can have great fun arguing over it and polishing it at the edges.

Things which deeply flawed and industry standards things like XML can lead to endless discussions - great fun - lots of hot air. Project management can happily preside over "the illusion of work" - wages get paid - everybody is happy. Projects get delayed - project management becomes very happy.

The optimal point is where projects get as delayed as much as possible, budget overruns are as large as possible and the project manger is almost, but not quite, sacked. This idea is explored in Putt's law and the successful Technocrat - recommended to me Gilad Bracha - and a great read.

Some things like (scheme, pascal, ..) are pretty nearly perfect - thus there is little to do. In fact pascal was perfect (anybody got a UCSD pascal emulator and image? - now that was really nice)

Fixing stuff that's broke

Programmers like to have something to do - so our lot in life is to fix flawed things. Most of my time is spent in fixing things that should work, but are in fact, broken.

ASN.1 (which got me started on this blog entry) is elegant - but how it has been used is not.

I am currently examining LDAP - LDAP schemas have to be seen to be believed (and yes LDAP schemas are written in ASN.1)

In LDAP schema speak a boolean is a 1.3.6.1.4.1.1466.115.121.1.7 (this is an OID, for those in the know) and 1.3.6.1.4.1.1466.115.121.1.40 is a string ...

I'm glad the LDAP schema designers didn't turn their hand at
programming language design. If they had, then

     boolean x,y,z;

Might have been

   type 1.3.6.1.4.1.1466.115.121.1.7 x,y,z;


The only thing that is good about LDAP schemas is that they are not XML schemas.
...

Saturday, June 28, 2008

Itching my programming nerve


Photo: oreillygmt

I've just got back from the first ever commercial Erlang conference. Some 40 talks in two days all related in some way or other to Erlang. It was a chance to meet old friends, make new friends and connect people together in the hope that new synergy effects would arise.

The most exciting thing was the emergence of what I think might be the first killer applications written in Erlang. I might be wrong, but my gut feeling is that what Alexander Reinefeld showed us will be the first killer application in Erlang.

Only a few language nerds are interested in programming languages in their own right. Most people are more interested in what you can do with a programming language than with the underlying language. Thus is was with Ruby. Ruby on rails was the application that drew developers into Ruby. It made them want to learn Ruby so that they could easily build web applications.

Alexander Reinefeld told us about an Erlang implementation of the Wikipedia that not only has a stunningly beautiful architecture, but which outperforms the existing Wikipedia.

I'll talk about the Wikipedia implementation later in this posting, but it was not the only notable talk there were many other great talks.

Claes Vikström (Klacke) gave a great lecture which was a mixture of battle stories, history and what he was doing today.

Klacke is the master of the one-line throw-away remark - "and then I implemented a DBMS ... and a web server" this was the technical stuff, and on the business side
...then we started a company and made a whole lot of money...
At the end of his lecture Klacke said something like:
... so how come we have this great technology and people are just doing boring things and not writing stock exchanges ... there aren't any killer applications ...
Just as an aside Joel Reymont did stir up the Erlang mailing list with his announcement that he wanted to write an open source stock exchange as a publicity stunt, but this ran out in the sand. Perhaps later we can resurrect this idea, it would be a bit of fun.

The Wiki

Now for the fun stuff. Alexander Reinefeld video answered Klackes call for action and for a non-boring application as he described how he had implemented the Wikipedia on a new p2p system now called Scalaris.

Here's my version of his story:
  1. They make a peer to peer system based on the chord algorithm
  2. They added a replication later using the paxos algorithm
  3. They added a transaction layer
  4. The injected the wikipedia
  5. It went faster that the existing wikipedia
Applied to Wikipedia, Scalaris serves 2,500 transactions per second with just 16 CPUs, which is better than the public Wikipedia.
Alexander is a tall bespectacled academic who usually only turns up at academic conferences. He was very worried at the start of the talk when he was introduced as "Professor Reinefeld" I think he thought it would frighten people.

The system they described won an IEEE prize for scalable systems and was also presented at the Google conference on scalability. I asked Alexander why publicity about what they had done was so hard to find.
"I'm academic, we usually publish papers," he said.
He'd also said he'd started a company that "wasn't doing very well" (tip to VCs - check this one out and give the guy some help).

So my take on this is that this is one of the sexiest applications I've seen in many a year. I've been waiting for this to happen for a long while. The work is backed by quadzillion Ph.D's and is really good believe me.

On second thoughts don't believe me but check out the video lecture. You can also download the code.

CouchDb

When Alexander had blown my mind Jan Lehnardt popped up for the next section and blew it even further by presenting CouchDB - am I going mad are we seeing the emergence of two killer applications? This cannot be.

Jan Lehnardt has a presentation technique that is a joy to watch - it reminded me of why I love programming.

Jan communicates on two level simultaneously. His body language oozes enthusiasm - he waves his arms so fast and hops up and down so we think that he was either a helicopter in a previous life or that he wants to get a job as a windmill. Words tumble out of his mouth so fast that his tongue often trips over the end of his sentences and falls flat into the middle of his next sentence conveniently missing out the middle of the last sentence.

Check out the video and you'll see that I mean - You'll see Jan almost taking off as he impersonates a helicopter. For more information see the slides of the talk. You can download CouchDb from the Apache incubator site.

This style of lecturing is amazing. Jan communicates simultaneously on two entirely different level. His enthusiasm is received by the amygdala in the limbic system and his slides go via your eyes to the pre-frontal cortex for analytic processing.

So what was this great stuff the Jan was so enthusiastic about?

CouchDb - is an Erlang application that turns a Key-Value JSON store into a system with a RESTFUL interface that stores arbitrary data structures data in a way that fits nicely in with the Erlang system. When I got home I downloaded CouchDb and took a look, and there is was, nicely packaged with a Mochiweb server, the same server which is used by facebook for their comet web chat system.

Like most good ideas the CouchDB is deceptively simple. Once you've seen it you think - yes that's how it should be, how simple, how beautiful. But designing simple things is not easy it requires many false starts and takes a long time to get right. Hats off to Damien Katz for the initial design and to his collaborators, and thanks Jan for telling us about it.

Synergy...

Now it just so happens that both Jan Lehnardt and Alexander Reinefeld both live in Berlin, both are working with key-value stores (the details, vary) which are programmed in Erlang, both of them are working on what might be the next killer Erlang application and ... they have never met.

I introduced them and then stood back. Wow.

After a moment of shyness they changed to speaking German and Jan started bouncing up and down and speaking even faster than in English - this was getting dangerous - this time Jan did turn into a helicopter and narrowly missed causing an accident as he flew out of the room.

Going home

Klacke and I took the same flight back to Sweden the next day.

"That itched my programming nerve," said Klacke

"Precisely ..."








Tuesday, June 24, 2008

Invasion of Privacy

On 18 June the Swedish Parliament passed a law giving sweeping new powers to the FRA (Swedish Defense Radio Establishment) allowing them to wiretap people in Sweden through phone conversations, email, text messages and more.

All people in Sweden using electronic communication can have their communication monitored despite the fact that they are not suspected of committing any crime.

In my view this is in direct contravention of article 12 of the UN declaration on human rights to which Sweden is a signatory.
Article 12.

No one shall be subjected to arbitrary interference with his privacy, family, home or correspondence, nor to attacks upon his honour and reputation. Everyone has the right to the protection of the law against such interference or attacks.
This shameful law applies to me - if you send me email (I get a lot of emails from readers of this blog and of my books) then you should be aware of the fact that your mails are not private but will be read by FRA employees - so your rights will be violated.

The Swedish government is sensitive to foreign opinion so if you wish to protest about the fact that your privacy would be violated if you mail me then I suggest you send mail to one of the leaders of the four political parties (Maud Olofsson, Fredrik Reinfeldt, Jan Björklund, Goran Hagglund) that voted this law through. They can be contacted through The Prime Minister and Ministers.

I urge you to make your opinions known.

My daughter asked me:

Does this mean they will read my MSN chats?
I said "yes".
She said "that sucks"


I get pretty pissed off when they confiscate my water bottle when I have to travel by air, but I guess I can live with this but reading my email, and the email of my wife and kids is totally unacceptable. I would never read my wife's or kids' email - such behavior is totally unacceptable in a civilized society.

All this is done in the name of saving us from terrorism - after 9/11 western politicians promised that they would not allow acts of terrorism to change our way of life. Well, spying on 9 million people who have not broken the law is a funny way of "not changing our way of life."

This really pisses me off.

/Joe Armstrong

[In other areas Sweden is a pretty decent place to live, with decent human values, but this new legislation is totally unacceptable]

[Note also - all mail to the erlang mailing list will be monitored by FRA - if this upsets you then please mail the people responsible (see above). If this worries enough people we can move the list to a country that respects human rights]


Monday, May 26, 2008

The Road we didn't go down

I've been following an interesting discussion on the Erlang mailing list where Steve Vinoski and friends have been telling us what's wrong with RPC.

The discussion started on 22 May, the general topic of conversation was the announcement that facebook had deployed a chat server written in Erlang.

In one of the posts Steve said:
"What all those years of CORBA taught me, BTW, is that RPC, for a
number of reasons, is generally A Really Bad Idea. Call it a hard-won lesson. The Erlang flavor of RPC is great because the entire Erlang system has distribution fundamentally designed and built into it, but for normal languages, RPC creates more problems than it solves."
more...

-- Steve Vinoski
Future posts asked Steve to elaborate on this.

Steve posted a long and brilliant summary of the problems with RPC to the Erlang mailing list:
"But if you don't have the time or energy, the fundamental problem is that RPC tries to make a distributed invocation look like a local one.
This can't work because the failure modes in distributed systems are
quite different from those in local systems, ..."
more ...

-- Steve Vinoski
Precisely - yes yes yes. As I read this my brain shouted YES YES YES - thank you Steve. Steve wrote more about this in RPC under fire ...

This the road we didn't go down

Steve went down this road and saw what was there and saw that it stunk, but he came back alive and could tell us what he had seen.

The fundamental problem with taking a remote operation and wrapping it up so that it looks like a local operation is that the failure modes of local and remote operations are completely different.

If that's not bad enough, the performance aspects are also completely different. A local operation that takes a few microseconds, when performed through an RPC, can suddenly take milliseconds.

If programmers cannot tell the difference between local and remote calls then it will be impossible to write efficient code. Badly placed RPCs in the middle of some mess of software can (and does) destroy performance.
I have personally witnessed the failure of several large projects precisely because the distinction between local and remote procedure calls was unclear.
Note that this factor becomes even worse in large projects with dozens of programmers involved. If the team is small there is a chance that the participants know which calls are local and which calls are remote.

How do we do things in the Erlang world?

All Erlang programs are composed from sets of parallel processes, these processes can create other processes and send and receive messages. Doing so is easy and is a lightweight operation.

Processes can be linked together for the purposes of error handling. If A is linked to B and A fails then B will be sent an error signal if A fails and vice versa. The link mechanism is completely orthogonal to the message send/receive mechanism.

When we are programming distributed systems, various forms of RPC are often extremely useful as programming abstractions, but the exact form of the RPC varies from problem to problem and varies with architecture.

Freezing the exact form of an RPC into a rigid framework and disregarding the error cases is a recipe for disaster.

With send, receive and links the Erlang programmer can easily "roll they own RPC" with custom error handling.

There is no "standard RPC stub generator" in Erlang nor would it be wise for there to be such a generator.

In a lot of applications the simplest possible form of RPC suffices, we can define this as follows:
rcp(Pid, Request) ->
Pid ! {self(), Request},
receive
{Pid, Response} ->
Response
end.
Nothing complicated, this code just sends a message waits for the reply.

There are many variations on this theme. The simplest RPC waits forever, so if a reply never comes the client hangs. We can fix this by adding a timeout:
rcp(Pid, Request, Time) ->
Pid ! {self(), Request},
receive
{Pid, Response} ->
{ok, Response}
after Time ->
{error, timeout}
end.
Suppose we wish an exception to be raised in the client if the remote machine dies in the middle of a RPC, then we define:
rcp(Pid, Request) ->
link(Pid),
Pid ! {self(), Request},
receive
Response ->
Response
end.
The addition of the link will ensure that the client terminates if anything goes wrong in the RPC.

Suppose we want to "parallelize" two rpcs:
rpc(Pid1, Pid2, Request) ->
Pid1 ! Pid2 ! {self(), Request},
receive
{Pid1, Response1} ->
receive
{Pid2, Response2} ->
{Response1, Response2}
end
end.
(don't worry this does work, the order of the replies is irrelevant)

The point I am trying to make through a number of small examples is that the level of granularity in the RPC AND the error characteristics is under the precise control of the programmer.

If it turns out that these RPC abstractions do not do exactly what we want then we can easily code our solution with raw processes and messages.

So, for example, going from a message sequence diagram to some Erlang code is a trivial programming exercise.

"Standard" RPC also make the following crazy assumption - "that the reply should go back to the client".

Interactions of the form tell X to do Y then send the result to Z are impossible to express in a standard RPC framework (like SOAP) but are simple in Erlang:
rpc(tell,X,toDo,Y,replyTo,Z) ->
X ! {Z, Y}.
(This assumes the convention I'd used earlier of always sending two-tuples as messages with the Id of the process that is expecting a reply as the first element of the tuple (using self(), in the earlier examples we forced the reply to come back to the originator)).

Let's suppose we want to add versioning to our protocols, this is easy:

rpc(Pid, Request, Vsn) ->
Pid ! {self(), vsn, Vsn, Request},
receive
...
end.

The point is here is to show that things like versioning, error handling parallelisation etc are easily added if we expose the interface between messaging and function calls and allow the user to custom build their own forms of interactions with remote code.

Of course, certain common patterns of interaction between complements will emerge - theses are what are baked into the OTP libraries.

What is OTP?

OTP is a set of battle tested ways of doing things like RPC in fairly common cases. The OTP methods do not cover all error cases but they do cover the common cases. Often we have to step outside the OTP framework and design our own specialised error and recovery strategies but doing so is easy, since OTP itself is a message driven framework and all we have to do is strip away the stub functions that send and receive the message and replace these with our own custom routines.

OTP should re-branded as "OTP on rails" it's really just a framework for building fault tolerant systems.

Does this method of building software without excessive reliance upon one particular flavour of RPC work?

I'd say the answer is Yes and Yes with a vengeance.

This is the way we have built real-time server software at Ericsson for decades. We have used PLEX, EriPascal, Erlang and C++ with Rose-RT for years. The common factor of all of these is the non-reliance on RPC. We specify protocols then we terminate them with a number of different technologies.

These protocols are way more complex than can be specified using RPCs but by exposing the protocols and the failure modes we can make systems that are highly reliable.

I'd always thought that if we did things with RPCs then we'd run into trouble.

Steve went there and did that and found the problems - we went down a different road.

What's really interesting is that Steve's world and our world are starting to collide - we have a lot to learn from each other.

Thursday, July 19, 2007

Scalable fault-tolerant upgradable systems Part 1

let's talk about servers which are:
  • Scalable
  • fault-tolerant
  • Dynamically Upgradable
Q: Are these really the same thing?


A: Well not really, but they are very similar.

A system that is fault-tolerant can easily be made scalable and easily made so that we can do in-service upgrade.

Here's how:

Algorithm1.

In-service Upgrade.

Assume we have N nodes running version one of a program - we want to upgrade to version two with no loss of service.

Foreach node K in nodes:
  1. migrate the traffic on node K to some other node
  2. stop node K
  3. upgrade the software
  4. migrate the traffic back to node K

Algorithm 2

Scale up system

To add a new node to the system:

  • Find some busy node
  • migrate half the traffic on the node to the new node
Algorithm 3

Make fault-tolerant system

Assume we have N nodes connected in a ring. If node N crashes we will recover on node N+1 (or the first node if N was the last node)

In operation we have to make sure that node N+1 has enough information about node N to take over from node N if node N crashes.

In practise we would send an asynchronous stream of messages from N to N+1 containing enough information to recover if things go wrong.


Similarities

These algorithms are very similar. They can all be built with a small number of primitives. The primitives must:
  • detect failure
  • move state from one node to another
Q: What are the state changes that must be moved?

A: Enough state to resume the operation on a new node.

Q: Could dynamic code upgrade be viewed as a special case of failure?

A: Yes - here's how

Algorithm 4

Dynamic code upgrade

Apply Algorithm 3 to make a fault-tolerant system.

For any node running old code:
  1. crash the node
  2. restart the node
  3. put new code on the node
  4. make the node available
As the new node becomes available Algorithm two (make system scalable) applies

What do you have to think about?

When designing a system for fail-over, scalability, dynamic code upgrade we have to think about the following:
  1. What information do I need to recover from a failure?
  2. How can we replicate the information we need to recover from a failure?
  3. How can we mask failures/code_upgrades/scaling operations from the clients

This is part of the essential analysis that we have to perform if we want to make a highly reliable system that is scalable and which can be upgrade with zero loss of service.

In part 2 - I'll talk about how to mask failures from the clients. Do we use IP-fail-over techniques, or some other technique?

When it comes to programming, you'll want to implement this all in Erlang - Erlang has the correct set of primitives for failure detection (links) and for stable storage (replicated amnesia tables) which make programming this a not too daunting task.

Thursday, September 28, 2006

Why I often implement things from scratch

Once upon a time there was an Erlang programmer who needed an FTP server running on one of the hosts in a private network. In fact he didn't need an FTP server, he just needed to transfer files between a central server and his client machine, but he thought that he needed an FTP server to do this.

He searched for FTP servers, and indeed found several of them. They had to be free of course, because even though the organisation he worked for had loads of money the administrative procedures for buying such a product were considerable. The program also had to have the right form of license, so that the legal department would be happy.

He downloaded several such servers, some of them wouldn't compile, and even if they did compile they had to be correctly configured in order to work, and this was not easy.

Suddenly our programmer was stuck by the thought that he might be able to write an FTP server himself and that writing the FTP server might be quicker than finding and installing an FTP server that somebody else had written.

"What do I want to do?" he asked himself.

"List files on a remote directory, copy files, between a local and remote machine, etc"

Then he remembered that the project he was working on used distributed Erlang.

"This must be easy," he thought. He was right.

So ... on the server machine he give this command:

>$erl -name server -cookie ASDRTFERT
1> node().
'server@host1.somenet.com'
[See this link for a description of what these commands do]. Then he went to another machine and typed this:
>$erl -name client1 -cookie ASDRTFERT
1> node().
'client1@host23.somenet.com'
Now he had started two erlang nodes. Now the nice thing about distributed Erlang is that you can easily run code on any of the nodes, so to check that he could access the server node from the client node, the programmer typed this:

2> rpc:call(server@host1.somenet.com',
erlang, node, []).
'server@host1.somenet.com'
Which is what would have happened if the command had been issued on the first machine. Now our programmer knew that he could evaluate any function on the remote machine, just as if it had been on the local machine. The correspondence is as follows:

If the local command was:
> file:get_cwd()
Then to perform this on the server all he had to do was call:
> rpc:call(server@host1.somenet.com',file, get_cwd, []).
So to list files on the remote machine, he did this:
1> rpc:call(server@host1.somenet.com',
file, list_dir, ["."]).
{ok, ["Makefile",
"readme",
....
Then he decided that he wanted to copy the Makefile to his local machine so he wrote this:
2> {ok, Bin} = rpc:call(server@host1.smenet.com',
file, read_file, ["Makefile"]).
<<".SUFFIXES: .erl .beam .yrl" .....>>
3> file:write_file("Makefile", [Bin]).
ok
At this point all that typing in the shell became tedious, so he fired up emacs and wrote this:
-module(myftp).
-export([get_file/1]).

get_file(F) ->
{ok, B} = rpc:call(server@host1.smenet.com',
file, read_file, [F]),
file:write_file(F ++ ".copy", [B]).
Then he compiled and tested his program:
4> c(myftp).
{ok,myftp}
5> myftp:get_file("Makefile").
ok
He then added a few bells and whistles and was done.

Moral

If you have the right tools it's often quicker to implement something from scratch than going to all the trouble of downloading compiling and installing something that somebody else has written.

This is a true story, but I've just written this code. Writing this code and the blog entry took about the same time as it would to find and install an FTP server on my machine.

Monday, September 11, 2006

Pure and simple transaction memories

Now for a technical article.

How can several parallel programs maintain a consistent view of state. By this I mean how can two programs, possibly in different countries, manipulate common state variables in a consistent manner? How can they do so in a way that does not involve any locking?

The answer is surprisingly simple and incredibly beautiful and makes use of something called a transaction memory.


How do transaction memories work?

To start with I must explain why concurrent updates to data represents a problem.


Imagine a server S with some state variable X and two clients C1 and C2. The clients fetch the data from the server (figure 1). Now both clients think that X=20. C1 increases X by 20 and C2 increases X by 30. They modify their local copies, (figures 2) and write the data back to the server (figures 2 and 3). If these updates had been performed one after the other then the final value of X stored on the server would have been 70 and not 50 obviously something has gone wrong.

The conventional way to solve this problem is to lock the server while the individual transactions are taking place, but this approach is thwart with problems as I have pointed out in an earlier article.

To allow these updates to proceed in parallel and without recourse to locking, we can make use of a so called transaction memory.


Transaction Memory

A transaction memory is a set of tuples (Var,Version,Value). In the diagram X has version 1 and value 20. Y has version 6 and value true.

The version number represents the number of times the variable has changed.

Now let's try and do a transaction. Suppose we want to change X and Y. First we send a {get,X,Y} message to the server. It responds with the values of the variables and their version numbers.

Having changed the variables we send a {put,(X,1,30),(Y,6,true)} message back to the server. The server will accept this message only if the version numbers of all the variables agree. If this is the case then the server accepts the changes and replies yes. If any of the version numbers disagree, then it replies no.

Clearly if a second process manages to update the memory before the first process has replied then the version numbers will not agree and the update will fail.

Note that this algorithm does not lock the data and works well in a distributed environment where the clients and servers are on physically different machines which unknown propagation delays.

Isn't this just the good old test-and-set operation generalised over sets?

Yes - of course it is. If you think back to how mutexes were implemented they made use of semaphores. Semaphores were implemented by an atomic test-and-set instruction. A semaphore can only have the value zero or one. The test-and-set operation said if the value of this variable is zero then change it to one this operation was performed atomically. To reserve a critical region it was protected by a flag. If the flag was zero then it could be reserved, if the flag was one then it was being used. To avoid two processes simultaneously reserving the region test-and-set must be atomic. Transaction memories merely generalise this method.

Now let's implement this in Erlang:



-module(tm).

-export([new/0, addVar/2, getVars/2, putVars/2]).

%% new() -> Pid
%% create a new transaction memory (TM)
%%
%% addVar(Pid, Var) -> ok
%% add a variable to the TM store
%%
%% getVars([V1,...]) -> [{Vsn,Data},....]
%% lookup variables v1,V2, ... in the TM
%%
%% putVars([{Var,Vsn,Data}]) -> Bool
%% update variables in TM


%% Heres a sample run
%%
%% 1> c(tm).
%% {ok,tm}
%% 2> P=tm:new().
%% <0.47.0>
%% 3> tm:addVar(x).
%% ok
%% 4> tm:addVar(P,x).
%% ok
%% 5> tm:addVar(P,y).
%% ok
%% 6> tm:getVars(P, [x,y]).
%% [{ok,{0,void}},{ok,{0,void}}]
%% 7> tm:putVars(P, [{x,0,12},{y,0,true}]).
%% yes
%% 8> tm:putVars(P, [{x,1,25}]).
%% yes
%% 9> tm:getVars(P, [x,y]).
%% [{ok,{2,25}},{ok,{1,true}}]
%% 10> tm:putVars(P, [{x,1,15}]).
%% no

new() -> spawn(fun() -> loop(dict:new()) end).

addVar(Pid, Var) -> rpc(Pid, {create, Var}).

getVars(Pid, Vgs) -> rpc(Pid, {get, Vgs}).

putVars(Pid, New) -> rpc(Pid, {put, New}).

%% internal
%%
%% remote procedure call

rpc(Pid, Q) ->
Pid ! {self(), Q},
receive
{Pid, Reply} -> Reply
end.

loop(Dict) ->
receive
{From, {get, Vars}} ->
Vgs = lists:map(fun(I) ->
dict:find(I, Dict) end, Vars),
From ! {self(), Vgs},
loop(Dict);
{From, {put, Vgs}} ->
case update(Vgs, Dict) of
no ->
From ! {self(), no},
loop(Dict);
{yes, Dict1} ->
From ! {self(), yes},
loop(Dict1)
end;
{From, {create, Var}} ->
From ! {self(), ok},
loop(create_var(Var, Dict))
end.

update([{Var,Generation,Val}|T], D) ->
{G, _} = dict:fetch(Var, D),
case Generation of
G -> update(T, dict:store(Var, {G+1, Val}, D));
_ -> no
end;
update([], D) ->
{yes, D}.

create_var(Var, Dict) ->
case dict:find(Var, Dict) of
{ok, _} -> Dict;
error -> dict:store(Var, {0,void}, Dict)
end.








Friday, September 01, 2006

Why I don't like shared memory

In my last blog concurrency is easy I wrote about a simple model for programming concurrent systems. When you write a blog you have to think about the target audience and what level you want to pitch the blog at. Should it be technically advanced, or should it popularise the ideas you want to talk about?

I chose to talk about concurrency in a decidedly non-technical manner, I thought I'd use the analogy of people talking to each other. In my blog I argued that processes should behave pretty much like people. People have private memories and exchange data by message passing.

Now reactions to this were beyond my expectations. To start with a lot of people read what I'd written - this came as a surprise. Hardly without publicising the article it reached the #3 stop on programming.reddit.com - indeed last Wednesday three of the top five programming articles on reddit.com were about Erlang. Secondly a discussion thread started on reddit.com where people discussed what I'd written.

Here I'm going to answer the first point that was raised in the discussion thread:





"dogger" said this:


I'm not sure I quite got why not having shared memory was so great. His example of throwing simple question/answer messages around isn't really how lots of programs work. I think sending messages has its place, as does shared memory. Choose which ever one is most appropriate.




Good comment! the things that we take for granted are the things we feel the least need to explain. Now I take the view that sharing memory is wrong. Having thought this way for the last twenty odd years I take this as axiomatic, and never really explain why I think shared memory is a bad idea - so in what follows I'll give are a number of reasons why I don't like sharing memory.

Dogger's second comment "His example ... isn't really how lots of programs work" Is of course, correct. Lots of programs do not work in the way I have suggest, the point is that these program could have been written in a different programming style which totally avoids shared memory and locks and which does make use of fine-grain concurrency and pure message passing. I also believe that such programs are much easier to write and understand since all of the problems with shared memory that I list below are sidestepped. Note that I do not suggest that I have a solution to any of the problems below. But I would say that such problems can be avoided altogether by using a different programming style.

Now I'll turn to why I don't like shared memory:

Problem 1 - Programs that crash in a critical region

The following approach is commonly used when two or more programs wish to share memory. Any program that wishes to manipulate shared memory, must do the following:
  1. Acquire a lock
  2. Manipulate the shared memory
  3. Free the lock
The code that the program executes after acquiring the lock and before freeing it is called the critical region.

During the time that the program is inside a critical region it should not crash, and it should not spend too much time inside the critical region.

But what happens if the program does crash inside the critical region?


In this case things get messy. In an ideal world we would like to have some kind of transaction semantics, meaning that the net effect of running the program would be either that all the memory changes made inside the critical region succeeded or none of them succeed and the state of memory is the same as it was before the program entered the critical region.

Suppose that A tries to change 10 memory locations, I'll call them M1,M2,...,M10, and that the program was supposed to do this:

  1. Acquire a lock
  2. Modify M1
  3. Modify M2
  4. ...
  5. Modify M10
  6. Release the lock
But in fact it did this:
  1. Acquire a lock
  2. Modify M1
  3. Modify M2
  4. Crash
We would like the effect of running A to be that either is succeeded and all the memory changes M1 to M10 took place, or that none of them succeeded. So having crashed at step 4 of the above we would like to undo the effect of the first two modifications of memory.

Achieving this is pretty complicated, it assumes that there is some monitor program that can detect that a thread has crashed and which reset the memory to its original state in the event of a crash.

Problem 2 - Programs that spend too long time in the critical region

A number of things can happen when a program is inside a critical region, it can manipulate memory, which is why it must be in the critical region in the first place, and it can perform computations. The problem is that these computations take place while the program is inside the critical region - so if these computations take a long time, then all other programs waiting to access the shared memory will be queued until the current program has left the critical region.

Writing code that executes inside the critical region can be very difficult, since we have avoid very time consuming computations and move them outside the critical region. We also have to remove things like remote procedure calls from the critical region, in case they should suddenly take too long. All of this is a very unnatural way of programming and extremely difficult to get right.

Problem 3 - Locking too much

Unfortunately we often lock far more memory than we need to, a program will typical lock all the shared memory, just to manipulate one tiny fragment of it. In languages which permit direct memory modification through pointers then the minimum size of memory that can be protected is determined by the granularity of the page tables. A typical page size might be in the range 8-64KB - with a page size of 8K you might only want to protect a single byte, but you are forced to protect a minimum of 8KBytes.

Your program might only need to protect 1 Byte, and the other programs in the system might wish to modify some other parts of memory in the same page, yet these have to wait until your program as left its critical region before they can manipulate their portion of the memory.

Now all of this probably doesn't matter on a single CPU where different threads all run on the same CPU, the CPU is always busy and at least its doing something. But on a multi-core CPU it does matter. On a multi-core CPU many of the processes will be waiting to acquire locks despite the fact that logically all these CPUs could be running in parallel.

We could, of course, divide the shared memory into different partitions, and let the program lock onto those parts of memory they were interested in, but now the programming gets even more difficult.

Problem 4 - Distributed shared memory

Now things get really messy. On a single motherboard there really can be a single memory that a number of different CPUs can access, but on a cluster or in a networked distributed system this is just infeasible. What really happens is that each node in the system has its own memory and that reads and writes and locks are applied to the local memory. In any system one of these memories must assume some kind of master role, the other memories in the system assume secondary roles and behave as caches. Then some kind of cache consistency protocol is run between the different memories to ensure that all the processes accessing this memory have a consistent view of the world.

Now all of this is very difficult to achieve - so at this point most programmers just give up and use a fault tolerant distributed database, which is generally pretty slow since it has to do a lot of messy things in the background.

Problem 5 - Sharing limits scalability

Threads which share data cannot run independently and in parallel. Now this doesn't matter on a single-core CPU, but it does matter no a multi-core CPU. At the point in their execution where the threads share data, their execution becomes serial rather than parallel. The critical regions in the threads introduce serial bottlenecks which limits scalability.

If we want really high performance we have to make sure that our applications share nothing, that way we can just replicate our solution over many independent CPUs.

Problem 6 - Sharing can introduce deadlocks

Sometime we try to increase concurrency by some form of fine-grain sharing. The idea is that instead of locking all our memory, we divide the memory into smaller regions and only lock those parts of memory we are interested in. Imagine now two threads P and Q which want access to memory regions A and B. Suppose P locks memory region A and then waits for memory region B, and Q does the opposite, ie it locks first B then waits for A. This results in a deadlock, P and Q now suspend indefinitely

Problem 7 - Sharing makes systems error prone and debugging difficult

Suppose two threads A and B share data. A mistake in A can overwrite data used by B. Even through the code in B was correct it might crash because the data structures it manipulates have been corrupted by A. Now all systems should ideally obey the my program should not be able to crash your program rule - this is clearly not the case when programs can share data.

Debugging becomes horrific. Thread B has crashed, so it seems reasonable to assume that the code for thread B is incorrect - this assumption is wrong, since the code in A is to blame. This separation of cause and effect makes debugging very difficult.

Finally a more general comment

Sharing doesn't exist in the real world

I'm an ex physicist. In classical physics and ignoring quantum effects two objects in the real world cannot exist in the same place at the same time.

If we have two objects they must be at different places. Now the only way one object can interact with another is by sending it a message (say by a light ray). If this light ray encodes some information about a state change, then as far as the receiving object is concerned the state change only becomes known after the message has been received.

In simple relativity theory the concept of simultaneity just does not exist.

The point is that in reality objects do not share state, I believe its not a good idea to model what cannot exist in reality in software.

The idea that you actually need sharing and locks to implement parallel software is false. Everything that can be achieved with sharing and locks can also be achieved with pure message passing and no locks. The is the Erlang way.



In a future posting I'll tell you how to make a transaction memory which provides a lock-free method of achieve fine-grain state consistency in sets of parallel processes.

Wednesday, August 23, 2006

Concurrency is easy

We understand concurrency

A deep understanding of concurrency is hard-wired into our brains. We react to stimulation extremely quickly, in a part of the brain called the amygdala, without this reaction system we would die. Conscious thought is just too slow, by the time the thought "hit the brakes" has formed itself, we have already done it.

On a motorway, I mentally track the positions of dozens, or hundreds of cars, this is done without conscious thought. If I couldn't do this I would probably be dead.

The world is parallel

If we wish to write programs that behave as other objects behave in the real world then these programs will have a concurrent structure.

This is why we should program in a concurrent programming language

And yet most often we program real-world applications in sequential programming languages. This is uncessarily difficult.

By programming in a language what was designed for programming concurrent applications (like Erlang) concurrent programming becomes a lot easier.

Erlang programs model how we think and interact

We don't have shared memory. I have my memory, you have yours, we have two brains, one each, they are not joined together. To change your memory I send you a message, I talk or wave my arms. You listen, you see, your memory changes, but without asking you a question or observing your response I do not know that you have received my messages.

This is how it is with Erlang processes. Erlang processes have no shared memory. Each processes has its own memory. To change the memory of some other process you must send it a message and hope that it receives and understands the message.

To confirm that another process has received your message and changed its memory, you must ask it (by sending it a message). This is exactly how we interact.

Sue: "Hi Bill, my telephone number is 45 67 89 12"

Sue: "Did you hear me?"

Bill: "sure, your number is 45 67 89 12"

These interaction patterns well-know to us, from birth onwards we learn to interact with the world by observing it and by sending it messages and observing the responses.

People function as independent entities that communicate by sending messages

That's how Erlang processes work, and that's how we work so it's very easy to understand an Erlang program.

Erlang programs are made up of lots of little processes all chattering away to each other - just like people.

An Erlang program is made up of dozens, possible thousands or even hundreds of thousands of small processes - all these processes operate independently. They communicate with each other by sending messages. Each process has a private memory. They behave like a huge room of people all chattering away to each other.

This makes Erlang program inherently easy to manage and scale. Suppose we have ten people (processes) and they have too much work to do, what can we do? get more people. How can we manage these groups of people, easy just shout instructions at them (broadcasting).

Erlang processes don't have shared memory, so there is no need to lock the memory while it is being used. Where there are locks, there are keys, and when there are keys the keys will one day get lost and what happens when you loose a key? - you panic.

Distributed software systems with locks and keys always go wrong.

If somebody dies other people will notice

I I'm in a room and suddenly keel over and die, somebody will probably notice, well at least I hope so. Erlang processes are just like people, they can on occasions die. Unlike people when they die they shout out in their last breath exactly what they have died from.

Imagine a room full of people, suddenly one person will keel over and die and just as they die, they say "I'm dying of a heart attack" or "I'm dying of an exploded gastric wobbledgog". That's what Erlang processes do. One process might die saying.

"I'm dying because I was asked to divide by zero", another might say

"I'm dying because because I was asked what the last element in an empty list was"


Now in our room full of people we might imagine there are specially assigned people whose job it is to clear away the bodies. Let's imagine two people Jane and John. If Jane dies then John will fix any problems associated with Jane's death. If Jane dies then John will fix the problems. Jane and John are linked together with an invisible agreement which says that if one of them dies the other will fix up any problems caused by the death.

That's is how error detection in Erlang works, processes can be linked together. If one of the processes dies, the other process gets an error message saying why the first process dies.

That's basically it.

That's how Erlang programs work.

What we've learnt so far

Erlang programs are made of lots of processes. These processes can send messages to each other.

These message may or may not be received and understood. If you want to know if a message was received and understood you must send the process a message and wait for a reply.

Pairs of processes can be linked together. If one processes in a linked pair dies the other process in the pair will be sent a message containing the reason why the first process died.

This simple model of programming is part of a model I call Concurrency Oriented Programming. You can read more about this here.

Tuesday, August 22, 2006

Making Money from Erlang

Last Friday I had lunch with Jane Walerud.

Jane is one of the unsung heroines of the Erlang story. She was the first entrepreneur to recognise that having a better programming technology gave commercial advantages that could be turned into money.

Jane was the first entrepreneur to recognise the commercial value of Erlang and form a new company that would eventually earn over USD 100 million from Erlang.

In 1998, in those heady days before the great IT crash, we formed Bluetail. Bluetail had a strong technical core, composed of the techies who had made Erlang, and Jane. Jane knew all sorts of things like how to start a company, how to raise venture capital, how to write a contract, how to sell software. Things that we knew nothing about.

We knew how to do do techie things like how to write compilers, make databases, make fault-tolerant systems - but not how to turn these ideas into money.

In 2000 we sold Bluetail to Alteon Web Systems for USD 152 million. You can read more about this here.

Since Bluetail, Jane has been involved with eight new companies but she is still looking for ways to exploit Erlang.

Every year we hold the annual "Erlang conference" - people come from all over the world to talk about Erlang. Jane always comes.

"It's a funny thing," Jane said,

"at last year's user conference there were two entrepreneurs - that's a doubling - I used to be all alone."