Write and Run

it's a simple way, but the only way.

WEB+DB PRESS Vol.122に特集「Rustで実装!作って学ぶRDBMSのしくみ」を書いた

f:id:koba789:20210408181437p:plain:w735

KOBA789 です。

時が経つのは早いもので、気づけば2月末に無職になってから1ヶ月以上が過ぎていました。

その間に何をしていたのかといえば、表題の特集記事の執筆をしていました。

宣伝

このブログ記事は WEB+DB PRESS Vol.122 を読みたくなるためのものです。ぜひ買ってね。買ったらちゃんと読んでね。

gihyo.jp

使用言語は Rust だし、RDBMS はそもそも難しいトピックだしで結構重めの内容ですが、まずは読み物として寝転びながらでもいいので読んでみてほしいです。

ゴールデンウィーク*1の自由研究のお供にもどうぞ。たぶんちょうどいい分量なんじゃないかなぁ。ゴールデンウィーク明けは自作 RDBMS を友人・同僚に自慢しましょう。

内容

タイトルのとおり、Rust で RDBMS を自作します。といっても主眼は RDBMS 自作ではなく、RDBMS の仕組みを知ることです。

作ろうとすると仕組みを知らざるをえないので、学びたいなら作りゃいいじゃんという理屈です。

実際の内容は下記目次を見てください。知ってる人が見ると「あれがない」「これがない」となりそうな目次ですが、まさか full-featured な RDBMS を学習目的で作るわけにはいかないのでご容赦ください。

目次: WEB+DB PRESS Vol.122|技術評論社

きっかけ

以下自分語り。

当ブログの以下の記事を見つけた WEB+DB PRESS の編集の方からお誘いの連絡をいただきました。些細なことでもブログに書いておくもんですね。

diary.hatenablog.jp

ちなみに、WEB+DB PRESS の特集記事で扱っている題材の RDBMS は、上記ブログ記事で取り上げている実装 qp とは別物です。

いくらかコードは流用していますが、WEB+DB PRESS 用に新規で書き下ろしています。発売に合わせてリポジトリを公開します。公開したらここにも追記しておきます。

追記: 先行販売にあわせてリポジトリを公開しました。

github.com

執筆

執筆は想像以上に大変で、想像より楽しかったです*2

実はこの規模の文章の執筆経験というのはあまりなく、しかも特集丸々ひとつを一人で考えて書かなきゃいけなかったので大変でした。

ある程度分量があると1日では書き切れないので作業が日を跨ぎます。するとモチベーションのコントロールが必要で、しかしこれは一人でやってるとどうにも難しい。

執筆自体は楽しくて、いつものノリで早口オタクを繰り広げたやつを文字にするだけでした。バーッと吐き出して、余計だなぁと思ったところを切り取るといった感じです。

吐き出すのはすごく楽しいですが、切り取るのは楽しくないですね。編集の方にいろいろ手伝ってもらいながらなんとか整えました。

感想

機会に恵まれたなぁと思います。私自身は極めて怠惰なので自発的に何かを成し遂げるということがなく、だいたいは大見得切ったばっかりに引くに引けなくなって最後までやることになるパターンです。

今回のように大見得切るチャンスをいただけると、自発的にはできないようなことを(結果的に)成せるのでありがたいです。

そういえば、かつて青木峰郎(前職の上司、って表現でいいのかな)に「ふつうの RDBMS」って本書いてくださいよ、と言ったことがありました。

結局未だに書いてくれてないんですが、どうしても読みたいので少しくらいは自分で書かないとダメかなと思って今回書いたみたいな経緯があります。

今後

発売めでたいハイ終わり、でもいいんですが、DBMS オタクとしてはまだまだ語り足りないことも多いのでどこかでまた吐き出せたらいいなと思っています。

DBMS フレンズがあまりいないので話したいことが溜まってるんですよね。無職になって一番困ってるのは DBMS の話をできる人間が近くにいなくなったことですし。

