【実務・中級編】データ圧縮とLSMツリー – Cloud Spanner

Cloud Spannerの内部心臓部：LSMツリーとバックグラウンドマージが織りなす「止まらない極限性能」の真実

テックリードの私だ。今日のコードレビュー、あるいはアーキテクチャ設計レビューで、こんな質問を受けたことはないだろうか？

「Cloud Spannerって、なぜ数百万QPSを捌きながら、ミリ秒未満のレイテンシを維持できるんだ？」
「RDBなのに、なぜインデックスの断片化を気にしてメンテナンス（REBUILDやOPTIMIZE）をする必要がないんだ？」

もし君のチームメンバーがCloud Spannerを「ただの分散型MySQLやPostgreSQLの化け物」だと思って設計しているなら、今すぐその手を止めさせろ。

Cloud Spannerは、外側こそ標準的なANSI SQLと強整合性（ACID）の美しさを纏っているが、その内臓（ストレージエンジンと分散アーキテクチャ）は、従来のB-TreeベースのRDBとは完全に異なる宇宙で動いている。特に、書き込みの爆発と読み取りの効率化を両立させるために採用されているLSM（Log-Structured Merge）ツリー構造と、その裏で静かに稼働するバックグラウンドマージ（Compaction）の仕組みは、Spannerの圧倒的なパフォーマンスの源泉だ。

今回は、このコアアーキテクチャの深淵に潜り込み、実務の設計において何を意識すべきかをロジカルかつシャープに伝授する。

—

1. なぜSpannerに「B-Treeの呪縛」がないのか？

伝統的なRDB（InnoDBなど）は、インデックスにB-Tree（あるいはB+Tree）を採用している。B-Treeは、その場でデータを書き換え（In-place update）するため、ランダムI/Oが発生する。データ量が増え、高頻度な更新・挿入が走ると何が起きるか？

そう、ページの断片化（Fragmentation）とバッファプールのヒット率低下だ。夜間バッチで「インデックスの再構築（REBUILD）」や「ANALYZE」を回した経験のあるエンジニアも多いはずだ。

しかし、Cloud Spanner（正確にはその分散ストレージレイヤ）は、LSMツリーの哲学をベースに設計されている。

LSMツリー × Spannerの基本思想

LSMツリーの基本は「追記型（Append-only）」だ。データをその場で上書きせず、常に新しいデータをシーケンシャルに書き込んでいく。
これにより、ランダムI/Oを極限まで排除し、ディスクの物理特性（SSDであっても）の限界を引き出す。

しかし、追記し続けるだけでは、同じキーの古いデータや削除マーク（Tombstone）が散乱し、読み取り時にすべてのファイルをスキャンしなければならなくなる。ここで登場するのが、今回の主役であるバックグラウンドでのマージ処理（Compaction / 階層的データ統合）だ。

—

2. SSTableの断片化解消と階層的データ統合のメカニズム

Cloud Spannerのストレージ層では、データはSSTable（Sorted String Table）と呼ばれるイミュータブル（変更不可）なファイル群として管理されている。

書き込み（Mutation）が発生すると、まずメモリ上のMemTableに蓄積され、一定量に達するとディスクへフラッシュされて新しいSSTable（Level 0）が生成される。このプロセスが繰り返されると、ディスク上にはキーレンジが重複した無数の小さなSSTableが乱立することになる。これが「断片化」の本質だ。

この断片化を解消し、読み取り性能を一定に保つために、Spannerのストレージエンジンはバックグラウンドで階層的なデータ統合（Leveled Compaction）を常に実行している。

[Write] —> MemTable —> Disk (Level 0: 多数の重複SSTable)
│
▼ <-- バックグラウンドマージ (Compaction) Level 1 (サイズ制御された非重複SSTable群) 外側から見ると綺麗に整列された単一のデータだが、内側では絶えずマージと古いバージョンのガベージコレクションが行われている。

マージ処理の裏側で何が行われているか？

1. キーのソートとマージ（Merge & Sort）:
バックグラウンドスレッドが複数のSSTableを読み込み、キー順にマージしながら新しいSSTableを生成する。この時、同じキーの古いバージョンや、明示的な削除（Tombstone）はポリシーに従って排除（ガベージコレクション）される。
2. Read Amplification（読み取り増幅）の抑制:
マージが行われないままだと、1回の読み取りで何十ものSSTableを探索（Seek）する必要がある。Compactionは、この探索コストを最小限（対数オーダー）に抑え込むために、ファイルを整理整頓し続ける。
3. Write Stallingの回避（CPU/IOリソースの制御）:
書き込みが異常に激しい場合、MemTableのフラッシュ速度がマージ速度を上回り、ディスクがSSTableで埋め尽くされそうになる。Spannerの内部スケジューラは、このバランスを動的に制御し、システムの可用性を落とさずにバックグラウンドI/Oをスロットリングする。

