Ruby
dbm

Ruby の dbm が default gems になっていた事を見過ごしていた件


はじめに

dbm (ruby/dbm) は Ruby 2.5.0 から default gems になっていますが、完全に記憶から抜け落ちていました(たぶん、気にかけていませんでした)。

default gems になったということは、リンクする dbm の決定を Ruby コンパイル時から gem インストール時まで遅延させることができる、ということですよね。言い換えると、同じ Ruby を使いつつ、プロジェクトごとに異なる dbm (ndbm 互換ライブラリ)を使い分けられる、ということですよね。


ndbm 互換ライブラリの決定

Ruby の DBM クラスは、任意の ndbm 互換ライブラリを扱うことができます。ただし、これは dbm gem をビルドするときに決定されるため、実行中の Ruby スクリプトから切り替える(指定する)ことはできません(無理やりやればできるかな?)。

ndbm 互換ライブラリは、デフォルトでは以下の優先順位で探索され決定されます。


  1. 4.3BSD original ndbm

  2. Berkeley DB

  3. gdbm

  4. qdbm

この優先順位は、ビルドオプション --with-dbm-type で指定することもできます。

# https://github.com/ruby/dbm/blob/18da9b1c4248b2b92046bd7150a08ee645d63a50/ext/dbm/extconf.rb#L2-L17

# configure option:
# --with-dbm-type=COMMA-SEPARATED-NDBM-TYPES
#
# ndbm type:
# libc ndbm compatible library in libc.
# db Berkeley DB (libdb)
# db2 Berkeley DB (libdb2)
# db1 Berkeley DB (libdb1)
# db6 Berkeley DB (libdb6)
# db5 Berkeley DB (libdb5)
# db4 Berkeley DB (libdb4)
# db3 Berkeley DB (libdb3)
# gdbm_compat GDBM since 1.8.1 (libgdbm_compat)
# gdbm GDBM until 1.8.0 (libgdbm)
# qdbm QDBM (libqdbm)
# ndbm Some legacy OS may have libndbm.

ndbm type は、以下の様にヘッダファイルと対応付けられています。

# https://github.com/ruby/dbm/blob/18da9b1c4248b2b92046bd7150a08ee645d63a50/ext/dbm/extconf.rb#L30-L42

headers = {
"libc" => ["ndbm.h"], # 4.3BSD original ndbm, Berkeley DB 1 in 4.4BSD libc.
"db" => ["db.h"],
"db1" => ["db1/ndbm.h", "db1.h", "ndbm.h"],
"db2" => ["db2/db.h", "db2.h", "db.h"],
"db3" => ["db3/db.h", "db3.h", "db.h"],
"db4" => ["db4/db.h", "db4.h", "db.h"],
"db5" => ["db5/db.h", "db5.h", "db.h"],
"db6" => ["db6/db.h", "db6.h", "db.h"],
"gdbm_compat" => ["gdbm-ndbm.h", "gdbm/ndbm.h", "ndbm.h"], # GDBM since 1.8.1
"gdbm" => ["gdbm-ndbm.h", "gdbm/ndbm.h", "ndbm.h"], # GDBM until 1.8.0
"qdbm" => ["qdbm/relic.h", "relic.h"],
}

例えば、Bundler を使って qdbm とリンクしたい場合は、Bundler のビルドオプションを設定しておきます。

$ bundle config --local build.dbm --with-dbm-type=qdbm

当然ですが、 ndbm 互換ライブラリのヘッダファイルは別途用意しておく必要があります。


どの dbm を使うか

各々、システム要求を満たす適当なものを選べば良いという話ではありますが、「大抵の場合はこれが使われている」という話があれば知りたいところです。ですが、あいにく dbm 識者と dbm 談義で一花咲かせた経験がないため、簡単なベンチマークで比較して検討をつけたいと思います。

1,008 バイトの key/content pair を 500,000 件、ひとつずつ書き込んだときと読み込んだとき、という試験を行いました。あくまで感覚をつかむための簡易な試験です。

※ 1,000,000 件の試験をした際、 sdbm のデータベースサイズが試験環境のディスクサイズを超えて書き込めなかったため、500,000 件程度の試験となりました。

