予定を立てた途端にやりたくなくなる症候群に堪えて連載を続ける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の上位バイトを使ったハッシュ関数も比較対象に加えて、衝突率を調べてみました。

衝突率に関しては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の回数を減らして高速化する技法をはじめ、今回詳細を省いた諸々について説明したいと思います。

約半年間の沈黙を破ってOSSの世界に戻ってきつつあるmikioです。先日、Tokyo Cabinet（以下「TC」と呼びます）というデータベースライブラリをリリースしました。今回から数回に分けて、TCの設計と苦労話について連載してみます。

DBMとは

TCは、いわゆるDBMの系譜のデータベースライブラリで、単純なハッシュテーブルをファイル上で永続化するだけの機能を提供します。DBMはAT&Tの古代UNIXの時代から受け継がれる伝統芸能なのですが、私はそういう枯れた技術が大好きなのです。

プログラマの皆さんは、PerlやRubyではハッシュ（連想配列）と呼ばれ、JavaやC++ではmapと呼ばれるような、何らかのキーに関連づけてなんらかの値を記録するデータ構造って実によく使いますよね。例えばmixiでは、ユーザアカウントに関連する情報（名前とかニックネームとか）は、ユーザIDをキーにしたハッシュに格納されています。ものすごく単純化した例を示すとこんな感じですね。

my %nicknames;
$nicknames{"123456001"} = "batara";
$nicknames{"123456002"} = "mikio";
$nicknames{"123456003"} = "penguin";
...
printf("nickname of 123456001: %s\\n", $nicknames{"123456001"});
printf("nickname of 123456002: %s\\n", $nicknames{"123456002"});
printf("nickname of 123456003: %s\\n", $nicknames{"123456003"});

文字列だろうが数字だろうが、スカラとして表せるものは何でもハッシュに入れることができる（より複雑なデータ構造の場合にはスカラに直列化してから入れればOK）だけでなく、ハッシュ内のレコード数がどんなに多くなっても一瞬でレコードを格納したり取り出したりできるので、とにかくめっちゃ便利です。これに慣れると、ハッシュがない言語なんて全く使う気にならないくらいです。

しかしながら、普通のハッシュはメモリ上にデータを保持することを前提として実装されているので、プログラムが終了するとデータは消えてしまいますし、メモリ容量以上のデータをうまく扱うことができません。キーと値の対応関係を別のファイルに書き出しておいてから、毎回プログラムが起動する度にハッシュを再構築するという手法も考えられなくはないですが、取り扱うレコード数が数千を超えたくらいからそれでは遅くてやっていられなくなります。ましてやmixiのユーザアカウントのように1000万を越える場合はプログラムを起動するだけで何時間かかるかわかりませんし、1レコードのサイズが100バイトとしたら100*10000000で最低1GB（実際には数10GB）ものメモリを食うので泣きが入ってしまいます。

そこで、DBM（DataBase Manager）の登場です。メモリ上のハッシュの様な使い勝手と性能を持ちながら、データをファイルに書き込むことで、レコードを永続化し、実メモリを越える容量のデータを取り扱うことができます。

DBM自体は「key/value」ペアの格納と削除と探索を行う機能を提供するだけですが、より複雑なロジックを司るハーネスをかぶせることで様々なシステムに進化します。リレーショナルデータベースのストレージエンジンとしても、プライマリキーをキーにしてレコードの実データを値にしたDBM風の機能が使われています。あるいは、ファイル名（実際にはinode）をキーにしてメタデータや実データを値にすることで、ファイルシステムを実現することができます（DBM自体がファイルシステムに依存しているという矛盾はさておき）。さらに、検索語をキーにしてそれを含む文書のIDを値にすることで、全文検索エンジンのインデックスを実現することもできます。ソフトウェアの花形といわれるシステムの裏には常にDBM風の機能が隠れているといっても過言ではありません。

ハッシュテーブルの高速性

必ずしもDBMを使わなくっても、例えばCSVでもデータベースは実現できます。上記のサンプルコードのデータベースは以下のようなCSVファイルとして記録してもよいのです。

