🤡

他のレコードと違う存在になりたいレコードへ

2023/12/05に公開

識別子

レコード

tech

TL;DR

小規模またはシングルデータベース向け
- Auto Increment は、その簡素さと効率性で、小規模またはシングルデータベース向けのシステムにぴったりです。
ID衝突を許容できないシステム向け
- ID の衝突が絶対に許容できないシステムには、Snowflake が最適な選択肢として際立っています。
長期間にわたり大量のIDを生成するシステム向け
- 大量の ID を長期間にわたり生成する必要があるシステムでは、Auto Increment, UUID v4, ULID, UUID v7 が有効です。
分散システムやマイクロサービス向け
- 分散環境とマイクロサービスアーキテクチャには、UUID v4, ULID, Snowflake, UUID v7 が最適で、これらはシステム間の ID 衝突を最小限に抑えます。
高速なレコード挿入が必要なシステム向け
- 高速なレコード挿入が求められる場合、Auto Increment, ULID, Snowflake, UUID v7 は効率的な選択です。

はじめに

データベースにおいて、データを一意に識別する手段は、システムの信頼性と効率の土台を築きます。多くのアプリケーションフレームワークは、シンプルで実績のある「Auto Increment」方式をデフォルトの識別子として採用しています。これは、連続して増加する数値を使い、データベースの各レコードにユニークな ID を割り振る方法です。この方法の単純さは、特に単一データベースサーバーや小規模アプリケーションにおいて強みとなります。

しかし、現代のアプリケーションは、シンプルなブログやウェブショップを越え、分散システム、マイクロサービスアーキテクチャ、クラウドベースのスケーラビリティを求められることが増えています。このような複雑なシステムでは、Auto Increment方式のIDには限界が顕在化します。スケールアウトや複数の書き込みノードが存在する環境では、IDの衝突を避けるために追加の工夫が必要となり、管理が複雑になりがちです。さらに、IDが予測可能なシーケンスであることは、セキュリティ上のリスクをもたらす可能性があります。

これらの課題に対処するため、UUID、ULID、Snowflake などの新しい形式の識別子が登場しました。これらはユニークさ、スケーラビリティ、生成の予測不可能性など、特定の利点を提供し、厳しい要求を持つ現代のアプリケーションのニーズに応えることを目指しています。本記事では、これらの識別子の機能と、それぞれが最適な状況について掘り下げていきます。

データ識別子

Auto Increment

id	name	email
1	Alice	alice@example.com
2	Bob	bob@example.com
3	Peter	peter@example.com
4	Tom	tom@example.com

構造
- 整数（Int）型
特徴
- 整数型を使用し、通常は 1 から始まる連番
- 新しいレコードがデータベースに挿入されるたびに、自動的に次の番号が ID に割り当てられる
- 多くのオブジェクトリレーショナルマッピング（ORM）フレームワークやウェブアプリケーションフレームワークでデフォルトで採用される

UUID v4

id	name	email
550e8400-e29b-41d4-a716-446655440000	Alice	alice@example.com
123e4567-e89b-12d3-a456-426614174000	Bob	bob@example.com
0c74f13f-fa83-4c48-9b33-689fed9a34b7	Peter	peter@example.com
5f9c7df8-3d59-4846-99fe-c4518e82c86f	Tom	tom@example.com

構造

128bit 長、16 進数表記
- ランダム値（122 bit）
- バージョンとバリアント（6 bit）

  0                   1                   2                   3
  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |                            rand_a                             |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |            rand_a             |  ver  |       rand_b          |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |var|                        rand_c                             |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |                            rand_c                             |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

特徴
- 128bit 長で、8-4-4-4-12 の形式に分かれた 16 進表記を用いて表される
- 全世界でユニークな値である可能性が非常に高い

ULID

