djbが開発したcdb(constant database)メモ

ふと組み込み型 kvs の cdb(constant database) の仕様を知りたくなったのでメモ。

URL

特徴

オフィシャルサイトの “What is it?” のコピペ

cdb is a fast, reliable, simple package for creating and reading constant databases. Its database structure provides several features:

  • Fast lookups: A successful lookup in a large database normally takes just two disk accesses. An unsuccessful lookup takes only one.
  • Low overhead: A database uses 2048 bytes, plus 24 bytes per record, plus the space for keys and data.
  • No random limits: cdb can handle any database up to 4 gigabytes. There are no other restrictions; records don’t even have to fit into memory. Databases are stored in a machine-independent format.
  • Fast atomic database replacement: cdbmake can rewrite an entire database two orders of magnitude faster than other hashing packages.
  • Fast database dumps: cdbdump prints the contents of a database in cdbmake-compatible format.

cdb is designed to be used in mission-critical applications like e-mail. Database replacement is safe against system crashes. Readers don’t have to pause during a rewrite.

利用例

  • djbdns
  • qmail

作者

Daniel J. Bernstein

競合ソフトウェア

インストール

http://cr.yp.to/cdb/install.html

make して次のようなエラー起きた場合

./load cdbget cdb.a buffer.a unix.a byte.a
/usr/bin/ld: errno: TLS definition in /lib/x86_64-linux-gnu/libc.so.6 section .tbss mismatches non-TLS reference in cdb.a(cdb.o)
/lib/x86_64-linux-gnu/libc.so.6: could not read symbols: Bad value
collect2: ld returned 1 exit status
make: *** [cdbget] Error 1

gcc のオプションで errno.h をインクルードするようにする

$ echo 'gcc -O2 -include /usr/include/errno.h' > conf-cc

プログラム群

インストールするとファイル conf-home で指定したディレクトリ(デフォルトは /usr/local/bin)に以下のプログラムがインストールされる

  • cdbdump
  • cdbget
  • cdbmake
  • cdbmake-12
  • cdbmake-sv
  • cdbstats
  • cdbtest

cdbmake

http://cr.yp.to/cdb/cdbmake.html

データベースを構築するプログラム。
仕様上、キーを追加するたびにデータベースを再構築する必要がある。

cdbmake/cdbget の入出力レコードは以下。

+klen,dlen:key->data

この形式でデータを渡す

$ cdbmake db.cdb db.tmp <<EOF
> +3,5:one->Hello
> +3,7:two->Goodbye
>
> EOF

cdbmake は db.tmp でデータベースを構築した後 db.cdb に move する。

cdbdump

全レコードをダンプする

$ cdbdump < db.cdb
+3,5:one->Hello
+3,7:two->Goodbye

cdb はレコードの順番も保持しているので

$ cdbdump < db.cdb  | cdbmake new.cdb new.tmp

とすれば db.cdb と new.cdb は一致する。

cdbget

http://cr.yp.to/cdb/cdbget.html

キーからデータを取得。
キーが存在しない場合は、ステータスコード100を返す

$ cdbget one < db.cdb
Hello
$ cdbget unknown_key < db.cdb
$ echo $?
100

cdbmake-sv

/etc/services ファイルからデータベースを構築する。
awk で cdb のレコード形式に変換し、 cdbmake しているだけ。

$ cdbmake-sv sv.cdb svt.tmp < /etc/services
$ cdbdump < sv.cdb  | head
+6,6:@1/tcp->tcpmux
+10,1:tcpmux/tcp->1
+6,4:@7/tcp->echo
+8,1:echo/tcp->7
+6,4:@7/udp->echo
+8,1:echo/udp->7
+6,7:@9/tcp->discard
+11,1:discard/tcp->9
+8,1:sink/tcp->9
+8,1:null/tcp->9
$ cdbget echo/tcp < sv.cdb
7

cdbmake-12

空白区切り(スペース、タブ)の key/data のペアからデータベースを構築する。
awk で cdb のレコード形式に変換し、 cdbmake しているだけ。
コマンドラインから操作する際に便利

$ cdbmake-12 12.cdb 12.tmp <<EOF
> one Hello
> two Goodbye
>
> EOF

cdbstats

cdb はキーのハッシュ値からインデックスの格納場所が決まる。
ハッシュ値から一意に決まるエリアが使用済みの場合、空きが見つかるまで場所をずらしていく。
ハッシュ値から決まる場所と実際に利用された場所との距離の統計情報を表示。

http://cr.yp.to/cdb/cdbstats.html

$ cdbstats  < sv.cdb
records       1237
d0             982
d1             184
d2              45
d3              18
d4               8
d5               0
d6               0
d7               0
d8               0
d9               0
>9               0

cdbtest

データベースの整合性チェック。

http://cr.yp.to/cdb/cdbstats.html

$ cdbtest < sv.cdb
found: 1234
different record: 3
bad length: 0
not found: 0
untested: 0

各項目の意味は URL を参照

重複キーの登録

cdb は同じキーに対して複数のデータを設定できる。

$ cdbmake-12 dup.cdb dup.tmp <<EOF
> one Hello
> one World
> EOF
$ cdbget one < dup.cdb
Hello
$ cdbget one 1 < dup.cdb  # skip first found key
World
$ cdbtest < dup.cdb
found: 1
different record: 1
bad length: 0
not found: 0
untested: 0

ベンチマーク

cdb と Berkeley DB とTokyo Cabinet のベンチマーク

https://news.ycombinator.com/item?id=622350
http://www.dmo.ca/blog/benchmarking-hash-databases-on-large-data/

データベースファイル仕様

cdb は “Fast lookups” と “Low overhead” を特徴として持っている。
データベースファイルの仕様は以下の2つを参照。

一般人向け(リファレンスコード有り)

http://www.unixuser.org/~euske/doc/cdbinternals/index.html

ミニマリスト向け(djb 本人の解説)

http://cr.yp.to/cdb/cdb.txt

ハッシュ関数

cdb ではハッシュ関数に h = ((h << 5) + h) ^ c(初期値は 5381) を利用している。

このハッシュ関数に関する考察は次の URL を参照

stackoverflow:Reason for 5381 number in DJB hash function?
http://stackoverflow.com/questions/10696223/reason-for-5381-number-in-djb-hash-function/13809282#13809282

djb ハッシュ関数と他のハッシュ関数の比較は次の URL が詳しい

stackexchange:Which hashing algorithm is best for uniqueness and speed?
http://programmers.stackexchange.com/questions/49550/which-hashing-algorithm-is-best-for-uniqueness-and-speed

別実装

Tagged with: , , ,
Posted in database

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Archives
  • RT @__apf__: How to write a research paper: a guide for software engineers & practitioners. docs.google.com/presentation/d… /cc @inwyrd 1 week ago
  • RT @HayatoChiba: 昔、自然と対話しながら数学に打ち込んだら何かを悟れるのではと思いたち、専門書1つだけ持ってパワースポットで名高い奈良の山奥に1週間籠ったことがある。しかし泊まった民宿にドカベンが全巻揃っていたため、水島新司と対話しただけで1週間過ぎた。 それ… 3 weeks ago
  • RT @googlecloud: Ever wonder what underwater fiber optic internet cables look like? Look no further than this deep dive w/ @NatAndLo: https… 3 weeks ago
  • @ijin UTC+01:00 な時間帯で生活しています、、、 6 months ago
  • RT @mattcutts: Google's world-class Site Reliability Engineering team wrote a new book: amazon.com/Site-Reliabili… It's about managing produc… 9 months ago
%d bloggers like this: