それが僕には楽しかったんです。

いろんなレイヤーに居ます

CMU Database Systems をひたすら追っていく ~03,04 Database Storage ~

この記事は「 けんつの1人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar 」 3日目の記事です。

はじめに

どうも、前日のアドカレをこの章が楽しみ過ぎてハイパー雑に書いてしまったが後悔はしてないけんつです。
最近みた映画で面白かったのは「ザ・コア」です。

今回は Database Storage についてです。
2つに分割されている講義をこの記事にまとめます。

Database Storage

Storage

この一連の記事で学習するデータベースはディスク指向であり不揮発性のディスクにデータを保存するアーキテクチャを前提としている。
記憶領域は CPU に近くなればなるほど、IOの速度は上がるが高価で要領が小さい。
また揮発性ストレージと不揮発性ストレージは以下のような違いがある。

Volatile Devices
  • 揮発性とは電源を切ればデータが消失することを指す。
  • 揮発性ストレージはバイトアドレスが可能なロケーションで高速なランダムアクセスをサポートする
  • このような特性を持つものは往々にしてメモリと呼ばれることが多い。*1
Non-Volatile Devices
  • 不揮発性とはデバイスが保持しているデータを維持するために継続的な電力供給の必要が無いことを指す
  • 不揮発性ストレージはシーケンシャルアクセス*2とブロックアドレス*3指定の点において優れている。

DBMS vs OS

参考にしている講義の目的の一つに、使用可能なメモリ容量を超える保存領域をデータベースでサポートすることが上がっている。
しかし、ディスクへの I/O はコストが高いので慎重に管理する必要がある。
またなぜ OS をベースにしないで DBMS を作りその上で仮想記憶のような仕組みを作るかというと、OS でも(ここでは Linux ) mmap を使いプロセスのアドレス空間でファイル内容をマッピングできるがページフォールトにヒットするとプロセスがブロックされる。
プロセスが他のタプルへのロックを保持していた場合はロックが破綻するため DBMS を作る。

File Storage

多くの DBMS のデータストアはディスク上のファイルを使用する。ファイル階層を利用する場合、単一のファイルを使用するものも存在する。*4
またこれらのファイルは OS からは内容を見ることが一般的には出来ず、DBMS だけが内容を解読する方法を知っている。
DBMS のストレージマネージャーは

Database Page

DBMS は「ページ」と言われる、固定長のデータを持つ一つ以上のファイルからデータベースを構築している。
ページは異なる種類のデータを格納することができる。しかし、多くの DBMS ではそのようなことをしていない。

ページという概念は DB 以外にも存在していてその容量は以下の通りとなる。

  • Hardware page (4KB)
  • OS Page (4KB)

これに対して、 Database page は 1-16KB と開きがある。MySQL は 16KB のはず。*5

またそれぞれのページには識別子が割り振られている。データベースがひとつのファイルから構成される場合、ページIDは単一のオフセットにすることができる。
またほとんどの DBMS にはページ ID をファイルパスとオフセットにマッピングするインリダイレクションレイヤーが存在する。

データベース内の各タプルには一意に定まる識別子が渡される。この識別子は最も一般的なもので page_id + offset/slot
の形式をとる。

そもそもページとは

これはページング方式と言われる手法の一つで、ページング方式とは記憶装置(今回であればファイルストレージ)をページという小さな単位に分割してデータを割り当てる。
また、これを用いて仮想記憶を構築することがある。それが以前に書いた mmap などの話に繋がる。

仮想記憶とは

仮想記憶とは、物理的なメモリをアプリケーションに対して、専用の連続した主記憶装置に見えるように提供するもののことを指す。
ざっくり言ってしまえばストレージをメモリに見せかける方法のこと。これを実現するためにページング方式などが用いられる。

Database Heap

ヒープファイルとはタプルがランダムに格納されるページの順不同なコレクションのこと。
DBMS にはページIDを指定してディスク上のページを見つける方法が必要でそのためにヒープが存在する。
またそれらを構築する場合の解決策として有効なものは以下の2つ。

  • Linked List: ヘッダーページにフリーページとデータベージのリストへのポインタを保持する
  • Page Directory: データページの場所を追跡する特別なページを保持する

全てのページは Header を保持している。その内容にはページサイズやチェックサム等のメタ情報が格納される。その他がデータ本体となる。

Page Layout

ページストレージアーキテクチャはページ内に格納されているデータをどのように整理するかというところに重点を置いている。
これには2つのアプローチが挙げられる。

  • Tupled-oriented
  • Log-Structured
Tuple-Oriented

ページがヘッダーにいくつタプルを格納しているかという情報を保持している。
その上で以下のようにタプルを任意の個数連続させる。
f:id:RabbitFoot141:20191107001742p:plain

この状態でふたつ目のタプルを削除する。
f:id:RabbitFoot141:20191107001848p:plain

さらにその状態でタプルを追加する。
f:id:RabbitFoot141:20191107002729p:plain

全てのデータが固定長なら良いが、可変長の列が存在すると問題が発生する。
またデータを削除し続けると無限にインデックスが上がってしまうなどの問題がある。(よくわかってないけど)

