Open2021/05/10にコメント追加8

作って学ぶRDBMSのしくみ実践メモ

これは何?

WEB+DB PRESS Vol.122 で特集されていた「自作ミニRDBMS」の記事を読みすすめ、時に脱線した際のメモを Work Log として残しています。

私は Rust 入門者なので、前半は開発環境の整備〜Rust の言語自体についての記載が多いです。ミニRDBMS に関する点はだいぶ後ろのほうになるかと思います（脱線しすぎ）。

Rust での開発環境の整備

Rustプログラミング言語サイトに沿って環境構築する。おすすめされている以下のコマンドをたたいて rustup を使う。

$ curl --proto '=https' --tlsv1.2 -sSf https://sh.rustup.rs | sh

コマンドが無事実行されたのを見届けたあとに ~/.cargo/bin を PATH に追加する

PATH=~/.cargo/bin:$PATH

最後に無事インストールされたことを確認する

$ cargo --version
cargo 1.51.0 (43b129a20 2021-03-16)

ゴミ人間

Rust での Hello, World!

Cargo Book に従って Hello, World! くらい済ませておく

$ cd /tmp
$ cargo new hello_world
$ cd hello_world
$ tree
.
├── Cargo.toml
└── src
    └── main.rs

$ cat src/main.rs
fn main() {
    println!("Hello, world!");
}

$ cargo build
   Compiling hello_world v0.1.0 (/private/tmp/hello_world)
    Finished dev [unoptimized + debuginfo] target(s) in 10.05s
hello_world (master) $ cat src/main.rs
fn main() {
    println!("Hello, world!");
}
$ ./target/debug/hello_world
Hello, world!

$ cargo run
    Finished dev [unoptimized + debuginfo] target(s) in 0.05s
     Running `target/debug/hello_world`
Hello, world!

ゴミ人間

Visual Studio Code ので開発環境整備

ここで紹介されていた rust-analytizer というものが便利だった

ゴミ人間

Rust の文法確認

Introduction - Rust By Example 日本語版を見ながら Rust の基本文法をおさらいする

変数

変数はデフォルトでイミュータブル
ミュータブルにしたい場合は mut キーワードを用いる

let x = 1;
// x = 2;  => Error

let mut y = 1;
let y = 2;

例えば標準入力からデータを受け取る io::stdin.read_line は引数に mut &String をとる

let mut input = String::new();
io::stdin().read_line(&mut input).expect("Error");
println!("Input value: {}", input);

関数とテスト

関数は fn キーワードで定義できる
- 明示的な return は必要なく、最後に評価された式が返却される
テストは同一のファイルに記述できる

pub fn add(a: u64, b: u64) -> u64 {
    a + b
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_add() {
        let value = add(1, 2);
        assert_eq!(value, 3);
    }
}

配列とタプル

コンパイル時にサイズが決定される配列がある
Tuple が標準の言語機能として存在する

let xs: [i32; 2] = [1, 2];
println!("{}", xs.len()); //=> 2

let a = (1, 2);
let b: i32 = a.0 + a.1;
let c: i32 = b.pow(2);

構造体・列挙体・定数

カスタム型は構造体 struct と列挙型 enum として定義できる
定数は const あるいは static というキーワードで定義できる

// Unit
struct Nil;
let _nil = Nil;

// Named Tuple
struct Pair(i32, i32);
let pair = Pair(1, 2);

// Classical Struct
struct Point {
    x: f32,
    y: f32,
}
let p = Point { x: 0.1, y: 0.2 };

// Enum
enum Event<T> {
    Next(T),
    Error,
    Complete,
}
impl<T> Event<T> {
    fn echo(&self) {
        match self {
            // Self は Event の type alias
            Self::Next(_) => println!("Next"),
            Self::Error => println!("Error"),
            Self::Complete => println!("Complete"),
        }
    }
}

struct や enum などは実装（メソッド）を持てる
メソッドのインターフェースを定める trait という言語機能もある

