先日の記事 「2012-03-07SekkaKVSTRIE* Sekkaにトライ木を実装するとしたら ver-1」からの差分。 GitHub上で実際にdistributed-trieという名前でライブラリを実装してみた。 現在は鋭意パフォーマンス計測中。

分散トライ木

トライ木は通常、C言語などのようなbit単位でデータを操作できる低レベル言語で実装されるのが一般的だ。 同一のマシンの同一プロセス空間にポインタなどを使って密結合なデータ構造を作るのがポピュラーなやりかた。 一方、今回私が作ったdistributed-trieはセオリーから外れており、Pure Rubyで書いてあるのと、複数のマシンから成る分散ハッシュテーブル(KVS)上にトライ木を構築するといったものだ。

分散のメリット

巨大な辞書を分散ストレージで一元管理し、パフォーマンスが足りなくなってきたらマシンをスケールアウトして対応することを狙っている。 Googleの「もしかして？」機能のようなスペルミス訂正などに使えると思う。 AWS EC2を使えば、リクエストが少ない時間帯は稼動マシン数を減らすなどしてコストを抑えることも可能だ。

distributed-trieの特徴

構成図

* Trie木の例

“A”, “to”, “tea”, “ted”, “ten”, “i”, “in”, “inn” というキー群によるトライ木

* 役割範囲はキー群の管理に限定

以下のキー部分の操作ライブラリが担当する。

    *key*      *value*    1   node:$     "i$ t A$"    2   node:i     "n$"    3   node:in    "n$"    4   node:t     "e o$"    5   node:te    "a$ d$ n$"

つまり、トライ木のキーに対応するデータは、ライブラリの責任範囲外。アプリケーションは自分でデータを格納する。 データの内容はアプリケーションの都合で自由に決めれる。

1 DATA:to データ7 2 DATA:i データ11 3 DATA:in データ5 4 DATA:inn データ9 5 DATA:tea データ3 6 DATA:ted データ4 7 DATA:ten データ12 8 DATA:A データ15

* トランザクション機能はKVS機能の担当

例えば、Tokyo Cabinetは複数エントリの一貫性を保持するトランザクション機能を持つ。 これも、ライブラリの責任範囲外。 トライ木の構築とトライ木に対応したデータの格納をトランザクションで括れば一貫性のあるデータ管理ができる。 ※ 分散KVSで一貫性を持つものはほとんど無いため、あまりトランザクションを使う場面は無いかもしれないが…

* KVSはプラッガブル

ユーザーがKvsIfクラスと同じ挙動を示すクラスを用意すれば、何にでもトライ木を構築できる。 例えば、DynamoDB、HBase、Okuyamaなど、Rubyのバインディングが存在するKVSなら簡単にトライ木を構築できる。 現段階では distributed-trie は Tokyo Cabinet / memcached / gdbm / SimpleDB / DynamoDB / Redis / ruby’s pure hash をサポートしている。

パフォーマンスの特性がわかってきたら、またブログ記事を書く予定。