daily dayflower

2009-03-06

UUID と Perl について

UUID がどういうものであるか,とか UUID の表現形については省略します。

が参考になるかと。

UUID の仕様として RFC 4122 を参照しました*1。なのでより細かいことについては原文を参照してください。策定されるまでにいろいろ経緯があるのですが,そのへんは

に譲ります。

UUID の構造

UUID の内部構造をおおまかに表すと以下のようになります。

variant
2 bit (3 bit)
version
4 bit
time
60 bit
clock_seq
14 bit (13 bit)
node
48 bit

実際には variant フィールドは clock_seq フィールドのオクテットの中に埋め込まれていますし,version フィールドは time フィールドのオクテットのなかに埋め込まれているのですが,各情報の情報量を純粋にビット数で表現すると上記のようになるということです。

variantRFC 4122(ないし元になった OSF DCE 1.1)UUID では 10b に固定です。また Microsoft GUID の場合 110b に固定です(それゆえ上記で variant の bit 数を二通り書きました)。

version というのは,UUID 仕様のバージョン,というより,どのようなアルゴリズムで UUID を算出するのか,ということを示します。RFC 4122 UUID では Version 1 〜 5 までの5種類の算出アルゴリズムが規定されています。

VersionDescription
1時刻とノードをベースに一意値を算出
2POSIX UID を埋め込んだ DCE Security バージョン*2
3ある名前空間に属するユニークな値から MD5 により一意値を算出
4完全ランダム
5ある名前空間に属するユニークな値から SHA-1 により一意値を算出

俗に UUID は 128 bit の空間があるので〜云々いわれていますが,RFC 4122 UUID に限っていえば,あるバージョンにつき 122 bit の variation しかないことになります(variantversion で最低 6 bit を要するので)。

time, clock_seq, node については,まぁ名前から内容を推察できるところでもあるのですが,実際には名前どおりの使われ方をするとは限りません。詳しくは各 version の説明で。

v1 (時刻とノードをベースに一意値を算出)

生成時刻と生成したマシンのノードID(MAC アドレス)を元に UUID を算出します。ので生成した UUID に重複がないことが(ほぼ)保証されます。

variant
2 bit (10b; fixed)
version
4 bit (0001b; fixed)
time
60 bit
clock_seq
14 bit
node
48 bit

timeUTC1582年10月15日1582年1月1日0時0分0秒からの経過時間を100ナノ秒単位でカウントした値になります。つまり,その規定日時からの経過ナノ秒を100で割った値になります。

clock_seq は,まったく同じ時刻に生成した UUID が重複してしまうのを避けるべく用意されたフィールドです。と書くと100ナノ秒単位の時刻で同じ時刻はまずないんじゃないかと思いますが,たとえばシステムの都合でシステム時刻が遡ってしまった場合に同じ時刻に生成される可能性があります。なので,UUID 生成系は最初期に乱数clock_seq初期化し,もし時刻が遡った場合は clock_seq を単調増加させる,などのように運用するべきだと仕様に書いてあります*3

node は一般的には UUID を生成したマシンのネットワークカードの MAC アドレスを使用します。ですが,UUID をみると逆にそれを生成したマシンの MAC アドレスがわかってしまうので,セキュリティ上「いまいちだなぁ」という場合*4,かわりにランダムなマルチキャスト MAC アドレスを使用することもできます。

ランダムなマルチキャスト MAC アドレスって何か難しそうですが,単純に最上位ビットが 1 でその他のビットフィールドがランダムなものです。つまり,1b + random 47 bit sequence です。47 bit の乱数値としては乱数値をそのまま利用してもよいですし,後述の Data::UUID でのアルゴリズムなどを利用することもできます。

利点
  • 時刻とマシン*5につき一意に UUID が定まるので
    • 複数のマシンで同時に UUID を生成したとしても一意性を保証できる
      • ただしランダムマルチキャスト MAC アドレスの場合を除く
      • 複数のマシン間で一意性を保証できるというのはなかなかのメリット
    • 同一のマシンで同じ UUID が生成されることはまずない
