UUIDの衝突を招く実装パターンの知識マップ(知識グラフ)
UUIDの衝突事故の多くは規格そのものではなく、生成や運用が前提を壊すことで起きると整理する記事です。RFC 9562が定めるUUIDv4はCSPRNGによる122ビットの乱数領域を、UUIDv7はカウンタによる単調性の設計を前提としており、固定seedの弱いPRNGでの自作やfork・snapshot後の生成器状態の巻き戻り、UUIDv3/v5を新規採番用途に誤用すること、UUIDv8の実装依存な一意性への過信、128ビットを削る切り詰めがいずれも重複を招きます。RFC自身が真のglobal uniquenessを絶対保証しないとしている以上、DB側のUNIQUE制約が重複挿入を防ぐ最終防衛線になります。
UUID
128ビットの識別子で、実装上十分な一意性を提供する一方、真のglobal uniquenessを絶対保証はしない識別子形式のこと。
RFC 9562
UUIDの形式、各version、生成のベストプラクティスを定めるIETFの標準文書のこと。
CSPRNG
次の値を予測しにくいことを設計目標に含む、暗号学的に安全な疑似乱数生成器のこと。
暗号学的に安全な疑似乱数生成器
UUIDv4
version/variantを除く122ビットを乱数で埋める、ランダムベースのUUIDのこと。
弱いPRNGによるUUID自作
一般用途のPRNGを固定seedなどで回し、UUID形式の文字列を自前で組み立てる実装のこと。
自前実装のUUID
新規採番
新しいレコードに一意な識別子を新規に割り当てる採番という用途・状況のこと。
新規レコードのID発行
UUIDv3/v5
同じnamespaceと同じcanonical nameから同じUUIDを再生成する、決定論的なUUIDv3/UUIDv5の総称のこと。
決定論的UUID
UUIDv8
一意性が実装依存であり前提にしてはいけないと定められた、実験用・ベンダー独自用のUUIDのこと。
UUIDの衝突
本来別々であるべき2つ以上の対象に、同じUUID値が発生・付与されてしまうことのこと。
UUIDの重複
生成器の状態
乱数の内部状態、clock sequence、カウンタなど、次のUUIDを決める生成器の状態のこと。
カウンタの桁あふれ
カウンタが最大値を超えて0へ戻ることのこと。
時刻の巻き戻り
NTP補正や手動変更で、システム時刻が前の値へ戻ることのこと。
UUIDの切り詰め
先頭数文字だけの利用や64ビット整数への圧縮など、128ビットの一意性の材料そのものを削る変換のこと。
切り詰め
prefix比較
DB側の一意制約
列や列集合の値がテーブル全体で一意であることを保証する、DB側のUNIQUE/PRIMARY KEY制約のこと。
UNIQUE制約
PRIMARY KEY制約
fork後の再seed
process forkのような状態変化のたびに、CSPRNGの状態を再seedすることのこと。
再初期化
UUIDv7
48ビットのUnixミリ秒タイムスタンプに、乱数やcarefully seeded counterによる74ビットを組み合わせる、時系列ソート可能なUUIDのこと。
単調性
あとから作ったUUIDのほうが必ず大きい値になる性質のこと。
namespace
UUIDv3/v5で名前を解釈する文脈を決める、name-based UUID生成に使うほうのUUIDのこと。
名前空間
正規化
大文字小文字や末尾のスラッシュまで含め、同じ対象を指す文字列を1つの形にそろえる処理のこと。
UUIDv1/v6
MACアドレス由来のnodeとclock sequenceを使う時刻系のUUIDのこと。UUIDv6はDB localityの改善のためUUIDv1を並べ替えたもの。
時刻系UUID
UUIDv4はversion/variantを除く122ビットの乱数領域を持ち、RFC 9562はその生成にCSPRNGを使うべきとしている(Section 6.9のSHOULD要件であり、用途によっては例外設計もあり得るとされる)
一般用途PRNGをseed固定などで回してUUID形式の文字列を自作することは、新規採番用途に用いる実装として推奨されない
UUIDv3/v5は同じnamespaceと同じnameから同じUUIDを再生成する決定論的IDであり、新規採番用途に用いることは推奨されない
UUIDv8の一意性は実装依存であり前提にしてはいけないため、一意性が必要な新規採番用途に用いることは推奨されない
同じseedの一般用途PRNGは別プロセスや別ノードでも同じ系列を再現するため、重複を招くことがある
stable storageを持たない実装でVM snapshotやコンテナ複製後に生成器の状態が巻き戻ると、重複が出ることがある
UUIDv3/v5を毎回新規採番として使うと、同じnamespaceと同じnameから同じUUIDが再生成され重複することがある
UUIDv7で同一ミリ秒内の連番カウンタが桁あふれすると、重複したUUIDが出ることがある
時刻が戻ったときに何もせず生成を続けると、UUIDv7などの時刻系UUIDで重複が出ることがある
128ビットのうち一意性の材料そのものを削る変換(先頭数文字だけの利用、64ビット整数への圧縮など)は重複を招く
UNIQUE/PRIMARY KEY制約は、列や列集合の値がテーブル全体で一意であることを保証し、重複した値の挿入そのものを防ぐ。ただし採番側で重複したUUIDが生成された事実は残るため、衝突そのものを防ぐわけではなく影響を止める仕組みである
process forkのような状態変化のたびにCSPRNGの状態を再seedすることで、状態の巻き戻りによる重複を軽減する
OS/ランタイム標準のCSPRNGベースのUUID API(uuid4()など)をそのまま使うことは、一般用途PRNGでのUUID自作を避ける対策になる
単調性を保つよう正しく設計・実装されたUUIDv7は、rand_aを専用カウンタにする、またはrand_bをランダム初期化カウンタとして使うなどの設計を利用する。counter rolloverやclock rollbackを考慮しない自作実装ではこの保証は成り立たない
桁あふれ時にタイムスタンプを繰り上げるなどの対策をしていない場合、カウンタが0へ戻るとあとから作ったUUIDのほうが必ず大きくなるという単調性が崩れる
時刻が前の値へ戻ったときに何も対策しない場合、あとから作ったUUIDのほうが必ず大きくなるという単調性が崩れる
UUIDv3/v5はnamespaceと呼ばれる文脈用UUIDと、canonical nameの組み合わせから決定論的にUUIDを生成する
同じcanonical formatのsame nameをsame namespaceで生成したUUIDが常に等しくなるためには、nameのcanonicalizationを仕様として固定することを前提とする
UUIDv4の122ビット乱数領域の仕様はRFC 9562のSection 5.4で確認できる
UUIDv7のtimestampとrandom bits、counterの構成はRFC 9562のSection 5.7で確認できる
UUIDv3/v5のnamespace + canonical nameによる生成規則はRFC 9562のSection 6.5で確認できる
UUIDv8の一意性が実装依存であることはRFC 9562のSection 5.8で確認できる
UUIDv6のnode/clock sequenceやDB locality改善の設計はRFC 9562のSection 5.6で確認できる
仮想マシンやコンテナの登場でMACアドレスの一意性はもはや保証されず、node IDの複製やclock sequenceの固定値化は重複を招くことがある
UUIDの形式全体の仕様はRFC 9562で確認できる