RustでDBを自作しよう！！

概要

以下の一般的なRDBMSのアーキテクチャの3～6の部分を実装をする。

機能	説明	実装有無
構文解析器	SQLを解析	×
クエリプランナ	実行計画作成	×
クエリエクスキュータ	実行計画に従いアクセスメソッドを呼び出し	○
アクセスメソッド	データ構造をたどりクエリエクスキュータの要求通り結果を返す（B+Treeを利用）	○
バッファプールマネージャ	データをメモリにキャッシュ	○
ディスクマネージャ	データをディスクに書込＆データをディスクから読込	○

構文解析器や実行計画作成ないのにどうやって実行するの？
→ SQLではなく、クエリエクスキュータを実行する

元ネタ

元ネタは以下
WEB+DB PRESS Vol.122の特集「Rustで実装！作って学ぶRDBMSのしくみ」

上記の雑誌を参考に記載しています
なるべく一般的な内容＆公開されているプログラムコードから判断できることのみを記載しています
詳細な説明を知りたい場合は、雑誌を買いましょう！！めちゃくちゃ良い巻の認識！！

環境構築

DBの作成にあたり環境構築を行う

Visual Studio C++ Build toolsのダウンロード＆インストール

Rustを使いはじめるには、Visual Studio C++ Build toolsが必要なので、以下のURLからダウンロード
https://visualstudio.microsoft.com/visual-cpp-build-tools/

「C++によるデスクトップ開発」にチェックを入れ、インストール

Rustをダウンロード＆インストール

以下のURLからRUSTUP-INIT.EXE(64-BIT)をダウンロード
https://www.rust-lang.org/ja/learn/get-started

rustup-init.exeを実行
※デフォルトの設定でインストール

コマンドプロンプトで以下を実行してバージョンが確認できれば成功

C:\>rustc --version
rustc 1.58.1 (db9d1b20b 2022-01-20)

visual studio codeをダウンロード＆インストール（任意）

以下からイントーラーをダウンロードして、画面に従ってインストール（任意）
https://code.visualstudio.com/download
※デフォルトの設定でインストール

コード補完の拡張機能（rust-lang.rust）をインストール（任意）

デバックの拡張機能（vadimcn.vscode-lldb）をインストール（任意）

実装（というか配置）

githubの
https://github.com/KOBA789/relly
をクローンorダウンロードしてきて配置

main.rsがなく、lib.rsなので、ライブラリとして作成されていますね

visual studio codeを起動し、C:\dev\relly-wdbフォルダをOPENする

ディスクマネージャはどのソース？

・以下がディスクマネージャの実装
https://github.com/KOBA789/relly/blob/wdb/src/disk.rs

・ポイント
ファイルは、ヒープファイル構造
ファイルの読み書きしている
※ヒープファイル（ファイルをページと呼ばれる固定の長さごとに区切る）

//ページ単位は4K
pub const PAGE_SIZE: usize = 4096;

//構造
pub struct DiskManager {
    heap_file: File,
    next_page_id: u64,
}

impl DiskManager {
    pub fn new(heap_file: File) -> io::Result<Self> {
        let heap_file_size = heap_file.metadata()?.len();
        let next_page_id = heap_file_size / PAGE_SIZE as u64;
        Ok(Self {
            heap_file,
            next_page_id,
        })
    }

    //省略

    // 読んだり
    pub fn read_page_data(&mut self, page_id: PageId, data: &mut [u8]) -> io::Result<()> {
        //省略
    }

    // 書いたり
    pub fn write_page_data(&mut self, page_id: PageId, data: &[u8]) -> io::Result<()> {
        //省略
    }

    //省略

バッファプールマネージャはどのソース？

・以下がバッファプールマネージャの実装
https://github.com/KOBA789/relly/blob/wdb/src/buffer.rs

・ポイント1
ディスクの内容をメモリ上にキャッシュすることで、ディスクの遅さを回避
キャッシュになかったら、ディスク読み込む

//構造
pub struct BufferPoolManager {
    disk: DiskManager,
    pool: BufferPool,
    page_table: HashMap<PageId, BufferId>,
}

impl BufferPoolManager {
    pub fn new(disk: DiskManager, pool: BufferPool) -> Self {
        let page_table = HashMap::new();
        Self {
            disk,
            pool,
            page_table,
        }
    }

    pub fn fetch_page(&mut self, page_id: PageId) -> Result<Rc<Buffer>, Error> {
        //キャッシュにある場合
        if let Some(&buffer_id) = self.page_table.get(&page_id) {
            let frame = &mut self.pool[buffer_id];
            frame.usage_count += 1;
            return Ok(Rc::clone(&frame.buffer));
        }
        //キャッシュにない場合
        let buffer_id = self.pool.evict().ok_or(Error::NoFreeBuffer)?;
        let frame = &mut self.pool[buffer_id];
        let evict_page_id = frame.buffer.page_id;
        {
            let buffer = Rc::get_mut(&mut frame.buffer).unwrap();
            if buffer.is_dirty.get() {
                self.disk
                    .write_page_data(evict_page_id, buffer.page.get_mut())?;
            }
            buffer.page_id = page_id;
            buffer.is_dirty.set(false);
            self.disk.read_page_data(page_id, buffer.page.get_mut())?;
            frame.usage_count = 1;
        }
        let page = Rc::clone(&frame.buffer);
        self.page_table.remove(&evict_page_id);
        self.page_table.insert(page_id, buffer_id);
        Ok(page)
    }

