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

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

InnoDB におけるページとインデックスの物理的な構成について

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

はじめに

どうも、最近このアドカレが本当に終わるのかどうなのか心配になってきているけんつです。
今回は DBMS のストレージ構造を考えていたらインデックスを物理的に保存する場合の構造ってどうなってるんだろうなぁと思ったので InnoDB の内部構造とその物理的な形式を追っていく。
あんまり深く追ってしまうと本当にキリが無いので自分の理解が足りない部分をメモしていく感じになる

参考にしたサイト


blog.jcole.us
blog.jcole.us

InnoDB のスペースファイルレイアウト

InnoDB のデータストレージモデルは MySQL のドキュメントではテーブルスペースと呼ばれているが InnoDB 自体ではファイルスペースと呼ばれている。
スペースは ibdata1, ibdata2, ... などで複数の物理ファイルで構成されるが単一の論理ファイルとして扱われる。

InnoDB の書くスペースには 32bit のスペースIDが与えられる。このIDを元に DBMS やストレージはスペースを参照する。
またこの ID は 0 から始まり、ID が 0 のものはシステムスペースと言われる。このシステムスペースはストレージに関する内部的な情報を保持する。

ページ構成

各スペースは 16 KB*1 毎に 32 bit のID が割り当てられページに分割される。
このページ ID はスペースの先頭からのオフセットに過ぎない。

実際にページは次のようなレイアウトを取る。

https://i0.wp.com/jcole.us/blog/files/innodb/20130103/50dpi/Basic_Page_Overview.png
https://i2.wp.com/jcole.us/blog/files/innodb/20130103/50dpi/FIL_Header_and_Trailer.png


FIL Header *2というものが 38 byte あり、ボディに相当する部分が 16338 KB ある。
そして末尾に FIL Trailer というものが 8 byte ある。
Header はページの種類を示すために使用される。

FIL Header
name length
Checksum 4 byte
Offset (Page Number) 4 byte
Previous Page 4 byte
Next Page 4 byte
LSN for last page modification 8 byte
Page Type 2 byte
Flush LSN (0 except space 0 page 0) 8 byte
Space ID 4 byte
FIL Trailer
name length
Old-Style Checksum 4 byte
Low 32 bits of LSN 4 byte

Header, Trailer の構造的特徴

まずページタイプはヘッダーに保存される。このヘッダーには後に続くページデータを解析するために必要な情報が入っている。またスペースIDもヘッダーに直接保存されている。
ページは初期化される段階でページIDをヘッダーに保存する。そして、フィールドから読み取られたページIDがファイルへのオフセットに基づいていることを確認する。

また Previous Page と Next Page というフィールドが存在するように、ページは前後のページに対するポインタを保持している。
これによりページは双方向リストとして扱うことができる。インデックスの構築はこの特性を利用した上で全てのページをリンクすることを目的としている。

LSN*3 についてはまだ CMU の講義で Database Recovery まで進んでいないので触れない。

スペースファイル

スペースファイルは多くのページの連続体となっている。ただ連続しているわけではなく、効率的に管理するためにページは64個で1グループと見なされエクステントという単位で管理されるされている。このエクステントを連続して保持しているのがスペースファイルとなる。
そのためは次のような構造を取る。

https://i2.wp.com/jcole.us/blog/files/innodb/20130103/50dpi/Space_File_Overview.png

FSP_HDR, IBUF_BITMAP, INODE*4 が続いたあとはエクステントと言われる領域が連続する。

テーブル毎のスペース

InnoDB は FIle_per_tablespace がデフォルトで有効になっているためテーブルごとにスペースファイルを作成する。
ibd ファイルというものがそれに該当するが次のような構造を取る。

https://i2.wp.com/jcole.us/blog/files/innodb/20130103/50dpi/IBD_File_Overview.png

この構造で注目したいのはインデックスに関する情報を保持しているという点。
ルートページに関するインデックスや、インデックスにおいてノードページとリーフページと情報を保持している。

これが物理的なインデックス情報の保持に関わってくる。

おわりに

インデックス全然わからない。

*1:デフォルトでは 16 KB となっているが変更可能

*2:FIL というのは File の短縮形らしい

*3:ログシーケンス番号というもの。リカバリの際に使用することがあるらしい。

*4:Index のノード情報を持つ

既存の RDBMS のストレージがどのような仕組みになっているのか調べてみる

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

はじめに

