Help us understand the problem. What is going on with this article?

UUID version1の生成アルゴリズム

More than 3 years have passed since last update.

きっかけ

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

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

UUIDとは?

UUIDはこんなID

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

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

生成アルゴリズム

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はランダム性が高くて、はなからシーケンシャルにならないのは分かってたので。 

takc923
よろしくお願いします。
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした