kawasin73のブログ

技術記事とかいろんなことをかくブログです

Rust で SQLite を再実装している

Rust 作ったもの Database

セキュリティを盾に一点突破。どうもかわしんです。最近 Rust で SQLite を実装してます。

以前の記事で HTTP Parser を Rust で実装しようとしたものの、すでに実装されていたので断念しましたが、いい題材を見つけました。SQLite です。開発中のリポジトリはこれです。

github.com

今の時点では、Read Only で1つの WHERE 句を持った SELECT 文しか処理できないですが、以下の機能を実装しています。

  • sqlite3 で生成された database ファイルの読み取り (cursor.rs, btree.rs, record.rs)
  • SQL 文の解析 (token.rs, parser.rs)
  • テーブルとインデックスのメタデータのパース (schema.rs)
  • 動的なファイルの読み込み (pager.rs)
  • SQL クエリとスキーマ情報を元に必要なインデックスを使ってデータの読み出し (lib.rs)

それぞれの機能はまだシンプルで最適化はされていないですし、CREATE TABLE や INSERT などの書き込み処理にも対応していかないといけないので先は長いです。

なぜ Rust で SQLite を実装するのか

元々データベースかサーバーを作ってみたいなという興味があったのと仕事で Rust を使っていていい言語だなと思ったのがきっかけです。

C 言語で書かれたソフトウェアを Rust で書き直すことには、特に Rust という言語を使うこと自体に優位性があります。

Chromium の The Rule Of 2 では以下のうちの全てを満たすと危険で、２つ以下だけであれば安全という風に解釈されます。

  • Untrustworthy Inputs
  • Unsafe Implementation Languages
  • High Privilege

source

この3つのうちの一角を占める "Unsafe Implementation Languages" は Rust を使うことで解決します。つまり、C ではなく Rust を使うだけで安全なプログラムと解釈されやすくなります。

それだけ Rust で書くということには大きなインパクトがあると思っています。

強すぎる SQLite

すでに広く使われているソフトウェアを再開発するのは仕様が出来上がっているので実装に集中でき、頭を使わなくていいので楽です。さらに、リファレンス実装も公開されているので細かいロジックの予習・復習が簡単です。大まかな設計も参考にできます。

その中で、なるべくシンプルで簡単なものを作りたいなと思って思いついたのが SQLite でした。

SQLite は SQL をインターフェースにした埋め込みデータベースで、ライブラリ関数呼び出しから直接データベースを操作します。他の RDBMS に比べてシンプルそうだったので作ってみることにしました。

また、"Rust sqlite" などで Github や crates.io を調べた限り見つかったのは C の実装ライブラリの binding だけで Rust での pure な実装はなかったので一番乗りする形で実装することにしました。（Let's Build a Simple Database という SQLite based を謳うチュートリアルを元にした mini-db がありましたが、どちらも SQLite file format とは関係なかったのでノーカンです）

SQLite はドキュメントがとても充実しており、実装するときに大いに参考になります。SQL Syntax や File Format など全ての仕様がドキュメントにまとめられており、またとても読みやすいです。逆にそのドキュメントの充実具合は恐ろしさの始まりでもあります。

www.sqlite.org

SQLite のドキュメントを読み始めるとまず１行目で驚愕の事実を突きつけられます。

SQLite is a C-language library that implements a small, fast, self-contained, high-reliability, full-featured, SQL database engine.

今リンク先を見たら内容が変わっていましたが、僕が読んだ 2 月時点の web archive をみると初っ端から LLVM が GCC に負けます。

The Clang/LLVM compiler is not competitive with GCC. Clang-generated binaries are consistently larger and slower than GCC-generated binaries.

Rust は LLVM ベースなのでもう負けです。勝てません。GCC の方が LLVM よりもバイナリサイズも小さいし速いらしいです。

SQLite is built using a DO-178B-inspired process.

リンク先の DO-178B の Wikipedia を読むと

DO-178B, Software Considerations in Airborne Systems and Equipment Certification is a guideline dealing with the safety of safety-critical software used in certain airborne systems.

航空機業界で使われる安全性を担保するための開発方法のガイドラインらしいです。なんだそれ、こちとら個人開発プロジェクトだぞ。勝てないじゃん。

というわけで、ここまでガチガチに開発されてカリッカリにチューニングされたソフトウェアに勝てるわけがないので、SQLite を再開発しようという人がいないのかなと思いました。が、僕は Rust を使うことよるセキュリティの向上、その一点突破にかけて開発していきます。

名前選び

Rust のソースコードファイルの拡張子は .rs なので rsqlite がいい感じだなと思ったのですが、すでにありました。C-binding library ですが3年前で開発が止まっています。ダウンロード状況を見る限り使われている様子もありません。うーむ。

他にも考えましたが、rusqlite も sqrite も sqlite も sqlite3 もすでに取られており、全て C-inding library でした。

というわけで苦肉の策ですが、"Pure Rust SQLite" ということで "prsqlite" という名前になりました。

最大の難関 VDBE

SQLite は SQL 文をパースしてバイトコードにコンパイルし、VDBE (Virtual DataBase Engine) という Virtual Machine で SQL を実行しています。

www.sqlite.org

EXPLAIN を sqlite で実行してみると実際のバイトコードが見えます。

sqlite> EXPLAIN SELECT * FROM example WHERE col1 = 10 ORDER BY col2 ASC;
addr  opcode         p1    p2    p3    p4             p5  comment
----  -------------  ----  ----  ----  -------------  --  -------------
0     Init           0     14    0                    0   Start at 14
1     Noop           1     4     0                    0
2     OpenRead       0     2     0     2              0   root=2 iDb=0; example
3     OpenRead       2     3     0     k(2,,)         0   root=3 iDb=0; i_example
4     Explain        4     0     0     SCAN example USING INDEX i_example  0
5     Rewind         2     13    1     0              0
6       DeferredSeek   2     0     0                    0   Move 0 to 2.rowid if needed
7       Column         0     0     1                    0   r[1]=example.col1
8       Ne             2     12    1     BINARY-8       81  if r[1]!=r[2] goto 12
9       Column         0     0     3                    0   r[3]=example.col1
10      Column         2     0     4                    0   r[4]=example.col2
11      ResultRow      3     2     0                    0   output=r[3..4]
12    Next           2     6     0                    1
13    Halt           0     0     0                    0
14    Transaction    0     0     4     0              1   usesStmtJournal=0
15    Integer        10    2     0                    0   r[2]=10
16    Goto           0     1     0                    0

バイトコードの仕様はドキュメントに全て記述されていますが、めんどくさそうで正直実装したくないです。今は SQL の構文木をインタープリタ的に実行しているので、いけるとこまでこの方法でいきたいです。ただ、複数のテーブルや、中間テーブルを考え始めると複雑性が高まるのでバイトコードを導入しなければいけないこともなんとなくわかります。

最後に

コミットログを見て貰えばわかりますが、2月に作り始めて1週間くらいで社内のオープンソースのリリース手続きがめんどくさ過ぎることを知って飽きて辞めてましたが、最近再開して無事公開に漕ぎ着けました。ソースファイルに会社のコピーライトが付いているのもそのためです。はぁ。

最近は会社から帰ってきてから楽しくてずっと SQLite を作ってます。ちゃんと睡眠を確保して飽きるまで頑張っていきます。

前回の記事 ではソフトウェアエンジニアとしての AI の脅威についてビクビクしてましたが、当面は王道の正面切って AI を利用しながら high productivity を頑張ります。