どうも、最近ずっと DBMS について勉強していたら全然コードを書く暇がなくて先にストレージ部分から作ってしまおうと思ったけんつです。
最近は鬼滅の刃をみて号泣するオタクをやってます。

ここまで勉強してみて

ここまで CMU Database Systems を追ってきて、ストレージ周りという意味では一段落したのかなと思っている。
ただここで気になったのが既存の RDBMS のストレージ周り、いわゆるストレージエンジンは実際にはどういった実装がされているのかということ。
なので今回はそれを調べて色々とまとめていく。

InnoDB を追っていく。

特に使えるからという理由でなく、なんとなく MySQL が好きなので MySQL のデフォルトストレージエンジンである InnoDB を対象に追ってみる。
といっても、何をどう追えばいいのかわからなかったので適当に「InnoDB Internal」 みたいなぐぐり方をして出てきたものを足がかりに調べてみる。

InnoDBアーキテクチャ

ここでは MySQL 8.0 で使われている InnoDB を対象にまとめてみる。

dev.mysql.com

InnoDBアーキテクチャを見ていく。

https://dev.mysql.com/doc/refman/8.0/en/images/innodb-architecture.png

この画像にあるなかで、今回やっている内容に関係しそうなものと言えば

メモリに配置されるものであれば

  • Adaptive Hash Index
  • Buffer Pool

ディスクに配置されるもので

  • Tablespace

あたりとなる。

OS Cache についてもまとめる必要がありそう。

Adaptive Hash Index

これはトランザクション機能や信頼性を犠牲にすることなく、ワークロードとバッファプールに十分なメモリをもたせたシステムで、オンメモリデータベースのような機能をもつ。
頻繁にアクセスされるインデックスのページに応じてメモリ内に構築されるハッシュインデックスで、キーに対する値を取得する際に使用される。
MySQL 5.6 における Adaptive Hash Index にはなってしまうが次のドキュメントに B+ Tree と Hash Index の比較が書かれている。
MySQL :: MySQL 5.6 リファレンスマニュアル :: 8.3.8 B ツリーインデックスとハッシュインデックスの比較

Buffer Pool

これは InnoDB にアクセスが行く前に構えているテーブルとインデックス情報をキャッシュするメモリ上の領域を指す。
データそのものにアクセスする際にこれにキャッシュされているとメモリ上の値を直接使用することができるため処理の高速化が予想できる。

また面白いことに、このバッファプールは通常単方向リストとして実装されることが多いが
そのバッファプールリストは2つのサブリストからなり、バッファプールが使用できる領域の 5/8 が比較的直近のデータが格納される領域となっていて
残り 3/8 が比較的古いデータが保持される構造になっている。
こうなっているのは、まずページが読み込まれた時に比較的古いデータが保持されるリストの先頭に追加される。
古いデータを保持するバッファプールリストの要素が読み込まれた場合、それは新しいデータを保持するリストに移動する。
この様にして効率よくメモリを利用する仕組みが取られている。

バッファプールは LRU に基づいて開放される。
MySQL :: MySQL 8.0 Reference Manual :: 15.5.1 Buffer Pool

ざっとみた感じでは CMU Database Systems で紹介されていたものと似ている。

Table Space

これは Database Storage の時にやった内容とは少し異なる方法で実装されている。
そもそもにこれは何かというと実際には、これがデータを保持しているということになっているらしいが、次のような構成を取っている。

https://qiita-user-contents.imgix.net/https%3A%2F%2Fqiita-image-store.s3.amazonaws.com%2F0%2F17852%2F30270220-fd4a-b404-80f3-f149990c63a4.png?ixlib=rb-1.2.2&auto=compress%2Cformat&gif-q=60&s=03922b6764747f71adf3285bc5f14ae9
基礎MySQL ~その 5~ InnoDB② - Qiita

テーブルスペース*1の中にセグメントという領域があり、さらにその中に extent という領域*2が存在し
その extent の中にみんな大好き Page *3が格納されている。

テーブルスペースといっても、様々でその中でも特に関係のあるものといえば「File-Per-Table Tablespaces」だと思う。
これを有効にしない状態でデータを書き込むと ibdata が肥大化するなどの懸念があるが、これを有効にすることでテーブル毎にテーブルスペースを独立させることができるため単一ファイルの肥大化を防ぐことができる。

OS Cache と Database Storage