とにもかくにも飽き性なのですっかり忘れてるってこともありえますが、もし覚えてたらやっていきます。よろしくどうぞ。

追記2: YouTube にサンプルコードのデモを含む紹介動画を投稿しました。ゴールデンウィーク中は何本か追加で解説動画を公開していきます。こちらもよろしくどうぞ。 www.youtube.com

*1:無職は毎日ゴールデンウィークです

*2:編集の方には大変ご迷惑をおかけしました……

クックパッド株式会社を退職しました

タイトルの通りです。2月26日付でクックパッド株式会社を退職しました。有給は6時間しか余っていなかったので最終出社日=契約最終日です。

社内の人は社内ブログにもうちょいマシな記事を置いてきているはずなのでそちらを読んでください。

なんでやめたの?

改めて説明するのがダルいのであまり詳しく書きたくはないのですが、要らぬ邪推を避けるために書いておくと、少なくとも給与やオフィス移転などへの不満ではないです。

平たく言えば COVID-19 Situation に疲れたというやつです。

転職先は?

転職しません。無職をやります。

フリーランスやるんですか、ともよく聞かれるんですがフリーランスは無職ではありません。

しばらくはやりたいことをやって過ごそうかと思います。学びたいことはたくさんあるし。

最後に

元同僚のみなさんへ。改めて、本当にお世話になりました。

この狭い業界で、あるいはこの広い世界のどこかで、いつかまた互いの行く道が交わるときが来たのなら、そのときは仲良くしてくれると嬉しいです。

草草不一

クエリエクスキューターの気持ちになる

これは 自作DBMS Advent Calendar 2020 - Adventar 25日目の記事です。

LSM-Tree 実装するとか言ってたけど奥歯に穴が空くなどのインシデントがあり、できませんでした。

代わりと言ってはなんですが、簡単な Tuple-at-a-time 方式のクエリエクスキューターを書いてみたのでご紹介します。

github.com

実装した理由はもちろん自分の学習のためでもあるのですが、会社の同僚が MySQL のインデックスの貼り方で悩んでいるときにパッと説明用に取り出せる小さいコードが欲しかった、という背景があります。 そういうわけで今回は Rust ではなく Ruby で書いてみました。

クエリ実行にだけ焦点を当てたかったため、データはすべてナイーブなインメモリで書き込みなし、データ構造も B-Tree ですらなくて静的に構築されたただのソート済み配列です。

B-Tree もソート済み配列も検索の時間計算量は O(log(n)) であり、違うのは挿入と削除の時間計算量です。 DBMS の利用者的な観点で言えば、B-Tree は挿入と削除の時間計算量が O(n) ではなく O(log(n)) な魔法のソート済み配列とみなすことができます。

このような激しい割り切りにより、わずか200行程度で SeqScan, IndexScan, Limit, Sort の基本的なオペレーターと4種類の実行計画のサンプルコードを実装できています。この実装の小ささは Ruby の Enumerable の便利さも一役買っています。

これくらい短いコードであれば DBMS 初学者にもポンと渡して十分気軽に遊んでもらえるのではないかと思います。

サンプルコードのテストデータとして ISUCON9 予選問題のデータを利用しています。 参考実装からクエリを拾って、それを題材に適切なインデックスと実行計画を考える練習ができます(問題公開されてるのはマジで偉大)。

ISUCON の練習や MySQL の学習と称して布教をし、うっかりこちら側に足を滑らせてくれる人が増えないかなと目論んでいる次第です。

というわけで、Ruby 200行から始める DBMS 沼のご紹介でした。

Happy Holidays!

Amazonのコンテナホスト用OS「Bottlerocket」をなんとかして自宅サーバーで使う

id:koba789 です。

ここのところ B-Tree の話ばかり書いていたのでたまには別のネタを。

自宅サーバー管理めんどくさい問題

