preface.re

= はじめに

== データベースシステムとは


データベースとはデータの集まりで、特に整理整頓されているデータの集まりを指すこ
とが多いです。データベースの操作とは、その中に含まれるデータを検索した
り、追加、編集、削除したり、まとめて集計加工をしたりすることを指します。

データベースシステムとは、データベースの管理やユーザおよびアプリケーショ
ンによる操作を受け負うソフトウェアのことを指します。ひとりで使うデータ
ベースであれば、Excel などの表計算ソフトでも足りることが多いと思います。
これもデータベースシステムと呼べるでしょう。一方、複数人で共有したいデー
タベースの場合、同時に同じデータを更新したらデータが壊れたりおかしくなっ
たりしないか気になりますね。そのような心配をしなくていいのが典型的なデー
タベースシステムです。

データベースシステムといったとき、皆さんは具体的にどんなソフトウェアを
思い浮べるでしょうか？オープンソースのデータベースシステムだけとっても、
MySQL、PostgreSQL など、商用だと Oracle、SQL Server、DB2、Google
Spannar、Amazon Aurora など、たくさんあります。
これらの多くは SQL@<fn>{footnote_sql} という操作インターフェースを供えており、
トランザクション処理が可能です。
また、大量のデータを加工・集計する処理も、規模や状況によりますが可能です。

//footnote[footnote_sql][日本語では「エスキューエル」と読む人が多いようですが、英語だと「シークエル」と呼ぶ人が多いらしいです。]


もう少し広い範囲でも見てみることにします。Hadoop や Spark などは、細か
い単位でのデータ操作が苦手で、とりわけトランザクション処理には対応して
いない代わりに、SQL SELECT 文もしくはそれに相当する実行、つまり、デー
タを大量に加工、集計する用途に特化しています。また、ひとつのホストでは
保持できない程の大量のデータを扱えるように、複数のホストをまたがって動
作する分散システムです。etcd は、設定情報を分散システムで安全に共有す
る目的で使われることが多いデータベースシステムですが、Key-value store
に分類されます。Key-value store は、主に Key を指定して、Value を検索、
操作するという、SQL よりも単純なインターフェースを持っています。
Key-value store に分類される Memcached や Redis は、データの永続化をあ
る程度犠牲にしてでも、高速に処理したいデータを扱う目的で使われることが
多いようです。他にも、目的、用途に応じて様々なデータベースシステムがあ
ります。


== トランザクション処理

本書は、上記で紹介した様々なデータベースシステムの一部が持っている機
能であるトランザクション処理を対象とします。トランザクション処理は世
の中になくてはならない処理のひとつです。皆さんが銀行 ATM でお金を入出
金したり送金したりする度に、裏でトランザクションが実行されます。ATM
での操作が「きちんと」実行されないと困りますよね。また、皆さんがインター
ネット上の販売サイトで何かを購入するときに、決済(支払い)の画面で、決済
ボタンを押す度に、裏でトランザクションが実行されます。これらの操作も
「きちんと」処理してくれないと困りますよね。お金のやりとりにはほぼ必須
ですが、それに限らず様々なやりとりでトランザクション処理は必要とされて
います。世の中には「きちんと」処理してくれないと困るデータが多いからで
す。「きちんと」がどういう意味を持つかについて理解するには、ACID 特性
の理解が必要となります。興味を持った方は自分で調べてみてください。

トランザクション処理の重要性について書きましたが、本書が書かれた一番の
理由は、著者が、トランザクション処理をおもしろい、と思っているからです。


== トランザクション処理を学ぶのに向いている人

アルゴリズムとデータ構造を学ぶのがおもしろいと思う方は、トランザクショ
ン処理もおもしろいと感じる適性が間違いなくあると思います。何故ならトラ
ンザクション処理は、メモリ上、ディスク上で、様々なデータ構造を必要とし、
その操作に伴うアルゴリズムを必要とするからです。並列プログラミングが大
好きな人も、トランザクション処理の性能を高めるために、それを駆使する必
要があるので、楽しいと思います。CPU やメモリ、ストレージデバイス、ネッ
トワークデバイスなどのハードウェアに興味がある人にも、トランザクション
処理(に限らずデータ処理全般)はハードウェアの機能や特性をいかに活用する
かという側面がありますので、楽しめると思います。


== 本書の目的


本書によって、データベースシステム、とりわけトランザクション処理の大ま
かな仕組みを理解し、作る側になれる人を増やしたいと思っています。

