Vector clocks in Erlang
This post came from a short-lived blog I tried to run (tail-recursion.net) where I wanted to write up a short bit of code I'd written that week.
This is a complete implementation of vector clocks in Erlang. As I was
reading Distributed systems for fun and
profit, chapter 3 covered
vector clocks. It's something I could do with what I've learned of
Erlang so far, so I decided to implement it. It spawns a process that
handles vector clocks for this node. While I learned this before
starting to learn gen_server or any other OTP behaviours, Erlang
Programming was building up to it, so some of the same traits are
present here. This could be improved by putting it in a gen_server
implementation (which I will do), but it represents the start of my
Erlang journey. Namely, it furthers my understanding of computer
science by putting into practice a concept from distributed systems.
-module(vclock).
-export([start/1, stop/0, get/0, increment/0, merge/1, forget/1]).
-export([init/1]).
Process set up minutae
start(Name) ->
VClock_pid = spawn(vclock, init, [Name]),
register(vclock, VClock_pid).
stop() ->
call(cmd, stop),
receive
{reply, ok} ->
ok
end.
init(Name) ->
Vclock = maps:new(),
vclock(Name, maps:put(Name, 0, Vclock)).
call(Type, Message) ->
Pid = self(),
vclock ! {Type, Pid, Message}.
The heart of the vector clock process
vclock(Name, Vclock) ->
receive
{cmd, Pid, stop} -> Pid ! {reply, ok};
{request, Pid, get} ->
Pid ! {reply, {clock, lists:keysort(1, maps:to_list(Vclock))}},
vclock(Name, Vclock);
{request, Pid, increment} ->
Node_time = maps:get(Name, Vclock),
New_vclock = maps:update(Name, Node_time + 1, Vclock),
Pid ! {reply, ok},
vclock(Name, New_vclock);
This is a little ugly, and probably should be put into a generic handler. However, it was my first introduction to Erlang maps and I'm still getting a feel for the language.
{request, Pid, {merge, Other_vclock}} ->
Other_map = maps:from_list(Other_vclock),
Other_nodes = maps:keys(Other_map),
Nodes = maps:keys(Vclock),
All_nodes = lists:usort(Nodes ++ Other_nodes),
New_vclock = merge(Vclock, Other_map, All_nodes),
Pid ! {reply, ok},
vclock(Name, New_vclock);
{request, Pid, {forget, Node}} ->
case Node of
One of the things I love about pattern matching is that I don't have to check equality of the name: if it matches the name argument to this function, the pattern match will catch that here.
Name ->
Pid ! {reply, bad},
vclock(Name, Vclock);
_ ->
Nodes = maps:remove(Name, Vclock),
Pid ! {reply, ok},
vclock(Name, Nodes)
end
end.
Merging is a tail-recursive function. Normally in Erlang, errors aren't caught but they're caught here to detect when it's appropriate to give a default value to a node's clock.
merge(Vclock, _, []) -> Vclock;
merge(Vclock, Other, [Node | Nodes]) ->
Time1 = case maps:find(Node, Vclock) of
error ->
0;
{ok, T1} -> T1
end,
Time2 = case maps:find(Node, Other) of
error ->
0;
{ok, T2} -> T2
end,
New_vclock = maps:put(Node, max(Time1, Time2), Vclock),
merge(New_vclock, Other, Nodes).
Client access
get() ->
call(request, get),
receive
{reply, {clock, Clock}} -> Clock
end.
increment() ->
call(request, increment),
receive
{reply, Response} ->
Response
after timeout() ->
timeout
end.
Not being fluent in Erlang, the timeout is a hard-coded value. In practice, it would be useful to have a network-adaptive timeout.
timeout() ->
1500.
merge(Vclock) ->
call(request, {merge, Vclock}),
receive
{error, Error} ->
{error, Error};
{reply, ok} ->
{reply, ok}
end.
forget(Node) ->
call(request, {forget, Node}),
receive
{reply, ok} ->
ok
after timeout() ->
timeout
end.
I wanted to include this to provide a snapshot of my first experiences with Erlang. It'll be interesting to see future code snapshots.
The untransformed code is available.