DBMS をフルスクラッチで作る Database Design and Implementation: Second Edition1 を読みながら、この本で作る DBMS(SimpleDB) を Go で実装しました。始めてからちょうど5ヶ月くらいかかりました。
去年も DBMS を自作していましたが、当時は DBMS の理論を学ばずに「この SQL が投げられたときにこういう結果を返すにはこういう実装にすればとりあえずそれっぽい動きをしてくれそう」という感じに実装していて理論的なところは何も学んでいませんでしたが、今回はちゃんと本に沿って実装したので理論・実装を体系だって学べました。
私はこの本を Riki Otaki さんの「自作DBMSとおすすめ書籍2」という記事で知りました。
自作コンパイラ、自作 OS に関する書籍は数多あれど自作 DBMS の本も存在していたのか!いつかやりたいなぁと思いつつ当時はペーパーバック版が6000~7000円くらいしたのでとりあえず欲しい物リストに入れるだけで放置していました。Springer の本は為替とか関係なく急に高くなったり安くなったりしますが、あるとき3600円弱まで下がったのでそのタイミングで買いました。
元実装は Java ですが、私は Java の書き方をよく知らないので Go で実装しました。やる前は class のない Go で書きなおすのは結構辛いかもしれないと思っていましたが、元実装では継承などをあまり使っていなかったので Go に書き直すのでも特別難しいという感じはしませんでした。
元実装と変えたところとして11章でやる JDBC の実装は行わず、代わりに Go の標準ライブラリである database/sql と PostgreSQL wire protocol に対応しました。 自作 DBMS に使いやすい CLI mode を実装するのは結構大変なのでそちらに注力したくない場合は PostgreSQL や MySQL などのメジャーな DBMS のプロトコルに乗っかるとすでにあるものを使い回せるのでおすすめです。ただし MySQL のプロトコルはパケットの構造が複雑で parse するの面倒なので個人的には PostgreSQL のプロトコルのほうがおすすめです。10種類くらいのパケット構造が理解できればとりあえず psql とは通信できます。
この本の良いところ
標準ライブラリのみで実装されている
サードパーティ製のライブラリを使ったほうが実装が楽になる部分はおそらくたくさんあった(parser とか)と思いますが、それらを使うと動く仕組みがブラックボックス化して理解できた気になれないので、自作〇〇をするときは極力標準ライブラリのみで実装したいというのが私の趣味なのですが、この本の実装は標準ライブラリのみで実装されているので曖昧なところが出ずに実装できたのはよかったです。
フルスクラッチ実装
大学の講義の課題で作る DBMS だとある程度型が出来上がっているところに足りないパーツを実装するといった穴埋め方式がよくあると思います。穴埋め方式の利点として重点を置きたい場所に集中できるという点がありますが、逆に自分で作っていない部分はブラックボックスに感じてしまいます。自分で実装していない部分も読めばいいかもしれませんが、それらのコードは講義のレベルを超えるから学生には実装させなかったりしているので読んで理解するというのもなかなか骨の折れる作業です。この本は穴埋め方式でなくフルスクラッチ方式だったのでこのパーツは一体何をしているのか?という疑問を持たずに進めることができました。
この本の辛いところ
元実装のコードが読みづらい
マジックナンバーが出てきたり、副作用のある method が多くコードだけを読んでいると結構辛いなというところが多々ありました。package が循環参照している箇所もあり、全体的な構成としてわかりづらさを感じました。
この本を進めている途中で UC Berkeley CS186 の課題の RookieDB という DB の存在を知りましたがこちらのほうが読みやすく、アーキテクチャも良さそうに見えました(隣の芝生が青く見えただけかもしれません)
RookieDB の Lock manager
12章以降写経だけでは作ったものが動かない
内容が理解できずともとりあえず写経すれば動いていた11章までとは打って変わって、12章以降は本に載っている実装を写経するだけではパーツが結合されない部分が出てきます。
12章では index を実装しますが、UPDATE
, INSERT
, DELETE
のときに index に更新をかける処理は入る一方、SELECT
のときに index を使うようにする修正は入らないのでこの時点で index を使った SELECT
に対応させたい場合は自分で実装する必要があります。幸い15章の実装で index を使った SELECT
ができるようになりますが、一方でその実装だとそれまで使えていた view が使えなくなります。
13章では集約関数や GROUP BY
に対応するためのコードを書きますが、これだけでは動かなくて自力で Lexer, Parser に修正を加える必要があります。こちらは index のときと違い後半の章が終わっても結合されません。
14章も書いただけでは結合されず、15章の実装をすると結合されます。
一応15章までたどり着くと13章を除き色々解決されますが、12章はじめから15章終わりまでには140ページ近くあるので、そこまでモチベを落とさないようにするのはなかなか大変だなぁと思い、私は合間合間で独自修正を入れました。
おわりに
以前、自作 DBMS 界隈では有名な CMU の講義動画 を見て、講義の課題である DBMS 実装をやろうと思ったものの講義の序盤の方で早々に挫折した経験がありますが、この本は無事に終わらせることができました。私同様 CMU の講義が難しいと感じた方はこの本で勉強してみると良いかもしれません。
-
第2版は2020年出版ですが、「現在主流の HDD の容量は 40 GB」みたいなことが書かれていて第1版と変わっているのかな?と思うところはありました。↩
-
現在はブログは閉じられてしまったようです。Internet Archive では閲覧可(2022/8/7)↩