mixi engineer blog

＊＊＊ 引っ越しました。最新の情報はこちら → https://medium.com/mixi-developers ＊＊＊ ミクシィ・グループで、実際に開発に携わっているエンジニア達が執筆している公式ブログです。様々なサービスの開発や運用を行っていく際に得た技術情報から採用情報まで、有益な情報を幅広く取り扱っています。

DBMによるテーブルデータベース

mixi

正月早々インフルエンザにかかって寝込んだmikioです。電車に乗る時や繁華街などに出る時はマスク着用が必須ですね。さて今回は、Tokyo Cabinetで実装したテーブル方式のデータベースについて紹介します。意外にどうして強力な機能なので、このネタは連載することを予告します。

テーブルデータベースとは

簡単に言えば、リレーショナルデータベースのテーブルのように、複数の列からなるレコードを格納できるデータベースです。SQLや表結合などの複雑な機能はサポートしませんが、そのぶん高速に動作します。つまり、DBMの速度で動くリレーショナル風データベースです（厳密にはリレーショナルデータベースではありません）。

tabledatabasecmp.png

TCの基本となるハッシュデータベースは、単純なkey/value型のデータベースであり、つまりキーにも値にもスカラ（数値や文字列などの特に構造を持たない単一の値）しか格納することはできません。キーや値にCSVやXMLなどで構造を持たせることはできますが、その構造を元にしてクエリを発行したりレコードを操作することはできません。一般的なアプリケーションで用いるほとんどのデータ構造はkey/value構造を組み合わせることで表現できるのですが、その組み合わせの分だけDBファイルを作ってそれを操作するコードを書くのはなかなか面倒なものです。

そこで、テーブルデータベースの登場です。ハッシュデータベースのように主キーでレコードを識別しながらも、リレーショナルデータベースのようにレコード内に名前をつけた複数のコラムを持たせることができます。ハッシュデータベースと違って、レコード内の個々のコラムの値を条件にしてレコードの集合を問い合わせられることが挙げられます。また、リレーショナルデータベースとは違って、あらかじめスキーマを定義する必要がなく、レコード毎に異なる種類のコラムを持たせることができます。

社員名簿を実装してみる

例として、社員名簿を考えてみましょう。社員毎にレコードを割り当てて、各レコードには、社員番号、名前、性別、入社日、所属部署名を持たせることにしましょう。以下のようなデータベースになります。

id name sex hdate div
1 空条承太郎 male 2005-03-21 brd,dev
81 東方仗助 male 2006-06-01 dev
92 汐華初流乃 male 2007-03-11 hr
127 空条徐倫 female 2007-05-23 brd,hr

ちなみに、MySQLでスキーマを表現するならば、以下のようになるでしょうか（divを正規化していないのはわざとで、"brd,hr" で役員会と人事部の兼務ということを示すことにします）。 

create table staffs (
  id int primary key,
  name varchar(255),
  sex enum ( 'male', 'female' ),
  hdate date,
  div varchar(255)
);

上記をハッシュDBで実装するのは結構面倒ですね。名前DB、性別DB、入社日DBなどなどを別ファイルにして、それらを矛盾しないように更新するロジックを書くのは骨が折れます。一方で、テーブルデータベースを使えば簡単です。まずはTCに付属のコマンドラインツールで上記のデータを格納したDBを作ってみましょう。以下のコマンドを実行すればOKです（TSVインポートツールもあります）。 

tctmgr create casket
tctmgr put casket 1 "name" "空条承太郎" "sex" "male" \
  "hdate" "20050321" "div" "brd,dev"
tctmgr put casket 81 "name" "東方仗助" "sex" "male" \
  "hdate" "20060601" "div" "dev"
tctmgr put casket 92 "name" "汐華初流乃" "sex" "male" \
  "hdate" "20070311" "div" "hr"
tctmgr put casket 127 "name" "空条徐倫" "sex" "female" \
  "hdate" "20070523" "div" "brd,hr"

予めスキーマを決めなくても、任意の名前をつけた属性をコラムとして格納できます。データベースの中身を見るには以下のコマンドを実行します。 

tctmgr list -pv casket
-------- 
1    name  空条承太郎  sex  male   hdate  20050321  div  brd,dev
81   name  東方仗助    sex  male   hdate  20060601  div  dev
92   name  汐華初流乃  sex  male   hdate  20070311  div  hr
127  name  空条徐倫    sex  female hdate  20070523  div  brd,hr

テーブルデータベースでも、普通のハッシュデータベースと同じように、主キーを指定して値を取り出すことができます。 

tctmgr get casket 81
-------- 
81   name  東方仗助    sex  male   hdate  20060601  div  dev

面白いのはここからです。主キー以外の任意のキーでも検索ができるのです。 

# 名前が「空条」で始まる社員
tctmgr search -pv casket name STRBW "空条"

