豪鬼メモ

ピンチはチャンス

DBMの設計と実装 その0 全体の計画

DBMの設計と実装について20回くらいに分けて書いてみる。まずは全体の計画と意気込みから。

諸君　私はDBMが好きだ
諸君　私はDBMが好きだ
諸君　私はDBMが大好きだ

ハッシュ表が好きだ
開番地法が好きだ
連鎖法が好きだ
赤黒木が好きだ
B+木が好きだ
スプレー木が好きだ
トライ木が好きだ
スキップリストが好きだ
ブルームフィルタが好きだ

統計で　会計で
辞書検索で　文書検索で
言語処理で　画像処理で
アカウント管理で　機械学習で
シミュレーションで　ゲームで
ローカルで　クラウドで

この地上で使われるありとあらゆるデータベースが大好きだ

数値を並べただけのテーブルから一瞬で所望のレコードが探せるのが好きだ
ノードの分割操作を繰り返していくと根にたどり着いて木の高さが上がった時など心が踊る

単一プロセスの操るライブラリだけでデータ管理が完結するのが好きだ
メモリとスレッドに物を言わせて全ての入力データをバッチ処理した時など胸がすくような気持ちだった

シリアライズした高次データが単なる文字列として格納されるのが好きだ
人間可読性を求めたJSONにBase64エンコードしたバイナリを入れている様など感動すら覚える

クラスの異なるオブジェクト達を無理やり同一ファイルに押し込めていく様などはもうたまらない
待ち並ぶスレッド達が私の投入したジョブキューとともにロードアベレージを上げるスケジューラにごりごりと動かされるのも最高だ
哀れなフリーブロック達が粗末なガベコレで結合されたのを無視してページごと記憶領域が確保された時など絶頂すら覚える

破棄済みのオブジェクトに滅茶苦茶にされるのが好きだ
必死に守るはずだったクリティカルセクションが複数スレッドに蹂躙され一貫性が犯されデータが壊れていく様はとてもとても悲しいものだ

I/O層の遅さに律速されてタイムアウトするのが好きだ
バグレポートに追い回され廃人のようにバイナリを眺めるのは屈辱の極みだ

諸君　私はDBMを　地獄の様なDBMを望んでいる
諸君　休日にすら技術ブログを読み漁る辣腕プログラマ諸君
君達は一体何を望んでいる？

更なるDBMを望むか？
主キーでしか検索できない糞の様なDBMを望むか？
データ最適化の限りを尽くしRDBのオプティマイザを凌ぐ嵐の様な性能を望むか？

（key-value! key-value! key-value! key-value! key-value! key-value!）

よろしい　ならばDBMだ

我々は渾身のテストを通過して今まさにリリースされんとするパッケージだ
だが、この暗い闇の底で8年もの間堪え続けてきた我々にただのDBMではもはや足りない！！

オープンソースを！！
一心不乱のオープンソースを！！

我らはわずかに週末と夜　週1000人日に満たぬホビープログラマに過ぎない
だが諸君は一騎当千の古強者だと私は信仰している
ならば我らは諸君と私で総工数100万と1人日の開発集団となる

我々を忘却の彼方へと追いやり眠りこけている連中を叩き起こそう
ソースアーカイブを落としtarで開かせmakeさせよう
連中にビルド時間の遅さを思い出させてやる
連中に動作時間の速さを思い出させてやる

キーと値のはざまには奴らの哲学では思いもよらない事があることを思い出させてやる
10万行のソースコードのライブラリで世界を記録し尽くしてやる

そうだ　あれが我々が待ちに望んだC++20の規格だ

私は諸君らを約束通り連れて帰ったぞ　あの懐かしの工程へ　あの懐かしのDBMへ

(テックリード殿！CTO代行！代行殿！プロダクトマネージャ殿！)

そしてブランチはついにマージされカナリーへと登る

ソフトウエアエンジニア各員に伝達　仕様変更である

さぁ　諸君
エディタを開くぞ


そんなわけで、かつてライフワーク的に作っていたDBMを今風に作り直してみることにした。コロナ禍の中、週末特にやることもないので。まずはその設計をここにメモしていこうと思う。

まずはDBMって何かということだが、DataBase Managerの略であり、キーと値からなる連想配列をファイル上に記録したものである。キーバリューストアとかKVSとか言われたりもするらしい。KVSというとコンセプトとかインターフェイスについての言及になるが、DBMというとそのローカルファイル上の実装についての言及であることが多いだろう。オリジナルのDBMはかのケン・トンプソンが実装していて、有志によってNDBM、GDBM、SDB、TDB、Berkeley DBなどいろいろな改良版が作られている。私もいくつか作っていて、QDBM、TC、KCを経て、今回はなんと4作目である。今回の目標は以下の通り。

  • C++17準拠
  • スレッド並列性の向上
  • 堅牢性の向上
  • 仕様の単純化