欠点
  • 算出過程が可逆でありランダム性が少ないので,一度 UUID を取得した場合,その系での他の UUID を推測可能になる*6
  • 西暦5200年あたりで time フィールドがオーバーフローする
    • その頃まで今生成した UUID を使っているのでしょうか……
    • なお約3600年くらいの周期でラップアラウンドします
    • 仮にラップアラウンドで利用するとして3600年というのは長いとみるか短いとみるか
    • てか version にゆとりがあるので,その頃までによりよいアルゴリズムversion が規定されることに期待しましょう

v2 (POSIX UID を埋め込んだ DCE Security バージョン)

RFC 4122 に詳述されておらず,現在ではあまり使われていないので省略します。

v3 (名前空間とユニークな値から MD5 により一意値を算出)

UUID といえば「とりあえずユニークな ID が欲しい」というときに利用するイメージですが,v3 UUID(と後述する v5 UUID)はちと違います。

v3 UUID の場合,あるタイプの「値」に紐づけするための ID が欲しいときに利用します。たとえば以下のような感じ。

namespacenameUUID
DNSfoo.example.com144f6edc-d2bf-3866-a7c5-e51ac983cbcb
DNSbar.example.com407f4389-4d81-3274-b641-873cef95d948
URLhttp://example.com/foo8f932a5b-ab21-3f60-b1e7-4ec6da1ff1ec
URLhttp://example.com/bara51e9810-1653-3040-a007-47daaa5af9c4

おもしろい?のは,上記の UUID を全世界の誰が生成したとしても,同じ name に対応する UUID は同じ UUID になるところです*7

たとえばウェブクローラを開発していて,ある URL に対応するデータを格納したい場合,ただの AUTO INCREMENT な整数値ではなくこの v3 UUID を ID として利用するという用途が考えられます*8

後述するように OID や X.500 DN などの namespace が規定されているので,ネットワーク管理に用いることを念頭においていたのではないでしょうか。

UUID の構造の内訳は以下のようになります。

variant
2 bit (10b; fixed)
version
4 bit (0011b; fixed)
hashed_value
128 bit (122 bit)

hashed_valueMD5 によるハッシュ値なのでそのままだと 128 bit の幅を持ちます。実際には variantversion を格納しなくてはいけないので,おのおの該当部分が定数値で上書きされます。なので実質 122 bit です。

ハッシュ演算に用いるデータソースは

  • namespace UUID (128 bit; 16 octets) + name (variable octets)

です。

namespace UUID とは利用する name のタイプを示すものです。下記の4種が RFC 4122 で予約されています。

  • DNS (6ba7b810-9dad-11d1-80b4-00c04fd430c8)
  • URL (6ba7b811-9dad-11d1-80b4-00c04fd430c8)
  • OID (6ba7b812-9dad-11d1-80b4-00c04fd430c8)
  • X.500 DN (6ba7b814-9dad-11d1-80b4-00c04fd430c8)

独自の namespace(たとえばメールアドレスなど)に属する値を符号化したい場合,上記と重複しない UUID を生成してそれを使えばよいでしょう。

利点と欠点
  • v1 と用途が異なるので同じ基準で利点欠点をあげることはできません
  • ただ,namespace とその namespace 下の name に対して一意に UUID が定まるというのは利点といえるでしょう
    • たとえばクローリングを分散処理で行っている際に,異なるリソースに対する UUID が(あまり)衝突しない,など

余談(予約済み namespace UUID について)

定義済みの namespace UUID を見ると,純然たる v1 UUID です。もうちょっと特殊な値を用意するかと思いましたが,意外に実直ですね。自分の決めたことはきちんと守る,みたいな。

node ID によると,生成したマシン(で使われている NIC)のベンダDELL のようです。

time は1998年あたりですが具体的な月日は算出していません。だってオリジンが1582年とかなんだもん。

v4 (完全ランダム)

v1 UUID では,時刻とマシンノード ID をもとに生成しているので,そういった private な情報が露出すると困る場合があります。またある時点・場所における UUID を類推することも可能であり,セキュリティリスクとなりえます。

