開発メモ

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	64,390,416	0.613
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は64MBほどなので、空間効率がかなり向上している。これは個々のノードのメモリ配置を工夫しているからである。

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は言語標準のハッシュ（連想配列）機構とほぼ同じように使えるようになっているため、ほんのちょっとの手間で省メモリな計算環境を手に入れることができることになる。

冒頭のグラフに示したように、PythonやRubyやPerlの連想配列に文字列を格納した場合にはだいたいstd::mapと同じような空間のオーバーヘッドがかかる。それをGraphDBの圧縮モードに置き換えると、理想的なケースではメモリ使用量を20分の1にできるというわけなのだ。今回のテストはキーと値が単純すぎるので圧縮が効きすぎている感もあるが、大体10分の1くらいにはなると思う。各言語で省メモリなハッシュが使えるというネタはTCの時にも書いたが、その際にはメモリ使用量半減というのを謳っていた。今回はそこからさらに圧倒的に省メモリにしちゃったわけで、なかなかどうしてグーじゃないの。

まとめ

Kyoto CabinetにオンメモリB+ツリーとしてGrassDBというのが加わった。オンメモリのB+ツリーなんてあまり聞かない手法ではあるが、空間効率の観点ではそれなり利用価値のあるものだと思う。省メモリなハッシュという位置づけはわかりやすくていいんじゃないかな。

なお、特殊なケースでは、局所的に時間効率が悪化しても、空間効率が一定の閾値を越えることで、システム全体の時間効率が向上するということがあり得る。実メモリに載らないほどのデータを扱おうとしてスワップが起きまくって課題が解決できないような場合には、今回のような省メモリの構造を使うと、スワップするよりは時間効率を改善できるかもしれない。もしくは、1台のメモリに載らないから数台に分散させている場合に、省メモリの構造を使うことで1台に集約できるなら、ネットワーク通信の負荷を省略して時間効率の向上に寄与するかもしれない。

Tokyo CabinetとKyoto Cabinetの商用ライセンスをどう定義したら俺にとってハッピーだろうか検討してみた。

背景

俺が作成した各種ソフトウェアのライセンス管理業務を妻に任せて、さしあたって妻の個人事業としてライセンス販売を行ってもらうことにした。KCの名義を「FAL Labs」にしたのはその布石である。事業が軌道に乗れば、法人化したり、人を雇ってサポートサービスを始めたりといったことも検討するが、現状で「箱」だけ作ってリスクを増大させるのもあまり得策ではないと考える。

現状のビジネスモデルを一言で言うと、「お小遣いモデル」あるいは「シェアウェアモデル」である。つまり、ライセンスすべき製品は既にあるので、それをほぼゼロのコストで収益化することを目指す。現時点では、人を雇ったり外部委託業務を発生させたりしてコストやリスクを増大させることなく、生活の足しになる程度の収入を得られればよいと考える。

したがって、営業活動はしない。サポート契約もしない。そしてライセンス契約もできるだけシンプルなものにしたい。それらの制約によって、収益もかなり限定されたものになるだろう。でも、今はそれでいい。

LGPL/GPLのリンク例外

TCはLGPL、KCはGPLで一般公衆にライセンスされているオープンソース製品であり、俺が商用ライセンスを規定したとしても、それらのライセンスが無効になることはない。LGPL/GPLで一旦ライセンスしたバージョンを既にダウンロードしてその条件のもとで製品なりサービスに組み込んで利用している人がいるとして、それを一方的に剥奪することは当然ながら不可能である。次のバージョンからプロプライエタリなライセンスでリリースする権利が俺にはあるが、たとえそうしたとしても、旧バージョンを第三者がメンテナンスしてLGPL/GPLでリリースしつづけることが可能であるので、単なる意地悪という以外に意味はない。よって、TCやKCがオープンソースでありつづけることは絶対的である。

LGPLやGPLについて確認しておこう（詳細は原典で確認してほしい）。TCやKCを組み込んだソフトウェアをLGPLやGPLの条項に基づいて自由なライセンスの下で公開したくない場合には、LGPLやGPLによる利用許諾が認められないので、その他のライセンスを俺と別個に契約することが必要となる。ただし、LGPLであるTCの場合は、TCを動的ライブラリとして第三者が利用可能な形態で配布した状態でそれにリンクする場合に限り、アプリケーションを自由なライセンスにする義務から免れることができる。

以上を踏まえて、プロプライエタリなソフトウェアの開発者がTCやKCとの別個のライセンス契約を望んだ場合に、俺は商用ライセンス契約を提案することとなる。で、まったく新たにライセンスを作ることも考えられるのだが、俺は法律家ではないので、込み入った条項を的確に定義する自信がない。英語と日本語を両方作らなきゃならないし、ちょっと考えるだけでも非常に面倒くさい。そこで、基本的にLGPLやGPLの条項を踏襲した上で、それらのリンク例外という条項をいくつか盛り込むことで商用ライセンスを構成しようと思う。