それらを解決し、適切にデータを配置する手法に "Slotted Pages" という方法がある。
これは slots という領域をヘッダーの次に確保する。そしてこの slots に各タプルがどの位置から開始されるかを格納しておく。
また slots の領域は可変の為、データを末尾から追加していく。これにより可変長のデータやデータの削除に対応できる。

Log-Structured

Tuple-Oriented の方ではタプルそのものを保存する方法を紹介したが Log-Structured ではタプルをページに保存するのではなくログレコードのみを保存する。
またデータベースは以下のような変更が加わった場合にログレコードを追加する。

  • Insert: タプル全体を保存する
  • Delete: タプルを削除済みとしてマークする
  • Update: 変更された属性の差分が保存される。

またレコードを読み込む場合は、ログを逆方向にスキャンしタプルを再作成する。
全てのレコードにアクセスしてはコストがかかるため、インデックスを貼ってジャンプするべき。

さらにログは定期的に圧縮して簡略化すると更にコストは下がる。

これらの手法は Apache HBase や LevelDB, Cassandra で採用されている。

ログ圧縮に関しては次の2つの手法が一般的。

  • Level Compaction
  • Universal Compaction

Tuple Layout

タプルは基本的に Byte へのシーケンスで、それらの Byte 列を型と値に解析するのが DBMS が担う部分となる。
そのため、どのようなアーキテクチャにタプルを落としこむかという観点が重要になってくる。

Tuple Header

大まかにタプルのレイアウトといっても、前提は存在していてページと同様にヘッダーがありボディとしてアトリビュートのデータが続くという構成になっている。
このタプルのヘッダーには BitMap であったり、同時実行制御のための情報が格納される。
ただし、データベースのスキーマに関するいわゆるメタデータは保存しない。

Tuple Data

タプルに保存されるアトリビュート、いわゆる列ごとのデータは一般的にテーブル作成時の順序で保存される。
外部キー制約などが存在するような場合は関連するタプルを非正規化し、同じページに格納してしまう。
これにより I/O の量を削減することができたり、更新のコストを下げることができる。

Data Representation

この章ではデータの表現についてまとめる。
例えば DBMS の内部ではどういうデータ型を使用するのか*6ということを書いていく。

Variable Precision Numbers

いわゆる可変精度小数点の表現について。
これらは厳密ではないが実装時に C/C++ を使用すると IEEE-754 規格の可変精度数値型を利用できる。
また CPU が命令を直接実行できるような構造を保持すると任意の精度の数値よりも高速に処理できる。
ex) FLOAT, REAL

Fixed Point Precision Numbers

固定小数点精度の表現について。これらは通常のデータに加えて精度やスケールに関して詳細なメタデータを追加で保持した上でバイナリに落とし込まれるべき。
丸め誤差が許容できない場合に使用することができる。
ex) NUMERIC, DECIMAL

Large Value

殆どの DBMS ではタプルが単一ページのサイズを超えることを許容していない。

ページサイズより大きい値を格納するために DBMS は個別にオーバーフローストレージページといわれる領域を使用する。*7

Workloads

OLTP

On-Line Transaction Processing といわれる代物。ライフサイクルの短いトランザクションをベースに処理を行うため少量のデータを繰り返し登録することや、それらを読み込むことに特化した手法のこと。どちらかというとシンプルなクエリに強く、 Write を得意とする。

OLAP

On-Line Analytical Processing といわれる代物。これはトランザクションのライフサイクルが長い処理に向いている。主に大容量のデータを一度に保存したり、コストが莫大にかかるような JOIN や検索などに向いている。 OLTP とは逆の特性をもつ。どちらかというと Read 系に強い。

Storage Models

ここで紹介するストレージモデルは2つある。

N-ary Storage Model

このモデルは、全てのアトリビュートをひとつのタプルを連続してページ内に保存するもので、 クエリが個々のエンティティでのみ動作しデータの挿入を繰り返す傾向があるため OLTP を用いる。*8

このモデルは高速にデータを作成、更新、削除することができる。そのためタプル全体を必要とするようなクエリに適している。
反対に、タプル全体を必要としないテーブルの大部分をスキャンすることには向いていない。

Decomposition Storage Model

これはアトリビュート毎にページを分割して登録するモデルであり、 OLAP を使用する。*9
そのため、必要なデータを読み取るための無駄な I/O を削減する。
NSM と対象的に、データを操作することに関しては向いていない。

おわりに

ひとまずこれで Database Storage は終わり。
勉強している途中で、ページを検索する際にメモリ上にページを保持すると思うがこれは膨大なテーブルだとどうなるのだろうか?と疑問に思ったがそれらの問題を上手く解決するために Buffer Pools が存在する。
次の内容は Buffer Pools について。

*1:レジスタなどもあるが講義資料ではそう紹介されていた

*2:ランダムアクセスの逆、先頭から順にアクセスする。

*3:いわゆるインデックスのようなもので、ブロックアドレスを指定する事でその場所にあるデータを読み出せる。このアドレスは順に先頭から割当たる。らしい。

*4:SQLiteなど

*5:事実上、どんなサイズの行であっても格納できるらしい。

*6:講義内では C/C++ のデータ型や IEEE-754について言及されている

*7:MySQL ではページサイズの半分より大きいらしい

*8:行を基準にデータを保存する

*9:列を基準にデータを保存する