id	name	email
01ARZ3NDEKTSV4RRFFQ69G5FAV	Alice	alice@example.com
01ARYZ6S41TSV4RRFFQ69G5FAV	Bob	bob@example.com
01AS3YPYXJTSV4RRFFQ69G5FAV	Peter	peter@example.com
01B2M2Y8JPTSV4RRFFQ69G5FAV	Tom	tom@example.com

構造
- 128bit 長、16 進数表記
  - タイムスタンプ（48 bit）
  - ランダム値（80 bit）
特徴
- Base32 エンコーディングを使用し、26 文字のアルファベットと数字で構成される
- 時系列情報を含み、生成された順にソートが可能

Snowflake

id	name	email
1382971839180339201	Alice	alice@example.com
1382971839180339202	Bob	bob@example.com
1382971839180339203	Peter	peter@example.com
1382971839180339204	Tom	tom@example.com

構造

64bit 整数
- 符号 bit（1 bit）
- タイムスタンプ（41 bit）
- ワーカーID（10 bit）
  - データセンターID（5 bit）
  - マシン ID（5 bit）
- シーケンス番号（12 bit）

 0                   1                   2                   3
 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|0|                        timestamp(ms)                        |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|   timestamp(ms)   |    worker id      |    sequence number    |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

特徴
- Twitter によって開発された方式（参考）
- タイムスタンプ、データセンターまたはワーカーノードの ID、シーケンス番号の情報が含まれている
- 時系列情報が組み込まれているため、生成された順番に沿ってソート可能

UUID v7

id	name	email
01715b4c-b8e7-7d59-b6e7-6967c6c7c080	Alice	alice@example.com
01715b4c-b8e8-7dfa-a470-8969b8b8b890	Bob	bob@example.com
01715b4c-b8e9-7e1b-b6f8-9968d6d8d8a0	Peter	peter@example.com
01715b4c-b8ea-7e5c-b7e9-a678c7c8c8b0	Tom	tom@example.com

構造

128bit 長、16 進数表記
- タイムスタンプ（48 bit）
- バージョンとバリアント（6 bit）
- ランダム値（74 bit）

  0                   1                   2                   3
  0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |                           unix_ts_ms                          |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |          unix_ts_ms           |  ver  |       rand_a          |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |var|                        rand_b                             |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
 |                            rand_b                             |
 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

特徴
- UUID の新しいバージョンで、時系列順序に基づいた ID 生成が可能
- ソート可能な時系列情報を含んでおり、UUID v4 よりも高度な時系列管理が可能

データ識別子の比較

特徴	Auto Increment	UUID v4	ULID	Snowflake	UUID v7
IDのサイズ	4-8 byte	16 byte	16 byte	8 byte	16 byte
IDの衝突耐性	高	非常に高	非常に高	最高	非常に高
ID生成の限界	データベース依存	理論上は無限	時刻ベースの限界あり	時刻ベースの限界あり	時刻ベースの限界あり
分散サポート	低	高	高	高	高
レコード挿入パフォーマンス	高	低	中	中	中
IDの推測容易性（セキュリティ上の問題発生確率）	高	低	中	中	中
実装の複雑さ	低	低	低	中〜高	低

IDのサイズ

Auto Increment
この方式では、使用される整数型によって ID のサイズが変わります。例えば、INT 型では 4byte、BIGINT 型では 8byte を使用します。選択されたデータ型によって ID の最大値が決まり、それによってサイズが 4byte か 8byte かが決定されます。
Snowflake
この ID 生成方式は 8byte のサイズを持ち、一意性とタイムスタンプ情報を組み込んでいます。
UUID v4、ULID、UUID v7
これらはすべて 128 ビット長を使用し、16byte の ID を生成します。

IDの衝突耐性

