valid,invalid

関心を持てる事柄について

C言語でSQLiteのクローンを作るチュートリアルやった

Database SQLite Clang

2019年12月の冬休みに1週間程かけて"Let's Build a Simple Database"という、C言語でSQLiteのクローンを作るチュートリアルをやりました。この存在を教えてくれた同僚に感謝 :pray:

cstack.github.io

チュートリアルの内容

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の構造を実装してみることで具体的な探索処理などがイメージできるようになりました。

チュートリアルでは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

f:id:ohbarye:20200417161306p:plain
insertしたデータがちゃんと入っていることや、想定したレイアウト担っていることが一応確認できる

パイプを使った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やデータベースの知識がつくと以下のような実践的記事や実製品の解説が力強く読めるようになりました。

また、まだ実践していないのですが次のステップとしていくつか良さそうな教材があるのでメモしておきます。

*1:正確にはインデックスにはB-Tree、テーブルにはB+ Treeが使われている