hdknr’s posterous

基本的な 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 の論文を熟読して分散バージョンを開発中です。

””
　では、どうすればいいのか？　MySQL や PostgreSQL を使った RDBMS sharding でも、動的なノード追加（と無停止での負荷の再分散）を実現したい。というのが、今回コードを書き始めた動機でした。それが Pacific です。
””

　分散 KVS が RDBMS sharding に対して優れている要素としては、事前の分割設計が不要で、動的なノード追加（とそれにともなう負荷の再分散）が容易、といった点が挙げられると思います。一方で、Kai や Kumofs のような最近の実装では eventually consistent でこそ無くなってきているものの、ハッシュベースの分散 KVS は、レンジクエリができなかったり (例: 最新５件の日記を表示)、トランザクションがないためアプリケーションプログラムが複雑になったりするという問題を抱えています。

ただ、この流れは一朝一夕には起こらない。
先日マイクロソフトがクラウド上のデータベースである SQL Data Services の
アーキテクチャ変更を行ったのは、世の中の時間の流れに技術ロードマップを
あわせたためであり、Key Value的な要素を弱め、SQL互換のインタフェースを
より重視した実装となる予定だ。技術の普及には教育、運用、互換性保証などの
エコシステム全体に浸透させなければならない。ゴリ押しに技術で先行しても
疲弊するだけである。それでも世の中をがむしゃらに牽引する陣営がでてくれば
話は別だが、ロジカルには難しい判断だ。

■memcached周辺

まず、地道にWebアプリケーションのキャッシュ技術を追求してきた人たちが、
キャッシュ用Key Valueストアとしてデファクトになりつつあるmemcachedに
影響を受けたさまざまなバリエーションを開発し、大規模Webアプリケーションに
組み込んで実際に効果を上げつつあるという、健全かつオーガニックな流れがある。

それぞれの詳細は、WEB+DB PRESSの特集に詳しいが、MemcacheDB、repcached、
Flare、Tokyo Tyrant、groongaなどmemcached互換のプロトコルを持つものや、
Tokyo Cabinet、GDBM、QDBM、TinyCDB、CouchDBなどの実装が存在する。
なぜこのようなフラグメントな状態になっているかを解く鍵はmemchachedにある。

まず、memcachedは非常にシンプルな構造であり、6000行そこそこのソースで、
200K程度のバイナリとなる。Facebookやmixiなど大規模Webサイトを支える
基盤としては正直ギャップを覚える。そしてこの衝撃的なシンプルさが

1.技術的興味を持った若者がソースを追ってみたくなる
2.memchached自体がシンプルなので場合により追加実装が必要になる
3.個人または少人数で追える、実装できる規模である

という波及効果を生み出し、キャッシュ用Key Valueストアおよびその派生を
生み出す原動力になっているのだろう。自身もスタートアップ企業でのCTOを
経験しながら東工大准教授となっている首藤氏も驚いていたようだが
日本人の若者が多く関わっている姿は頼もしい限りである。

key-valueストアの良さは、関数型言語やMapReduceと相性がよいことだ。
CouchDB がErlangという風変わりな関数型言語で実装されているのは注目に値すると思う。
並列処理による処理の高速化(MapReduce)、分散システムによるフォールトレランス(耐障害性)などの特徴があるのだろう。

最近のWebアプリは、MVCモデルのうち、Viewの部分に技術革新が起きている。
最新バージョンのRailsが持つCookie Session Storeのように、非同期処理の機構をWebアプリに導入することで、Webアプリをデスクトップアプリのように、ネットワーク接続に無関係のまま扱えるようにしたい。

基本的な動かし方

python code

1. import kademlia_tcp
2. kademlia_tcp.DEBUG = True
3. n = kademlia_tcp.KademliaNode("ip address", port)
4. n.join(n)
5. remote = kademlia_tcp.ContactNode("ip address", port)
6. n.join(remote)
7.  

という感じでネットワークを作れます。DEBUGをセットすると、通信情報など、様々な情報が出力されます。あとは

python code

1. key = n.hash("key")
2. n.publish(key, "value")
3. n.find_value(key)
4. n.ping(other_node)
5. n.store(other_node, key, value)
6. n.find_node(other_node)
7.  

というようなメソッドが使えます。

Kai に kademlia の組み込みを提案する為、試しに作っていたのですが、README に書いた How to Use の項目が動くようになったので晒してみます。

cooldaemon’s ermlia at master — GitHub

• Azureus

アルゴリズムはKademlia、プロトコル部は独自

• BitComet

アルゴリズムはKademlia、プロトコル部はBitTorrent互換

• BitTorrent

アルゴリズムはKademlia、プロトコル部はKhashmirで実装

• eMule

アルゴリズムはKademlia、プロトコル部はKadネットワークと呼ばれる

• LimeWire

アルゴリズムはKademlia、プロトコル部はMojitoDHT