Interval tree clock

Version: 0.3.0

Authors: Nyiro, Gergo (gergo.nyiro@gmail.com).

References

Interval Tree Clocks: A Logical Clock for Dynamic Systems

Summary

Interval tree clock (itc) is a good candidate for a logical clock in a distributed system where the members join and leave the cluster very often.

Itc offers the following actions:

seed: initialize a clock
event: increment the clock
fork: create clock for the new cluster member
join: synchronize the clocks
leq: compare two clocks

Simple Scenario

Initialize a clock:

1> Tic0 = itc:seed().
{1,0}

Create clock for a new cluster member:

2> [Tic1, Toc1] = itc:fork(Tic0).
[{{1,0},0},{{0,1},0}]

The forked clock cannot be compared to the original clock:

3> itc:leq(TicA0, TicA1).
true
4> itc:leq(TicA1, TicA0).
true

Only the tic of the next event can be compared to the original clock:

5> Tic2 = itc:event(Tic1).
{{1,0},{0,1,0}}
6> Toc2 = itc:event(Toc1).
{{0,1},{0,0,1}}

So the clocks can be ordered:

7> itc:leq(Tic0, Tic2).
true
8> itc:leq(Tic2, Tic0).
false

If the cluster nodes are synchronized then the clocks can be joined

9> TicC3 = itc:join(TicA2, TicB2).
{1,1}
10> itc:leq(TicA2, TicC3).
true

and the new clock can be used in the syncronized nodes.

Event store

The itc can be the time stamp of a distributed event store. The events module is an example for such a usage. The event store can be initialized with the events:init/0 function:

1> EventsA0 = events:init().
[{{1,0},init}]

New action can be added to the store with events:append/2 function. (The action can be any term in our example.)

2> EventsA1 = events:append(EventsA0, {action, 1}).
[{{1,1},{action,1}},{{1,0},init}]
3> EventsA2 = events:append(EventsA0, {action, 2}).
[{{1,2},{action,2}},{{1,1},{action,1}},{{1,0},init}]

A new event store can be forked with the events:fork/1 function:

4> [EventsA3, EventsB3] = events:fork(EventsA2).
[[{{{1,0},2},fork},
  {{1,2},{action,2}},
  {{1,1},{action,1}},
  {{1,0},init}],
 [{{{0,1},2},fork},
  {{1,2},{action,2}},
  {{1,1},{action,1}},
  {{1,0},init}]]

The event store may got separated events, but the last common time stamp can be found with the events:get_last_seen_event_tic/2. (Where the second parameter is the last time stamp of the compared event store.)

5> EventsA4 = events:append(EventsA3, {action, 4}).
[{{{1,0},{2,1,0}},{action,4}},
 {{{1,0},2},fork},
 {{1,2},{action,2}},
 {{1,1},{action,1}},
 {{1,0},init}]
6> EventsA5 = events:append(EventsA4, {action, 5}).
[{{{1,0},{2,2,0}},{action,5}},
 {{{1,0},{2,1,0}},{action,4}},
 {{{1,0},2},fork},
 {{1,2},{action,2}},
 {{1,1},{action,1}},
 {{1,0},init}]
7> EventsB4 = events:append(EventsB3, {action, 14}).
[{{{0,1},{2,0,1}},{action,14}},
 {{{0,1},2},fork},
 {{1,2},{action,2}},
 {{1,1},{action,1}},
 {{1,0},init}]
8> LastTic = events:get_last_tic(EventsA5).
{{1,0},{2,2,0
9> SyncFrom = events:get_last_seen_event_tic(EventsB3, LastTic).
{{0,1},2}

The unseen events can be selected with the events:list_unseen_events/2 function, where the second parameter is the last common time stamp from the events:get_last_seen_event_tic function. And the unseen events can be merged into the event store with the events:merge/2 function.

10> UnseenEventsA = events:list_unseen_events(EventsA5, SyncFrom).
[{{{1,0},{2,2,0}},{action,5}},{{{1,0},{2,1,0}},{action,4}}]
11> events:merge(EventsB3, UnseenEventsA).
[{{1,4},merge},
 {{{1,0},{2,2,0}},{action,5}},
 {{{1,0},{2,1,0}},{action,4}},
 {{{0,1},2},fork},
 {{1,2},{action,2}},
 {{1,1},{action,1}},
 {{1,0},init}]

As you can see the time stamp of the merge event is normalized, because the two branch of the itc is merged too.

Event server

The synchronization protocol described above is implemented in the event_server module.

1> event_server:start_link(a).
{ok, <0.N.0>}
2> event_server:add(a, 1).
ok
3> event_server:add(a, 2).
ok
4> event_server:list(a).
[2,1]
5> event_server:start_link(b).
{ok, <0.N.0>}
6> event_server:join(b, a).
ok
7> event_server:list(b).
[2,1]
8> event_server:add(b, 3).
9> event_server:list(a).
[3,2,1]
10> event_server:start_link(c).
{ok, <0.N.0>}
11> event_server:join(c, b).
ok
12> event_server:add(c, 4).
ok
13> event_server:add(a, 5).
ok
14> event_server:list(a).
[5,4,3,2,1]
15> event_server:list(b).
[5,4,3,2,1]
16> event_server:list(c).
[5,4,3,2,1]

Generated by EDoc