Database Internals を読み解く ~Introduction and Overview~
はじめに
ゴールデンウィークが外出自粛一択になってしまったので前から気になっていた Database Internals を買った。
なので、ぼちぼち読み始めつつ学んだことをメモ程度にまとめていきたい。
参考文献の構成
前半はストレージエンジン、後半は分散システムについての二部構成になっている。
ストレージエンジン部分は B-Tree Index やトランザクション処理とリカバリー、ファイルフォーマットなど、これぞストレージエンジン感のある部分が解説されている。
分散システム部分は分散トランザクション、レプリケーション、分散システムにおける一貫性などの話が展開される。
愚直に最初から読んでいく。
Introduction and Overview
DBMS Architecture
コンポーネント間の区別などに違いがある場合もあるがDBMS の大まかなアーキテクチャは以下の図のようになっている。*1 *2
DBMS は一般的にサーバ・クライアントモデルを取る。クライアントからのリクエストはトランスポートサブシステムで受け取り、下のレイヤーへと伝播していく。
サーバインスタンスはリクエストを受け取り次第、クエリをパーサーにかける。ここでは単なる構文解析の他にアクセスコントロールの確認を行う。これらの手順を全てパスした場合、オプティマイザによる最適化が行われる。ここでの最適化というのは冗長な部分やそもそもに不要な部分の除去、その後に行われるカーディナリティ*3をはじめとした統計情報を用いた効率的な実行方法の構築などを指す。
クライアントのリクエストによってわたってきたクエリが最適化までされた段階で実行計画が提供される。ここで提供される実行計画は結果が確実に返却される一連の流れであり、結果は同じだが効率が異なる複数の実行計画から最適なものが選択される。
その後はストレージエンジン内で複数のコンポーネントを跨いで実行される。ストレージエンジンには次の要素が含まれる。
- Transaction Manager
Transaction Manager では DBMS 内で論理的整合性が崩れないようにトランザクションを管理する。
- Lock Manager
Lock Manager はトランザクションが実行されている間、データベースオブジェクトが整合性などに違反しない状態を維持するために必要な同時実行制御上必要なロックを管理する。
- Access Method
ディスク上のデータ整理とアクセスを管理する。ここでのアクセスメソッドとはヒープファイルや B-Tree, LSM Trees などの選択を含む。
- Buffer Pools
メモリ上のデータ管理、キャッシュする。リカバリに関するログなどもここで扱う場合がある。
On-Memory vs Disk-Based DBMS
DBMS はメモリ上にデータを持っておく場合*4と、ディスク上にデータを持っている場合がある。*5
オンメモリといっても、一次データをメモリ上に持っているだけで WAL のような機構を持っている場合はログをディスク上に吐く場合が多い。ディスクベースの DBMS はディスク上に一次データを持っているが、一時的なストレージとしてメモリ上にキャッシュしている。
オンメモリの利点としては比較的低いアクセスコスト、パフォーマンス、アクセス粒度の面でディスクベースの DBMS より優位な点がある。またその実装を主にメモリが対象になるためディスクベースのそれと比較してシンプルになりやすい。
OS の観点から見るのであれば、オンメモリであればメモリの確保、開放といった管理を抽象化できるという利点存在し、ディスクベースではデータのシリアライズ方式や参照方法、断片の再構成*6などを行う必要があるため複雑化しやすい。
メモリ上でデータを管理する場合、揮発することを考慮しなければならないことが大きな制限となるがこの点は不揮発性メモリの登場によって解消される可能性が出てきている。
Column Versus Row-Oriented DBMS
列指向か行指向かという話なので、RDB に関しての話。
それぞれ、行と列でデータ構造を分割して*8保存する。MySQL, PostgreSQL は行指向データベース。
Row Oriented Data Layout
このタイプの DBMS はデータをレコードか行として保持する。
表形式にすごく近い表現方法をもつデータレイアウトだが、表形式とは異なる。またこの形式の場合、レコードや行を一意に特定できるキー*9が存在するなら様々な面でうまく働く。
また行指向データレイアウトの大きな利点として行単位でデータにアクセスし、保存することが前提となるので空間局所性*10が向上する。これはディスクの1ブロック内*11 (()) にページがもつ全てのデータを格納できる場合、特に効果を発揮する。
Column Oriented Data Layout
列指向データベースは行を列に分けて保存する。あまり馴染みがないと思ったのは正しく、なぜならいわゆる Web 系のデファクトスタンダードである DBMS では採用されていないことが多いため。
この列指向データレイアウトを採用する場合どこに利点があるのかと、データ分析に利用する場合は行指向であれば不必要なデータも一旦読み込まれてしまう*12ことがあるが、列指向はその名の通り列で分かれているためパフォーマンスを出しやすい。
列で分割されていると普通に使う時辛くないかとおもうことがあるかもしれないが、それを解消するため列指向データレイアウトはデータの最小構成単位がタプルになっていることが多い。このタプルは仮想IDと列の値の組になっていることが多く一意に行に相当するものを探索することが可能となる。
Data file and Index File
DBMS の最も大事な目的はデータを管理し、迅速なアクセスを提供することにある。そのために、物理的なデータをどのように管理するかを考慮する必要がある。*13
実データはファイルに持っておくことがほとんどだが、フラットファイルではなく実装依存の固有形式なファイルフォーマットをとっていることが多い。これにはいくつかの理由がある。
まずはストレージの観点から、ファイル操作時のオーバヘッドを最小にしたいという理由がある。次にアクセス、正確には読み込みに関連して限りなく小さいステップでデータを読み込むため。最後に更新時になるべく変更回数を小さくするため。
このような理由を可能な限り満たすために Slotted Page といった形式が存在する。また削除については多くの DBMS では削除マーカーを置いて論理削除することで削除したように見せている。
DBMS はデータ操作、特に検索においてインデックスと呼ばれるものを補助的に使用している。インデックスはレコードのメタデータを持っているため、全てのレコードを探索することなく少ない回数でレコードを探索することができる。
Data Files
データファイルは index-organized table, heap-organized table, hash-organized table などを用いて実装することができる。
index organized table はデータ自身とそのインデックス情報を含み構成される。またそのレコード自体は順に配置されるため、実際にスキャンするときはその内容をシーケンシャルスキャンすればよい。
heap organized table は順序関係ないレコードの列挙で構成されるヒープファイルの集まりとなる。順序は関係ないが基本的にレコード順になっている。レコードが追加されてもファイルの再構成などを必要としないが、特に検索時にそれぞれのレコードに対するインデックスがないとフルスキャンするはめになる。
hash-organized table ではレコードそのものはキーのハッシュ値によってバケットに格納される。レコードは追加順かキー順でソートすることで検索が高速化できると言われている。
Index Files
インデックスは前述の通り、レコードを効率的に検索できるように構造化したものを指す。インデックスを構築するのに必要なデータはレコードを識別するキー*14か主キーになる。
インデックスには大きくわけて二つの種類がある。プライマリインデックスとセカンダリインデックス。MySQL で言えば主キーがあれば自動的に付与される*15ものがプライマリインデックスで、手動で後から貼ったインデックスをセカンダリインデックスという。
記憶がただしければ、セカンダリインデックスを用いて検索した場合、セカンダリインデックスのリーフノードの値はプライマリインデックスの値であり、それが判明した段階でプライマリインデックスで検索し最終的にレコードにたどり着くはず。
インデックスを含む場合、ファイルの構成方法を二つ存在する。 インデックスを含めたまま物理ファイルにするタイプと、インデックスは別ファイルに分割するタイプ。前者を Index organized table というらしい。
前者はプライマリインデックス、後者はセカンダリインデックスでよく使われるみたい。
最後に
ここで学んだこととしてあげたものはこの後詳細な解説がやってくるのでざっくりとまとめておいた。
次はインデックス、 B-Tree に関する話。
*1:分散 DB など分散システムを前提とする場合はコンポーネント間の関係はこの限りではない。これはあくまでも単一のサーバインスタンスとして DBMS を利用する場合。
*2:図はまとめていい部分や今回読まない部分を含んでいるため書籍の図と差分がある
*3:カラムの値の種類がレコードの数に対して多いか少ないか https://www.shift-the-oracle.com/words/cardinality.html
*4:Redis のようなオンメモリ KVS
*5:大体の RDBMS はディスク上に一次データを持っている。MySQL もこれ。
*6:slotted-page などで論理削除を用いない場合を考えるとわかりやすい
*7:Redis であれば AOF, RDB がまさにそれにあたる
*9:いわゆる主キー、Primary Key、PK と呼ばれるやつら
*10:キャッシュを考慮する場合に重要となる指標のひとつ。連続または近傍領域に対して比較的近い時間にアクセスがされればされるほど空間局所性があるという。ある特定の行の次の行にアクセスすることは冷静に考えてそれなりに存在する
*11:多くの場合は 4 KB ではあるが、DBMS によってはページサイズが 8 KB, 16 KB になっている場合もある。さらにページを 16 KB として、それを連続して配置させるスペースという概念で管理する場合もある。
*12:SELECT column FROM hoge みたいにすれば列だけ読み込めるじゃんと思うかもしれないが、内部的には必ずしも特定の列のみをストレージメディアから読み込んでいるとは限らない。
*13:オンメモリは考えない。あくまでも確定した実データをディスクに持っている場合の話。
*14:重複が認められているもの。ただし重複しすぎると大体インデックスが効かなくなる
*15:主キーがない場合はその代替に相当するもので構成される