つまり、LGPL/GPLが宣言するように、あるがまま提供され、商用目的で使おうがいかなる目的で使おうが無保証であるという条件を踏まえた上で、上述した自由なライセンスの伝染性を回避する権利を金銭的対価のもとに提供するということである。

包括ライセンスとその制限

簡単のために、まずは個人または法人に対する包括的ライセンスについて考える。つまり個々の商品に組み込む権利や個々のコンピュータの上で稼働させる権利をその数量に比例させて売るのではなく、その人または会社によって開発され配布される製品に数量的には無制限に組み込むことを許諾するライセンスである。その場合、対象の個人や法人の営業規模によって予めライセンス料金を定めることになる。契約が一回だけになるので簡単であるが、その反面、継続的に収入を得ることは望めない。しかし営業コスト最小の目標の下では包括ライセンスが最も手軽でよい。

ライセンシーは、TCやKCのライセンサーである「FAL Labs」に対して規定の金額を支払うことによって、LGPLやGPLによるソース公開義務を免れて自己の製品を配布することができるようになる。ただし、いくつか制限を加えておかないと我々のビジネスが破綻してしまう。

第一に、そのライセンスによって得た権利を他者に譲渡することはできないようにしなければならない。そうしないと個人にライセンスを買わせて、それを大企業が引き取れば、個人のライセンス料金で大企業が利用できるようになってしまうからだ。これに関しては、その旨をライセンスに明記しておけばそれほど問題はないと思う。ライセンシーが合併したり買収されたりした場合にどう扱うかなどの詳細を詰める必要はあるが。

第二に、TCやKCを組み込んだ製品がTCやKCの単なるラッパーとして実質的にKCやTCの機能そのものを再配布することができないようにしなければならない。そうしないと、あるライセンシーがTCやKCのライセンスを買って、10行程度のラッパーを書いて、それを別の名前でより安価に売ることが可能になってしまい、俺の商売は上がったりになる。この条件を明確にするのはかなり難しいと思っている。「単なるラッパー」なのか歴とした製品やサービスなのかを客観的に判断する指標がない。これは下請け企業が元請け企業にサブシステムを納入するとしてそこにTCやKCを使っていた場合にもあてはまる。

価格

世の中には様々な企業があり、その営業規模（支払い能力）を簡単に測ることは難しいので、包括ライセンスの値付け方式を適正に定めるのは難しい。しかし、いわゆるマーケティングのスキルを全く持たない俺としては、とりあえず会社の規模で定めるのが妥当であろう。以下のような感じだろうか。TCとKCは別個のライセンスとするが、両方契約してくれたら後から契約した方は5割引にしてもいいとかにしようか。

個人	10万円
法人	従業員数一人あたり10万円

これが高いか安いかは正直言ってわからない。従業員数10人の企業だと100万円、100人の企業だと1000万円、1000人の企業だと1億円である。でも、数量無制限って考えると100人企業で1000万円は安いよねぇ。1000人企業で1億円ってのは何か高い気もするけど、いずれにせよ高額案件は応相談って感じになるだろうから、もっと高めに設定しておいてもいいくらいだ。だって、Berkeley DBなんて、「1プロセッサあたり」で5800ドル（50万円ちょい）だよ。

まとめ

GPLリンク例外のライセンスモデルであれば比較的簡単に商売を始められそうだ。価格に関しては高めに設定しておいて、売れなかったら下げればいい。しかし、ライセンスの制限条項に関しては後から厳しくすることは難しいので、売り出す時点でかっちりと決めておかねばならない。が、俺が適当に書くのは後々係争を招きそうで不安だ。

なので、その辺に詳しい方に相談に乗っていただきたいと常々思っているのだが、どなたか私めと飯でも食ってくれる人いませんか。あるいはプロの方で、そのライセンス文書（英文）の策定までコンサルしてくれる方いませんか。

追記：Kyoto Cabinetの宣伝のために、期間限定IRC相談窓口を設けた。freenode（chat.freenode.netとか）で #kyotocabinet にjoinしていただきたい。OSS開発者/プロプライエタリ開発者問わず、何でも聞いてね。

Kyoto Cabinet 1.2.0にて、B+木をディレクトリデータベース上で実装したという話。

ディレクトリツリーデータベース

先日リリースしたディレクトリデータベース（DirDB）は個々のレコードを別個のファイルとして単一のディレクトリ内に格納する実装であり、抽象データベースを継承しているので主なインターフェイスはファイルハッシュデータベース（HashDB）と同じである。

ところで、ファイルハッシュデータベースでページ管理を行ってB+木を表現する実装として、ファイルツリーデータベース（TreeDB）というのが従来からある。ということは、ディレクトリデータベースでページ管理を行ってB+木を表現する実装を考えてもよさそうだ。これをディレクトリツリーデータベースと呼ぶ。木というイメージとたくさんファイルがあるというイメージから、ForestDBという識別子にしようか。区別のために、従来のディレクトリデータベースはディレクトリハッシュデータベースと呼ぶことにする。