みなさん自宅にサーバーはありますか。
まぁ当然あると思うんですけど、管理めんどくさくないですか。私はめんどくさいなぁと思っています。

主に何がめんどくさいかといえば各種(たくさんの)パッケージの定期的なアップデートや構成管理だと思います。

Mutable な物体の管理はめんどくさい、Immutable なら毎度発破解体して作り直せばいいので気がラクでよい、というのがここ10年くらいのトレンドであり、ベアメタルにインストールする OS なんてのはコンテナが動けばそれで十分であって、コンテナの外のユーザーランドに余計なモノを置くのはジリープアー(徐々に不利)だということにみなさん薄々気づいているわけです。

私は10年くらい前からそのような事実に気づいていたので、当時から SmartOS というおもしろ OS を使っていたのですが、最近は開発元である Joyent の異常者CTO が辞めてしまって先行きが不安ということと、そもそもカーネルLinux ではないのでやはり互換性の面で不安というのがあり、使うのをやめていました。
というか Linux カーネルじゃないのに Linux の Docker イメージが動くってどういうことなんだマジで(こういうことらしいです)。

というわけで最近は RancherOS というやつを使っていたのですが、これがまたいまいち開発に元気がなくなってきてしまったので乗り換え先を探していました。
ちなみに、乗り換えるときも kube のマニフェストをスッとするだけでだいたい済むのはコンテナ OS のいいところですね。

乗り換え先 Bottlerocket

乗り換え先として Bottlerocket という OS に目をつけました。

aws.amazon.com

これは Amazon が開発しているコンテナホスト用 OS です。
いまのところは AWS 向けに開発が進んでいるため、EC2 以外の環境でそのまま動かすことはできません。
EC2 以外でも動かせるようにする計画はありそうなのですが、少なくとも現時点ではコードに手を入れるしかありません。 もっとも、ベアメタルで動かそうと思うと相応の苦しみがあります(後述)。

自宅で動くように改造する

SSH できるようにする

Bottlerocket では管理用のシェル環境すらもコンテナ内です。管理用コンテナには control と admin の2種類があります。

control は Bottlerocket の apiclient(ちょっと設定変更とかができる)を叩く用、admin はトラブル時にホストの ns に入ってトラブルシューティングをする用です。admin はデフォルトで無効化されており、control コンテナに入って有効化してはじめて起動します。

後者の admin コンテナのシェルへのアクセスは普通に SSH なのですが、前者の control コンテナのシェルへのアクセスは、セキュリティ上の理由から SSM(AWS Systems Manager Session Manager) を使うことになっています。
もちろんそんなもの(SSM)はおうちにないですし、apiclient は admin からでも叩けるので、自宅では control コンテナを使わないことにします。
常に admin コンテナを有効にしておくことになるのでセキュリティ的には弱くなりますが、自宅に SSH 以上のセキュリティを求めるのは難しいので諦めます。

で、この admin コンテナの ssh に使う公開鍵はオリジナルだと IMDS から取得することになっているのですが、これもまたおうちにはないので使わないこととし、代わりに公開鍵をコンテナイメージに焼き込みます。

これで SSH 可能になりました。

パッチはこんな感じ。

github.com github.com

ouchi(おうち)。アウチではない。

アップデートを配るリポジトリを用意する

さて、ここまでで自宅の VM で起動するようにはなっています。しかしアップデートは動きません。

Bottlerocket は TUF 準拠の仕組みでアップデートを行います。
オリジナルの Bottlerocket は S3 にある TUF Repository でアップデートを配っているのですが、私はカスタムビルドのアップデートを配らねばならないため、別途専用のリポジトリが必要です。

私は minio を使って自宅のネットワーク内に構築しました。

ベアメタルで動くようにする

ここからが本当の地獄です。

Bottlerocket のカーネルには、 EC2 の VM インスタンスまたはベアメタルインスタンスで動くのに十分なドライバしか含まれていません。

