Kyoto Cabinet 1.2.2から加わったGrassDBは、オンメモリでページ管理を行うB+木を実装してメモリを節約しちゃう仕組みである。それを使ってJava、Python、Ruby、Perlなどのハッシュ（連想配列）機構を鬼のように省メモリにしてみる。頑張ればなんと20分の1になる。
前提
B木やその変種のB+木などは、キーの順序が近いレコード群を「ページ」という単位にまとめてシリアライズしてストレージに書き込むことで、入出力の頻度を減らして高速化することを意図している。メモリに比べて低速なストレージの上で大量のデータを管理するために使われる。多くのRDBMSやいくつかのDBMがB+木をサポートしているのはそれが理由であろう。一方で、メモリ上で検索可能なデータ構造を表現するためには、二分探索木やその特殊例である赤黒木が使われる。STLのstd::mapの実装にも赤黒木を使うのが一般的である。個々のレコードが木のノードに紐付けられていれば、探索に必要な処理もレコード単位で行うことができて効率的だからである。
大事なことなのでさらに言い換える。B木は複数のレコードをまとめてノードを構成するので、個々のノードは大きくなる代わりに、ノードの数は少なくなる。一方で二分探索木は個々のレコードがノードになるので、個々のノードは小さい代わりに、ノードの数は多くなる。ファイル上で木を表現する場合にはノード間移動にファイル入出力という重い処理が伴うので、ノード数を少なくするB木を用いるのが適切である。メモリ上で木を表現する場合には、ノード間移動はポインタを辿るだけでできるので、ノードの操作（回転など）の局所性が高い二分探索木を用いるのが適切である。
オンメモリのB+木
上述のとおり、オンメモリなら赤黒木を使えばよいので、オンメモリのB+木なんて普通は使わない。赤黒木だったら目的のレコードまでの探索経路上に表れるlog2(N)個のレコードを読めば探索処理が完結するが、B+木は目的のレコードまでの探索経路上に表れるノードに乗っかっている関係ないレコードまで読み込んで、デシリアライズした上で探索処理を行わなければならないので、どうしても時間効率が悪くなってしまうのだ。
しかし、空間効率の点ではB+木の方が赤黒木よりも優れている。赤黒木の各ノードは左右の子ノードへのポインタを持つ必要があるため、64ビットプロセッサの環境においては、少なくとも8*2=16バイトのオーバーヘッドが各レコードにかかることになる。それ以外にレコード自体のキーや値のデータ（長さとポインタ）をメモリ上に確保する必要がある。B+木ではノードの数が少なく、またノードの中のレコード群をシリアライズして持つため、ポインタのオーバーヘッドやレコード自体のデータのメモリアラインメントによるオーバーヘッドが小さくなるので、結果的にレコード毎に必要な空間が小さくなる。
さらに、KCのB+木はノード毎の圧縮をサポートしているので、それを使うと、オーバーヘッドを減らすのみならず、レコードの実データの総量よりもさらに小さいメモリ使用量で、大量のレコードをオンメモリで扱うことができるはずだ。B+木は赤黒木に比べてただでさえ遅いのにさらに圧縮処理なんて入れるともっと遅くなってしまうのだが、今現在の作業は時間と空間のトレードオフで空間効率を重視した市場を開拓するものであるから、この際、時間効率は置いといて、空間効率のみを追求するオプションも考えてみる価値がある。
実装
ディレクトリツリーデータベース（ForestDB）を作った時に、ファイルツリーデータベース（TreeDB）をテンプレート化して、下層のページ管理アルゴリズムを切り替えられるようにしてある。ディレクトリツリーデータベースではディレクトリハッシュデータベース（DirDB）を使い、ファイルツリーデータベースではファイルハッシュデータベース（HashDB）を使っている。同じ勢いで、キャッシュハッシュデータベース（CacheDB）をページ管理アルゴリズムに用いたB+木として「キャッシュツリーデータベース」も簡単に実装できるはずだ。そして、その名前は「GrassDB」にした。「TreeDB」が揮発性になったものなので、草（木だけど冬を越せない）のイメージからとったものである。
ここで、そもそものTreeDBの実装について振り返ってみる。TreeDBにおいては、データは「ハッシュ層」と「ツリー層」の2階層に分けて管理している。ハッシュ層はHashDBが担当し、シリアライズしたノードのデータをファイルで管理するものである。ツリー層がTreeDBの本体であり、必要なノードをハッシュ層からロード（ページイン）してオンメモリで扱いやすい構造に一時的にデシリアライズしてキャッシュしておき、B+木の探索や更新や再構成をメモリ上で行う。メモリに余裕があるうちは全てのノードをツリー層で扱うのだが、キャッシュサイズが一定を越えた場合には、あまり使われない（LRUな）ノードをハッシュ層に追い出す（ページアウト）する。ページアウトの際、ロードされてから更新されてダーティフラグが立っているキャッシュはファイルに書き戻し、そうでないキャッシュは単に捨てられる。圧縮オプションが有効になっている場合、圧縮はページアウトの際に行われ、伸張はページインの際に行われる。つまりツリー層にあるデータは圧縮されていない。
ストレージであるべきハッシュ層をCacheDBにすると、ツリー層もハッシュ層もキャッシュであるという奇妙な構成になる。ツリー層はデシリアライズされているので空間効率は赤黒木とさほど変わらない（ノード内は配列なのでツリーよりは効率はいいけど）。空間効率を最大化させるにはやはりツリー層の割合を減らしてハッシュ層に多くのデータを置くのがよいだろう。その調整はチューニングパラメータでできるようにしている。
で、CacheDBは既に実装されているので、あとはテンプレート（PlantDB）にそれを差し込んでインスタンス化するだけである。メタデータやチューニングパラメータ等でインターフェイスの微調整は必要だったが、それほど難しくなく実装はできた。
typedef PlantDB<CacheDB> GrassDB;
性能
KCの全種類のデータベース型を気軽に扱える多相データベースを使って100万レコードの書き込みテストを行う。例によってキーと値は8バイトずつで「00000001」「00000002」…てな内容。試すのは以下のケースである。
- ProtoHashDB（std::unordered_mapのラッパー）
- kcpolytest order -set "casket#type=-" 1000000
- ProtoTreeDB（std::unorderedのラッパー）
- kcpolytest order -set "casket#type=+" 1000000
- CacheDB
- kcpolytest order -set "casket#type=*" 1000000
- GrassDB（デフォルト）
- kcpolytest order -set "casket#type=%" 1000000
- GrassDB（省メモリ設定）
- kcpolytest order -set "casket#type=%#bnum=50000#psiz=32768#pccap=1m" 1000000
- GrassDB（圧縮設定）
- kcpolytest order -set "casket#type=%#bnum=50000#psiz=32768#pccap=1m#opts=c" 1000000
上記のテストコマンドを俺の環境（Core i7 2GHz、メモリ2GB、Ubuntu 10.04）で実行してみたところ、結果は以下のようになった。
| 名前 | 使用メモリ | 経過時間 |
| ProtoHashDB | 136,466,432 | 0.859 |
| ProtoTreeDB | 159,907,840 | 2.924 |
| CacheDB | 72,392,704 | 0.551 |
| GrassDB（デフォルト） | 59,170,816 | 0.826 |
| GrassDB（省メモリ設定） | 21,172,224 | 0.772 |
| GrassDB（圧縮設定） | 7,487,488 | 1.454 |
std::unordered_mapに100万件を格納すると、136MBのメモリを食い、std::mapに100万件を格納すると、159MBのメモリを食う。これ結構いけてないよね。キーと値のサイズの全レコードの合計は16MBだから、ほとんどがデータ構造によるオーバーヘッドだということになる。それに比べるとCacheDBは72MBほどなので、空間効率がかなり向上している。これは個々のノードのメモリ配置を工夫しているからである。
GrassDBのデフォルトでは59MBのメモリを食っているが、これはデフォルトの設定（キャッシュ容量64MB）だと全レコードがキャッシュ層に載ってしまうからである。なのでシリアライズしてハッシュ層にデータを移すべく、キャッシュ容量を1MBに設定し、さらに個々のノードの容量を増やしてノード数減らすためにページサイズを32768Bに設定し、そうするとハッシュ層のバケット数も少なくて済むのでバケット数を50000個に減らしてみた。すると、メモリ使用量は21MBほど。そこからキーと値の合計16MBを引くと、オーバーヘッドは全体で5MB以下ということになる。つまり1レコードあたり5バイトくらい。これは結構いけてるね。圧縮しちゃうともっとすごい。なんとメモリ使用量7MB。元来の16MBの半分になっちゃってる。
弱点
古今東西の天才達がアルゴリズムを研究しまくっている中で、この俺ごときが魔法のように全てに秀でたアルゴリズムをいきなり思いつくはずはない。俺にできるのはバランスを探ることぐらいで、当然ながら長所を見出すために短所を割り切っているのだ。既に述べたように、それは時間効率の悪化である。
上記のテストはシーケンシャルアクセスだったので、B+木でも経過時間が伸びていない。キャッシュ層のヒット率が高いのでシリアライズ（および圧縮）とデシリアライズ（および伸張）の操作の回数が非常に少なくなり、またハッシュ層の負荷も非常に小さくなるからだ。しかし、ランダムアクセスを行う場合はキャッシュ層のヒット率は激減するので、それらの操作による負荷が高くなる。
各テストコマンドに「-rnd」オプションをつけて実行するとランダムアクセスの性能が測れるのだが、その結果は以下のようになる。
| 名前 | 使用メモリ | 経過時間 |
| ProtoHashDB | 88,207,360 | 0.945 |
| ProtoTreeDB | 99,622,912 | 3.439 |
| CacheDB | 43,311,056 | 0.647 |
| GrassDB（デフォルト） | 31,326,208 | 2.559 |
| GrassDB（省メモリ設定） | 16,732,160 | 86.360 |
| GrassDB（圧縮設定） | 2,782,416 | 1119.355 |
ということで、省メモリ設定にしてしまうと、86秒もかかる。圧縮しちゃうともっとひどいことになり、1119秒もかかる。スループットに直すと11579qpsと893qpsだから、まあユースケースによっては許容範囲だとは思うが、GrassDBの利用にあたって時間効率がかなり悪化するということは注意しなければならない。
なお、ノードのシリアライズやデシリアライズの負荷はページサイズに比例するので、ページサイズを減らせば時間効率の悪化は多少緩和される。しかしページサイズを減らすとノード数が増えるので空間効率は悪化する。結局は時間と空間のトレードオフなのだ。
言語バインディングでも使ってほしい
多相データベースクラスでデータベースを開く際に名前を「%」にするとGrassDBが開かれる。Java、Python、Ruby、Perl、Luaの各バインディングでは多相データベースをサポートしているので、当然GrassDBもすぐに使えるようになっている（KC 1.2.2が必要）。KCのAPIは各言語標準のハッシュ（連想配列）機構とほぼ同じように使えるようになっているため、ほんのちょっとの手間で省メモリな計算環境を手に入れることができることになる。Rubyだとこんな感じ。
require 'kyotocabinet'
include KyotoCabinet
# ハッシュを作ってGrassDB省メモリモードに連結
hash = DB::new
hash.open('%#bnum=50000#psiz=32768#pccap=1m')
# レコードを入れる
hash['japan'] = 'tokyo'
hash['china'] = 'beijing'
hash['korea'] = 'seoul'
# レコードを検索する
printf("%s\n", hash['japan'])
printf("%s\n", hash['china'])
printf("%s\n", hash['korea'])
# 全レコードを表示する
hash.each do |key, value|
printf("country=%s capital=%s\n", key, value)
end
# データを破棄する
hash.close
冒頭のグラフに示したように、PythonやRubyやPerlの連想配列に文字列を格納した場合にはだいたいstd::mapと同じような空間のオーバーヘッドがかかる。それをGraphDBの圧縮モードに置き換えると、理想的なケースではメモリ使用量を20分の1にできるというわけなのだ。今回のテストはキーと値が単純すぎるので圧縮が効きすぎている感もあるが、一般的なユースケースでは10分の1くらいにはなると思う。各言語で省メモリなハッシュが使えるというネタはTCの時にも書いたが、その際にはメモリ使用量半減というのを謳っていた。今回はそこからさらに圧倒的に省メモリにしちゃったわけで、なかなかどうしてグーじゃないの。
まとめ
Kyoto CabinetにオンメモリB+ツリーとしてGrassDBというのが加わった。オンメモリのB+ツリーなんてあまり聞かない手法ではあるが、空間効率の観点ではそれなりに利用価値のあるものだと思う。省メモリなハッシュという位置づけはわかりやすくていいんじゃないかな。
なお、特殊なケースでは、局所的に時間効率が悪化しても、空間効率が一定の閾値を越えることで、システム全体の時間効率が向上するということがあり得る。実メモリに載らないほどのデータを扱おうとしてスワップが起きまくって課題が解決できないような場合には、今回のような省メモリの構造を使うと、スワップするよりは時間効率を改善できるかもしれない。もしくは、1台のメモリに載らないから数台に分散させている場合に、省メモリの構造を使うことで1台に集約できるなら、ネットワーク通信の負荷を省略して時間効率の向上に寄与するかもしれない。