実装

TreeDBの実装は全てkctreedb.hに書いてある。その場合、クラス定義の中でHashDBという識別子を使っているところをBASEDBとかいう名前で検索置換して、クラスの前にtemplate <class BASEDB>とか書いてあげて、内部クラス識別子にいくつかtypenameを補うだけで、実装をテンプレート化できる。C++素晴らしい。

こうしてできたB+木実装のクラステンプレートをPlantDBと名づける。そんでもって、ファイルツリーデータベースとディレクトリツリーデータベースは今や以下の実装になってしまった。

typedef PlantDB<HashDB> TreeDB;
typedef PlantDB<DirDB> ForestDB;

これが意味するところは大きい。連想配列のインターフェイスを持つものはたいがい、それをベースとしたB+木に進化させることができるのだ。実際は連想配列（set/get/remove）以外にもファイル操作（open/close）などのインターフェイスを実装しなきゃならないけども、必要ないならダミーでよい。

DirDBをPlantDBに対応させるにあたっては、HashDBで使っていたバケット数などのチューニングメソッドのダミー実装をつける必要があった。テンプレート特殊化でも対処できただろうが、その辺のリファクタリングは今後の課題としよう。

性能

で、実際にForestDBをビルドして動かしてみたところ、驚くべきことに一発でテストケースをパスした。俺すげー。っつかC++すげー。しかも、性能がなぜかTreeDBを凌駕している。これも驚きだ。ファイル数が増えているっていうのに、なぜ高速化するんだろう。例によってキー8バイト値8バイトのレコード100万件のset/get/removeのテスト結果を以下に示しておく。CPUはCore i7 LM620（2GHz）でメモリは4GBでOSはUbuntu10.04でファイルシステムはEXT3（writeback）。

	write	get	remove
HashDB	0.747	0.765	0.675
DirDB	149.592	207.701	215.489
TreeDB	0.727	0.909	0.828
ForestDB	0.709	0.846	0.735

ファイルハッシュデータベースとディレクトリハッシュデータベースを比べると、前者の方が200倍くらい早い。なのに、ファイルツリーデータベースとディレクトリツリーデータベースを比べると、後者の方がほんの少し早くなる。なんでだろう。

今回のテストはB+木のシーケンシャルアクセスをしているので、一旦書き込まれたリーフノードは二度とアクセスされることはなく、ファイルツリーデータベースでは、各ページにおいてwriteかreadを1回発行するのみで処理が終わる。ディレクトリツリーデータベースではそれに加えてopenとcloseが1回づつ加わるので遅くなりそうなものだが、その代わりにcloseした後は関連するリソースの優先度を下げるみたいな効率化がなされていたりするのだろうか。わからん。

ファイルツリーデータベースとディレクトリツリーデータベースに関しては1億件のテストもやってみようか。B+木のページサイズは65536にした。

	write	get	remove
TreeDB	82.625	98.071	107.854
ForestDB	105.450	100.412	112.348

今度はファイルツリーデータベースの方が性能が良くなった。上記の表には現れていないが、ディレクトリツリーデータベースの方はデータベースのclose処理に追加で45秒くらいかかっている。謎だ。でも俺としてはファイルデータベース系が勝つ方が嬉しい。なぜならそれがKCのコアだから。

KCの今後

2つのディレクトリDBが加わったことで、KCは今や技のデパートみたいな状態になってきた。これだけ揃えばかなりいろんなユースケースで活躍できるんじゃないだろうか。

名前	時間計算量	アルゴリズム	ロック粒度	永続性	用途
ProtoHashDB	O(1)	ハッシュ表	全体 (rwlock)	なし	なし（テスト用）
ProtoTreeDB	O(log N)	赤黒木	全体 (rwlock)	なし	オンメモリで順序構造を管理
CacheDB	O(1)	ハッシュ表	レコード (mutex)	なし	キャッシュ
HashDB	O(1)	ハッシュ表	レコード (rwlock)	あり	小さいけど多数のメタデータ的情報
TreeDB	O(log N)	B+木	ページ (rwlock)	あり	小さいけど多数の順序付きメタデータ的情報
DirDB	未定義	未定義	レコード (rwlock)	あり	大きいけど少数のデータ
ForestDB	O(log N)	B+木	ページ (rwlock)	あり	比較的大きく比較的多数の順序付きデータ

ディレクトリツリーデータベースの面白い用途としては、やはり転置インデックスが挙げられると思う。転置インデックスはレコードの長さがどんどん伸びていくのが特徴であり、その場合はフラグメンテーションが起きやすいファイルハッシュデータベースでページ管理をするよりは、フラグメンテーションをほとんど起こさないと言われるEXT3等のファイルシステムを直接使ってページ管理をする方が効率的だろう。