一方,v4 では完全に乱数値で UUID を算出するので,そのようなケースにも用いることができます。

variant
2 bit (10b; fixed)
version
4 bit (0100b; fixed)
random_seq
122 bit

完全にランダムとはいっても,前述のように variantversion は固定値なので,残る 122 bit がランダムな値になります。

UUID generator によっては,これら固定の 6bit のフィールドについてもランダムなものとするインプリメントもあるようです(イクナイ!)。

利点
欠点
  • 他のマシンの生成した UUID と衝突しうる。
  • 乱数の質が悪い場合,自分の生成した UUID とすら衝突しうる
    • 自分がそれまでに生成した UUID を全部おぼえておいて除外すればいいんですが,まぁそこまでやる実装もないでしょう

v5 (名前空間とユニークな値から SHA-1 により一意値を算出)

v3 と同じなので解説は省略します。ハッシュアルゴリズムとして MD5 の代わりに SHA-1 を使います。それ(と version フィールド)以外は v3 とまったく同じ。

variant
2bit (10b; fixed)
version
4bit (0101b; fixed)
hashed_value
128bit (122bit)
利点と欠点
  • 利点と欠点も省略
  • MD5 より SHA-1 のほうが安全。が解読してどうこうする人がいるのか?
  • とはいうもののハッシュ関数が違うだけでアルゴリズムは v3 と同じなので backward compatibility を考慮しないのならこちらを利用するのが prefer だそうです(そりゃそうですね)

nil UUID

特殊な UUID として nil UUID というものがあらかじめ定義されています。これは全フィールドが 0 のものです。

  • 00000000-0000-0000-0000-000000000000

全フィールドが 0 なので,あらゆる variant / version の UUID とは衝突しません。

とくに RFC 4122 で用途が定められているわけではありませんが,たとえば UUID が存在しないこと(NULL のようなもの)として使うことが考えられるでしょう。

で,Perl のどのモジュールが UUID をサポートしているの?

UUID をサポートするモジュールは結構いろいろあるのですが,その中からわりと「独立」したものを選んでみました。

モジュールv1v2v3v4v5備考
Data::UUID×××一番広く使われているが v4 をサポートしてほしかった
UUID××××e2fsprogs の libuuid ベース
UUID::Random××××完全に全フィールドランダムなので v4 とはいえない
Data::UUID::LibUUID××UUID よりまじめに書いてあるけど CPAN Testers Report がちょっと微妙なことに
OSSP::uuid×実装としては一番まともっぽいが CPAN から入れられない
APR::UUID××××mod_perl に同梱なので単独では入れられない?; これも独自ランダムくさい

以下,この中からいくつかのモジュールをピックアップして説明します。

Data::UUID

Paul J. Leach and Rich Salz による Internet Draft "UUIDs and GUIDs" をもとに,XS コードを独自実装しています。

CPAN モジュールとしてデファクトスタンダードといえるのではないかと思いますが,version 1 と 3 のみサポートしています。ですが,アップデートの頻度も結構ぼちぼちですし,いつかは RFC 4122 ベースになってくれるんじゃないのかなぁ。

なお version 1 の node として MAC アドレスではなく,hostid や hostname そして現在時刻を元に MD5 ハッシュを計算し,その一部を利用しています(なので異なるマシン間で UUID が重複しにくいです)。これは PerlMAC アドレスを取得するのが面倒という理由もありますが,ネットワークにつながれていないなど MAC アドレスを取得できない状況で node ID を算出するための次善策として RFC 4122 の 4.5 節でも述べられている手法です。

あと今使ってみて気づいたけど,NameSpace_DNS などの定数はデフォルトエクスポートされますね。:all なんて export tag も定義されていません。なので POD の DESCRIPTION の Examples は現在間違ってます。

利点
  • 広く使われている
欠点
  • v4 をサポートしていない
  • v1 を真面目にインプリメントしているので,clock_seq 等を外部ファイル(デフォルト/tmp 下)に保持している
    • そのこと自体がイヤな場合もあるかも
    • 複数プロセスから同時にアクセスした場合どうなのか?

