データベース

2011年04月02日

BDBで測定やらなんやらやっていたら
DBの情報を保存するファイルサイズが
ものすごいサイズになっていました。

そんなわけで今回は回数ごとにファイルサイズを出してみました。

ちなみにRECNOにしたデータベースファイルでは
データ用のバッファがまるまる保存されるのか
少ないエントリでもえらい容量を食ってました\(^o^)/
プログラムも作ってないので
今回はhashとbtreeでサイズの比較をしています。

1回のDBファイルサイズ
% ls -s *.db
16 -rwx------ 1 nanodayo staff 8.0K 2 17 13:52 btree.db*
32 -rwx------ 1 nanodayo staff 16K 2 17 13:51 hash.db*


hashのほうが容量必要なみたいですねー。
ある程度余分な領域があるのでしょうか。

エントリ数は1でも2でもサイズが同じだったので
エントリ数が一定以上になった場合に改めて確保・・・という形ではないかと思われます。

10,000回のDBファイルサイズ
992 -rwx------ 1 nanodayo staff 496K 2 14 21:48 btree.db*
720 -rwx------ 1 nanodayo staff 360K 2 14 21:47 hash.db*


100,000回のDBファイルサイズ
9928 -rwx------ 1 nanodayo staff 4.8M 2 14 23:14 btree.db*
6104 -rwx------ 1 nanodayo staff 3.0M 2 14 23:04 hash.db*


1,000,000回のDBファイルサイズ
112456 -rwx------ 1 nanodayo staff 55M 2 15 03:14 btree.db*
84280 -rwx------ 1 nanodayo staff 41M 2 15 01:34 hash.db*


こっちではbtreeの方が容量を多く使っていますね。
領域を確保する際のしきい値はbtreeの方が低いのでしょうか。

しきい値の違いを求めるには、エントリ数を増やしながら
ファイルサイズを見ていかないといけなさそうです。
(今回はやっていませんorz)

エントリ数を10倍にしてってますが
容量もだいたい10倍になっていますね。

10,000,000回のDBファイルサイズ
1142768 -rwx------ 1 nanodayo staff 558M 2 17 10:46 btree.db*
134418952 -rwx------ 1 nanodayo staff 64G 2 16 18:03 hash.db*


ただここでは逆転。
容量の差も大きいです。

しきい値の計算方法自体に違いがあるということでしょうか。

nanodayo at 09:19コメント(0)トラックバック(0) 

2011年02月15日

BDBで使えるデータ構造についてです。
BDB内の用語ではアクセスメソッドと呼ばれています。

recno


行単位なデータ構造
多分双方向リストと変わらない・・・?
行番号みたいな概念があるので
BDBでも次のデータとか前のデータみたいな指定の仕方ができます。
順番に処理したい時には適しているデータ構造ですね。

btree


いわゆる二分木ツリー。

btree


図にするとこんな感じ。
ツリーの偏りが控えめに構築できていれば
パフォーマンスは良いはず。
オーダーはLog Nとかになるんだったかな。

hash


一定の法則に基づいて、元の値に対するインデックスの値を求めます。
割り算が例に出されることが多いです。

例えばある数を、9で割った余りは0から8のどれかになります。
これをそのまま配列の添字にして格納すれば探索が一回でできるので
データの量と関係なく、一定の速度が期待できます。

これがkey-valueのペアだったりすると
keyに対応するvalueを一回の処理で探索できます。

hash


ところが、ここで疑問が出てくると思います。
元の値は違うけど、たまたま同じハッシュ値になったらどうするんだろう
そう、確かにそういう問題がはらんでいます。

なので
・ハッシュ値の範囲を広くする
・衝突した場合、そこにリストを作って管理する
という方法が採られています。
リストの例は、図の8番目の配列がそうですね。

衝突した場合は別ですが
エントリ数が多くても、検索にかかる処理は同じなので
大量のエントリを扱う場合はハッシュが適しているかと思います。
ただし、使われないメモリ領域も確保する必要があるので
無駄が生じます。
図で言うと2,5,8以外は使っていませんしね。

