basic-design.re

= DBMS を学ぶためのリファレンス設計 基本


これまで、トランザクションを処理を目的とした DBMS が備えているべき
機能や性質について個別に説明してきました。
では、全体としてどんな機能があればトランザクション処理できると言えるでしょうか。
本章では、トランザクション処理ができるといえる最小限の機能セットについて考えます。
習うより慣れろの精神で、作ってみよう、という人はこれを読んで
実際に動くプログラムとしての DBMS を作ってみてください。



== 並行実行制御

並行実行制御は、今なおより良いものを求めて研究が行われている奥深いテーマですが、
必要最小限のトランザクション処理システムに必要か、と言われると、
なくても成立すると思いますので、ここでは涙を飲んでバッサリ削ろうと思います。
並行実行制御をせずに、きちんと動かす、すなわち Serializable に実行するためにはどうするか。
そうです、本当に Serial (直列)実行をすれば良いのです。
直列実行するスケジューラを Trivial scheduler といいます。
また、データ構造の排他は大変で、設計と実装の難易度が上がりますので、
思いきってシングルスレッドで動かす DBMS を作ることにしましょう。

ということで皆さんはまずシングルスレッドで動くトランザクション処理システムを
作ることを目標にしてもらおうと思います。
Trivial scheduler には並行実行制御は不要なので、
インデクスと WAL 機能があれば最小限の DBMS ができることになります。



== インデクスとスキーマ

インデクスを実現するデータ構造について、Tree map と Hash table を紹介しました。
より単純な DBMS は、どちらかのみサポートしているでしょう。
Tree map なら Range query が出来ますから、Phantom problem やその対処に興味がある人は
Tree map を選びましょう。そのような事情がない人は、Hash table でも良いでしょう。
極端な例を挙げると、インデクスを使わずに Record の配列を使っても良い、と主張する
人がいるかも知れません。Table full scan はできますね……
ただ、お目当ての Record に低コストでアクセスできる機能はさすがに必須としたいなと私は思います。