    //省略

・ポイント2
どのバッファを捨てるかのアルゴリズムはClock-sweepを利用
※Clock-sweepはポスグレでも採用されている
※くるくる回して、いらないキャッシュを探索

    fn evict(&mut self) -> Option<BufferId> {
        let pool_size = self.size();
        let mut consecutive_pinned = 0;
        // くるくる回しまーす
        let victim_id = loop {
            let next_victim_id = self.next_victim_id;
            let frame = &mut self[next_victim_id];
            // バッファの利用回数0の場合
            if frame.usage_count == 0 {      
                // いらないキャッシュのバッファIDを返却
                break self.next_victim_id;
            }
            if Rc::get_mut(&mut frame.buffer).is_some() {
                frame.usage_count -= 1;
                consecutive_pinned = 0;
            } else {
                consecutive_pinned += 1;
                //捨てられるバッファがない場合
                if consecutive_pinned >= pool_size {
                    return None;
                }
            }
            self.next_victim_id = self.increment_id(self.next_victim_id);
        };
        Some(victim_id)
    }

アクセスメソッドはどのソース？

・以下がアクセスメソッドの実装
https://github.com/KOBA789/relly/blob/wdb/src/btree.rs

・ポイント
B+Treeをアルゴリズムとして利用
B+Treeの実装は難しいので、以下で概念を理解するのが良さそう
https://qiita.com/kiyodori/items/f66a545a47dc59dd8839

・サンプル

以下にB+Treeの動作確認の為、サンプルあり
C:\dev\relly-wdb\examples

B+Treeにデータ挿入するコード

C:\dev\relly-wdb>cargo run --example btree-create

B+Treeのデータを検索

C:\dev\relly-wdb>cargo run --example btree-query
   Compiling relly v0.1.0 (C:\dev\relly-wdb)
    Finished dev [unoptimized + debuginfo] target(s) in 1.12s
     Running `target\debug\examples\btree-query.exe`
[48, 79, 6f, 67, 6f] = [4b, 6f, 62, 65]

他にも色々なサンプルコードあり

クエリエクスキュータはどのソース？

・以下がクエリエクスキュータの実装
https://github.com/KOBA789/relly/blob/wdb/src/query.rs

・ポイント
クエリエクスキュータは、さまざまな種類（今回は、シーケンススキャン、フィルター、インデックススキャン）がある
このクエリエクスキュータの組み合わせ方を定義するのが実行計画

クエリエクスキュータの例（フィルター）
くるくる回して、条件に合致するか判別

impl<'a> Executor for ExecFilter<'a> {
    fn next(&mut self, bufmgr: &mut BufferPoolManager) -> Result<Option<Tuple>> {
        // データくるくる
        loop {
            match self.inner_iter.next(bufmgr)? {
                Some(tuple) => {
                    // 条件に一致した場合
                    if (self.cond)(&tuple) {
                        return Ok(Some(tuple));
                    }
                }
                None => return Ok(None),
            }
        }
    }
}

実行計画の例（フィルター）

impl<'a> PlanNode for Filter<'a> {
    fn start(&self, bufmgr: &mut BufferPoolManager) -> Result<BoxExecutor> {
        let inner_iter = self.inner_plan.start(bufmgr)?;
        Ok(Box::new(ExecFilter {
            inner_iter,
            cond: self.cond,
        }))
    }
}

クエリエクスキュータを実行してみる

・以下が実装例
https://github.com/KOBA789/relly/blob/wdb/examples/simple-table-plan.rs

・ポイント
SeqScanをFilterで入れ子にして、select * 省略 where id >= 'w' and id < 'z' and first_name < 'Dave'
を表現している

fn main() -> Result<()> {
    let disk = DiskManager::open("simple.rly")?;
    let pool = BufferPool::new(10);
    let mut bufmgr = BufferPoolManager::new(disk, pool);
    //　フィルター
    let plan = Filter {
        // 検索条件
        cond: &|record| record[1].as_slice() < b"Dave",
        // シーケンススキャン
        inner_plan: &SeqScan {
            table_meta_page_id: PageId(0),
            // 検索条件
            search_mode: TupleSearchMode::Key(&[b"w"]),
            while_cond: &|pkey| pkey[0].as_slice() < b"z",
        },
    };
    let mut exec = plan.start(&mut bufmgr)?;

    while let Some(record) = exec.next(&mut bufmgr)? {
        println!("{:?}", tuple::Pretty(&record));
    }
    Ok(())
}

事前作業（テーブル作成＆データ挿入）

C:\dev\relly-wdb>cargo run --example simple-table-create

実行

C:\dev\relly-wdb>cargo run --example simple-table-plan
   Compiling relly v0.1.0 (C:\dev\relly-wdb)
    Finished dev [unoptimized + debuginfo] target(s) in 1.19s
     Running `target\debug\examples\simple-table-plan.exe`
Tuple("x" [78], "Bob" [42, 6f, 62], "Johnson" [4a, 6f, 68, 6e, 73, 6f, 6e])
Tuple("y" [79], "Charlie" [43, 68, 61, 72, 6c, 69, 65], "Williams" [57, 69, 6c, 6c, 69, 61, 6d, 73])