Reveal My Ignorance Blog by Eisuke Kuwahata

ランダムに生成したIDが衝突する確率の議論

4 min read

「ランダムなIDをあるパターンに従って生成するとき、どう設計すべきか？」という質問があったので技術的な側面と数学的な側面で説明してみよう。

技術的な側面

そもそも衝突したくないなら典型的な方法として「時間の情報を含めてIDを生成する」という方法があり、 UUIDv1にもタイムスタンプが使われているし、 ULID という選択肢もある。

しかし、UUIDv1はMACアドレスに依存してしまう設計なので現在はほぼ使われていないし、ULIDは最初の10桁がタイムスタンプ情報なので短く詰めることでランダム性を失ったり、IDそのものに特定の構造を定義したいという場合はそのままでは使えない。

今回の質問でも特定の構造が指定された場合の話だったので、シンプルにランダム生成することを前提とした。

もし衝突したら何が問題か

IDの生成直後にすぐDBに保存する仕組みであれば、DBに登録済みか確認し重複している場合には再生成すれば実用上は問題なく使える。 （もちろん、衝突が何度も発生するような状況ではパフォーマンスの問題に発展してしまうが）

それでも問題になるのは次のようなケースが考えられる。

  • 一時的にIDを生成しユーザーがデータを入力したタイミングでDBに保存するため、生成時には重複が検知できない
  • 多数の同時リクエストや冗長構成によって、ほぼ同時にID生成される可能性が高く、DBに保存されていたとして生成時の重複が検知できない可能性がある
    • かといってINSERT時のテーブルロックなどをしてしまうとパフォーマンス上の問題となってしまう

そのような状況の解決を図ったID生成方法の実例に Twitter IDs(Snowflake) がある。 大規模なサービスではID生成だけでもミッションクリティカルな機能になったりもする。

数学的な側面

\(\)

数学的には「誕生日のパラドックス」が有名である。

\( M \) を生成可能なパターン数とする。 例えば 8 桁の数字でランダムな値を作る場合、00000000 から 99999999 までの範囲で \(10^8\) 個生成可能である。

このうち、 \(n\) 回ランダムに生成したとき「一度でも衝突が発生する確率」を考える。 「\( n \) 回目で発生する確率」と読み間違えないように注意してほしい。

余事象の確率で考える

「\(n\) 回生成したときに一度でも衝突が発生する」ということを考えたいとき、「\(n\) 回生成しても一度も衝突が発生しなかった場合」の余事象を考えれば良い。

「全く衝突が発生しなかった場合」の反対なので、「少なくとも一度は衝突が発生している場合」ということになる。

「\(n\) 回生成しても一度も衝突が発生しない確率 \(P_\text{nc}(n)\)」を求めよう。

\(n=1\) ならば、 \(M\)個中どれが選ばれても衝突することがないので、 \(\frac{M}{M} = 1\) (100%)である。

次に \(n=2\) ならば、 \(M\)個中最初に選んだものを除く \(M-1\) 個から選ばれても衝突することがないので、 \(\frac{M}{M} \frac{M-1}{M}\) である。

このようにして、衝突が発生しない確率が次のように計算できる

$$ P_{\text{nc}}(n) = \frac{M}{M}\frac{M-1}{M} \dots \frac{M-(n-1)}{M} = \frac{M!}{M^n (M-n)!} $$

つまり衝突が発生する確率は全確率 1 から発生しない確率を引いたものとなる。

$$ P_{\text{c}}(n) = 1 - P_{\text{nc}}(n) = 1 - \frac{M!}{M^n (M-n)!} $$

数値計算してみる

Node.js で次のようなコードを実行してみる

const M = 10**8;
let p_nc = 1.0;
let n = 1;

while (p_nc > 0.5) {
  n += 1;
  p_nc *= (M - (n-1)) / M;
}

console.log(`n = ${n}`);

数値計算上の誤差はあるだろうが、計算結果は n = 11775 となる。 上記の「8桁の数字」で生成されるIDでは、11,775回生成するだけで衝突が発生する確率が50%を超える結果となる。

では、実際に生成してみて衝突が発生するまでの生成回数を調べてみよう。100回試してみて、その平均値を取ってみる。

const M = 10**8;

function collisionTest() {
  let memo = {};
  let generated = Math.ceil(Math.random() * M);
  while (!memo[generated]) {
    memo[generated] = true;
    generated = Math.ceil(Math.random() * M);
  }
  return Object.keys(memo).length;
}

const trial = 100;
const results = [...Array(trial).keys()].map(() => collisionTest());
const average = results.reduce((a,b) => a+b) * 1.0 / trial;
console.log(`average = ${average}`);

average = 11866.35 という結果になる。 ランダムなので実行ごとにばらつきはあるが、平均値が上記の50%の確率で衝突する値に近いことがわかる。

実用的な範囲は？

実用性を考えると、衝突確率が1%未満である安全性の高い範囲を考えておきたい。 p_nc > 0.99 と置き換えればその値は計算でき、 n = 1419 である。 設計するサービスが1,000個未満のIDで運用できるなら衝突する可能性はかなり少ないだろうが、それを超え始めると度々衝突が発生することも考えられるため、サービスのスケールを見積もりながら安全な範囲を計算すると良い。

一例として、先程の確率計算を関数化したものを使ってみる。

/**
 * max_ids: 生成可能なIDの数
 * p_under: 衝突確率がこれ以下である最大値を求める (0以上1未満の値を指定)
 */
function collisionSafe(max_ids, p_under) {
  let p_nc = 1.0;
  let n = 1;

  while (p_nc > 1 - p_under) {
    n += 1;
    p_nc *= (max_ids - (n-1)) / max_ids;
  }

  return n;
}

collisionSafe(10**8, 0.01);  // => 1419
collisionSafe(10**9, 0.01);  // => 4484
collisionSafe(10**10, 0.01); // => 14179

まとめ

「誕生日のパラドックス」の解説にもあるように、「思ったより少ない生成個数で衝突が発生しやすい」ということを意識して、ランダムなIDを生成すると良い。