struct Adder {
    a: u32,
    b: u32,
}

impl Adder {
    fn new(a: u32, b: u32) -> Self {
        Adder { a, b }
    }

    fn calc(&self) -> u32 {
        (*self).a + (*self).b
    }
}

fn main() {
    let x = Adder::new(1, 3);
    println!("1 + 3 = {:?}", x.calc());  //=> 4
}

インスタンスメソッドの引数 self には次の 3 つの種類がある
- &self: インスタンスメソッド
- &mut self: 該当のオブジェクトがミュータブルである必要のあるインスタンスメソッド
- self: オブジェクトのリソースを消費するインスタンスメソッド

struct Counter {
    value: u32,
}

impl Counter {
    fn new() -> Self {
        Counter { value: 0 }
    }

    fn add(&mut self) {
        self.value += 1;
    }

    fn peek(&self) -> u32 {
        self.value
    }

    fn destory(self) {
        // do nothing
    }
}

fn main() {
    let immutable_counter = Counter::new();
    println!("count: {:?}", immutable_counter.peek());
    // immutable_counter.add(); => ERROR
    // ミューテーションを起こすメソッドをコールするためには変数を let mut で宣言する必要がある
    // ただしオブジェクトの所有権を受け渡すような操作は受け付ける
    immutable_counter.destory();
    // println!("count: {:?}", counter.peek()); => moved out したあとのオブジェクトは操作できない

    let mut counter = Counter::new();
    println!("count: {:?}", counter.peek());
    counter.add();
    println!("count: {:?}", counter.peek());
    counter.add();
    println!("count: {:?}", counter.peek());
    counter.add();
    println!("count: {:?}", counter.peek());
    counter.destory(); //=> `counter` moved due to this method call
    println!("count: {:?}", counter.peek()); //=> Error: this function takes ownership of the receiver `self`, which moves `counter`
}

Box

Rust はすべての値をデフォルトでスタックに割り当てる
Box<T> を作成することにより値をヒープに割り当てられる
- これはヒープ上に置いている T の値への単なるスマートポインタ
- スコープを抜けるとデストラクタがコールされてヒープメモリが解放される
- オペレータ *によりデリファレンスできる

fn main() {
    let boxed_number: Box<u128> = Box::new(1);
    let number: u128 = *boxed_number;
    println!("size: {:?}", mem::size_of_val(&boxed_number)); //=> size: 8(ポインタのサイズ)
    println!("size: {:?}", mem::size_of_val(&number)); //=> size: 16(128 bit = 8 bit * 16)
}

クロージャ

ゴミ人間

Rust における LinkedList の実装

Introduction - Learning Rust With Entirely Too Many Linked Lists を参考に概要をメモっていく

再帰的な構造を持つ `enum`, `struct`

再帰的な構造を持つ enum, struct はそのサイズがコンパイル時に定まらず、エラーとなる

pub enum List {
    Empty,
    Elem(i32, List),
}

Box<T> はヒープ上に置かれた T の値へのスマートポインタを表すため、これを用いるとコンパイル時にその構造体や列挙型のサイズは定まる（なぜなら参照先のデータに依存せず、そのポインタのサイズは固定長であるから）

#[derive(Debug)]
pub enum List {
    Cons(i32, Box<List>),
    Nil,
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn it_works() {
        println!("{:?}", List::Nil);  //=> Nil
        println!("{:?}", List::Cons(1, Box::new(List::Nil)));  //=> Cons(1, Nil)
    }
}

この構造の問題点は以下の2つだが、一見すると 1 と 2 でプラマイゼロのように見える

末尾を表すだけのノード Nil にヒープを割り当てている
先頭のノードだけスタックに積まれている

この構造は一見問題なさそうに見えるが、下記のようにリストを分割・結合する際に B の next を null に書き換えたのち、C をスタックにコピーしなくてはならないず、無駄が生じる（なるほど）

[] = Stack
() = Heap

[Elem A, ptr] -> (Elem B, ptr) -> (Elem C, ptr) -> (Empty *junk*)

