UUID4が衝突するのか心配で食事も満足にできず夜も寝ることができません
UUID(Universally Unique Identifier)とは汎用識別子であり、
ISO/IEC 11578:1996や、
IETFのRFC 4122で仕様が公開されている。
UUID 4の構造
RFC 4122ではいくつかバージョンが定められているが、そのうちバージョン4は122ビットの乱数から生成される。
実際は、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を識別子として使うならば、当然それらが被らない、衝突しないことが期待される。
今回は 
個のUUID 4が生成された場合に衝突する確率を見積もるのが目的である。
の場合
UUID 4を
個以上生成した場合、UUID 4の全パターンは
であるので、確率1で衝突する。
このような論法を鳩の巣原理という。
鳩の巣原理は一見単純ながら面白い定理を証明できたりするのだが本題から外れるので割愛する。
以降、 は以下の自然数を考える。
の場合
衝突する確率を直接求めるのではなく、余事象である衝突しない確率を考える。
まず、2個のUUID 4を生成してその2つが衝突しない確率は
である。
次に3個目のUUID 4を生成していずれの生成したUUID 4と衝突しない確率は
である。
この論法を繰り返すと、 個のUUID 4が衝突しない確率
として次の式を得る。
\begin{align*}
p_0 = \prod^{N-1}_{k=1}\left(1-\frac{k}{2^{122}}\right).
\end{align*}
よって、 個のUUID 4が生成された場合に衝突する確率
は次の式となる。
\begin{align*}
p = 1 - \prod^{N-1}_{k=1}\left(1-\frac{k}{2^{122}}\right).
\end{align*}
めでたし、めでたし。
確率の評価
衝突する確率を計算できたとは言え、これでは計算が大変である。
そこで、適当な不等式で評価してみよう。
補題: 任意の実数
において
が成り立つ。
証明: 
として微分して増減を調べる。
この不等式を使って衝突する確率を評価してみる。
\begin{align*}
p \geq 1 - \prod^{N-1}_{k=1}\left(e^{-\frac{k}{2^{122}}}\right).
\end{align*}
指数法則より、
\begin{align*}
p \geq 1 - e^{\left(\sum^{N-1}_{k=1} -\frac{k}{2^{122}}\right)}.
\end{align*}
みんな大好き
の計算をすると、
\begin{align*}
p \geq 1 - e^{-\frac{N(N-1)}{2\times 2^{122}}}.
\end{align*}
これで衝突する確率を下から押さえることができた。
例えば、
とすると、
となり、非常に小さい値となる。
本当は指数函数を多項式で上から押さえたいのだが、よい方法がない。
結論
UUID 4が衝突する確率は非常に小さく、杞憂である。
ただし、これはあくまでも数学的な話であり、例えば乱数のシードを固定した、UUIDを間違えて使いまわしてしまった場合は衝突する。
また、衝突する確率は0ではないので、絶対に衝突が許されない場合は別の方法を考える必要がある。