# 2006年以降に入社した男の社員
tctmgr search -pv casket hdate NUMGE 20060101 sex STREQ "male"

# 役員か人事部の社員で一番古株の人
tctmgr search -pv -ord hdate numasc -m 1 casket div STROR "brd,hr"

演算子いろいろ

ハッシュデータベースだと主キーの完全一致しかなかったのに、ずいぶんと便利になった感じがしますよね。そう思っていただくために、よく使いそうな演算子を結構頑張って用意したわけです。ポインタずらしつつ文字列操作をいちいち書かにゃならんし、テストケースもたんまり書かなきゃならんし、地味すぎて泣ける作業なのです。

合致条件の演算子には以下のものがあります。演算子の前に「~」をつけると否定の意味になります。

  • STREQ : 右辺の文字列が完全一致する
  • STRINC : 右辺の文字列を含む
  • STRBW : 右辺の文字列で始まる
  • STREW : 右辺の文字列で終わる
  • STRAND : 右辺の文字列内のカンマ区切りの文字列の全てを含む
  • STROR : 右辺の文字列内のカンマ区切りの文字列のいずれかを含む
  • STROREQ : 右辺の文字列内のカンマ区切りの文字列のいずれかと完全一致する
  • STRRX : 右辺の文字列の正規表現と一致する
  • NUMEQ : 右辺の数値と一致する
  • NUMGT : 右辺の数値より大きい
  • NUMGE : 右辺の数値と同じかより大きい
  • NUMLT : 右辺の数値より小さい
  • NUMLE : 右辺の数値と同じかより小さい
  • NUMBT : 右辺のカンマ区切りの2つの数値の間である
  • NUMOREQ : 右辺のカンマ区切りの文字列のいずれかと一致する

順序指定の演算子には以下のものがあります。デフォルトは順序不定です。

  • STRASC : 文字列の辞書順の昇順
  • STRDESC : 文字列の辞書順の降順
  • STRASC : 数値の昇順
  • STRDESC : 数値の降順

ということで、SQLを使わないデータベースライブラリでも結構実用的なアプリケーションが実装できそうな予感がしてきませんか？ ブログだったら、各エントリをレコードにして、タイトルと著者名と本文と投稿日時をコラムにすればよいでしょう。メーラだったら、各メールをレコードにして、本文やSubjectやFromやToなどをコラムにすればよいでしょう。バイナリデータも入れられるので、簡易的なファイルシステムとして利用することもできます。

ただし、このデータベースがリレーショナルデータベースとは言えない決定的な要因として、表結合（複数のテーブルをまたがった演算）ができないことが挙げられます。表結合ができないということは、上記の所属部署のようにスカラ値で表現できないデータに第一正規化を施してテーブルを分割した場合、クエリを複数回に分けて発行しなければならないということを意味しています。

とはいえ、mixiなどの高負荷のシステムでは実際は表結合はあまり使われないんですね。なぜなら、テーブル毎に異なるマシン群に分散させたり、さらには論理的には同一のテーブルを主キーで区分して物理的に複数のマシンに分散させたりするからです。mixi社内用語だと前者はレベル1分散、後者はレベル2分散と呼ばれています。物理的に分散していても単一のデータベースとして扱えるソリューションもあるにはあるのですが、各種ベンダーソリューションの「癖」に振り回されるよりはおとなしくクエリを複数回発行する方を選ぶというのも現実的な技術選択のひとつです（まあ、TCの癖の方がもっとひどいという話もありますが）。

インデックスを張る

コラムに着目したクエリを発行できるといっても、所詮はハッシュデータベースを基礎としているので、主キーの完全一致以外の条件は全て全表スキャンを行うことになります。つまり全データをgrepでスキャンしているのと同じ計算量です。もちろんそれでは大規模なシステムでは使えないので、任意のコラムにインデックスを張る機能が提供されます。

コラムには型がありませんが、インデックスには型があります。文字列型の演算を高速化させたい場合は文字列型のインデックスを、数値型の演算子を高速化させたい場合は数値型のインデックスを張ることになります。ただし、型が異なる場合でもインデックスを張っておくと、メインのハッシュデータベースの全表スキャンの代わりに、それよりは小さいインデックスの全表スキャンを用いるので、計算量は同じですが処理時間は短くなります。なお、型が同じでも高速化の度合いは演算子によって異なります。

  • 文字列型インデックス:
    • 計算量が小さくなる演算子：STREQ、STRBW、STROREQ
    • 計算量は同じだが高速化する演算子：STRINC、STREW、STRAND、STROR、STRRX、NUMEQ、NUMGT、NUMGE、NUMLT、NUMLE、NUMBT、NUMOREQ
    • 計算量が小さくなる順序指定：STRASC、STRDESC
  • 数値型インデックス:
    • 計算量が小さくなる演算子：NUMEQ、NUMGT、NUMGE、NUMLT、NUMLE、NUMBT、NUMOREQ
    • 計算量は同じだが高速化する演算子：STREQ、STRBW、STROREQ、STRINC、STREW、STRAND、STROR、STRRX
    • 計算量が小さくなる順序指定：NUMASC、NUMDESC