さらに悪いことに initrd や initramfs を使わないブートシーケンスを採用しているため、rootfs をマウントするまでに必要なドライバはモジュールにしてはいけません。

足らない場合、rootfs のマウント前にブートがコケて止まるわけなので調査は困難を極めます。ログをビデオカメラで撮影して追いかけるなどのテクが必要になります(シリアルコンソールを使え)。

最終的にうちのサーバーで起動させるのに必要な kernel config は以下のパッチのようになりました。

github.com

Bottlerocket は AmazonLinux 2 ベースなので、docker で amazonlinux:2 を起動してその中で make menuconfig するのが便利だと思います。

config を足してはビルドして、USB メモリに焼いてサーバーに刺して電源 ON、そしてブートが途中で止まる、というようなことを5億回くらいやりました。MegaRAID は許さん。

まとめ

とりあえず起動して SSH が通るところまではできました。
しかしまだ admin コンテナが起動するだけで、kubelet が不在の状態なので使い物になりません。

ここまで来ればあとは普通の Linux なのでなんとか常用するところまでもっていきたいですね。

B-Treeを図示するときの細かいテクニック

これは 自作DBMS Advent Calendar 2020 - Adventar の12日目の記事です。
自作 DBMS ネタというか、課題で B-Tree を書かされてる学生向けって気もしますが、いずれにせよ誰かの役に立つと信じて。

Disk-Oriented な DBMS で欠かせないデータ構造といえば B-Tree です。 で、そのデータ構造をちゃんと把握するには図示が有効なわけですが、これがまた大変というか、理解のために書いてるのに理解してないからうまく書けなくて余計混乱するという悪循環に陥りがちなわけです。

というわけでこの記事では B-Tree を図示するときの細かいテクニックをご紹介します。 (ボケーっとしながら書いたら真の B-Tree と B+Tree が混ざってしまった。適当に脳内で補完して読んでください)

ノードはキーと値(ポインタ)の2階建てにする

素朴に実装する場合、キーと値のペアの構造体を配列で持ったものをノードすると思います。
Rust で書くとこんな感じ。

struct Pair {
    key: K,
    value: V,
}

struct Node {
    pairs: Vec<Pair>,
}

こうすると、メモリ上では キー, 値, キー, 値, … という風にキーと値が交互に並ぶわけですが、これをそのまま図にするのはおすすめできません。
眺めているうちにどれがキーでどれが値だかわからなくなるからです。

そこで、キーと値を分けて2階建にします。こんな感じ。

f:id:koba789:20201211235116p:plain
2階建てにする

左上の斜線が入っている部分は使わないキーのフィールドです。 B-Tree のノードでは必ず値の個数がキーの個数より1個多くなりますから、素朴にペアを交互に並べた場合は必ずどこかに余りが出ます。
この使わない余りを右端にするか左端にするか悩むところですが、おすすめは左端です。
その理由については、図示のテクニックというより実装のテクニックなので今回は省略します。またの機会に。 (2分探索でもさらにもう一本書けるんじゃないか)

一番左の矢印は子ノードの右上に、それ以外は左上に

先程の図で、値のフィールドにキーとの不等式(?)が書いてあったのに気が付いたでしょうか。 キーの直下のポインタの先にあるノードのキーはいずれもそのキー以上であり、キーの左下のポインタの先にあるノードのキーはいずれもそのキー未満である、という意味です。 この関係を矢印に反映させることで混乱を減らせます(主観)。

f:id:koba789:20201212005005p:plain
キーの大小関係を意識して矢印を引く

ルートノードの一番左のポインタ、つまり未使用キーの下から伸びる矢印は一番左のノードの右上を指すようにします。 「一番左のノードには5未満のキーしかない」ことをわかりやすくするためです。
もちろん、メモリ上のアドレス的には左のノードの先頭のキーのあたりを指しているんですが、この場合そっちに忠実になるよりはキーの大小関係に着目したほうがわかりやすいと思います(個人差があります)。