split off C:
[Elem A, ptr] -> (Elem B, ptr) -> (Empty *junk*)
[Elem C, ptr] -> (Empty *junk*)

単純に Node が必ずヒープに配置されるような構造に書き換えた場合、以下のように B の next を null 書き換え、新しいポインタが C を指すように変更すれば済む（なるほど！）

[ptr] -> (Elem A, ptr) -> (Elem B, ptr) -> (Elem C, *null*)

split off C:
[ptr] -> (Elem A, ptr) -> (Elem B, *null*)
[ptr] -> (Elem C, *null*)

とはいえ、空のリストはそもそもヒープを確保する必要がないのだから、根本的にリストは「空のリスト」か「要素を持つリスト」に分類できる。

「空のリスト」はノードを持たない、「要素を持つリスト」は値と後続のリストというデータからあるノードを持つ。

List:
[Empty]
[More(&Node)] -> Node(Elem A, List)

このような構造をコードに落とすと以下のように表現できる。また、このときの List 列挙体は後述の null pointer optimization という仕組みにより型のサイズがコンパクトになる。

#[derive(Debug)]
pub struct Node {
    elem: i32,
    next: List,
}

#[derive(Debug)]
pub enum List {
    Empty,
    More(Box<Node>),
}

ところで通常のリストの実装においては Node は外部に公開したくない。そこで pub を消し去るという安直な手がすぐに思い浮かぶと思う。

しかしながら List は pub な列挙体であり、かつ列挙体はその性質上、アイテムのインターフェースを外部に公開しなければならないため、要素のひとつである More(Box<Node>) と整合しなくなり、コンパイラからの警告が発生する。

warning: private type `Node` in public interface (error E0446)
  --> src/first.rs:10:10
   |
10 |     More(Box<Node>),
   |          ^^^^^^^^^
   |
   = note: `#[warn(private_in_public)]` on by default
   = warning: this was previously accepted by the compiler but is being phased out; it will become a hard error in a future release!
   = note: for more information, see issue #34537 <https://github.com/rust-lang/rust/issues/34537>

その一方で、構造体であればマークしない限りフィールドは外部に公開されないため、LIst を構造体にして、これまで定義していた列挙体ごと隠蔽してあげる形をとれば無事解決となる。

#[derive(Debug)]
struct Node {
    elem: i32,
    next: List,
}

#[derive(Debug)]
enum Link {
    Empty,
    More(Box<Node>),
}

#[derive(Debug)]
pub struct List {
    head: Link,
}

また、このとき List はひとつのフィールドしか持たず、この構造体のサイズはフィールドである head、つまり Link 列挙体と同じサイズになる。これはゼロコスト抽象化の一例。

let xs = List { head: Link::Empty };
let ys = List {
    head: Link::More(Box::new(Node {
        elem: 1,
        next: List { head: Link::Empty },
    })),
};

println!("{:?}", xs);  //=> List { head: Empty }
println!("{:?}", ys);  //=> List { head: More(Node { elem: 1, next: List { head: Empty } }) }

列挙体がどのようにメモリ上に配置されるか

以下のような enum を定義したとき、どのタグ（D1〜Dn）であるかというフラグと、各タグにおけるデータ（T1〜Tn のうち最も大きいサイズ）を格納する領域が必要となる。また、それに加えて alignment の要件を満たす必要がある。

enum Hoge {
    D1(T1)
    ...
    Dn(Tn)
}

このあたりの細かい解説は repr(Rust) にとても丁寧に記載されている。

ところで、次のような enum があったとする。

enum Option<&T> {
    None,
    Some(&T),
}

この場合、最低限タグとポインタを格納する領域が必要となる。しかし、&T はポインタであり決してゼロにならない。すると 0 埋めされているときに None、それ以外のときに Some であると解釈することも可能であり、このときタグを明示的に記憶しておく必要がない。

