Cloud Spannerの論理シャーディングを理解する

はじめに

Cloud Spannerを利用していて、理解が難しく説明が難しかった論理シャーディングの考え方の整理をしていきたいと思います。
Cloud SpannerのDB設計記事や登壇資料を見るとホットスポットと並んで紹介されることの多いテクニックで、社内でもしっかり時間をとって説明しないと勘違いを生むポイントでもありました。紹介されることは多いものの、登壇資料などでは深く説明されることがないので、参考にするだけで目的もなく論理シャーディングをしてしまうケースもあるかと思います。
今回は論理シャーディングのコンセプトやその利用用途について、自分の理解を整理する意味でもまとめます。

Cloud Spannerにおけるホットスポットのおさらい

基礎的なスプリット分散の概念についてはCloud Spannerのスプリット分散をわかった気になるの記事の方をご覧ください。

Cloud SpannerではデータをNodeとZoneを跨いでミラーリングしていて、スプリットにレプリカを格納しています。スプリットの分割については、初回は主キー順にデータを並べたものを一定間隔で区切っているイメージで、その後統計データによってリシャーディングが行われ、Spanner側で自律的かつ透過的に分割する位置が整理されていきます（特定のsplitにアクセスが集中した場合、アクセスが集中した主キー範囲が複数のsplitに跨るように変更したり、splitを専属にしたりする）。

これらのレプリカセットの間では、一貫したレプリケーションを保証するためにPaxosという分散合意アルゴリズムを用いています。リーダーがWriteを処理、リーダー以外がReadを処理しています。

Readを処理するレプリカは複数存在するので、Readについては特定のデータ範囲（主キーの範囲）にアクセスが集中してもミラーリングの恩恵を受けてアクセスを分散させることができます。一方で、Writeを処理するPaxosリーダーは1つのスプリットなので、アクセス分散ができず特定のZoneの特定のNodeに負荷が集中してしまい、ホットスポットが発生します。

こういった事情があり、Cloud Spannerの物理設計段階では新規データの挿入や更新が行われる際の想定シナリオからWrite時に適切にアクセス負荷が分散されるような主キーの設計を行う必要があります。

ホットスポット対策

テーブル設計時にはホットスポットの発生を抑制するためのテクニックがあります。また、誤解されがちなポイントで注意が必要なのですが、Cloud Spannerではテーブルとインデックスは本質的にsplitの集合であり、データ格納方式も全く同じです。なので、テーブル設計では注意できていたことが、インデックス設計になるとノーマークになっていてインデックスのキーにアンチパターンを採用してしまっているといったことが開発の現場でも散見されるため注意が必要です。DB設計のレビュワーなどは特に気をつけたいポイントでもあります。

主キーの先頭にUUIDを設定

最も素朴な方法です。主キーの先頭に単調増加するようなタイムスタンプなどを利用してしまうと、データ範囲の末尾を担当するsplitにアクセスが集中してしまうためアンチパターンとなっています。

テーブルのサロゲートキーとして、UUIDを振ってあげることで新規データの挿入されるデータ範囲が分散させることができます。これでテーブルに対する新規データの挿入に関しては解決できます。

主キーの先頭がUUIDになっているだけでは不十分

テーブルの主キーにUUIDを採用することで、単一のテーブルに対するデータの挿入に対しては懸念がなくなります。一方で、下記の点にはまだ懸念が残っています。

• テーブルに紐づくインデックスのアクセス特性についてはインデックスのキー設計に依存する
• そのIDを参照して主キーに持つようなテーブル（弱エンティティ相当のテーブルなど）のアクセス特性は、そのUUIDに関係する新規挿入の頻度の偏りに依存する
• UUID間でデータ更新の頻度に偏りがあるとホットスポットが発生する

例えば、ゲームのDBにUserテーブルがあった場合を考えます。

CREATE TABLE User (
  UserID STRING(36) DEFAULT (GENERATE_UUID()), -- UUIDの主キー
  Name STRING(256) NOT NULL, --  名前
  Level INT64 NOT NULL, -- レベル（1から単調増加）
  WeaponID STRING(36) NOT NULL, -- ひのきの枝のIDからスタート
  ...
) PRIMARY KEY (UserID);

CREATE INDEX UserByLevel ON User(Level) STORING(Name, WeaponID);
CREATE INDEX UserByWeaponID ON User(WeaponID) STORING(Name, Level);

ゲームのリリース直後