それ以外の矢印については ノードの左上を指しましょう。こちらも決してノードの真上とかを指さないように。

このようにすると、木が B-Tree の要件を満しているかどうかを素早く判断できるようになります。
矢印の向きがそのままキーの大小関係になっているため、左向きの矢印の先でキーが大きくなっていないか、右向きの矢印の先でキーが小さくなっていないかを確認するだけで済みます。簡単ですね。

まとめ

というわけで今回は超小ネタを紹介しました。
もちろん図示の仕方はこれだけが正解ではありません。ぜひ自分にあった作図の方法を探ってみてください。

今回紹介できなかったノードの構造のパターンや2分探索のパターンなどはまた後日気が向いたときに記事にします。アドベントカレンダーにはまだたくさんの空欄がありますからね!

ではまた。

B+Treeのページレイアウトと可変長タプル

これは 自作DBMS Advent Calendar 2020 - Adventar 1日目の記事です。

初日からギリギリで大丈夫なんですかねぇ(主催者)。

先日こういう記事を書きました。

Rustで古典的なDisk-Oriented DBMSを実装した話 - Write and Run

その中で、

このあたりで固定長のページをノードとした B+Tree に、可変長のデータを入れようとすると途端に実装が面倒になることに気が付きます。 と書いたのですが、具体的にどう面倒になるのかについてはなにも説明しませんでした。 今回は固定長のページに可変長のタプルを入れるとなにがどう面倒なのかという話を解説します。

テーブルヒープにおける可変長タプル

まず、B+Tree ではなく単純なテーブルヒープを考えます。 PostgreSQL のテーブルデータなどがそういう実装ですね。

これは CMU の例の講義で説明されています。

03 - Database Storage I (CMU Databases Systems / Fall 2019) - YouTube

可変長のタプルはページの末尾に詰め、そこの各タプルへのポインタをページの頭に詰めるという方法です。 Slotted pages などと呼ばれているデータ構造です。 ポインタは固定長なので、インデックスを用いて可変長のタプルへ O(1) でアクセスできるようになります。 こうすると1ページあたりに入るタプルの数はそこに入るタプルのサイズによってまちまちになりますが、テーブルヒープではこれは問題になりません。

B+Tree のリーフノードにおける可変長タプル

続いて、B+Tree のリーフノードに可変長のタプルを入れる事を考えます。 インメモリで実装される B+Tree ではノードあたりのタプル数を固定にすることが多いですが、前述のとおり固定長のページをリーフノードとする場合はタプル数を固定にできません。 B+Tree にはノード分割という操作があるため、この性質が厄介なことを引き起こします。 タプル数固定のノードの分割ではタプル数が1/2になるように分割すればよく、またタプル数を1/2にしたノードには1つは必ずタプルを追加できるため困ることはありません。 固定長ページ・要素数可変のノードの分割では、分割によって作られた新しいノードに含まれるタプルの合計サイズが元のノードのそれをちょうど超えるように分割し、新規に挿入するタプルは元のノードの方に追加します。

さて、ここで問題になるのは「分割後のノードの空き容量は挿入するタプルに対して十分か」ということです。 最悪の場合、せっかく分割したのに結局入らないということになりかねません。

これを解決する最も簡単な方法は、ノードに含められるキャパシティの半分のサイズをタプルのサイズの上限とすることです。 こうすることで、分割後のノードには必ずタプルを追加できるようになります。 InnoDB などもこのようになってますね。

二分探索と slotted pages

Slotted pages の問題点として、二分探索と相性が悪いという点があります。 値の比較をするためにポインタを辿らなければならないため、CPU のキャッシュをぜんぜん活かせません。 そのため、キーが固定長であればキーを連続して埋めたほうがよいのですが、私の書いた qp ではキーが固定長であるにも関わらずそのような最適化はしていません。 これは同じデータ構造を使いまわしてサボるためです。 (両方実装してベンチマークで比較とかしてみたいですね)

