この記事は、Software Design2010年2月号の特集「ほんとうに知りたいあなたのためのkey-valueストア講座」に寄稿した記事の校正前の版です。
本稿では、巷で話題の軽量データベースライブラリTokyo Cabinetの概要と使い方について説明します。
DBMとは
PerlやRubyやPHPなどのスクリプト言語が世の中に多数存在しますが、どの言語にも必ず連想配列もしくはハッシュと呼ばれる機構があります。これは、キーと値という二つのオブジェクトを関連付けて記憶しておき、キーに一致する値を効率的に取得するための機構です。プログラマの皆さんは日々当たり前のように使っている機能ですよね。
スクリプト言語組み込みの連想配列はメインメモリ上にデータを記録するので、プロセスが終了したらデータが消えてしまいますし、メインメモリの容量以上のデータが扱えないという問題があります。それを解決するのがDBM（DataBase Manager）です。DBMは連想配列をファイル上で実現したものですので、プロセスが終了してもデータは残りますし、ディスク容量の許す限りの大規模なデータを格納することができます。
オリジナルのDBMはUNIXの生みの親であるKen Thompson氏が開発したもので、以下のようなC言語のインターフェイスを備えています。
typedef struct { char *dptr; int dsize; } datum; // データ用構造体
int dbminit (char *name); // データベースを開く
int store (datum key, datum content); // 任意のレコードを保存
datum fetch (datum key); // 任意のレコードを取得
datum delete (datum key); // 任意のレコードを削除
datum firstkey (); // 最初のキーを取得
datum nextkey (datum key); // 次のキーを取得
int dbmclose (); // データベースを閉じる
最近話題に取り上げられることが多いkey-valueストレージですが、その原型は30年も前に世に登場していました。多数のレコードを入れるとファイルサイズが極端に大きくなってしまうとか、プロセス内で同時にひとつしかデータベースを開けないとかいう制限はありましたが、こんな単純なインターフェイスでもデータベース管理機能として実用されていたのです。そして、NDBM、GDBM、SDBM、TDB、QDBM、BerkeleyDB、CDBなど、数多くの製品がDBMを模倣して登場しています。Tokyo Cabinet（以後TCと呼びます）もそういったDBMフォロワーのひとつです。
Tokyo Cabinetの特徴
TCは「DBMのモダンな実装」という製品コンセプトに基づいて開発されました。モダンであるとは、市場に流通するハードウェアの進化によるデータの大規模化や並列処理能力の向上に合わせた機能や性能を提供しているということです。具体的には、以下の点が挙げられます。
- 空間効率が高い
- レコード毎のヘッダが小さく、ファイルサイズも小さくなる
- 時間効率が高い
- アルゴリズムの単純化やメモリの有効活用により、高速に動作する
- 並列性が高い
- ひとつのデータベースにマルチスレッドで並列的に操作を行える
- 64ビット対応
- 理論上、最大8エクサバイト（約9京バイト）までのデータベースが扱える
C言語のインターフェイスだけでなく、各種スクリプト言語から利用するためのバインディングも多く開発されているので、Perl、Ruby、Java、Lua、Python、PHP、Erlang、Haskell、Goなどなど、ほぼ全ての言語のプログラマの方に気軽に使っていただけると思います。
DBM系の実装全般に言えることですが、データベースサーバとネットワーク通信でデータの授受を行うのではなく、アプリケーションプロセス内にライブラリとして組み込んで直接的にデータベースファイルを操作するので、TCは極めて高速に動作します（図1参照）。ファイル入出力がOSのキャッシュに乗っている状態だと、レコードの挿入は1秒に250万回、レコードの取得は1秒に300万回も行うことができます。リレーショナルデータベースしか使ったことのない方がTCを初めて触ったなら、文字通り桁違いの早さに驚かれるかもしれません。
簡単な使い方
TCは、LinuxやFreeBSDやMac OS Xなど、UNIX系のOSで利用することができます。インストール方法は多くのオープンソース製品と同様に、ソースパッケージを展開してビルドコマンドを実行するだけでOKです。ソースパッケージは公式サイト（脚注：http://1978th.net/tokyocabinet/）から入手してください。
$ tar zxvf tokyocabinet-1.4.40.tar.gz # パッケージの展開 $ cd tokyocabinet-1.4.40 # 展開されたディレクトリに移動 $ ./configure # 設定スクリプトを実行 $ make # コマンドとライブラリをビルド $ sudo make install # インストール（rootとして実行）
TCのパッケージにはライブラリだけでなくコマンドラインのツールも同梱されているので、まずはそれを使って簡易的な辞書ユーティリティを実現してみましょう。入力データとして、以下のようなTSV形式（タブと改行区切って行列を表す）のファイルを準備してください。
panda パンダ eagle タカ lion ライオン tiger トラ monkey サル hipo カバ
このファイルをanimal.tsvとして保存したならば、以下のコマンドで辞書データベースを構築することができます。dict.tchというファイルが作成されます。
$ tchmgr importtsv dict.tch animal.txt
この辞書データベースを使って単語を検索してみましょう。第1引数にサブコマンド名、第2引数にデータベース名、第3引数に検索キーを指定します。
$ tchmgr get dict.tch lion ライオン
tchmgrコマンドには、getの他にも、レコードを作成するput、レコードを削除するout、キーの一覧を取得するlistなどのサブコマンドがあり、一通りのデータベース操作をコマンドラインで行うことができます。
実のところ、DBMでできる主な操作はたったこれだけです。こんな単純なものは実用にならないと思われるかもれませんね。しかし、世にある複雑な探索アルゴリズムの多くはDBMに見られるような単純な操作の組み合わせで実現されているので、高速なDBMを獲得することは様々なシステムを効率化する上で強力な武器になります。
スクリプト言語から使う
各種スクリプト言語からTCを使う場合、組み込みの連想配列とほとんど同じように使うことができます。例えばRubyの場合、以下のように使うことができます。
# 標準のハッシュ
hash = Hash::new # ハッシュオブジェクトを生成
hash["foo"] = "bar" # レコードを格納
printf("%s\n", hash["foo"]) # レコードを参照
# TCのオンメモリハッシュDB
require 'tokyocabinet'
db = TokyoCabinet::ADB::new # データベースオブジェクトを生成
db.open("*") # TCのオンメモリハッシュDBに連結
db["foo"] = "bar" # レコードを格納
printf("%s\n", db["foo"]) # レコードを参照
db.close # データベースを閉じる
上記ではTCの抽象データベースという機能を使っています。抽象データベースオブジェクトは、openメソッドで指定するデータベース名で様々な種類のデータベースを切り替えることができます。サポートされているデータベースは以下の6種類です。
| <名前> | <命名規約> |
| オンメモリのハッシュ表 | "*" そのもの |
| オンメモリの二分探索木 | "+" そのもの |
| ファイル上のハッシュ表 | 拡張子が ".tch" |
| ファイル上のB+木 | 拡張子が ".tcb" |
| ファイル上の固定長配列 | 拡張子が ".tcf" |
| ファイル上のコラムテーブル | 拡張子が ".tct" |
オンメモリのデータベースは機能特性が言語組み込みの連想配列と同じだから存在意義がないと思われるかもしれませんが、たいていの場合、言語組み込みの連想配列よりも省メモリかつ高速に動作する利点があります（脚注：参考：http://alpha.mixi.co.jp/blog/?p=791）。
ファイル上のデータベースはDBMの元来の用途であるデータの永続化のために利用できます。キーの完全一致のみでレコードを探せればよいのならハッシュ表データベースを使うとよいでしょう。キーの範囲検索や前方一致検索が必要な場合はB+木データベースを使うとよいでしょう。キーが連番の数値の場合は固定長配列データベースを使うと非常に効率的です。レコードの構造がキーと値のように単純でない場合にはテーブルデータベースを利用するとよいでしょう（コラム1参照）。
Tokyo Tyrant
高速で便利なTCですが、不便な点もあります。データベースの整合性を保証するために、ひとつのプロセスがデータベースを書き込みモードで開いている間は、別のプロセスがデータベースを開こうとするとブロックして待たされてしまうのです。TCはマルチスレッドのプログラミングモデルに最適化されていて、マルチプロセスでアクセスするのには向いていません。
とはいえ、Apacheなどのマルチプロセスモデルのサーバ上でプログラムを動かすような場合にはどうしてもマルチプロセスでデータベースを共有したくなります。そこで、Tokyo Tyrant（以下TTと呼びます）というサーバを開発しました。TCのデータベースを抱え込んだ単一のサーバプロセスに対して複数のクライアントがネットワーク経由で操作指示を出すことで並列処理を実現します。
TTはTCのRPCサービスとみなしてもよいでしょう。事実、TTのクライアントAPIははTCのAPIとほとんど同じなので、TC用に作ったアプリケーションをTT用に書き換えるのは非常に簡単です。その証拠に、Rubyのサンプルコードを見てください。クラス名とopenメソッドの引数が違う以外はまったく同じコードになっています。
require 'tokyotyrant'
db = TokyoTyrant::RDB::new # データベースオブジェクトを生成
db.open("localhost", 1978) # データベースサーバに連結
db["foo"] = "bar" # レコードを格納
printf("%s\n", db["foo"]) # レコードを参照
db.close # データベースを閉じる
TTはmemcachedプロトコルもサポートしていますので、既にmemcachedを使っているシステムをTTに載せ替えるのは、アクセス先のサーバを変えるだけで済みます。筆者が勤務するmixiでもmemcachedプロトコルでTTを利用しています（コラム2参照）。
TTにはLuaというスクリプト言語を組み込むことができ、それによって任意のデータベース操作をサーバ側で行うことができます。key-valueストレージはSQLのような強力な操作言語を持たないのが一般的ですが、サーバ側にスクリプト言語を組み込むことで、SQLよりもさらに柔軟に処理を記述できます。透過的なキャッシュ機構（図2参照）として利用したり、MapReduceモデルの集計処理を実行したりもできます。
まとめ
TCはDBMのモダンな実装で、key-valueストレージの基礎となる連想配列をファイルシステム上で実現するものです。単純な機能しか提供しない分、一般的なリレーショナルデータベースとは桁違いの高速性を実現しています。TTはTCのRPCサービスとして利用することができ、特にWebサービスで利用する際に力を発揮することでしょう。
本稿で紹介したのはTCやTTの機能のごく一部に過ぎません。詳しい情報は公式サイトにある仕様書（脚注：http://1978th.net/tokyocabinet/spex-ja.html）に載せていますので、ぜひご一読ください。Tokyoシリーズには他にも検索エンジンTokyo Dystopiaやコンテンツ管理システムTokyo Promenadeがあり、それらも旺盛に開発を続けています。ご意見やご要望があれば作者にご連絡いただければと思います。
コラム1：テーブルデータベースの使い方
ハッシュ表やB+木などのデータベースはあくまでキーと値の関係を記録するkey-valueストレージの範疇に収まりますが、テーブルデータベースはそれらとは大きく異なります。レコードを識別するためにユニークなキー（主キー）を必要とするところは同じですが、値として任意の名前をつけたコラムを複数持つことができるのです。連想配列の値としてさらに連想配列を入れるようなイメージです。
シリアライズして文字列に変換すれば他のデータベースにも連想配列を格納することはできますし、実際テーブルデータベースはそのような実装になっています。テーブルデータベースの存在意義は、任意のコラムにインデックスを張れることです。主キーだけでなく、任意のコラムの値を条件として効率的にレコードを探索することができるのです。
例として社員名簿を考えてみましょう。社員番号を主キーとし、名前と部署名と役職をコラムとして各レコードに持たせます。Rubyでそのようなデータベースを作るには、以下のようなコードを書きます。
require 'tokyocabinet'
include TokyoCabinet
db = TDB::new
db.open("sample.tct", TDB::OWRITER | TDB::OCREAT)
db["12"] = { "name" => "John", "div" => "hr" }
db["18"] = { "name" => "Nancy", "div" => "sales" }
db["20"] = { "name" => "Bob", "post" => "ceo" }
db.close
上記で、平社員のJohnとNancyは部署名を持ちますが、CEOであるBobは部署名の代わりに役職を持っています。このように、スキーマを予め定義することなく、レコード毎に違ったデータ構造を持つことができるようなデータベースを、スキーマレスデータベースと呼ぶこともあります。CouchDBやMongoDBのような実装が有名ですが、TCやTTも同じような用途で使うことができます。
営業部に属する人の一覧が欲しい場合、以下ようにクエリを発行します。SQLのようなクエリ言語を使わなくても、簡単な演算子を組み合わせるだけで任意のレコード集合を取得できます。
qry = TDBQRY::new(db)
qry.addcond("div", TDBQRY::QCSTREQ, "sales")
p qry.search()
コラム2：mixiでのTC/TTの用途
月間ページビュー数が150億を越えるmixi.jpですが、その中で最も更新頻度が高いと思われるデータベースとして「最終ログイン時刻データベース」と呼ばれるものがあります。このデータベースには常時1万クライアント以上が接続していて、夜23時頃から25時頃までのピークタイムには秒間数万クエリが殺到することになります。リレーショナルデータベースでこのアクセスを捌こうとするとコストがかかりすぎることから、従来はmemcachedで分散させて最終ログイン時刻を管理していました。しかし、memcachedではデータ消失のリスクを常に抱えて運用することになるため、近頃TTに載せ替えました（脚注：参考：http://alpha.mixi.co.jp/blog/?p=166）。
しかも、今まで分散させて保持していたデータをたった1台のTTに集約させて保持しています。そうすることで複数レコードの一括取得を行う際のパフォーマンスを劇的に向上させることができるのです。150億PVを1台に集約させるって結構すごいことだなと我ながら思います。セッションデータのような小さいレコードを多数管理するようなユースケースでは分散でなく集中させることでコストを下げるという選択肢もあるということです。
TTはmemcachedと同じくサーバ側では分散処理の機能を一切持ちませんが、クライアントライブラリ側でアクセス対象のサーバを割り振ることで分散処理を行うことができます。データの冗長化は非同期レプリケーション機能で実現していて、上記のユースケースでもホットスタンバイのサーバに常に最新データを複製しながら運用しています。ただし、TTはサーバの台数を随時追加するスケールアウトのアプローチには向いていませんので、その場合は本特集で登場するFlareやkumofsなどの採用を検討してみてください。
mixiでは検索エンジンやレコメンドエンジンの内部でTCを直接使っています。検索エンジンが利用するインデックスは、検索語をキーとして、その語を含む文書のIDの配列を値とする連想配列なので、まさにDBMの出番なのです。友人の共通の友人を新たな友人候補として推薦するようなレコメンドシステムでは、ユーザIDをキーとして、その友人のユーザIDの配列を値とする連想配列を操作することになるので、またもDBMの登場となるのです。いずれのケースでもリレーショナルデータベースで論理的に同等のことはできるのですが、処理効率のためにスキーマの非正規化を行うような場合には、いっそのことkey-valueストレージの採用を検討してみるといいかもしれません。