なぜNTFSやFATではフラグメンテーションがよく起こるのにEXT系では起こらないのかと言えば、NTFSやFATではファイル群のデータをパーティションの前方に詰めぎみに配置しようとするのに対し、EXT系ではパーティション全体に個々のファイルのデータを分散させて置くかららしい。ファイルの長さを縮めた時にできる小さすぎて利用不能な隙間とか、ファイルの長さを増やそうとした時に後ろに別のファイルがあってそれができないから別の場所に書き直した場合にできる隙間とかが、もともとパーティション内にファイルが散在していればできにくいということらしい。

KCやTCのファイルハッシュデータベースでは、ユーザがパディングサイズを指定することができて、さらにフリーブロックプールとオートデフラグカーソルが隙間を回収していくことで上述のフラグメンテーションを緩和している。ファイルシステムのようにパーティションサイズが決まっていて、「予めこの領域を使い切っていい」という状態であれば、EXT系のように富豪的に領域を使ってフラグメンテーションをさらに緩和することができるだろう。ユーザから「予約データベースサイズ」を前もって教えてもらえれば同じことができるはずなので、今後それも検討してみる。

なお、多相データベースや各種言語バインディングからディレクトリツリーデータベースを呼ぶには、データベース名の拡張子に「.tcf」をつけるか、オプション文字列「#type=tcf」をつけるかすればよい。その他のオプションはファイルツリーデータベースと同じで、「#psiz=65536」とかでページサイズを調整でき、「#opts=c」で圧縮が有効になり、「#zcomp=arc#zkey=aiueo」で暗号化もできちゃう。すぐれもの。

まとめ

ディレクトリハッシュデータベース上にB+木を構築したディレクトリディレクトリツリーデータベースを実装してみたら、性能が思いのほか良くって驚いた。バカっぽい仕組みなようで、結構実用になるんじゃないかなぁ。単一マシンでのスケーラビリティやスループットを最大化させるのは実はこのディレクトリツリーデータベースなのかもしれない。でもそれを最強と認めるのはDBMの存在意義を否定することなので、今後はディレクトリツリーデータベースを倒すべく、ファイルツリーデータベースの改良を考えていきたいと思う。

Kyoto Cabinet-1.1.1に暗号化データベース機能を追加したという話。

背景

NTFSではファイルシステムの機能として特定のディレクトリを圧縮することができ、またその圧縮関数を暗号関数に置き換えることで、同じ枠組みで暗号化もサポートしている。ならば、圧縮をサポートしているKCでも、その圧縮関数を暗号関数に置き換えれば、圧縮データベースと同じ枠組みで暗号化データベースをサポートできるのではないか。つーことで、早速やってみた。

圧縮機能も暗号機能もユーザにとっては透過的に機能し、すなわちその機能を有効にするという以外はまったく同じ操作で生データベースも圧縮もしくは暗号化データベースも利用することができる。セキュリティに関わる機能を素人が実装するのは望ましいことではないが、カジュアルな用途では役に立つと思っている。とはいえ問題があれば指摘いただけると嬉しいので、ここに設計と実装を晒してみる。

枠組み

KCのファイルハッシュデータベース（HashDB）とファイルツリーデータベース（TreeDB）とディレクトリデータベース（DirDB）のいずれもが、tune_optionsというメソッドを持っており、それを用いてTCOMPRESSというフラグを立てると圧縮機能が有効になる。デフォルトではZlibの圧縮関数が呼ばれて、各レコードの値の部分が圧縮されて保存されることになる。

どの圧縮関数が適当かはアクセスパターンやデータパターンに左右されるのでプラガブルになっていることが望ましい。よって、従来から、tune_compressorというメソッドがサポートされていて、それに圧縮および伸長の関数を登録することで、ユーザがお好みの圧縮アルゴリズムを選択できるようになっている。ここに暗号および復号化の関数を登録すれば、既存の枠組みを一切変えることなく、暗号機能をサポートできる。

// 圧縮器の実装
class MyCompressor : kc::Compressor {
public:
  char* compress(const void* buf, size_t size, size_t* sp) { ... }
  char* decompress(const void* buf, size_t size, size_t* sp) { ... }
} mycompressor;

// データベースを圧縮モードで開く
kc::TreeDB db;
db.tune_options(kc::TreeDB::TCOMPRESS);
db.tune_compressor(mycompressor);
db.open(...);

暗号アルゴリズム

俺は暗号理論について全く詳しくないのだが、とりあえず実装が楽だし広く実用されているRC4（Arcfour）という暗号アルゴリズムを使うことにする。RC4は脆弱性を暴かれたWEPで使われているアルゴリズムなので脆弱だと思われがちだが、WEPの脆弱性はRC4の利用方法に問題があっただけで、RC4自体が解読可能になったわけではないらしい。今だったらおとなしくAESとか使うのがよさげな気もするが、そういう本気のユースケースでは既存のモジュールを使って上述のプラグインを実装することになるだろう。今回は、プラグインの一例としてのカジュアルな暗号機能を考え、できるだけ単純に実装できて簡単に利用できるものを目指す。