測定してみた


このように、データ構造ごとに特徴がありますが
実際、性能の差はどんなものだろうということで測定してみました。

内容としてはスクリプトを使って
100000回くらいDBへのPUTを実行し
一回一回のPUTにかかった時間を測定してみました。

結果としては
  • ハッシュは極端に遅いケースがあるが安定している
  • エントリ数が140くらいならbtreeの方が速い
という結果なりました。

グラフにするとこんな感じ。
(量が多すぎてグラフが書けなかったので先頭200回を取り出してます)

first200


サンプル数を1000にするとこんな感じ。

1000


ちなみに、keyをkey1とかkey2とかの、1づつ増やしての測定なので
btreeのツリーには偏りがあるかもしれません。
もしかすると一方向リストと同じかも・・・

CDF・PDFにするとこんな感じ。

cdf_hash_and_btree_200


pdf_hash_and_btree_200


何割かは、hashが速いようですが
btreeの方が速いケースが多いようです。
PDFでの、btreeの二つ目の山は140(くらい)を超えてからの
hashより遅くなるパターンが現れています。

1000回だとこう。

cdf_hash_and_btree_1000


pdf_hash_and_btree_1000


140を超え、btreeがhashより遅くなるパターンが多いので
大体の場合、hashの方が速いようですね。

btreeの200回と1000回の比較はこれ。

hash_cdf_200and1000


hashの200回と1000回の比較。

hash_cdf_200and1000


200回のグラフが、速いケースが多いのは
恐らくツリーが膨れていないからでしょう。
1000回だと、ツリーが大きくなって
時間のかかるケースの割合が増えるからでしょうか。

btreeの200回と1000回の比較はこれ。

btree_pdf_200and1000


山の高さが見事に逆転していますね。

hashの200回と1000回の比較

hash_pdf_200and1000


山が低くなっていますね。
hashの衝突などで、極端に遅くなるケースも出てくるからでしょうか。

nanodayo at 00:33コメント(0)トラックバック(0) 

2010年12月10日

DBって何?


データベースです。

プログラムで使うデータを保存するためのものですね。
データベースと言われて、真っ先に出てくるのはSQL。
主流なのはPostgreSQLとMySQLで、高機能なのがPostgresSQLで、シンプルな代わりに軽いのがMySQLというような住み分けになっています。

最近ではNoSQLなんて動きもあって、そもそもSQL自体が大げさなのでもっとシンプルなKVSとかが注目を集めています。

なんて話をしておきながら、今回の記事はSQLもKVSも扱いません。BDBです。
部類的にはKVSだったりするんでしょうか。まぁいい。

歴史的経緯


正式名称はBerkeley Database。
カルフォルニア大学のバークレー校で開発されたものらしいですが、開発者がSleepycat Softwareという会社を設立してそちらで開発。
その後はOracleに買収されて今に至る と紆余曲折しているようです。
オープンソースのもあるので利用はできるようです。

使い方


プログラムからは関数を呼び出して使います。
当然DBの操作を行うコードを書かねばなりません。

C言語での使い方の流れはこんな感じ。
  1. ヘッダファイルをinclude
  2. dbopenでデータベースファイルを開く
  3. put/getでデータベース内のデータを扱う
  4. syncで操作した内容をファイルに反映させる
  5. dbcloseでファイルを閉じる


ヘッダファイル
#include <sys/types.h>
#include <db.h>
#include <fcntl.h>
#include <limits.h>


dbopen
DB * dbopen(const char *file, int flags, int mode, DBTYPE type, const void *openinfo);

fileはファイルの名前を渡します。
flagsとmodeについてはopen()で指定するものと同様です。

DBTYPEは、DB内部でのデータ構造です。
DB_BTREE、DB_HASH、DB_RECONOのいずれかを指定します。
openinfoは、データを処理するためのアクセスメソッドを指定するみたいですが、NULLにすればデフォルトのものが適用されるそうです。

