Inside Tokyo Cabinet その弐 - mixi engineer blog

予定を立てた途端にやりたくなくなる症候群に堪えて連載を続けるmikioです（こんな私でもエアーマンくらいは倒せます）。前回はDBMの基本について説明しましたが、それを忠実に実装しても実際には使いものにはならないことにも触れました。今回は、実用的なDBMに進化すべく、Tokyo Cabinet（およびその前身のQDBM）で考えた工夫についてお話します。

ハッシュ関数についてもう少し

前回の記事に関して、「ハッシュ関数はビットシフト使って実装した方が早いよ」という旨のお便りをいただきました（ありがとうございます）。まさにその通りで、乗算命令（ここではimull）より左シフト命令（ここではsall）の方が速いみたいです（Intelの資料によると、mulが15から18で、salが4とのこと）。しかし、DBMの場合はファイルI/Oにかかる時間が支配的になるというのが重要な点です。したがって、ハッシュ関数そのものの実行時間を削る努力よりも、衝突率を下げてI/Oを減らす努力の方が重要なので、敢えてビットシフトを使わないという選択をした次第です。もちろん、その前提として、ビットシフトを使う（すなわち2の冪で乗算する）場合と31や37で乗算する場合でどちらが効率がよいかを実験する必要がありますね。ということで、その結果をご紹介します。まず、最速のDBMとして知られるCDBから借用して、TCのハッシュ関数を以下のように変更してみました。

static uint64_t tchdbbidx(TCHDB *hdb, const char *kbuf, int ksiz){ 
  uint64_t hash = 5381; 
  while(ksiz--){ 
    hash = ((hash << 5) + hash) ^ *(uint8_t *)kbuf++; 
  } 
  return hash % hdb->bnum; 
}

ついでにMD5の上位バイトを使ったハッシュ関数も比較対象に加えて、衝突率を調べてみました。

バケット数	TC(mul 31)	TC(mul 37)	CDB(sal 5)	MD5
524287	687903	684950	922530	792014
1048573	584752	326856	498956	431781
2097143	149083	186656	188474	226561
3145721	196271	149690	128975	153818
4194301	82535	89437	87075	116031
5242877	13518	50740	62703	93957
6291449	276680	26870	56007	78356
7340009	16440	18785	46407	67073
8388593	4480	48000	53502	58430

衝突率に関してはmul 37がおそらく優位（あくまで入力データ依存ですが）なような気がしたところで、実際に組み込んだ際の実行時間はどうでしょうか。1000万レコードのDBを作る処理では、mul 37では全体で31.472秒で、sal 5では全体で34.034秒でした。mul 37の勝利ですね。gprofコマンドでコールグラフプロファイルを見てみると、mul 37のハッシュ関数は1000万回で0.97秒、sal 5は0.76秒にすぎないことがわかりました。ここからも、いかにI/Oの時間が支配的なのか予想できますね。なお、mul 37のままでもハッシュ値の型をint32_tにすると0.61秒まで削れるのですが、そういった手工芸的な最適化についてはTCがstableになった段階で改めて考えることにします。

DBMに対する操作

一般的にDBMはライブラリとして提供され、APIを介してアプリケーションプログラムから利用されることになります。そして、アプリケーションに公開される主な操作は「キーと値からなるレコードを格納する」「キーに対応するレコードを削除する」「キーに対応するレコードの値を取り出す」の3つです。TCではそれぞれ「put」「out」「get」という関数になっています。イメージしやすいように、まずはそれらをJava風の疑似コードとして表現してみましょう。

class DBM { 
  boolean put(String key, String value); 
  boolean out(String key); 
  String get(String key); 
  ... 
}

putは、キーと値を受け取って、そのレコードをデータベースに格納して、その成否を返します。outは、キーを受け取って、そのレコードをデータベースから消して、その成否を返します。getは、キーを受け取って、そのレコードをデータベースから探して、値を返します。上記の3つは必須の機能と言っていいでしょう（CDBのように一度作ったら更新不可能なDBMもありますが）。そうそう、お約束の、openとcloseも忘れちゃいけませんね。アプリケーションのサンプルコードはこんな感じになります。