1234560001,batara
1234560002,mikio
1234560003,penguin

CSVファイルから特定のレコードを捜し出す際には、逐次探索を行います。すなわち、ファイルの先頭から末尾まで読み進めていって、キーとなるフィールドが完全一致するものを見つけた時点で対応する行の値を返すという処理を行います。したがって、該当のレコードがある場合は全レコードの平均半分を調べることになり、該当のレコードがない場合は全て調べることになります。つまり、探索にかかる計算量はレコードの数やデータベースのサイズに比例します。この状況を、レコード数をnとして「O(n)」と表します。「O」は「Order」で、「n」は「レコード数nに依拠する」という意味です。レコードを追加する場合や削除する場合の計算量も同じです。これでは遅すぎて、残念ながら1000万件規模では使いものになりません。

それに対して、DBMはハッシュテーブルを使って、データの探索や追加や削除を高速に行います。ハッシュテーブルの探索にかかる時間計算量は「O(1)」と表されます。「O」は「Order」で、「(1)」は「1に依拠する」、つまり「変化しない」あるいは「レコード数nとは関係ない」という意味です。これは凄いことですよね。レコード数が1件でも1000万件でも（1件あたりは）ほぼ同じ時間で処理ができるのですから、たとえmixiでも安心して使えるわけです。

ここまでは前置きで、ここからが本題です。では、なぜハッシュテーブルは高速なのでしょう。それは一言でいえば、「探索領域を限定するから」です。ここで、ハッシュテーブルの説明に至る前に、CSVの探索を高速化するワークアラウンドについて考えてみましょう。単一のCSVファイルに全てのレコードを保存するのではなく、「0.csv」「1.csv」「2.csv」…「9.csv」の10個に分けることにします。そして、キーの数値を10で割った余りでファイル名を特定して、そのファイルに格納します。

• 「1234560001,batara」 → 1234560001 % 10 == 1 → 「1.csv」
• 「1234560002,mikio」 → 1234560002 % 10 == 2 → 「2.csv」
• 「1234560003,penguin」 → 1234560003 % 10 == 3 → 「3.csv」

こうしてCSVファイルを作っておいた上で、「1234560002」に該当する値を探す場合は、格納する時と同じ計算を行って、「2.csv」を特定して、その中のレコードを探せばよいことになります。探索範囲を10分割しているのだから、探索する量も10分の1になり、すなわち探索が10倍高速化されることになります。ここですぐ気づくように、1000万件のレコードを格納しても、1000万個のファイルに分割して格納するようにすれば、実際に逐次探索する回数はほぼ1回になります。ハッシュテーブルとは、上記の手法を一般化したものです。格納するキーの数に匹敵するくらいの数に探索範囲を分割することで、逐次探索する回数を実質1回にするのです。DBMはハッシュテーブルを単一（もしくは少数）のファイルで実現する機能です。

ハッシュ関数

キーが数値でなくて英字などの文字列であったり、さらには任意のバイナリコードであっても大丈夫なように、それらに一定の計算をして、特定の範囲に収まる数値を生成する必要があります。このような数値を「ハッシュ値」と呼び、キーからハッシュ値を生成する関数を「ハッシュ関数」と呼びます。ハッシュ値が同一であるキーが複数ある状態を「衝突」と言いますが、この衝突ができるだけ少ないものがいいハッシュ関数だと言われています。

ハッシュ関数のソースコードをTCから抜き出してみます。kbufはキーの領域のポインタで、ksizはそのサイズで、hdb->bnumには通称「バケット数」＝「分割する数」が入っています。つまり、キーの各バイトを足していく過程で既存の値に37を掛けておくということです。

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