—

3. 実務へのインプリケーション：設計レビューで何を指摘すべきか？

このアーキテクチャを理解していれば、コードレビューやデータモデリングのレビューで「何を言わなければならないか」が自ずと見えてくる。

アンチパターン：ホットスポットを生むプライマリキー設計

よくある失敗例を見てみよう。

— 【最悪の設計例】時系列データをそのまま単調増加するIDやタイムスタンプで主キーにする
CREATE TABLE Events (
EventId STRING(MAX) NOT NULL, — UUIDや単調増加のシーケンス、あるいは現在時刻ベースのID
UserId INT64 NOT NULL,
Payload STRING(MAX)
) PRIMARY KEY (EventId);

なぜこれがLSMツリー構造において最悪なのか？
Cloud Spannerは、プライマリキーの辞書順でデータを分割し、Splitsという単位でストレージノードに配置する（これがシャーディングを自動で行う仕組みだ）。

もし `EventId` に単調増加する値や現在時刻を使うと、すべての新規書き込みが「現在時刻に対応する単一のSSTable / 単一のタブレット（Split）」に集中する。
結果として、バックグラウンドマージが追いつかないほどの書き込み集中（ホットスポット）が発生し、CPUやストレージI/Oが飽和、レイテンシが跳ね上がる。

正解の設計パターン：逆転・分散キー（Bit-reversal / Hash Prefix）

もし時系列データを扱う必要があるなら、キーの先頭にハッシュプレフィックスを付与するか、ビット反転（Bit-reversal）を用いて、書き込み負荷をすべてのSSTable/Splitsに均等に散らせなければならない。

— 【推奨の設計例】キーの先頭にハッシュや分散要素を入れる、またはUUIDv4を使用する
CREATE TABLE Events (
— ハッシュ化されたプレフィックスを持たせる、あるいは完全にランダムなUUIDv4を使う
ShardId INT64 NOT NULL,
EventTimestamp TIMESTAMP NOT NULL,
EventId STRING(MAX) NOT NULL,
Payload STRING(MAX)
) PRIMARY KEY (ShardId, EventTimestamp, EventId);

※注: Cloud Spannerのベストプラクティスでは、UUIDv4のようなランダムなプレフィックスや、自然な分散キーを使うことが強く推奨されている。LSMツリーの「追記性能」と「分散シャーディング」の恩恵を最大化するためだ。

—

4. パフォーマンス上の注意点：バックグラウンド処理との共生

LSMツリーベースのストレージにおいて、「書き込み」「読み取り」「バックグラウンドマージ（Compaction）」の3つは常にリソース（CPU、メモリ、ディスクI/O）を奪い合っている。

実務でシステムを運用する際、以下のポイントに留意せよ。

1. スキーマ変更（ALTER TABLEなど）時の挙動:
Spannerのスキーマ変更はオンラインで実行され、非常に洗練されているが、大量の既存SSTableに対してメタデータの更新やバックグラウンドでの再処理が発生する。巨大なテーブルに対するインデックス追加などは、トラフィックのピークタイムを避けて実施するのがプロの作法だ。
2. TTL（Time-to-Live）機能のコスト:
SpannerのTTL機能を用いると、古いデータが自動削除される。しかし、これはLSMツリーの文脈においては「Tombstone（削除マーク）のバラマキ」を意味する。TTLによる一括削除の後、バックグラウンドマージがTombstoneを綺麗に掃除し終わるまでの間、ストレージ容量が一時的に解放されなかったり、スキャン性能に影響が出たりすることがある。大量削除を行う場合は、その後のCompactionコストを考慮したキャパシティプランニングが必要だ。

—

結びにかえて

Cloud Spannerは「魔法の箱」ではない。その裏側では、物理的なハードウェアの制約を突破するために、LSMツリーの数学的・アルゴリズム的な美しさがフル活用されている。

データをその場で書き換えない（イミュータブルなSSTable）
断片化はバックグラウンドの階層的マージ（Compaction）が裏で完璧に調律する
だからこそ、我々エンジニアは「書き込みが特定キーに偏らない（ホットスポットを作らない）データモデリング」に全力を注ぐ必要がある

次にテーブル設計を行うときは、表面的なSQLの書き方だけでなく、その裏側でうねるSSTableとマージの息吹を感じ取ってほしい。

妥協のない設計を。健闘を祈る。