Rustでリレーショナルデータベースを自作したときの成果と反省と学び

はじめに

この記事では、個人プロジェクトとしてRust言語でリレーショナルデータベースを開発した経験（もう五ヶ月も前...）について、その成果と反省、得た学びを共有します。

DBMSを自作した理由

自分がDBMSの自作に着手したのは、『Designing Data-Intensive Applications』という本の内容を深く理解するためでした。

この本は、データシステムの設計と運用において最も大切な「信頼性」、「拡張性」、「保守性」を保証する方法論を、豊富な文献を引用しつつ、理論と実践の橋渡しを巧みに行いながら、丁寧に説明している名著です。読んだことがない人は速攻購入してくだい。本当にいい本です。

この本は、データベースの内部構造に関する話も豊富に含まれていたので、「データベース自作してみようか...」という気持ちになりました。

Rustを採用した理由

データベースの実装のついでに、Rustも詳しくなりたかったので、Rustを実装言語として採用しました。

結構、安直で申し訳ないですが、それが真実です...。

参考にしたデータベース

PostgreSQLやMySQLなどの商業用のデータベースは、大概、数千万行のコード量になります。 現実的に考えると、これらのデータベースのソースコードを読んで実装を勉強するのは無理なので、教育用のデータベースを教材にする必要がありました。

参考にする教育用のデータベースの候補には、CMUのデータベースの講義で使われるbustubとDatabase Design and Implementationという教科書で実装が解説されているSimpleDBがありましたが、教科書がある方が自分のレベルや学習方法と合うと思い、SimpleDBを参考にすることにしました。

実装したデータベース

OxideDBというデータベースを実装しました。

「Rustは錆」→「錆は鉄の酸化物」→「酸化は英語でOxide」ということで、OxideDBと名付けました。

命名自体は結構気に入っていますが、DBを入れると被りやすい命名アンチパターンを踏んでいるらしく、次は、無関係な一音節の単語2つを繋げる「The Pavlo Database Naming Method」という方法を採用していこうと思います。

実装とテストをあわせて、14,000行ほどの規模のソフトウェアになりました。

CRUD操作も基本的なSQLで実行できて、インデックスも張ることができます。

これが実装できた自分を誇らしく思います。

成果

ソフトウェア開発のコツが掴めた

「ソフトウェア開発は抽象化の連続」という言葉が好きなのですが、まさにこの言葉の意味をこの身を持って理解することができました。

初期段階では、実装に必要なすべてのコードの詳細を頭に入れておかなければ、一行も書けなかったのですが、 開発が進むにつれ、処理を適切に抽象化しインターフェース化したら、その瞬間に具体的な実装の詳細を忘れても、問題なくコードが書けるようになりました。

人間の脳は忘却後に抽象化するプロセスを辿りますが、ソフトウェア開発ではこのプロセスを逆転させるだけで効率化できることに気付けたのは自分にとって大きな成果だと感じています。

トランザクションを理解できた

データベースにおけるデータの一貫性を守るための機構であるトランザクションの仕組みを、実装を通して理解できました。 この経験によって、「ラッチ」、「ロック」、「WAL」、「トランザクション分離レベル」などの、ドキュメントで頻繁に登場するものの直感的に理解しにくい概念を実装ベースで理解することができました。

自信を育むことができた

DB自作は労力的にはコンパイラ自作やOS自作と比べても遜色ないので、そのレベルのことを学部生のうちにできたことは自信に繋がりました。

多少、難しいエンジニアリングも「まぁ、データベース作ったことあるし。」で片付いて臆することがなくなりました。

反省

途中でデータベース実装がただのコードの翻訳作業となった

SimpleDBのソースコードを参考にしながらRustでデータベースを実装した訳ですが、途中で実装作業が、コードの翻訳作業になりました。

途中から、ソースコードの実装上の意味などを深く考えずに、ただ流れ作業でJavaのコードをRustに変換していました。

データベースの実装の知識がない状態では、学習のために多少コードの写経や翻訳作業を強いられるのは仕方のないことですが、学習の目的を見失わないようにするべきでした。

ラッチの粒度が粗い

データベースの機能は実装できたものの性能が絶望的にないです。 具体的には、データベース内でディスクにバイト列を読み書きするFileManagerや、ヒープ上でデータの読み書きをして低速なディスクI/Oの代わりにメモリI/Oでデータの読み書きを行うBufferManagerなどのコンポーネントや、他の全てのコンポーネントがArc<Mutex<>>でラップされている影響でデータの読み書きが並列化できていないです。

pub struct OxideDB {
    block_size: usize,
    file_manager: Arc<Mutex<FileManager>>,
    log_manager: Arc<Mutex<LogManager>>,
    buffer_manager: Arc<Mutex<BufferManager>>,
    lock_table: Arc<Mutex<LockTable>>,
    metadata_manager: Option<Arc<MetadataManager>>,
    planner: Option<Arc<Mutex<Planner>>>,
}

これはJavaに最適化されたアーキテクチャをあまり深く考えずにRustに変換してしまったことが原因です。 LogManagerとBufferManagerはディスクアクセスを行うため、ディスクアクセスを行うFileManagerインスタンスをコンストラクタに渡して依存性注入(DI)が行われています。他のインスタンスも同様に、DIのマトリョシカを行うように設計されています。

DIによって、クラス/構造体間の結合度を下げ、変更やテストが容易なコードになるのですが、このデザインパターンは、マルチスレッドのプログラムにおいて*1、「複数のインスタンスで共有する場合はArc<>、さらに、インスタンスに変更が加えれる可能性があるのであれば、Arc<Mutex<>>をラップしなければならない」というRustの言語ルールと衝突します。

今回の実装では、メモリ管理をGCに任せるJavaと、所有権を持つスコープを厳密に管理してメモリ管理をするRust、それぞれの最適なソフトウェアデザインパターンが異なることを意識せずに、元のSimpleDBの設計を忠実にRustで再現してしまったので結果的に、ラッチの粒度が粗いデータベースが出来上がってしまいました。

