Write and Run

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

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 やリカバリなどを実装していければと思っています。