付与の変域の中で値をできるだけ均一にバラけさせるために、ものすごくたくさんの手法が提案されています。しかし、私がいろいろと試した限りでは、あんまり凝ったものはだいたいダメな感じで、上記くらいで十分です。37でなく31を掛けても結構いいですが、シーケンシャルな数値や英単語を扱う限りにおいては37の方が安定しているような気がしなくもないです。最後に余り算で使うことになるバケット数は素数がいいらしいとknuth先生は言っているそうで、TCでも素数を割り当てていますが、実際のところはどうでもいいみたいです（2の冪にしてビットマスクした方が高速でよいという噂もあります）。なお、751は私の高校受験の際の受験番号です（つまりこの値は本当にどうでもいいです）。

各バイトで掛ける数について、ちょっと参考になるかもしれない実験結果を紹介しましょう。「00000001」「00000002」「00000003」…「01000000」というような、シーケンシャルな数値を8桁で表したキー100万個の集合を対象に、上記のハッシュ関数の衝突数を調べてみました。

うーむ。決定的によいものはなさそうですね。結局のところ、入力パターンを規定した場合にさえ、どのようなハッシュ関数が最良かは言いきれないので、「えいや」で決めるしかなさそうです。空前の素数ブームなのでとりあえず素数。んでもって3と7は縁起がよさそうなので37。そして751（ry

単純なファイルフォーマット

ハッシュ値ごとにファイルを分けて保存するというのも悪くないアイデアですが、100万個とかのファイルを作るとなるとファイルシステムが大変なことになってしまいます。そこで、全レコードを単一のファイルに保存することにして、ハッシュ値に該当するレコードのファイル内の位置を記録した配列を管理することにします。これを「バケット配列」と呼ぶことにします。また、バケット数はバケット配列の要素数という意味になります。

さて、今から最も単純なDBMのフォーマットを設計していくことにします。まず、バケット配列をファイルの先頭に配置して、実際のレコードはその後ろに置くことにしましょう。例えばバケット数が1000個で、その各要素をint型（4バイト）の数値で表現するならば、ファイルの先頭4000バイトまではバケット配列を記録するのに使い、4001バイト目（オフセットで言えば4000バイト目）以降はレコードの本体を記録します。

次に各レコードのフォーマットを考えます。CSVファイルの場合はレコードの区切りを改行で表していましたが、DBMではキーや値に改行を含められることも考えて、区切り文字でなく、サイズを別に記録することで区切りを判定することにします。また、CSVでは同じハッシュ値の次のレコードは自明（同一ファイル内の次の行）でしたが、DBMでは全てのレコードが同一ファイルにあるので、「同一のハッシュ値を持つ次のレコードの位置」も記録することにします。以上をまとめると、各レコードには以下の領域が必要となるわけです。

• キーのサイズ：int型（4バイト）
• 値のサイズ：int型（4バイト）
• 次のレコードの位置：int型（4バイト）
• キーの実データ：任意のバイト列
• キーの値の実データ：任意のバイト列

ここで、いくつかレコードを格納した場合の模式図を見てみましょう。「1234560003,penguin」と「1234570003,devil」はハッシュ値がともに3で衝突しているので、後から入れた「1234570003,devil」が「1234560003,penguin」の後ろにぶら下がっていることに注意してください。なお、このような衝突の管理方法を「セパレートチェーン」などと呼ぶこともあります。

まとめ

上記でDBMの基本的な構造はおわかりいただけたと思います。ハッシュテーブルを使えば高速にデータを探索できますし、それをファイル上で扱うことで大規模かつ永続的な用途にも使えるようになります。

しかし、問題はここからなのです。以下のような問題を解決すべく、ここから改善改善改善の旅が始まります。

• バケット数が十分に確保できない場合にどうするか
• レコードを消すときにどうするか
• 既存のレコードの値を変更するにはどうするか
• 合計サイズがint型で表現できないくらい大きい場合にどうするか
• 各レコードのヘッダ部分をもっと圧縮できないか
• 探索や更新を並列で行うにはどうするか

