Cloud Spannerの核心：LSMツリーストレージエンジンがもたらす「妥協なき超分散スケーラビリティ」の正体
こんにちは。チーフアーキテクトの私だ。
今日のコードレビュー、あるいはアーキテクチャ設計レビューで、こんな質問を受けたとしよう。
「Cloud Spannerって、リレーショナルデータベースなのに、なぜあんなに爆速でスケールするんだ？ 内部でB-Treeでも狂ったようにチューニングしているのか？」
もし、君のチームにこう答えているメンバーがいたら、即座にその設計書を差し戻してほしい。
Cloud Spannerの圧倒的な書き込み性能と無限に近いスケーラビリティを支えているのは、伝統的なインプレース更新型のB-Treeではない。その基盤にあるのは、分散ファイルシステム「Colossus」上で稼働するLSMツリー（Log-Structured Merge-Tree）ベースのストレージエンジンだ。
今回は、Spannerの足元を支えるこのLSMツリーの内部実装に深く潜り込み、実務の現場で我々エンジニアが「どう設計し、どう立ち回るべきか」をロジカルかつシャープに伝授しよう。
—
1. なぜSpannerはLSMツリーを選ぶのか？（分散アーキテクチャの必然）
RDBの代名詞であるMySQL (InnoDB) やPostgreSQLは、B-Tree（あるいはその派生）を採用している。B-Treeは単一ノード上のランダムI/Oに最適化されているが、これを数千・数万ノードの分散環境に持ち込もうとすると、致命的なボトルネックに突き当たる。「分散トランザクションにおけるロック競合とランダムI/Oの嵐」だ。
Spannerは、データをSplit（スプリット）と呼ばれる動的なシャード単位で管理し、これをColossus上に配置している。この分散ストレージモデルにおいて、LSMツリーが選ばれたのは必然の理だ。
[Client Write]
│
▼
[MemTable (In-Memory SkipList)] ──(Raft Log)──> [Distributed Consensus]
│
▼ (Flush when full)
[Immutable MemTable]
│
▼ (Background Compaction)
[LSM Tree SSTables on Colossus (Level 0 -> Level N)]
書き込みのパス：すべては「アペンド」から始まる
Spannerのストレージエンジンに書き込みリクエストが到達すると、データはディスク上の所定の場所をその場で書き換える（インプレース更新）ことはしない。
1. MemTable（メモリ上のSkipListなど）へ高速にアペンドされる。
2. 同時に、Raftグループを介して他のレプリカへログとして同期される。
このアペンド・オンリー（追記型）のアーキテクチャにより、ディスクヘッドのシークを伴うランダムI/Oが完全に排除される。ディスクへの書き込みは常にシーケンシャルとなり、これが驚異的なスループットを生み出す源泉となっている。
—
2. 内部構造の解剖：MemTableからColossus上のSSTableへ
LSMツリーの本質は、「書き込みの高速化」と「読み取り・ compaction（コンパクション）のトレードオフ」の緻密なエンジニアリングにある。
MemTable と Immutable MemTable
メモリ上に展開されたMemTableが一定サイズに達すると、それは「Immutable MemTable（読み取り専用）」に凍結され、バックグラウンドスレッドによってColossusへフラッシュされる。このフラッシュ処理によって生成されるのが、SSTable（Sorted String Table）だ。
SSTable と Immutable の美学
SSTableはその名の通り、キーでソートされた不変（Immutable）のデータファイル群である。
- 不変性（Immutability）: 一度書き出されたファイルは二度と変更されない。これにより、複雑なロック機構や悲観的排他制御なしに、安全にリーダー・フォロワー間でファイルを共有・複製できる。
- Colossusとのシナジー: Googleの分散ファイルシステム「Colossus」自体も大容量の不変ブロックを扱うため、SSTableのデータ構造と極めて相性が良い。
バックグラウンド Compaction（マージ処理）
不変ファイルを増やすだけでは、いずれファイル数が爆発し、読み取り時に無数のファイルを走査（Read Amplification）しなければならなくなる。ここで登場するのが Compaction だ。
バックグラウンドで複数のSSTableを読み込み、キーの重複や古い世代のデータを削除・マージしながら、より整理された新しい世代のSSTableへと再構築する。
—
3. 実務へのインプリケーション：この仕組みから「どう設計すべきか」を導く
チーフアーキテクトとして、君たちに最も強く伝えたいのはここだ。「エンジンの内部構造を知っていれば、自然と正しいスキーマ設計の答えが見えてくる」ということだ。
アンチパターン：ホットスポットを生む「単調増加キー」
LSMツリーの特性上、キーが完全に昇順（例：UUID v1, シーケンシャルな整数ID, タイムスタンプのプレフィックス）で書き込まれると、データは常に特定のSSTableの末尾、ひいては特定のSpannerのSplitへと集中する。
- 何が起きるか:
特定のSplit（タブレット）に書き込みが集中し、そのノードのCPUとI/Oが飽和する。これが、Spannerにおける「ホットスポット」の正体だ。LSMツリーの「高速な追記」というメリットが、単一のSplitへの集中によって完全に殺されてしまう。
正解の設計パターン：逆転ハッシュ（Bit-Reversal）とプレフィックス分散
もし時系列データを保存する場合、キーの先頭にそのままタイムスタンプを置いてはならない。
— 【悪手】単調増加キーによるスキーマ
CREATE TABLE Events (
EventTime TIMESTAMP NOT NULL,
EventId STRING(64) NOT NULL,
Data STRING(MAX),
) PRIMARY KEY(EventTime, EventId);
— 【推奨】ハッシュプレフィックスによる負荷分散
CREATE TABLE Events (
ShardId INT64 NOT NULL, — 0からNのハッシュ値
EventTime TIMESTAMP NOT NULL,
EventId STRING(64) NOT NULL,
Data STRING(MAX),
) PRIMARY KEY(ShardId, EventTime, EventId);
このように、キーの先頭に適切なシャードID（ハッシュ値など）を付与することで、書き込みが複数のSplitへと美しく分散される。LSMツリーのMemTableへの書き込みが、ストレージ全体に並列分散され、真の水平スケーラビリティが解放されるのだ。
—
4. パフォーマンス上の注意点：Read Amplification と Compaction 滞留
LSMツリーは書き込みの王様であるが、読み取り（Read）や特定のクエリパターンにおいては注意が必要だ。
1. ポイントルックアップのコスト:
キーがどのSSTableに存在するかを特定するために、Bloomフィルターやインデックスのキャッシュが効かない場合、複数のSSTableを探索（Read Amplification）することになる。Spannerはこれを高度なインメモリキャッシュとブロックインデックスで極限まで最適化しているが、それでも設計上の意識は必要だ。
2. 大量のDELETE/UPDATEによるCompaction負荷:
LSMツリーにおける「削除」は、実データをその場で消すのではなく、「墓石（Tombstone）」という削除マーカーを書き込む処理だ。大量のDELETEや頻繁な上書き（実質的な追記）が発生すると、Colossus上には不要なデータとTombstoneが溢れ、Compactionスレッドが常に高負荷状態（Write Amplificationの増大）に陥る。
- 対策: ライフサイクル管理（TTL機能の活用など）を適切に行い、不要になったデータはパーティション（Split）単位で効率的にドロップできる設計にする。
—
最後に：アーキテクトとしての心構え
Cloud Spannerを「ただの無限にスケールするSQLデータベース」として扱うな。
その下層では、Colossusという強靭な基盤の上で、LSMツリーが絶え間なくMemTableをフラッシュし、SSTableをマージし、一貫性を保ちながら静かにうごめいている。
この分散ストレージエンジンの呼吸を感じ取れる者だけが、真に美しく、高スループットで、コスト効率の優れたデータベーススキーマを設計できる。
次回の設計レビューでは、「このクエリとインデックスは、LSMツリーのCompactionとSplit分散にどう影響するか？」という視点でコードを見てほしい。君たちのアウトプットの質が一段階引き上がることを、私は確信している。
コメント