データベースシステム

データベースの種類

KVS (Key-Value Store)

キーに対して値という単純なデータ構造をもつ。

行指向データベース

リレーショナルデータベース (関係データベース, RDB) がこれに当たる。 行を構成する列データをひとまとまりとして格納する。 小規模で高頻度なトランザクションか巨大だが書き込みをほとんど伴わないトランザクションに最適化されて設計されている。

• 少数の行に対する多くの列の処理が効率的である。

列指向データベース (カラム指向データベース)

列データをひとまとまりとして格納する。

• 大量の行に対する少数の列の処理が効率的である。
• 全行に対する少数の列の一括更新が効率的である。

ドキュメント指向データベース

スキーマレスで柔軟なデータ構造をもつ。

トランザクションの種類

OLTP (OnLine Transaction Processing, オンライントランザクション処理)

処理内容

ビジネスや商用 (業務, 決済処理, 取引処理) のトランザクション処理

処理単位

行単位 でデータを処理する

並行性制御

厳格なロックを必要とする

適正

処理単位が行 → 行指向データベース (ex. RDB)

OLAP (OnLine Analytical Processing)

処理内容

集計や解析のトランザクション処理

処理単位

列単位 でデータを処理する

並行性制御

厳格なリソースロックを必要としないか、楽観ロック (後述) とリトライで制御可能

適正

処理単位が列 → 列指向データベース

データベースのアーキテクチャ

in-place 更新型アーキテクチャ

in-place 更新型アーキテクチャを採用する DBMS に MySQL がある。

追記型アーキテクチャ

追記型アーキテクチャでは、一度書き込んだデータは不変である。 (immutable という)

追記型アーキテクチャでデータの削除を行う場合は、内部的なデータの削除を行う代わりに削除する行に削除フラグを立てる論理削除 (logical delete) を行う。 また、データの更新もデータの論理削除 → 新規データ (更新後のデータ) の挿入という手順で行う。

削除フラグが立ったレコードをトゥームストーン (tombstone, 英語で「墓標」の意) という。

トゥームストーンが増えると、データファイルは肥大化しデータの取得処理のパフォーマンスは劣化する。 そのため、追記型アーキテクチャを採用するDBMSはデータファイル中のトゥームストーンを回収し、その領域を再利用可能な状態にする。 この処理をコンパクション (compaction) という。

追記型アーキテクチャを採用する代表的なデータベースに PostgreSQL がある。

ACID 原則

データベースシステムは全てのトランザクションが ACID 原則に従うことを要求する。

原子性 (Atomicity)

トランザクションに含まれるタスクが全て実行されるか、あるいは全く実行されないことを保証する性質。

一貫性 (Consistency)

トランザクション開始と終了時にあらかじめ与えられた整合性を満たすことを保証する性質。

独立性 (Isolation)

トランザクション中に行われる操作の過程が他の操作から隠蔽される性質。

永続性 (Durability)

独立性と性能はトレードオフの関係にあるため、一般的なデータベースシステムはこの性質の一部を緩和して実装される場合が多い。 (後述の MVCC 参照)

可用性の向上

基本的には独立性を犠牲し、複数のトランザクションを並行に実行する。この時のトランザクションの独立性は後述のトランザクション分離レベルを参照。

MVCC (MultiVersion Concurrency Control, 多版型同時実行制御)

MVCC は並行性制御の 1 つである。 MVCC では書き込み処理が行われている最中に他のトランザクションによる読み取りアクセスがあった場合、書き込みの直前の状態 (= スナップショット) を処理結果として返す。 つまり、書き込み中も読み取りができ、読み取り中でも書き込みができる。

独立性の保証

独立性を提供する主な手段は並行性制御となる。

悲観的ロック

トランザクションの開始から完了まで他からの更新を抑止する。

ロックのモードによる分類

• 共有ロック (リードロック, 読み込みロック)
• 排他ロック (ライトロック, 書き込みロック)

任意のリソース対象に対して、複数の共有ロックか 1 つの排他ロックのどちらか一方のみを獲得することができる。

ロックの粒度による分類

• 行ロック
• テーブルロック

行ロックと並行処理の組み合わせが引き起こす問題についてはトランザクション分離レベル (後述) を参照。

デッドロック

悲観ロックを採用した場合に発生しうる、2 つ以上のトランザクションが互いのロック解除を待ち、互いの進行を妨げてしまう現象。 デッドロックを防ぐには、ロックの順番を同じにする。

楽観的ロック

上記の悲観ロックとは対照的に存在する並行性制御。

他の処理と競合してはならないトランザクションにおいて、開始時には特に排他処理など行なわず、完了する際に他からの更新がされたか否かを確認し、もし他から更新されてしまっていたら自らの更新処理を破棄し、エラーとする。

時刻印ロックは完了する際に他からの更新がされたか否かを確認する方法の 1 つである。

原子性と永続性の保証

ロールバック

トランザクションがコミットできなかった場合に、事前に取っておいたデータベース情報のコピー (before image, ex. UNDO セグメント) を使って、データベースをトランザクション開始前の状態に戻すこと。

ロールフォワード

データベースに障害が発生した場合に、 after image (ex. コミットログ, REDO ログ) と同じコミットを適用してデータベースを最新状態にすること。 バックアップはバックアップ取得後にコミットされたトランザクションによる更新を反映していないが、バックアップから復元した後にロールフォワードすることで、障害発生直前までにコミットした全トランザクションが反映された状態まで復旧できる。

WAL (= Write Ahead Log, ログ先行書き込み)