DBMのような基本的な機能は、世界一できる奴が世界一効率の良い実装を公開してくれればそれが決定版になりそうなものですが、探してもなかなかないんですよね（ハッシュ関数と同じでそもそも最良なんてないというのがその理由なわけですけど）。そして、GDBMやBerkeley DBなどの優れた実装が既にあるなかで、それらのよいとこ取りをしてQDBMというデータベースマネージャを作りました。それでもまだ改良の余地があると感じたので、このたびTCを作った次第です。馬鹿の一つ覚えのようにDBMを作ってどうするのかと思われるかもしれませんが、根幹の部分で頑張っておけばそれより上の層で幸せになれることを、ここまで読んでくれた皆さんにはおわかりいただけていると思います。

この連載ではTCの仕様決定や技術選択の過程を晒していく予定なのですが、「そこもっとこうした方がいくね？」という点があれば私にこっそりご連絡いただけると大変嬉しい夏の日です。

新卒で入った会社ではキーボードを半年に一回壊していたnealです。今回はmixiのサービスとは関係ないですが、開発部のこだわりの入力デバイス、キーボードについてちょっと書いてみました。

開発部 では「マイキーボード」を持ち込む人が多く、コードを書くプロとしてそれぞれの思いがあります。魚屋さんで例えれば包丁でしょうか？包丁の切れ味が悪かったり、使いにくかったら仕事になりませんよね。それと同じで頭に浮かんだコードを文字列にするキーボードというデバイスは開発者にとって重要な道具です。

社内で一番の人気者はPFU社のHHK。マイキーボード使用者の中でも5割り近くがHHKです。心地よいクリック感と「A」の左横にコントロールがある配列、これだけでもコードを書く人間の心をワクワクさせてくれます。

究極のキーボード を追及すると必ずKINESISの名前が出てきます。タッチや配列だけではなく、独特な「Concave Key Wells」という形状が手首に優しいです。お財布には優しくないのが一番のネックなんですけど。

写真はLarry Wallのサイン付き。HHKユーザにもLarry Wall, Tatsuhiko Miyagawa, Dan Kogaiのサイン入りキーボード所有者がいますが、流行りなんでしょうか？

HHKやKINESISも欲しいけど、自分は旧IBMのトラックポイント付きを使っています。写真は最近入社した仲間のトラベルバージョン。ホームポジションから手を動かさずにポインタでカーソル移動が可能で、ターミナル間の移動やブラウザ/ターミナル間の移動にマウスを必要としません。この赤いポインタに慣れると普通のキーボードでは人差し指が寂しくなるのはトラックポイント中毒なのか？！

自分が大学を卒業し、仕事を始めた頃は、「キーボードなんて消耗品だよ」と思っていたのですが、それは大間違いでした。そもそも半年で壊れる安物を使っていた時点で問題でしたが、それなりのキーボードはしっかりメンテナンスをすればかなり長持ちする物です。そして、頭の中で次から次へと浮かんでくるコードを文字列へと伝える為には自分が愛着を持った道具を使うのがベストだと思っています。これは単に道具へのこだわりだけではなく、書いているコードにもこだわりや愛情が現れ、そこからユーザが喜んで使ってくれるサービスを生み出して行くと私は信じています。

*click click click*

今年も、来る9月5日にサマーインターンシップを開催することになりました。目的を簡単にいえば、弊社が持っているサービスやそれを支える技術について学生の皆さんに知ってもらって日頃の研究開発活動の一助にしてもらおうということと、興味を持っていただけたなら進路の選択肢のひとつとして弊社を考えていただきたいということです。私も講師を任されているので、宣伝がてら背景事情について語ってみます。

この時期になると各社こぞって「オフィス見学」「ラボツアー」「インターンシップ」といった催しをして学生の皆さんと接触していくみたいですが、学校を出て久しい私の感覚だと、「卒業年度の前年度（学部なら3年、修士過程なら1年）の8月に就活とかって早くね？」と思うところです。そこで人事の人に聞いたわけですが、「優秀な人の多数が早く就職活動を始める傾向にあり、彼らにアピールしたいなら時期を逸してはいけない」とのこと。なるほど確かに、弊社で能力を振るったとしたら大ブレークするサービスを作れたかもしれない人に出会ったとしても、既に他社に決まっているのではもったいないですよね。

