【実務・中級編】 Bツリーインデックス構造 – Cloud Spanner

【Cloud Spanner深層】なぜSpannerのBツリーはLSMと共存しても壊れないのか？――極限のインデックス設計論

こんにちは。テクニカルリードの私だ。
今日のコードレビュー、あるいはアーキテクチャ設計レビューで、こんな質問を受けたとしよう。

> 「Spannerは分散リレーショナルデータベースとして、実態はLSMツリー的な分散ログ構造を取りつつ、なぜBツリーインデックスでミリ秒の高速ランダム読み取りを両立できるのですか？インデックスの裏側で何が起きているんですか？」

この質問に、ドキュメントの表層をなぞったような回答をしてはならない。「Googleだから凄いです」で済ませるエンジニアは、うちのチームには不要だ。

今回は、Cloud Spannerのコアアーキテクチャの心臓部、「Bツリーインデックス構造とLSMツリー的メカニズムの共存」について、実務で使える知見を交えて徹底的に解説する。設計の前提を覆すインサイトを持ち帰ってほしい。

—

1. イントロダクション：Spannerインデックスのパラドックス

多くのエンジニアは、NoSQLや分散ストレージの文脈で「書き込みスループットを稼ぐならLSMツリー（Log-Structured Merge-tree）、ランダム読み取り性能を重視するならBツリー」という二項対立で世界を見ている。

しかし、Cloud Spannerはこの常識を鮮やかに破壊している。
グローバル規模の分散トランザクション（TrueTimeによる外部整合性）を担保しながら、内部では高度にチューニングされたBツリー構造を維持し、数TB規模のデータセットに対しても予測可能な低レイテンシ（p99 < 10ms）のポイントルックアップとレンジスキャンを実現している。なぜSpannerは、相反する特性を持つアプローチを一つのエンジン内で調和させられているのか？その答えは、ストレージ層の物理データ構造と、分散トランザクションログ（Paxos）の絶妙な役割分担にある。 ---

2. コアアーキテクチャ：BツリーとLSM的アプローチの共存メカニズム

Spannerのストレージエンジン（内部的にはColossus上に構築されたデータファイル群）を深く覗いてみよう。

データの物理表現としてのBツリー（MutationsとFiles）

Spannerの各Tablet（データシャード）は、キー順にソートされたデータを保持する。データム（Row）やインデックスのエントリは、ローカルストレージ上ではBツリー（正確にはB+ツリーの変種）の形式で構造化されている。

これにより、以下のメリットが生まれる。

キャッシュ効率の最大化: ページ単位（通常は数KB〜数十KB）でのメモリロードにより、メモリ上のキャッシュヒット率が劇的に向上する。
効率的なレンジスキャン: `WHERE created_at >= … AND created_at < ...` のようなクエリにおいて、ディスクシークを最小限に抑え、連続したメモリブロックをスキャンできる。

では、なぜ「LSM的」と言われるのか？

ここで誤解してはならないのは、Spannerが純粋なインプレース更新型の古いBツリーデータベースではないという点だ。

Spannerへの書き込み（Mutation）は、まずメモリ上のMemTable（またはそれに類する構造）に蓄積され、同時にPaxosロググループに追記される。
ディスク上への永続化の際、不変（Immutable）なデータファイル（SSTableに類似した構造）としてフラッシュされる。古いデータと新しいデータのマージ（コンパクション）は、バックグラウンドで非同期に実行される。

つまり、

書き込みパス: 追記型（Append-only / LSM的）であり、ディスク上のランダムI/Oを排除してスループットを最大化。
読み取りパス: 最終的にソートされたB+ツリー構造としてインデックス化され、高速な二分探索（O(log N)）を保証。

この「書き込みはLSM的、読み取りはBツリー的」というハイブリッドこそが、Spannerが無限のスケールと超高速なルックアップを同時に達成している物理的な理由だ。

—

3. 実務で直面する設計の罠：ホットスポットとインデックスの裏側

このアーキテクチャを理解していれば、Spannerでやってはいけない設計が自ずと見えてくる。コードレビューで以下のアンチパターンを見つけたら、即座に差し戻しを命じてほしい。

アンチパターン：単調増加するキーをインデックスの先頭に置く