次回は、Rustの言語ルールに沿ってデータベースを設計することにします。

データベース開発と先人のアドバイスから得た学び

自分は、とあるデータベース自作コミュニティに参加しているのですが、そのコミュニティで頂いたアドバイスから得た学びを共有します。

ラッチの粒度の粗さは伸び代

コミュニティでラッチの粒度が粗いことを嘆いていたら、「ラッチの粒度の粗さは伸び代だよ」と慰まれました。

皆さんも自作DBに挑戦される際は、ロックの粒度に臆せず実装をしていきましょう。

ソフトウェアの設計と実装は繰り返される試行を通して洗練される

「今回作ったものは、それはそれで理解の役に立ったし、経験値も積めたので、感謝とともにどっかで投げ捨てましょう」（一部に変更を加えました）

データベース実装の労力を鑑みるとかなりショッキングなアドバイスですが、結果的にためになりました。

設計は本来、その後の実装における不確実性を最小限に抑えるためのものですが、実際の開発過程では、設計の段階で想定していた通りに進むことは稀です。さらに、実装段階で設計自体に問題が見つかることも少なくないです。

そのようなケースで、ソフトウェアの可塑性の限界を超える変更を加える必要があると判断した場合、また0からやり直すのも手です。

このアドバイスがなかったら、このOxideDBに価値がほとんどない追加機能作業をして時間を無駄にするところでした。

このアドバイスをしてくれた方によると、3ラウンドくらいで良い設計になるらしいです。

あと2ラウンド頑張ります！

※ シンプルにベターなソフトウェアを目指す場合の知見です。ビジネスの話だと、既に使った工数を無駄にすることは避けるインセンティブが働くので、この考え方はトレードオフの関係にあるということに注意が必要です。

今後の展望

並行処理を勉強

今回の開発では、自分の並行処理の知識のなさが誤った実装の原因だと考えているので、詳しくなりたいです。

教科書は『並行プログラミング入門―Rust、C、アセンブリによる実装からのアプローチ』を読もうと思います。

とにかくラウンド2

ラウンド2に挑戦したいです。 大体、Rustに合う設計は頭の中にぼんやりあるので、並行プログラミングについての勉強と並行して行いたいです。

教材的なのをOSSで作りたい

もっとデータベース自作erを増やしたい所存なので、初学者が取り掛かりやすいようなハンズオン形式の教材をかなり遠い将来作りたいと考えています。

イメージとしては、rustlingと似たようなものを想定しています。

終わり

最後まで読んでくれてありがとうございました。データベース自作ぼちぼち頑張りますので、応援のほどよろしくお願いします。

ちなみに、自分が実装の際に参考にした文献はだいたい自作RDBMSやろうぜ!にあります。自作DBコミュニティの情報もあります。

修正

なるべく正しい知識を広めたいので、記事に間違った内容があれば、どのような手段でも構わないのでご連絡ください。

  • 2024/03/05
    • 「ラッチの粒度が粗い」の節で、「マルチスレッドのプログラムにおいて」という文言を追加しました。
    • ryo_gridさんのご指摘によって修正、ありがとうございました！

*1:シングルスレッドの場合はRefCell型でいけます。

ターミナル風のブログサイトを作った

今回、yoshisaur.netでターミナル風のブログサイトを作りました。

元々、M4TT72という方がMITライセンスの元でターミナル風のサイトを作っていたので、改良するという形で使わせていただいています。

元々はブログポスト用に作られていなかったので、マークダウンファイルを置くと静的にページが生成されるように改良しました。

また、スタイルもTerminal CSSを使っていて、これもMITライセンスだったので改良して使っています。

休日モードなのでブログは軽めに書きました。良いお年を!

デバッガの練習のためにRustでCTF(Pwn)問題を作った

画像はCC BY 2.0 DEEDライセンスのもと使用しています。*1

1. はじめに

琉球大学知能情報アドベントカレンダー Advent Calendar 2023の12月5日の記事です。

12月1日の個人的に興味があるRustとWasmについてでバイナリを読む作業があったのですが、思いの外楽しかったので、今回はデバッガの使い方を学ぶために、CTF(Pwn)問題をRustで作成してrust-lldbを用いて解いて行こうと思います。

x86_64アーキテクチャ用のバイナリファイルを解析していきます。

2. デバッガとは

デバッガは、プログラムの実行を制御し、バグやエラーを特定し、修正するためのツールです。デバッガを使用すると、プログラムをステップバイステップで実行したり、特定の条件でプログラムの実行を一時停止したり、変数の値を確認したりすることができます。

デバッガは、プログラムの動作を理解し、問題を特定し、解決するための重要なツールです。特に、複雑な問題や予期しない動作をデバッグする際には、デバッガの使用はほぼ必須となります。

今回扱うデバッガはソースレベルデバッガです。ソースレベルデバッガには、GCCベースのコンパイラではgdb、LLVMベースのコンパイラではlldbなどがあります。

RustはLLVMベースで、rust-lldbというデバッガが提供されています。

3. CTFとは

CTF（Capture The Flag）は、コンピュータセキュリティのスキルを競う競技の一つです。参加者は、様々なセキュリティ問題を解決し、"フラグ"と呼ばれる特定の文字列を見つけ出すことでポイントを獲得します。問題は、Webセキュリティ、暗号学、ネットワークセキュリティ、ディスアセンブル、バイナリ解析など、様々なカテゴリに分けられます。

今回作成するCTF問題は、Pwn問題と呼ばれるカテゴリのものです。

Pwn問題は、バイナリ解析とエクスプロイト作成のスキルを試す問題です。与えられたバイナリを解析し、そのバイナリの脆弱性を突くことでフラグを取得します。

4. 実際に解いてみる