とりあえずはkcutil.hのユーティリティ関数群のひとつとして、arccipherという関数を追加してみた。ストリーム暗号は変換によってデータサイズが変わらないのと、暗号と復号が同じ関数でできるってのが楽でいいな。それはそれで問題なのだが、それは「利用モード」でカバーすべき話だろう。

/**
 * Cipher or decipher a serial object with the Arcfour stream cipher.
 * @param ptr the pointer to the region.
 * @param size the size of the region.
 * @param kbuf the pointer to the region of the cipher key.
 * @param ksiz the size of the region of the cipher key.
 * @param obuf the pointer to the region into which the result data is written.  The size of the
 * buffer should be equal to or more than the input region.  The region can be the same as the
 * source region.
 */
void arccipher(const void* ptr, size_t size, const void* kbuf, size_t ksiz, void* obuf);

ストリーム暗号では同じ鍵を2回使うことはできない。なぜなら、平文1と平文2をそれぞれ暗号化した暗号1と暗号2があるときに、暗号1と暗号2の各バイトのXORをとると、平文1と平文2のXORと同じバイト列が得られるからだ。平文のXORに文字の頻度分析とかすると元の文書のデータが結構予測できてしまうので、危険である。

std::string key = "1234";
std::string plain1 = "abcdefghij";
std::string plain2 = "0123456789";

unsigned char* cipher1 = new unsigned char[1024];
unsigned char* cipher2 = new unsigned char[1024];
kc::arccipher(plain1.data(), plain1.size(), key.data(), key.size(), cipher1);
kc::arccipher(plain2.data(), plain2.size(), key.data(), key.size(), cipher2);

// 平文1と平文2のXORがとれちゃう
for (size_t i = 0; i < plain1.size(); i++) {
  uint32_t x = cipher1[i] ^ cipher2[i];
  printf("%x: %c: %c\n", x, x ^ plain2[i], x ^ plain1[i]);
}

ということで、暗号関数を呼び出す毎に鍵を毎回変えなきゃならない。とはいえ毎回違う鍵の入力をユーザに求めるわけにはいかないので、ユーザから入力された鍵をちょっとずつ加工しながら使いまわすことにする。具体的には、直前に作った暗号のハッシュ値32ビットと、暗号関数が呼ばれた回数32ビットを連結したデータ（初期化ベクトル）を、ユーザが入力した鍵に接頭させたものを、個々のデータの暗号鍵にする。実際の実装は以下のようになる。

/**
 * Compressor with the Arcfour cipher.
 */
class ArcfourCompressor : public Compressor {
public:
  /**
   * Constructor.
   */
  ArcfourCompressor() : kbuf_(NULL), ksiz_(0), salt_(0), cycle_(false) {
    _assert_(true);
    kbuf_ = new char[0];
    ksiz_ = 0;
  }
  /**
   * Destructor.
   */
  ~ArcfourCompressor() {
    _assert_(true);
    delete[] kbuf_;
  }
  /**
   * Set the cipher key.
   * @param kbuf the pointer to the region of the cipher key.
   * @param ksiz the size of the region of the cipher key.
   */
  void set_key(const void* kbuf, size_t ksiz) {
    _assert_(kbuf && ksiz <= MEMMAXSIZ);
    delete[] kbuf_;
    if (ksiz > NUMBUFSIZ) ksiz = NUMBUFSIZ;
    kbuf_ = new char[ksiz];
    std::memcpy(kbuf_, kbuf, ksiz);
    ksiz_ = ksiz;
  }
  /**
   * Begin the cycle of ciper salt.
   * @param salt the additional cipher salt.
   */
  void begin_cycle(int64_t salt = 0) {
    salt_ = salt;
    cycle_ = true;
  }
private:
  /**
   * Compress a serial data.
   */
  char* compress(const void* buf, size_t size, size_t* sp) {
    _assert_(buf && size <= MEMMAXSIZ && sp);
    uint64_t salt = cycle_ ? salt_.add(1) : 0;
    char kbuf[NUMBUFSIZ*2];
    writefixnum(kbuf, salt, sizeof(salt));
    std::memcpy(kbuf + sizeof(salt), kbuf_, ksiz_);
    char* zbuf = new char[NUMBUFSIZ+size];
    char* wp = zbuf;
    writefixnum(wp, salt, sizeof(salt));
    wp += sizeof(salt);
    arccipher(buf, size, kbuf, sizeof(salt) + ksiz_, wp);
    if (cycle_) {
      size_t range = size < sizeof(uint64_t) ? size : sizeof(uint64_t);
      salt_.add(hashmurmur(wp, range) << 32);
    }
    *sp = sizeof(salt) + size;
    return zbuf;
  }
  /**
   * Decompress a serial data.
   */
  char* decompress(const void* buf, size_t size, size_t* sp) {
    _assert_(buf && size <= MEMMAXSIZ && sp);
    if (size < sizeof(uint64_t)) return NULL;
    char kbuf[NUMBUFSIZ*2];
    std::memcpy(kbuf, buf, sizeof(uint64_t));
    std::memcpy(kbuf + sizeof(uint64_t), kbuf_, ksiz_);
    buf = (char*)buf + sizeof(uint64_t);
    size -= sizeof(uint64_t);
    char* zbuf = new char[size];
    arccipher(buf, size, kbuf, sizeof(uint64_t) + ksiz_, zbuf);
    *sp = size;
    return zbuf;
  }
  /** The pointer to the key. */
  char* kbuf_;
  /** The size of the key. */
  size_t ksiz_;
  /** The cipher salt. */
  AtomicInt64 salt_;
  /** The flag of the salt cycle */
  bool cycle_;
};