ところで、「優秀な」という言葉を気軽に使ってしまいましたが、何をもって優秀とするのでしょうか。学校の成績が良いこと、教養と常識が広く深いこと、知能と学習能力が高いこと、根気があってストレス耐性が高いことなど、いろいろパラメータがあると思います。あるいはもっと実践的に、ソフトウェアの開発経験があるとか、プログラミング言語を使いこなしているとか、アルゴリズムをよく知っているとか、英語の読み書きができるとかいった評価もできると思います。もちろん、そういう意味で優秀な方は素晴らしいしwelcomeなわけですが、しかし、もっと重要なことがあります。それは、「楽しく働けること」です。

楽しく働くといっても漠然としていますが、それはすなわち、やりたい仕事に打ち込めることだと思います。もし嫌々仕事をやったとしても成果はでにくいし、無理矢理やってもミスばかりして効率が悪いだろうし、周囲の人間ともうまくいかなくなって続かないでしょう。一方楽しく仕事ができれば、次々とアイデアがでてくるし、それを次々と実践して成果を上げることができるし、その繰り返しの中で成長してさらにいい仕事をして、さらに仕事が楽しくなっていくことでしょう。さて、そのために必要となることをざっと挙げてみると以下のような感じでしょうか。

• 実現性：自分がやりたい仕事がその会社で実現できる
• 成長性：やりたい仕事に向かって自分を高めていける
• 需要：その仕事が必要とされ、やれば評価してもらえる
• 環境：上司や同僚が自分やその仕事を理解し、共感し、支援してくれる
• 興味：そもそもその仕事をやること自体が自分の性に合っていて楽しい

他にも様々な観点があるでしょうが、少なくとも私が勤め先を探すにあたっては上記を満たすことを重視しました。ここで強調したいのは、上記のような条件への適合は、私が優秀か凡庸かということではなく、私という人物にその会社が合っているかどうか、あるいは逆にその会社に私という人物が合っているかどうかで決まるということです。簡単にいえば相性の問題なわけですけど、それってホームページの企業概要を読んでも判断できませんよね？ やはり実際に働いている人に話を聞いたり、欲をいえば仕事をいっしょに経験してみて初めてわかることです。

ということでサマーインターンシップ。一緒に仕事をするとまではいきませんが、できるだけ現場の雰囲気がわかるような機会になればいいなと思っています。弊社のサービスの現状と課題や、サービスを支える技術の解説はもちろん、現場の人達のワークスタイルや人柄のようなものが伝わるように、現在内容を精査しているところです。技術的なトピックとしては、DBの分散や検索系のアーキテクチャやアプリケーションフレームワークについて取り上げる予定です。乞うご期待！

ちなみに、仕事の話ばかりしましたけど、プライベートも大事ですよ。弊社開発部の平均年齢は26か27前後ですけど、意外にも既婚者&&(愛妻家||愛夫家)が多いです。

お久しぶりです、初めての日本の夏に圧倒されているトールマエサカです。

今日はLinuxにおけるネットワークプログラミング関連のネタです。分散データベースサーバの開発過程で最近よくLinuxのepollというイベントハンドリング機能を使っています。これがまた優秀な機能なので紹介します。

このContextでいうイベントハンドラーはサーバがクライエントのリクエストを処理するためのメカニズムです。イベントの感知と通知は大雑把にいうと以下の三つの処理で構成されています：

• 一つもしくは複数のディスクリプタを監視
• ディスクリプタの準備が整うまでハチ公のごとくひたすら待ち続ける
• 準備が整ったディスクリプタの通知

アプリケーションでの実装は一昔までselect(2)、もしくはpoll(2)というシステムコールで行われていました。二つとも役目は同じですがselect(2)の場合、kernelをいじらない限りディスクリプタセットのサイズは一定という制限があります。対してpoll(2)の場合、ディスクリプタを纏める配列のサイズはプログラマが設定するため、このような制限はないといわれています。

