リレーショナルデータベース (関係データベース, RDB) がこれに当たる。 行を構成する列データをひとまとまりとして格納する。 小規模で高頻度なトランザクションか巨大だが書き込みをほとんど伴わないトランザクションに最適化されて設計されている。
列データをひとまとまりとして格納する。
厳格なリソースロックを必要としないか、楽観ロック (後述) とリトライで制御可能
in-place 更新型アーキテクチャを採用する DBMS に MySQL がある。
追記型アーキテクチャでは、一度書き込んだデータは不変である。 (immutable という)
追記型アーキテクチャでデータの削除を行う場合は、内部的なデータの削除を行う代わりに削除する行に削除フラグを立てる論理削除 (logical delete) を行う。 また、データの更新もデータの論理削除 → 新規データ (更新後のデータ) の挿入という手順で行う。
「論理削除」という言葉はしばしばシステム設計の文脈でも使われる。 この場合は、「参照制約や監査証跡などの観点から、データを削除する代わりにデータをマスキングした上で論理削除カラムにフラグを立てる」という意味で使われることが多い。
削除フラグが立ったレコードをトゥームストーン (tombstone, 英語で「墓標」の意) という。
トゥームストーンが増えると、データファイルは肥大化しデータの取得処理のパフォーマンスは劣化する。 そのため、追記型アーキテクチャを採用するDBMSはデータファイル中のトゥームストーンを回収し、その領域を再利用可能な状態にする。 この処理をコンパクション (compaction) という。
DBMSデータファイルに対するコンパクション処理は、JVMヒープに対するガベージコレクションの関係に似ている。
JVMのガベージコレクションのSTW (Stop the World) のように、DBMSのコンパクション処理もデータファイルのロックにより応答不能時間を伴う。 コンパクション処理一回当たりの応答不能時間が最小となるように、DBMSのコンパクション処理には
の2つが実装されていることが多い。
追記型アーキテクチャを採用する代表的なデータベースに PostgreSQL がある。
データベースシステムは全てのトランザクションが ACID 原則に従うことを要求する。
トランザクションに含まれるタスクが全て実行されるか、あるいは全く実行されないことを保証する性質。
トランザクション開始と終了時にあらかじめ与えられた整合性を満たすことを保証する性質。
独立性と性能はトレードオフの関係にあるため、一般的なデータベースシステムはこの性質の一部を緩和して実装される場合が多い。 (後述の MVCC 参照)
基本的には独立性を犠牲し、複数のトランザクションを並行に実行する。この時のトランザクションの独立性は後述のトランザクション分離レベルを参照。
MVCC は並行性制御の 1 つである。 MVCC では書き込み処理が行われている最中に他のトランザクションによる読み取りアクセスがあった場合、書き込みの直前の状態 (= スナップショット) を処理結果として返す。 つまり、書き込み中も読み取りができ、読み取り中でも書き込みができる。
独立性を提供する主な手段は並行性制御となる。
トランザクションの開始から完了まで他からの更新を抑止する。
任意のリソース対象に対して、複数の共有ロックか 1 つの排他ロックのどちらか一方のみを獲得することができる。
行ロックと並行処理の組み合わせが引き起こす問題についてはトランザクション分離レベル (後述) を参照。
悲観ロックを採用した場合に発生しうる、2 つ以上のトランザクションが互いのロック解除を待ち、互いの進行を妨げてしまう現象。 デッドロックを防ぐには、ロックの順番を同じにする。
上記の悲観ロックとは対照的に存在する並行性制御。
他の処理と競合してはならないトランザクションにおいて、開始時には特に排他処理など行なわず、完了する際に他からの更新がされたか否かを確認し、もし他から更新されてしまっていたら自らの更新処理を破棄し、エラーとする。
時刻印ロックは完了する際に他からの更新がされたか否かを確認する方法の 1 つである。
トランザクションがコミットできなかった場合に、事前に取っておいたデータベース情報のコピー (before image, ex. UNDO セグメント) を使って、データベースをトランザクション開始前の状態に戻すこと。
データベースに障害が発生した場合に、 after image (ex. コミットログ, REDO ログ) と同じコミットを適用してデータベースを最新状態にすること。 バックアップはバックアップ取得後にコミットされたトランザクションによる更新を反映していないが、バックアップから復元した後にロールフォワードすることで、障害発生直前までにコミットした全トランザクションが反映された状態まで復旧できる。
コミットログを最初に書き込むので、クエリを処理している間に障害が起こった場合、ロールフォワードでコミットされる。 主に in-place な更新できるデータベースで採用されている。
あるページに変更を加える際に、まずシャドウページがアロケートされる。 ページの変更が完了し永続化可能な状態になったら、変更前のページを参照している箇所全てを新しいページを参照するように変更する。 主に in-place な更新を行えないデータベースで採用されている。
トランザクション分離レベルとは、トランザクションが複数同時に行われた場合、どれほどの一貫性、正確性で実行するかを 4 段階で定義したものである。 ACID 原則のうちの I に関わる概念である。
並行トランザクションが起こしうる問題には以下のようなものがある。
同じトランザクション中でも同じデータを読み込むたびに値が変わってしまう現象
並行して動作する他のトランザクションが追加したり削除したデータが途中で見えてしまう現象
トランザクションの分離レベルと、そのレベルで起こりうる問題を以下に示す。
ファントムリード, ノンリピータブルリード, ダーティリードが発生
確定した最新データを常に読み取る (前述の MVCC は READ COMMITTED に該当する処理である)
MySQL + InnoDB のデフォルト (ただし ネクストキーロック (Next-Key Locks), ギャップロック (Gap Locks) という仕組みでファントムリードを回避する)
直列化可能 (いかなる場合でも、それらのトランザクションを時間的重なりなく逐次実行した場合と同じ結果になる)
件のデータの中から条件に合致する 件のデータを範囲探索すると のアクセスコストがかかる。
予め参照処理を高速化するデータ構造 (= インデックス, indexing) を作成することで、アクセス効率を高めることができる。
多分岐の平衡木である。 多分探索を行うことにより範囲探索を で行える。 記憶装置のブロックサイズを (bytes), キーのサイズを (bytes) とすると、理論的には 分平衡木が最も効率がよい。
B-tree の改良型である。 平衡木の葉ノードが連結リストになっており、範囲探索を で行える。 多くのデータベースシステムで採用されている。
ハッシュインデックスは配列で構成され、キーのハッシュによってエントリが格納される場所が決定する。 B-tree, B+-tree と比べ、空間計算量, 時間計算量に優れるが、完全一致にしか対応していない。
複数の異なるキーが同じハッシュになることや、複数のハッシュが異なるエントリが同じ場所に割り当てられることを衝突という。
衝突が発生した場合は、衝突を起こしたキー同士を連結リストに格納する (連鎖法, chaining) か、別のハッシュ関数でハッシュを計算しなおす (開番地法, open addressing)。
配列のサイズに対するエントリ数の割合を座席利用率 (load factor) と呼び、この数値が 1 に近づく、あるいは 1 より大きくなると性能が悪化する。 そのため、より大きい配列を用意してインデックスを再構築 (リハッシュ) する。
キーの衝突がない場合、完全一致探索を で行える。
探索キーの取りうる値の数 (カーディナリティ, cardinality) が低い場合に適している。
一部のデータベースシステムのインデックスには以下のような機能もある。
関数や式に基づいたインデックスを作成する。関数は immutable (同じ引数に対して常に同じ結果を返す) である必要がある。
実際のデータ自体をインデックスの順序で並べることで、範囲検索における I/O アクセスを最小化する。
MySQL + InnoDB では強制的に主キーから構成されるクラスタインデックスが作成される。
PostgreSQL では CLUSTER
コマンドにより実際のデータを並び替えることができる。
コネクションプール (connection pool) はデータベースコネクションのキャッシュである。 確立したコネクションをコネクションプールに保存して再利用する。 これにより、コネクションの確立に必要なリソースや時間を節約することができる。
特にコネクション単位でプロセスを作成する Oracle では有用である。
コネクションプールのライブラリには Spring Boot にデフォルトで含まれている HikariCP (Java) などがある。