アドカレを通して CMU Database Systems をひたすら追ってみて
この記事は「けんつの１人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar」 25 日目の記事です。
はじめに
以下の記事に触発されて CMU Database Systems を追っていって途中から DBMS の自作に切り替えてアドカレにしてみて、色々と思うところやどこまでできたのかをまとめられたらいいなと思う。
なにをやったか
CMU Database Systems を追った
DBMS について体系的に学習するために以下の講義を追った。
- 01 Relational Data Model
- 02 Advanced SQL
- 03,04 Database Storage
- 05 Buffer Pools
- 06 Hash Tables
- 07, 08 Tree Indexes
- 09 Index Concurrency Control
- 10 Query Processing
- 16 Concurrency Control Theory
- 17 Two-Phase Locking
- 19 Multi-Version Concurrency Control
- 20 Logging Schemes
- 21 Database Recovery
ほとんどが DBMS の中でも DB Storage に関する内容。
ところどころ抜けている部分は JOIN アルゴリズムだったり、内部的にクエリで得た検索結果をソートしたりといった内容で、後半で行った DBMS の実装に含めないことにした部分。
DBMS の実装の一部
Database Storage については実装を進めた。やってくるクエリを直列で捌くぐらいなら問題内程度の実装にはなっている。
そのあたりは 11 ~ 18 日あたりの雑な記事を参照するとわかりそう。
クエリのパーサ何かはこの後書くけど諸事情で断念したので、終盤のトランザクション周りとクエリあたりは実装できていない。
既存の実装を調べた
途中で、実際に MySQL, PostgreSQL ではどのように実装されているのかというところも諸々調べてみた。
rabbitfoot141.hatenablog.com
rabbitfoot141.hatenablog.com
rabbitfoot141.hatenablog.com
ストレージだけ実装した
前述の通り、トランザクションは実装できていないけどひとまずストレージだけは実装した。
構成要素としては以下の通り
- Catalog
- Tuple
- Page
- Buffer Pool
- B Tree Index
- Clock Sweep Cache
- LRU Cache
- Disk Manager
Page, Tuple は Protocol Buffer を使わず、 gob も使わず自前で byte 列にシリアライズしている。
Buffer Pool 周りは PostgreSQL 8*1を参考に実装している。
ひとまず、ページに対してタプル*2の追加はできるし、テーブルという単位でそれらを管理することもできる
あとは B Tree では int32 相当の値と string の検索に対応することもできた。
やってみて
辛さ半分、楽しさ半分
辛いところ
最初にあげた記事にもあるようにコンピュータ・サイエンスの基本的な知識が要求されるため、現役学部生といえど情報工学を専攻している身には新しく学ぶことになる前提知識が多くてかなり大変だった。
この一連の流れを通して学習することが、CS の基本知識 + DBMS の理論についてなのでかなり盛りだくさんだったのは言うまでもなく苦労の連続だった。
そして最も厳しかったのは B Tree や Buffer Pool の実装で、これはデータ構造とアルゴリズムの実装が連続するため知識としてもっていても
またそれらを実装できるのは全く別の話なのでかなり時間を食ってしまったし、わかるとできるを結びつけるのを締め切りに迫られながらやるのはかなりメンタルに来るものがある。
楽しかったところ
まず、DBMS に関して体系的に学べたのは新しい発見の連続でこれはかなりワクワクする内容だった。特にストレージ周りは新しく学ぶことばかりで、日々の勉強が楽しかった。このワクワク、なかなか伝わりにくいとは思うが新しく学んだことを試行錯誤しながら実装するのはめちゃくちゃ楽しい。
以前、 Linux Kernel モジュールを書いていたことがあるのだけど講義内で出てくる仮想記憶や mmap などのシステムコールについても解説があり
自分のなかで断片として持っていた知識が「あぁ実際にはこういう実装に使えるのか。それでこの DBMS はこういう実装になっているのか」とつながっていく感覚もさらに実装の幅が広がったのもワクワクの連続だった。
また、既存の DBMS についての実装もかなり追ったので MySQL*3 の binlog, LRU Cache や PostgreSQL の BufferPool に関連する本来ブラックボックスのようになっているものの裏側をきちんと理解することが出来てので当初の目的通り最低限そういった知見が得られたのは非常に良かったと思う。
Golang 力があがった
これは sansan の荒川さんのレポジトリを参考にして作っていたというのが関係している。
github.com
例えば、Slice と Array の使い方だったり、 B Tree のような構造の実装であったりとすごく得るものがあった。
B Tree で Node がもつ Item で Interface を使っていたが、interface の使い方で普段は迷うことが多いのですごく参考になった。
また実装に入った段階で出来るだけ異なるアプローチや仕組みを実装しようと思っていたので、常に試行錯誤の連続も何度も書いて消してを繰り返したので必然的に Golang 力があがった。
あとは Goroutine 周り。あまりヘビーな使い方をしたことがなかったが、ラッチ相当の機能を実装するために sync.RWMutex なんかを多用したため、そのあたりの排他制御に関する知見と実装方法にたいする理解も深まった。
既存の実装への理解が深まった
楽しかったところにもあったが、これもひとつ大きな副次的効果だと思う。めちゃくちゃ調べて
こういった Page の物理的構成に関する記事を見て参考にしたり
http://www.interdb.jp/pg/pgsql08.html
こういったものも参考にしたので、自然と既存の実装について理解がかなり深まった。
MySQL のドキュメントもかなり参照した。
反省点
SQL に対する理解と見通しが甘かった
今回はこれに尽きる。
後々、JOIN やサブクエリ等の実装もしたかったので、再帰降下構文解析でなく goyacc で実装しようとは最初から思っていたのだが
簡単に出来ると思っていて*4、ストレージの実装にかなりの時間を使ったのだが実際やってみると B Tree や Buffer Pool の実装の比にならないほど難航した。
そのため、その後に控えていたトランザクションの実装をする時間がなくなってしまったという事態になってしまった。
めちゃくちゃ見通しが甘かった。
CS の基礎が不足している
これも想像以上に時間がかかった理由になっている。
本来 DBMS の理論の学習に時間を割くべきだが、そこで前提とされている CS に関する基礎知識が不足していたためにところどころで遅れを招いた。
これは普段から、如何にライブラリ何かがいい感じにしてくれるバックグラウンドにあるものを理解できていないかというところが露呈したと思っている。
どうにかそのあたりも勉強しないといけないと痛感した。