DBM db = new DBM(); 
db.open("myfile.db", ...); 
db.put("1", "one"); 
db.put("2", "two"); 
db.put("3", "three"); 
db.put("4", "for"); // boo-boo 
db.out("4"); 
db.put("4", "four"); 
System.out.println("spelling of 4: " + db.get("4")); 
db.close();

次に欲しくなるのは、「データベースに入れたキーの一覧」を参照する機能です。そうしないとデータベースに何が入っているかわかりませんからね。ただし、以下のようにリストを返すことは絶対にしません。

class DBM { 
  ... 
  List keys(); 
}

なぜなら、データベース内に1000万件のレコードが入っていたら1000万個の要素を一気にメモリ上に載せることになり、各種の資源を喰い尽くしてしまうからです。Perlなどで keys(%db) などとして同様のことをする人がたまにいますが、ワンライナー以外では自重してください。ということで、一気に取り出すのではなく、個々のキーを別個の関数呼び出しで取り出すことにします。このような機構を「イテレータ」と呼ぶこともあります。あるいはDBMの文脈では「データベースを横断的にアクセスしてキーを取り出していく」ことから、「トラバース」とか「トラバーサルアクセス」とか呼ぶこともあります。イテレータに対する操作は、「初期化する」と「次の要素を取り出す」の2つからなります。TCではそれらを「iterinit」および「iternext」と呼ぶことにします。

class DBM { 
  ... 
  bool iterinit(); 
  String iternext(); 
}

なお、このようにDBMオブジェクトにイテレータを内蔵する方式だと、複数のイテレータを同時に使うことができません。TCでは歴史的な理由および性能上の理由で内蔵イテレータ方式を採用しているのですが、上位のAPIでは「カーソル」というより高度な機能で複数のイテレータを実現できるようにする予定です。さて、イテレータを使ったサンプルコードはこんな感じになります。

db.iterinit(); 
String key; 
while((key = db.iternext()) != null){ 
  String value = db.get(key); 
  System.out.println(key + ": " + value); 
}

多くのDBMでは上記の関数群には詳細な挙動を指示するパラメータが付けられることも多いですし、String型でなく別の型を使うことも多いでしょう。しかし、だいたいの使いかたは同じだと思っていただいて大丈夫です。もしDBMを使ったことがない方は、まずはQDBMからでも使ってみてください。現状ではTCよりも解説が充実していますし、C++、Java、Perl、Rubyからも使えますし、UNIXでもWindowsでもMacでも使えますし、アメリカ航空宇宙局（NASA）でも使われています（マジです（その中の清掃事務所あたりかもしれないですが））。

セパレートチェーンの進化

長い前置きでしたが、ここからが本題です。TCの偉いところについてでしたね。さて、ハッシュテーブルの探索にかかる時間計算量 O(1) は、バケット数（バケット配列の要素数）がレコード数に匹敵するくらい多いことを前提としています。ここでちょっとした問題が起きます。バケット数はデータベースを作成する時に決定していなければならないのに、適切なバケット数を決定するために必要なレコード数は、必ずしもデータベース作成時にわかっているわけではないということです。とりあえず多めに取っておくというのも悪くないアイデアですが、バケット配列もまたファイル上に領域をとるし、読み出せばメモリを食うことになるので、際限なく増やすわけにはいきません。

バケット数が十分に取れない場合、前回述べたような単純な線形リストによる衝突管理手法だと、探索にかかる時間計算量は O(n) になります。すなわちレコード数に比例する、激遅の世界です。それではいかんということで、TCでは衝突したレコード群を二分探索木で組織化しています。図のように、個々のレコードにぶら下げる子供を左右の2方向に分けて、キーが大きいものを左、小さいものを右のチェーンに繋ぐようにします。探索時にチェーンを辿る際には入れたときと同じ方法で左右を判定すれば、迷うことはありません。

左右が理想的に分かれた場合、1段で1個、2段で1+2=3個、3段で1+2+4=7個、4段で1+2+4+8=15個、5段で1+2+4+8+16=31個、6段で1+2+4+8+16+32=63個...のレコードが管理できることになります。つまり各バケットの平均衝突数をcとした場合に、log₂(c+1) 回だけチェーンを辿れば探索が終了するということです。これを時間計算量で表すと O(log n) となります。バケット数10のデータベースに1000万レコードを入れたとしても20回くらいチェーンを辿れば探索が終了するのですから、これは O(n) である線形リストの100万回に比べると大した進歩ではないでしょうか。

