WIP【備忘録】Architecture of a Database System(2007)を読む
Architecture of a Database System(2007)を読む
この論文は DB の全体構成を話した後に各構成要素について各章で説明するものとなっている。 「DB についてなんとなく知っている、細かいことは分からん」ぐらいの知識の自分にはかなりピッタシな論文だった。
例えば以下の様な項目を扱っている。
この論文は 100 ページ近くあり非常に長いので、各章についてまとめていこうと思う。 これ、冷静に教科書では...。
Ch1 前書き
感想
この章は以下の項目を扱っている。
- DB の全体構成
- クエリの動く流れ
この章は DB に詳しくない私には特に価値があるものだった。
自分はここを読んで、初めて DB でクエリが処理される流れをイメージすることが出来た。
今まで、何となくおっきなストレージがあってそれを管理するソフトが有るぐらいの気持ちだったので、かなり解像度が上がった気がする。
メモ
まず、DB の主要な構成図が以下のように記載されている。 知らない単語がいっぱいだ...。
引用：Architecture of a Database System
上で見ると、一般的な DB は主要な５つの構成要素を持つ。 これらがどう連関するか、クライアントが簡単なクエリを API を通じて呼び出す流れを見てみよう。
クライアントが API を呼び出し、ネットワークを通じて
Client Communications Manager(CCM)と接続する。 CCM の役割は例えば以下。呼び出し元(クライアント)との接続の確立と記憶
- 受信した SQL クエリ への応答
データや制御メッセージ(ex エラーコード)の送信
DBMS がクライアントの最初のクエリを受け取ると、
Process Managerが計算のスレッドをそれに割り当て、スレッドのデータと制御出力が CCM を通じてクライアントに接続されていることを確認する必要がある。 このステージで特に重要なのはアドミッション制御(ex クエリの処理をすぐに開始するか、十分なリソースが利用できるまで処理を延期するか)だ。スレッドにクエリが割り当てられると、
Relational Query Processerがクエリを実行する。 具体的には以下のような動作。権限の確認 (そのユーザーはそのクエリの実行を許可されているのか)
- クエリを
実行計画へコンパイル - コンパイルされた実行計画は
plan executorによって処理される qlan executorはoperatorは Join, Selct,...等のシステム下位層からレコードを取得するアルゴリズムで構成される実行計画のoperatorはTrandactional Storage Manager(TSM)からデータを取得するTSMは全てのデータ読み取りや操作(ex 作成,更新,削除)呼び出しを管理する。 また、TSMは以下の要素を含む。Access Method... ディスク上のデータを整理してアクセスするアルゴやデータ構造Baffer Manager... ディスクバッファとメモリバッファの間を繋ぐLock Manager... データアクセスの際にはロックをここから取得する(目的例: 他のクエリとの競合を防ぐ)Log Manager... トランザクションを記録するレコードへのアクセスが開始され、クライアントへ計算結果を返す。これは、これまでの手順の逆方向を辿ることで行われる。
Access Methodはoperatorに制御を返し結果のタプルが生成されるとCCMのバッファに配置し、クライアントに送信される。 (大規模なデータの場合は複数の反復を行う)
(勿論、このシンプルな例では DB の主要な構成要素全てが現れているわけではない。)
Ch2 プロセスモデル
感想
この章では Process Manager の役割の説明がされている。 プロセスモデル自体は割と一般的な話だったので理解しやすかった。
メモ
Process Manager は以下の要素で構成されていた。
- Dispatch adn Scheduling
- Admission Control
複数ユーザーが同時に利用できる DBMS を構成するためには、各ユーザのリクエストをプロセス/スレッドにどんな方法で割り当てるかを考える必要がある。 ここでは DBMS のプロセスモデルについていくつかの選択肢を紹介している。 (これは他の多くの並行サーバーシステムのテンプレとして機能するらしい)
まずは、以下のシンプルな仮定の元で、３つの自然なプロセスモデルが考えられる。 (以下の仮定は後の章で緩和される) 多くの主要な DBMS は複数のプロセスモデルを実装している。
仮定
仮定 1. OS スレッドが使用できる... この条件は多くの OS で満たされるが、一部のプラットフォームでは満たされない
仮定 2. CPU は１つ... この仮定は非現実的だが、話を簡単にするために置く
| 利点例 | 欠点例 | |
|---|---|---|
| Process per DBMS Worker | - 実装が簡単 | - プロセスはスレッドよりメモリ消費が激しく、スケールしない - DBMS 接続間(lock table, buffer pool)でのインメモリデータ構造を OS サポート上の共有メモリに置く必要がある(?) |
| Thread per DBMS Worker | - スレッドはプロセスより軽い | - マルチスレッドプログラミング一般の課題がある（競合状態のデバッグが難しいなど） - OS 間での移植が難しくなる場合がある - |
| Process Pool | - Process pe DBMS の利点全て - pool size を柔軟に変更できる |
- DBMS 接続間(lock table, buffer pool)でのインメモリデータ構造を OS サポート上の共有メモリに置く必要がある(?) |
引用：Architecture of a Database System
仮定１を外す 広く使用されている DBMS の多くは、レガシー/移植性/スケーラビリティの観点から、実装において OS スレッドには依存していない。 主要な DBMS のいくつかは、独自の軽量スレッドを実装することでこれを実現している。 各 DBMS スレッドは独自の状態を管理し、非同期インターフェースを介して I/O 等のブロッキング動作を実行し、タスク間でディスパッチするスケジューリングを頻繁に制御するように設計されている。
アドミッションコントロールの役割 複数の同時リクエストはどの様にサポートされるのだろう。
マルチユーザーシステムは、作業量が増加するとスループットは増加するが、ある点を超えるとスラッシングが起こる。 特に、DBMS ではソートやハッシュ join 等の操作はメモリ消費が激しい。 そのため、十分なリソースが利用できない限り新しい作業を始めないように管理する必要があり、アドミッションコントローラはその役割を担う。 アドミッションコントローラはクエリが解析・最適化された後に実行され、そのクエリを{延期, 少ないリソースで実行, 制約なしで実行}の選択をする。
優秀なアドミッションコントローラはgraceful degradation under overload、つまりトランザクションの待機時間は到着率に比例して増加するものの、スループットをピークのままに保つ。
Ch3 並列アーキテクチャ：プロセスとメモリ調整
感想
この章では、DBMS のマクロなアーキテクチャ設計について書いてある。 まとめのところにも書いているが、データ指向アプリケーションデザインという本と内容がかなり被っていたので、半分ぐらいは知っている内容だった。 NUMA は知らなかった。
まとめ
この章では、DBMS のマクロなアーキテクチャ設計について書いてある。 共有メモリアーキテクチャとか、シェアードナッシング、共有ディスクなどだ。 ここら辺の話はデータ指向アプリケーションにも書いてあった気がする。 なので、NUMA の話と仮定２を外す話をメモしておく。
Non-Uniform Memory Access(NUMA)は初めて知った。
NUMA は共有メモリシステムとシェアードナッシングの中間点にある。 NUMA は独立したメモリを備えたシステムのクラスタ上で、共有メモリプログラミングモデルを提供する。 クラスタ内の夫々のシステムは各自のローカルメモリには素早くアクセスできるが、クラスタ相互接続を介したリモートメモリへのアクセスは遅い。(この速度の不均一性が名前の由来)
多くの大規模共有メモリシステムではメモリアクセスの速度に大きな不均一性があるため、NUMA のプログラミングモデルと最適化手法は現在の世代の DBMS システムにとって依然として重要だ。
NUMA の説明は以下の記事がわかりやすい。
https://qiita.com/tomo0/items/5352b8ceb6ccb70390c8
仮定２を外す DBMS スレッドを複数の OS プロセスにマッピングする場合、以下のことを決める必要がある。
- 使用する OS プロセスの数
- DBMS スレッドを OS スレッドに割り当てる方法
- 複数の OS プロセスに分散する方法
経験則としては物理プロセッサごとに 1 つのプロセスを使用するのがお勧めらしい。(今もだろうか？) これにより、プロセスごとのメモリオーバーヘッドを最小限に抑えながら、ハードウェアに固有の物理的な並列処理を最大化できるらしい。
Ch4 リレーショナル・クエリプロセッサ
感想
実行計画という単語自体は知っていたが、それがどんなタイミングで現れて何をするのかというのはこれを読んで初めて知った。
DWH の項はもう少し詳しく知りたいな
メモ
この章では、クエリプロセッサと、ストレージマネージャのアクセス方法の非トランザクション的な側面について説明される。 この章はかなり長いので、詳しい内容はほぼ割愛した。
一般に、クエリ処理は１ユーザーのシングルスレッドタスクと見なすことができる。 また、同時実行制御はシステムの下位層によって透過的に管理される。(Ch5)
ちなみに、SELECT等の DML はクエリオプティマイザを通るが、CREATE TABLE等の DDL はクエリオプティマイザを通らない実装が多いらしい。
(2017 年時点でもそうっぽい？ https://dzone.com/articles/query-optimizer-and-data-definition-language-queri)
とはいえ、一部の製品は、DDL の最適化に着手し始めているらしい。
クエリの解析と承認(Query Parsing and Authorization) クエリが与えられた時、先ずは SQL パーサーが以下のタスクを行う。
- クエリが正しく書かれていることを確認
- 名前と参照を解決
- テーブル名、属性参照等
- このステップ中に、テーブルに関するメタデータを内部クエリデータ構造にキャッシュする場合もある
- クエリをオプティマイザーが使用する内部形式に変換
- ユーザーがそのクエリの実行を許可されていることを確認
- 一部の実装では、クエリの静的解析の段階で完全な承認チェックを行う
- 行レベルのセキュリティ等、クエリの承認チェックを実行中まで延期する利点は多くある
クエリの書き換え(Query Rewrite) リライタは、クエリのセマンティクスを変えないままでクエリ(の内部形式)を単純化および正規化する。その際にはそのクエリとカタログ内のメタデータを用いる。 リライタは主に以下のことを行う。
- ビューの処理
- カタログマネージャからビュー定義を取得し、クエリを書き直す
- 一定の算術評価
- 定数の算術式を簡略化する (ex
R.x < 10+5=>R.x < 15)
- 定数の算術式を簡略化する (ex
- 術後の論理的な書き換え
- 論理的な書き換えは、WHERE 句の述語と定数に基づいて行われる
- 例えば、
R.x < 2 AND Rx = S.yからS.y < 2を追加できる(これにより、index base のアクセス方法を使用し早い段階でデータをフィルタリング出来る)
- セマンティクスの最適化
- 多くの場合、スキーマの整合性制約はカタログに格納されており、一部のクエリの書き換えに使用できる
- 冗長な join の排除 など
- サブクエリの平坦化及びその他のヒューリスティックな書き直し
なお、多くの商用システムのリライタはあくまで論理的な構成要素であり、実際の実装ではクエリ解析の後のフェーズまたはクエリの最適化の初期フェーズのいずれかに存在する。
クエリの最適化(Query Optimizer) クエリオプティマイザは内部クエリ表現を(効率的な)実行計画に変換する。 実行計画は、クエリ演算子のグラフを介してテーブルデータを流すデータフロー図と考えることができる。
引用：Architecture of a Database System
多くのシステムではクエリはまずselect-from-whereブロックに分割され、個々のブロックの最適化が完了した後に後処理としていくつかの演算子(groupbyやorderby,having, distinct等)が各クエリブロックの先頭に追加される。
個々のクエリブロックの最適化は、Selinger による論文(System R)と同様の手法を使用しているが、現在までで様々な拡張が行われた。
- Plan space
- System R では直積をなるべく後にする等の制約により探索空間を狭めていたが、今日のシステムでは状況によっては直積を早めに行うなど探索空間を広めている
- Selectivity estimation
- 今日の多くのシステムは、ヒストグラムやその他の要約統計量を通して属性の値の分布を考慮する
- Search Algorithms
- Parallelism
- Auto-Tuning
クエリの実行(Query Executor)
エグゼキュータは実行計画に基づき演算子のプロシージャを再帰的に呼び出す。
最新のエグゼキュータの殆どはiteratorモデルを採用している。
[fig]
実行計画の全ての演算子（データフローグラフのノード）は、iterator class のサブクラスとして実装される。
イテレータの重要な特性は、 データフローと制御フローを結合することだ。
get_next()はコールスタックを介して呼び出し元へのタプル参照を返す標準のプロシージャ呼び出しなので、コントロールが返される時にグラフ内の親にタプルが返される。(詳しくは論文参照)
アクセス方法(Access Methods) アクセスメソッドは、システムがサポートする様々なディスクベースのデータ構造へのアクセスを管理するルーチンだ。 これらには通常、順序付けされていないファイル（ヒープ）と B+tree 等のインデックスが含まれている。
アクセスメソッドが提供する基本的な API はイテレータ API であり、init()ルーチンはcolumn operator constant形式の「検索引数」（またはシステム R の用語では SARG）を受け入れる。
SARG をアクセスメソッドレイヤーに渡すのは以下の理由がある。
- B+tree の様な index アクセスメソッドを効率的に実行するには SARG が必要
- CPU オーバーヘッドを小さくする(詳細は論文を参照)
また、他のイテレータとは対照的に、アクセスメソッド、トランザクションを取り巻く同時実行および回復ロジックと深い相互関係がある。
データウェアハウス(DWH) DWH はこの論文では「定期的に新しいデータが読み込まれる意思決定支援用の大規模な履歴データベース」と定義されている。
まず、この章で DWH の話がされている理由は２点。
- DWH は、DBMS の非常に重要なアプリケーションである
- この章でこれまでに説明した従来のクエリ最適化および実行エンジンは、DWH ではうまく機能しない。よって、良好なパフォーマンスを実現するには、拡張/変更が必要になる。
つまり、DWH には、OLTP 環境とはまったく異なる機能が必要ということだ。 例えば以下のような項目が挙げられている。
- レコードのの高速挿入、削除、更新に最適化されている B+tree に加えて、ビットマップインデックスが必要
- 汎用的なクエリ最適化の代わりに、スノーフレークスキーマに対する集約クエリに特別な注意を払う必要がある
- 通常のビューの代わりに、マテリアライズドビューが必要
DWH はもっと深く学ぶべきだと思うので、どこか他の機会にちゃんと勉強したい。
DB の拡張性 ここでは、広く使われている拡張機能の種類を簡単に列挙し、この拡張性を提供する際に発生するアーキテクチャ上の問題のいくつかに焦点を当てている。
- 抽象データ型
- 構造化タイプ(配列, 集合, 木,..)と XML
- 全文検索
Ch5 ストレージ管理
感想
ループット適切に調整されたトランザクション処理 DBMS は、通常、I/O バウンドではなく、メインメモリがボトルネックになる
これが本当に衝撃だった。。
メモ
Ch5,6 のではTransactional Storage Managerの中身を見ていく。
具体的には
Lock Manager... 同時実行制御Log Manager... リカバリ(回復)Buffer manager... データベースの I/O をステージングするためのバッファプールAccess Methods... ディスク上にあるデータの整理
今日、DBMS で使用されている基本的なタイプの DBMS ストレージマネージャーは以下の２種類だ。
この決定は、空間(何処に書き込む？)と時間(いつ書き込む？)の両方の観点で、DBMS のストレージ制御の性能に影響を与える。
空間制御 ディスクはランダムアクセスよりシーケンシャルアクセスのほうが圧倒的に早いので、データをブロックに配置する事が非常に重要。
方法 1 は DBMS がデータの空間的局所性を制御しやすいが、ディスクパーティション全体を DBMS 専用にする必要アリ。 また、RAID や SAN 等の論理 Volume Manager による仮想ディスクが一般になり、物理制御のメリットが薄れつつある。
一方、現在推奨されているのは方法 2 だ。 方法は OS のファイルシステムで非常に大きいファイルを作成し、そのファイル内でデータの配置を管理する事ができる(raw ディスクアクセスの近似) また、仮想ストレージシステムだったらそこら辺をよしなにやってくれる。
時間制御 いつ書き込むかというのは非常に重要な問題なので、DBMS には、ブロックをディスクに書き込むタイミングについて推論する重要なロジックが含まれる。
ただ、方法 2 を使うと、殆どの OS ファイルシステムはファイルブロックの read/write をいつ実行するかを決定するための I/O バッファリングを組み込んいるので、DBMS のロジックと競合する可能性がある。（？）
本文では時間制御に関する以下の問題に触れている。
- ACID トランザクションの正確性
- パフォーマンス
最終的なパフォーマンスの問題は以下の操作による高い CPU オーバーヘッドだ。
- ダブルバッファリング
- DBMS が正確さのために独自のバッファリングを行う必要があるので、OS による追加のバッファリングは冗長
- メモリ内のデータコピー
バッファの管理 DBMS は効率的なデータアクセスを実現するために、独自のメモリスペースに大きな共有バッファプールを実装している。 現在、ほとんどの商用 DBMS は、システムのニーズと利用可能なリソースに基づいてバッファプールのサイズを動的に調整するようになっているらしい。
最近では非常に大きなバッファプールが利用できようになったため、大容量のメインメモリを効率的に活用出来るようになったが、その一方で、大規模で非常にアクティブなバッファプールは、再起動の回復速度や効率的なチェックポインティングなどの問題を発生させる。 (詳しくは Ch6)
Ch6 トランザクション ： 同時実行制御と回復
感想
この章の話は DB の入門書にも書いていたと思う。 WAL とかラッチ辺りが理解できていない気がするのでいつか調べたい。
メモ
この章は長めなので、簡単にまとめるに留める。 後半は内容が難しめで、理解度も低い気がする。
- ACID について
- CID の夫々の意味についてまとめられている。
- Serializability について
- 2PL(二層ロック), MVCC(Multi-Version Concurrency Control), OCC(Optimistic Concurrency Control)について夫々概要がある。
- ロックとラッチについて
- ロックとラッチの比較がされている
- 正直ラッチはよくわからなかった・・・別の資料を見て補完したい
- トランザクションの Isolation Level
- 色んな isolation level が紹介されている
READ UNCOMMITEDとかのANSI SQL isolation levelは知っていたけど、CURSOR STABILITYとかSNAPSHOT ISOLATIONは知らなかった。
- ログマネージャ
- クラッシュ後の正しい動作をサポートするには、ログとデータベースの永続データからメモリ常駐データ構造を再作成できる必要がある
- WAL は抑えておいたほうが良さそう
- インデックスのロックとロギング
- インデックスが常にデータベースからトランザクション的に一貫したタプル を返す事が、インデックスの同時実行性と回復性を保つ唯一の不変条件だ
- トランザクションストレージの相互依存性
- トランザクションストレージシステムの 3 つの主要な側面である同時実行 制御、回復管理、およびアクセス方法は相互依存関係がある
WAL プロトコル WAL プロトコルは、次の 3 つの非常に単純なルールで構成されている。
- DB のページを変更するたびにログレコードが生成され、DB のページがフラッシュされる前にログレコードがログデバイスにフラッシュされなければならない
- ログレコードは順番にフラッシュしなければならない。つまり、ログレコード r に先行する全てのログレコードがフラッシュされるまで r はフラッシュできない。
- トランザクションのコミットリクエスト時に、リクエストを正常に返す前にコミットのログレコードをログデバイスにフラッシュしなければならない
1 が原子性を確保し、2,3 が耐久性を確保する。
Ch7 共有の構成要素
感想
この章で紹介されている機能は「そりゃあるよね」という機能だったきがする。 意外性はなかった。
メモ
この章では以下の共有のコンポーネントとユーティリティについて解説している。
- カタログマネージャ
- メモリアロケータ
- ディスク管理サブシステム
- レプリケーションサービス
- 管理、監視及びユーティリティ
カタログマネージャ データベースカタログは、システム内のデータに関する情報を保持しているメタデータだ。 カタログは、システム内の基本エンティティ（ユー ザー、スキーマ、テーブル、列、インデックスなど）の名前とそれらの関係を 記録し、それ自体が DB にテーブルのセットとして格納される。 メタデータをテーブルとして管理するメリットは多くある。
- メタデータを他のデータと同じ形式に保つことで、システムはよりコンパクトになる
- ユーザーは他のデータと同じ言語とツールを使用し、DB を管理するための内部システムコードを調査できる
メモリアロケータ(メモリ割り当て) 商用システムでのメモリ割り当ては context-base でメモリ割り当てを行うものが多い。 メモリコンテキストは、メモリプールと呼ばれる連続した仮想メモリのリスト(region)を維持するメモリ内データ構造だ。 各 region には、コンテキストラベルまたはコンテキストヘッダー構造へのポインターのいずれかを含む小さなヘッダーを含めることができる。
メモリコンテキストを使用するメリットの一例を書いておく。
- 低レベルでプログラマーが制御可能な、ガベージコレクションの代替手段として機能する
- パフォーマンス
ディスク管理サブシステム ディスクドライブは全て、容量と帯域幅が大きく異なる複雑で異種のハードウェアだ。 そのため、DBMS には、raw デバイス/論理ボリューム/ファイル全体でのテーブルや、その他のストレージユニットの割り当てを管理するディスク管理サブシステムがある。
この項の残りは RAID の辛みなどを話している。
レプリケーションサービス 信頼性を高めるために、定期的にネットワーク全体で DB を複製することがよく行われる。 複製された DB は、メインシステムがダウンした場合に備えて、少し古くなった「ウォームスタンバイ」として機能する。
レプリケーションは例えば以下のような種類がある。
- Physical Replication
- 物理的な複製。一番簡単。しかし、スケールしないことや、DB のトランザクション的に一貫性のあるスナップショットを保証するのは難しい等の欠点があるので基本的に推奨されない。
- Trigger-Based Replication
- トリガーがテーブルに配置され、テーブルへの挿入や削除/更新時に、差分レコードが特別なレプリケーションテーブル(RT)に保存される。この RT はリモートサイトに送られる。
- Pysical Replication の欠点を解決するが、許容できないパフォーマンスの低下をもたらす事がある。
- Log-Based Replication
管理、監視及びユーティリティ DBMS は、システムを管理するための一連のユーティリティを色々提供している。
- オプティマイザー統計収集
- オプティマイザーのための統計を収集する機能
- 物理的な再編成とインデックスの構築
- 使用される中で発生する断片的な未使用スペースを無くすために、テーブルの異なる列での並べ替えや複数ディレスクへの再パーティション化を行う
- バックアップ/エクスポート
- すべての DBMS は、データベースをバックアップストレージに物理的にダンプする機能をサポートしている
- バルクロード
- 多くのシナリオでは、大量のデータをデータベースにすばやく取り込む必要があるため、高速データインポート用に最適化されたバルクロードユーティリティが提供されている事が多い
- 監視、調整、およびリソースガバナー
- リソースなどの監視や履歴ログ照会が出来る。また、多くのシステムでは、クエリが実行時間/メモリ/ロック取得などの特定のパフォーマンス上限を超えたときにアラートを出すみたいなことも出来る
Ch8 結論
DB しゅごい、複雑だ・・・ 疲れた・・・
