【実務・中級編】 スプリット分割アルゴリズム – Cloud Spanner

スプリット分割アルゴリズムの深淵：Cloud Spannerがいかにして「ホットスポット」を物理的に消滅させるか

こんにちは。チーフアーキテクトの私だ。
これまでのキャリアで数多くの大規模分散データベースを見てきたが、Cloud Spannerのコアエンジニアリング、特にストレージとコンピュートの分離およびスプリットの動的分割（Dynamic Split）のメカニズムは、分布式ストレージの歴史における一つの到達点だと言っていい。

多くのエンジニアは、Spannerを「リレーショナルな保証を持つNoSQL」程度に捉えている。だが、それは氷山の一角に過ぎない。
「なぜSpannerは数百万QPSを受けてもノードが死なないのか？」
「なぜプライマリーキーの設計を少し間違えただけで、レイテンシーが跳ね上がるのか？」

その答えのすべては、今回解説するスプリット分割アルゴリズム（Split Splitting Algorithm）にある。
今回は、ドキュメントの表面的な解説を剥ぎ取り、実務の設計レビューでそのまま使える『極限の知見』を叩き込む。覚悟してついてきてほしい。

—

1. コアアーキテクチャ：スプリットとは何か？

まず、用語の定義を合わせよう。
Cloud Spannerにおいて、テーブルのデータは単一の巨大なファイルや、単一のハードディスクに保存されているわけではない。データは辞書順（Lexicographical order）にソートされた上で、「スプリット（Split）」と呼ばれる物理的なチャンクに分割される。

各スプリットは、Paxosグループによって複数のリージョン/ゾーンにまたがってレプリケーションされ、可用性と強整合性が担保されている。

[ テーブル全体 (辞書順ソート) ]
|– [ Split A: ‘A’ ~ ‘D’ ] —> Paxos Group A (Node 1, 2, 3)
|– [ Split B: ‘E’ ~ ‘M’ ] —> Paxos Group B (Node 4, 5, 6)
|– [ Split C: ‘N’ ~ ‘Z’ ] —> Paxos Group C (Node 7, 8, 9)

このスプリットこそが、Spannerの水平スケーリング（Scale-out）の最小単位である。データ量が増大すればスプリットは自動的に細分化され、それぞれのスプリットは異なるコンピュートノード（正確にはタブレットサーバ群）へと動的に再配置される。

—

2. スプリット分割アルゴリズムの裏側：サイズと負荷の二刀流

スプリットの分割は、単に「データサイズが一定を超えたら割る」という単純なものではない。Spannerのアルゴリズムは、以下の2つの強力なトリガーによって駆動されている。

① ストレージサイズベースの分割 (Size-based Splitting)

  • 閾値: 一般的に1つのスプリットが数GB（通常は2GB〜4GB程度）を超えると、システムは分割を試みる。
  • 挙動: データの容量的上限に達したため、辞書順の中央値付近でスプリットを物理的に2つに切断する。

② 負荷ベースの分割 (Load-based Splitting) —— ★ここが本丸

  • 閾値: CPU使用率、QPS（読み取り/書き込み頻度）、バイトスループットなどのメトリクスが特定の負荷閾値を超過したとき。
  • 挙動: データサイズが小さくても（極端な話、数MBであっても）、そこにアクセスが集中していればスプリットは強制的に分割される。

この「負荷ベースの分割」こそが、Spannerがホットスポットを動的に撃破できる理由だ。
しかし、ここに実務上の大きな罠が潜んでいる。

—

3. 致命的なアンチパターン：「単調増加キー」の悲劇

設計レビューで最も頻繁に目にするバグがこれだ。
「時系列データを保存するから」という理由で、以下のようなスキーマを切るエンジニアが後を絶たない。

— 【絶対にやってはいけないアンチパターン】
CREATE TABLE AccessLogs (
AccessLogId INT64 NOT NULL, — 1, 2, 3, 4… とインクリメントされるID
Timestamp TIMESTAMP,
UserId STRING(64),
Payload STRING(MAX),
) PRIMARY KEY(AccessLogId);

この設計の何が問題か？
`AccessLogId` が単調増加する場合、すべての新規書き込みは辞書順の「一番ケツ（末尾）」に集中する。

分割アルゴリズムの限界とスプリットの「追いかけっこ」

Spannerの負荷ベース分割は、ホットスポットを検知すると「よし、その熱いスプリットを半分に割ろう」とする。しかし、すべての書き込みが常に最大のキーに集中しているため、分割しても、新しく生まれた右側のスプリットに瞬時に負荷が集中する。