使い方は簡単で、set_key メソッドででユーザ入力の鍵を登録して、鍵の攪拌を始めたいタイミングで begin_cycle を呼べばよい。その際に64ビットのユニークなsaltを指定することが重要である。どうやってユニークにするかはアプリ側の責任だが、カジュアルにはミリ秒の時間とかでもいいかなーと（多分怒られる）。実際にはmacアドレスとinodeとタイムスタンプを組み合わせるとかするのかもしれない。

// RC4圧縮器（暗号器）を作る
kc::ArcfourCompressor comp;
comp.set_key("foobarbaz", 9);

// データベースを圧縮モードで開く
kc::TreeDB db;
db.tune_options(kc::TreeDB::TCOMPRESS);
db.tune_compressor(&comp);

// 鍵の攪拌を開始する
comp.begin_cycle(kc::time() * 1000);

もっとカジュアルに

上記のようないかにも裏方の知識を要するプログラミングをしたいユーザは少ないだろう。特にスクリプト言語バインディングからはC/C++のプログラミングなしで呼べるようにしないと使えない。ということで、多相データベース（PolyDB）の命名規則を拡張して、圧縮関数と暗号鍵を指定できるようにしてみた。

kc::PolyDB db;
db.open("casket.kct#zcomp=arc#zkey=foobarbaz");

うおおお。簡単！　たったこれだけで暗号化データベースが作れちゃう。鍵の管理はアプリケーションの責任になるが、中の暗号アルゴリズムがどうなっているかとかいうことを気にせずに気軽に暗号化ができるというのは嬉しいことだ。もちろんスクリプト言語バインディングからも同じように使える（KCを最新版にする必要はあるが）。

ただし、ファイルハッシュデータベースとディレクトリデータベースの圧縮関数はレコードの値部分にしか適用されないので、暗号関数を使った場合も同様で、キーは平文のままになることに注意すべきだ。ファイルツリーデータベースはページ単位で圧縮を行うので、キーも暗号化される。なので、キーの存在を知られたくない場合（大抵のユースケースではそうだと思うが）は、ファイルツリーデータベースを使うべきである。多相データベース経由の場合は、拡張子「.kct」かオプション「#type=kct」をつける。

あと、暗号関数自体をDB内に記憶することはできないので、暗号関数はDBを開く度に必ず指定する必要がある。DB内部には一定のデータに暗号関数をかけた時のチェックサムだけが保存されているので、指定する暗号関数が一貫していなかったりパスワードが間違っていたりした場合にはエラーを検出してopenに失敗するようになっている。

性能

100万レコードの読み書きにかかる時間とファイルサイズを平文データベースと暗号化データベースで比較してみた。

	set	get	remove	size
HashDB (平文)	0.786	0.784	0.693	38297720
HashDB (暗号)	4.456	4.306	4.240	46297720
TreeDB (平文)	0.713	0.801	0.741	19931904
TreeDB (暗号)	0.736	0.864	0.756	19931904

ファイルハッシュDBにおいては、暗号化による時間と空間のペナルティがかなり大きいことがわかる。時間効率が悪化する原因は、暗号化処理もしくは復号処理とそれに伴う初期化ベクトルの生成処理をレコード数と同じ頻度で行うことである。空間効率が悪化する原因は、各レコードにひもづけて初期化ベクトルを保存しなきゃならないからである。

一方で、ファイルツリーDBにおいては、時間も空間もほとんど変わらない。暗号化処理や復号処理はページ単位でしか行わず、ページ数はレコード数に比べるとかなり少ないので、結果的にオーバーヘッドが非常に小さくなるのだ。サイズが全く同じなのは、ページ毎に付加される初期化ベクトルがページ毎のアラインメントによるパディング領域に収まるからである。

まとめ