おわり

日付変更1時間前に書き始めたのであまりおもしろいことが書けませんでした。 まだアドベントカレンダーの枠はたくさんあまっているので、追加のトピックについては適当な日の枠を使って書いていこうかと思います。

Rustで古典的なDisk-Oriented DBMSを実装した話

KOBA789 です。みなさん DBMS は好きですか。私は好きです。

最近、自作 DBMS をずっと作っていて、ようやく最低限の機能ができたので公開をしました。 (とはいえコードを書いていたのは正味2日ほど。設計と勉強に2週間かかった)

github.com

この記事ではこれを作った目的と、そのちょっとした詳細についてご紹介します。

目的

Disk-Oriented DBMS の学習に適している Rust で書かれた実装が欲しかった、というのが理由です。

DBMS の勉強に適している実装というのは意外と多くありません。
MySQLPostgreSQL といった有名な実装は実用的である一方でコード量は非常に多く、また細かな最適化によって教科書的なアルゴリズムと実際のコードの差が大きくなっているため、初学者にとっては構造を把握しづらくなっています。
教科書的な実装の Disk-Oriented DBMS というのは実装がクソめんどくさい割にそのままでは性能が悪く非実用的なためにわざわざ実装する人はおらず、現代では勉強に適した典型的な Disk-Oriented DBMS の実装はほとんどありません。

また Disk-Oriented DBMS は複数のスレッドが1つのバッファを奪い合うという設計上、当然ながら latching のテクニックが重要になります。
C 言語で実装する場合には教科書に載っているアルゴリズム擬似コードをそのまま実装すればよいのですが、これを Rust で実装するとどうなるのかに興味がありました。
Rust で Disk-Oriented DBMS を実装しようだなんて思う人間はまずいないため、やはり自分で実装するしかありませんでした。

勉強と設計

Rust 特有の難しさはあとでなんとかすることにしても、まずは Disk-Oriented DBMS の実装テクニックを知る必要があります。

とっかかりとしては CMU のこの講義が参考になりました。

www.youtube.com

この講義では BusTub という C++ で書かれた Disk-Oriented DBMS を課題の題材に使っており、この実装も参考になります。

github.com

課題で学生に実装を書かせるために重要な部分はだいたいスケルトンになっており、詳細を知るには課題のヒントを見ながら自力で実装しなければなりません。 スケルトンになっているとはいえ、クラス設計はほぼ完成しているのでそこは大変参考になります。

このあたりで一度、バッファプールとテーブルヒープの実装を書き上げ、フルスキャンしかできない DBMS を作りました。
しかしフルスキャンしかできず、トランザクションもない DBMS というのは大変つまらないものです。
ここで次に B+Tree を実装するかトランザクションを実装するか悩んだのですが、フルスキャンしかできない DBMS で 2PL を実装するとすべてがテーブルロックになることに気づいたので、先に B+Tree を実装することにしました。
Predicate Lock を実装すればインデックスがなくても細かいロックで 2PL を実装できるとか、2PL ではなく PostgreSQL 的な Append-Only MVCC なら(Serializable にはならないけど)できるんじゃないかとかあったんですが、それはそれです。

B+Tree の実装については上記の講義動画に加え、Modern B-Tree Techniques という本が非常に参考になりました。

now publishers - Modern B-Tree Techniques

200ページに渡ってほぼ B-Tree についてのみ書かれているのですが、その分非常に丁寧でだいたい全部書いてあるのでおすすめです。
困ってもこれを読めば解決するという安心感があります。

このあたりで固定長のページをノードとした B+Tree に、可変長のデータを入れようとすると途端に実装が面倒になることに気が付きます。
データ構造の解説などで登場する B-Tree もほぼすべてメモリ上のデータ構造で、かつデータは固定長であることがほとんどです。
これはぜひ可変長にせねばならんと思い、可変長のデータを入れられる設計にしました。

詳細

