OLTA TECH BLOG

テクノロジーと好奇心で事業を成長させる

TECH BLOG

ULID移行から最適な自己流IDの設計まで・その2【基礎編】:整数型ID、Snowflake ID、MongoDBのObjectID、ULID、UUIDなどの特徴、比較と選択

 

◇ アノキミモノガタリその弐

アノ日のULID、キミとまた出会えるまで十億億回の輪廻のタイムスリップ、A.D.10889年まで。

君の名は、01FZG96YPZK4SANAG1ZM5T2K9Z、忘れないその目。

タイムマシンのプロトタイプ開発は成功した途端、投資家たちへの報告会で、

すぐに不明な理由でクリスタ星人の怪獣ボスがコントロールしているボード会で、

CEOの座が取られ、会社から追い出された。

愚かな行動。

まだプロトタイプ段階のタイムマシンは実には、

実験成功した瞬間で、タイムループができてしまった。

テストで利用されてたその時刻、令和4年4月1日零時23分55秒の999ミリ秒にしか戻れない。

50年1回の輪廻。

勇気を持って、研究室のビルから退去される直前に、

自分を実験体に、タイムマシンを再度起動した。

ごめんな、この前、実験体として50年前に送った柴犬のコマちゃん、

まだ17歳のボクに、出会えたのだろう。

いまから、あなたたちの未来を剥奪した贖罪としてコマちゃんに、ボクに、あいにいく。

ぼくは永遠にタイムループの中にトラップされた。

はじめに

こんにちは、転生したら相変わらずエンジニアだった OLTA(オルタ)プロダクトグループ研究開発チームのタイトルの前置きがとにかく長い B.です。

INVOYカードの開発を担当しています。

今回、UUID*1RFCRFC4122から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などの特徴と比較

よのなかの分散型一意識別子,Snowflake ID,MongoDB ObjectID,ULID,UUIDv1,UUIDv4,UUIDv7,ULID↔UUID,Ulid-Flake

よのなかの分散型一意識別子

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秒

 

UNIXタイムスタンプ (Unix Epoch Time)

協定世界時 (UTC) 1970年1月1日0時0分0秒

UNIXタイムスタンプ (Unix Epoch Time)

協定世界時 (UTC) 1970年1月1日0時0分0秒

カトリック教会におけるグレゴリオ暦の実施日

協定世界時 (UTC)1582年10月15日

N/A

UNIXタイムスタンプ (Unix Epoch Time)

協定世界時 (UTC) 1970年1月1日0時0分0秒