バイナリのダウンロードページを用意しました。こちらからダウンロードしてください。

4.1. 問題の内容を確認する

$ ./behemoth0で実行できます。

実行権限が付与されていなければ$ chmod 755 behemoth0を実行してください。

$ ./behemoth0        
Please enter your password:

このようにパスワードを入力するように促されます。

正しいパスワードを入力すると何らかの報酬が貰えることが期待できます。

4.2. stringsコマンドで文字列を抽出してみる

stringsコマンドは、バイナリファイルや他の種類のファイルからASCII文字列を抽出するためのUnix系システムのコマンドです。このコマンドは、ファイル内の印刷可能な文字列を表示します。これは、バイナリファイルの内容を調査する際に特に役立ちます。

実際に実行して文字列を抽出してみます。

$ strings behemoth0

...省略
/rustc/5680fa18feaa87f3ff04063800aec256c3d4b4be/library/core/src/alloc/layout.rsattempt to divide by zeroIEXXOI^BEXYOHK^^OXSY^KZFOPlease enter your password: src/main.rs
qwerty12345answer'Answer'? Well, aren't we playing the philosopher today!
'12345'? I see, you've mastered the art of counting!
Oh, 'qwerty'? How original!
As if it would be that easy!
Oh, choosing to remain silent? How intriguing!
Access denied. Try again.
...省略

このようにpassword, qwerty, 12345のような文字列が抽出できました。

実際に入力してみます。

$ ./behemoth0
Please enter your password: password
As if it would be that easy!
Access denied. Try again.
Please enter your password: qwerty
Oh, 'qwerty'? How original!
Access denied. Try again.
Please enter your password: 12345
'12345'? I see, you've mastered the art of counting!
Access denied. Try again.

煽り文句と共にパスワードが弾かれました。

ネタバレですが、stringsコマンドで抽出できた文字列をパスワードに入れても正解はありません。

実装のコードでは、平文で正解のパスワードが記述されていないようです。

4.3. デバッガを用いて解析する

stringsコマンドではこの問題が解けないことがわかりました。

正解のパスワードはおそらく、実行時に動的に生成されていると考えることができます。

この場合は、バイナリファイルを実行しながらメモリにある変数を調べることができるデバッガを使います。

以下のコマンドを実行します。

$ rust-lldb behemoth0

パスワードが正しいか照合するということは、文字列を比較する処理がどこかにあるはずです。

C言語の場合はstrcmp関数などがありますが、Rustでは==演算子で文字列の比較をします。

==演算子はstd::cmp::PartialEqトレイトのeqメソッドを呼び出すことで、二つの値の等価性を評価します。*2

eqメソッドが呼ばれる箇所にbreakpointを設置します。

breakpointとは、デバッガがプログラムの実行を一時停止する指定した地点のことです。breakpointを設置することで、その地点での変数の値を確認したり、ステップバイステップでプログラムを実行したりすることができます。

Rustのデバッガであるrust-lldbでは、b (breakpoint set --name)コマンドを使用してbreakpointを設置します。以下のようにeqメソッドが呼ばれる箇所にbreakpointを設置します。

(lldb) b eq
Breakpoint 1: 60 locations.

出力結果は、eqという名前の関数またはメソッドがプログラム内の60箇所で使用されていて、breakpointがそのすべての箇所に設置されたことを示しています。

breakpointを設置したらプログラムをr (run)コマンドで走らせます。パスワードの入力が聞かれるので適当な値を入力します。パスワードを入力し終えるとeqメソッドが呼ばれるまで実行されます。

(lldb) r
Process 3493 launched: '/Users/yoshisaur/workspace/blog/20231205/behemoth0/target/debug/behemoth0' (x86_64)
Please enter your password: password
Process 3493 stopped
* thread #1, name = 'main', queue = 'com.apple.main-thread', stop reason = breakpoint 1.2
    frame #0: 0x00000001000057a4 behemoth0`_$LT$alloc..string..String$u20$as$u20$core..cmp..PartialEq$GT$::eq::h76fa5ff4362a6554(self=0x00007ff7bfefecb0, other=0x00007ff7bfefec60) at string.rs:366:5
Target 0: (behemoth0) stopped.

eqメソッドが呼ばれた段階で、fr v (frame variable)コマンドを用いて、現在のフレームの変数を表示します。このコマンドは、現在のスタックフレームのすべての変数を表示します。

(lldb) fr v
(alloc::string::String *) self = 0x00007ff7bfefecb0
(alloc::string::String *) other = 0x00007ff7bfefec60

これは、selfとotherという2つの変数がメモリ上の特定のアドレスを指していることを示しています。selfは入力されたパスワードを、otherは正しいパスワードを表していると考えるのが自然です。

しかし、これらはただのメモリアドレスなので、直接的な情報は得られません。そのため、これらのアドレスが指す実際の文字列を見るためには、さらにデバッガのコマンドを使用する必要があります。

具体的には、p（print）コマンドを使用して、これらの変数が指す文字列を表示します。

(lldb) p *other
(alloc::string::String) $0 = "ネタバレ防止" {
  vec = size=25 {
    ネタバレ防止
  }
}

答えをネタバレすると面白くないので省略しました。実際に入力して報酬をゲットしてみてください。

一旦デバッガでの作業が終了したのでq(quit)でデバッガから抜けてください。

4.4. stringsコマンドが有効でなかった理由

パスワードは解析できたのでこれで十分ですが、stringsコマンドで文字列を抽出できなかった理由もデバッガで調査しようと思います。

stringsコマンドで文字列を抽出できなかったのは、実行時に動的に正解のパスワードの文字列を動的に生成しているのが原因であると考えることができます。

もし動的にパスワードを生成しているのであれば、文字列を生成する関数またはメソッドが存在しているはずです。

main関数内から探してみましょう。

出力が長いので一旦出力をテキストファイルに書き出してから探すことをおすすめします。