シナリオとしてゲームのリリース直後を想定して考えてみます。まず、リリース直後は新規ユーザ登録がスパイクとして発生します。Userテーブルは新規登録時はUUIDで挿入先のスプリットを分散させるので、アクセス負荷を均一に分散できるでしょう。一方で、UserByLebelインデックスはどうでしょうか？リリース直後はLevelが1のユーザが大量に追加され続けるので、キーがLevelから始まるこのINDEXは先頭のデータ範囲を担当するスプリットにアクセスが集中することになるため、ホットスポットが発生します。同様に、ひのきの枝を持っているUserも大量に発生するため、UserByWeaponIDインデックスもホットスポットを産みます。
Userテーブルへの挿入・更新時は、同一トランザクションで紐づくインデックスの更新も行っているため、新規ユーザ登録でパンクしてゲームのリリース直後にユーザから不満の声が絶えない状態になってしまうでしょう。

このように、テーブルの主キーにUUIDを採用していれば、オールOKではないことがわかります。

ゲームのリリースから一定期間経った後

シナリオとしてゲームがリリースされてから一定期間経ち、Userのレベルの分布もある程度一様になったと仮定します。この時期に、やはりログイン・アクティビティ頻度が高いのは高レベル帯のユーザです。彼らはどんどん攻略を進めるため武器を頻繁に変更しますし、UserIDを参照するテーブルがあればそのテーブルに記録されるデータも頻繁に更新されるでしょう。また、ギルドなどを組めばアクセス頻度の高いギルドと低いギルドの差は顕著に現れるはずですし、ログイン頻度の高いギルドにはどんどん新しいメンバーが追加されるため、ギルド単位のアクティビティを管理したりすると特定のギルドのIDが属するデータ範囲だけホットスポットになるようなことも想定されます。

例えば、ActivityLogといったギルドとユーザの活動を記録し、調査時のトレーサビリティを向上させるようなテーブルがあったとします。

CREATE TABLE ActivityLog (
  GuildID STRING(36) NOT NULL,
  UserID STRING(36) NOT NULL,
  LogMessage STRING(MAX) NOT NULL,
  CreatedAt INT64 NOT NULL,
  ...
) PRIMARY KEY (GuildID, UserID);

-- ギルドがどんな活動をしているかをトレースするためのインデックス
CREATE INDEX ActivityLogByGuild ON ActivityLog(GuildID, CreatedAt DESC) STORING(UserID, LogMessage);

-- ユーザがどんな活動をしているかをトレースするためのインデックス
CREATE INDEX ActivityLogByUser ON ActivityLog(UserID, CreatedAt DESC) STORING(GuildID, LogMessage);

このようなテーブルがある場合、GuildIDやUserIDに従って挿入先のSplitを決定してしまうため、利用頻度の高いギルド・ユーザによるアクセスでホットスポットが発生します。

頻度の高い主キー範囲へのアクセスを論理シャーディングで分散させる

ここまでに紹介した問題点の共通点は、テーブルとインデックスの主キーの範囲間でアクセス頻度に大きな偏りがあることです。論理シャーディングはこの問題点を解決するために利用されます。

ActivityLogを例に見ていきます。新しくShardIDを主キーに追加しています。ShardIDの導入で、GuildIDとUserIDが被っていても異なるShardIDが生成されるようにすることを考えます。

CREATE TABLE ActivityLog (
  ShardID STRING(36) NOT NULL, -- 新しく追加
  GuildID STRING(36) NOT NULL,
  UserID STRING(36) NOT NULL,
  LogMessage STRING(MAX) NOT NULL,
  CreatedAt INT64 NOT NULL,
  ...
) PRIMARY KEY (ShardID, GuildID, UserID);

-- ギルド・ユーザがどんな活動をしているかをトレースするためのインデックス
CREATE INDEX ActivityLogByGuild ON ActivityLog(ShardID, GuildID, CreatedAt DESC) STORING(UserID, LogMessage);

-- ユーザがどんな活動をしているかをトレースするためのインデックス
CREATE INDEX ActivityLogByUser ON ActivityLog(ShardID, UserID, CreatedAt DESC) STORING(GuildID, LogMessage);

ShardIDの計算はGuildID・UserID・CreatedAtを連結してハッシュ値を計算したものを論理シャード数で割った余りとして計算することにしてみます。論理シャード数を制御することで、ShardIDのハッシュ空間の大きさを制御することができます。hashにはCRC32などが例として挙げられます。

ShardID = hash(GuildID + UserID + CreatedAt) % ShardNum

こうすることで、主キーの先頭に数字が付与されて、同じGuildID・UserIDでも論理シャード数の範囲内でsplit分散を実現できるようになります。

論理シャード数の検討

