前置き

こちらの記事はカケハシ Advent Calendar 2021の12日目の記事になります。

新規事業の開発を担当している木村です。
本来であれば新規事業で利用している技術を紹介したいのですが、まだリリースに至っていないので汎用的なテーマになっております。
カケハシでは何人かの有志が集まって定期的な社内勉強会が開かれております。私が参加している「データ基盤のトレンド勉強会」では社内横断でデータエンジニアリングにまつわる課題を解決するための様々な視点からの洞察を得るために、最新の技術をキャッチアップしています。
私の個人は、トレンドを無策に追うよりも背景となる概念を理解した方が効果的にトレンドの情報を取捨選択できると考えており、勉強会の皮切りに「IDの設計観点」というテーマでお話しました。今回はそのテーマをブログ記事と致します。

IDの設計観点

私がIDを設計する時には以下の3つの観点に分解しています。

ドメインの観点
ID体系の特性の観点
ストレージ特性の観点

特にストレージ特性に目を向けた設計はデータ基盤に関連する内容です。では、1つずつ簡単に説明していきます。

ドメインの観点

キーの設計といっても色んな観点があります。データモデルの違いによっても異なります。 IDは"ドメイン領域"における集合の同一性(identifier)を表す概念であり、ソフトウェアの中でその概念をどう捉えるかが設計観点になります。この考え方自体は、データモデル(リレーショナルデータモデルやキーバリュー等)の違いがあっても根本的には同じだと考えます。

FYI

ID体系の特性の観点

パフォーマンスの観点になると、IDの特性が重要になってきます。 IDの特性については以下の記事がよくまとまっていますので、本稿では割愛します。

ID生成方法についてあれこれ

DB採番 (ソート可能な数値)
ULID (ソート可能な文字列)
UUID (ソート不能な文字列)
Twitter snowflakeライクなID生成機 (ソート可能)

概ね上記の4つかそれに類似する生成方法がよく採用されてるかと思います。パフォーマンスの観点を表にしました。なお、重複頻度や推測困難性、実装簡易性についてはパフォーマンス観点ではありませんが、設計の補助的観点として列に追加しています。

ID体系	型	ソート可能性	生成速度	重複頻度	推測困難性	実装簡易性
連番(DB採番)	数値	◯	×	△	×	△
UUID	文字列	×	◯	△	◯	◯
ULID	文字列	◯	◯	△	△	◯
連番(Twitter snowflake方式)	数値	◯	◯	◯	×	×

補足

Twitter snowflake方式
- パフォーマンス観点はいいですが、ID生成器自体の実装難易度は少々高いです。
連番(DB採番)
- 複数のストレージにエンティティを保存する際にID生成が1つのDBに依存すると並列処理の妨げになる
- 1つのDBに負荷が集まりやすい (SPoF)

ストレージ特性の観点

MySQL(InnoDB)のIDを考える

B+Treeのクエリのパフォーマンス要求を気にするのであれば、ソート可能なID体系が望ましいです。データ構造的にソート可能なIDであれば探索コストが少なくなり、低レイテンシー低負荷の状態を作ることができます。データ構造の具体的な説明は以下の記事で詳しく紹介されています。

全てに当てはまりませんが、過度な非機能要求がなければULIDが無難かと思います。

BigtableのKeyを考える

※ Bigtableの文脈だとKeyと呼ぶのが適切です。記事の前後関係の理解のために「ID」と読み替えてもらっても構いません。

分散KVSのアーキテクチャは細部は違えど類似点も多いです。
ファイルシステムレベルのKeyによる分散方法で言えば、GCS等でも同等のことが言えます。
ちなみに、S3はKeyによる分散を気にしなくて良くなりました。内部アーキテクチャがどうなっているかは分かりませんが。(【速報】全てのS3ユーザ必見！S3の性能が大幅パワーアップ！面倒なアレが不要に！)

Bigtableのアーキテクチャ

以下の画像は公式ドキュメントの「Bigtableの概要#Bigtableのアーキテクチャ」から拝借しています。

Colossus: ファイルシステム
SSTable: KeyとValueの不変マップ(バイト文字の保存形態)
Shared Log: ログ(耐久性観点)
Node(通称、タブレットサーバー): Keyがどこのファイルシステムに保存されているか等のメタデータが管理されていて、リクエストをルーティングする
Keyは辞書順に並び替えられてファイルシステムに保存される

Bigtableの場合はソート可能なKeyで保存すると保存領域が集中し、1つのNodeがホットスポットアクセスに繋がります。(カーディナリティの低いKeyでも類似した結果を招きます。) Nodeが水平スケールすることで分散させる仕組みなので、うまく分散しなくなりたとえNodeが追加してもスループットは上がらなくなる場合があります。 Bigtableをうまく使うには、Keyを均等に分散する必要があります。つまり、ソート可能性のあるIDをそのままKeyにするのは悪手です。

ストレージの特性を理解し、連続性のないKeyを作成するのがベストプラクティスとなります。 (この関係で連続性のある集合を取得するのは不向きなストレージとも言えます。)

全てに当てはまりませんが、過度な非機能要求がなければUUIDからKeyを作成が無難かと思います。

[TIPS] 既にソート可能性のあるID体系を使い回す必要がある場合の代替案

hash関数を使い「{hash値}_{元値}」を生成し、Keyとする方法があります。 ※ 元値を結合しているのはトレーサビリティのためです。

[TIPS] クエリユースケースからkeyを作る

パフォーマンスに意識を向けてクエリユースケースから逆算したKey設計が求められます。

具体

薬局の特定のユーザーの行動ログを取得する場合を考えてみましょう。

Key: 薬局ID:ユーザーID:timestampの場合
- 薬局のカーディナリティが低い場合は1つの薬局のアクセスが集中する可能性があります。
Key: ユーザーID:薬局ID:timestampの場合
- ユーザーIDが均一に分散されているキーであれば、1つの薬局のアクセスが集中しなくなります。
- 例えば、薬局のユーザーリストを取得したい場合は不向きです。