SQL についての情報はたくさんあります。本もたくさん出ています。それはデー
タベースシステムを使う人に必要な知識で、データベースシステムを使う人は
たくさんいるからです。トランザクションを伴うアプリケーションを設計実装
する人達は、ひとまとめにしたい複数のデータベース操作をひとつのトランザ
クションにまとめるだけで済むことが多いと思います。トランザクションとい
う概念のもたらす抽象化は良く出来ており、使う側にとっては便利な道具です。
一方で、その皺寄せがトランザクション処理を実行するデータベースシステム
に来ているのです。

データベースシステムを作れるであろう人は、私が思うに少ないです。もちろ
ん、使う人ほど多くなくていいですが、作る人がもっといて欲しいなと思いま
す。さらに、データベースシステムの作り方を教える人も少ないと思います。
というわけで、微力ではありますが多少の心得がある私が本書を書くことによっ
て多少なりとも目的に向かえたらなと思います。


== 本書で学べること


本書を読む皆さんには、トランザクションを処理する仕組みについて実際にプ
ログラムを作ることを通して学んでもらいます。

トランザクションを実行するのに必要な主な仕組みは、メモリ上およびディス
ク上でデータに効率良くアクセスするためのアクセスメソッド(インデクス構
造)、効率的に更新データを永続化する永続化機構 (Write-ahead logging,
WAL やCheckpointing)、およびトランザクションを同時にたくさん実行するた
めの並行実行制御(Concurrency control, CC) です。

私がおもしろく、そして難しいと思うところは、トランザクションを並列に実
行するための、様々な仕組みで、Concurrency control はそのひとつです。た
だ、Concurrency control をデータベースシステム上で実現するにあたって、
典型的には複数の CPU コアを使ってトランザクションを並列に実行するので
すが、複数スレッド/プロセスからひとつのデータ構造にアクセスするので、
並列プログラミングと言われている技術が必要になります。具体的には Lock
や Latch などデータの適切な排他を行う仕組みが、場合によっては、
Lock-free だとか Mutex-free と呼ばれているような技術も必要です。

並列プログラミングにチャレンジするかどうかは皆さん次第ではありますが、
これらの技術的に難易度が高めの能力を前提としてしまうのは、本書の目的に
必ずしも沿わないと思います。

そこで、並列処理にチャレンジする前に到達して欲しいマイルストーンとして、
シングルスレッドで、基本的なトランザクション処理ができるデータベースシ
ステムが動くことを目指して欲しいと思います。シングルスレッドプログラム
に対象を絞ったときは、初めに、ディスク、つまり永続ストレージの特性と操
作について、次にデータ構造(主にアクセスメソッドとしてのインデクス)、そ
して WAL (と Checkpointing) について学んでもらいます。ここまでを実装す
ると、クラッシュリカバリができるようになり、最低限のトランザクション処
理ができるデータベースシステムですよといえるようになります。

次なるステップとして、Concurrency control について学んでもらおうと思っ
ています。これには、2 つのアプローチがあります。ひとつめは、カーネルス
レッドではなく、ユーザースレッドもしくはそれに準ずる手法を用いて、
Concurrency control の仕組みを実装し、動かしながら学んでもらうアプロー
チです。このアプローチの良いところは、スレッドセーフなデータ構造を使っ
たり並列プログラミングの技法を駆使しなくても Concurrency control を動
かせることです。ふたつめは、既存のスレッドセーフなデータ構造ライブラリ
を使って、複数のカーネルスレッドで動かすことを前提に Concurrency
control の手法を実装するアプローチです。こちらは、Concurrency control
実装に並列プログラミングが必要となります。ここまでで、一通りトランザク
ション処理の要素技術を学べると思います。



== 前提となる知識と経験

プログラミングをまったくやったことがない方は本書を読んでもチンプンカン
プンとなる可能性が高いです。なんでも構わないので、プログラムの書き方
(変数だの関数だの分岐だのループだのファイル操作などなど)に慣れ、基本的
なデータ構造とアルゴリズム(配列、リスト、マップ、サーチ、ソート、など
など)に慣れてからの方が良いでしょう。

プログラムの書き方について、具体的には、データの種類および入れ物である
型と変数について、処理の単位である関数について、分岐やループなどプログ
ラムの構造について、ファイル操作などの入出力について、ある程度知ってい
て慣れている必要があります。C/C++ などを使う場合は、さらにポインタの使
い方やヒープとスタックの違いについてなどを知っていると良いでしょう。

