By | 2017年8月22日

今回はJavascriptでUUIDを生成してサーバに送信したくなったのでJSでUUIDを生成していきたいと思います。

ソースコード

なにはともあれコードから。



UUIDとは

バージョンが幾つかあるのですが、
urn:uuid:f81d4fae-7dec-11d0-a765-00a0c91e6bf6
といった16進数で表した数値です。分散処理システムでもユニークな数値になるように設計されています。

UUIDのバージョン

RFC4122の “4.1.3.Version” の章によると5つのバージョンがあります。
(プロトコルのtime_hi_and_versionの値を変化させます。)

バージョン 概要
1 時刻ベースのバージョン(RFC4122で定義するバージョン)
2 DCEセキュリティーバージョン(POSIX UIDに組み込まれているバージョン)
3 名前ベースをMD5でハッシュしたバージョン
4 疑似ランダムにより生成
5 名前ベースをSHA-1でハッシュ化したバージョン

バージョン1については、定義上は時刻ベースですが並列処理の場合は同時刻も考えられますので、プラスしてMACアドレスの値も含めて計算します。(3ページあたりに書いてあります)

UUIDの衝突確率

UUIDのバージョン4の値が重複する確率ですが、128ビット中バリアントの2ビットとバージョン情報の4ビットの6ビットが固定値なのでそれ以外の122ビットが可変値となります。
つまり

\(
\begin{eqnarray}
\displaystyle P(n) &=& 1 – \prod_{i=1}^{n-1} x_i \left( 1- \frac{i}{2^{122}} \right) \\
& \approx & 1- \exp \left( – \frac{n^{2}}{2^{123}} \right)
\end{eqnarray}
\)

となるんですが、数式を見てもパッとしないです。。
Wikipediaを見てみると \(
2,199,023,255,552 = 2^{41}
\) 回、試行することで \(
0.0000000000005 = (5 × 10^{−13})
\) の確率で重複するということなので、ロト7の1等を2回連続を当てる確率の
\(
\displaystyle \left( \frac{1}{10,295,472} \right) ^2 = 9.4342521 \cdot 10 ^ {-15}
\)
よりは高いですが、重複は現実的でないことがわかります。
(ちなみにunsigned intの最大値が4,294,967,295なので重複よりはデータベースのオートインクリメント溢れを気にしたほうがいいかもしれません)

仕様とか書こうと思ったのですが疲れたのでとりあえずいったんコミット。