通常、Linux 環境下でファイルにアクセスする場合ファイルキャッシュを経由する。ファイルキャッシュは本来、同一ファイルの読み込み等が行われた際にそれを通すことで読み取りを高速化したり
遅延書き込み機能を使うことでプロセスに対する書き込み性能を向上させる役割がある。

しかし、ほとんどの DBMS にはバッファプールが存在するためファイルキャッシュを経由するとキャッシュを実質的に2つ経由することになり無駄な遅延が発生する。
そのため、 ファイルキャッシュを利用しない Direct I/O という機能*4を使い余分なキャッシュを経由せずにデータをファイルとして扱うようにしている。

これは InnoDB にも搭載されている機能である。

おわりに

MySQL のストレージエンジンである InnoDB の仕組みについて、 CMU Database Systems とかぶる部分や、被っては居ないが特に重要という点についてまとめてみた。
これらを踏まえて、次は DBMS のストレージ部分を復習してから設計にとりかかる。

*1:/var/lib/mysql 以下に存在する hoge.idb がそれに該当する

*2:64 page = 1MB

*3:MySQL はデフォルトで 16KB のはず

*4:Linux Kernel 2.4 で導入された

CMU Database Systems をひたすら追っていく ~09 Index Concurrency Control ~

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

はじめに

どうも、最近このアドカレの一週間分をみてこれあと二週間半分やるのかと思うとすごく辛い気持ちになっているケンツです。
今回はインデックス、つまりここでは B+ Tree の同時実行制御についてやっていきます。

Index Concurrency Control

同時実行制御プロトコルは共有オブジェクトでの同時操作において正しい結果を確保するために DBMS が使用する方法を指す。
ここで言う「正しい」とは主に2つの意味合いがあり、

  • 論理的正確性: 表示されるはずのデータを表示できるかどうか。スレッドが読み取りを許可する必要のある値を読み取ることが出来るかどうかに関わってくる。
  • 物理的正確性: オブジェクトの内部表現が適切かどうか。データ構造内にスレッドが向こうなメモリ位置を読み取るポインタが存在しないことに関わってくる。

ここでは論理的正確性に重点を置いて進めていく。

Locks vs Latches

以前にもどこかで書いた記憶があるけど、ロックとラッチの話。インデックスにおけるロックやラッチの話なので再度ここにまとめおく。

Lock
Latches
  • Index の内部データ構造の重要なセクションを他のスレッドから保護する。
  • 処理が行われている間適宜発生する
  • DBMS は変更をロールバックさせる必要はない

またラッチには2つのモードが存在する

  • READ: 複数のスレッドが同時に同じアイテムを読み込むことを許可する。スレッドは別スレッドが読み取りモードで持っている場合読み取りラッチを取得することができる。
  • WRITE: 1つのスレッドのみがアイテムにアクセスできる。他のスレッドがいずれかのモードでラッチを取得している場合、スレッドは書き込みラッチを取得できない。

Latches Crabbing/Coupling

Crabbing / Coupling*1 は複数のスレッドが同時に B+ Tree にアクセス/変更を許可するための決まりのこと。
次のような手順を取る。

  • 親のラッチを取得する
  • 子のラッチを取得する
  • 安全に操作できる場合は、親のラッチを解除する。

ここでいう安全に操作できる場合とは更新時にノードの分割が行われたり、マージされない状態を指す。

基本的なラッチの手順として更に細かく見ていく。

  • 検索: ルートから開始して下に移動し、子のラッチを確保してから親のラッチを解除する
  • 挿入/検索: ルートから開始して必要に応じて任意の数のラッチを取得する。その後、子をラッチを取得したら安全かどうか確認する。安全な場合は全ての親のラッチを解除する。
Improved Lock Crabbing Protocol

このように一見素晴らしく見えるラッチのプロトコルにもいくつか問題がある。というのもトランザクションが挿入・削除を行う場合排他的なラッチを取得するがこの排他的ラッチはルートから取られているというがまずい。
ルートから排他ラッチが取られている場合、その並行性は大きく制限されてしまうから。

その代わりと言っては何だが、サイズ変更が必要なマージや分割が必要になることはまれであるためトランザクションは共有ラッチををリーフノードまで取得することができる。それぞれのトランザクションはターゲットリーフノードへのパスが安全であるということを想定し、 READ ラッチを取得し、検証することができる。

