UUID4が衝突するのか心配で食事も満足にできず夜も寝ることができません

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

UUID 4の構造

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

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$ は $2^{122}$ 以下の自然数を考える。

$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}$ として次の式を得る。