Auto Increment
事実上ゼロです。Auto Incrementでは、各新規レコードは前のIDから1増加するため、同一データベース内ではIDの衝突は発生しません。ただし、分散システムや複数のデータベースを同期させる場合は、異なるデータベース間で衝突が起こる可能性があります。
UUID v4
非常に高いです。UUID v4は128ビットのランダムまたは擬似ランダムIDを生成します。理論上の衝突確率は非常に低いですが、完全な衝突の排除は不可能です。IDの衝突確率P=0.5の試行回数は約230京回です。
ULID
非常に高いです。ULIDは、最初の48ビットにミリ秒単位のタイムスタンプを使用し、残りの80ビットにランダムな値を割り当てます。この構造により、ULIDはソート可能であり、UUID v4よりもわずかに低い衝突確率を持ちます。具体的には、IDの衝突確率がP=0.5になる試行回数は約1兆回とされています。
Snowflake
最高です。Snowflake は Twitter によって開発された 64 ビット ID 生成システムで、衝突を防ぐためにタイムスタンプ、ワーカーID、およびシーケンス番号を組み合わせた独自のアプローチを採用しています。衝突は発生しません。
UUID v7
UUID v7は、60ビットのミリ秒単位のタイムスタンプ、48ビットのランダム値、および4ビットのバージョン情報を含む新しい形式のUUIDです。この構造により、UUID v4, ULIDよりもわずかに低い衝突確率を持ちます。具体的には、IDの衝突確率がP=0.5になる試行回数は約1374億回とされています。

ID生成の限界

Auto Increment
データベースの数値型の最大値に依存します。
UUID v4
理論上は無限に近いです。128 ビット空間は非常に広大で、実用上は枯渇することはほぼあり得ません。
ULID
約 8,919 年。48 ビットのタイムスタンプ部分による時刻ベースの限界が存在します。
Snowflake
約 69.7 年。41 ビットのタイムスタンプ部分による時刻ベースの限界が存在します。
UUID v7
約 36,533,878 年。60 ビットのタイムスタンプ部分による非常に長い期間の限界が存在します。

分散サポート

Auto Increment
低い。Auto Increment ID は通常、単一のデータベース依存であり、分散システムでは ID の同期や衝突の問題が生じやすいです。
UUID v4
高い。ランダムまたは擬似ランダム生成により、分散環境での ID 衝突のリスクが非常に低く、分散システムでの使用に適しています。
ULID
高い。タイムスタンプとランダム要素の組み合わせにより、分散システムにおいて高いレベルのユニークネスと衝突耐性を提供します。
Snowflake
高い。ワーカーID とシーケンス番号の組み合わせにより、分散システム内でユニークな ID を効率的に生成できる設計になっています。
UUID v7
高い。時刻ベースのタイムスタンプとランダム要素の組み合わせが、分散環境での ID の衝突を最小限に抑え、高いユニークネスを保証します。

レコード挿入パフォーマンス

Auto Increment
高速なID生成が可能で、連続する数値を生成するため、データベースのインデックス構造に適しています。これにより、レコード挿入パフォーマンスは高くなります。

実際に、レコードが1000万行存在する状態で、レコード挿入にかかる時間を計測してみましょう。前提として、以下のようなテーブルを定義します。

mysql> desc AutoIncrementTable;
+-------+--------------+------+-----+---------+----------------+
| Field | Type         | Null | Key | Default | Extra          |
+-------+--------------+------+-----+---------+----------------+
| id    | int          | NO   | PRI | NULL    | auto_increment |
| name  | varchar(191) | NO   |     | NULL    |                |
| email | varchar(191) | NO   | UNI | NULL    |                |
+-------+--------------+------+-----+---------+----------------+

また、既存データは以下であるとします。

mysql> SELECT * FROM AutoIncrementTable LIMIT 2;
+----+--------+--------------------+
| id | name   | email              |
+----+--------+--------------------+
|  1 | Name 1 | email1@example.com |
|  2 | Name 2 | email2@example.com |
+----+--------+--------------------+

この前提の元、レコードを挿入してみると、≒11.55ms かかることが確認できました。

mysql> SHOW PROFILES;
+----------+------------+-----------------------------------------------------------------------------------+
| Query_ID | Duration   | Query                                                                             |
+----------+------------+-----------------------------------------------------------------------------------+
|        1 | 0.01155425 | INSERT INTO AutoIncrementTable (name, email) VALUES ('', 'example1@email.com')    |
+----------+------------+-----------------------------------------------------------------------------------+