仮にパス内のノードが安全で無い場合は以下の様に動作する。

  • 検索: 上のものと同じ挙動をする
  • 挿入/削除: READラッチを検索の場合と同様に設定し、リーフに移動する。そのあとリーフに WRITE ラッチを設定する。リーフが安全でない場合は全てのラッチを解除し、上記の挿入/削除プロトコルを使用してトランザクションを再開する。

Leaf Node Scans

ここまで紹介したラッチはトップダウン方式を取る。*2
しかし、それを許容すると目的のラッチが使用できないといった場合が想定できる。その場合は別のスレッドがラッチを開放するまで待機する必要がある。これによりデッドロッ具が発生しない。
しかし、リーフノードスキャンでは2つの異なる方向から*3走査されるため、デッドロックの影響を受けることがある。またインデックスラッチではデッドロックの検出、回避をサポートしないことが多い。
そのため、この問題への対処は待機しないというモードをサポートする必要がある。スレッドがリーフノードでラッチを取得しようとした場合、その操作を中止してラッチを開放し、操作を再開させる必要がある。

おわりに

今回はそれなりに短い分量だったがインデックスの同時実行制御についてだった。
ここまででストレージに関するところは一段落したと思っているので、次回以降は実際の RDBMS ではどのような実装がされているかをまとめていく。
それが終わり次第、実装していく簡易的な DBMS の特にストレージ周りの設計をしていく。

*1:この2つをどう訳せばいいかわからない

*2:現在探索しているノードの下にあるノードからのみラッチを取得できる。

*3:左右両端から探索される

CMU Database Systems をひたすら追っていく ~07, 08 Tree Indexes Part 1,2~

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

はじめに

どうも、最近終わったはずの卒研に追加要求が出てきて非常にしんどい気持ちになっているけんつです。
今回は Tree Index です。
実はこれ、この記事を書き終わってから書いているのですが、この記事だけ異様に時間がかかっているので何書いてんだろうなって自分でも思ってます。

Tree Indexes

Indexes

テーブルインデックスとはテーブルの列に対するサブセットのレプリカである。
また DBMS はテーブルのコンテンツとインデックスが常に同期的されていることを保証する必要がある。

DBMS の責務は他にもあり、クエリが実行された際に適切なインデックスの利用することもその一つである。*1

一般的に要素の、つまりタプルの検索に使用されることが多いがこれにはメリットだけでなく、インデックスを多く生成すればそれだけストレージで管理する要素数が増えてしまうのでトレードオフとなる。*2

B+ Tree

インデックスを構築するにも様々なデータ構造があるが DBMS 特に RDBMS で一般的な B+ Tree を取ることを考える。
まず B+ Tree とは、データのソートを維持し、検索、追加、削除を O(log n) で行うことができる平衡探索木を指す。
また順序を維持する必要がある DBMS では大体 B+ Tree でインデックスが構成される。
B+ Tree 自体は B Tree をベースに B Link Tree の相互参照ポインタなど他の B Tree データ構造がもつ特性を合わせて実装される。

更に正確に言うのであれば、B+ Tree は次のような特性を持つ M-way Search Tree のことを指す。

  • 全てのリーフ濃度の深さは同じになっている
  • root 以外の内部ノードは最低でも半分以上データが入っている。
  • k個のキーを保持する内部ノードは k+1 個の null でない子要素を保持する。

B+ Tree の全てのノードには、Key-Value のペアの配列が含まれる。

  • すべてのノード配列はキーでソートされる
  • 内部ノードの値配列には他のノードへのポインタを保持する
  • リーフノード値に対する2つのアプローチとして、レコードIDとタプルデータが存在する。

B+ Tree の操作

Insert
  • まずリーフである L を探索する
  • ソートされた順序で L にデータを追加する
  • 追加できない場合は L を L1, L2 と分割して、それぞれの要素が均等になるように再構築して中間キーをコピーする
  • 内部ノードを分割する場合は、要素を均等に分配し中央のキーを親ノードにする。
Delete
  • リーフ L を探索する
  • エントリを削除する
  • 削除後 L が含む要素数が上限値の半分より多い場合は削除を完了する
  • その他の場合では隣接するリーフノードを動かすことができる場合も存在する
  • 上のパターンで再構築できなかった場合は、 L と隣接ノードをマージして親を削除する

B+ Tree の設計

