C言語でSQLiteクローンを実装するチュートリアルやってみた

# はじめに

仕事の合間を縫って「C言語でSQLiteクローンを作る」チュートリアルをやってみました。

https://cstack.github.io/db_tutorial/

これはタイトルの通り、単純なREPLから[SQLiteの設計](https://www.sqlite.org/arch.html)を参考に、簡単なSQLが実行可能なデータベースエンジンを実装するチュートリアルです。

経験年数(だけ)は駆け出しエンジニアとは言いづらくなってきたとき、私の開発経験において**ブラックボックスになりがちなデータベースの基本的な構造について少しでも触れたい**と考えやってみました。

:::note warn
22年9月現在、チュートリアルはB treeの実装途中で終わっており、全体は未完成となっていますが多くの事項について知見を学べるので記事に残します。
:::

# 環境について

リポジトリをフォークしDocker化しました。

https://github.com/yasuaki640/db_tutorial_study_record

またRuby 3系で[RSpec](https://rspec.info/)が動かなかったので、既存の`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言語でテーブルやその行をどう表現するか試行錯誤しており、我々も楽しい気分になってきましたね。

```shell
~ ./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テストが簡単に実行できそうです。

```ruby
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モードで眺めてみます。

![](https://cstack.github.io/db_tutorial/assets/images/file-format.png)

`cstack`の文字コードは16進数表記で`63737461636b`です。
ファイル上にちゃんと保存されていますね。

## Part 6 - The Cursor Abstraction

B treeを用いた実装にする前に、[カーソル](https://ja.wikipedia.org/wiki/%E3%82%AB%E3%83%BC%E3%82%BD%E3%83%AB_(%E3%83%87%E3%83%BC%E3%82%BF%E3%83%99%E3%83%BC%E3%82%B9))に関する操作のIFを定義します。

## Part 7 - Introduction to the B-Tree

B treeに関する説明のパートです。B+ treeや内部ノード、葉ノードに関しての説明があります。

:::note info
ここから若干難解 & 地道な実装に入っていきます。
永続化する機構は今までのパートで完成したので、時間がない方はここでやめておいてもいいかもしれません。
:::

## Part 8 - B-Tree Leaf Node Format

いよいよB treeの構造をコードで表現していきます。
木構造を採用することによるメリットやデメリット、B treeをバイト列で表現した際にどんなフォーマットになるのか等の説明があります。

:::note warn
ここからのパートは私がざっくりとした理解にとどまっています。。。
間違い含む場合があるので見つけたらそっと教えてください。
:::

## Part 9 - Binary Search and Duplicate Keys

葉ノードの2分探索を実装し、ソートされた順序でデータを保存可能にします。
またキーの重複チェックも実装します。

## Part 10 - Splitting a Leaf Node

先ほどのパートでは一つの葉ノードに全データを保存していました。
ここでは葉ノードを分割する処理を実装します。
その際には根ノードも更新する必要があります。
※地道な実装が続きます、、、

![](https://cstack.github.io/db_tutorial/assets/images/btree3.png)

## Part 11 - Recursively Searching the B-Tree

B treeの再帰的な検索機能を実装し、より多くのデータをストアできるようにします。
またあるテストケースが失敗したときも後続のテストが実行されるようにテストをリファクタします。

```diff
     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できるように実装を変更します。
こっから若干バグ修正に追われてきます。

:::note warn
このパートを実装してもRSpecのテストは落ちたままです。
:::

## Part 13 - Updating Parent Node After a Split

葉ノードの分割後に行う親ノードの更新処理を実装します。
ちなみにここではinsertしたデータがどのような木構造にマップされているかを見ることができます。

```shell
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言語](https://9cguide.appspot.com/)等のサイトで復習しました。
[バイナリファイルの読み書き](https://9cguide.appspot.com/17-02.html)に関しても言及があるので参考にしてみると良いかもしれません。

## 英語読めないとき

[DeepL Pro](https://www.deepl.com/ja/pro)を契約してページごと変換しました。
非常に自然な日本語訳が出力されます。
しかし、コードブロックがレイアウト崩れを起こすので、[Google翻訳の拡張機能](https://chrome.google.com/webstore/detail/google-translate/aapbdbdomjkkjkaonfhkkikfgjllcleb?hl=ja)で代用してもいいかもしれません。

## バイナリデータの読み方

蛇足ですが、バイナリを読むときはvimのバイナリモードを使えます。

```shell
$ 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](https://cstack.github.io/db_tutorial/)やっていきやしょう。


# 参考

https://ohbarye.hatenablog.jp/entry/2020/04/17/sqlite-clone-db-tutorial

https://www.bohyoh.com/Books/NewMeikaiJavaAlgorithm/index.html

https://www.shoeisha.co.jp/book/detail/9784798124704