Rust ではこのようなケースにきちんと最適化を行ってくれるらしい。そのあたりの詳細は以下のページに詳しく書かれていてとても参考になる。今度、手元環境でもちゃんと検証してみたい。

簡単なメソッドの実装

List を作成する便利メソッド: new, from を生やす
[T] の head は first() -> Some(T)、tail は [1..] で取れる
- 配列が空の場合も [1..] は [] を返してくれる親切設計

impl List {
    pub fn new() -> Self {
        List { head: Link::Empty }
    }

    pub fn from(xs: &[i32]) -> Self {
        match xs.first() {
            Some(head) => List {
                head: Link::More(Box::new(Node {
                    elem: *head,
                    next: List::from(&xs[1..]),
                })),
            },
            None => List::new(),
        }
    }
}

is_empty, len を生やす
** is_empty は std::matches というベンリマクロを使うと簡単に書ける
Rust において self は self, &mut self, &self の 3 種類があり、独特なため訓練が必要
** len() の場合は &self が適切

impl Link {
    pub fn len(&self) -> u32 {
        match self {
            Link::Empty => 0,
            Link::More(node) => 1 + node.next.len(),
        }
    }
}

impl List {
    pub fn is_empty(&self) -> bool {
        matches!(self.head, Link::Empty)
    }

    pub fn len(&self) -> u32 {
        self.head.len()
    }
}

ミュータブルなメソッドの追加

リストの先頭に要素を追加する push の実装を試みる。他言語で書く場合と同じように脳死で書くと次のようなコードになりがち。

    pub fn push(&mut self, elem: i32) {
        let new_node = Node { elem, next: self };
        self.head = Link::More(Box::new(new_node))
    }

しかしこれはコンパイルできない。

（続く）

ゴミ人間

イミュータブルな単方向 Linked List の実装

enum List<T> {
    Cons(T, Box<List<T>>),
    Nil,
}

impl<T> List<T> {
    fn empty() -> List<T> {
        List::Nil
    }
}

ゴミ人間

Rust の Ownership と Borrowing について

次のようなコードは当たり前だが正常にコンパイルと実行が可能

fn main() {
    let stack_i32 = 1;
    let stack_i32_2 = stack_i32;
    println!("stack_i32: {:?}", stack_i32);
    println!("stack_i32_2: {:?}", stack_i32_2);
}

しかし他言語になれており、Rust をよくしらない人にとって次のようなコードのコンパイルに失敗するのは奇妙にみえる

fn main() {
    let heap_i32 = Box::new(1);
    let heap_i32_2 = heap_i32; //=> move occurs because `heap_i32` has type `Box<i32>`, which does not implement the `Copy` trait
    println!("heap_i32: {:?}", heap_i32); //=> value borrowed here after move
    println!("heap_i32_2: {:?}", stack_i32_2);
}

Rust には Ownership と Borrowing という概念があり、上記のコードのコンパイルエラーはこれらが関係している

Ownership はじめの一歩

Rust ではスタック/ヒープどちらにおいてもすべてのデータが Owner を持つ
各データとオーナーは常に一対一に対応する
- あるデータが同時に複数のオーナーを持つことはない
- この設計により Race Condition を防ぐ狙いがある
= により Ownership が move し、Ownership を明け渡した変数は以後操作できなくなる
スタック領域のデータはスコープを抜けた際に解放される
ヒープ領域のデータは allocate 時に束縛した変数の持つ Ownership を受け渡すことにより、スコープを超えて保持できるが、最後の Owner がスコープを抜けた際に解放される

前述のコードのエラーを解消する方法は以下の 2 通りある

データのクローン
Ownership の Borrow

1つ目の方法は元のデータの Ownership を渡すのではなく、複製したデータの Ownership を渡すというものだが、スタック領域に比べてヒープ領域におけるデータのクローンはコストが高い点に注意が必要

fn main() {
    let heap_i32 = Box::new(1);
    let heap_i32_2 = heap_i32.clone();
    println!("heap_i32: {:?}", heap_i32);
    println!("heap_i32_2: {:?}", heap_i32_2);
}