DBMにちょっと秘密のデータを格納したい時、KCの暗号化データベース機能を使うと便利である。暗号強度がどれほどのものなのかはよくわからないので、現状では実験的な位置づけにすぎないけども、今まで平文で保存していたブログのパスワードとかをこっちに載せ替えるのとかには役立つと思う。特にファイルツリーDBでは性能が全くと言っていいほど劣化しないので、本当に気軽に暗号化を施すことができる。

俺はWindowsをほとんど使わないのだが、KCのWindowsサポートを続けるためにはWindows環境が必要なので、新しいマシンを買った。それでいろいろ設定したので今後のためにメモを残しておく。

旧マシン

Thinkpad T60を使っていた。画面解像度がSXGA+の最後のマシンである。最近のマシンはワイドとか言って横解像度ばかり高くなって、縦解像度をおろそかにする傾向にあるわけで、SXGA+（1440x1050）という縦1000越えのもので持ち運べるものはもうほとんどないではないか。T60もかなりでかいけど、今だとFull HD（1900x1080）とかいうようなマシンじゃないと縦1000越えは得られない。そんなのでかすぎるよ。ということで俺はT60が好きだった。プログラマに必要なのは縦解像度なのだ。

ただ、デュアルブートでたまに起動していたWindows XPがもうめちゃくちゃ壊れてきていて、3回に1回くらいしかまともに起動しない。でもってすぐ固まる。この状態ではとても開発などできるものではなかった。さらに無線LANがハードウェア的に壊れたのかWindows側からもLinux側からも認識されなくなっていて、悲しいけれどもう引退勧告をせざるを得なかった。今までありがとうT60。名機だったよ。

新マシン

ThinkpadのX201sを買った。秋葉原の某ショップで134780円で売られていて、Lenovo直販サイトの20万〜オプションという価格に比べるとすこぶる安かったので、即決。解像度はWXGA+（1440x900）と縦が短いが、横幅30cm以下のマシンではこれが一番マシ。CPUはCore i7の2GHz。メモリはデフォルト2GBなので増設して4GBにした（500円）。無線LANはもちろん、bluetoothやWiMAXもデフォルトでついてきて結構お得。そして、キーボードがフルサイズでかなり打ちやすいのもよい。

Windows側の設定

デフォルトでWindows 7（32ビット）が入っているので、それを64ビットに変えたい気もするが、とりあえず今は放っておく。電源入れて、無線LANの設定して、Windows Updateを2回ほどかければ、とりあえず使える状態にはなる（この時点で初心者に優しくはないと思うが）。あとはregeditでCaps LockをCtrlにするとかxyzzyを入れるとか外観をクラシックWindows風にするとか遊んで終了。

デュアルブートでLinuxを入れるために、デフォルトでWindowsのCドライブに全部割り当てられているパーティション構成をどげんかせんといかん。今までだとLinux立ち上げて全体のパーティションを切り直してから、リカバリメディアで先頭パーティションにWindowsを入れ直すという面倒をかけていた。しかしWindows 7（Vista）からは起動中のシステムドライブのパーティションも縮小できるというナイスな機能が搭載されているので、それで後半130GBをLinux用に開放することができた。残念ながらシステムファイルのある位置よりも小さくはできないらしく、150GB以上をWindows側に残してしまったが、まあ許容範囲だろう。

あと、Visual Studio Expressを入れて、各種環境設定をごにょごにょする必要がある。MinGWとかもいれなきゃな。

Linux側の設定

Ubuntu 10.04をインストール。Xシリーズは内蔵の光学メディアがないので、妻のX31の外付けDVDを借りてそこから起動して行った。で、swapを8GB、/をext4の16GB、/homeをext4の80GB、残りをテスト用にEXT3、EXT2、ReiserFS、XFS、JFSに割り当ててパーティションを設定。あとは指示どおりでOKOK押すだけ。

起動したら、synapticでg++やらvalgrindやらemacsやらを入れまくって、開発環境を整える。Python3やLua5.1やRuby1.9を入れるのも忘れずに。JDK1.6は手動で入れた。でもって.bashrcと.emacsと.sshを旧マシンからコピーしてきて、いちおう使える状態にはなった。

無線LAN

ここからが鬼門である。今までの作業は有線LANのネット接続で行っていたいたのだが、今回は是が非でも無線LAN接続を成功させねばならない。なぜならリビングで開発作業をすると妻と喧嘩になるからだ。俺の部屋で作業するにはLinux上で無線LANを使えるようにするのが絶対条件である。

結論としては、苦労した末に接続できた。Ubuntu 10.04のカーネル（2.6.32）にはX201sに積んであるCentrino Advanced-N 6200用のドライバが既に組み込まれている。lspciというコマンドを実行すると、「Network controller: Intel Corporation WiMAX/WiFi Link 6050 Series (rev 35)」と出力されるし、iwconfigというコマンドを実行すると「wlan0 ... IEEE 802.11abgn ... Tx-Power=15 dBm」などと表示されるので、どうやら認識はされているらしい。ただし、実際に使うにはファームウェアというファイルが別途必要らしく、それはデフォルトでは入らない。そしてそれはsynapticとかでも手に入らない。

