DDIA 第3章: ストレージとデータ取得

概要

この章では、データベースが内部的にどのようにデータを保存し、要求されたときにどうやってデータを見つけるかを探ります。ストレージエンジンを理解することで、ワークロードに適したデータベースを選択し、パフォーマンスをチューニングできるようになります。主要な2つのファミリーはログ構造化エンジンとページ指向エンジンです。

データベースを支えるデータ構造

最もシンプルなデータベース：追記専用ログ

最もシンプルなストレージエンジンは追記専用ファイルです。書き込みは高速（O(1)）ですが、読み取りにはファイル全体のスキャンが必要です（O(n)）。読み取りを効率化するには、インデックスが必要です。これはプライマリデータから導出された追加のデータ構造で、道しるべの役割を果たします。

重要なトレードオフ： インデックスは読み取りを高速化しますが、書き込みを遅くします。なぜなら、書き込みのたびにインデックスを更新する必要があるからです。データベースがデフォルトですべてをインデックス化しないのはこのためです。クエリパターンに基づいてインデックスを選択します。

Hash Indexes

最もシンプルなインデックス戦略：すべてのキーがデータファイル内のバイトオフセットにマッピングされたインメモリハッシュマップを保持します。これは基本的にBitcask（Riakのデフォルトストレージエンジン）が行っていることです。

キーの数が限られていて頻繁に更新がある場合にうまく機能する
すべてのキーがメモリに収まる必要がある
範囲クエリは効率的でない（kitty00000からkitty99999の間をスキャンできない）

コンパクション： ログは追記専用のため、永遠に増え続けます。コンパクションは重複するキーを破棄し、最新の値のみを保持することでログセグメントをマージします。

SSTableとLSM-Tree

Sorted String Table（SSTable）： Hash Indexedセグメントに似ていますが、キーバリューペアがキーでソートされています。

Hash Indexesに対する利点：

セグメントのマージが効率的（マージソートのように）
スパースなインメモリインデックスで十分 — すべてのキーは不要で、一部のキーだけ保持してその間をスキャンする
インデックスエントリ間のブロックを圧縮できる

LSM-Tree（Log-Structured Merge-Tree）： 完全なストレージエンジンパターン：

書き込みはインメモリの平衡木（memtable）に行く
memtableが十分大きくなったら、SSTTableとしてディスクにフラッシュする
読み取りはまずmemtableを確認し、次に最新のディスク上のセグメント、その次に古いセグメントを確認する
バックグラウンドのマージとコンパクションがセグメント数を管理可能に保つ

使用例：LevelDB、RocksDB、Cassandra、HBase、Lucene（ターム辞書用）。

Bloom filterは、存在しないキーに対する不要なディスク読み取りを避けるためによく使用されます。

B-Tree

最も広く使用されているインデックス構造です。B-treeはデータベースを固定サイズのページ（通常4 KB）に分割し、一度に1ページずつ読み書きします。これは基盤となるハードウェアに対応しています。

各ページはアドレスで識別される（ディスク上のポインタのようなもの）
ページにはキーと子ページへの参照が含まれる
分岐係数は通常数百
4 KBページで分岐係数500の4階層B-treeは最大256 TBを格納できる

LSM-treeとの主な違い： B-treeはページをその場で変更しますが、LSM-treeはファイルに追記するのみで、その場での変更は行いません。

Write-Ahead Log（WAL）： ページを変更する前に、データベースは変更を追記専用ログに書き込みます。これによりクラッシュからの復旧が可能になります。

B-Tree vs. LSM-Tree

側面	LSM-Tree	B-Tree
書き込みスループット	一般的に高い	低い（すべての書き込みがツリーを更新）
書き込み増幅	コンパクションにより高くなりうる	WALへの1回の書き込み + ページへの1回
読み取りパフォーマンス	遅い（複数の構造を確認）	速い（1つの確定的な場所）
圧縮	良い（ページフラグメンテーションなし）	ページ内に無駄な空間あり
予測可能性	コンパクションが読み取りに干渉しうる	より予測可能なレイテンシ
トランザクション	困難（キーが複数セグメントに存在しうる）	容易（キーは正確に1箇所に存在）

その他のインデックス構造

セカンダリインデックス

プライマリインデックスとは異なり、セカンダリインデックスはレコードを一意に識別しません。以下のいずれかが可能です：

一致する行IDのリストを格納する（ポスティングリストのように）
各エントリが行の場所を指す

インデックス内への値の格納

クラスタードインデックス： 実際の行データをインデックス内に格納する（例：InnoDBのプライマリキー）
非クラスタードインデックス： 行が存在する場所への参照（ヒープファイルポインタ）を格納する
カバリングインデックス： インデックス内に一部のカラムを格納し、一部のクエリをインデックスだけで回答できるようにする

