- ◇ アノキミモノガタリその弐
- はじめに
- 整数型ID、Snowflake ID、MongoDBのObjectID、ULID、UUIDなどの特徴と比較
- 整数型ID、Snowflake ID、MongoDBのObjectID、ULID、UUIDの選択フローチャート
- Snowflake IDの仕組み
- MongoDBのObjectIDの仕組み
- ULIDの仕組み
- UUIDの仕組み
- ULIDとUUIDとの互換性問題
- ULIDやUUIDの切り出し問題
- まとめ
- IDシリーズ記事の一覧
◇ アノキミモノガタリその弐
アノ日のULID、キミとまた出会えるまで十億億回の輪廻のタイムスリップ、A.D.10889年まで。
タイムマシンのプロトタイプ開発は成功した途端、投資家たちへの報告会で、
すぐに不明な理由でクリスタ星人の怪獣ボスがコントロールしているボード会で、
CEOの座が取られ、会社から追い出された。
愚かな行動。
まだプロトタイプ段階のタイムマシンは実には、
実験成功した瞬間で、タイムループができてしまった。
テストで利用されてたその時刻、令和4年4月1日零時23分55秒の999ミリ秒にしか戻れない。
50年1回の輪廻。
勇気を持って、研究室のビルから退去される直前に、
自分を実験体に、タイムマシンを再度起動した。
ごめんな、この前、実験体として50年前に送った柴犬のコマちゃん、
まだ17歳のボクに、出会えたのだろう。
いまから、あなたたちの未来を剥奪した贖罪としてコマちゃんに、ボクに、あいにいく。
ぼくは永遠にタイムループの中にトラップされた。
はじめに
こんにちは、転生したら相変わらずエンジニアだった OLTA（オルタ）プロダクトグループ研究開発チームのタイトルの前置きがとにかく長い B.です。
INVOYカードの開発を担当しています。
今回、UUID＊1のRFCがRFC4122からRFC9562に刷新されたことをきっかけに、約2年間眠っていたテックブログの記事を加筆して発表しようと思います。
2024年5月に正式的に発表されたRFC9562では、time-basedでソート可能なUUID v7が新しく提案されました。UUID v7ではULID＊2の利点もたっぷり吸収されたようで、いまさら振り返ってみるとULIDの素晴らしさに対して再認識できた部分もあるので、ULIDとUUIDv7との比較の部分も追加で書きました。また、もしULIDや既存のID仕様などでは、システムのニーズに合わない場合、どのように最適な自己流のID仕様を設計するのかについても詳しく解説しました。
＊1 UUID: Universally Unique Identifier, 汎用的一意識別子。
＊2 ULID: Universally Unique Lexicographically Sortable Identifier, 汎用的一意の辞書式にソート可能な識別子。
背景編ではなぜULIDを採用したかついて話しました。基礎編では、全面的に整数型ID、Snowflake ID、MongoDBのObjectID、ULIDまたUUIDなどの特徴、比較と選択について詳しく述べます。
整数型ID、Snowflake ID、MongoDBのObjectID、ULID、UUIDなどの特徴と比較
|
ID種類 |
整数型自動採番 Int |
整数型自動採番 BigInt |
Snowflake ID |
ObjectID MongoDB |
ULID |
UUID v1 |
UUID v4 |
UUID v7 |
|---|---|---|---|---|---|---|---|---|
|
例示 |
1234567890 |
1234567890123456789 |
1465347002426867720 |
667ed503b129f621cb75bab2 |
01FZG96YPZK4SANAG1ZM5T2K9Z |
3f64d8c8-3562-11ef-9454-0242ac120002 |
8028151e-bdcb-4881-b45f-8da65c180795 |
01905f71-cef9-7563-9323-6f397c2cc171 |
|
サイズ(Bits) |
32-bit |
64-bit |
64-bit |
96-bit |
128-bit |
128-bit |
128-bit |
128-bit |
|
サイズ(Bytes) |
4-byte |
8-byte |
8-byte |
12-byte |
16-byte |
16-byte |
16-byte |
16-byte |
|
桁数(Chars) |
最大10桁 |
最大19桁 |
最大19桁 |
24桁 |
26桁 |
32桁 |
32桁 |
32桁 |
|
デフォルトの序列エンコード方式 |
Decimal Base10 |
Decimal Base10 |
Decimal Base10 |
Hex Base16 |
Crockford’s Base32 |
Hex Base16 |
Hex Base16 |
Hex Base16 |
|
情報量密度 (Bits/桁) |
log2(10) ≈ 3.32 |
log2(10) ≈ 3.32 |
log2(10) ≈ 3.32 |
log2(16) = 4 |
log2(32) = 5 |
log2(16) = 4 |
log2(16) = 4 |
log2(16) = 4 |
|
ソード可否 |
✅ |
✅ |
✅ |
✅ |
✅ |
❌ |
❌ |
✅ |
|
時間の表示精度 |
N/A |
N/A |
ミリ秒 |
秒 |
ミリ秒 |
100ナノ秒 |
N/A |
ミリ秒 |
|
時間部分のサイズ(Bits) |
N/A |
N/A |
41-bit |
32-bit |
48-bit |
60-bit |
N/A |
48-bit |
|
時間部分の開始時刻 (Epoch) |
N/A |
N/A |
Twitter Epoch Time 協定世界時 (UTC) 2010年11月04日1時42分0秒
|
N/A |
||||
|
時間部分の利用可能期限 (UTC/A.D.) |
N/A |
N/A |
2080年07月10日 17:30:30.208 |
2106年02月07日 06:28:15 |
10899年08月02日 05:31:50.655 |
5623年06月18日 21:21:00.685 |
N/A |
10899年08月02日05:31:50.655 |
|
ランダム部分のサイズ(Bits) |
N/A |
N/A |
12-bit (厳密にランダムでなく0から始まる+1の数列) |
24-bit
|
80-bit |
14-bit |
122-bit |
74-bit |
|
ランダム部分の限定前提条件 |
N/A |
N/A |
同じworkerにおいて各ミリ秒で |
同じ機器ID・プロセスIDにおいて各秒で |
各ミリ秒で |
N/A |
各ミリ秒で |
|
|
ランダム部分の利用可能空間範囲 |
2^31-1 ≒2.15e+9 ≒21.5億 =2,147,483,647 |
2^63-1 ≒9.22e+18 ≒922京 =9,223,372,036,854,775,807 |
2^12 ≒4.096e+3 ≒4千 =4,096 |
2^24 ≒1.68e+7 ≒1677.7万 =16,777,215 |
2^80 ≒1.21e+24 ≒1.21𥝱 =1,208,925,819,614,629,174,706,176 |
2^14 ≒1.64e+4 ≒1.64万 =16,384 |
2^122 ≒5.32e+36 ≒5.32澗 =5,316,911,983,139,663,491,615,228,241,121,378,304 |
2^74 ≒1.89e+22 ≒189垓 =18,889,465,931,478,580,854,784 |
|
ランダム部分の衝突確率 (p=0.5の試行回数の期待値) |
N/A |
N/A |
衝突しないようなメカニズムを有する |
2^(24/2) ≒4.096e+3 ≒4千 =4,096 |
2^(80/2) ≒1.1e+12 ≒1兆 =1,099,511,627,776 |
2^(14/2) =1.28e+2 ≒1百 =128 |
2^(122/2) ≒2.31e+18 ≒231京 =2,305,843,009,213,693,952 |
2^(74/2) ≒1.37e+11 ≒1,374億 =137,438,953,472 |
|
単独Server・Workerにおける衝突耐性 (ランダム部分で自動+1メカニズムなし) |
N/A |
N/A |
N/A |
N/A |
非常に高 |
低 |
最高 |
高 |
|
単独Server・Workerにおける衝突耐性 (ランダム部分で自動+1メカニズムあり) |
衝突しない |
衝突しない |
衝突しないようなメカニズムを有する |
衝突しないようなメカニズムを有する |
衝突しないようなメカニズムを有する |
衝突しないようなメカニズムを有する |
N/A |
衝突しないようなメカニズムを有する |
|
分散システムにおける衝突耐性 |
非常に低 |
非常に低 |
衝突しないようなメカニズムを有する |
高 |
高 |
高 |
高 |
高 |
|
B+tree インデックスのレコードの検索と挿入性能 O(log n) |
非常に高 |
非常に高 |
非常に高 |
高 |
高 |
中 |
低 |
高 |
|
プライバシー・セキュリティ関連 |
連番なので規模と変化率が暴露 連番で推測しやすいので内部資源の保存構造も特定しやすい・ターゲットしやすい |
連番なので規模と変化率が暴露 連番で推測しやすいので内部資源の保存構造も特定しやすい・ターゲットしやすい |
ある程度推測しやすい タイムスタンプが暴露 ID/URLなどが全公開の場合秒精度で変化率が暴露 |
v0.2以前の場合機器IDやプロセスIDなどが暴露 タイムスタンプが暴露 ID/URLなどが全公開の場合秒精度で変化率が暴露 |
タイムスタンプが暴露 ID/URLなどが全公開の場合ミリ秒精度で変化率が暴露 |
MACアドレスが暴露 タイムスタンプが暴露 ID/URLなどが全公開の場合100ナノ秒精度で変化率が暴露 |
N/A |
タイムスタンプが暴露 ID/URLなどが全公開の場合ミリ秒精度で変化率が暴露 |
|
適用シーン |
小中規模 シングルDB 個人プロジェクト 逆に連番が欲しいシステム 高速の挿入が必要なシステム 絶対にソート順番を生成順番の一致性を確保したいシステム または上記プライバシー・セキュリティ関連の問題に気にしないシステム |
中規模 シングルDB 個人プロジェクト 逆に連番が欲しいシステム 高速の挿入が必要なシステム 絶対にソート順番を生成順番の一致性を確保したいシステム または上記プライバシー・セキュリティ関連の問題に気にしないシステム |
中大規模 分散システム 2039年まで利用可能なシステム または上記プライバシー・セキュリティ関連の問題に気にしないシステム |
小中規模 分散システム 秒間4000個以下のIDが生成されるシステム または上記プライバシー・セキュリティ関連の問題に気にしないシステム |
中大規模 分散システム 高速大量にIDを生成するシステム ID/URLはユーザーごとに公開 1千年後も生きてるシステム または上記プライバシー・セキュリティ関連の問題に気にしないシステム
|
小中規模 分散システム 100ナノ秒間100個以下のIDが生成されるシステム または上記プライバシー・セキュリティ関連の問題に気にしないシステム |
中大規模 個人プロジェクト 分散システム 高速大量にIDを生成するシステム 1万年後も生きてるシステム
|
中大規模 1千年後も生きてるシステム または上記プライバシー・セキュリティ関連の問題に気にしないシステム |
↑上の比較テーブルが見づらい場合、下の画像版をクリックしてください。↓
整数型ID、Snowflake ID、MongoDBのObjectID、ULID、UUIDの選択フローチャート
衝突検知と自動回避メカニズム
ここで1つ注意が必要な箇所は、違う選択のルートにて辿り着いた同じ種類のIDは、一意性を確保するために必要なアプローチと対応も違うということを意味しています。例えば「ULIDまたはUUID v7」と言った選択肢には、2つの経路が存在します。
-
経路A： MongoDB?
-no->Sortable?-yes>Uniqueness?-yes>Distributed?-no->Unpredicatable?-yes->「ULIDまたはUUID v7」 -
経路B： MongoDB?
-no->Sortable?-yes>Uniqueness?-no>Timestamp?-yes->Unpredicatable?-yes->「ULIDまたはUUID v7」-
非分散システム（シングルServer/Pod）である限り、生成されたIDの一意性が確保されています。シングルDBなのか、マルチDBなのか、特に気にする必要がありません。
-
分散システム（マルチServer/Podで、シングルDB）の場合、生成されたIDの一意性が確保されません。
-
なぜなら、threadingもmutexも作用範囲は同じサーバーにあるプロセスのthreadやgoroutineだからです。
-
このケースでも生成されたIDの一意性を確保したい場合、大抵データベースの主キー(PK)の一意性制約(UNIQUE KEY)を利用して、DBに保存する時点で返したエラーを利用して、衝突の検知と自動回避メカニズムを実現させます。
-
-
分散システム（マルチServer/Podで、マルチDB）の場合、生成されたIDの一意性が確保されません。
-
なぜなら、まず同じくthreadingもmutexも作用範囲は同じサーバーにあるプロセスのthreadやgoroutineだからです。また、主キー(PK)の一意性制約(UNIQUE KEY)はシングルDBにしか効きません。
-
このケースでも生成されたIDの一意性を確保したい場合、ID発行の専用集中システムを用意する必要があります。
-
またマルチServer/Podの場合、NTP(Network Time Protocol)を利用して、各サーバーの時刻をSyncさせる必要があります。この場合、Syncの結果、時間の進行が速かったサーバーの時刻は急に逆行したような現象が発生します。時刻の逆行が発生すると、単に排他的制御では一意性を確保できません。この時は、生成した最後のIDのlast_timestampを記録しておいて、記録したタイムスタンプより前のタイムスタンプが急に現れてきた際に、待機するようなメカニズムも必要になります。
-
-
Snowflake IDの仕組み
Snowflake IDは、Twitter社(現X)が2010年6月1日に発表した分散システムに適応できる64-bitの一意識別子です。現在、Snowflakeがその後に発表された多くの一意でソート可能な分散システムにおけるIDの設計に多大な影響を与えています。
Snowflake IDは64-bitの長さを持ち、次のように構成されています。
-
1-bitの符号ビット：
-
41-bitのタイムスタンプ：
-
10-bitのワーカーID：合わせて1024通の組み合わせがあります。
-
5-bitのデータセンターID：
-
分散システムにおけるデータセンターやリージョンを識別します。
-
5-bitを使用することで、最大32個のデータセンターを識別できます。
-
-
5-bitのマシンID：
-
各データセンター内のマシンやノードを識別します。
-
5-bitを使用することで、最大32台のマシンを識別できます。
-
-
-
12-bitのシーケンス番号：
-
同じミリ秒内で生成されるIDを区別するためのシーケンス番号です。
-
12-bitを使用することで、1ミリ秒内に最大4096個のIDを生成できます。
-
初期値は0に設定されています。
-
同じミリ秒内で複数のIDを生成する場合、シーケンス番号を自動+1ビットで単調増加するインクリメントの仕組みを持っています。
-
シーケンス番号が最大値の4095に達した場合は、次のミリ秒が来るまで待機します。
-
-
時間順にソート可能：
-
タイムスタンプが先頭に配置されているため、生成されたIDはミリ秒の精度で時間順にソート可能です。
-
-
スケーラビリティ：
-
データセンターIDとマシンIDを組み合わせることで、大規模な分散システムに対応できます。
-
ただし、各機器のシステム時間を1ミリ秒もずれないよう合わせるためにNTP(Network Time Protocol)周りの設定と調整、また時間にて生成されたIDが衝突しないように協調するためには大変です。SnowflakeIDは以上のことを確保できています。
-
-
BigInt (長整数型、long int型) との互換性：
-
符号付きの64-bit方式を採用したために、長整数型とは完全な互換性があります。
-
UUIDやULIDのように、特殊なmodel fieldを定義しなくても普通にBigIntとして利用できます。
-
-
絶対的な一意性：
-
コンパクトで検索や挿入性能が良い：
-
整数型自動採番と同じような単調増加性を有するために、サイズもコンパクトで64-bitだけのため、B+tree構造を採用したDBには、とても高い検索や挿入性能を持っています。
-
-
ある程度の予測可能性と潜在的なプライバシー問題：
Snowflake IDは、分散システムにおける一意識別子として非常に有用であり、多くのシステム設計に影響を与えています。その64-bitの構造は、コンパクトで、一意性、時間順のソート可能性、スケーラビリティなどを提供し、Twitter社をはじめとするDiscordやInstagramなどの有名なスタートアップ企業やプロジェクトで採用されています。一方、残念ながらSnowflakeプロジェクトは2014年5月末にOSSとしての開発が中止されました。また、各Worker間のシステム時間の一致性を確保するなどのため、Snowflakeを実運用するためのインフラ整備は非常に大変で、中小企業にとって気軽に導入できるものではありません。
ちなみに、Snowflakeにインスパイアされ、SONY社が開発したSonyflakeもあります。SonyflakeとSnowflakeとの最も大きいな違いは、16-bit のマシンIDを使用することで、Snowflakeの1,024の代わりに、最大65,536台のマシンを識別できます。そこで、より大規模な分散システムに利用可能です。また、タイムスタンプの精度をミリ秒から10ミリ秒単位に下げるとこで、Snowflakeの69年の代わりに、より長期間の約174年間にわたるID生成が可能になります。
MongoDBのObjectIDの仕組み
MongoDB の ObjectID を例で説明すると、以下のようなイメージです。
-
最初の4-byteの秒単位の精度を持つUNIXタイムスタンプ
-
真ん中の5-byteは機器IDとプロセスIDに基づく文字列
-
最後の3-byteは単調増加のランダム文字列
ObjectIDは 、MongoDBの各 entity 項目に _id フィールドのデフォルトPK(Primary Key)値として利用されています。少なくとも協定世界時(UTC)2106年2月7日6時28分15秒まで問題なく使用できます。
注意点として、現在ネット上に掲載されている MongoDB の ObjectID の構成図ははほとんどが上記のバージョン0.1のものであり、このバージョンでは真ん中の5バイトが機器IDとプロセスIDを直接使用していました。しかし、下の図で示したように、最新のバージョン0.2以降では、真ん中の5-byteは機器IDとプロセスIDよって生成されたランダム値に変更されました。これにより、セキュリティと一意性がさらに向上しています。
-
最初の4-byteの秒単位の精度を持つUNIXタイムスタンプ
-
真ん中の5-byteは機器IDとプロセスIDによって生成されるランダム文字列
-
最後の3-byteは単調増加のランダム文字列
ULIDの仕組み
-
48-bitのUNIXタイムスタンプ部分：
-
80-bitの単調増加できるランダム値部分：
-
一意性を確保するための単調増加できるランダムなビット列です。
-
SnowflakeやMongoDBのObjectIDなどでは、WorkerIDやMachineIDなどを利用して、分散システムでの一意性を確保できました。一方、ULIDでは、WorkerIDなどの代わりに、できるだけ多くのランダム値のビットを持たせることで、生成されたIDの一意性を非常に高い確率で保証しています。既存のタイムスタンプでソート可能な各種IDの中では、最も高い衝突耐性を有しています。p=0.5時の試行回数の期待値は1兆回となります。
-
ランダム値の衝突耐性だけで一意性を最大限に保証しているため、単独のID発行サーバーなどのような煩雑なシステム設計や構成は不要で、シンプルさを持ちます。
-
ULIDは、Base32方式でエンコードされ、case insensitiveです。Base32エンコード方式では、視認性を高めるために、特定の英文字（I, L, O, U）が含まれていません。I, L, Oの文字は1や0と混同しやすいため、除外されています。Uの除外は、英語において卑猥な言葉の文字列が生成されるのを回避するためです。このように、ULIDはシンプルかつ効率的であり、時間順にソート可能な一意識別子として広く利用されつつあります。
ULIDにおける広い空間
ULIDは、広い識別子空間を持っています。UNIXタイムスタンプ部分の精度はミリ秒まで、10桁、48-bitで、最大値は7ZZZZZZZZZです。これにより、少なくとも協定世界時（UTC）10889年8月2日5時31分50秒655ミリ秒まで問題なく使用できます。
Pythonのdatetimeライブラリの年の最大値を超えてしまうため、JavaScriptのDateで試してみます。
さらに、後ろのランダム値の部分は、16桁、80-bitで、最大値は ZZZZZZZZZZZZZZZZ です。約各ミリ秒で1.21𥝱(じょ/億京)の組み合わせが存在します。
これは、GAFAやMAMAAのようなビッグ・テック企業の超巨大規模の分散システムを除き、既存のほとんどのSaaSプロダクトの需要をはるかに超えています。
ランダム値部分の作成は特にシード値(Seed)の提供は不要で内製され、random.random()のような安全でない方式では作成されていません。例えば python版のulidライブラリでは、暗号学的に安全な os.urandom() ＊5を利用しています。もちろん、自らがもっと安全だと考える乱数生成方法を渡すことも可能です。
＊5 os.urandom(): 要注意なのは乱数発生源と乱数生成のクオリティは各機器のハードウェアと各オペレーティングシステムの実装によります。
ULIDにおける単調性問題
ULIDの仕様書には、同じミリ秒で1個以上のULIDが作成された場合、ランダム値部分が+1ビットの単調増加させるメカニズムがあると記載されています。しかし、これはあくまで理想論であり、以下のような実際の運用環境では単調性が保証されない場合があります。
-
分散システムにおける時刻の誤差：
-
違う機器の時刻の誤差によって、タイムスタンプの単調性が破綻します。
-
複数のサーバーにまたがる分散システムでは、NTP(Network Time Protocol)を利用しても、距離が遠いほど時刻の誤差が生じます。また、機器の個体差によっても誤差が発生します。
-
-
異なるプロセス間でのULID発行：
-
これはULIDの具体的な実現にもよりますが、同一サーバー内でも異なるプロセスでULIDを発行する場合、単調性が保証されない可能性もあります。そこで違うprocessやthreadでの排他的制御を実装する必要があります。
-
-
ランダム値部分の最大値オーバーフロー問題：
-
単一障害点（SPOF）の問題：
-
ULID発行専用サーバーを用意することで絶対的な単調性を保つことができますが、この場合、単一障害点(SPOF, single point of failure)が発生する恐れがあります。専用サーバーがダウンすると、ULIDの発行ができなくなります。また、ULIDの利用時のシンプルも失います。
-
以上の理由から、分散システムでマルチサーバーやマルチデータベースを利用し、同じミリ秒で数千、数万、数億のULIDを作成する必要があるサービスにおいて、ULIDの絶対的な単調増加性を求める場合には向いていないと考えられます。単調増加性が重要な要件である場合、Snowflakeのような他の識別子生成方法を検討する必要があります。
ULIDの安全性問題
ULIDの衝突確率については、鳩の巣原理と誕生日攻撃理論に関わります。これらの理論を簡単に説明すると、閏年や双子問題を除き、1年は365日であり、366人を集めれば必ず少なくとも2人の誕生日が同じ日であることが断言できます。一方、50%の確率で誕生日が同じ人が出るには、特に183人すらいらなくて、ただの23人だけで50%に達します。
ここでハッシュ関数の衝突問題に置き換えると、2つのn-bitの値が衝突するまで必要な試行回数の期待値は 2n/2 で求められます。ULIDの衝突確率も同様で、同じミリ秒において、衝突まで必要な試行回数の期待値を求めると、なんと、とんでもない天文学的数字の約1.1兆回になります！
ULIDの同じミリ秒内の単調性における推測可能問題
前述の通り、ULIDは同じミリ秒で1個以上生成された場合、ランダム値部分が+1ビットのように単調増加するメカニズムがあります。これは何を意味するかというと、同じミリ秒内で複数のULIDが生成された場合、初期値または任意の1つのULIDが分かれば、続きのULIDの序列が推測できることを意味しています。
そこで、同じミリ秒以内もID系列の推測がされたくないシステムの場合、ULIDの実現の同じミリ秒内の+1ビット自動増加のメカニズムを無くすか、+1ビットでなく+nビットのランダム値の間隔にするか、またUUID v4など他のID生成案を検討する必要があります。
ULIDの実現におけるオーバーフロー問題
おそらく気付いたかもしれませんが、Base32でエンコードした26桁の文字列では、理論上で130-bitの情報を持つことは可能です。一方、ULIDのサイズでは仕様上で128-bitしかありません。48-bitのタイムスタンプの部分で最大値は7ZZZZZZZZZです。80-bitのランダム値の部分で最大値は ZZZZZZZZZZZZZZZZ です。ULIDで利用可能な最も大きいな値は 7ZZZZZZZZZZZZZZZZZZZZZZZZZ です。そこで、これ以上大きい値はオーバーフローになります。例えば8000000000ZZZZZZZZZZZZZZZZ とか 80000000000000000000000000 とかのような文字列に対して、ULIDでParseしようとしたらオーバーフローになるために、ULIDを実現する際に7ZZZZZZZZZZZZZZZZZZZZZZZZZ 以上大きい値は適宜overflow errorを返すよう注意が必要です。
UUIDの仕組み
UUID (Universally Unique Identifier)は、RFC4122で提案され、128-bitの一意識別子で、様々な用途で広く利用されています。Djangoのmodel fieldsにはUUIDFieldがあり、UUIDを簡単に扱うことができます。また、Pythonのuuidライブラリを使って、UUIDv1/UUIDv3/UUIDv4/UUIDv5など、以下のようなUUIDを生成できます。その中に一番利用されているのはuuid4です。
-
UUIDv1：
-
ハードウェアのMACアドレスと現在のタイムスタンプを基に生成されます。特定の機器で生成されたことがわかるため、プライバシーに懸念がある場合があります。
-
-
UUIDv3：
-
UUIDv4：
-
完全にランダムな値を基に生成されます。最も広く利用されていて、一意性が高いです。
-
-
UUIDv5：
RFC9562で新しく提案されたUUIDv6/UUIDv7/UUIDv8について、まだ広く利用されていないため、現在利用できるpipはまだ少ないです。例えばこちらの uuid6 pipでは、uuid6とuuid7が利用できます。こちらの uuid7 pipではuuid7だけが利用できます。
-
UUIDv6：
-
UUID1と同様にタイムスタンプを基にしていますが、順序性を改善し、ソート可能なように設計されています。
-
-
UUIDv7：
-
タイムスタンプに基づいたUUIDで、時間順にソート可能です。UUID6とは異なり、タイムスタンプ部分が先頭に配置されています。
-
-
UUIDv8：
-
カスタムのUUIDとして定義されています。特定の用途や要件に応じて設計されます。
-
UUID v1の仕組み
UUID v1において、UNIXタイムスタンプではないですが、実には最初の数桁は一応タイムスタンプ方式を採用しました。しかし、残念ながらその並ぶ順番はタイムスタンプのlower bitは先に並ばれたので、ソートできる単調増加の値ではありません。また、第13桁の4-bitはバージョン表示用に利用されて固定です。第17桁の2-bitも、バリエーション表示用に利用されて固定であり、最終的に128-bitの空間は実質的122-bitしか利用できません。そのほか、MACアドレス取得できないケースや、MACアドレス暴露によるプライバシー問題に繋がるとも指摘されています。
UUID v1は、時間ベースで生成されるUUIDであり、以下のような構造を持っています。
-
タイムスタンプ：60-bitのタイムスタンプを使用します。これは、協定世界時（UTC）1582年10月15日0時0分0秒からの100ナノ秒単位での経過時間です。1582年10月15日はカトリック教会におけるグレゴリオ暦の実施日です。
-
バージョン：第13桁の4-bitはバージョン番号を示します。UUID v1の場合、これは0b0001となります。
-
バリエーション：第17桁の2-bitはバリエーション番号を示します。常に0b10となります。
-
クロックシーケンス：14-bitのクロックシーケンスは、複数のUUIDが同じタイムスタンプで生成された場合に一意性を確保するために使用されます。
-
ノード：48-bitのノードは、通常、デバイスのMACアドレスを使用します。MACアドレスが利用できない場合は、ランダムな値が使用されます。
-
ソートの問題：
-
タイムスタンプの低位ビットが先に配置されているため、時間順にソートすることが困難です。これにより、時間ベースのソートができないという課題があります。
-
一方、比較する際に変化が激しい低位ビットを先に比較するために、比較時の性能が上がります。
-
-
タイムスタンプ問題：
-
バージョンとバリエーションの固定ビット：
-
これはUUID v1の問題というより、UUID全体的の問題です。UUIDにはバージョンを示す4-bitとバリエーションを示す2-bitが固定されているため、実質的には128-bitの空間のうち122-bitしか利用できません。
-
一方、バージョンとバリエーション情報を活用できるシステムにおいて、利点になります。
-
-
プライバシー問題：
-
MACアドレスが利用できない場合：
-
MACアドレスが利用できない場合、ランダムな値を使用することになりますが、これにより一意性が若干低下する可能性があります。
-
そこで、UUID v1は、時間ベースで生成される一意識別子ですが、その構造上の制約からいくつかの課題を抱えています。特に、ソートの問題やプライバシー問題、固定ビットによる空間の制約が主な課題です。これらの問題を解決するために、UUID v4やv6、v7などその他のバージョンが利用されることが多くなっています。
UUID v4の仕組み
UUID v4は、他のUUIDバージョンと異なり、UNIXタイムスタンプやMACアドレスを一切使用せず、固定ビット以外は完全にランダムな値を基に生成されます。ただし、各ライブラリの実現にもよりますが、仕様上でランダム値を作成するためにシード値(Seed)の提供が常に求められています。
UUID v4の構造は次の通りです。
-
ランダム値：122-bitのランダム値が提供されたシード値によって生成されます。
-
バージョンビット：UUID v4の場合、第13桁の4-bitはバージョン番号4の0b0100を示します。
-
バリエーションビット：第17桁の上位2-bitはバリエーションを示し、常に0b10に設定されます。
-
一意性：122-bitを完全にランダムな値を使用するため、一意性が非常に高いです。衝突の可能性は非常に低く、実質的に無視できるレベルです。
-
簡便性：他のUUIDバージョンと異なり、タイムスタンプやMACアドレスに依存しないため、生成が非常に簡単です。
-
プライバシー：MACアドレスなどの機器固有情報を含まないため、プライバシーに関する懸念がありません。
一方、UUID v4の生成において、ランダム値生成におけるシード値は、直接にランダム値の品質を決めるために、非常に重要です。シード値の提供は、以下の理由で求められます。
-
再現性：特定のシード値を使用することで、同じ乱数列を再現することが可能です。これにより、テストやデバッグが容易になります。
-
セキュリティ：暗号学的に安全な乱数生成方法を使用することで、予測可能性を低減し、UUIDの一意性と安全性を保証します。例えば、Pythonのos.urandom()は暗号学的に安全な乱数を生成します。
UUID v4は、完全にランダムな値を基に生成されるため、一意性が高く、生成が簡単で、プライバシーに優れています。固定ビット以外はすべてランダム値で構成され、シード値の提供により安全かつ再現性のある乱数生成が可能です。そこでUUID v4は、多くのアプリケーションで広く利用されている標準的な一意識別子です。
UUID v7の仕組み
2024年5月に発表されたRFC9562では、UUIDの新しいバージョ 6、7、8が提案されました。その中で、UUID v6とUUID v7は、UUID v1と同じように最初の数桁はタイムスタンプ方式を採用していますが、以下は異なる点です。
-
タイムスタンプ種類
-
タイムスタンプのビット配置：
-
タイムスタンプ以外のビット配置：
-
UUID v6：UUID v1を利用してきたシステムとの互換性を維持するために、同じ配置になります。
-
UUID v7：固定ビット以外に、すべてを単調増加できるランダム値にしました。
-
UUID v7は以下のような構造を持っています。
-
タイムスタンプ：最初の48-bitはUNIXタイムスタンプのミリ秒単位での表現です。これにより、時間順にソート可能です。
-
バージョン：第13桁の4-bitはバージョン番号7の0b0111を示します。
-
バリエーションビット：第17桁の上位2-bitはバリエーションを示し、常に0b10に設定されます。
-
ランダム値：残りの80-bitは単調増加できる暗号学的に安全なランダム値です。
ULIDとUUIDとの互換性問題
ULID実はUUIDと互換性があります。これは、UUIDが持つ一意性と識別性を活かしながら、ULIDの利点である時間順にソート可能な特徴を取り入れているためです。これにより、ULIDは多くのアプリケーションでUUIDの代替として使用できます。しかし、ULIDはUUIDと互換性がありますが、ある特定のバージョンのUUIDに変換されるわけではありません。なぜなら、ULIDから変換されたUUIDは、実はバージョン情報のないUUIDになるからです。そのため、UUIDのバージョンに依存するアプリケーションでは注意が必要です。
ULIDベースのUUID
UUID v7が提案されるまで、ULIDベースのUUIDはある意味、MongoDBのObjectID、UUID v1およびUUID v4の特徴を組み合わせたような構造を持つ、一種の「キメラ」のような存在でした。
なぜなら、最初の48-bitのUNIXタイムスタンプは、MongoDB の ObjectID のように high-bitからlow-bitまでの単調増加のソートできる順番で並んでいます。次に、最後の80-bitのランダム値は、外部からシード値を提供する必要がなく、UUIDで元々バージョンやバリエーションなどを表示するための第13桁と第17桁の固定ビットもバージョンやバリエーションの意味を持たず、128-bitの空間を丸ごとで利用できるようになりました。したがって、UUID v4のバージョン指定でUUIDのValidationを行う場合、偶然にバージョン4のUUIDが作成された場合を除き、バージョンの検証に通らないはずです。
最終的に UUID: 017FE093-7ADF-9932-AAAA-01FD0BA14D3F に変換できます。
理論上このUUIDの第13桁のバージョン値を見ると9なので、これはUUID v9のはずだと思われます。一方、現在UUID v9はまだ発表されていないために、このバージョンビットの値はデタラメであることがすぐわかります。
UUIDv7が正式的に発表された今、ULIDの素晴らしさを再認識
RFC9562の「Motivation」と言った章節に、参考になったリストの中にULIDが堂々と1位に載せています。
UUIDへ変換後のULIDを見ながら、UUID v7と比較してみると、UUIDの特徴である4-bitの固定version fieldと、2-bitの固定のvariant fieldを除くと、ULIDとUUID v7とはまるで双子のような存在に見えます。さらに、ULIDには固定ビットが存在しないため、UUID v7の74-bitのランダム値の空間に対して、ULIDは80-bitのランダム空間を有しています。
また、ULIDはBase32でエンコードしているために、32桁かつハイフンも入りのHexでエンコードしているUUIDと比べ、わずか26桁の文字列で表現できるULIDでは桁数の長さ制限があるシステムの中において、大きいなアドバンテージになります。特に、サードパーティーのシステムと連携する際に、26桁以内のIDが要求される仕様は多く見られます。またUUIDの文字列を扱う際に、ハイフンの有無の悩みも自然に解消されます。
ULIDやUUIDの切り出し問題
ULIDやUUID v7の一部を切り出して使ってもいい？
システムは仕様上で20桁のIDが必要なので、安直にULIDやUUID v7の先頭20桁だけを切り出して使ってもいいじゃないと思ってしまうかもしれません。しかし、ULIDやUUID v7の識別子は、一部を切り出して使用することは基本的に推奨されません。
なぜなら、ULIDでもUUID v7でも、UNIXタイムスタンプ以外のランダム部分は、同じミリ秒において初期値は確かにランダム値ですが、同じミリ秒以内で1個以上生成すると後続のIDは+1で単調増加するからです。ゆえに、安直に最後の1桁でも切り捨てたら、同じミリ秒以内生成されたIDはほぼ確実に衝突になります。
例えば、ULIDやUUID v7の先頭20桁だけを使用すると、実質的にUNIXタイムスタンプの部分だけを切り出した場合との衝突の確率は同じになります。この場合、ミリ秒ごとに1個以上のIDを生成しない限りは衝突しませんが、そうでない場合は衝突のリスクが生じます。
そこで、UNIXタイムスタンプの部分だけを切り出して使えるシーンは、ミリ秒ごとに1個以上のIDを生成しないことを確保できるシステムだけに適用できます。つまり、もし衝突したら、必ず1ミリ秒を待ってたらIDを再生する仕組みを作る必要があります。
実はsnowflakeはこのような仕組みを持ってます。もっと明確にいうと、snowflakeは同じミリ秒内に最大4096個のIDを生成できます。1ミリを待ってるのでなく、1ミリ秒内に4096個以上のIDを生成しようとすると、シーケンス番号が枯渇し、衝突の可能性が出てきます。この場合、シーケンス番号が4095に達した場合、次のミリ秒が来るまで待機します。
そこで、この問題を解決するためには、次のような方法があります。
-
ミリ秒ごとに1つのIDしか生成しないシステムにする。
-
ID生成の衝突回避アルゴリズムを導入する。
このように、システムで20桁のIDを使用する場合は、単にULIDやUUID v7の先頭20桁を切り出すのではなく、衝突を回避するための適切なアルゴリズムや仕組みを導入する必要があります。
その他、ランダム部分で同じミリ秒で1個以上のIDを生成した場合+1するようにする単調性(Monotonicity)の保証は、ULIDやUUID v7の仕様には推奨してますが、強制ではありません。多くのULIDの実現はデフォルトで実は単調性(Monotonicity)なしの実装となります。例えば、Pythonのahawker版のulidライブラリでは、単調性保証付きのULIDを利用するにはfrom ulid import monotonic as ulidのように単独のmonotonicライブラリからimportする必要があります。そのために、ランダムの部分の単調性がないのULIDの場合、話は少し違います。
ランダムの部分の単調性がない場合、一応切り出して使ってそれほど問題ありませんが、衝突耐性は残ったランダム部分のサイズによって、劇的に低下する可能性があります。大抵1桁(4-bit)が切り出されることにつれて、4倍の逓減率で衝突する試行回数の期待値が減少しますので、そのリスクを認識した上で利用する必要があります。一方、この場合でも、ID生成の衝突回避アルゴリズムを導入することで解決できます。
UUID v4の一部を切り出して使ってもいい？
答えはYES and NOです。
UUID v4の場合、確かにほぼすべてのビットがランダム値で、タイムスタンプ情報などが持たないために、別にその一部を切り出してもいいという発想があるかもしれません。しかし、UUID v4の一部だけを切り出して利用する場合、以下のリスクを認知した上で利用する必要があります。
-
衝突耐性は劇的に低下になるリスク。
-
UUID v4は非常に高い衝突耐性を持っています。p=0.5の時、約231京(2.31e+18)の試行回数の期待値が必要とされます。一方、1桁(4-bit)が切り出されることにつれて、16倍の逓減率で利用できる組み合わせの数が減少します。4倍の逓減率で衝突する試行回数の期待値が減少します。システムの規模やIDの生成率によって、IDが衝突する可能性が高騰するなど不都合が生じる可能性があります。
-
-
固定ビットの存在が支障になるリスク。
-
前文で紹介したようにUUID v4では、第13桁の4-bitでバージョン番号を示す固定ビットと、第17桁の上位2-bitでバリエーションを示す固定ビットが存在します。一部を切り出すことによって、UUID v4の検証ができなくなるので、バージョンやバリエーションの検証が必要とされるシステムには不都合が発生します。
-
そこで、UUID v4の一部を切り出して利用したい場合、上記のリスクを十分に評価した上で利用しなければなりません。
また、UUID v4の一部だけを切り出して利用するよりは、現在のシステムの需要に応じて、暗号学的に安全な乱数生成メカニズム（例えばpythonの場合os.urandom()など）を利用して、上記に紹介したUUID v4やUUID v7またULIDなどの特性を吸収し、システムに合わせた独自のIDを改めて設計したほうが良いでしょう。
まとめ
以上は基礎篇の内容です。全面的に整数型ID、Snowflake ID、MongoDBのObjectID、ULIDまたUUIDなどの特徴、比較と選択について詳しく述べました。次の選択編ではULID移行時に整数型IDと入れ替わるべきか？共存させるべきか？について詳しく説明します。
この記事、もしご参考になればとてもうれしいです。OLTAでは Tech Vision の元、一緒にユーザーに価値を提供し、その結果事業を成長させるサービス作り続けるための仲間を募集しています。 もし、この投稿にご興味を持っていただいたら、是非カジュアルにお話しさせてください。
