読者です 読者をやめる 読者になる 読者になる

理系学生日記

おまえはいつまで学生気分なのか

忍者TOOLS

UUID (version 4) における衝突確率を計算する

technology math

UUID というのは、全世界・全時間において一意性を持った識別子とされています。RFC 4122 の言葉を借りると、

A UUID is 128 bits long, and can guarantee uniqueness across space and time

http://www.ietf.org/rfc/rfc4122.txt

とされています。

ですが、128 bit という有限長なんだから 2^{128} 回試行すれば少なくとも 1 回は生成した UUID が衝突するということになります。UUID は万能じゃねーんだ。冷静になれ。
UUID ってのは一意性が「保証」されているわけじゃなく、「実用上は一意と見做せる」ということになります。ですから、衝突する確率というのは 0 にはなりません。じゃぁ、果たしてどのくらいの確率で衝突が発生するのか、計算してみましょう。


計算のまえに結論を言う。n回 UUID を生成したときに衝突が発生する確率は1-\exp\left(-\frac{1}{2^{122}}\frac{n^2}{2}\right) くらい。
試行回数に対する衝突確率の伸びをグラフ化するとこんなかんじ。x 軸はログスケールな。

前提

確率的に計算できそうなの UUID の Version 4 しかなさそうです。Version 4 では、128 bit のうち、122 bit にランダムな数値をセットして UUID とします (残りの 6 bit は固定値です)。

定式化

ここでは、「version 4 の方法で n 回 UUID を生成したとき、それらが 1 つでも衝突してしまう確率 P」を求めます。
"1 つでも"というところからピンと来ると思いますが、これは "衝突が一切発生しない" という事象に対する背反事象になります。このため、まずは衝突が一切発生しない確率をもとめ、それを 1 から引くという考え方をするのが王道です。

計算

順を追って考えましょう。

  1. n回の試行のうちの、最初の 1 回目を考えます。このとき、衝突する UUID は存在しないので、衝突しない確率は 1 (100 %) です。
  2. n回の試行のうちの、2 回目を考えます。このとき、1 回目に生成した UUID と衝突する可能性があります。UUID として発生し得るパターンは 2^{122} パターンあるので、衝突する確率は \frac{1}{2^{122}} になり、衝突しない確率は 1-\frac{1}{2^{122}} になります。
  3. n回の試行のうちの、3 回目を考えます。このとき、1 回目に生成した UUID、あるいは 2 回目に生成した UUID と衝突する可能性があります。したがって、衝突する確率は \frac{2}{2^{122}} になり、衝突しない確率は 1-\frac{2}{2^{122}} になります。
  4. ...
  5. n回の試行のうちの、n 回目を考えます。このとき、1 回目から n-1 回目に生成した UUID と衝突する可能性があります。したがって、衝突する確率は \frac{n-1}{2^{122}} になり、衝突しない確率は 1-\frac{n-1}{2^{122}} になります。

以上から、n 回の試行において衝突が一切発生しない確率は、
1 \cdot \left(1-\frac{1}{2^{122}}\right) \cdot \left(1-\frac{2}{2^{122}}\right) \cdots \left(1-\frac{n-1}{2^{122}}\right)=\prod_{i=1}^{n-1}\left(1-\frac{i}{2^{122}}\right)
ということになります。
従って、衝突が発生する確率 Pは、P=1-\prod_{i=1}^{n-1}\left(1-\frac{i}{2^{122}}\right)です。

近似しましょう

で、こんな式を見せられても、実値を計算するのがマジでダルいですから、近似しましょう。1-\frac{i}{2^{122}}というのを何とかして綺麗にしてやりたい。
ここで、指数関数のテイラー展開を思い出すと、x \ll 1 のとき、e^x \approx 1 + x です。試行回数 n\frac{i}{2^{122}} \ll n となる範囲を考えることにすると、この指数関数のテイラー展開を利用して、1-\frac{i}{2^{122}} \approx \exp\left(-\frac{i}{2^{122}\right) と近似できます。

これを P の式に代入してやると、
P\approx 1-\prod_{i=1}^{n-1}\exp\left(-\frac{i}{2^{122}}\right)=1-\exp\left(-\frac{1}{2^{122}}\sum_{i=1}^{n-1}i\right)
で、おなじみの公式 \sum_{i=1}^{n-1}i=\frac{n(n-1)}{2}を使うと、
P\approx 1-\exp\left(-\frac{1}{2^{122}}\frac{n(n-1)}{2}\right)
が導けます。
n^2 >> nとすれば、P\approx 1-\exp\left(-\frac{1}{2^{122}}\frac{n^2}{2}\right)
になります。かなりきれいになりました。

じゃぁ衝突確率が p になるときの試行回数 n はどのくらいなの

衝突が発生する確率 P p になるための試行回数 n を求めてみましょう。
1-\exp\left(-\frac{1}{2^{122}}\frac{n^2}{2}\right) \approx p n に対して解けば良いです。
これ、わりとかんたんで、n\approx \sqrt{2\cdot 2^{122} \ln{\frac{1}{1-p}}} になります。
これをグラフにしてみると以下のようなかんじになります。

たとえば、衝突確率が 1 % (p=0.01) とすると、必要な試行回数は 3 \times 10^{17} 回くらいですね。