耐障害性の高いConsistent Hashingを実装してみる

GitHub - dchiji/Cradle: Consistent Hashing

とあるプロジェクトの一環で作ったプログラムで、突然あるノードが落ちても一瞬でネットワーク再構成/データ復旧することが可能な程度の耐障害性が特徴です。
Consistent Hashingということで、当然のことながらデータ保持時の負荷分散もサポートしています。
実用に耐えるのは難しいかもしれませんが、簡易KVSとして試用しても良いレベルだと思っています。

利用するにはErlang処理系をインストールしておく必要があり、テストにはR12B-5を使用しました。

使用方法

準備

src/dssg.erlをダウンロードして

$ erlc dssg.erl

を実行しておきます。

新規ノードを立ち上げる

start関数を引数無しで呼び出すことにより、新規ノードを立ち上げることができます。
また、ノード追加時に必要なノード名を得るためにnode関数を呼び出します。

$ erl -sname hoge
Erlang (BEAM) emulator version 5.6.5 [source] [async-threads:0] [kernel-poll:false]

Eshell V5.6.5  (abort with ^G)
(hoge@daiki-eeepc)1> dssg:start().
true
(hoge@daiki-eeepc)2> node().
'hoge@daiki-eeepc'

ノードの追加

node関数を呼び出して得たノード名(ここでは 'hoge@daiki-eeepc')をstart関数の引数にすることでネットワークにノードを追加することができます。

$ erl -sname foo
Erlang (BEAM) emulator version 5.6.5 [source] [async-threads:0] [kernel-poll:false]

Eshell V5.6.5  (abort with ^G)
(foo@daiki-eeepc)1> dssg:start('hoge@daiki-eeepc').
true

データのput/get

ノードを立ち上げた状態でputv(Key, Value)もしくはgetv(Key)を呼び出すことで、値のput/getを行うことができます。

(hoge@daiki-eeepc)3> dssg:putv(a, hogehoge).
{<0.37.0>,
 {put,1337672431590932383376536722780050290890528640001,a,
      hogehoge}}
(hoge@daiki-eeepc)4> dssg:getv(a).          
{ok,{1337672431590932383376536722780050290890528640001,
     hogehoge}}

ノードのleave(終了方法)

^Cをすると

BREAK: (a)bort (c)ontinue (p)roc info (i)nfo (l)oaded
       (v)ersion (k)ill (D)b-tables (d)istribution

と表示されるので、「a」キーをタイプして処理系を終了させます。