UUIDはなぜ、分散環境で好き勝手に生成しても衝突しないのか。RFC4122規格とUUIDの性質。

UUIDとは、Universally Unique Identifierの略で、単純にいえば世界でひとつのIDです。
よくUUIDって言うけど、その正体は何なのか。調べてみました。

PHPのuniqid関数でユニークIDを生成する。
PECLのuuidライブラリを利用する
UUIDとは何なのか
uuid_createのソースコードを覗いてみる
libuuidを使ってみる
UUIDは、どのバージョンが良いのか？
バージョン1とバージョン4の違い
時刻だけでは衝突してしまうので、バージョン1はMACアドレスも利用する
その衝突率とは？
まとまらないまとめ

PHPのuniqid関数でユニークIDを生成する。

PHPには、uniqidという標準関数があります。
PHP: uniqid – Manual
動かしてみます。

echo uniqid();
// => 533530ea695ba

いかにも衝突しそうです。これはいわゆるUUIDではありません。
エントロピーを高める、というオプションがあるので、これを使うと少しはマシになります。

echo uniqid('',true);
// => 5335312f95cc15.22999666

ちなみに連続で生成してみると、ばらつきは極めて小さいです。

53353a2c2104d
53353a2c21085
53353a2c210a6
53353a2c210c0
53353a2c210d4

アプリケーションサーバが分散されていて、それぞれがuniqid関数からIDを生成したら、お互いに衝突してしまいそうです。

PECLのuuidライブラリを利用する

PECLのuuidライブラリを導入することで、もっと品質の高いIDを生成することができます。

PECL :: Package :: uuid
インストールはPECLから簡単にできます。

sudo pecl install uuid

･･･できるはずだったんですが、Mac OS Xで試したらmakeに失敗してしまいました。
そこで「php で uuid を生成する」を参考にソースコードからインストールしました。
uuid_create関数を実行すると、見覚えのある感じの文字列が出てきました。「これぞUUID」という感じです。

echo uuid_create(UUID_TYPE_RANDOM);
// => CDAF9924-EEC8-467A-A822-AA4DB2887814

UUIDとは何なのか

UUIDが見覚えのある文字列であるのは、規格として定義されているからです。RFC 4122に定義されています。

RFC 4122 – A Universally Unique IDentifier (UUID) URN Namespace
これを見ると、UUIDと言っても、バージョンが5種類あるようです。

バージョン	説明
1	時刻とMACアドレスを元にするバージョン
2	DCEセキュリティバージョン
3	バイト列を元にするバージョン。MD5ハッシュを使用
4	ランダム生成するバージョン
5	バイト列を元にするバージョン。SHA-1ハッシュを使用

UUID の Version の見分け方
さきほどのPHPのプログラムは、パラメータにUUID_TYPE_RANDOMを渡しているので、バージョン4と思われます。

uuid_createのソースコードを覗いてみる

ちょっと遊びの領域に突入しますが、uuid_createのソースコードを覗いてみます。一部を抜粋します。

/* {{{ proto string uuid_create([int uuid_type])
  Generate a new UUID */
PHP_FUNCTION(uuid_create)
{
	// ...(略)...
	do {
		uuid_t uuid;
		char uuid_str[37];
		switch(uuid_type) {
		// ...(略)...
		  case UUID_TYPE_DCE_RANDOM:
			uuid_generate_random(uuid);
			break;
		// ...(略)...
		}
		uuid_unparse(uuid, uuid_str);
		RETURN_STRING(uuid_str, 1);
	} while (0);
}
/* }}} uuid_create */

どうやら、PECLのuuidライブラリは、C言語のuuid_generate_random関数をラップしているだけのようです。

libuuidを使ってみる

このuuid_generate_random関数は、libuuidの一部で、Linuxに標準で入っているようです。
uuid_generate_random(3) – Linux man page
試しにC言語でuuid_generate_random関数を呼んでみます。

#include 
#include 
int main(){
        uuid_t uuid;
        char uuid_str[37];
        uuid_generate_random(uuid);
        uuid_unparse(uuid, uuid_str);
        printf("uuid: %s\n", uuid_str);
}

実行すると、UUIDが取得できます。

$ cc uuid.c && ./a.out
uuid: 6FBDFD4D-AF49-4905-81CA-1B8220479F55

UUIDは、どのバージョンが良いのか？

では、5つあるバージョンのうち、どれを使うのが良いのでしょうか？
libuuidには、バージョン4で生成するuuid_generate_random関数の他に、バージョン1で生成するuuid_generate_time関数があるので、おそらくこのどちらかが有力だと思われます。

バージョン1とバージョン4の違い

では、「バージョン1とバージョン4の違いは？」というと、バージョン4が乱数から生成されるのに対して、バージョン1が時刻から生成されることです。
バージョン1で、間髪入れずにUUIDを生成してみると、似たような文字列が生成されます。時刻を元にしているので、先に紹介したPHPのuniqidと同様に似たような値になるのですね。

2DA68D16-B656-11E3-961E-20C9D07FF9F3
2DA68DA2-B656-11E3-961E-20C9D07FF9F3
2DA68DD4-B656-11E3-961E-20C9D07FF9F3
2DA68DFC-B656-11E3-961E-20C9D07FF9F3

一方のバージョン4は、乱数を元にUUIDを生成するので、連続で生成してもバラバラの値が生成されます。

25233C75-939B-47F7-B714-49AB00806564
E80ABA24-C6AE-4DCC-B131-B5EE01B31B07
1EEFFFF2-57CB-46A1-BAE6-C22618B21F3A
2EF69AAB-0926-4EEB-A400-197456D64107

文字列的な意味でどちらが良いかはサービスによりそうです。あとで生成順にソートしたいか、バラバラの方が良いか、です。

時刻だけでは衝突してしまうので、バージョン1はMACアドレスも利用する

時刻だけでUUIDを生成すると、厳密に同じ時刻にUUIDが生成されると値が衝突してしまいます。
単一のホストで順次的にUUIDを生成していれば、厳密に時刻が一致することはありませんが、複数のホストで並列的にUUIDを生成していると、時刻が一致してしまうことは考えられます。
そのような状況のために、バージョン1は、MACアドレスを利用することで、分散環境でのUUIDの衝突を回避しています。

// ホスト A
83BCDA84-B65B-11E3-A0A8-20C9D07FF9F3
83BDF644-B65B-11E3-9A2C-20C9D07FF9F3
...
// ホスト B
843E120C-B65B-11E3-8197-3C07542E7A63
843EA136-B65B-11E3-B318-3C07542E7A63
...

このように、同一のホストで生成された値は似たような値が並びますが、別のホストで生成された値は後半のブロックがまったく異なります。これがMACアドレスに当たります。
MACアドレスを知られたくない場合には、代わりにホストごとに乱数を設定しておくこともできるようです。
永久に使える自分だけのURIを作る。

その衝突率とは？

UUIDは、衝突を回避するための中央管理がありません。特にバージョン4は、ランダム生成なので、衝突してしまうような気もしないでもないです。
調べてみたら、UUIDの重複について言及されているブログがありました。「1兆個のUUIDを生成しても、生成したUUIDが重複する確率は、隕石が頭に降ってくる確率より低い」ということなので、相当低そうです･･･。
UUID の重複する可能性
ちなみに、このlibuuidによる、バージョン4のUUIDの生成は、Linuxの擬似乱数生成器(/dev/urandom)に依存しているそうです。
そうすると、この乱数生成の性能に依存してきます。
Linux、「/dev/random」「/dev/urandom」とはなんぞや？