コミットログを最初に書き込むので、クエリを処理している間に障害が起こった場合、ロールフォワードでコミットされる。 主に in-place な更新できるデータベースで採用されている。

シャドウページング

あるページに変更を加える際に、まずシャドウページがアロケートされる。 ページの変更が完了し永続化可能な状態になったら、変更前のページを参照している箇所全てを新しいページを参照するように変更する。 主に in-place な更新を行えないデータベースで採用されている。

トランザクション分離レベル

トランザクション分離レベルとは、トランザクションが複数同時に行われた場合、どれほどの一貫性、正確性で実行するかを 4 段階で定義したものである。 ACID 原則のうちの I に関わる概念である。

並行トランザクションが起こしうる問題には以下のようなものがある。

ダーティリード (dirty read)

不完全なデータや、計算途中のデータを読み取ってしまう動作

ノンリピータブルリード (non-repeatable read)

同じトランザクション中でも同じデータを読み込むたびに値が変わってしまう現象

ファントムリード (phantom read)

並行して動作する他のトランザクションが追加したり削除したデータが途中で見えてしまう現象

トランザクションの分離レベルと、そのレベルで起こりうる問題を以下に示す。

READ UNCOMMITTED

確定していないデータまで読み取る分離レベル

ファントムリード, ノンリピータブルリード, ダーティリードが発生

READ COMMITTED

確定した最新データを常に読み取る (前述の MVCC は READ COMMITTED に該当する処理である)

ファントムリード, ノンリピータブルリード が発生

PostgreSQL, Oracle のデフォルト

REPEATABLE READ

読み取り対象データを常に読み取る

ファントムリード が発生

MySQL + InnoDB のデフォルト (ただし ネクストキーロック (Next-Key Locks), ギャップロック (Gap Locks) という仕組みでファントムリードを回避する)

SERIALIZABLE

直列化可能 (いかなる場合でも、それらのトランザクションを時間的重なりなく逐次実行した場合と同じ結果になる)

インデックス

$N$ 件のデータの中から条件に合致する $M$ 件のデータを範囲探索すると $O(NM)$ のアクセスコストがかかる。

予め参照処理を高速化するデータ構造 (= インデックス, indexing) を作成することで、アクセス効率を高めることができる。

B-tree

多分岐の平衡木である。 多分探索を行うことにより範囲探索を $O(M\log{N})$ で行える。 記憶装置のブロックサイズを $B$ (bytes), キーのサイズを $k$ (bytes) とすると、理論的には $B/k$ 分平衡木が最も効率がよい。

B+-tree

B-tree の改良型である。 平衡木の葉ノードが連結リストになっており、範囲探索を $O(\log{N}+M)$ で行える。 多くのデータベースシステムで採用されている。

ハッシュインデックス

ハッシュインデックスは配列で構成され、キーのハッシュによってエントリが格納される場所が決定する。 B-tree, B+-tree と比べ、空間計算量, 時間計算量に優れるが、完全一致にしか対応していない。

複数の異なるキーが同じハッシュになることや、複数のハッシュが異なるエントリが同じ場所に割り当てられることを衝突という。

衝突が発生した場合は、衝突を起こしたキー同士を連結リストに格納する (連鎖法, chaining) か、別のハッシュ関数でハッシュを計算しなおす (開番地法, open addressing)。

配列のサイズに対するエントリ数の割合を座席利用率 (load factor) と呼び、この数値が 1 に近づく、あるいは 1 より大きくなると性能が悪化する。 そのため、より大きい配列を用意してインデックスを再構築 (リハッシュ) する。

キーの衝突がない場合、完全一致探索を $O(1)$ で行える。

ビットマップインデックス

探索キーの取りうる値の数 (カーディナリティ, cardinality) が低い場合に適している。

一部のデータベースシステムのインデックスには以下のような機能もある。

式インデックス

関数や式に基づいたインデックスを作成する。関数は immutable (同じ引数に対して常に同じ結果を返す) である必要がある。

クラスタインデックス

実際のデータ自体をインデックスの順序で並べることで、範囲検索における I/O アクセスを最小化する。

MySQL + InnoDB では強制的に主キーから構成されるクラスタインデックスが作成される。

PostgreSQL では CLUSTER コマンドにより実際のデータを並び替えることができる。

アプリケーション側の実装

コネクションプール

コネクションプール (connection pool) はデータベースコネクションのキャッシュである。 確立したコネクションをコネクションプールに保存して再利用する。 これにより、コネクションの確立に必要なリソースや時間を節約することができる。

特にコネクション単位でプロセスを作成する Oracle では有用である。

コネクションプールのライブラリには Spring Boot にデフォルトで含まれている HikariCP (Java) などがある。

参考文献

• Oracle Corporation, MySQL 8.0 Reference Manual, 2020
• PostgreSQL グローバル開発グループ, PostgreSQL 12.4 文書, 2020
• Wikipedia, NoSQL
• Wikipedia, 列指向データベース管理システム
• Wikipedia, オンライントランザクション処理
• Wikipedia, OLAP
• Wikipedia, ACID
• Wikipedia, MultiVersion Currency Control
• Wikipedia, 並行性制御
• Wikipedia, 悲観的並行性制御
• Wikipedia, 楽観的並行性制御
• Wikipedia, ログ先行書き込み
• Wikipedia, シャドウページング
• Wikipedia, トランザクション分離レベル
• Wikipedia, 索引 (データベース)
• Wikipedia, B 木
• Wikipedia, ハッシュテーブル
• Wikipedia, Connection pool
• saiya_moebius, RDBMS in Action, 2019