UUID version 4は衝突するのか？¶

2017-11-09 公開

UUID(Universally Unique Identifier)とは汎用識別子であり、 ISO/IEC 11578:1996や、 IETFのRFC 4122で仕様が公開されている。

UUID 4の構造¶

RFC 4122ではいくつかバージョンが定められているが、そのうちバージョン4は122ビットの乱数から生成される。

具体的には、UUIDのフォーマットにおけるタイムスタンプやクロックシーケンス、ノードの値をすべて真の乱数か疑似乱数で埋めたものがUUIDバージョン4である。フォーマットの構造は以下のとおりである。

    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
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                          time_low                             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |       time_mid                |         time_hi_and_version   |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |clk_seq_hi_res |  clk_seq_low  |         node (0-1)            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
   |                         node (2-5)                            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

Pythonでは簡単にUUID 4を生成することができる。

import uuid

i = uuid.uuid4()
print("time_low:", i.time_low)
print("time_mid:", i.time_mid)
print("time_hi_and_version:", i.time_hi_version)
print("clk_seq_hi_res:", i.clock_seq_hi_variant)
print("clk_seq_low:", i.clock_seq_low)
print("node:", i.node)

実行結果は以下の通りになる。

time_low: 3924201199
time_mid: 64286
time_hi_and_version: 20234
clk_seq_hi_res: 161
clk_seq_low: 137
node: 160669060093137

衝突確率の計算¶

UUID 4を識別子として使うならば、当然それらが被らない、衝突しないことが期待される。今回は \( N \) 個のUUID 4が生成された場合に衝突する確率を見積もるのが目的である。

\( N \ge 2^{122} + 1 \) の場合¶

UUID 4を \( 2^{122} + 1 \) 個以上生成した場合、UUID 4の全パターンは \( 2^{122} \) であるので、確率1で衝突する。このような論法を鳩の巣原理という。鳩の巣原理は一見単純ながら面白い定理を証明できたりするのだが本題から外れるので割愛する。

以降、\( N \) は \( 2^{122} \) 以下の自然数を考える。

\( N \le 2^{122} \) の場合¶

衝突する確率を直接求めるのではなく、余事象である衝突しない確率を考える。まず、2個のUUID 4を生成してその2つが衝突しない確率は \( \dfrac{2^{122}-1}{2^{122}} \) である。次に3個目のUUID 4を生成していずれの生成したUUID 4と衝突しない確率は \( \dfrac{2^{122}-2}{2^{122}} \) である。この論法を繰り返すと、\( N \) 個のUUID 4が衝突しない確率 \( p_0 \) として次の式を得る。

\[ p_0 = \prod^{N-1}_{k=1}\left(1-\frac{k}{2^{122}}\right). \]

よって、\( N \) 個のUUID 4が生成された場合に衝突する確率 \( p \) は次の式となる。

\[ p = 1 - \prod^{N-1}_{k=1}\left(1-\frac{k}{2^{122}}\right). \]

衝突する確率を計算できたとはいえ、計算が大変である。そこで、適当な不等式で確率を評価する。

下からの評価¶

補題

任意の実数 \( t \) において \( 1 + t \le e^{t} \) が成り立つ。

証明

\( f(t) = e^{t} - (1 + t) \) として微分して増減を調べる。

この不等式を使って衝突する確率を下から評価してみる。

\[ p \ge 1 - \prod^{N-1}_{k=1}\left(e^{-\frac{k}{2^{122}}}\right). \]

指数法則より、

\[ p \ge 1 - e^{\left(\sum^{N-1}_{k=1} -\frac{k}{2^{122}}\right)}. \]

みんな大好き \( \sum \) の計算をすると、

\[ p \ge 1 - e^{-\frac{N(N-1)}{2\times 2^{122}}}. \]

例えば、\( N = 10^{10} \) とすると、\( p \ge 9.4 \times 10^{-18} \) となる。

上からの評価¶

\( i \) 番目と \( j \) 番目に生成したUUID 4を \( u_i, u_j \) と書くとき、衝突とは「ある \( i < j \) について \( u_i = u_j \)」が成り立つ事象である。これは各対についての衝突事象 \( A_{i,j} = \{u_i = u_j\} \) の和集合として表せる。和集合の確率の上界(Booleの不等式)により、

\[ p = \Pr\left(\bigcup_{1 \le i < j \le N} A_{i,j}\right) \le \sum_{1 \le i < j \le N} \Pr(A_{i,j}) = \binom{N}{2} \cdot \frac{1}{2^{122}} = \frac{N(N-1)}{2 \cdot 2^{122}}. \]

例えば、\( N = 10^{10} \) とすると、\( p \le 9.4 \times 10^{-18} \) となり、下からの評価と同じオーダーで押さえられる。

結論¶

結局、UUID 4が衝突する確率は非常に小さく、杞憂である。ただし、これはあくまでも数学的な話であり、例えば乱数のシードを固定した、UUIDを間違えて使いまわしてしまった場合は衝突する。また、衝突する確率は0ではないので、絶対に衝突が許されない場合は別の方法を考える必要がある。