結果として何が起きるか？
1. スプリットが割られる
2. 右側のスプリットに書き込みが集中し、即座に負荷閾値を超える
3. またスプリットが割られる
4. 際限のないスプリットの分裂（Split Storm）が発生し、メタデータの管理コストと Paxos のリーダー選出オーバーヘッドが急増する。
5. 最終的にレイテンシーが劇的に悪化し、スループットが頭打ちになる。

これが、Spannerにおけるホットスポットのメカニズムだ。アルゴリズムは優秀だが、物理法則（単一のキーへの集中）を魔法のように消し去ることはできない。

—

4. 堅牢な設計パターン：ハッシュ分散とインターリーブ

では、どう設計すべきか？テクニカルリードとして、私はプロジェクトメンバーに以下のパターンを強く推奨している。

パターンA：UUID v4 や ハッシュプレフィックスによるシャード化

書き込みの負荷を空間全体に分散させ、意図的に複数のスプリットへヒットさせるアプローチだ。

— 【推奨される設計：ハッシュプレフィックスによる分散】
CREATE TABLE AccessLogs (
— 先頭にハッシュのプレフィックス（例: 0〜fの16分散、またはUUID）を付与
ShardId INT64 NOT NULL,
AccessLogId INT64 NOT NULL,
Timestamp TIMESTAMP,
UserId STRING(64),
Payload STRING(MAX),
) PRIMARY KEY(ShardId, AccessLogId);

  • 解説: アプリケーション側で `ShardId`（例えば `MOD(FARM_FINGERPRINT(UserId), 16)` など）を計算し、プライマリーキーの先頭に置く。これにより、データは16個以上の異なるスプリットに綺麗に分散し、スプリット分割アルゴリズムが完璧に機能する土壌が整う。

パターンB：親子関係（Interleaved Tables）による局所性の最大化

一方で、リレーショナルな整合性を保ちつつ、特定のエンティティ（例：テナントやユーザー）に紐づくデータを効率よく取得したい場合、インターリーブが有効だ。

CREATE TABLE Tenants (
TenantId STRING(36) NOT NULL,
Name STRING(100),
) PRIMARY KEY(TenantId);

CREATE TABLE TenantData (
TenantId STRING(36) NOT NULL,
DataId INT64 NOT NULL,
Payload STRING(MAX),
) PRIMARY KEY(TenantId, DataId),
INTERLEAVE IN PARENT Tenants ON DELETE CASCADE;

  • 解説: `TenantId` を共通の親とすることで、親子のデータが物理的に同じスプリット（または近接するスプリット）にコロケーションされる。ただし、特定の巨大テナント（メガテナント）が全体の9割の負荷を占めるようなケースでは、そのテナント自体がホットスポットになるため、テナント内部でのさらなるシャード化を検討する必要がある。

—

5. パフォーマンス上の注意点とモニタリングの極意

Cloud Spannerを運用する上で、スプリットの状態を監視することはSREとしての必須スキルだ。

1. Google Cloud Console / Monitoring の活用:

  • `CpuUtilization` や `Storage utilization` のメトリクスをスプリット単位（またはノード単位）で注視せよ。一部のノードだけCPUが90%張り付いている場合、それはスプリット分割が追いついていないか、前述の単調増加キーによるホットスポットが発生している動かぬ証拠だ。

2. ウォームアップ（Pre-splitting）の考慮:

  • 大規模な初期データ（テラバイト級）をバルクインポートする場合、何もしないと単一のスプリットからスタートするため、インポート速度が出ない。
  • 事前に適切なキー範囲でスプリットを分割（Pre-split）するか、キーを綺麗に分散させた状態でインポートするアーキテクチャ設計が不可欠である。

—

結びにかえて

Cloud Spannerのスプリット分割アルゴリズムは、現代の分散データベースが到達した一つの「神業」だ。人間が手動でシャードを再配置する必要性を消し去り、システムが自律的にスケールする。

しかし、「アルゴリズムが優秀だから、どんなクソみたいなプライマリーキーを切っても勝手に何とかしてくれる」と考えるのはプロ失格だ。

データベースの物理構造（スプリットと辞書順ソート）を脳内に焼き付け、アルゴリズムが最も働きやすい環境（負荷が美しく分散するスキーマ）を整えてやるここと――それこそが、我々テクニカルリードがコードレビューで示すべき、真のエンジニアリングなのだ。

スポンサーリンク

コメント

タイトルとURLをコピーしました