ここで、論理シャード数はどのように決定するのかという問題に直面すると思います。単純に考えればシャード数が多い方がハッシュ空間が広がって、より分散されるように感じると思います。一方で、ShardIDを導入したテーブルからデータを取得するクエリを書いてみると、Read時にオーバヘッドが発生する可能性を考慮しないといけないことがわかります。

例として、指定したギルドの最新のアクティビティを指定した件数だけ取得するクエリを検討してみましょう。
GENERATE_ARRAYを使ってShardIDを全パターン生成して、そのShardIDに対応する論理シャードから欲しいカラムを引いて連結させる処理が必要になることがわかります。つまり、少なくとも@shardNum * @limitだけスキャンが発生することになるため、論理シャード数が多いほどReadパフォーマンスが低下します。

SELECT 
  g.UserID, g.LogMessage, g.CreatedAt
FROM 
  UNNEST(GENERATE_ARRAY(0, @shardNum - 1)) AS s, -- 0〜shardNumのShardIDを生成してCROSS JOIN
  UNNEST(ARRAY(
    -- 各論理シャードから欲しいデータを取得
    SELECT AS STRUCT UserID, LogMessage, CreatedAt
    FROM ActivityLog@{FORCE_INDEX=ActivityLogByGuild}
    WHERE ShardID = s
      AND GuildID = @guildID
      LIMIT @limit -- N件
      -- INDEXがCreatedAtでDESCソートされているからORDER BYはいらない
  )) AS g
-- シャード間ではCreatedAtの前後が発生するからORDER BYする
ORDER BY g.CreatedAt DESC
LIMIT @limit --N件

結果として下記の2点のトレードオフになり、いい塩梅を探す必要があります。

• むやみにシャード数を増やすと、スキャン行数が増えてReadパフォーマンスが低下する
• 極端にシャード数を減らすと、ホットスポットが発生してWriteパフォーマンスが低下する

ちょうどいい論理シャード数というのはあくまでも目安として、主キー範囲全体の平均アクセス頻度と最もアクセス頻度の高い主キー範囲の比を用いることが考えられます。
ゲーム会社であれば、既存のリリースタイトルの実績値などからある程度予測がつく何らかの指標（例えば、ギルドごとのレベルの総量とか、取れるなら実際のテーブル挿入・更新頻度など）を用いるのが良さそうです。

既存のタイトルの実績として、一定の主キー範囲ごとに区切って疑似的なスプリットとみなし、スプリット単位の1分あたりのアクセス頻度を計測した結果が下記のようになったと仮定します。（数字は適当です）

• Aグループ: 5000回
• Bグループ: 200000回
• Cグループ: 5000回
• Dグループ: 5000回
• Eグループ: 5000回

ここで最もアクセス頻度の高いグループはBグループの200000回で、全体の平均は44000回です。平均と最大値の比はだいたい4.5になります。このままだとBグループを担当するスプリットに平均よりも約5倍のアクセスが発生してホットスポットになってしまいます。

そこで、N=5として論理シャーディングを導入してみるとどうなるか考えてみます。
今までBグループのスプリットに5件挿入されていたデータが、理想的には5個の論理シャードに均一に割り振られるようになるので、論理シャード単位で全体的に均一にアクセスがならされるようになることがわかるはずです。

このように、想定するシナリオを分析し、事前にシャード数を見積もり、しっかり事前に負荷試験を行っておくことがCloud Spannerの負荷分散には求められます。

まとめ

Cloud SpannerのDB設計でホットスポットを作り込まないために考慮すべきことを箇条書きで。

• Paxosの分散合意アルゴリズムの都合で、Write時にhotspotが発生する可能性がある
• hotspotの発生を回避するためには、主キーが単調増加しないようにUUID等にする
• インデックスや外部キーを持つテーブルでは、アクセス頻度に影響を受ける可能性がある
• 論理シャーディングで特定の主キー範囲へのアクセス頻度の偏りをならすことができる
• 論理シャード数はシナリオから逆算して目安を計算する

まだまだ自分も理解が浅いところもあるため、まさかりは歓迎です。間違っていたことを書いていたら、ぜひご指摘お願いします！

参考文献

• https://cloud.google.com/blog/products/gcp/sharding-of-timestamp-ordered-data-in-cloud-spanner/?hl=en
• https://github.com/gcpug/nouhau/tree/spanner/shard/spanner/note/shard
• https://blog.g-gen.co.jp/entry/cloud-spanner-explained#シャーディング
• https://cloud.google.com/spanner/docs/schema-design#fix_hash_the_key