Data::UUID::LibUUID

e2fsprogs に同梱されている libuuid をリンクしているコードです。

なぜ ext2 fs 用のツールに UUID のライブラリなの?って感じですが,ext2 fs ではパーティションのラベルとして UUID も使えるんです*9。ので,UUID を利用するために(おそらく当時まともなライブラリがなかったので)自力でライブラリを書いたのでしょう。必要な機能に比べて用意されている API がずいぶんがんばっちゃってる感じですが。

コアライブラリ自体は libuuid の changelog を見た感じだと結構まめにメンテナンスされているようです。かつ,結構クロスプラットフォームみたいです。

なお UUID という CPAN モジュールも同じように e2fsprogs 由来の libuuid を利用していますが,Makefile.PL がややなげやり(というかライブラリがあること前提)ですし,CPAN Testers Report があまりあつまっていません。きちんとリリースされてないのかな。

利点
  • Data::UUID よりサポートしている version が多い
    • v4 をサポートしている
欠点
  • v3 をサポートしていない
  • e2fsprogs がポートされていない環境では動かせない
  • Perl の世界ではいまいちメジャーじゃない感じ?

OSSP::uuid

ライブラリの実装としては OSSP: OSSP uuid にあります。Perl を含む各種言語へのバインディングも同梱されています。同梱されている分,逆に CPAN には登録されていません。その代わり,EPEL に Perl バインディング含め登録されています(つまり Fedora にもあるってことかな)。Ubuntuapt にも登録されています。

RFC 4122 等の各種仕様をもとにして開発されており,UUID 系ライブラリプロジェクトとしてはかなり鮮度が高いのではないでしょうか*10ライブラリ本体の著者は OpenSSL などで有名な Ralf S. Engelschall です。

利点
  • サポートされているバージョンが多い
  • v1 では node として MAC アドレスとランダムマルチキャスト MAC アドレスを利用可能
欠点

Perl モジュールについて考えたこと

*1:実際には UUID の仕様というより,UUID の URN namespace についての仕様――つまり UUID を URN として使う場合の仕様――なのですが,UUID の定義についても詳述されています。

*2:自分でも何を書いているかよくわかりませんが,後述するようにこのバージョンについては省略します

*3:それを文字通りそのままインプリメントするかどうかは別ですが。少なくとも Data::UUID ではそのようにインプリメントしてあります。

*4:たとえば同一ネットワークでその MAC アドレスのマシンになりすます場合とかですかねぇ……でも同一ネットワークにいるなら他マシンの MAC アドレスくらい知れる気もしますが。

*5MAC アドレス自体が 48 bit しかなく同一 OUI につき16,777,216個しか発行できないので,いい加減なベンダだと適当に MAC アドレスを発行している可能性もありそうですが。

*6:まぁしないと思いますが,v1 UUID をセッション ID に使うと,他のセッションの ID を簡単に推測できるので,セッションハイジャックが簡単になります。

*7:ただしこの例は Data::UUID で生成したので,Data::UUID のインプリメントが間違っていなければ,ですが。

*8:ただしハッシュ関数を利用しているので衝突が発生しえます。現実問題として v3 UUID を URL にたいするユニーク ID として用いるのはやめたほうがよいでしょう

*9:これにより複数マシンの複数ディスクのパーティションを一意に特定できる。なのでディスクを付け替えたとしても意図されないマウントがおきたりしない。

*10:ただし私見です。客観的に見ると e2fsprogs の libuuid のほうが de-facto standard になっている気もします

*11:drop-in-replacement で使えるようにという意図?

norachlonorachlo 2012/10/11 11:17 UUIDを調べていて辿り着きました。とても参考になります。

ところでリンク先のRFC4122では、バージョン1の経過時間を
1582年10月15日からとするように記述してあるように見えるのですが。。。
勘違いだったらすいません。

dayflowerdayflower 2012/10/11 11:35 まったくもってそのとおりですね。お恥ずかしい。ご指摘ありがとうございます。修正しました。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証