まず第一に、今回は、C++17に準拠した実装にする。というか、C++17の新機能の使いこなしを練習する過程でこの作業が行われている。たまには標準ライブラリをバシバシ使わないと、使い方を忘れてしまうので。C++20の機能も使いたいところではあるが、ちょい古めの環境だとまだ使えないので我慢。UNIX-likeなシステムで動作することを前提とするが、I/O層の一部をすげ変えればWindows等の非POSIX環境にも移植できるようにしたい。バッファはchar*とsize_tで管理する代わりにstd::stringやstd::string_viewを積極的に使う。スレッドはstd::thread、排他制御はstd::mutexとstd::shared_timed_mutex、アトミック整数にはstd::atomic_intを使う。前回はそれらもPthreadベースのラッパークラスを自分で実装していて手間だったし、Windows版の作成がかなり大変だった。今回は低水準な領域はできるだけ省力化して、もっと高水準な領域を追求したい。

スレッド並列性も個人的に好きなトピックだ。データベース全体を対象とするreader-writerロックで管理するのは簡単だが、やりたくない。つまり読み込み操作を行うスレッド同士は同時に動作できるが、書き込み操作を行っているスレッドがあるとその他のスレッドはブロックされて待たされる仕様にはしない。KCの時からそうだが、書き込み操作のスレッド同士も同時に動作するように設計および実装する。そうすると実装が複雑化するのでシングルスレッドのスループットは下がるのだが、マルチスレッドのスループットは向上する。CPUのクロック周波数が頭打ちになった代わりにマルチコア技術が進展し、最近のカーネルだとスレッド生成コストも安くなり、さらにSSD等の登場でストレージの速度も上がってきた。クラウド時代といっても、ローカルマシンレベルの並列性も重要なのだ。DBMを使うとしたらそこがボトルネックにならないように配慮したいものだ。

堅牢性についてだが、今回は、インプレース更新と追記更新という二つのモードを用意することにした。既存のレコードを更新したり削除したりするにあたり、インプレース更新は、その既存のレコードの保存領域を書き換える。一方で追記更新では、新たなデータをファイルの末尾に追記する。インプレース更新は空間効率が良いが、データの更新中にプロセスが死ぬとデータが壊れる可能性がある。追記更新はデータを削除した時でさえファイルサイズが増えるという空間効率の悪さを持つが、データが壊れることは決してない。インプレース更新と追記更新のどちらが良いかはユースケースによる。今まではインプレース更新のみを実装してきたが、今回は追記更新もサポートし、その実用的な効率性がそこそこ高いということを示したい。

仕様は単純化する。機能が多いほどにメンテナンス性が下がるからだ。KCでは圧縮ストレージやら暗号ストレージやらトランザクションやらスナップショットやらの機能を追加していったが、今回はそういうのは省く。ただ、キーと値のペアが保存できるだけの単なるDBMを実装する。あと、KCで後悔したことの一つである、ハッシュテーブルと二分探索木を併用したデータ構造を改めて、ハッシュテーブルと線形連結リストに単純化する。ハッシュ値の衝突時に二分探索ができた方が最悪計算量の保証ができて良いと考えたのだが、それによって失うものが多すぎた。データ構造を単純化しつつ、テーブルロックをかけずにリハッシュできる仕組みを模索する方が良さげだ。

今までは自分でテストツールを実装していたが、今回はGoogle Testとかのテストスイートを使って効率化する。ファイルIO層、ブロックストレージ層、DBM層の三層で独立してテストできるようにするだろう。とりあえず動作環境はUNIX系（というかLinuxとMac OS X）だけに限定する。Win系でも将来的には動くといいけど、当面は気にしない。それより、AndroidやiOSでの動作を気にしたいところだ。

DBMのインターフェイスに合わせて複数の実装クラスを提供する。それぞれが異なるデータ構造とアルゴリズムであり、ユースケースによって使い分けることになる。

クラス名 記憶媒体 アルゴリズム 順序 時間計算量 並列性
HashDBM ファイル ハッシュテーブル なし O(1) レコード毎のRWロック
TreeDBM ファイル B+木 あり O(log N) ページ毎のRWロック
SkipDBM ファイル スキップリスト あり O(log N) 全体のRWロック
TinyDBM オンメモリ ハッシュテーブル なし O(1) レコード毎のRWロック
BabyDBM オンメモリ B+木 あり O(log N) ページ毎のRWロック

KCとの違いとしては、全体の性能や機能性や信頼性が上がっているべきことの他に、以下の点が挙げられる。

  • HashDBMで追記書き込みモードを実装する
  • HashDBMとTreeDBMの再構築をノンブロッキングにする
  • TreeDBMの並列性をテーブルロックからページロックに格上げする
  • HashDBMをオンメモリにしたTinyDBMを実装する
  • TreeDBMをオンメモリにしたBabyDBMを実装する
  • 順序アクセス対応でTreeDBMよりスケーラブルな実装として、スキップリストに基づくSkipDBMを実装する

こうして書き出してみると、なかなか大変そうな計画である。でも多分実現できるだろう。ほとんどの技術的課題は何度も経験しているものだからだ。世田谷公園をジョギングしつつ、設計も既に固めてある。頭の中でできてるってことは、あとは手を動かすだけだ。

余談。KCのメンテだが、雇用契約の関係でもう更新できないのが実情だ。いろいろ大人の事情があってね。今回はそうならないようにうまいこと進める所存。