$ rust-lldb behemoth0 2>&1 | tee session.txtでテキストファイルに書き込みながらコンソールにも出力を表示させることができます。

disassemble --name mainをlldbで実行して、main関数をディスアセンブル*3してください。

実行したらlldbから抜けて、$ grep "callq" session.txt | lessを実行してください。

このコマンドは、session.txtファイルからcallqという文字列を含む行を検索し、その結果をlessコマンドで表示します。callqはx86_64アーキテクチャのアセンブリ言語で関数呼び出しを表す命令です。つまり、このコマンドはmain関数内で呼び出されるすべての関数を探すために使用されます。

behemoth0[0x100004cf7] <+55>:   callq  0x100004c60               ; behemoth0::memfrob::h0a7613b04ef7d854 at main.rs:3
.
.
.
省略
.
.
.
behemoth0[0x100005263] <+19>: callq  0x100004be0               ; std::rt::lang_start::h8203cbc8150ed6fb at rt.rs:159

これらの関数呼び出しの中に、文字列を生成する関数があるはずです。

その中で特に注目すべきは、behemoth0::memfrob::h0a7613b04ef7d854という関数です。

behemoth0クレートがmemfrob関数を独自に定義しているので、標準クレートで実装されていない特殊な処理が行われている可能性があります。

ちなみにh0a7613b04ef7d854の部分は、Rustの名前修飾（name mangling）によって生成された一意の識別子です。Rustでは、コンパイル時に関数名や変数名を一意に識別できるように、名前修飾を行います。これにより、同じ名前の関数や変数が他のスコープで定義されていても、それぞれを一意に識別することが可能になります。

lldbでmemfrob関数が呼ばれている箇所にbreakpointを設置して、実行します。

