はじめに
仕事の合間を縫って「C言語でSQLiteクローンを作る」チュートリアルをやってみました。
これはタイトルの通り、単純なREPLからSQLiteの設計を参考に、簡単なSQLが実行可能なデータベースエンジンを実装するチュートリアルです。
経験年数(だけ)は駆け出しエンジニアとは言いづらくなってきたとき、私の開発経験においてブラックボックスになりがちなデータベースの基本的な構造について少しでも触れたいと考えやってみました。
22年9月現在、チュートリアルはB treeの実装途中で終わっており、全体は未完成となっていますが多くの事項について知見を学べるので記事に残します。
環境について
リポジトリをフォークしDocker化しました。
またRuby 3系でRSpecが動かなかったので、既存のGemfile.lockを削除しbundle installしなおしています。
後半では章ごとのdb.cの差分が省略されているため、/prac/dbs配下に章ごとのdb_part[章番号].cが格納されています。
これでgccとbundle exec rspecの実行ができるようになり、実装の準備が整いました。
実装
それでは章ごとの概要と気づきに入ります。
Part 1 - Introduction and Setting up the REPL
SQliteのアーキテクチャや基本的な用語の説明に始まり、超単純なREPLを実装します。
業務ではC言語でREPLを実装したことがないので普通に学びが多いです。
Part 2 - World's Simplest SQL Compiler and Virtual Machine
入力されたSQLを解析する世界で最もシンプルなSQLコンパイラを実装します。
この時点では.exitとselectの2 wordsしか認識しません。
Part 3 - An In-Memory, Append-Only, Single-Table Database
いよいよinsert文を実装します。
メモリ上にデータを出し入れする関数も実装します。
ちなみにインメモリなのでプログラムを終了したらデータは消えます。
C言語でテーブルやその行をどう表現するか試行錯誤しており、我々も楽しい気分になってきましたね。
~ ./db
db > insert 1 cstack foo@bar.com
Executed.
db > insert 2 bob bob@example.com
Executed.
db > select
(1, cstack, foo@bar.com)
(2, bob, bob@example.com)
Executed.
Part 4 - Our First Tests (and Bugs)
RubyのテストFWであるRSpecでテストを書きます。
業務ではJestを書いてるので、特に苦もなく読めました。
RSpecを使えばCLIツールのE2Eテストが簡単に実行できそうです。
describe 'database' do
def run_script(commands)
raw_output = nil
IO.popen("./db", "r+") do |pipe|
commands.each do |command|
pipe.puts command
end
pipe.close_write
# Read entire output
raw_output = pipe.gets(nil)
end
raw_output.split("\n")
end
null終端文字の対応等、いろんなバグが発生するので、これを直していきます。
Part 5 - Persistence to Disk
いよいよデータを永続化します。
キャッシュ機構や、ページフォールトを実装します。
ここでは実データが保存されたファイルを以下のvimのbinaryモードで眺めてみます。
cstackの文字コードは16進数表記で63737461636bです。
ファイル上にちゃんと保存されていますね。
Part 6 - The Cursor Abstraction
B treeを用いた実装にする前に、カーソルに関する操作のIFを定義します。
Part 7 - Introduction to the B-Tree
B treeに関する説明のパートです。B+ treeや内部ノード、葉ノードに関しての説明があります。
ここから若干難解 & 地道な実装に入っていきます。
永続化する機構は今までのパートで完成したので、時間がない方はここでやめておいてもいいかもしれません。
Part 8 - B-Tree Leaf Node Format
いよいよB treeの構造をコードで表現していきます。
木構造を採用することによるメリットやデメリット、B treeをバイト列で表現した際にどんなフォーマットになるのか等の説明があります。
ここからのパートは私がざっくりとした理解にとどまっています。。。
間違い含む場合があるので見つけたらそっと教えてください。
Part 9 - Binary Search and Duplicate Keys
葉ノードの2分探索を実装し、ソートされた順序でデータを保存可能にします。
またキーの重複チェックも実装します。
Part 10 - Splitting a Leaf Node
先ほどのパートでは一つの葉ノードに全データを保存していました。
ここでは葉ノードを分割する処理を実装します。
その際には根ノードも更新する必要があります。
※地道な実装が続きます、、、
Part 11 - Recursively Searching the B-Tree
B treeの再帰的な検索機能を実装し、より多くのデータをストアできるようにします。
またあるテストケースが失敗したときも後続のテストが実行されるようにテストをリファクタします。
raw_output = nil
IO.popen("./db test.db", "r+") do |pipe|
commands.each do |command|
- pipe.puts command
+ begin
+ pipe.puts command
+ rescue Errno::EPIPE
+ break
+ end
end
pipe.close_write
Part 12 - Scanning a Multi-Level B-Tree
バグが出ているので複数の葉ノードに保存されたデータをselectできるように実装を変更します。
こっから若干バグ修正に追われてきます。
このパートを実装してもRSpecのテストは落ちたままです。
Part 13 - Updating Parent Node After a Split
葉ノードの分割後に行う親ノードの更新処理を実装します。
ちなみにここではinsertしたデータがどのような木構造にマップされているかを見ることができます。
db > Tree:
- internal (size 3)
- leaf (size 7)
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- key 7
- leaf (size 8)
- 8
- 9
...
学習時のポイント
C言語読めないとき
Cは大学の授業で触りをやっただけなので、アドレス演算子&と間接演算子*周り含め処理が読めない場合も多かったです。
そのため、苦しんで覚えるC言語等のサイトで復習しました。
バイナリファイルの読み書きに関しても言及があるので参考にしてみると良いかもしれません。
英語読めないとき
DeepL Proを契約してページごと変換しました。
非常に自然な日本語訳が出力されます。
しかし、コードブロックがレイアウト崩れを起こすので、Google翻訳の拡張機能で代用してもいいかもしれません。
バイナリデータの読み方
蛇足ですが、バイナリを読むときはvimのバイナリモードを使えます。
$ vim -b mydb.db
00000000: 0100 0000 6373 7461 636b 0000 b0a5 8ca4 ....cstack......
00000010: ffff 0000 5807 8ca4 ffff 0000 0000 0000 ....X...........
00000020: 0000 0000 6066 6f6f 4062 6172 2e63 6f6d ....`foo@bar.com
...
:%!xxd # エディタを開いた後に入力
終わりに
ここまででそれなりにデータベースっぽいものが実装できたと思います。
アルゴリズムやデータ構造に関しては,普段の開発でスクラッチ実装することがあまりないので自分の弱みが露呈した形となりました、、、
というわけでみんなもLet's Build a Simple Databaseやっていきやしょう。
参考