ノードサイズ
  • B+ Tree のノードサイズはディスクの速度に依存する。可能な限り多くのタプルをノードをディスクからメモリ上に配置することを考慮する。
  • ディスクの速度が遅いほどノードサイズを大きくする
  • いくつかの手法ではより多くのキーに対する参照を保持するのとスキャンが遅くなることのトレードオフを考える必要がある
マージの境界線
  • 一部のDBMSではノードの要素数が半分以下になったときに必ずマージを走らせるという構造になっていない
  • マージ操作が発生するタイミングを遅くすることで木構造の再編成の量を減らすことができる場合が存在するため
  • DBMS がアンダーフローを発生させてから定期的に再構築するほうがよい場合もある
可変長キーの扱い
  • ポインタ: キーをタプルへのポインタとして保存する。(ほとんど使用されない)
  • 可変長ノード: B Tree の各ノードサイズを可変にする。メモリ管理のコストが上がるためあまり使用されない
  • キーマップ: ノード内の Key-Value のリストにマップするポインタの配列を含ませる。スロットページに似たアプローチを取る
ユニークでないインデックス
  • 重複キー: 同じノードレイアウトを使用するが、重複キーを複数保存する
  • 値リスト: それぞれのキーを一回だけ保存して一意な値リストを維持する
ノード内検索
  • 線形探索: ノードの Key-Value エントリーを探索するべきキーが見つかるまでフルスキャンする。
  • 二分探索: その名の通り。事前にノードがソートされている必要がある。
  • 補間探索: ノード内の既知のキー値に基づいて検索の開始位置を概算する。その位置から線形探索する。これも事前にソートされている必要がある。

B+ Treeの最適化

プレフィックス圧縮
サフィックスの切り捨て
  • 内部ノードのキーはトラフィックの誘導にのみ使用されキー全体を保持する必要がない
  • インデックスを利用し探索順を決めるのに最小限のプレフィックスのみを保存する

インデックスの追加的な利用

  • 暗黙的なインデックス: 殆どの DBMS で行われている様にインデックスを自動生成して主キー等に適用されるものがある
  • 部分的なインデックス: テーブルのサブセットに対してインデックスを貼る。これによってインデックスそのもののサイズとそれの管理コストが減る可能性がある
  • カバーインデックス: クエリを実行する上で必要な全ての属性はインデックスを利用できるため、タプルを取得する必要がない場合がある
  • インデックスを含む列: インデックスのみのクエリをサポートするためにインデックスに追加の列を埋め込む。
  • 関数/式インデックス: 関数、式の出力を元の値でなくキーとして保存する。そのインデックスがどういったクエリで使用できるかは DBMS が決める必要がある

スキップリスト

スキップリストは中間ノードをスキップする複数のレベルにおける追加ポイントを持つソートされた単方向リストを指す。
一般的に O(log n) で検索を行うことが出来る。これは B+ Tree 以外のインデックスを構築するためのデータ構造として利用することが出来る。

これが B+ Tree を超える点として、B+ Tree より少ないメモリで構成できる点やインサートデリートでデータ構造を再構成する必要が無い点にある。
また逆に B+ Tree と比較した場合の欠点として、ローカリティを最適化しないために、ディスク/キャッシュフレンドリーでは無い点や、双方向リストを実装しない限り逆方向への探索がコストかかるから。

基数ツリー

これはトライデータ構造の変形でキー全体を比較する代わりにキーのデジタル表現を使用してプレフィックスを調べる手法をとる。
キーの各要素にノードが無く、キーが異なる前に最大のプレフィックスを表すようにノードが統合されるという点でトライデータ構造と異なる。
木構造の深さは、キーの数でなくキーの長さに依存する。リーフノードへのパスはリーフのキーを表す。全ての属性は基数ツリーの2進数比較可能な数字に分解出来るわけではない。

おわりに

卒研やら内定者懇親会へ行ったりしていたら気がつけばこの記事を書くことに一週間も費やしてしまった。
全く理解できていないので、一周した後に加筆修正する必要がありそう。

*1:インデックスがあれば必ずそれを利用するのでなく場合によっては使用しない場合がある。

*2:管理コストを上げるか、実行速度を向上させるか

CMU Database Systems をひたすら追っていく ~06 Hash Tables~

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

はじめに

どうも、最近ダーク・タワーという映画がめちゃくちゃ刺さりまくって何周も見ているけんつです。
今回はハッシュテーブルに入っていく。徐々にレイヤー(ヒエラルキー)が上がってきてそれなりにわかりやすい部分が多くなってきているので少しスピードアップしていきたい。

