Key で sort 済みの Key-Value Storage を作り始めた

タイトルの通り Key で sort 済みの Key-Value Storage を作りはじめました。
良くある DHT だと Key の Hash を取る事で分散させるので順序情報を失ってしまうのですが、それを Skip Graph という仕組みで順序情報を保持したまま分散させることが可能になります。

sort 済みだとうれしいのは KVS に対して Range Query が可能になること。
例えば、empno-999 以上の value リストを 最新10件、KVS に要求するみたいなことが出来るようになります。

従来の KVS では上記のような Range Query は不可能だったので、そこは RDBMS に任せていたと思うんですが。（RDBMS で Range Query 後、Key のリストを KVS に投げるなど）
この辺りの RDBMS の負荷と分散しづらさを KVS 側で引き取り、かつ KVS のスケールアウトしやすさをそのまま維持しようというのが狙いです。
基本的な API は memcached プロトコルに以下の２つを追加するイメージです
index-name は sort 済みのデータの固まりを識別するためのものです。

get_sorted(index-name, key1, key2, limit, order) => sorted list of values
put_sorted(index-name, key, value) => undef

1ノードのみのプロトタイプは手元で動いているので、id:viver さんに教えていただいた、Skip Graph の論文を熟読して分散バージョンを開発中です。