データ指向アプリケーションデザイン：第3章

概要

DDIA第3章「ストレージと検索」のライブ配信による解説です。発表者が図を描きながら、データベースがディスクレベルでどのようにデータを保存・検索するかを説明します。主なテーマは2つあります：OLTPとOLAPデータベースの違い、そしてそれぞれのアクセスパターンの違いがなぜ根本的に異なるストレージレイアウトにつながるのかです。

OLTPとOLAP：2つの異なる世界

OLTP (Online Transaction Processing):

Webアプリケーションを支える — MySQL、Postgres、SQLite、Oracle
短く高速なトランザクション（サブミリ秒）
読み取りが大半（80〜90%）、書き込みは少ない（10〜20%）
キーによる少数の行の取得クエリ（例：SELECT * FROM users WHERE id = 2）
データベース：MySQL、Postgres、SQLite

OLAP (Online Analytical Processing):

ビジネスインテリジェンスと分析を支える
大量のデータをスキャン（「今年販売されたすべての商品」「6ヶ月間のユーザートレンド」）
クエリの実行時間が長くても問題ない — ユーザー向けではないため
OLTPデータベースからETL（Extract–Transform–Load）でデータを抽出し、専用のデータウェアハウスに格納

なぜ分離するのか？ OLTPデータベース上で重い分析スキャンを実行すると、キャッシュスラッシングが発生し、エンドユーザー向けのアプリケーションが遅くなるためです。

行指向ストレージ（OLTP）

OLTPデータベースでは、データはディスク上に行単位で保存されます：

[ID:1, Ben, ben@hi.com, 1234 Fifth St] [ID:2, Zed, zed@mail.com, 5678 Oak Ave] [ID:3, Ally, ...]

このレイアウトは、以下のようなクエリに最適です：

単一の行または少数の行を選択する場合
それらの行のすべてまたは大部分のカラムが必要な場合
主キーでデータにアクセスする場合

行のすべてのカラムがディスク上で物理的に隣接しているため、1回のページ読み取りでその行に必要なすべてのデータが取得できます。

B-Tree：OLTPのインデックス

B-treeはOLTPデータベースで主流のインデックス構造です：

ノードのサイズはディスクページサイズ（通常4 KB）に合わせて設計
各ノードは複数のキーバリューペアを含む — 読み取りはページサイズ単位で行われるため、ディスクI/Oに効率的
検索はルートからリーフまで走査し、レベルごとに1ページを読み取る

MySQLとPostgresの実装の違い：

MySQL (InnoDB)：B-treeのリーフノードに実際の行データを格納（クラスタードインデックス）
Postgres：行データを「ヒープファイル」（ページの大きな配列）に格納し、B-treeインデックスはヒープファイルへのポインタを含む
どちらもセカンダリB-treeインデックスをサポート

トレードオフ： B-treeは将来の挿入のためにノード内に空きスペースを残し、ランダム書き込みには親ノードの走査が必要です。汎用的なワークロードには優れていますが、大量の順次書き込みには最適ではありません。

列指向ストレージ（OLAP）

OLAPデータベースでは、データは列単位で保存されます：

Names:     [Ben, Zed, Ally, ...]
Emails:    [ben@hi.com, zed@mail.com, ally@x.com, ...]
Addresses: [1234 Fifth St, 5678 Oak Ave, ...]

分析においてこれが重要な理由：

分析クエリは通常、多くの行をスキャンしますが、必要なカラムは少数です（例：SELECT AVG(price) FROM sales WHERE date > '2025-01-01'）
行ストレージでは、すべての行のすべてのカラムを読み込むことになる — I/Oの無駄
列ストレージでは、クエリが実際に必要とするカラムのみを読み取る

カラムの順序： どの値が同じ行に属するかを再構成できるように、すべてのカラムファイルで行の順序が同じでなければなりません。

カラム圧縮

カラムは反復的なデータを含むため、高い圧縮率が得られます：

何千人ものユーザーが同じ名前を共有
メールアドレスは共通の部分文字列を持つ（@gmail.comが何百万回も出現）
日付は頻繁に繰り返される（同じ日に多くのイベント）

ビットマップエンコーディングやランレングスエンコーディングなどの手法があります。圧縮によりストレージサイズが削減され、I/Oが減少することでクエリが高速化します — OLAPデータベースはペタバイト規模の履歴データに達する可能性があるため、特に重要です。

LSM Tree：書き込みに最適化

LSM tree（Log-Structured Merge Tree）は、高い書き込みスループットが求められるワークロード向けに設計されています：

クリックイベントストリーム、ログ取り込み、メトリクス収集
継続的で高速な順次データ

B-treeとの違い：

B-treeはページをインプレースで更新し、将来の書き込みのために空きスペースを残す — 読み取り中心のワークロードに適している
LSM treeはメモリ内に書き込みをバッファリングし、ソートされたセグメントをディスクにフラッシュし、バックグラウンドでマージする — はるかに高い書き込みスループット

使用例： Cassandra、ClickHouse、RocksDB、LevelDB

トレードオフ： B-treeはより予測可能な読み取りレイテンシを提供し、LSM treeはより高い書き込みスループットを提供しますが、読み取りは複数の構造をチェックする必要がある場合があります。

最もシンプルなデータベース

この章は面白い思考実験から始まります：bashの6行でキーバリューデータベースを構築できます — 書き込み時にキーバリューペアをファイルに追記し、読み取り時にgrepで検索します。動作はしますが、実際のデータベースが何百万行ものコードで構成されている理由を示しています：このアプローチはO(n)の読み取り、トランザクションサポートなし、並行処理なし、耐久性の保証なしという問題があります。

重要なポイント

OLTPとOLAPデータベースが存在するのは、アクセスパターンが根本的に異なるため — 本番データベースで分析を実行してはいけない
行ストレージは行のすべてのカラムをまとめて格納 — 個々のレコードの取得に最適
列ストレージはカラムのすべての値をまとめて格納 — 大規模データセットのスキャンと集約に最適
B-treeはOLTPインデックスの主力であり、効率的なI/Oのためにディスクページサイズに合わせて設計
LSM treeは読み取りレイテンシと引き換えに書き込みスループットを向上させ、大量取り込みワークロードに最適
カラム圧縮（ビットマップエンコーディング、ランレングスエンコーディング）はペタバイト規模に達し得るOLAPデータベースにとって不可欠

Claudeによる翻訳

概要