Hash Table

ハッシュテーブルはキーがハッシュ値マッピングされている連想配列を抽象化したデータ構造のこと。
これらは大きく2つの部分から成る。

  • ハッシュ関数: これは大きなキースペースを小さなドメインマッピングするために使う。配列へのインデックスを計算するために使用されるがスループットと衝突率のトレードオフを考慮する必要がある。
  • ハッシュスキーマ: ハッシュの衝突を処理するためのもの。衝突回避のために大きなハッシュテーブルを割り当てる必要性とキーを検索・追加するために追加の命令を実行することのトレードオフを考慮する必要がある。

これら全てを考慮すると非常に規模が大きく複雑なものが出来上がってしまうので、ここではシンプルなエレメント毎にひとつのスロットを持つ巨大な配列をハッシュテーブルを想定する。

この章ではこれらを順をおってみていく。

Data Structures

その前にハッシュテーブル以外にも DBMS は内部的に様々な種類のデータ構造を使用している。例えば以下のようなもの。

  • Internal Meta-Data: データベースとシステム状態に関する情報を保持する
  • Core Data Storage: データベース内のタプルを保存する基礎となるストレージ
  • Temporary Data Structures: クエリ実行中に一時的なデータ領域を作成し、実行を高速化する(Join など)
  • Table Indexes: 特定のタプルに対する検索を高速化するための補助的なデータ構造。

またこれらのデータ構造を設計するためには以下の観点が重要になる。

  • Data Organization: メモリ上のレイアウトとデータ構造にどのようにデータを保存するかということ
  • Concurrency: 複数のスレッドが単一のデータ構造にアクセスする方法を確立すること

Hash Function

Open Addressing Hashing
  • スロットが単一の巨大なテーブルを作成する。
  • テーブル内の次の空きスロットを線形に探索して衝突を回避する
  • 値が存在するかどうかを確認するにはハッシュを用いてオフセットに移動してキーをスキャンする。
  • 無駄な評価の回数を減らすため、ハッシュキーの衝突を避けることが重要
Cuckoo Hashing
  • 異なるハッシュ関数によるテーブルを複数管理する
  • 要素の追加時に全てのテーブルを確認して空きスロットがある領域を選択する
  • 空きスロットを保持するテーブルが無い場合、いずれかのテーブルから要素を削除して新しい領域を確保する
Chained Hashing
  • ハッシュテーブルの各スロットのバケットに対するリンクリストを保持する
  • 同じハッシュキーを持つ要素を同じバケットに配置することにより衝突を避ける
  • バケットにキーを追加出来ない場合リストに別のバケットを作成し格納するという手段をとり続けるためハッシュテーブルは巨大になっていく
Extendible Hashing
  • Chained Hashing のようにバケットを使用したアプローチを取る。
  • バケットのリンクリストを無制限に増やすのではなく、増分的に分割する。
  • バケットがいっぱいになるとバケットを分割し要素を入れ替える
Linear Hashing

おわりに

今回はそこまで量があるわけではないが検索などを高速化するためのハッシュテーブルの構築に関わる内容となった。
これで不思議に思うが最悪存在しなくてもいいハッシュテーブルを作成する理由とは何なのか。
それは次の章にあるインデックスを構築するためらしい。というわけで次はインデックスの話となる。

CMU Database Systems をひたすら追っていく ~05 Buffer Pools~

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

はじめに

どうも、最近「これ1人アドカレめちゃくちゃキツイな」とにわかに思い始めたけんつです。
最近は Netflix オリジナルコンテンツの映画にはまっています。

今回は前回紹介したページなどを一時的に保存するために使う Buffer Pools についてです。

Buffer Pools

Buffer Pools Organization

バッファプールはメモリ上に固定長のページを要素に持つ配列として構築される。この配列の各エントリーをフレームと呼ぶ。
DBMS がページをリクエストする際にディスク上のページをこれらフレームにコピーする。

Buffer Pools Meta Data

ページテーブルという現在メモリに格納されている*1ページを追跡するための領域が存在する。
これらのようにページ毎に追加のメタデータを保持する。メタデータの中にはダーティフラッグ*2*3や Pin Counter *4が存在する。

Lock vs Latches

Lock

