Cloud Spannerの主キーの設計

Toyohito Murooka

Published in

google-cloud-jp

9 min readAug 26, 2019

Cloud Spannerがパフォーマンスを発揮するには主キーの設計が非常に重要です。そこで実際に主キーを作成ついて記載します。

はじめに

こちらは下記のような方向けに記載しております。

ID生成についての理解がない
RDBのAuto IncrementでしかIDの生成をしたことがない

もしCloud Spannerについて知りたいのであれば、公式ドキュメントを見ることをおすすめします。

Cloud Spanner ドキュメント | Cloud Spanner | Google Cloud

Cloud Spanner は完全に管理されたミッションクリティカルなリレーショナルデータベースサービスであり、グローバルなスケールでのトランザクション整合性、スキーマ、SQL（拡張機能を含む ANSI…

cloud.google.com

ただドキュメントを見てもID生成器のことなどを理解していないと、いざ設計するとき苦労するかと思い記載しました。ドキュメントの補足資料として読んでいただけたら幸いです。

Cloud Spannerの特徴

特徴を簡単に記載しますと

ノード、スプリットで構成されている。レコードデータはスプリットに配置される。どこに配置するかはレコードの主キーに依存する。
レコードの増減に応じてCloud Spanner側で自動で(1)どのレコードをどのスプリットに配置するか。(2)スプリットの数をコントロールする
レコードをどのスプリットの配置するかはレコードの主キーの値に依存する
分散されたスプリットにアクセスが散らばることで高パフォーマンスを実現

シーケンシャルな主キーを避ける

Cloud Spannerでは主キーをシーケンシャルな値にすることはパフォーマンスの劣化を生みます。Cloud Spanner自身にAuto Increment機能はないですし、アプリでそのようなIDを生成・Insertすることも好まれません。ではなぜ避ける必要があるのでしょうか？

理由はホットスポットをつくらないようにする必要があるためです。
ここでいうホットスポットとは局地的な(特定のノード、スプリットへの)アクセス集中です。

特定のノードやスプリットに処理が集中するとそのノード、スプリットに対するパフォーマンスに影響を及ぼします。

スキーマ設計

主キー設計を行う上で注意しておかないといけないことがあります。

「UUID ジェネレータが上位ビットを擬似ランダムに選択することを確認してください」

これは一体何をさすのでしょうか？こちらを理解するにはます、IDの生成方法についての理解が必要です。

ID生成器

ここではRDBのAutoIncrement以外のID生成器について代表的なものを取り上げます。

UUID

UUIDは128ビットのID生成器で、現在バージョン1から5までが規格化されており、よく使われるのはタイムスタンプベースのVersion1とランダムベースのVersion4です。

※UUIDは歴史的経緯から互換性のない複数の異なる仕様に分かれております。ここでは RFC4122で規格化されたものという体で説明します。(他の規格の場合は後述のバリアントのビット数が異なります)

UUID v1

タイムスタンプとクロックシーケンス、ノード(MACアドレス)から構成
クロックシーケンスとは同一のタイムスタンプ上での重複を避けるための連番
普通はネットワークカードに（通常一意に）与えられているMACアドレスを用いられる
バリアントとはどの仕様でつくられたUUIDなのかを示すもの(1〜3ビット)。RFC4122で規格化されたものは10を使用。詳しくはこちらを参照

UUID v4

乱数によりID生成される。
Version(4ビット)、バリアント(2ビット)、のこりの122ビットで乱数を生成する
|乱数(48ビット)| Version(4ビット) |乱数(12ビット)|バリアント(2ビット) |乱数(62ビット)|
他のversionのUUIDに比べて分散性の高いIDを生成
IDが衝突する可能性がゼロではない。ただし、その可能性に関しては加味する必要はないレベル(こちらを参照)

snowflake

twitter社がOSSとして提供している64ビットのID生成ツール
タイムスタンプ、ノードID、連番で構成

ULID

128bitのID生成器。タイムスタンプと乱数にて構成
IDにMACアドレスを使用しない

他にもFirebase PushID、Instagram IDなどがありますが
どれもタイムスタンプが上位ビットに配置されます。
UUID v4以外はすべてタイムスタンプが上位ビットに配置されます。

タイムスタンプ上位のIDのほうがソート性に優れ、
逆にUUID v4は値の分散率が高いです。

したがって
Cloud SpannerのID生成に向く上位ビットにタイムスタンプを使用しないものとはUUID v4のように生成値の分散率が高いものになります。

複合主キー

ちなみに連続的な数のカラムを主キーにしたい場合は、複合主キーにして左側のカラムを分散した数のカラム(Sharding用カラム)にする手もあります。

ShardId = hash(key parts) % N

PRIMARY KEY (ShardId, シーケンシャルな値のカラム)

しかし、ここでは一つの主キーに対していかに分散した値を入れられるかに焦点を当てて話を進めます。

※Cloud Spannerではシャーディング管理を受け持ってくれるのにも関わらず、自前でシャーディング数を管理するのはなるべくなら避けたいところです。

おまけ(ビット反転によるID生成)

ちなみにドキュメントに主キーの作成方法として下位のような記載がありました。

「従来の手段で連続番号を生成し、次にビットを反転して最終値を得ることです。」

ここでいうビット反転のロジックとはXorshiftアルゴリズムになります。簡単にかつ低負荷で疑似乱数を生成できる方法です。

Goで書くとこのような感じになります。

i := getIncrementNum()
seed := i
seed = seed ^ (seed << 13)
seed = seed ^ (seed >> 7)
num = seed ^ (seed << 17)fmt.Printf("%d, %d\n", i, num)

10件分の結果はこんな感じです

自前でID生成器を作成する場合に、アルゴリズムの一部として使用できるかと思います。

クエリハッシュ関数を使用する

uuid v4でのIDは128ビットなのでSTRING(36)を使用すると思いますが、都合によりInt64の主キーを利用する場合はどのようにすればいいのでしょうか？
Insert時にクエリ関数(FARM_FINGERPRINT)を使用する方法があります。

※ただし、ビット数は128ビットから減少しますので注意が必要です。

FARM_FINGERPRINT関数とは

オープンソース FarmHash ライブラリの Fingerprint64 関数を使用したハッシュ関数。STRING または BYTES 入力。

FARM_FINGERPRINTと一意のカラムを使用

名前は一意でなくてはいけないので、FirstName + LastNameをベースにFARM_FINGERPRINTをかけて主キーを作成すれば、一意性もたもたれます。

stmt := spanner.Statement{
    SQL: `INSERT Singers (SingerId, FirstName, LastName) VALUES 
            (FARM_FINGERPRINT(CONCAT(@firstName, @lastName)), @firstName, @lastName)`,
    Params: map[string]interface{}{
        "firstName": firstName,
        "lastName":  lastName,
    },
}

FARM_FINGERPRINTの使用によるパフォーマンスについて調べてみました。

内部でCONCATしている場合は少し負荷がかかっているようですが、FARM_FINGERPRINT単体であればそれほど遜色がない結果かと思います。

そもそもサロゲートキーは必要か

ドキュメントにも記載されてますが、
主キー用のサロゲートキーを設けずに現実の属性(一意のカラム)を使用することを推奨していますので、仕様が許すようならそちらを検討すべきかと思います。

できる限り、主キーには現実の属性を使用することをおすすめします。これは特に属性が変更されない場合に当てはまります

最後に

今回のおさらいです。

ID生成器を使用す場合は生成ロジックが上位ビットがタイムスタンプでないようにする
複合主キー(ShardId)を使用した方法
クエリハッシュ関数の利用
サロゲートキーを設けない

以上になります。