複合カラムインデックス

連結インデックス： 定義された順序でカラムを結合する（電話帳のように：姓、次に名）
多次元インデックス： 複数のカラムで同時に検索する必要があるクエリ向け（例：緯度AND経度）。R-treeが一般的な選択肢です。

全文検索とファジーインデックス

Luceneはターム辞書にSSTTableに似た構造を使用しますが、与えられた編集距離内のファジーマッチングをサポートするために有限状態オートマトン（trieに類似）を追加しています。

インメモリデータベース

すべてをメモリに保持する方式（例：VoltDB、MemSQL、Redis）：

ディスク読み取りを避けるから速いのではなく（OSキャッシュがそれを処理する）、ディスク向けのデータエンコーディングのオーバーヘッドを回避するから速い
ディスクベースのインデックスでは実装が難しいデータ構造を提供できる（例：Redisのプライオリティキューやセット）
WAL、スナップショット、またはレプリケーションにより耐久性を実現できる

トランザクション処理 vs. 分析（OLTP vs. OLAP）

特性	OLTP	OLAP
読み取りパターン	少数のレコードをキーで取得	大量のレコードを集約
書き込みパターン	ユーザー入力によるランダムアクセス、低レイテンシの書き込み	一括インポート（ETL）またはイベントストリーム
主要ユーザー	Webアプリケーション経由のエンドユーザー	社内アナリスト
データセットサイズ	GBからTB	TBからPB
ボトルネック	ディスクシーク時間	ディスク帯域幅

データウェアハウス

OLTPシステムからETL（Extract–Transform–Load）を介して抽出された、読み取り最適化されたデータの別コピーです。スタースキーマ（またはスノーフレークスキーマ）を使用します：

ファクトテーブル： 各行はイベント（例：販売）を表します。非常に大きくなりえます（数十億行）。
ディメンションテーブル： イベントの誰が、何を、どこで、いつ、なぜを記述します（例：商品、顧客、店舗、日付）。

カラム指向ストレージ

典型的なデータウェアハウスのクエリでは、数百カラムのテーブルから数カラムだけアクセスします。行指向ストレージはすべてのカラムを読み込むためI/Oを無駄にします。

カラム指向ストレージは各カラムのすべての値をまとめて格納します。これにより、必要なカラムだけを読み取るため、分析クエリが大幅に高速化されます。

カラム圧縮

カラムには多くの繰り返し値があることが多く、非常に圧縮しやすいです：

ビットマップエンコーディング： カラム内の各ユニーク値に1つのビットマップ。ユニーク値の数が行数に対して少ない場合にうまく機能します。
ランレングスエンコーディング： ビットマップをさらに圧縮します。

圧縮されたカラムはベクトル化処理も可能にします。CPU SIMD命令を使用して、圧縮されたカラムデータのチャンクを直接操作します。

カラムストレージのソート順序

すべてのカラムファイルで行が同じ順序でなければなりません。ソート順序（例：日付順、次に商品順）を選択して、一般的なクエリを支援し、最初のソートキーの圧縮を改善できます。

複数のソート順序： 同じデータを異なる方法でソートして格納します（複数のセカンダリインデックスを持つようなもの）。Verticaはこのアプローチを使用しています。

カラムストレージへの書き込み

LSM-treeはここでうまく機能します：書き込みはインメモリストア（行指向）に行き、その後カラム形式でディスクにフラッシュされ、既存のカラムファイルとマージされます。

集約：マテリアライズドビューとData Cube

マテリアライズドビュー： 一般的な集約の事前計算キャッシュ（例：SUM(amount) GROUP BY product_id, date）。基盤データが変更されると更新されます。
Data Cube（OLAP Cube）： 複数の次元に沿った集約のグリッド。事前計算されたクエリには非常に高速ですが、アドホック分析には柔軟性に欠けます。

主なポイント

ストレージエンジンの2つのファミリー： ログ構造化（LSM-tree）はデータを追記してバックグラウンドでマージする。ページ指向（B-tree）は固定サイズのページをその場で更新する
LSM-treeは書き込みスループットが高い傾向がある。B-treeはより予測可能な読み取りパフォーマンスを持つ傾向がある
OLTPとOLAPは根本的に異なるアクセスパターンを持ち、異なるストレージエンジンで最もよく対応できる
カラム指向ストレージは関連するカラムのみを読み取り、積極的な圧縮を可能にすることで、分析クエリのパフォーマンスを劇的に向上させる
インデックスはトレードオフ： すべてのインデックスは読み取りを高速化するが、書き込みにオーバーヘッドを追加する — クエリパターンに基づいて選択する
インメモリデータベースはディスク読み取りを避けることではなく、ディスク指向のデータエンコーディングのオーバーヘッドを回避することで高速化を実現する

Claudeによる翻訳

概要