時間部分の利用可能期限 (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において各秒で

各ミリ秒で

同じ機器のMACアドレス各100ナノ秒

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などの特徴と比較

整数型ID、Snowflake ID、MongoDBのObjectID、ULID、UUIDの選択フローチャート

整数型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」

    • 非分散システム(シングルServer/Pod)なので、生成されたIDの一意性が確保されています。シングルDBなのか、マルチDBなのか、特に気にする必要がありません。

      • 衝突の検知と自動回避メカニズムは、並行プロセスあっても、threadなどの排他的制御によって簡単に実現できます。

      • 例えばpythonの場合threading.Lock()を利用したり、goの場合sync.Mutex.Lock()を利用したりすることで実現できます。

  • 経路B: MongoDB? -no-> Sortable? -yes> Uniqueness? -no> Timestamp? -yes-> Unpredicatable? -yes-> 「ULIDまたはUUID v7」

    • 非分散システム(シングルServer/Pod)である限り、生成されたIDの一意性が確保されています。シングルDBなのか、マルチDBなのか、特に気にする必要がありません。

      • 前述の通り、衝突の検知と自動回避メカニズムは、並行プロセスあっても、threadなどの排他的制御によって簡単に実現できます。

      • 例えばpythonの場合threading.Lock()を利用したり、goの場合sync.Mutex.Lock()を利用したりすることで実現できます。

    • 分散システム(マルチServer/Podで、シングルDB)の場合、生成されたIDの一意性が確保されません。

      • なぜなら、threadingもmutexも作用範囲は同じサーバーにあるプロセスのthreadgoroutineだからです。

      • このケースでも生成されたIDの一意性を確保したい場合、大抵データベースの主キー(PK)の一意性制約(UNIQUE KEY)を利用して、DBに保存する時点で返したエラーを利用して、衝突の検知と自動回避メカニズムを実現させます。

    • 分散システム(マルチServer/Podで、マルチDB)の場合、生成されたIDの一意性が確保されません。

      • なぜなら、まず同じくthreadingもmutexも作用範囲は同じサーバーにあるプロセスのthreadgoroutineだからです。また、主キー(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符号ビット

    • Snowflake IDは64-bitの符号付き整数型を採用したため、最初の1-bitは実質的にpositive integerのsign-bitとして利用されています。常に0に設定されています。

  • 41-bitタイムスタンプ

    • Snowflake IDは短いタイムスタンプを最大限に利用するために、協定世界時(UTC)1970年1月1日から始まるUNIXタイムスタンプでなく、独自のエポック(Epoch, 基準時刻)の協定世界時(UTC)2010年11月04日1時42分0秒を利用しました。

    • 基準時刻からの経過時間をミリ秒単位の精度で表します。

    • 41-bitを使用することで、約69年間の時間を表現できます。少なくとも協定世界時 (UTC) 2080年07月10日までに利用可能です。

  • 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に達した場合は、次のミリ秒が来るまで待機します。

Snowflake IDの構成図

Snowflake IDの特徴は以下に挙げられます。
  • 時間順にソート可能

    • タイムスタンプが先頭に配置されているため、生成されたIDはミリ秒の精度で時間順にソート可能です。

  • スケーラビリティ

    • データセンターIDとマシンIDを組み合わせることで、大規模な分散システムに対応できます。

    • ただし、各機器のシステム時間を1ミリ秒もずれないよう合わせるためにNTP(Network Time Protocol)周りの設定と調整、また時間にて生成されたIDが衝突しないように協調するためには大変です。SnowflakeIDは以上のことを確保できています。

  • BigInt (長整数型、long int型) との互換性

    • 符号付きの64-bit方式を採用したために、長整数型とは完全な互換性があります。

    • UUIDULIDのように、特殊なmodel fieldを定義しなくても普通にBigIntとして利用できます。

  • 絶対的な一意性

    • 分散システムにおいて、各データセンターやリージョン、また各マシンやノードで、一意なIDを生成できます。

    • 同じミリ秒内でも単調増加のインクリメント仕組みや、最大値に達したら待機するメカニズムも有するため、生成されたIDは衝突はしない絶対的な一意性が確保されています。

    • またNTPサービスによって、時刻逆行現象が発生した時に、各サーバーで生成した最後のIDのlast_timestampを記録することで、記録したタイムスタンプより前のタイムスタンプが急に現れてきた際に、待機するようなメカニズムも有するため、時刻逆行した時の一意性も確保できています。

  • コンパクトで検索や挿入性能が良い

    • 整数型自動採番と同じような単調増加性を有するために、サイズもコンパクトで64-bitだけのため、B+tree構造を採用したDBには、とても高い検索や挿入性能を持っています。

  • ある程度の予測可能性と潜在的なプライバシー問題

    • 同じデータセンターまた同じ機器の場合、ワーカーIDの部分が固定のため、生成されたIDの序列は予測しやすくなります。また、データセンターや機器の情報も暴露されます。

    • 最後のシーケンス部分は初期値0から始まる+1の数列であるために、生成されたIDはある程度予測可能な状態になります。

    • Twitterのような誰でも見れるユーザー生成コンテンツ(UGC, User Generated Contents)サービスにおいて特に支障になります。一方、タイムスタンプやローケーションなどを非公開にする必要があるサービスにおいて、利用されるシーンによって不都合が発生するリスクもあります。

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 を例で説明すると、以下のようなイメージです。

MongoDB ObjectID Version 0.1 構成図
MongoDB では特有な BSON (Binary JSON) データ交換フォーマットが存在し、その中に ObjectID というデータタイプがあります。ObjectID とは、トータル24桁12-byteの文字列で構成され、以下のように分割されます。
  • 最初の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は単調増加のランダム文字列

MongoDB ObjectID Version 0.2 以降の構成図

ULIDの仕組み

ULID (Universally Unique Lexicographically Sortable Identifier)は、MongoDBのObjectIDに非常に近い理念を採用していますが、マシンIDなどの部分を持たないため、さらにシンプルで明快な構成を持っています。ULIDは以下の2つの部分で構成されています。
  • 48-bitのUNIXタイムスタンプ部分

    • ミリ秒単位の精度を持ち、生成された時刻を表します。

    • 協定世界時UTC)10889年8月2日まで使用できます。

  • 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における広い空間

ULIDは、広い識別子空間を持っています。UNIXタイムスタンプ部分の精度はミリ秒まで、10桁、48-bitで、最大値は7ZZZZZZZZZです。これにより、少なくとも協定世界時UTC)10889年8月2日5時31分50秒655ミリ秒まで問題なく使用できます。