コンポーネントは大きく分けて Disk Manager, Buffer Pool Manager, Access Method の3部からなります。
トランザクションや複雑なクエリ言語は実装していないため、Lock Manager や Query Planner などはありません。
B+Tree の Access Method がほとんど直接インターフェースとして露出しています。
クエリのインターフェースとしては TCP 上で1行の JSON を送り合う素朴なプロトコルを採用しています。

Disk Manager

一番簡単なコンポーネントです。4KB 単位でバイト列を読み書きするだけです。説明不要でしょう。

qp/disk.rs at master · KOBA789/qp · GitHub

Buffer Pool Manager

すべてのスレッドが共有するバッファプールを管理します。
キャッシュ管理のアルゴリズムは LRU ではなく Clock Sweep です。PostgreSQL とかで使われているやつですね。
ちなみにバッファの free-list は実装していません。 free-list が一度枯れてしまったら DROP TABLE とかしないと復活しないわけですが、この DBMS には物理削除が実装されていないので不要という判断です。 起動直後にすべてのバッファを usage_count=0 で埋めてすべてを Clock Sweep に任せています。

意外と一番 Rust っぽいパズルがあったのがこの Buffer Pool です。 Rust の Mutex は保護対象のデータのコンテナのようになるため、無駄なロックを避けるためには Mutex に含める構造体のフィールドを最小限にする必要があります。 結果として細かな構造体がたくさん入れ子になり、深い階層構造を作っています。
前述の BusTub の実装と比べると対象的だと思います。

ページを fetch する際は BufferPool の巨大なロックを取り、ページテーブルで対象フレームが見つかったらフレームの中の Arc を clone して返します。
もし目的のページがフレームになければファイルから読み込んで victim フレームに書き込んでから、同様に Arc を clone して返します。
この状態ではページを Pin したのみでページのデータのバイト列へのアクセスはできませんので、実行スレッドが実際に読み書きする際は更に内側の RwLock を獲得してから操作します。

Mutex<
  BufferPool {
    frames: Vec<
      page_id,
      usage_count,
      body: Arc<
          RwLock<
            Page {
              is_dirty,
              data,
            }
          >
        >
      >
    >
  }
>

qp/buffer.rs at master · KOBA789/qp · GitHub

Access Method

公開しているコードに含まれている Access Method は B+Tree のみです。
フルスキャンしかできないテーブルヒープは消してしまいました。

qp/btree.rs at master · KOBA789/qp · GitHub

B+Tree の実装で特徴的な部分は特にありませんが、Latch Crabbing のために独自の latch 実装を書いています。
latch の実装としては parking_lot を使っているのですが、parking_lot の RwLock には owned な lock guard を獲得する方法がありません。
たとえば、tokio の Mutex には Arc<Mutex<T>> から owned な lock guard を獲得するメソッドがあります。
前述の通り、ページを Arc<RwLock<T>> で保護しているため、このようなメソッドがあるとロックを獲得したままデータを move できて便利です。
というか、ないと Latch Crabbing のようなテクニックを実現できません。

unsafe コードが含まれる唯一のモジュールです。

qp/lock.rs at master · KOBA789/qp · GitHub (lock.rs は名前がややこしいので latch.rs のほうがいいですね)

可変長のデータを固定長のページに格納するために Cell や Slot と呼ばれる構造があります。
それを実装したのが slotted.rs です。
もともとテーブルヒープを実装した際に書いたものですが、そのまま B+Tree の内部構造に流用しています。

qp/slotted.rs at master · KOBA789/qp · GitHub

DBMS を実装してみて

まだ全然要素が足りていないものの、実装をすることで Disk-Oriented DBMS のつらい部分を体験することができました。
既存の DBMS はすげーわと思うとともに、Disk-Oriented な DBMS をメニーコアでスケールさせるのはマジで無謀だわという実感を得ることもできました。
今後も暇を見つけて CC やリカバリなどを実装していければと思っています。