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

はじめに
----

[`dbm`](https://docs.ruby-lang.org/ja/latest/library/dbm.html) ([`ruby/dbm`](https://github.com/ruby/dbm)) は Ruby 2.5.0 から default gems になっていますが、完全に記憶から抜け落ちていました(たぶん、気にかけていませんでした)。

- [NEWS for Ruby 2.5.0](https://docs.ruby-lang.org/ja/latest/doc/news=2f2_5_0.html)

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


`ndbm` 互換ライブラリの決定
----

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

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

1. 4.3BSD original ndbm
1. Berkeley DB
1. `gdbm`
1. `qdbm`

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

```ruby
# 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` は、以下の様にヘッダファイルと対応付けられています。

```ruby
# 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 のビルドオプションを設定しておきます。

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

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


どの dbm を使うか
----

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

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

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

※ `cdb` や `Tokyo/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`](https://en.wikipedia.org/wiki/Dbm) の記事(タグ)ってない、のか。


おまけ その(2)
----

- [多様性と戦う Fight with Diversity](https://staff.aist.go.jp/tanaka-akira/pub/2013-06-01-rubykaigi-akr-ja.pdf)

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

1. `dbm`: [`Version 7 Unix`](https://en.wikipedia.org/wiki/Version_7_Unix) に含まれる Ken Thompson が書いた最初の `dbm` (AT&T のライセンス)
1. `ndbm`: 4.3 BSD に含まれる `dbm` から派生した実装 (AT&T のライセンス)
    - [The Single UNIX Specification](http://pubs.opengroup.org/onlinepubs/7908799/xsh/ndbm.h.html) として API が標準化
1. `sdbm`: `ndbm` のライセンス問題を解決するために public domain として配布された `ndbm` のクローン
1. `gdbm`: `ndbm` のライセンス問題を解決するために新しく開発され GPL で配布された実装

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

- `cdb`: Daniel J. Bernstein (djb) によって開発された、更新できないという制約のもと高速化を実現した実装
    - `TinyCDB`: Michael Tokarev によって開発された、更に高速で機能も追加された互換ライブラリ
- `qdbm`: 平林幹雄氏が開発した高速で効率的な `ndbm` 互換ライブラリ
- `Tokyo/Kyoto Cabinet`: 平林幹雄氏が開発した高速で効率的な `dbm` の代替
- etc.

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