UUID v4
ランダムまたは擬似ランダム生成されるため、生成されたUUIDがデータベースのリーフページに挿入される際、そのページをバッファープールで探さなければなりません。リーフページがバッファープールでヒットしない場合、ストレージに対するI/Oが発生し、パフォーマンスが劣化します。これにより、レコード挿入パフォーマンスは低下することがあります。

先程と同様に、レコードが1000万行存在する状態で、レコード挿入にかかる時間を計測してみましょう。前提として、以下のようなテーブルを定義します。

mysql> desc UUIDTable;
+-------+--------------+------+-----+---------+-------+
| Field | Type         | Null | Key | Default | Extra |
+-------+--------------+------+-----+---------+-------+
| id    | varchar(191) | NO   | PRI | NULL    |       |
| name  | varchar(191) | NO   |     | NULL    |       |
| email | varchar(191) | NO   | UNI | NULL    |       |
+-------+--------------+------+-----+---------+-------+

また、既存データは以下であるとします。

mysql> SELECT * FROM UUIDTable LIMIT 2;
+--------------------------------------+--------------+--------------------------+
| id                                   | name         | email                    |
+--------------------------------------+--------------+--------------------------+
| 000009ec-8815-4a34-91a6-a0a4d668ff03 | Name 4549518 | email4549518@example.com |
| 00000c82-f6c7-42ab-a1fe-69e9757d5e7e | Name 2625675 | email2625675@example.com |
+--------------------------------------+--------------+--------------------------+

この前提の元、レコードを挿入してみると、≒28.61ms かかることが確認できました。

mysql> SHOW PROFILES;
+----------+------------+-----------------------------------------------------------------------------------+
| Query_ID | Duration   | Query                                                                             |
+----------+------------+-----------------------------------------------------------------------------------+
|        1 | 0.02861525 | INSERT INTO UUIDTable (id, name, email) VALUES (UUID(), '', 'example1@email.com') |
+----------+------------+-----------------------------------------------------------------------------------+

以上のことから、こちらにあるように、UUID v4の挿入パフォーマンスがAuto Incrementに比べて悪いことが分かります。

ULID
タイムスタンプとランダム要素の組み合わせにより、一定の順序性を保持しながらもユニークな ID を生成します。しかし、完全な順序性がないため、データベースのインデックスにおけるレコード挿入パフォーマンスは Auto Increment ほど高くなく、中程度です。
Snowflake
タイムスタンプ、ワーカーID、シーケンス番号を組み合わせて生成されるため、一定の順序性がありますが、完全な連続性は保持されません。これにより、データベースのインデックスへのレコード挿入パフォーマンスは中程度です。
UUID v7
タイムスタンプとランダム要素の組み合わせにより生成され、一定の時系列的順序を持ちますが、完全な連続性はないため、Auto Increment と比較して中程度のレコード挿入パフォーマンスを提供します。

IDの推測容易性（セキュリティ上の問題発生確率）

Auto Increment
この方式は推測容易性が高いです。IDが順番に増加するため、1つのIDを知っていれば、次や前のIDを簡単に推測できます。これはセキュリティ上の問題を引き起こす可能性があります。
UUID v4
UUID v4 は推測容易性が低いです。これらの ID はランダムに生成され、特定のパターンや順序がないため、特定の ID を基に他の ID を推測することは非常に困難です。
ULID
ULID は推測容易性が中程度です。これらの ID にはタイムスタンプが含まれているため、生成された時間帯をある程度推測できますが、ID 全体を正確に予測することは難しいです。
Snowflake
Snowflake 方式も推測容易性が中程度です。タイムスタンプ情報を含むものの、ID の他の部分はランダムまたは独自のロジックに基づいて生成されるため、完全な ID を推測するのは困難です。
UUID v7
UUID v7 も推測容易性が中程度です。これらの ID にはタイムスタンプが含まれていますが、ランダム要素やその他の構成要素が組み合わさっているため、完全な ID を推測することは難しいです。

