dbの3態

前回はFreeBSDのパッケージングシステムを調べた。RDBM/SQLだった。じゃ、 他のOSは？

OpenBSDが一番初期の形だ。それにあきたらなくなって、FreeBSDはsqliteを取 り入れたんだった。

vbox$ cd /var/db/pkg
vbox$ ls -l emacs-28.2-no_x11/
total 1000
-rw-r--r--  1 root  wheel  489364 Nov  3 05:47 +CONTENTS
-rw-r--r--  1 root  wheel    1298 Nov  3 05:46 +DESC
-rw-r--r--  1 root  wheel      52 Nov  3 05:47 +REQUIRING
vbox$ cat emacs-28.2-no_x11/+REQUIRING
gnutls-3.7.7
gmp-6.2.1p0
libxml-2.10.3
jansson-2.14

こんな具合にテキストベースで全て賄われている。

一方ArchLinux/pacmanに有るパッケージ情報も見てみる。

[sakae@arch local]$ pwd
/var/lib/pacman/local
[sakae@arch local]$ file emacs-nox-28.2-2/*
emacs-nox-28.2-2/desc:  ASCII text
emacs-nox-28.2-2/files: ASCII text
emacs-nox-28.2-2/mtree: gzip compressed data, from Unix, original size modulo 2^32 818561

descは、いわゆるパッケージのinfo。filesはファイル名のリスト。mtreeは、 それにシグネチャを加えたもの。サイズが大きいので、tgzになってる。素直 な仕組みで、OpenBSDのそれと似ている。

デビアンのパッケージングシステムがどうなってるか、調べてみた。そしたら、

sakae@deb:/var/lib/apt$ file listchanges.db
listchanges.db: Berkeley DB (Hash, version 9, native byte-order)

dpkg/ とかも関係してくるみたいだけど、深くは追求しない。それより、バー クレーですよ。リナも憧れのバークレーですよ。スタンフォードでもいいんだ ろうけど、ソフトの世界じゃバークレーかMITが聖地ですから。

Berkeley DB を見ると、ボラクルに売却されて随分昔から、 Oracle Berkeley DB になってるようだ。知らなかったぞ。

DB_File - Berkeley DB バージョン 1.xへのPerl5アクセス

btree – 単純な BTree データベース for MicroPython

bsddb – Berkeley DB ライブラリへのインタフェース

何の気もなく

man -k database
btree(3) - btree database access method
dbopen(3) - database access methods

なんてやったら、面白いのが出てきた。中身を眺めてみると、

NAME
     btree – btree database access method
DESCRIPTION
     The dbopen() routine is the library interface to database files.  One of
     the supported file formats is btree files.  The general description of
     the database access methods is in dbopen(3).  This manual page describes
     only the btree specific information.
SEE ALSO
     dbopen(3), hash(3), recno(3)

どうやら標準で提供されるデータベース構築用のルーチンみたいだ。dbopenす る時に、データベースの性格をB木にするか、ハッシュにするか、レコードに するか選ぶみたい。

とりあえず、ソースに対面かな。README

#       $OpenBSD: README,v 1.5 2015/04/05 14:35:16 tedu Exp $
#       @(#)README      8.27 (Berkeley) 9/1/94

This is version 1.85 of the Berkeley DB code.

ボラクルに買収される前の由緒正しきコードとな。

注目なのは、hash/ndbm.c なんてのが混っている事。そう、あのndbmですよ。 これに対抗する為、gdbmなんてのが作られた。

かの昔、CGIが出初めた頃、スケジュールWEBを作ろうとした。どっちのdbmが 優秀なんだろうかねと散々悩んだものだ。こんな所で出会うとはね。

コードをざっと 見。

static DBM *
_dbm_open(const char *file, const char *suff, int flags, mode_t mode)
{
  :
        info.bsize = 4096;
        info.ffactor = 40;
        info.nelem = 1;
        info.cachesize = 0;
        info.hash = NULL;
        info.lorder = 0;
        return ((DBM *)__hash_open(path, flags, mode, &info, 0));
}

hashを使っているんだね。

で、dbopenとかは、どう使えばいいの？ こういう時は実例に当たるのが一番 だろう。提供されてるソースを横断的に探してみる。リナでこれをやろうとす ると、とっても大変だろう。検索の目印は、dbopenで十分だろう。

vbox$ find . -name '*.c' | xargs grep -l dbopen
./distrib/special/libstubs/db.c
./lib/libc/db/db/db.c
./lib/libc/gen/devname.c
./lib/libc/gen/getcap.c
./lib/libc/gen/getnetgrent.c
./lib/libc/gen/getpwent.c
./lib/libc/gen/ttyname.c
  :
./usr.bin/cap_mkdb/cap_mkdb.c
./usr.bin/vacation/vacation.c
./usr.bin/vi/common/exf.c
./usr.bin/vi/common/log.c
./usr.sbin/dev_mkdb/dev_mkdb.c
./usr.sbin/kvm_mkdb/kvm_mkdb.c
./usr.sbin/kvm_mkdb/testdb.c
./usr.sbin/netgroup_mkdb/netgroup_mkdb.c
./usr.sbin/pwd_mkdb/pwd_mkdb.c
./usr.sbin/rpc.statd/statd.c
./usr.sbin/sa/pdb.c
./usr.sbin/sa/usrdb.c
./usr.sbin/smtpd/makemap.c
./usr.sbin/smtpd/table_db.c
./usr.sbin/spamdb/spamdb.c
./usr.sbin/ypserv/common/ypdb.c
./usr.sbin/ypserv/makedbm/db.c

簡単な奴を作ってみる。仕様は、与えた文字列をkeyにして、それを倍に連結して登録するやつ。

#include <stdio.h>
#include <string.h>
#include <sys/types.h>
#include <db.h>
#include <fcntl.h>
#include <limits.h>

DB *db;

void reg_kv(char *mykey) {
    char dst[128];
    DBT key, data;

    snprintf(dst, sizeof dst, "< %s_%s >", mykey, mykey);
    key.data = (char *)mykey;
    key.size = strlen(mykey) + 1;
    data.data = (char *)dst;
    data.size = strlen(dst) + 1;
    (void)(db->put)(db, &key, &data, 0);
}

int main(){
  db = dbopen("z.db", O_CREAT|O_RDWR, 0644, DB_BTREE, NULL);
  reg_kv("hogefuga");
  reg_kv("hello");
  reg_kv("HACKING");
  (void)(db->close)(db);
  return 0;
}

読み出しのコードは、まだなんで、ちょいとズルしてみた。キーも値も、取り 敢えず保存されたっぽい。そこはかとなく、辞書順になってる。まあ断定は出 来無いけど。

vbox$ strings z.db
HACKING
< HACKING_HACKING >
hello
< hello_hello >
hogefuga
< hogefuga_hogefuga >

キーを指定して値を表示するコード例。

#include <stdio.h>
#include <string.h>
#include <sys/types.h>
#include <db.h>
#include <fcntl.h>
#include <limits.h>

DB *db;

void chkV(char *mykey) {
    DBT key, data;

    key.data = (char *)mykey;
    key.size = strlen(mykey) + 1;
    if ((db->get)(db, &key, &data, 0) == 0)
      printf("%s\n", (char *)data.data);
    else
      printf("Not found\n");
}

int main(){
  char ck[64];

  db = dbopen("z.db", O_RDONLY, 0644, DB_BTREE, NULL);
  for ( ; ; ){
    printf("key? "); scanf("%s", ck);
    chkV(ck);
  }
  (void)(db->close)(db);
  return 0;
}

動かして確認してみる。

vbox$ ./a.out
key? HACKING
< HACKING_HACKING >
key? hello
< hello_hello >
key? hacking
Not found

gettimeofdayを使うかと思っていたら、便利なものが有った。

#include <time.h>
#include <sys/time.h>

int main(){
  char buf[128];
  FILE *fp;
  int cnt=0;
  struct timespec pst, start, stop;

  db = dbopen("z.db", O_CREAT|O_RDWR|O_TRUNC, 0644, DB_HASH, NULL);
  fp = fopen("./SEED", "r");
  clock_gettime(CLOCK_MONOTONIC, &start);
  while(fgets(buf, sizeof buf, fp) != NULL){
    buf[strlen(buf) - 1] = '\0';
    reg_kv(buf);
    cnt++;
    if (cnt % 10000 == 0){
      clock_gettime(CLOCK_MONOTONIC, &stop);
      timespecsub(&stop, &start, &pst);
      printf("%d %lld.%09ld\n", cnt, (long long)pst.tv_sec, pst.tv_nsec);
    }
  }
  fclose(fp);
  (void)(db->close)(db);
  return 0;
}

10000 0.342093758
20000 0.814867812
 :
220000 12.170719463
230000 12.939625008

gnuplot "log" w l で、簡単にグラフ化。件数が増えるとグラフが直線から剃 れて立ってくる風。ちょいと上のプログラムを変更すれ ば、微分した結果をグラフ表示できるぞ。

vbox$ seq -f p%.6fq  0 0.000997 1000 | head -5
p0.000000q
p0.000997q
p0.001994q
p0.002991q
p0.003988q
vbox$ seq -f p%.6fq  0 0.000997 1000 | wc
 1003010 1003010 12928798

こんな風に人口データを作成して、試してみると面白いかな。

(gdb) b hash_put
Function "hash_put" not defined.
Breakpoint 1 (hash_put) pending.
(gdb) r
Starting program: /tmp/a.out

Breakpoint 1, hash_put (dbp=0x7c002940, key=0xcf7dbd04, data=0xcf7dbcfc, flag=0\
) at /usr/src/lib/libc/db/hash/hash.c:523
523             hashp = (HTAB *)dbp->internal;
(gdb) n
524             if (flag && flag != R_NOOVERWRITE) {
(gdb) p *hashp
$2 = {
  hdr = {
    magic = 398689,
    version = 2,
    lorder = 1234,
    bsize = 8192,
    bshift = 13,
    dsize = 256,
    ssize = 256,
    sshift = 8,
    ovfl_point = 11,
    last_freed = 167,
    max_bucket = 1522,
    :

これが管理情報か。次はハッシュの真髄。

(gdb) b __default_hash
Breakpoint 2 at 0x782a464: file /usr/src/lib/libc/db/hash/hash_func.c, line 52.
(gdb) c
Continuing.

Breakpoint 2, __default_hash (key=0x1ada33be, len=9) at /usr/src/lib/libc/db/hash/hash_func.c:52
52              if (len > 0) {
(gdb) bt
#0  __default_hash (key=0x1ada33be, len=9) at /usr/src/lib/libc/db/hash/hash_func.c:52
#1  0x07809493 in __call_hash (hashp=0x4c413e00, k=0x1ada33be "hogefuga", len=9) at /usr/src/lib/libc/db/hash/hash.c:848
#2  hash_access (hashp=<optimized out>, action=HASH_PUT, key=0xcf7d40d4, val=0xcf7d40cc) at /usr/src/lib/libc/db/hash/hash.c:574
#3  0x07808bb6 in hash_put (dbp=0x4c3f7f00, key=0xcf7d40d4, data=0xcf7d40cc, flag=0) at /usr/src/lib/libc/db/hash/hash.c:532
#4  0x1ada48c2 in reg_kv (mykey=0x1ada33be "hogefuga") at mydb.c:19
#5  0x1ada4968 in main () at mydb.c:24

dbm — Unix "データベース" へのインターフェース

Pythonのdbmの使い方

In [1]: import dbm
   ...: db = dbm.open('/tmp/dbm', 'c')
   ...: db['foo'] = 'bar'
   ...: db['hoge'] = 'meta'
   ...: db.close()

(venv) [sakae@fb /tmp]$ file dbm.db
dbm.db: Berkeley DB 1.85 (Hash, version 2, native byte-order)
(venv) [sakae@fb /tmp]$ strings dbm.db
barfoo
metahoge

前回の資料をみていたら、矢印が使われていた。それから、一行野郎も出てい た。初めての体験で新鮮だな。

# key の検索。ヒットすれば True、しなければ False
def member(self, key) -> bool:
    t = self.root
    :
	    return False

# キーのリスト
def keys(self) -> list: return keys_sub(self.root)

そして、遂にでてきたか。 Check out Codon: A Python compiler if you have a need for C/C++ speed

組み込み関数も、対象でしょうね。

This year's Index

Home