(lldb) b memfrob
Breakpoint 1: where = behemoth0`behemoth0::memfrob::h0a7613b04ef7d854 + 46 at main.rs:4:5, address = 0x0000000100004c8e
(lldb) r
Process 4695 launched: '/Users/yoshisaur/workspace/blog/20231205/behemoth0/target/debug/behemoth0' (x86_64)
Process 4695 stopped
* thread #1, name = 'main', queue = 'com.apple.main-thread', stop reason = breakpoint 1.1
    frame #0: 0x0000000100004c8e behemoth0`behemoth0::memfrob::h0a7613b04ef7d854(input="暗号化前の文字列") at main.rs:4:5
   1    use std::io::{self, Write};
   2
   3    fn memfrob(input: &str) -> String {
-> 4        input.bytes().map(|b| (b ^ 42) as char).collect()
   5    }
   6
   7    fn main() {
Target 0: (behemoth0) stopped.

出力で出たRustコードでネタバレを喰らいましたが、一応、読んでいきましょう。

memfrob関数では、文字列の各バイトを42でXOR演算した結果を新たな文字列として返す関数だと出力のコードからわかります。

Rustのコードは見なかったことにして、デバッガのみでmemfrob関数が正解のパスワードを動的に生成していると発見してみましょう。

memfrob関数が呼ばれた時点のフレームの変数を出力します。

この出力から、memfrob関数の引数inputに文字列(パスワードに関するものかは未確定)が渡されていることがわかります。

現在の関数が終了するまで、プログラムの実行を続けるfinishコマンドを使って、memfrob関数を終了するところまで実行させます。

(lldb) finish
Process 5021 stopped
* thread #1, name = 'main', queue = 'com.apple.main-thread', stop reason = step out
Return value: (alloc::string::String) $0 = "ネタバレ防止" {
  vec = size=25 {
      ネタバレ防止
  }
}

    frame #0: 0x0000000100004cfc behemoth0`behemoth0::main::h537f6aedbc8cd8a6 at main.rs:12:9
   9        let frobbed_password = memfrob(secret_password);
   10
   11       loop {
-> 12           print!("Please enter your password: ");
   13           io::stdout().flush().unwrap();
   14           let mut input = String::new();
   15           io::stdin().read_line(&mut input).unwrap();
Target 0: (behemoth0) stopped.

memfrob関数が動的に正解のパスワードを生成していることがわかりました。

これで、stringsコマンドでバイナリから静的に文字列を解析してもパスワードが見つからない原因が調査できました。

5. Rustのコード

今回の問題は以下のようなコードで実装されました。

use std::io::{self, Write};

fn memfrob(input: &str) -> String {
    input.bytes().map(|b| (b ^ 42) as char).collect()
}

fn main() {
    let secret_password = "ネタバレ防止";
    let frobbed_password = memfrob(secret_password);

    loop {
        print!("Please enter your password: ");
        io::stdout().flush().unwrap();
        let mut input = String::new();
        io::stdin().read_line(&mut input).unwrap();
        input = input.trim().to_string();
        match input.as_str() {
            _ if input == frobbed_password => {
                let output = memfrob("ネタバレ防止");
                println!("{}", output);
                break;
            }
            "" => println!("Oh, choosing to remain silent? How intriguing!"),
            "password" => println!("As if it would be that easy!"),
            "qwerty" => println!("Oh, 'qwerty'? How original!"),
            "12345" => println!("'12345'? I see, you've mastered the art of counting!"),
            "answer" => println!("'Answer'? Well, aren't we playing the philosopher today!"),
            _ => println!("Access denied. Try again."),
        }
    }
}

不要に思えるパスワードのパターンマッチング、煽り文句はstringsコマンドの出力を使ったときに問題を解く人を出力で惑わせるために書きました。

Rustでは、バッファオーバーを起こすプログラムを使ってCTF問題を作るのは難しいですが*4、このようにデバッガを用いたリバースエンジニアリングの問題は作れます。

余談ですが、実はGNUのCライブラリには、ジョークとして実装されたmemfrob関数があります。GNUのCライブラリにあるmemfrob関数は、このRustのコードの関数と全く同じ処理をします。今回、RustではGNUのCライブラリを直接呼ぶのは難しかったため、独自実装しました。

6. 参考にしたCTF問題の出典

問題の内容はOverTheWireのbehemothという常設CTFを参考にして作成しました。簡単にチャレンジできて、非常に楽しいので、こちらも解いてみてください。

7. まとめ

この記事ではRustで作成したCTFをrust-lldbという用いて解いてデバッガの使い方を学習して練習しました。

あまりデバッガに日頃触れていない方にとっての学びになったことを祈っております。

実際に、この記事の問題を解いたら、報酬となる出力がコンソールに表示されます。それを僕にDMで教えてください。喜びます。

最後まで読んでくださって、どうもありがとうございました。

*1:Lydia Liu氏の画像をCC BY 2.0 DEEDライセンスのもと使用しています。Campers Playing Capture the Flag

*2:Trait std::cmp::PartialEqのドキュメントを参照

*3:ディスアセンブル（disassemble）とは、バイナリコード（機械語）を人間が理解可能なアセンブリ言語に変換することを指します。

*4:そもそもNXビット、XDビットなどの実行禁止ビットをサポートしているプロセッサでは作れない

個人的に興味があるRustとWasmについて

どうも、ヨシザウルスです。光栄ながら琉球大学知能情報アドベントカレンダーのトップバッターを務めさせていただきます。

1. はじめに

この記事は、私が個人的に興味を持っているRustとWasmについて説明します。

間違いや訂正が必要だと感じた箇所があればコメント大歓迎です。

では、早速、RustとWebAssemblyの説明をしたいと思います。

2. Rust

Rust logo

Rustはメモリ安全性を保証しつつもC/C++に匹敵するパフォーマンスを発揮できるプログラミング言語です。

メモリ安全性とは、メモリアクセスに関するバグをコンパイル時に検知することで、実行時にメモリアクセスに関するバグが発生しないことを保証することです。

メモリーアクセスに関するバグはセキュリティの脆弱性にも繋がるため、メモリ安全性を保証することは非常に重要です。

ちなみに、Rustは習得が非常に難しい言語です。 所有権、ライフタイムなど、一部の文法が特殊で、慣れるのに時間がかかります。しかし、これらの文法はRustのメモリ安全性を保証するために必要なので、それらを理解し、適切に使用することが不可欠です。

かなり荒く不親切な内容になりますが、Rustの基本的なルール(所有権、ライフタイム)を紹介します。

2.1. Rustの所有権

以下に所有権を説明するコードを示します。

fn main() {
    // 文字列を作成し、所有権をs1に与える
    let s1 = String::from("Hello, Rust!");

    // s1の所有権をs2にムーブする
    let s2 = s1;

    // s1を使用しようとすると、所有権が移動しているためエラーが発生する
    // println!("{}", s1); // この行はコンパイルエラーになる

    // s2は所有権を持っているため、正常に動作する
    println!("{}", s2);
}

このコードは、s1に文字列を作成し、その所有権をs2に移動しています。 そのため、s1を使用しようとするとコンパイルエラーが発生しますが、s2は所有権を持っているため、正常に動作します。

Rustは、所有権を移動することで、メモリアクセスに関するバグをコンパイル時に検知することができます。

少し発展させて、借用ルールも説明します。

fn main() {
    // 文字列を作成し、所有権をs1に与える
    let s1 = String::from("Hello, Rust!");

    // s1の所有権をs2にムーブする
    let s2 = s1;

    // s2の所有権を借用し、参照を作成する
    let len = calculate_length(&s2);

    // s2は所有権を持っているため、正常に動作する
    println!("{} is {} characters long.", s2, len);
}

// sの所有権を借用し、文字数を返す関数
fn calculate_length(s: &String) -> usize {
    s.len()
}

このコードは、calculate_length関数がsを参照として借用していることを示しています。 そのため、sの所有権を持っているs2を使用しようとしてもコンパイルエラーが発生しません。 また、sの所有権を持っているs2を変更することもできません。

このようにRustは所有権を使ってメモリ安全性を保証しています。

2.2. Rustのライフタイム

所有権の他にもRustには、ライフタイムという概念があります。ライフタイムとは、参照が有効である期間のことです。ライフタイムは、コンパイラが参照の有効な期間を検証するのに使用されます。

ライフタイムに関する例を示します。

fn main() {
    let string1 = String::from("Hello, Rust!");
    let string2 = String::from("Hello, Lifetimes!");

    // longest関数を呼び出し、戻り値をresultとして受け取る
    let result;
    {
        // string1とstring2の参照を渡し、戻り値の参照をresultに格納する
        result = longest(&string1, &string2);
        println!("The longest string is: {}", result);
    } // resultはスコープを抜けるが、resultの参照は有効なライフタイム内にあるため問題ない

    // resultの参照を使おうとすると、スコープ外なのでエラーが発生する
    // println!("The longest string is: {}", result);
}

// 'aは関数の引数と返り値のライフタイムが関連していることを示す
fn longest<'a>(x: &'a str, y: &'a str) -> &'a str {
    if x.len() > y.len() {
        x
    } else {
        y
    }
}

このコードのlongest関数の関数シグネチャにある'aはライフタイム注釈で、これはコンパイラにlongest関数によって返される参照の参照が有効である期間は引数xとyのライフタイムに依存していること示しています。これによってresultが参照しているstring1またはstring2の参照が有効であるということを保証しています。

このケースでは、longest関数は2つの文字列の参照を引数として受け取り、そのうちの1つを参照として返します。しかし、この関数がどの参照を返すかは実行時までわかりません。したがって、このようにライフタイム注釈を使って、引数の参照と同じまたはそれより短いライフタイムを持つことを保証する必要がありました。

Rustの魅力はまだまだあります。RustからC/C++を呼べたり、asm!でRustからインラインでアセンブリーが書けたり、低レイヤー、組み込み、アプリケーション、何にでも応用が効く言語なので魅力満載です。

3. Wasm

これもかなり面白い技術だと思います。簡単に紹介すると、どのOS, CPUでも実行できるバイナリフォーマットです。

WebAssembly(Wasm)については以下のように公式ページで説明されています。

WebAssembly（略称Wasm）は、スタックベースの仮想マシンのためのバイナリ命令形式です。Wasmは、プログラミング言語の移植可能なコンパイルターゲットとして設計されており、クライアントとサーバーのアプリケーションをWeb上にデプロイすることを可能にします。

「スタックベースの仮想マシンのためのバイナリ命令形式」という表現が直感的に理解しづらいので以降噛み砕いて説明していきます。これがわかるとかなり面白いです。

3.1. 「スタックベースの仮想マシンのためのバイナリ命令形式」とは

「スタックベースの仮想マシンのためのバイナリ命令形式」とは何なのか、用語を一つづつ紐解いて説明していきます。

3.1.1. 「スタック」

「スタック」は、データ構造の一種で、データの追加（プッシュ）と削除（ポップ）が一方向からしか行えない特性を持っています。この特性は「後入れ先出し」（Last In First Out, LIFO）とも呼ばれます。

スタックの主な操作は以下の通りです：

  • プッシュ（Push）：スタックの一番上に新しいデータを追加する。
  • ポップ（Pop）：スタックの一番上のデータを取り出し、そのデータをスタックから削除する。

スタックの具体的な使われ方について、スタックベースの計算機やプログラミング言語(RPN, Forth, PostScript)で使われる逆ポーランド記法を例に出して説明します。

逆ポーランド記法はオペランド(数)の後に演算子を置くという書き方をします。

つまり、具体例を出すと5 * (3 + 4)という式を表すと5 3 4 + *となります。

計算は以下のように行います。

  1. 5 をスタックにプッシュする（スタック：5）。
  2. 3 をスタックにプッシュする（スタック：5, 3）。
  3. 4 をスタックにプッシュする（スタック：5, 3, 4）。
  4. + を見つけたので、スタックから 3 と 4 をポップし、それらを足す。結果の 7 をスタックにプッシュする（スタック：5, 7）。
  5. * を見つけたので、スタックから 5 と 7 をポップし、それらを掛ける。結果の 35 をスタックにプッシュする（スタック：35）。
  6. 式が終了したので、スタックのトップにある 35 が最終的な結果となる。

スタックを使った計算の流れはこのようなものになります。実はWasmもスタックベースの処理をしているので、逆ポーランド記法と同じ計算をします。

3.1.2. 「仮想マシン」

仮想マシンは、異なるOSやCPUアーキテクチャ間での互換性を提供します。つまり、仮想マシンは「OSやCPUのアーキテクチャを吸収する」役割を果たします。Wasmも仮想マシン上で命令が実行されるので、これにより、同じバイナリ命令形式ファイルが異なる環境で一貫して動作することが保証されます。これは、開発者が各環境に対して個別にバイナリ命令形式ファイルを生成する必要がなく、一度生成したWasmをどの環境でも実行できるということを意味します。

WebAssemblyテキストフォーマット(wat)を使ってWasmの仮想マシン上での計算フローを説明します。watはWebAssemblyのバイナリ命令形式を人間が読み書きできるテキスト表現です。Wasmからwatへの変換もできます。

以下のようなwatファイル(ファイル名: calculate.wat)を用意します。 内容は先程の5 * (3 + 4)を関数化してx * (y + z)としたものです。

(module
  (func (export "calculate") (param $x i32) (param $y i32) (param $z i32) (result i32)
    local.get $x
    local.get $y
    local.get $z
    (i32.add)
    (i32.mul)
  )
)

この関数の実行フローは以下のようになります：

  1. $x、$y、$zの値が順にスタックにプッシュされます。
  2. i32.add命令が実行されると、スタックのトップから2つの値（$zと$y）がポップされ、それらの加算結果がスタックにプッシュされます。
  3. 次にi32.mul命令が実行されると、スタックのトップから2つの値（加算結果と$x）がポップされ、それらの乗算結果がスタックにプッシュされます。
  4. 最後に、スタックのトップにある値（乗算結果）が関数の戻り値として返されます。

例に出した逆ポーランド記法と同じ流れの処理をしています。

この段階でwatファイルが用意できたので、変換して実際にWasmのバイナリ命令形式ファイルを使ってみます。

$ wat2wasm calculate.watを実行して、calculate.wasmを生成します。

このwasmファイルを使うために、htmlファイルとjsファイルを作成します。すべて同じディレクトリに配置してください。

index.html

<!DOCTYPE html>
<html>
<head>
    <title>WebAssembly Demo</title>
</head>
<body>
    <h1>WebAssembly Demo: x * (y + z)</h1>
    <input id="x" type="number" placeholder="Enter x">
    <input id="y" type="number" placeholder="Enter y">
    <input id="z" type="number" placeholder="Enter z">
    <button onclick="calculate()">Calculate</button>
    <p id="result"></p>
    <script src="main.js"></script>
</body>
</html>

main.js

async function calculate() {
    const x = document.getElementById('x').value;
    const y = document.getElementById('y').value;
    const z = document.getElementById('z').value;

    const wasmModule = await WebAssembly.instantiateStreaming(fetch('calculate.wasm'));
    const result = wasmModule.instance.exports.calculate(x, y, z);

    document.getElementById('result').innerText = `${x} * (${y} + ${z}) = ${result}`;
}

$ python3 -m http.server 8000を実行してください。

http://localhost::8000を開いて、x = 5, y = 3, z = 4 を代入して計算結果を取得してください。

この画像のような結果になると思います。

これはWasmをjsから呼び出すことに成功したことを意味します。(拍手)

ちなみにwasmはjs以外でも読み込めます。

Rustでも読み込んでみましょう。

$ cargo init rust-wasm

Cargo.tomlに以下の行を追加(バージョンはブログ公開時点での最新版)

[dependencies]
wasmer = "4.2.4"

wasmディレクトリをrust-wasmに作成して、wasmファイルを置きます。

main.rsを以下のように書きます。

// 標準ライブラリからenvとfs::readをインポートします。
use std::env;
use std::fs::read;
// wasmerから必要なものをインポートします。これはWebAssemblyを扱うためのライブラリです。
use wasmer::{imports, Instance, Module, RuntimeError, Store, Value};

// main関数を定義します。エラーが発生した場合は、エラーを返します。
fn main() -> Result<(), Box<dyn std::error::Error>> {
    // コマンドライン引数を取得します。
    let args: Vec<String> = env::args().collect();
    // 引数をi32型にパースします。
    let arg1 = args[1].parse::<i32>()?;
    let arg2 = args[2].parse::<i32>()?;
    let arg3 = args[3].parse::<i32>()?;

    // WebAssemblyバイナリを読み込みます。
    let wasm_bytes = read("./wasm/calculate.wasm")?;
    // ストアを作成します。これはWebAssemblyの状態を保持します。
    let mut store = Store::default();
    // モジュールを作成します。これはWebAssemblyのコードを保持します。
    let module = Module::new(&store, &wasm_bytes)?;

    // インポートオブジェクトを作成します。これはWebAssemblyがホスト環境から関数を呼び出すために使用します。
    let import_object = imports! {};
    // インスタンスを作成します。これはWebAssemblyの実行環境を保持します。
    let instance = Instance::new(&mut store, &module, &import_object)?;

    // "calculate"関数をエクスポートから取得します。
    let calculate = instance.exports.get_function("calculate")?;
    // 関数を呼び出し、結果を取得します。
    let result = calculate.call(
        &mut store,
        &[Value::I32(arg1), Value::I32(arg2), Value::I32(arg3)],
    )?;

    // 結果を取得します。結果がi32型でない場合はエラーを返します。
    let result_value = match result[0] {
        Value::I32(val) => val,
        _ => return Err(Box::new(RuntimeError::new("Unexpected result type"))),
    };

    // 結果を出力します。
    println!("{} * ({} + {}) = {}", arg1, arg2, arg3, result_value);

    // 正常終了します。
    Ok(())
}

$ cargo 5 3 4と実行すると以下のような出力が得られます。

$ cargo run 5 3 4
    Finished dev [unoptimized + debuginfo] target(s) in 0.12s
     Running `target/debug/rust-wasm 5 3 4`
5 * (3 + 4) = 35

このようにjsでなくとも専用のランタイムさえあれば、Wasmをどの言語からでも呼び出せます。

Wasmの仮想マシンさえあればどのようなOS, CPU, さらにどのような言語(Wasmランタイムがあれば)からでもWasmが呼び出せることがわかりました。

ここまで読めば、「スタックベースの仮想マシン」が何を意味するのか理解できると思います。

3.1.3. 「バイナリ命令形式」

次に「バイナリ形式」の部分について簡単に解説します。

jsが呼んでいるcalculate.wasmの中身を見てみましょう。

xxdコマンドでバイナリファイルを16進数で表示してみます。

$ xxd calculate.wasm

00000000: 0061 736d 0100 0000 0108 0160 037f 7f7f  .asm.......`....
00000010: 017f 0302 0100 070d 0109 6361 6c63 756c  ..........calcul
00000020: 6174 6500 000a 0c01 0a00 2000 2001 2002  ate....... . . .
00000030: 6a6c 0b

これでは中身がさっぱりなので、専用のコマンドを使います。

$ wasm-objdump -s calculate.wasmを実行してバイナリファイルを読んでみましょう。

$ wasm-objdump --full-contents calculate.wasm

calculate.wasm: file format wasm 0x1

Contents of section Type:
000000a: 0160 037f 7f7f 017f                      .`......

Contents of section Function:
0000014: 0100                                     ..

Contents of section Export:
0000018: 0109 6361 6c63 756c 6174 6500 00         ..calculate..

Contents of section Code:
0000027: 010a 0020 0020 0120 026a 6c0b            ... . . .jl.

若干読めるようになりました。

この出力をWasmのバイナリフォーマットのドキュメントを参考にして読んでいきます。

このWasmのバイナリ命令フォーマットは、セクションがType, Function, Export, Codeに分かれています。

Codeの010a 0020 0020 0120 026a 6c0bを読んでみましょう。

ドキュメントにある命令のバイトコードのインデックスから以下のコードが読み解けました。

  • 0x20
    • local.get
    • 引数をスタックにpushする命令
  • 0x6a
    • i32.add
    • 2つのi32の加算をする命令
  • 0x6c
    • i32.mul
    • 2つのi32の乗算をする命令
  • 0x0b
    • 関数を終了する命令

これを使ってもう一度バイナリ命令フォーマットを読んでみましょう。

20 00 20 01 20 02で3つの引数(00, 01, 02)をスタックにpushしていることがわかります。

6aでスタックから2つ値をpopして加算しています。

6cでスタックから2つ値をpopして乗算しています。

0bで関数を終了しています。

先程、書いたwatファイルと同じ内容になってることが確認できました。

バイナリも触り程度ですが、概要を掴むことができました。

Wasmを示す「スタックベースの仮想マシンのためのバイナリ命令形式」という表現の意味がこれでわかるようになりました。

3.2. もっと面白いWasm

Wasmの説明が内部構造よりの話になってしまいましたが、これで説明は終わりです。

jsの限界速度よりも速く実行ができるので、フロントエンドのパフォーマンスチューニングで最後の手段みたいに使うと楽しいかもしれません。

実はWasmはもっと面白くて、コンパイラ言語に限らずどのような言語からでもWasmにコンパイルできたりなど、もっと深い話があります。実装する言語によっては同じ処理でも実行速度が違ったりします。例えばPythonで生成したWasmとRustで生成したWasmでは、RustのWasmの方が圧倒的に速いです。

あと、Wasmは、設計上、システムコールなどのユーザーランド外の処理はできないです。サンドボックス内の実行をしているので、セキュリティ的にも安心して使えると言ってもいいです。

もっとWasmには魅力がありますが、長くなるので一旦ストップします。

4. 終わり

RustとWasmのお話をしました。

実は、Wasmを書くならRustがまず第一候補に上がるくらい両方とも相性がいいです。

Rust + Wasmでコンテナ技術がなくなる...みたいな未来があったら楽しいですね。10年後の話かもしれません。

読みにくいオタクの早口みたいな記事になりましたが、書く作業は楽しかったです。

記事を読んでくださって、ありがとうございました。

解除したい実績

人生の可能性は無限大

夢は持つだけ持ったほうがいい。

夢というと遠そうだし叶えられなかった場合に悲しいので「実績」という表現で達成したいことを並べる。

実績名: 「刃渡り2億センチ」

日本列島*1一周のことです。

日本人として生まれたならやりたいよね。

実績名: 「最強のITエンジニア」

自分は大学で情報工学を学んでいるんだけど、ITの技術書を書きたい。それじゃなくても自分が開発したSNSとかがバズってザカバグになるのもいいよね。

多分、ITエンジニアなら誰でもそういう目標はあるよね。

実績名: 「それ、なんの訳に立つの?」

マイナー資格を100個獲得したいです。

雑談に強くなりそうだし。

実績名: 「パワー!!!!!!!!!!!」

フィジークとか出るの男の夢ですよね。

今ぽよんぽよんだけど、やってみたい。一応自重筋トレしてて順調に停滞しています。

実績名: 「Sing Sing Sing」

カラオケに自分の曲を出したい。

作曲とかしたことないけど、歌われる曲を作ってみたいよね。

実績名: 「漢の夢」

グラビアアイドル*2と付き合いたいです。空に向かって「俺はグラビアアイドルと付き合っている!!」と叫びたい。

実績名: 「世界一ィィィ!!」

なんらかの方法でギネスを取りたいです。意外と簡単に取れそうなやつもあって、例えば同じ誕生日の人が同じ場所に集まる人数のギネス記録*3とか「228人」で比較的簡単そう。

実績名: 「画伯」

自分の絵を100万円以上の値打ちで売りたい。オークションとかでよくわからん単色の背景の絵が結構高い金額で売買されているの見ると私もワンチャンとなっちゃいますよね。

*1:2億センチくらいあるらしい

*2:ちなみに著者の好きなグラビアアイドルは「東雲うみ」さんです。彼女は芸術の領域にいます。

*3:https://www.guinnessworldrecords.jp/world-records/largest-same-birthday-gathering

ハッカーズチャンプルー2023に登壇した

日記

TL;DR

ハッカーズチャンプルー2023にレギュラー枠(25分)で登壇しました。自作DBについて話しました。沖縄で関わったエンジニアに自分の成長を見せることができて大変よかったです。

きっかけ

ハッカーズチャンプルーが4年ぶりに開かれるということをX(Twitter)で知ったのがきっかけで登壇を応募しました。

テーマ

テーマは自作DBです。

自作CPU、自作OS、自作ブラウザ、自作プロトコルスタックくらいはよく耳にしますが、自作DBって結構ニッチですよね? 絶対おもしろい発表にして自作DBを布教してやろうという気概でした。

準備 (初期段階)

プロポーザルが採択されるかわからない段階ですでに準備は始めていて、9月はじめからコードを書き始めました。

自作するDBはほぼ経験がないRustで実装することにしました。

参考にするDBのアーキテクチャはSimpleDBです。

コードを書き始めて1日で1コンポーネントを書き上げて走り出し好調なスタートでした。

準備 (中盤)

transactionの実装が鬼でした。開発期間1ヶ月間の約1/4を占める1週間をこのコンポーネント1つにかけてしまいました。

参考にしているSimpleDBのアーキテクチャとRustの厳密な言語ルールが矛盾してしまっているのが原因でした。(詳細はスライドを参考にしてください。)

transactionをやっと実装し終えてDBの実装の3分の1が終わった段階で、ハッカーズチャンプルーまであと2週間という段階...。

準備 (終盤)

残りの3分の2を実装するにあたって、途中で丁寧につけていたドキュメントとエラーハンドリングはやめて、ただただ脳死でテストと実装を書きました。

14000行のRust製DBができました。その名もOxideDB、Rustの錆->酸化物から取りました。

なんとか完成してやっとこさスライド作成をしようとしたのが、発表前日、おいおい。

研究室の先生が夜中までスライド作成のサポート、プレゼン発表のFBをしてくださって助かりました。ありがとうございました。

結果、1徹状態でハッカーズチャンプルーを迎えることになりました。

発表当日

発表当日、会場につくと、研究室の先生、お世話になった先輩達、元バ先の社員さん達と社長など、沖縄で僕がお世話になったエンジニアが大勢いました。

これが僕の「集大成」...。

僕の全力のエンジニアリングは、多分この人達に伝わってくれたと思う。楽しかったな...。

発表ではスライドだけの説明だけじゃなくて、最後に自作DBを走らせるデモも行いました。

発表のデモで、自作したDBのSQLクエリが正しく実行されたときの会場のみなさんのリアクションが嬉しかったです!!!!

みんなの反応

ツイッターでのリアクションも折角なので貼っていこう(拾えきれていなかったらすみません)

振り返ってみて

ハッカーズチャンプルー2023の経験は忘れることはできないと思う。

これからのエンジニア人生の励みになる素晴らしい経験になりました。

運営のスタッフのみなさま、僕の発表を見てくれた方々(先生、元バ先の人達、先輩、同期、後輩、あとそこのあなた!!)、ありがとうございました。