2分探索木の欠点は、キーの入れかたが偏った場合に実質的に線形リストと同じ計算量になってしまうということです。例えば小さいキーから始めて段々と大きいキーを格納していった場合、図のように左の子だけが連なってどんどんチェーンが伸びていってしまいます。

これを避けるために、TCでは、キーに第2のハッシュ関数を適用して、その大小でチェーンの左右の分岐を判定しています（ハッシュ値が同じ場合はキーの辞書順で判定します）。第1のハッシュ関数と第2のハッシュ関数が相関しないようにしておけば、確率的にはほぼ均等に左右がばらけることが期待できます。さらに副作用として、このハッシュ値を各レコードのヘッダとして保存するようにすれば、ヘッダだけ読み出してキーを読み出さなくても左右の分岐を決められるので、I/Oの量が節約できます。

データベースに既に格納してあるレコードを削除する場合、レコードのエントリを修正することになります。ここで言う「エントリ」とは、そのレコードを探索した時に直前に使ったチェーンの「繋ぎ元」のことです、すなわち、バケット配列直下だった場合はバケット配列の要素で、左の子だった場合は親の左チェーンで、右の子だった場合は親の右チェーンになります。また、エントリを修正する際には、二分探索木から要素を削除する手順を守らなければなりません。以下の場合分けをして考えるとわかりやすいでしょう。

そのレコードには子がない → エントリをクリア
そのレコードは左の子だけを持つ → 左の子の位置をエントリに書き込む
そのレコードは右の子だけを持つ → 右の子の位置をエントリに書き込む
左の子と右の子を持つ → 左の子の位置をエントリに書き込み、右の子を左の部分木の最も右の子にする

なお、左の子と右の子を両方持っている場合のセオリーは、「左の部分木の最小要素で自分を置き換える」ですが、木の形をバランスさせることに努めるよりも、簡便法でI/Oの回数を減らす方が得策との考えから、上記の手順にしています。

フリーブロックプール

削除したレコードの領域は空き領域として残ることになりますが、データベースの更新を繰り返していくほどにその空き領域は増えていくことになり、そのままでは性能がどんどん劣化していくともに、ファイルが肥大化していずれはディスクを喰い尽くすことになってしまうでしょう。そのために、空き領域を再利用する仕組みが必要になります。データベースを更新していく際のファイルの様子を例を見ながら考えてみましょう。まず、「831546」というキーに対応する「mikio」という値を格納するとします。このレコードを直列化したデータを [831546:mikio] と表現することにして、そのようなレコードのデータが以下のように並べられてファイルに格納されていたとします。

[135:cat][12534:dog][888:lion][1943:tiger]

ここで、「563」の値を「dog」から「wolf」に変更する前後のデータフォーマットを考えてみましょう。

前　[135:cat][12534:dog][888:lion][1943:tiger] 
後　[135:cat][12534:wolf][888:lion][1943:tiger]

お気付きのように、[12534:dog] の長さが1バイト増えるために [888:lion] 以降のデータを全て後ろにずらさなければなりません。しかし、「ずらす」という処理は一撃ではできずに、「読み込んで」「書き出す」という処理を対象の全データに対して行う必要があります。その計算量はデータベースのサイズに比例するので、巨大なデータベースでは大変なことになってしまいます。例えば、10GBのデータベースなら、更新のたびに平均5GB読み込んで、平均5GB書き出さなければならないことになるのです。これは現実的ではありませんね。そこで、[12534:dog] のレコードがあった領域は「フリーブロック」として扱い、新しいレコードをファイルの末尾に書き込むことにします。

前　[135:cat][12534:dog][888:lion][1943:tiger] 
後　[135:cat]-----------[888:lion][1943:tiger][12534:wolf]

さらに [1943:tiger] が [1943:penguin] に更新された場合にはこうなります。

前　[135:cat]-----------[888:lion][1943:tiger][12534:wolf] 
後　[135:cat]-----------[888:lion]------------[12534:wolf][1943:penguin]