cdbTokyo/Kyoto Cabinet は Ruby の DBM からは扱えませんが、比較のため取り上げました。


時間

※ キーや値の文字列オブジェクトを作る部分も含む(厳密さは求めなかった)。

type
write (u/s) [s]
read (u/s) [s]

Hash
1.572769 (1.281160 / 0.263842)
0.335770 (0.300842 / 0.007701)

sdbm
7.689297 (1.739403 / 5.900456)
4.128331 (1.215769 / 2.888625)

gdbm
33.555130 (11.001524 / 22.242232)
0.860940 (0.802744 / 0.031668)

Berkeley DB
33.210002 (13.640456 / 19.278301)
1.522672 (0.821140 / 0.675800)

qdbm
21.922223 (6.524669 / 15.090120)
1.270316 (0.598023 / 0.646751)

cdb
2.248181 (1.628379 / 0.509936)
0.514831 (0.443600 / 0.044133)

Kyoto Cabinet
9.228834 (4.819895 / 4.346801)
1.154338 (0.607743 / 0.521693)


ファイルサイズ

type
dir [B]
pag [B]

Hash
N/A
N/A

sdbm
4,194,304
34,356,848,640

gdbm
16
536,682,496

qdbm
181
526,291,472

type
DB [B]

Berkeley DB
774,090,752

cdb
516,002,048

Kyoto Cabinet
522,297,720


メモリ使用量

ps コマンドの RSS 変化量(厳密さは求めなかった)。

type
write [KiB]
read [KiB]

Hash
1,029,272
15,312

sdbm
4,536
3,420

gdbm
4,096
3,176

Berkeley DB
5,076
3,952

qdbm
4,052
2,748

cdb
14,488
7,004

Kyoto Cabinet
5,288
4,016


まとめ

書き散らしただけで、まとめられませんでした。


  • Ruby で dbm をプロジェクトごとに選択できる様になっていた事に気がついた

  • 簡易な辞書引きが目的であれば、許容可能なメモリ使用量に収まる限り Hash を使うことが多いかな

  • 辞書全体をメモリに載せられないなら cdb がちょうどよいかな(更新操作が不要なら)

  • 書き込みのコストを気にせず、手軽に使いたいなら gdbm でもよいかな


  • QDBM, Tokyo/Kyoto Cabinet は、安定したのか停滞したのか、よく知らない


  • Kyoto Cabinet 以降に登場した dbm 系を知らない


  • Gemfile 内でビルドオプションは指定できないんだっけ?

※ 社内勉強会のネタが全く思いつかず、この dbm ネタでお茶を濁せるかなと考えて、メモを作成。


おまけ その(1)

Qiita に dbm の記事(タグ)ってない、のか。


おまけ その(2)

諸事情から dbm ファミリはたくさんいます。まずは、機能面よりもライセンス面から、複数の実装が生まれていった様です。



  1. dbm: Version 7 Unix に含まれる Ken Thompson が書いた最初の dbm (AT&T のライセンス)


  2. ndbm: 4.3 BSD に含まれる dbm から派生した実装 (AT&T のライセンス)




  3. sdbm: ndbm のライセンス問題を解決するために public domain として配布された ndbm のクローン


  4. gdbm: ndbm のライセンス問題を解決するために新しく開発され GPL で配布された実装

その後、何人かの開発者によって、性能を向上させたり、過去の実装を置き換えることなどを目指した実装が作られました。



  • cdb: Daniel J. Bernstein (djb) によって開発された、更新できないという制約のもと高速化を実現した実装



    • TinyCDB: Michael Tokarev によって開発された、更に高速で機能も追加された互換ライブラリ




  • qdbm: 平林幹雄氏が開発した高速で効率的な ndbm 互換ライブラリ


  • Tokyo/Kyoto Cabinet: 平林幹雄氏が開発した高速で効率的な dbm の代替

  • etc.

色々あって、悩みますね。OS (ディストリビューション) やプログラミング言語のパッケージマネージャに対応してくれていれば、嬉しい限り。