インデックスの威力を見るために、また付録のテストコマンドを使ってみましょう。以下のコマンドを実行してください。テスト用のコラムを含んだ100万のレコードを格納したデータベースを作ります。 

tcttest write casket 1000000

格納されたレコードの一部を見てみましょう。 

tctmgr list -m 10 -pv casket
-------- 
1   str  1   num  1  type  22
2   str  2   num  1  type  28  flag  4,9,12
3   str  3   num  1  type  23  flag  4,7,10,15
4   str  4   num  1  type  27  flag  5,7,8
5   str  5   num  1  type  20  flag  4,7,8
6   str  6   num  5  type  20  flag  3
7   str  7   num  3  type  13  flag  1,2,5,6
8   str  8   num  6  type  20  flag  3,5,7,8
9   str  9   num  3  type  15  flag  1,3,5,7
10  str  10  num  6  type  29  flag  1,4,5,10

上記のデータベースに、”str” コラムが “98765″ で始まるレコードを問い合わせます。「-ph」オプションでヒントも出力します。 

tctmgr search -m 10 -pv -ph casket str STRBW 98765
-------- 
98765   str  98765   num  35013   type  27  flag  4
987650  str  987650  num  210440  type  23
987651  str  987651  num  303719  type  10
987652  str  987652  num  531217  type  12
987653  str  987653  num  597234  type  16  flag  1,3,4
987654  str  987654  num  530354  type  15  flag  5,7
987655  str  987655  num  287157  type  31
987656  str  987656  num  918276  type  18  flag  5
987657  str  987657  num  617401  type  27  flag  4,5
987658  str  987658  num  243921  type  28  flag  3
  :::: scanning the whole table
  :::: limited matching: 10
  :::: result set size: 10
  :::: leaving the natural order
  :::: elapsed time: 1.00759

「scanning the whole table」と書いてあるので、全表スキャンが行われたことがわかります。そして検索に1秒ほどかかったこともわかります。これじゃあ遅すぎるということで、”str” コラムに文字列型のインデックスを張ってみましょう。 

tctmgr setindex casket str

これで、もう “str” の検索は高速化されています。さきほどの検索をもういちどやってみます。 

tctmgr search -m 10 -pv -ph casket str STRBW 98765
-------- 
98765   str  98765   num  35013   type  27  flag  4
987650  str  987650  num  210440  type  23
987651  str  987651  num  303719  type  10
987652  str  987652  num  531217  type  12
987653  str  987653  num  597234  type  16  flag  1,3,4
987654  str  987654  num  530354  type  15  flag  5,7
987655  str  987655  num  287157  type  31
987656  str  987656  num  918276  type  18  flag  5
987657  str  987657  num  617401  type  27  flag  4,5
987658  str  987658  num  243921  type  28  flag  3
  :::: using an index: "str" asc (STRBW)
  :::: limited matching: 10
  :::: result set size: 10
  :::: leaving the natural order
  :::: elapsed time: 0.00011

もちろん検索結果は全く同じなのですが、ヒントの部分に「using an index: “str” asc (STRBW)」と出ています。”str” に張ったインデックスが効いてSTRBWが高速化されたことを示しています。それによって、経過時間が0.0001秒ほどになったこともわかります。スゲー！

インデックスはデータベースを作った後で張ってもよいし、予めインデックスを張ってからレコードを追加してもかまいません。もちろん、インデックスとレコード本体は自動的に同期がとられます。

API

ここまでコマンドラインインターフェイスでデータベースを操作してきましたが、TCはライブラリなので、APIを用いてアプリケーションにデータベース操作機能を組み込むことができます。C言語のサンプルコードを見てみましょう。 

#include <tcutil.h>
#include <tctdb.h>
#include <stdlib.h>
#include <stdbool.h>
#include <stdint.h>