このように、更新を続けていくとフリーブロックがどんどん増加していき、データベースが肥大化していきます。そこで、フリーブロックを再利用することでそれを防ぐことにします。例えば [123:ape] というレコードを登録する場合には、[12534:dog] の跡地に入れればよいでしょう。

前　[135:cat]-----------[888:lion]------------[12534:wolf][1943:penguin] 
後　[135:cat][123:ape]--[888:lion]------------[12534:wolf][1943:penguin]

また、直後がフリーブロックであるレコードはそれを利用してその位置のまま長さを増やすことができます。例えば [888:lion] が [888:lionelrichie] に更新された場合には以下のようになります。

前　[135:cat][123:ape]--[888:lion]------------[12534:wolf][1943:penguin] 
後　[135:cat][123:ape]--[888:lionelrichie]----[12534:wolf][1943:penguin]

再利用を進めていくと今度はフリーブロックが細かく分けられすぎて再利用できなくなる「フラグメンテーション」という問題が発生するのですが、レコードを前から詰めていく「デフラグ」という処理を行うことでそれには対処できます。ただし、デフラグの計算量はデータベースのサイズに比例するので頻繁には行えません。したがって、できるだけフラグメンテーションによる肥大化を抑制するようにフリーブロックを管理することが求められます。フリーブロックのリストを管理してレコードの更新時に適切なものを割り当てる機能を「フリーブロックプール」と呼ぶことにしますが、その実装については改めて述べます。今は、フリーブロックを再利用する機構が重要であるということだけ押さえておいてください。

TCのデータフォーマット

それでは、いよいよTCのデータフォーマットについて説明します。といってもそれほど複雑なものではなく、前回説明した単純なものに、二分探索木のチェーンやフリーブロックプールを実現するための領域を追加しただけです。

まず、ファイル全体は、ヘッダ部、バケット部、フリーブロックプール部、レコード部の4つに大別されます。ヘッダ部はファイルの先頭から128バイトの固定長でとられ、バケット数やレコード数などのメタデータが記録されます。バケット部は、ハッシュ値に対応する最初のレコードの位置を要素とした配列を記録する領域です。フリーブロックプール部は、フリーブロックの位置と長さのペアを要素とした配列を記録する領域です。

残りがレコード部で、各レコードの以下の情報を持つ要素が記録されます。

マジックナンバ : データの識別と整合性確認に用いる。0xA1固定
ハッシュ値 : チェーンの進路決定に用いるハッシュ値
左チェーン : 左チェーン接続先の位置
右チェーン : 右チェーン接続先の位置
パディングサイズ : パディングのサイズ
キーサイズ : キーのサイズ
値サイズ : 値のサイズ
キー : キーのデータ
値 : 値のデータ
パディング : 隣のレコードまでの埋め合わせ

ただし、フリーブロックとなった領域には、各レコードの以下の情報を持つ要素が記録されます。

マジックナンバ : データの識別と整合性確認に用いる。0xA2固定
ブロックサイズ : そのブロックのサイズ

ところで、パディングとかフリーブロックはレコードの探索などの処理では一切アクセスされない領域なのですが、なぜわざわざそれらを書き込んでいるのでしょうか。それは、トラバーサルアクセスのためです。トラバーサルアクセスの際にはパディングやフリーブロックは読み飛ばすことになるのですが、何バイト読み飛ばせばよいかを指示できないとその処理はできませんよね。

まとめ

DBMの操作は「格納」「削除」「取得」「イテレータ初期化」「イテレータ続行」で、TCではそれぞれ「put」「out」「get」「iterinit」「iternext」としてAPIを定義しました。そしてその操作を効率的に実現するための衝突管理やフリーブロックプールの仕組みについて考えた上で、それを反映したデータフォーマットを設計しました。DBMは単純なアルゴリズムとデータ構造の組み合わせではありますが、それらを適切に選択するには結構な試行錯誤がいる面白い分野です。この記事を読んで、自分もDBMを作っちゃろかなと思い立つ人が一人でもいれば幸いです。

上記のフォーマットでは、位置やサイズなどの数値データの型についての言及を敢えて省いています。しかし、実はデータベースの空間効率を考える上では数値データの扱いは非常に重要です。次回はそれらをいかに圧縮して保持するかについてお話しします。また、I/Oの回数を減らして高速化する技法をはじめ、今回詳細を省いた諸々について説明したいと思います。