両方ともアプリケーションに呼ばれる度に監視下のディスクリプタセットをkernelに渡し、kernelは渡されたリストに対しstateを更新し送り返します。送り返されたディスクリプタ達からready状態のディスクリプタをピックアップするためにアプリケーションはディスクリプタ達を一つ一つ調べます。つまりディスクリプタの数が多くなればなるほど性能が劣化するという事ですね。

epollの違い

すでにkernelが知っている情報をアプリケーションで再計算する従来の手法に対しLinux Kernel 2.6から追加されたepollではディスクリプタのstateがkernel内で管理されます。select(2)やpoll(2)の様に呼ばれる度にディスクリプタセットをkernelに送る必要もありませんし無駄にディスクリプタセットをループする必要がなくなります。又、edge-triggeredインターフェイスとしても使えるため、kernelの負担を多少下げることも可能。パフォーマンスの方はselect(2)とpoll(2)のtime complexityがO(n)に対しepollはO(1)と無視のできない性能の差を実現しています。

性能のベンチマーク結果は様々なサイトで報告されていますが、libeventのチャートを見ると凄さが解っていただけると思います。epollは正義の味方のmemcachedの中でもlibevent経由で使われています。サンプルコードや詳しい内容はmanに書かれているので是非お時間のある時に読んでみてください。読んだ事がなければワクワクさせてくれる内容です。

epollのもう一つ素晴らしいところは使い方がとても簡単という事です。基本的な使い方をここで紹介しますが、ハードコアな見本はuserverという複数のイベントハンドラーが扱える小型のウェブサーバーやlibeventのソースコードがお勧めです。又、検索してみたらodz bufferさんによる簡潔な例があったのでこれも参考になるかと思います。

Linux以外の場合

epollのメカニズム自体はLinuxの特権ではなく、例えばBSDにはkqueueというメカニズムがあります。自分はあまり詳しくないのでここは触れないでおきますが、この分野に興味のある方はDan Kegel氏のThe C10K Problemを読むと楽しいですよ（お決まりのレコメンドですみません、、）。Solarisの /dev/poll の話も含まれています。

使い方

さて使い方ですが、epoll_create(2), epoll_ctl(2), epoll_wait(2)を使って扱います。基本的にステップは三つあります。

epollのディスクリプタを作る。

int epfd;
if((epfd = epoll_create(MAX_EVENTS)) < 0) {
    fprintf(stderr, "epoll_create()\\n");
    exit(1);
}

作成したディスクリプタをepollに追加。

struct epoll_event event;
int sock;

/* get_socket()系は自前で実装が必要 */
if((sock = get_socket()) < 0) {
    fprintf(stderr, "get_socket()\\n");
    exit(1);
} 

memset(&event, 0, sizeof(event));
ev.events  = EPOLLIN | EPOLLET; /* "man epoll" から拝借 */
ev.data.fd = sock;

/* ソケットをepollに追加 */
if (epoll_ctl(epfd, EPOLL_CTL_ADD, sock, &event) < 0) {
    fprintf(stderr, "epoll_ctl()\\n");
    exit(1);
}

後は待ち続ける。出番がきたらそれ相応の処理を行う。

int nfd, i;
struct epoll_event events[MAX_EVENTS];

while(1) {
    nfd = epoll_wait(epfd, events, MAX_EVENTS, EP_TIMEOUT);

    if(nfds < 0) {
        fprintf(stderr, "epoll_wait()\\n");
        exit(1);
    }
    for(i = 0; i < nfd; ++i) {
       /* ディスクリプタ達を処理。 */
    }
}

上記のコードはmanのlevel-triggeredインターフェイスでepollを使った場合のサンプルをフォローしていて、 for文の中身が気になる方はmanにもう少し詳しいコードが載っています。

ミクシィ開発部で使われている言語の99%がPerlと思われがちですが、弊社ではこういったコアに近いレベルの開発も実は行っています。

毎日mikio氏に色々と教わりながら面白おかしくハックしている今日この頃です。