メモリ上とディスク上のデータフォーマットを無理に共通化したくありませんし、
ページ単位で Atomic に書いたりするのは面倒そうですし、何よりバッファキャッシュ管理をしたくない
(本書でも説明していません！！！）ので、
インメモリ DBMS を作ることにしましょう。
メモリに格納できない大きなデータベースは扱わないという割り切りをします。
これで、メモリ上でインデクスを実装すれば良くなりました。
シングルスレッド前提なので、排他制御も不要です。
あれれ、多くのプログラミング言語ではほぼ標準ライブラリで
この要件を満たす Tree map や Hash table を用意しているようですよ。
それらのライブラリを使えばインデクスが何故高速か、そのメカニズムを知らなくても
インデクスを実装できてしまいます。
私としては学びのために自分でインデクス構造を実装することも検討して欲しいのですが、
最小限、という意味ではサボって構いません。

DDL (Data definition language) 等を用意すると手間なので、
設定ファイルを読み込む形で定義させるか、もっと簡単に作るために、
ハードコーディングしてしまいましょう。
動的なスキーマ変更もサポートしないこととします。
極端なことをいえば、テーブルはひとつあれば十分じゃないでしょうか。

Record の仕様を決めましょう。
もちろん、たくさんの Primitive 型を用意して、任意の Column を組み合わせて Record を定義できると便利ですね。
しかし、設計と実装を簡単にするために、サボりましょう。
巷の Key-value store と呼ばれるものには、Key 型も Value 型もバイト列型しか選べないものもあるようです。
バイト列は表示するときに面倒なので、いっそ文字列に限定してしまいましょうか。
文字列も、ユニコードだのなんだのは面倒くさいので、ASII 文字だけに限定してしまいましょうか。

リッチなスキーマを想定するのであれば、セカンダリインデクスは欲しくなりますが、
Key-value store なら、プライマリインデクスだけあれば良いでしょう。
必要になったとしても、同じデータ構造を流用すれば良いので、
セカンダリインデクスは比較的簡単に実装できると思います。


== Write-ahead Logging

インメモリ DBMS とはいっても、ACID property を満たすために永続化はしないといけません。
ログ先行書き込み (WAL) 機能は Commit 条件を満たすために実装する必要があります。
ログファイルのフォーマットを決めましょう。
DBMS がどんなデータ操作をサポートするかを決めて、
そのオペレーションの Redo log の仕様を決めます。
SQL と似たようなインターフェースを想定するのであれば、
Update/insert/delete の三種類をサポートすることになります。
もっと簡単にしたいなら、Put (Upsert) のみサポートするのもありでしょう。
Upsert とは、その Primary key を持つ Record が存在していなければ Insert、
存在していたら Update する、という操作です。

Redo/undo log のどれを採用するかについて考えましょう。
Trivial scheduler を使う場合、トランザクションロジックによる明示的な Abort 命令と
Crash による Abort 以外では Abort しませんので、比較的簡単に実装できる Redo log のみを使う設計をオススメします。

そのトランザクションを Commit するぞと決めるまで、
メモリ上のデータベース本体に変更を反映しないようにすれば、Undo log は不要です。
Redo log は 後述する Write set から作れます。
Redo log は Atomic に書きましょう。Atomic に書く単位について、
オペレーション単位で書くか、トランザクション単位で書くか、これも設計上の選択肢です。


== Read set と Write set

DBMS 側のトランザクション実行エンジンはどのように振る舞えば良いでしょうか。
本書は Non-deterministic DBMS を想定すると言いましたね。
実行エンジンは次にどんな命令が来るのか分からないのでトランザクションの状態管理をする必要があります。

同じ Record に対する複数回のアクセスをうまく吸収するための仕組みとして Read set と Write set があります。
Read set はトランザクションが過去に読んだ Record の参照とその内容を保持しておきます。
Write set はトランザクションが書いた内容で、やはり Record の参照とともに保持しておきます。
Trivial scheduler を採用するとき Read set は不要です。なぜなら自分以外にトランザクションは
並行に実行されていないので、同じ Record を何回読んでも自分が変更しない限り同じだからです。

Trivial scheduler を採用していても Write set は必要です。
何故なら Redo log のみ記録する設計を選んだからです。
いついかなるときでも Undo はできないので、Undo が不要になることが確定するまで
データベース本体に変更を反映してはいけません。
Undo が不要になる瞬間は、Commit することが確実視されたときです。
一般には、CC protocol がそのトランザクションを Commit させると決定(Commit しても良いと判断)したときですが、
Trivial scheduler においてその判断は不要なので、Commit 命令を受けとった瞬間が対応します。
もしそれより前にデータベース本体に変更を反映してしまい、
その後トランザクションロジックから Abort 命令が来たら、Undo できなくて詰みます。
トランザクション実行中はデータベース本体と Write set を別々に管理しますが、
トランザクションロジックから見ると、
あたかもそれまでの変更がデータベース本体に反映されているかのように振る舞います。
すなわち、Write set に存在する Record の Read 要求に対しては Write set に保持されている内容を返すということです。
別の見方をすれば Write set はキャッシュデータとして振る舞います。
Write set はトランザクションによるデータベース変更への変更データそのものなので、
Write set から Redo log が作れます。自分で決めたフォーマットに従って変換するだけです。



== Crash recovery

DBMS 起動時にやるべきことは、Crash recovery です。
Crash recovery は、Commit の返事をした(および Commit だと判定した)全てのトランザクションの実行結果が
反映されたデータベース状態をメモリ上に再構築し、新規トランザクションを受けつけられる状態にすることです。
前回の Checkpointing 時のデータベースファイルがあればメモリに読み出し、
WAL ファイルの中身を Redo してメモリ上に正しいデータベース状態を再構築します。
このとき、同じログを複数回適用するハメになるかもしれないことに気をつけてください。
典型的には、同じログを何回適用しても大丈夫なように作る必要があります。
もしくは、二回目以降はスキップできるような仕組みを用意する必要があります。どちらにするか、
それも設計の選択肢です。


== Checkpointing

Checkpointing は出来るだけ簡単なものにしたいので、
トランザクションが動いていないときのみ、いやいやもっと極端に起動時のみにやることにしましょう。
起動時、Crash recovery 直後は、メモリ上には正しいデータベース状態がありますが、
その直後にまた Crash したら、せっかく Crash recovery したのに同じことをやりなおす必要があります。
そこで、今再構築したばかりのデータベース状態を、Snapshot としてファイルとして
書き出して永続化してあげましょう。これを Dump 操作といいます@<fn>{footnote_load}。
永続化が完了したら、次の Crash recovery はこの Snapshot から始めればよいので、
今ある WAL ファイルの中身はもう必要ありませんので、消してしまいましょう。
それぞれの操作について、永続化も含めて順番には気をつけましょう。
いついかなるときに Crash するか分かりませんから、常に備える必要があります。
これが一番ナイーブですが一番簡単な Checkpointing だと思います。
また、Dump 操作においては、Atomic にファイル全体を書くことを忘れないようにしましょう。

//footnote[footnote_load][Crash recovery で必要とした、Snapshot ファイルをメモリに読み込む操作を Load と呼びます。Dump/load はお互いに逆の操作なのでセットで考えます。]


== トランザクションとワークロード

Read/insert/update/delete (もしくは Get/put)、そして Commit/abort を実行する API を用意して、
簡単な動作確認をするためのトランザクションを実装してください。
トランザクションロジックが呼び出すデータベース操作 API はライブラリとして実装しましょう。
ネットワークなどを介した専用プロトコルを用意するより簡単です。
それを組み込み DBMS というのでしたね。
トランザクションやそれを呼び出すワークロードも同じプログラミング言語で書いて DBMS 実装に
組み込んでしまいましょう。
とはいえ、たとえコンパイルで同一バイナリになるとしても、
インターフェースをきちんと定義して境界を意識して設計実装してください。
DBMS が起動し、初期化が終わってトランザクションを受けつけられる状態になったら、
トランザクションを有限個または無限個実行するような
コード(ワークロード実装)を用意しておいて動かしてみてください。

Crash test がしたい場合は、外部から強制的に DBMS が動いているホストを落とすとき、
トランザクションが実行中であるようにしておく必要がありますね。
性能測定がしたい場合は、時間を測ったり実行できたトランザクションの個数を数えたり
するコードもアプリケーションとして一緒に書いてしまいましょう。


== 作って動かしてみる


以上で、大体のアーキテクチャは固まってきました。
細かいところは自分で考えてみてください。また、ご自分の興味に従って設計を変更しても大丈夫です。

まずは出来るだけ簡単だけど、動くものを作ることが学びのモチベーション維持のためにも大切です。
だから本章は最小限の設計を指針としています。
出来るだけ少なくて簡単な要件から始めましょう。
そして、要件を満たす仕様を考えていきます。
そして、仕様に沿って実装して動かしてみましょう。
要件、仕様、そして実装をいったりきたりすると思います。これが出戻りというやつですが、
大いにいったりきたりしましょう。やってみないと分からないことはあるものです。
トランザクションシステムは、特に設計の選択肢が多いと思います。
どんな選択をすれば、どんなメリットやデメリットがあり、どんな制約が発生するか、
考えながら設計しましょう。
どんな選択をしたか、何故そうしたか、それらを整理することを心がけてください。
人に説明できることが重要です。
本書を使って学ぶみなさんには、要件と仕様をきちんと定めていくこと、定めようとすることが
ソフトウェアの品質向上にどれだけ寄与するかということも学んで欲しいと思います。
@<secref>{memo|sec-requirements-and-specification}
も参考にしてください。

コーディングについては、単に動けば良いというわけではなく、読みやすさに気をつけましょう。
@<secref>{memo|sec-readable-code}を参考にしてください。



== テスト

作ったプログラムが正しく動いていることを確認するにはテストをすることが欠かせません。
正常系として、データ操作をしたらそれが反映されているか、などの基本動作についてテストします。
プロダクションで動かすことを考えていくならエラー処理(そして異常系テスト)がとても重要ですが、
学習用のプログラムなので、ある程度は目をつぶりましょう。
しかし、異常系の中で DBMS としてひとつだけ絶対に押さえておかなければならないテストがあります。
それが Crash test です。
トランザクション実行中にマシンの電源を落として、Crash recovery できることを確認してください。
Virtual Machine を使って仮想的に電源を落とすのが良いでしょう。
Commit の返事をしたのに反映されていないことがないかどうか、
中途半端な状態になっていないか、データとして壊れていないかどうかを確認してください。
@<secref>{memo|sec-about-test}も参考にしてください。