DB構造体
typedef struct {
 DBTYPE type;
 int (*close)(const DB *db);
 int (*del)(const DB *db, const DBT *key, u_int flags);
 int (*fd)(const DB *db);
 int (*get)(const DB *db, DBT *key, DBT *data, u_int flags);
 int (*put)(const DB *db, DBT *key, const DBT *data, u_int flags);
 int (*sync)(const DB *db, u_int flags);
 int (*seq)(const DB *db, DBT *key, DBT *data, u_int flags);
} DB;


dbopen()の返り値がこれなので
db = dbopen(なんたらかんたら)みたいに実行してから
db->get(なんたらかんたら)のようにして、各種操作を行います。

DBT構造体
typedef struct {
 void *data;
 size_t size;
} DBT;


実際に扱うデータは、このDBT構造体で扱います。
dataへのポインタと、データサイズだけというとってもシンプルな構造。
key用とdata用に2つ作る必要があります。

サンプルコード

//dbtest.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <sys/types.h>
#include <db.h>
#include <fcntl.h>
#include <limits.h>

int main(int argc, char** argv)
{
  const char* file;
  int flags;
  int mode;
  DBTYPE type;
  const void* openinfo = NULL;
  DB* db;
  DBT* key;
  DBT* value;
  DBT* get;
  int opt;
  char keybuf[512];
  char valuebuf[2048];
  char getbuf[2048];

  key = malloc(sizeof(DBT));
  value = malloc(sizeof(DBT));
  get = malloc(sizeof(DBT));
  key->data = keybuf;
  value->data = valuebuf;
  get->data = getbuf;

  while((opt = getopt(argc, argv, "k:v:")) != -1) {
    switch(opt) {
      case 'k':
        strcpy(key->data, optarg);
        printf("key is %s\n", (char *)key->data);
        break;
      case 'v':
        strcpy(value->data, optarg);
        printf("value is %s\n", (char *)value->data);
        break;
    }
  }

  key->size = strlen(key->data);
  value->size = (strlen(value->data)+1);
  printf("value size is %d\n", (int)value->size);

  file = "hash.db";
  flags = O_CREAT;
  flags |= O_RDWR;
  mode = S_IRWXU;
  type = DB_HASH;

  db = dbopen(file, flags, mode, type, openinfo);
  db->put(db, key, value, 0);
  db->sync(db, 0);
  db->get(db, key, get, 0);
  printf("got value is %s\n", (char *)get->data);
  printf("got value size is %d\n", (int)get->size);
  db->close(db);
  return 0;
}


引数で指定したkey/valueをdbに書きこんで、そのまま読み出すプログラム。
以下のように実行します。


# ./dbtest -k key -v value
key is key
value is value
value size is 6
got value is value
got value size is 6


value->size = (strlen(value->data)+1);で、+1しているのがポイントです。
strlenだと、ヌル文字をカウントしないので、+1しないと以下のような結果になってしまいます。

# ./dbtest -k key -v value
key is key
value is value
value size is 5
got value is valuekey
got value's size is 5

valueの後にkeyというデータもくっついています。
DB_TYPEにDB_HASHを使った場合は起きますが、DB_BTREEでは起きませんでした。
おそらくデータを保存する際の書式で、DB_BTREEではヌル文字で区切っているけど、DB_HASHではデータにヌル文字が含まれている前提なのではないでしょうか。
なのでgetした際に、ヌル文字が登場するまで読んでいて他のデータが混ざっているのかなぁと。

postmapで確認
同じプログラムからkey/valueを取得しても、ちゃんと動いているか分かりにくいので、postmapでも確認してみましょう。
postmapとはpostfixに付属のツールで、DBファイルのデータを扱えます。
※DBの確認方法としてはあんまり一般的ではないと思われます。

# postmap -q key hash
value


余談
postmapを最初に見つけたときに
postfixをposixに空目していて、何の疑いもなく
DBの確認に使っていましたとさ\(^o^)/

nanodayo at 00:51コメント(14)トラックバック(0)