いろいろ調べたあげく、iwlwifi-6050-4.ucodeというファイルを/lib/firmwareというディレクトリの下に置けばよいらしいということがわかった。しかし、iwlwifi-6050-4.ucodeがなかなか見つからない。結局、Intel Linux Wirelessなんたらというサイトのダウンロードページからiwlwifi-6050-ucode-9.201.4.1.tgzを取ってくればその中にあるということがわかった。でそれを所定の場所に置いて再起動したところ、デスクトップ上のネットワークマネージャにアクセスポイントの一覧が出てくるではないか。あとは普通にWPAのパスワードを入力するとつながる。ついにやったぜ！

けど、ちょっと不安定な気もするなあ。もしかしてもうちょい設定があるのかも。まあ今のところはいいや。急につながらなくなっちゃった時は、FnキーとF5を同時に押してデバイスのON/OFFをしてあげてからまたネットワークマネージャで接続するとよいらしい。

追記

無線LANカードが電力食いすぎたのか、筐体が異常に熱くなってしまった。で、いろいろ調べたところ、iwconfig wlan0 power on とかいうのを実行すると省電力モードになるようで、とりあえずはそれでしのぐ。rc.localに書いておけばOK。あと、WPA/WPA2+AESという方式だとなんだか不安定なので、WPA/WPA2+TKIPという設定にした。それでもたまに切れるけどまあいいや。

さらに、EXT4は不安定な気がする。というのも、KC-Javaのmake checkをEXT4上でやるとほぼ確実にOSごとハングアップしてしまうからだ。EXT3やEXT2上ではそのような問題は起きないし、そもそもアプリケーションの責任でOSが固まるということはありえないので、おそらくファイルシステムのバグだ。ということで、/や/homeなどの実用的なパーティションでEXT4を使うのはまだ時期尚早かも。EXT3でインストールしなおした。

おまけ

synapticでIPAフォントを入れるとFirefoxでなぜかビットマップフォントが表示されて汚くなるので、その場合はホームディレクトリにこの.fonts.confファイルを置くと直る。

性能

旧マシンのCPU（Core 2 Duo）も新マシンのCPU（Core i7）もクロック数はともに2GHzなので、シングルスレッドでの性能は両者同じくらいなのかなと思いきや、新マシンの方がかなり早かった。KCのビルド時間が、旧マシンだと134秒くらいで、新マシンだと81秒くらいだ。make -j4で4並列ビルドしてみると、旧マシンは75秒くらいで、新マシンは45秒くらいであった。旧マシンは2コア扱いで新マシンは4コア扱いなのだが、こちらは期待したほどCore i7が早いってわけではなかった。まあでもかなり早くなっているのは間違いない。

なお、KCの最新バージョンでは、make gchとやるとプリコンパイルヘッダを作るようになっているので、KC自体の開発をする際には、今いじっていないヘッダのプリコンパイルヘッダを作っておくとビルド時間がかなり短縮できる。-O0で最適化を抑止してさらにプリコンパイルヘッダを作っておくと、新マシンならKCの並列ビルドは13秒で終わる。これならストレスなく開発できるネ！

追記

KCの実行速度を旧マシンと新マシンで比較してみたところ、新マシンの方が圧倒的に早いという結果が出た。双方ともEXT2上で100万レコードの読み書きを実行した。

	T60	X201s
HashDB,1スレッド,set	1.82	0.74
HashDB,1スレッド,get	1.54	0.74
HashDB,4スレッド,set	2.15	0.65
HashDB,4スレッド,get	1.49	0.47
TreeDB,1スレッド,set	1.91	0.76
TreeDB,1スレッド,get	2.06	0.92
TreeDB,4スレッド,set	1.90	0.74
TreeDB,4スレッド,get	1.36	0.66

どのテストも2倍から3倍くらい新マシンの方が高速である。ここで特筆すべきは、2コア相当のCore 2 Duo程度のCPUだとスレッド数を増やしても高速化しないばかりか、かえって遅くなることもあるKCだが、4コア相当のCore i7とかになるとスレッドを増やした恩恵が受けられるようになるということだ。期待通りの挙動でよかった。8コア、16コアになってくるとやっとTCでなくKCの時代が来ると思う。

まとめ

やっぱりThinkpadは良いですよ。Lenovoになってからどうかなーって気もしていたけども、やっぱりノートPCの中では一番いい。マウスもトラックパッドもホームポジションから手が離れちゃうでしょ。プログラマならトラックポイント使うでしょ。Thinkpadの中でも、省スペース＆高性能というXシリーズと、そこそこ高性能というTシリーズはが俺は好きだ。これでLinuxで無線が使えれば最高だなと思っていたが、ついに念願かなったよ。

今日は猛暑だったが、うだうだマシンいじっててあっという間に一日が終わってしまった。ニート道を爆進中である。明日からは本気出す！