UUID version1の生成アルゴリズム

きっかけ

友「IDの採番にMySQLのAUTO INCREMENT使ってるけど、インサートしないとIDが作れないから面倒。」
友「UUID v1で採番するのってありだと思うんだけどどうだろう」
俺「けどUUIDってシーケンシャルじゃないからMySQLに格納するなら相性悪いで¹」
友「UUID v1ってタイムスタンプとMACアドレスから生成するからシーケンシャルだと思うけど」
俺「え、そうなん？」

というわけで調べたらシーケンシャルじゃなかったんだけど、せっかく調べたのでUUID v1なIDの作り方をまとめる。

UUIDとは？

UUIDはこんなID

b39fc2e2-1cd6-11e5-9a21-1697f925ec7b

で、形式はこれなんだけど生成方法が5種類あって、よく使われるのはversion1と4。RFC4122で規定されている。このエントリではv1の方の作り方をまとめる²。

生成アルゴリズム

UUIDのフォーマットは4つハイフンで区切られた5つのセクションに分かれるが、これはそれぞれ

• タイムスタンプ(後述)の下位32bit
• タイムスタンプの真ん中の16bit
• versionが4bitとタイムスタンプの上位12bit
• クロックシーケンス16bit(後述)
• MACアドレス48bit

となる。
タイムスタンプは普通のunixtimeではなく、1582/10/15 00:00:00 UTCからの100ナノ秒単位のタイムスタンプ。
クロックシーケンスは同じ時間同じMACアドレスでIDを生成しても別のIDになるためのビット。前回のUUID生成時のタイムスタンプとクロックシーケンスが分かり、かつ現在のタイムスタンプが前回のタイムスタンプより小さい場合にインクリメントする。普通に現在のタイムスタンプが前回より大きかったら前回のクロックシーケンスをそのまま使う。前回のタイムスタンプかクロックシーケンスがわからない場合はランダムな値を使う。

実際に作ってみる

タイムスタンプを計算する。

$ echo "obase = 16; ibase = 10; $(date -d'1582/10/15 00:00:00 UTC' +%s) * -10000000 + ($(date +%s%N) / 100)" | bc
1E51CF5E4A5E520

で、上から12bit, 16bit, 32bitと分割すると1E5 1CF5 E4A5E520。で、バージョンが1なので、UUIDの最初の部分がE4A5E520-1CF5-11E5-...になる。

でクロックシーケンスはとりあえず今は何でもいいから0000にしておく。
実験に使ってるvmのMACアドレスが今08002700bc01。

$ ifconfig | grep HWaddr
eth0      Link encap:Ethernet  HWaddr 08:00:27:00:bc:01

というわけで全部くっつけると、E4A5E520-1CF5-11E5-0000-08002700BC01となる。
uuidgen -tってコマンドでUUID v1の生成が出来るので、タイムスタンプ生成した時間とほぼ同時にid生成すると

$ uuidgen -t
e4a668b8-1cf5-11e5-b07c-08002700bc01

うん、あってる。

1. プライマリーキーにすると強制的にインデックスが作られる。で、インサートされる位置がランダムだとインデックスの更新にコストがかかる。と思ってたけどぐぐったら検証した人がいて環境にもよるんだろうけど思ったほどのパフォーマンス低下じゃないらしい - MySQLテーブルの主キー(Primary Key)をUUIDにした場合のパフォーマンス - Annadel ↩

2. v4はランダム性が高くて、はなからシーケンシャルにならないのは分かってたので。 ↩