2019年12月の冬休みに1週間程かけて"Let's Build a Simple Database"という、C言語でSQLiteのクローンを作るチュートリアルをやりました。この存在を教えてくれた同僚に感謝 :pray:
チュートリアルの内容
Richard Feynman先生の“What I cannot create, I do not understand.”という言葉が掲げられているように、データベースを作ることでデータベースをより深く理解することに主眼が置かれているチュートリアルです。
これは重要事項説明かつタイトル詐欺に関する謝罪なのですが… 残念ながらこのチュートリアルは完成しておらず、Part 13が2017-11-26に公開されたのを最後に更新が止まってしまっており、以下の13章しかありません。
- Part 1 - Introduction and Setting up the REPL
- Part 2 - World’s Simplest SQL Compiler and Virtual Machine
- Part 3 - An In-Memory, Append-Only, Single-Table Database
- Part 4 - Our First Tests (and Bugs)
- Part 5 - Persistence to Disk
- Part 6 - The Cursor Abstraction
- Part 7 - Introduction to the B-Tree
- Part 8 - B-Tree Leaf Node Format
- Part 9 - Binary Search and Duplicate Keys
- Part 10 - Splitting a Leaf Node
- Part 11 - Recursively Searching the B-Tree
- Part 12 - Scanning a Multi-Level B-Tree
- Part 13 - Updating Parent Node After a Split
なのでデータベースに関して網羅的に学べるわけではなく、内容は以下に限られます。SQLiteのクローンも完成しません…。
- ちょっとしたREPLの作り方
- In memoryでのデータ保存とディスクへの永続化
- page, pager, cursorといった抽象化
- B Tree (B+ Tree) がなぜデータベースのテーブルやインデックスに使われるのかの説明とその実装
とはいえ、データベースの内部実装でもとりわけ重要なB Tree周りの解説とハンズオンに大部分が割かれているのでB Treeを理解りたい人や、なんとなく理解った気持ちでいるけど実際にテーブルをB Treeで実装してみて深く知りたい人におすすめです。(ただ、チュートリアルの後半のNodeの分割や木の更新に関わる処理は地道な実装が多くてけっこう辛めでした)
また、スクラッチで巨大なアプリケーションを書くときに「小さく作る」「常に動く状態を保つ」といったプラクティスが実践されているのも良い点です。
登場するコードの全体像はすべてGitHubで確認できるのでC言語を書けなくても写経しながら読んでいけばだいたいなんとかなります。また、実装に対するE2EテストはRubyのRSpecで書かれています。
学んだこと
実施している最中のメモはこちら: Let's Build a Simple Database - ohbarye
B Tree (B+ Tree) がなぜデータベースのテーブルやインデックスに使われるのか
検索すれば以下のような先人の良い記事がたくさん見つかるのですが、B Tree自体の理解が浅かったときに読んでもいまいちピンと来ていませんでした。チュートリアルを通して手を動かしてB Treeの構造を実装してみることで具体的な探索処理などがイメージできるようになりました。
- 第7回 性能改善の鍵,インデックスの特性を知る~B-treeとハッシュ (1)B-tree :SQLアタマアカデミー|gihyo.jp … 技術評論社
- B TreeとB+ Treeの違い - Carpe Diem
- なぜBTreeがIndexに使われているのか - maru source
チュートリアルではB+ Treeを導入する際に高速な検索・削除・挿入といったメリットだけでなく、B+ TreeのNodeとして持つべき内部データ・メタデータなどのオーバーヘッドでfile sizeが肥大化するデメリットも併せて説明しています。
「SQLiteではB-Treeがテーブルとインデックスの両方に用いられている*1」という"知識"を持っていても、「なぜ他の選択肢、たとえば要素の参照・追加・削除がすべて平均的にはO(1)で行なえるハッシュテーブルではいけないのか」「どのようなトレードオフがあるのか」を説明できる程度までは"理解"していなかったことが浮き彫りになりました。
メモリレイアウトの工夫
ふだん高級言語でWebアプリケーションを書いているとあまり気にされないレベルのメモリの使い方について。
たとえば、ページサイズを4096 bytesにする。この数字はほとんどのコンピューターアーキテクチャの仮想メモリシステムで使用されるページと同じサイズであり、これらが同じおかげで余計な分割処理を行うことなくメモリに出し入れできる。他にもチュートリアルの簡便さのためにページ上限を決めたり、ページを超えて行を保存することを禁止することでページをまたいでのread / writeを避けたりしてるのですが、それがなぜかということも解説されています(ページをまたぐとメモリアドレスが隣接しない可能性が高いので大変になる)。
他にも、pagerにpage number Xを要求する => メモリに乗っているキャッシュから読むことを試みる => キャッシュミスが発生する => データベースファイルを読み取ることでデータをディスクからメモリにコピーする
のようなフォールバック処理を書くことで、「あ〜、こういうときに処理が低速になるのか」と体感できたりします。
こうしたローレベルの工夫によりデータベース製品は性能や品質を実現しているという理解が得られました。
Vimをhex editorとして使う
作成するデータベースは終了時にfileにデータをdumpします。dumpされたデータファイルはただのバイナリファイルなので以下のようにして中を覗くことができます。
$ vim -b test.db :%!xxd
パイプを使ったREPLのテスト
これも本筋ではないのですがREPLのテストをパイプを使っているのを初めて見たので学びがありました。
def run_script(commands) raw_output = nil IO.popen("./db test.db", "r+") do |pipe| # REPLを起動し、そのプロセスに繋がるpipeが得られる commands.each do |command| begin pipe.puts command # pipe越しにinsertとかselectのSQL commandを流し込む rescue Errno::EPIPE break end end pipe.close_write raw_output = pipe.gets(nil) # REPLプロセスの出力 (文字列) を得る end raw_output.split("\n") end it 'inserts and retrieves a row' do result = run_script([ "insert 1 user1 person1@example.com", "select", ".exit", ]) expect(result).to match_array([ "db > Executed.", "db > (1, user1, person1@example.com)", "Executed.", "db > ", ]) end
さらなる課題
B Treeやデータベースの知識がつくと以下のような実践的記事や実製品の解説が力強く読めるようになりました。
- MySQL with InnoDB のインデックスの基礎知識とありがちな間違い - クックパッド開発者ブログ
- DBMSをGoで実装してみた - Sansan Builders Box
- InnoDBの実装について
また、まだ実践していないのですが次のステップとしていくつか良さそうな教材があるのでメモしておきます。
- カーネギーメロン大学の講義
- 個人が無償で公開している教材も良いが、きちんと広く深く学んでいくためには大学が公開しているコンテンツのほうが良さそう
- Database basics: writing a SQL database from scratch in Go | notes.eatonphil.com
*1:正確にはインデックスにはB-Tree、テーブルにはB+ Treeが使われている