Erlang による Skip Graph の実装

参考：
　　Skip Graph の論文
　　http://www.cs.yale.edu/homes/aspnes/skip-graphs-journal.pdf

ソースコードはこちら

特徴

・Erlangによる完全なSkip Graphの実装
　　　・複数マシンを利用してスケールアウト可能
・boot/4関数内のLevel_Maxの値を大きくすることにより、Levelの階層を増やすことができる
　　　＝＞スケールアウトしてエントリ数が増えても、検索効率が落ちない
・keyにatomを指定することもできるので、柔軟な範囲検索を行うことができる
・コードの行数は200行未満

実際の動作（Erlangを知っている人向け）

起動(分散)

<ノードjohn@asus>

$ erl -sname john
Eshell V5.7  (abort with ^G)
(john@asus)1> sg:start().
true
(john@asus)1>

<ノードmary@asus>

$ erl -sname mary
Eshell V5.7  (abort with ^G)
(mary@asus)1> sg:start(john@asus).
true
(mary@asus)1>

実行(分散)

<ノードjohn@asus>

(john@asus)2> sg:put_(3, hoge).
<0.43.0>
(john@asus)3> sg:put_(2, foo).
<0.45.0>
(john@asus)4> sg:put_(4, foobar).
<0.47.0>
(john@asus)5> sg:put_(1, bar).
<0.49.0>
(john@asus)6>

<ノードmary@asus>

(mary@asus)3> sg:put_(6, hoge6).
<0.48.0>
(mary@asus)4> sg:put_(5, hogehoge).
<0.50.0>
(mary@asus)5>

<ノードjohn@asus>

(john@asus)6> sg:put_(7, hoge7).
<0.55.0>
(john@asus)7> sg:get_(4,7).
*** DEBUG sg 70   {get,{key,0}}
*** DEBUG sg 70   {get,{key,1}}
*** DEBUG sg 70   {get,{key,4}}
[foobar,hogehoge,hoge6,hoge7]
(john@asus)8>

atomをkeyに指定

$ erl
Eshell V5.7  (abort with ^G)
1> c(sg).
{ok,sg}
2> sg:start().
true
3> sg:put_(hoge, ken).
<0.42.0>
4> sg:put_(foo, john).
<0.44.0>
5> sg:put_(zoo, noise).
<0.46.0>
6> sg:get_(foo, zoo).
[john,ken,noise]
7>

※これは簡易的な動作デモで、実際は1マシン6万ピアでの高速な範囲検索を確認しています。

今後について

・KVSとして実用的に使えるレベルまで仕上げたい
　　　・Replicationの実装
　　　・耐障害性の強化
・総エントリ数をもとに、プログラムが動的にLevelの階層を変更する機能の実装
・Range-Key Skip Graph化