JavaScriptを有効にしてください

UUID v4の衝突実験をした話

 ·  ☕ 1 分で読めます

みなさんユニークな ID を振りたいときどうしていますか?

プライベートで VR に最適化したネットワーク同期エンジンを作っていて,そのエンジンで使うオブジェクトの識別子に UUID v4 を検討していました.

しかしながら UUID v4 は非常に確率が低いものの衝突する可能性があります.

そのためサーバーのメモリが許す限りの UUID を生成して衝突するかを実験してみました.

以下のリポジトリに実際の実験に使ったコードをおいておきます.

https://github.com/bootjp/collision_experiment_uuidv4

環境

  • CPU : Xeon E5-2620 2.0GHz * 2
  • MEM : DDR3-ECC 48GB

結果

1
2
3
4
5
6
$ go run run.go > /tmp/uuid.txt &
# OOM Killer が発動するか実行終了まで待つ
$ cat /tmp/uuid.txt | wc -l
436208281
[email protected]:~$ ls -lah /tmp/uuid.txt
-rw-rw-r-- 1 bootjp bootjp 16G Mar 31 15:17 /tmp/uuid.txt

436,208,281(4 億)の UUID を生成して重複はありませんでした.

4 億個ほどの UUID であれば 3 回実行しても重複は確認できませんでした.

まとめ

すくなくとも 4 億程度であれば衝突の可能性は大丈夫そう

Map を使っているためか,メモリ効率が悪く 4 億個までしか検証できませんでした.
これは次の課題としてロックをとった Slice で再度検証してみます.

***

共有

bootjp / ぶーと
著者
ミドルウェアエンジニア / 7年後に分散データベース研究の世界に貢献することを目指して


目次