基本的なアルゴリズムとデータ構造については、Tree map 構造と Hash table
構造をインデクスとして使ったときの特性の違いだとか、Search と Sort ア
ルゴリズムだとかについて知っていると良いです。分からなければ、必要に応
じて学べば良いです。

開発に用いるプログラミング言語について。データベースシステムは、C/C++
などのよりメモリや CPU を直接扱いやすい言語で書いてあることが多いです
し、最近ですと、Go、Java などで書かれているものもあるようです。もちろ
ん、上記の言語を使わないとダメというわけではありません。ただ、特にファ
イルの操作については、システムコールを使って説明することも多いので、お
使いのプログラミング言語でどのようにそれらの処理が抽象化されているかに
ついてはご自分で調べてください。
ファイル操作については標準もしくはそれに準ずる
ライブラリが用意されている言語が多いようなので、
それを適切に使えば目的は達成できると思います。



== 本書を読んだ後

本書で学んだ後、是非皆さんの興味が強いテーマを深欲りして欲しいと思いま
す。たとえば、インデクス構造を自作したり、スレッドセーフにしたり、性能
を追求するなど。WAL の仕組みを改善してみるなど、並列化してみるなど、
Checkpointing を頑張ってみるなど。異なる Concurrency control 手法を実
装してみるなど。よりハードウェアの性能を活用できるような方法を考えてみ
るなど。組込みシステムや分散システムなどの異なる環境を想定してみるなど。
トランザクション処理とは違う視点、例えば、SQL 処理の最適化・並列化など
や、ストレージ技術などに視野を広げて勉強するのも良いと思います。

皆さんには、本書で学んだことを生かして、いずれ、是非オリジナルの特徴を
持ったデータベースシステムの開発にチャレンジしていただきたいですし、実
用的なデータベースシステムを作る側の人になって活躍して欲しいです。もち
ろん、データベースシステムを使う側の人になったとしても、ここで得た知識
は多いに役立つでしょう。どのような仕組みになっているかを知らないで使う
のと、知っていて使うのでは、大きな差が出ます。データベースシステムの気
持ちを知らない人は、データベースシステムをうまく使うことが出来ません。
また、研究の分野でもまだまだ課題はたくさんあり、それらを解決に導く新し
い手法を探求していって欲しいとも思います。

データベースシステムは、秘密にしなければならないデータを格納することも
多いので、データの漏洩や改竄をされないように厳重に守らなければなりませ
ん。その第一歩は、バグを出来るだけ少なくするような設計実装であることは
いうまでもありませんが、データベースシステムそのものだけでなく、周辺環
境、使う人達のことも含めて、セキュリティには十分意識して頂きたいと思い
ます。


== 本書の構成

@<chap>{data}でデータベースが扱うデータとは何か、
@<chap>{transaction}でトランザクションとは何かについて簡単にですが学びます。
使う側の視点で、トランザクションシステムは
どんな性質を持っているとみなせるのかについて説明します。

@<chap>{indexes}でインデクスについて、
@<chap>{wal}で永続化について、
@<chap>{concurrency-control}で並行実行制御について学びます。
これらは皆さんが作るトランザクションシステムの主要な仕組
みでしたね。それぞれの役割や典型的な手法について紹介します。

@<chap>{file-io}ではファイルの読み書きを行う基本的な道具について学びます。
この章はほぼ Linux 前提の知識で、関係する System call について紹介しています。
お使いのプログラミング言語が良いライブラリを持っている場合はそちらを使
いましょう。また、異なる OS 向けの設計実装したい場合は同様の API を調
べて正しく使う必要があります。

@<chap>{atomic-write}では、データの Atomic な永続化方法について解説します。
これは、ファイルの読み書きをする基本的な道具を使って、
トランザクションシステムの設計実装をするために必要な典型的な手法について整理したものです。

@<chap>{basic-design}では、「DBMS を学ぶためのリファレンス設計 基本」というタイトル通り、
最小限、トランザクションシステムと呼べるもののリファレンス設計について
示します。ここではかなり永続化にウェイトが置かれています。
そのための@<chap>{file-io}と@<chap>{atomic-write}だったんですね。
とはいえ、あまり詳細には書いていない(書けていないともいう)ので、
ご自分で細かいところを詰めながら作ってみてください。

@<chap>{next-step}は、「DBMS を学ぶためのリファレンス設計 応用」について説明します。
@<chap>{basic-design}で作ったものを改造しながらさらに学んでいくにあたって、
複数の発展方向がありますので、それぞれについての指針を説明します。

@<chap>{memo}には、それまでの章に入れづらかったり、長くなりすぎた内容について、
順不同でまとめて置いてあります。