ロックはよく聞くやつ。他のトランザクションから現在走らせているトランザクションの処理を保護するもので、これはトランザクションが有効な期間は保持される。
しかし、変更をロールバックできるという特性を満たす必要がある。保護されるものとしてはタプルやテーブル、インデックスが挙げられる。

Latches

ラッチと言われる代物。DBMS 内部のデータ構造の重要なセクションを他のスレッドから保護する役目がある。これもロックと同様に、オペレーションが走っている間は保持される。
こっちはロックと異なり、ロールバック出来なくても良い。

Page Table vs Page Directory

ページディレクトリとは前にもやったように、ページをまとめて特定のディレクトリに格納しておきページIDとその場所をマッピングするというもの。ただし、DBMS が再起動した時のために全ての変更を終了前にディスクに書き込む必要がある。


対してページテーブルという代物は先にも説明したように、バッファープールフレームにコピーしたページのIDをマッピングする。
これはページテーブルとは異なり、メモリ上に保存されるためディスクに保存する必要はない。

ここまでのメモ

バッファプールにはデータの原本、またはコピーが存在する。
SELECT 等を行った時はバッファプールを検索する。仮に対象のページが無い場合はバッファプールを LRU に沿うかたちで開放してページをバッファプールに確保してから検索する。

UPDATE,INSERT,DELETE のときはバッファプールに書き込んで、ログファイルに書き込むそのあとにゴニョゴニョする*5

Buffer Pools Optimization

Multiple Buffer Pools

DBMS は様々な目的のために複数の種類のバッファプールを持つ場合がある。これにより、ラッチが競合するイベントが減り局所性が向上する。
いくつかの実例は以下に挙げる。

  • Multiple Buffer pool instances
  • Per-database buffer pool
  • Per-page type buffer pool
Pre-Fetching

クエリプランに基づいてページを事前に取得することで最適化することが出来る。ページに対して連続アクセスするときによく使用される。

Scan Sharing

同一のページを複数のスレッドが同時に読み込む場合にそれらのカーソルを他のカーソルにアタッチして同一の結果を用いるというもの。

Replacement Policies

この章は、バッファプールに確保したデータを必要に応じてどうやって置き換えて行くかという話になる。
基本的には LRU*6 が前提となる感じがある。

CLOCK

その名の通り、時計と似たような動きをするやつ。
ページごとのタイムスタンプを必要としないアルゴリズム。循環バッファを構築する必要がある。

  • 各ページにアクセス時にフラグを立てる参照ビットが存在する

この性質を使う。
「時計の針」と言われる基準を利用する。この「時計の針」がどのように影響するかというと

  • ページビットが1に設定されているかどうかをスイープチェック時に確かめる
  • 1 なら 0 に設定して、 0 ならそのページを開放する。

これによりバッファプールを置き換えるという。

その他のアルゴリズム
  • LRU-K
  • LOCALIZATION
  • PRIORITY HINTS

Allocation Policies

この章は、めちゃくちゃ短いけどどうやって Buffer Pool に割り当てるかということ。おそらくどのように割り当てても大体は問題ないという感じなのかなと思っている。*7

これには2つある。

  • グローバルポリシー:DBMSがすべてのアクティブなトランザクションに対して決定を行う方法。
  • ローカルポリシー:同時送信の動作を考慮せずに、特定の送信にフレームを割り当てる。

おわりに

ひとまず Buffer Pool についてはまとめきったと思いたい。ところどころ怪しいところがあるけど。
書いてて唯一疑問に思ったこと、といえばバッファプールがデータ原本であり、INSERT,UPDATE,DELETE 時にバッファプールが更新され、そのあと色々あってファイルに吐き出されるなら
ACID 特性の永続性ってどうやって担保しているんだろうか?という疑問が残っている。これを担保するにはそれらの処理が終わった段階でファイルに書き込まないといけないのでは?と思っている。

今後その解説が出てくるだろうか。

*1:つまりバッファプールに格納されている

*2:スレッドがページを変更するときに設定される

*3:バッファプールには存在するがテーブルスペースが存在しないものをダーティページという

*4:そのページを操作するスレッドの数

*5:ここがわからない

*6:最後のアクセスが最も古いものから削除する

*7:実際 InnoDB における Buffer Pool Size で適切な数値というのはデータベースそのものと同等となっている。つまりデータベースにある全てのデータがメモリに乗るような Buffer Pool が存在すればどのようにデータを割り当てても問題はそこまでないということ?

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:列を基準にデータを保存する