— 【悪夢のDDL例】
CREATE TABLE Transactions (
TransactionId INT64,
CreatedTimestamp TIMESTAMP,
AccountID STRING(64),
Amount NUMERIC,
) PRIMARY KEY(TransactionId);

— 時系列のインデックスを作成
CREATE INDEX TransactionsByTime ON Transactions(CreatedTimestamp);

何が起きるのか？

`CreatedTimestamp` は単調増加する。SpannerのBツリーインデックスはキー順にソートされているため、新しい書き込み（INSERT）は、常に単一のTabletの特定のBツリーの右端（最末端のページ）に集中する。

1. そのTabletをホストしている特定のSplits/NodesにCPUとディスクI/Oが殺到する（ホットスポット）。
2. Paxosグループのリーダーが過負荷になり、レイテンシが急増。
3. 最悪の場合、Tabletの分裂（Splitting）が追いつかずにスループットが頭打ちになる。

正しい設計（ソリューション）

UUIDv4やハッシュプレフィックスを用いて、書き込みを分散させなければならない。あるいは、スパーシティー（まばらさ）を意識したプレフィックス設計を行う。

— 【推奨される設計例：シャード化されたインデックス】
— ShardID（例: 0〜15のハッシュ値）をプレフィックスに置くことで、
— Bツリーの異なるレンジ（＝異なるTablet）に書き込みを分散させる。
CREATE INDEX TransactionsByTime
ON Transactions(ShardID, CreatedTimestamp, TransactionId);

—

4. パフォーマンス上の注意点：インデックスのメンテナンスコスト

Bツリーインデックスは「魔法の杖」ではない。インデックスを張れば張るほど、書き込み性能（Mutationのレイテンシとスループット）のコストが増大することを忘れてはならない。

1. インデックスの数と書き込みトランザクションの肥大化

Spannerでは、ベーステーブルに1行INSERTすると、定義されているすべてのセカンダリインデックスに対しても更新用のMutationが生成される。これらはすべて同一の分散トランザクション（2PC / Paxos）内で原子的にコミットされる。
つまり、インデックスが5つあるテーブルへの書き込みは、裏側で6つのBツリー構造を同時に更新するコストを払っていることになる。

2. インデックスオンリーアクセス（Covering Index）の活用

クエリのパフォーマンスを極限まで引き上げるためには、オプティマイザがベーステーブルを参照せず、インデックスのBツリーだけでクエリを完結させられるように設計（`STORING` 句の活用）することが鉄則だ。

— カラムをインデックスに含める（ストアリングインデックス）
CREATE INDEX TransactionsByAccount
ON Transactions(AccountID, CreatedTimestamp)
STORING (Amount);

— このクエリは、ベーステーブルを一切読みに行かず、
— 「TransactionsByAccount」のBツリーだけでO(log N)のレンジスキャンで完結する。
SELECT Amount
FROM Transactions@{FORCE_INDEX=TransactionsByAccount}
WHERE AccountID = ‘acc-12345’
AND CreatedTimestamp >= ‘2023-01-01T00:00:00Z’;

この設計により、ストレージ層でのランダム読み取り（ベーステーブルのシーク）を完全に回避し、Bツリーのキャッシュヒット率を限界まで高めることができる。

—

5. チーフアーキテクトからの提言

Cloud SpannerのBツリーインデックス構造は、単なる「便利な機能」ではない。それは、Googleの分散システムエンジニアリングの歴史が生んだ、「分散トランザクションと単体マシンのデータ構造（B+ツリー）の究極の結婚」である。

君たちがコードを書くとき、あるいはインデックスを張るときは、常に頭の中で以下の問いを思い浮かべてほしい。

> 「今、私が追加したこのインデックスのキーは、Bツリーのどのあたりに書き込まれるか？特定のTabletに負荷が集中（ホットスポット化）していないか？」
> 「このクエリは、ベーステーブルのBツリーまでフェッチしに行かざるを得ない構造になっていないか？」

このレイテンシの数ミリ秒、スループットの数倍の差にこだわり抜くこと。それこそが、真のプロフェッショナルエンジニアの仕事だ。

次のレビューで、君たちの口から「ホットスポット」や「Bツリーの物理レイアウト」についての鋭い指摘が出ることを楽しみにしている。設計に戻れ。