実装の複雑さ

Auto Increment
データベースが自動的に ID を生成するため、開発者はこれを直接実装することはありません。
UUID v4
既存のライブラリや機能を利用することが一般的です。そのため、実装の複雑さは低いと言えます。
ULID
UUID v4と同様に、多くのプログラミング言語で利用可能なライブラリによって容易に生成できます。タイムスタンプを含むものの、実装の複雑さは低いと言えます。
Snowflake
この方式は特定のシステム要件に応じてカスタマイズする必要があるため、実装の複雑さが高いです。ワーカーIDやシーケンス番号の管理が必要になるため、そのロジックを自身で実装する必要があります。
UUID v7
最近サポートされてきた新しい形式ですが、多くのプログラミング言語で利用可能なライブラリが提供されており、実装の複雑さはUUID v4やULIDと同様に低いと考えられます。

ユースケース

ユースケースに基づいて最適な ID 生成方式を選択するためのガイドラインを以下にまとめます。これにより、プロジェクトの特定のニーズに合わせて最適な選択ができるようになります。

1. 小規模なシングルデータベースアプリケーション

推奨されるID生成方式
Auto Increment
理由
単純で理解しやすく、実装が簡単。データベースが自動的に連番IDを管理。

2. 衝突を絶対に許容できないシステム

推奨されるID生成方式
Snowflake
理由
Snowflake ID生成方式は、タイムスタンプ、ワーカーID、シーケンス番号を組み合わせて、衝突が事実上発生しないように設計されています。万が一同じミリ秒内に複数のIDが生成された場合でも、シーケンス番号が異なるため、IDの重複は起こりません。万が一シーケンス番号が枯渇しても、1ms待つため、IDの重複は起こりません。このような設計により、IDの衝突を絶対に許容できないシステムにとって、Snowflakeは最適な選択肢となります。

3. 長期間にわたり大量のIDを生成するシステム

推奨されるID生成方式
Auto Increment, UUID v4, ULID, UUID v7
理由
これらの方式は理論上無限または非常に長期間にわたりユニークなIDを生成可能。特にUUID v7は非常に長い期間使用可能。

4. 分散システムやマイクロサービスアーキテクチャ

推奨されるID生成方式
UUID v4, ULID, Snowflake, UUID v7
理由
これらの方式は分散環境でのID衝突のリスクが非常に低く、分散システムでの利用に適している。ランダム性やタイムスタンプを組み合わせたID生成により、システム間での一意性が保証される。

5. 高速レコード挿入が要求されるデータベース

推奨されるID生成方式
Auto Increment, ULID, Snowflake, UUID v7
理由
Auto Incrementはデータベースのインデックス構造に適しており、高速な挿入が可能。Snowflakeも一定の順序性を提供するが、Auto Incrementに比べるとパフォーマンスがやや劣る可能性がある。

おわりに

この記事では、異なる ID 生成方式の特徴とそれらが最適なシナリオについて深掘りしました。Auto Increment から UUID、ULID、Snowflake、さらには最新の UUID v7 まで、各方式はその利点と制約を持ち、異なる要件に応じて選択されます。

特に、現代のアプリケーションではスケーラビリティ、パフォーマンス、そして柔軟性が求められます。例えば、単一データベースシステムにはAuto Incrementがシンプルで効果的ですが、分散システムや高い可用性を必要とする環境では、UILD, UUID, Snowflakeのような方式が適しています。（個人的には、UUID v7が最強に見えていますが、果たして、、、）

適切なID生成方式を選ぶことで、アプリケーションの効率性、安全性、そして将来の拡張性が大きく向上するでしょう。この記事により、読者の皆様がそれぞれのプロジェクトに最適な選択を行い、成功を収められることを願っています。