RDBMSをGoで自作した
普段業務で色々なデータベースを触っていると、こいつの中身はどうなっているんだろうと気になることがあります。そんなわけでDatabase Design and Implementation: Second Editionという書籍をもとに、Go言語でRDBMSを自作しました。本書はJavaで書かれていますが、そのまま写経するのは面白くないのでGoでリライトしています。
出来上がったもの:
CREATE TABLE / INDEX / VIEW、SELECT、INSERT、UPDATE、DELETEといった基本的なSQLが実行できます。書籍では終盤GROUP BYやクエリ最適化をする章がありますが、まだ手を付けておらずインデックスまでの実装となっています。
なおAIコーディングエージェント全盛期ですが、この実装は学習目的なのでAIの利用は控えめにしました（テストとかでは使った）。
実装の流れ
本書は基本的にボトムアップで進みます。低レイヤから一つずつ積み上げていく構成です。
chapter 1~3
まずデータベースやディスクといった概念の説明から始まり、DBのデータをブロック単位で読み書きするファイルマネージャの実装に入ります。ページ内の指定オフセットに数値や文字列を書き込んだりするプリミティブなところから実装していきます。TCPを実装した時も思ったのですが、こういうバッファにバイナリ詰めてる時がゼロから自作している感があって好きだったりします。
chapter 4
バッファマネージャとログマネージャを実装します。バッファマネージャはディスクアクセスを減らすためのバッファプールを管理するもので、ログマネージャは操作履歴を記録するものです。ログマネージャは特に次の章のトランザクションと密接に関わってきます。
バッファマネージャの実装を通して、DBMSが如何にしてディスクIOを回避し、メモリ上のバッファプール内で処理を完結させているかを垣間見ることができます。PinやUnpinの処理をLRUにしたりと工夫の余地も大きいところですね。またバッファサイズとページサイズの調整はパフォーマンスチューニングでもよく見る重要項目ですが、どのパラメータを調整しているのか、実装を通してよりイメージがつくようになりました。
chapter 5
トランザクションの実装で、一気にDBMS感が増して面白くなる章です。トランザクションごとの操作の分離、コミット、ロールバック、リカバリの仕組みが詳細に理解できます。読み進めるうちにWAL(Write Ahead Log)が偉大すぎることを改めて実感する章でもあります。ここから実装が一気に複雑になるので、それまでの実装のテストをしっかり書いてバグを潰しておかないと詰むかもしれません。特に非同期処理やロックが絡む部分はそうで、JavaからGoへの移植で一番差が出ることもありテストの重要性は高かったです。この辺りのテストでは最近（でもない？）追加されたGoのsynctestパッケージが役に立ちました。
chapter 6
ブロック内にどうやってレコードを配置するかを考え、レコードマネージャを実装します。SimpleDBは固定長レコードで実装しており、テーブルスキーマ作成時にレコードサイズが決まります。その後のレコード更新で伸びたりしません。実装はシンプルですが、ブロック内に使われない領域ができたり、そもそも文字列を確保分以上は伸ばせなくなるという制約を受けます。
可変長レコードの実装も解説されますが、実装は格段に複雑になります。ページ内のレコード境界が静的に決定できなくなる上、レコードサイズが大きくなった際にページから溢れたり他のレコードを押し出したりする可能性が出てくるからです。移動が発生すれば元の場所を指しているインデックスの更新も必要になることがあるため、変更の影響範囲も大きくなります。商用のDBのほとんどが可変長レコードを採用しているようです。
chapter 7
テーブルスキーマやメモリレイアウトなどを管理するメタデータマネージャを作ります。テーブルやビューの作成ができるようになります。
chapter 8~10
SQLのパーサ、クエリプロセッサ、プランナーを実装します。パーサは単純な再帰下降パーサです。ここまでできればSQLを実行してデータを操作できるようになり、実質RDBMSと呼べるものになります。クエリプロセッサ内のスキャナーは、基本的に先頭から順番にデータを見ていき、WHEREなどで条件があれば評価しつつデータを返していくという単純なものになっています。Nested Loopによる単純なJOINも実装します。
chapter 12
Hash indexとB-Tree indexを実装します。B-Treeは普段DBを扱う人にとっては馴染み深いかと思います。実装は難しいながらも洗練されており、ソートされたノードリストを持つツリーが分割されながら成長していく様子をイメージするのがポイントになります。また前章で作成したプランナーにうまく組み込み、データの取得と挿入時にインデックスが使われるようにする必要もあります。
chapter 13~
未着手ですが、ここを進めるとGROUP BYやORDER BYができたり、クエリが高速化したりするようです。ここは今後おいおいやっていきます。
感想
非常に楽しめましたし学びになりました。最近改めて「詳説データベース」を読み返しているのですが、やはり実装が頭にあると理解度が段違いになります。最初に読んだときはWALやインデックスの説明でふーんそんなもんかと流していた箇所が、自作を経験した後だと鮮明にイメージできるようになりました。また商用DBを扱うときも、パラメータの意味に想いを馳せたりできます。
本記事で紹介したDatabase Design and Implementation: Second Editionですが、DB自作初心者に非常におすすめです。コアとなるロジックの説明がとにかく丁寧で、置いていかれることがありません。一方でコードを読む際は多少のエスパー力が求められる場面もあったりしますが、普段コードを書く人なら問題ないと思います。困ったらAIもありますからね。
DB周りを深掘りしていきたい欲が増したので、今後は作ったsimpledb-goをclient-server構成にしたり、分散データベースにしてみたりと、色々試してみたいところです。