# 2^48-1ミリ秒
>>> math.pow(2, 48) - 1
281474976710655
>>> import datetime
>>> datetime.datetime.fromtimestamp(281474976710655/1000.0)
ValueError: year 10889 is out of range
>>> datetime.MAXYEAR
9999

Pythondatetimeライブラリの年の最大値を超えてしまうため、JavaScriptDateで試してみます。

> new Date(281474976710655).toISOString()
'+010889-08-02T05:31:50.655Z'
// 10889-08-02T05:31:50.655Z

さらに、後ろのランダム値の部分は、16桁、80-bitで、最大値は ZZZZZZZZZZZZZZZZ です。約各ミリ秒で1.21𥝱(じょ/億京)の組み合わせが存在します。

# 2^80≒1.21e+24
>>> math.pow(2, 80)
1208925819614629174706176

これは、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での排他的制御を実装する必要があります。

  • ランダム値部分の最大値オーバーフロー問題

    • もし偶然で最後の80-bitのランダム値部分が最大値ZZZZZZZZZZZZZZZZに近い値が作成された場合、最大値に到達するとoverflowが発生します。このとき、最小値0000000000000000に戻されるのではなく、overflow errorが発生します。

    • Snowflakeのようなシーケンス番号が枯渇した場合、次のミリ秒が来るまで待機するメカニズムや、衝突した場合の衝突回避メカニズム、またULID発行専用サーバーを設定することなどでULIDの単調性の破綻問題を回避できます。

  • 単一障害点(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兆回になります!

# 2^(80/2)≒1.1e+12
>>> math.pow(2, 40)
>>> 1099511627776

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の一意識別子で、様々な用途で広く利用されています。Djangomodel fieldsにはUUIDFieldがあり、UUIDを簡単に扱うことができます。また、Pythonuuidライブラリを使って、UUIDv1/UUIDv3/UUIDv4/UUIDv5など、以下のようなUUIDを生成できます。その中に一番利用されているのはuuid4です。

  • UUIDv1

    • ハードウェアのMACアドレスと現在のタイムスタンプを基に生成されます。特定の機器で生成されたことがわかるため、プライバシーに懸念がある場合があります。

  • UUIDv3

    • 名前空間に基づいたMD5ハッシュを使用して生成されます。同じ名前空間と名前の組み合わせに対しては同じUUIDが生成されます。

    • MD5ハッシュはすでにCollision Attacksなどの面で脆弱なので、安全ではありません。SHA-1ハッシュを使用したUUIDv5がおすすめされます。

  • UUIDv4

    • 完全にランダムな値を基に生成されます。最も広く利用されていて、一意性が高いです。

  • UUIDv5

    • UUID3と同様に名前空間に基づいて生成されますが、SHA-1ハッシュを使用します。

RFC9562で新しく提案されたUUIDv6/UUIDv7/UUIDv8について、まだ広く利用されていないため、現在利用できるpipはまだ少ないです。例えばこちらの uuid6 pipでは、uuid6uuid7が利用できます。こちらの 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 v1の課題点として以下が挙げられます。
  • ソートの問題

    • タイムスタンプの低位ビットが先に配置されているため、時間順にソートすることが困難です。これにより、時間ベースのソートができないという課題があります。

    • 一方、比較する際に変化が激しい低位ビットを先に比較するために、比較時の性能が上がります。

  • タイムスタンプ問題:

    • UNIXタイムスタンプではないために、かつ100ナノ秒という微妙な単位の精度を持っているため、変換する時に扱いづらいかもしれません。

  • バージョンとバリエーションの固定ビット

    • これはUUID v1の問題というより、UUID全体的の問題です。UUIDにはバージョンを示す4-bitとバリエーションを示す2-bitが固定されているため、実質的には128-bitの空間のうち122-bitしか利用できません。

    • 一方、バージョンとバリエーション情報を活用できるシステムにおいて、利点になります。

  • プライバシー問題

    • ノード部分にMACアドレスを使用するため、MACアドレスが外部に暴露される可能性があります。これにより、デバイスが特定され、プライバシーに関する懸念が生じます。

  • 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に設定されます。

UUID v4 の構成図
UUID v4は、以下の特性を持ちます。
  • 一意性122-bitを完全にランダムな値を使用するため、一意性が非常に高いです。衝突の可能性は非常に低く、実質的に無視できるレベルです。

  • 簡便性:他のUUIDバージョンと異なり、タイムスタンプやMACアドレスに依存しないため、生成が非常に簡単です。

  • プライバシーMACアドレスなどの機器固有情報を含まないため、プライバシーに関する懸念がありません。

一方、UUID v4の生成において、ランダム値生成におけるシード値は、直接にランダム値の品質を決めるために、非常に重要です。シード値の提供は、以下の理由で求められます。

  • 再現性:特定のシード値を使用することで、同じ乱数列を再現することが可能です。これにより、テストやデバッグが容易になります。

  • セキュリティ:暗号学的に安全な乱数生成方法を使用することで、予測可能性を低減し、UUIDの一意性と安全性を保証します。例えば、Pythonos.urandom()は暗号学的に安全な乱数を生成します。

UUID v4は、完全にランダムな値を基に生成されるため、一意性が高く、生成が簡単で、プライバシーに優れています。固定ビット以外はすべてランダム値で構成され、シード値の提供により安全かつ再現性のある乱数生成が可能です。そこでUUID v4は、多くのアプリケーションで広く利用されている標準的な一意識別子です。

UUID v7の仕組み

2024年5月に発表されたRFC9562では、UUIDの新しいバージョ 6、7、8が提案されました。その中で、UUID v6UUID v7は、UUID v1と同じように最初の数桁はタイムスタンプ方式を採用していますが、以下は異なる点です。

  • タイムスタンプ種類

    • UUID v1で利用したカトリック教会におけるグレゴリオ暦の実施日の1582年10月15日を初期値でなく、UUID v6UUID v7では、もっと汎用的な協定世界時 (UTC) 1970年1月1日0時0分0秒から始まるUNIXタイムスタンプを採用しました。

    • 時間の精度もUUID v1で利用した100ナノ秒でなく、UUID v6UUID v7では、もっと一般的なミリ秒単位の精度を採用しました。

  • タイムスタンプのビット配置

    • UUID v6UUID v1を利用してきたシステムとの互換性を考慮した仕様です。UUID v1のタイムスタンプのlower bithigher bit配置を交換し、時間順にソート可能にしたバージョンです

    • UUID v7high-time, mid-time, low-time方式のsection配置を完全にやめることで、ULIDと同じように先頭の48-bitを丸ごとにUNIXタイムスタンプにしました。これにより、ULIDと同様に時間順に並べることができます。また、新規導入の場合はUUID v7を利用すべき(SHOULD)とRFC 9562で述べられています。

  • タイムスタンプ以外のビット配置

    • UUID v6UUID v1を利用してきたシステムとの互換性を維持するために、同じ配置になります。

    • UUID v7:固定ビット以外に、すべてを単調増加できるランダム値にしました。

UUID v7は以下のような構造を持っています。

  • タイムスタンプ:最初の48-bitUNIXタイムスタンプのミリ秒単位での表現です。これにより、時間順にソート可能です。

  • バージョン:第13桁の4-bitはバージョン番号7の0b0111を示します。

  • バリエーションビット:第17桁の上位2-bitはバリエーションを示し、常に0b10に設定されます。

  • ランダム値:残りの80-bitは単調増加できる暗号学的に安全なランダム値です。

UUID v7 の構成図
UUID v7は、時間順にソート可能な一意識別子を提供し、新しいシステムでの導入を推奨します。タイムスタンプの下位ビットを先頭に配置するのをやめることで、ULIDの利点を取り入れ、時間軸でのソートが可能となります。また、ランダム値部分は暗号学的に安全な乱数を使用することで、一意性と安全性が確保されています。これからはUUID v4と共に、UUID v7も主流として多くのシステムに利用されるでしょう。

ULIDとUUIDとの互換性問題

ULID実はUUIDと互換性があります。これは、UUIDが持つ一意性と識別性を活かしながら、ULIDの利点である時間順にソート可能な特徴を取り入れているためです。これにより、ULIDは多くのアプリケーションでUUIDの代替として使用できます。しかし、ULIDUUIDと互換性がありますが、ある特定のバージョンのUUIDに変換されるわけではありません。なぜなら、ULIDから変換されたUUIDは、実はバージョン情報のないUUIDになるからです。そのため、UUIDのバージョンに依存するアプリケーションでは注意が必要です。

ULIDベースのUUID

UUID v7が提案されるまで、ULIDベースのUUIDはある意味、MongoDBのObjectIDUUID v1およびUUID v4の特徴を組み合わせたような構造を持つ、一種の「キメラ」のような存在でした。

なぜなら、最初の48-bitUNIXタイムスタンプは、MongoDB の ObjectID のように high-bitからlow-bitまでの単調増加のソートできる順番で並んでいます。次に、最後の80-bitのランダム値は、外部からシード値を提供する必要がなく、UUIDで元々バージョンやバリエーションなどを表示するための第13桁と第17桁の固定ビットもバージョンやバリエーションの意味を持たず、128-bitの空間を丸ごとで利用できるようになりました。したがって、UUID v4のバージョン指定でUUIDValidationを行う場合、偶然にバージョン4のUUIDが作成された場合を除き、バージョンの検証に通らないはずです。

ULIDベースUUIDのバージョン情報なしの構成図
最初に例で挙げられた ULID: 01FZG96YPZK4SANAG1ZM5T2K9Z は、

最終的に 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を除くと、ULIDUUID v7とはまるで双子のような存在に見えます。さらに、ULIDには固定ビットが存在しないため、UUID v774-bitのランダム値の空間に対して、ULID80-bitのランダム空間を有しています。

また、ULIDはBase32でエンコードしているために、32桁かつハイフンも入りのHexでエンコードしているUUIDと比べ、わずか26桁の文字列で表現できるULIDでは桁数の長さ制限があるシステムの中において、大きいなアドバンテージになります。特に、サードパーティーのシステムと連携する際に、26桁以内のIDが要求される仕様は多く見られます。またUUIDの文字列を扱う際に、ハイフンの有無の悩みも自然に解消されます。

ULIDやUUIDの切り出し問題

ULIDやUUID v7の一部を切り出して使ってもいい?

システムは仕様上で20桁のIDが必要なので、安直にULIDUUID v7の先頭20桁だけを切り出して使ってもいいじゃないと思ってしまうかもしれません。しかし、ULIDUUID v7の識別子は、一部を切り出して使用することは基本的に推奨されません。

なぜなら、ULIDでもUUID v7でも、UNIXタイムスタンプ以外のランダム部分は、同じミリ秒において初期値は確かにランダム値ですが、同じミリ秒以内で1個以上生成すると後続のIDは+1で単調増加するからです。ゆえに、安直に最後の1桁でも切り捨てたら、同じミリ秒以内生成されたIDはほぼ確実に衝突になります。

例えば、ULIDUUID v7の先頭20桁だけを使用すると、実質的にUNIXタイムスタンプの部分だけを切り出した場合との衝突の確率は同じになります。この場合、ミリ秒ごとに1個以上のIDを生成しない限りは衝突しませんが、そうでない場合は衝突のリスクが生じます。

そこで、UNIXタイムスタンプの部分だけを切り出して使えるシーンは、ミリ秒ごとに1個以上のIDを生成しないことを確保できるシステムだけに適用できます。つまり、もし衝突したら、必ず1ミリ秒を待ってたらIDを再生する仕組みを作る必要があります。

実はsnowflakeはこのような仕組みを持ってます。もっと明確にいうと、snowflakeは同じミリ秒内に最大4096個のIDを生成できます。1ミリを待ってるのでなく、1ミリ秒内に4096個以上のIDを生成しようとすると、シーケンス番号が枯渇し、衝突の可能性が出てきます。この場合、シーケンス番号が4095に達した場合、次のミリ秒が来るまで待機します。

そこで、この問題を解決するためには、次のような方法があります。

  • ミリ秒ごとに1つのIDしか生成しないシステムにする

  • ID生成の衝突回避アルゴリズムを導入する

このように、システムで20桁のIDを使用する場合は、単にULIDUUID v7の先頭20桁を切り出すのではなく、衝突を回避するための適切なアルゴリズムや仕組みを導入する必要があります。

その他、ランダム部分で同じミリ秒で1個以上のIDを生成した場合+1するようにする単調性(Monotonicity)の保証は、ULIDUUID 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 v4UUID v7またULIDなどの特性を吸収し、システムに合わせた独自のIDを改めて設計したほうが良いでしょう。

まとめ

以上は基礎篇の内容です。全面的に整数型ID、Snowflake ID、MongoDBのObjectID、ULIDまたUUIDなどの特徴、比較と選択について詳しく述べました。次の選択編ではULID移行時に整数型IDと入れ替わるべきか?共存させるべきか?について詳しく説明します。

この記事、もしご参考になればとてもうれしいです。OLTAでは Tech Vision の元、一緒にユーザーに価値を提供し、その結果事業を成長させるサービス作り続けるための仲間を募集しています。 もし、この投稿にご興味を持っていただいたら、是非カジュアルにお話しさせてください。

 

corp.olta.co.jp

IDシリーズ記事の一覧

techblog.olta.co.jp