Python
UUID
iRidgeDay 5

UUID 4が衝突する確率を見積もる

UUID 4の構造

UUID(Universally Unique Identifier)とは汎用識別子であり、ISO/IEC 11578:1996や、IETFRFC 4122で仕様が公開されている。RFC 4122ではいくつかバージョンが定められているが、そのうちバージョン4は122ビットの乱数から生成される。

詳しくUUID 4の構造は以下の通りである。UUIDのフォーマットから引用した。

        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)                            |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

上記の構造において、タイムスタンプやクロックシーケンス、ノードの値をすべて真の乱数か疑似乱数で埋めたものがUUIDバージョン4である。

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は衝突するのか?

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

  • $ N \geq 2^{122} + 1 $ の場合

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

  • $N \le 2^{122}$ の場合

衝突する確率を直接求めるのではなく、余事象である衝突しない確率を考える。まず、2個のUUID 4を生成してその2つが衝突しない確率は$\frac{2^{122}-1}{2^{122}}$である。次に3個目のUUID 4を生成していずれの生成したUUID 4と衝突しない確率は$\frac{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 \leq e^{t}$が成り立つ。

証明: $(t) = e^{t} - (1 + t)$として微分して増減を調べる。

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

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

指数法則より、

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

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

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

これで衝突する確率を下から押さえることができた。

例えば、$N = 10^{10}$とすると、$p \geq 9.4 \times 10^{-18}$となり、非常に小さい値となる。
多項式を下から評価しているので、評価した値よりも確率が大きくなる可能性はあるが、$t \sim 0$の場合は$e^{t} \sim 1 + t$とみなせるのでそこまで悪くはない評価だと思う。

結論

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