2つ目の方法は Borrowing というものでコードに落とすと単純に次のようなものとなるが、その概念については後ほど触れることにする

fn main() {
    let heap_i32 = Box::new(1);
    let heap_i32_2 = &heap_i32;
    println!("heap_i32: {:?}", heap_i32);
    println!("heap_i32_2: {:?}", heap_i32_2);
}

Borrowing はじめの一歩

スタックの変数はデフォルトでイミュータブルであり、関数のパラメタとして渡した時点でコピーされ、関数側のスコープで操作を加えても、元の変数に影響しない

fn main() {
    let stack_i32 = 1;
    do_something(stack_i32);
    println!("param: {:?}", stack_i32); //=> 1
}

fn do_something(mut param: i32) {
    param += 100;
    println!("param: {:?}", param); //=> 101
}

同様のことをヒープの変数に対して行うと次のような仕組みで println! の呼び出し前に heap_i32 が解放されてしまうコードとなるためコンパイルエラーが発生する

do_something_heap 関数のパラメタとしてヒープのデータ heap_i32 を渡すと、同時に Ownership も関数のスコープ側に渡る
do_something_heap 関数の実行が終わると、ヒープのデータの最後の Owner である param もスコープから抜けるためデータが解放される
main 関数の実行に戻り、println! を呼び出そうとしてもすでに heap_i32 が指すデータの Ownership は受け渡し済みであり、またそのデータ自体も解放済みとなっているため、コンパイル時にこれを検出してエラーが発生する

fn main() {
    let heap_i32 = Box::new(1);
    do_something_heap(heap_i32);
    println!("param: {:?}", heap_i32); //=> ERROR!: value borrowed here after move
}

fn do_something_heap(param: Box<i32>) {
    println!("param: {:?}", param);
}

例えば、関数にパラメータをクローンして渡せば、これは前述のスタックの例と同じ振る舞いになる

fn main() {
    let heap_i32 = Box::new(1);
    do_something_heap(heap_i32.clone());
    println!("param: {:?}", heap_i32);
}

fn do_something_heap(param: Box<i32>) {
    println!("param: {:?}", param);
}

ヒープ領域のデータのクローンはコストが高いため、クローンを行わず関数の戻り値にて Ownership を元のスコープに戻すという手法も考えられる

fn main() {
    let mut heap_i32 = Box::new(1);
    heap_i32 = do_something_heap(heap_i32);
    println!("param: {:?}", heap_i32);
}

fn do_something_heap(param: Box<i32>) -> Box<i32> {
    println!("param: {:?}", param);
    param
}

引数で複数のヒープの変数を受け取る関数を実装するときに前述の方法だと戻り値の型が大変なことになるため、Rust に用意されている Borrowing という機能をつかって次のようなコードで解決できる

fn main() {
    let heap_i32 = Box::new(1);
    do_something_heap(&heap_i32);
    println!("param: {:?}", heap_i32);
}

fn do_something_heap(param: &Box<i32>) {
    println!("param: {:?}", param);
}

ゴミ人間

ディスクマネージャの実装

プロジェクトの作成

$ cargo new my_rdbms
$ cd my_rdbms
$ touch ./src/disk.rs
$ code .

src/disk.rs に DiskManager を実装していく
実装コードはここ

これは何?

Rust での開発環境の整備

Rust での Hello, World!

Visual Studio Code ので開発環境整備

Rust の文法確認

変数

関数とテスト

配列とタプル

構造体・列挙体・定数

Box

クロージャ

Rust における LinkedList の実装

再帰的な構造を持つ enum, struct

列挙体がどのようにメモリ上に配置されるか

簡単なメソッドの実装

ミュータブルなメソッドの追加

イミュータブルな単方向 Linked List の実装

Rust の Ownership と Borrowing について

Ownership はじめの一歩

Borrowing はじめの一歩

ディスクマネージャの実装

再帰的な構造を持つ `enum`, `struct`