int main(int argc, char **argv){
  TCTDB *tdb;
  int ecode, pksiz, i, rsiz;
  char pkbuf[256];
  const char *rbuf, *name;
  TCMAP *cols;
  TDBQRY *qry;
  TCLIST *res;

  /* データベースオブジェクトを作る */
  tdb = tctdbnew();

  /* データベースオブジェクトを開く */
  if(!tctdbopen(tdb, "casket.tdb", TDBOWRITER | TDBOCREAT)){
    ecode = tctdbecode(tdb);
    fprintf(stderr, "open error: %s\\n", tctdberrmsg(ecode));
  }

  /* レコードを格納する */
  pksiz = sprintf(pkbuf, "%ld", (long)tctdbgenuid(tdb));
  cols = tcmapnew3("name", "mikio", "age", "30", "lang", "ja,en,c", NULL);
  if(!tctdbput(tdb, pkbuf, pksiz, cols)){
    ecode = tctdbecode(tdb);
    fprintf(stderr, "put error: %s\\n", tctdberrmsg(ecode));
  }
  tcmapdel(cols);

  /* レコードを素朴な方法で格納する */
  pksiz = sprintf(pkbuf, "12345");
  cols = tcmapnew();
  tcmapput2(cols, "name", "falcon");
  tcmapput2(cols, "age", "31");
  tcmapput2(cols, "lang", "ja");
  if(!tctdbput(tdb, pkbuf, pksiz, cols)){
    ecode = tctdbecode(tdb);
    fprintf(stderr, "put error: %s\\n", tctdberrmsg(ecode));
  }
  tcmapdel(cols);

  /* TSVを使ってレコードを格納する */
  if(!tctdbput3(tdb, "abcde", "name\\tjoker\\tage\\t19\\tlang\\ten,es")){
    ecode = tctdbecode(tdb);
    fprintf(stderr, "put error: %s\\n", tctdberrmsg(ecode));
  }

  /* レコードを検索する */
  qry = tctdbqrynew(tdb);
  tctdbqryaddcond(qry, "age", TDBQCNUMGE, "20");
  tctdbqryaddcond(qry, "lang", TDBQCSTROR, "ja,en");
  tctdbqrysetorder(qry, "name", TDBQOSTRASC);
  tctdbqrysetmax(qry, 10);
  res = tctdbqrysearch(qry);
  for(i = 0; i < tclistnum(res); i++){
    rbuf = tclistval(res, i, &rsiz);
    cols = tctdbget(tdb, rbuf, rsiz);
    if(cols){
      printf("%s", rbuf);
      tcmapiterinit(cols);
      while((name = tcmapiternext2(cols)) != NULL){
        printf("\\t%s\\t%s", name, tcmapget2(cols, name));
      }
      printf("\\n");
      tcmapdel(cols);
    }
  }
  tclistdel(res);
  tctdbqrydel(qry);

  /* データベースを閉じる */
  if(!tctdbclose(tdb)){
    ecode = tctdbecode(tdb);
    fprintf(stderr, "close error: %s\\n", tctdberrmsg(ecode));
  }

  /* データベースオブジェクトを破棄する */
  tctdbdel(tdb);

  return 0;
}

TCのハッシュデータベースを使ったことがある人ならば、だいたい同じような使い方だと感じていただけると思います。違う点として、レコードを格納する際に値に文字列を指定する代わりに、コラムを含んだマップオブジェクトを指定することに注意してください。また、レコードを検索する部分はB+木のカーソルオブジェクトに近いインターフェイスになっています。データベースオブジェクトからクエリオブジェクトを作って、それに該当条件や順序指定などを施してから、検索結果を取り出します。検索結果は主キーのリストとして得られるので、それを用いてレコード本体を取り出してから表示しています。

え、なんか複雑で使いにくそうですか？ まあ、CやC++だとこれが限界でしょう。近いうちにPerlとRubyとJavaのバインディングについては私自身で書きますが、そうなると、言語に備え付けの連想配列でレコードを表現できるので、典型的なイディオムを組み合わせて直感的にプログラミングできるようになるでしょう。クエリ言語をでっち上げてDBIなどの高水準なインターフェイスを作る猛者も現れるかもしれません。

まとめ

Tokyo Cabinetに追加されたテーブルデータベースについて説明しました。SQLは喋らないけどうまい具合にテーブルが扱える小粋なツールです。そもそもなんでこれを作ったかと言えば、個人ブログを再開すべくまたブログシステムを書き始めたからです。前回QDBMで作ったストレージレイヤに気にくわない点が多かったので、TCでもっとスマートに作れないかなと思い、せっかくだから汎用のライブラリに仕上げた次第です。TCをベースとしてO/Rマッパーや分散オブジェクトシステムを実装している諸兄にももしかしたら役立つかもしれないと期待しています。

TCのテーブルデータベースに近いユースケースをカバーするものとしてSQLiteが挙げられます。「SQLiteでいいじゃん。何で？」はFAQになりそうな予感がしますが、ぶっちゃけ、SQLiteに対して主張できる優位性は特にありません。まだ十分に性能テストができていませんが、できれば時間効率と空間効率で褒めてもらえるようにこれから頑張ります。今後、TCの抽象データベースでテーブルデータベースをサポートして、Tokyo Tyrantからもテーブルデータベースを扱えるようにする予定です。

次回はテーブルデータベースの実装について詳細に説明してみたいと思います。この次も、ワッフルワッフル！