- はじめに
- 今回の動画
- Database Storage
- おわりに
この記事は「 けんつの１人 DBMS アドベントカレンダー Advent Calendar 2019 - Adventar 」 3日目の記事です。
はじめに
どうも、前日のアドカレをこの章が楽しみ過ぎてハイパー雑に書いてしまったが後悔はしてないけんつです。
最近みた映画で面白かったのは「ザ・コア」です。
今回は Database Storage についてです。
２つに分割されている講義をこの記事にまとめます。
Database Storage
Storage
この一連の記事で学習するデータベースはディスク指向であり不揮発性のディスクにデータを保存するアーキテクチャを前提としている。
記憶領域は CPU に近くなればなるほど、IOの速度は上がるが高価で要領が小さい。
また揮発性ストレージと不揮発性ストレージは以下のような違いがある。
Volatile Devices
- 揮発性とは電源を切ればデータが消失することを指す。
- 揮発性ストレージはバイトアドレスが可能なロケーションで高速なランダムアクセスをサポートする
- このような特性を持つものは往々にしてメモリと呼ばれることが多い。*1
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を指定してディスク上のページを見つける方法が必要でそのためにヒープが存在する。
またそれらを構築する場合の解決策として有効なものは以下の２つ。
- Linked List: ヘッダーページにフリーページとデータベージのリストへのポインタを保持する
- Page Directory: データページの場所を追跡する特別なページを保持する
Page Header
全てのページは Header を保持している。その内容にはページサイズやチェックサム等のメタ情報が格納される。その他がデータ本体となる。
Page Layout
ページストレージアーキテクチャはページ内に格納されているデータをどのように整理するかというところに重点を置いている。
これには２つのアプローチが挙げられる。
- Tupled-oriented
- Log-Structured
Tuple-Oriented
ページがヘッダーにいくつタプルを格納しているかという情報を保持している。
その上で以下のようにタプルを任意の個数連続させる。
この状態でふたつ目のタプルを削除する。
さらにその状態でタプルを追加する。
全てのデータが固定長なら良いが、可変長の列が存在すると問題が発生する。
またデータを削除し続けると無限にインデックスが上がってしまうなどの問題がある。(よくわかってないけど)
それらを解決し、適切にデータを配置する手法に "Slotted Pages" という方法がある。
これは slots という領域をヘッダーの次に確保する。そしてこの slots に各タプルがどの位置から開始されるかを格納しておく。
また slots の領域は可変の為、データを末尾から追加していく。これにより可変長のデータやデータの削除に対応できる。
Log-Structured
Tuple-Oriented の方ではタプルそのものを保存する方法を紹介したが Log-Structured ではタプルをページに保存するのではなくログレコードのみを保存する。
またデータベースは以下のような変更が加わった場合にログレコードを追加する。
- Insert: タプル全体を保存する
- Delete: タプルを削除済みとしてマークする
- Update: 変更された属性の差分が保存される。
またレコードを読み込む場合は、ログを逆方向にスキャンしタプルを再作成する。
全てのレコードにアクセスしてはコストがかかるため、インデックスを貼ってジャンプするべき。
さらにログは定期的に圧縮して簡略化すると更にコストは下がる。
これらの手法は Apache HBase や LevelDB, Cassandra で採用されている。
ログ圧縮に関しては次の２つの手法が一般的。
- 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
Workloads
OLTP
On-Line Transaction Processing といわれる代物。ライフサイクルの短いトランザクションをベースに処理を行うため少量のデータを繰り返し登録することや、それらを読み込むことに特化した手法のこと。どちらかというとシンプルなクエリに強く、 Write を得意とする。
OLAP
On-Line Analytical Processing といわれる代物。これはトランザクションのライフサイクルが長い処理に向いている。主に大容量のデータを一度に保存したり、コストが莫大にかかるような JOIN や検索などに向いている。 OLTP とは逆の特性をもつ。どちらかというと Read 系に強い。
おわりに
ひとまずこれで Database Storage は終わり。
勉強している途中で、ページを検索する際にメモリ上にページを保持すると思うがこれは膨大なテーブルだとどうなるのだろうか？と疑問に思ったがそれらの問題を上手く解決するために Buffer Pools が存在する。
次の内容は Buffer Pools について。