argius note

プログラミング関連

JavaでUUIDを生成する

Java

主キーの話に関連して、UUIDについても――実際は初めてのことばかりでしたが――おさらいをしてみました。

リファレンスなど

まず、基本としてRFC4122の文書があります。
それから、Javaではありませんが、以下の方のエントリが非常に分かりやすくまとめてくださっています。

そして英語のページですがこちらも参考にさせていただきました。

OSSのJava実装。

次に、バージョンとその大雑把な意味を列挙します。

version 1
時刻ベースのUUID
version 2
DCE Security 用？
version 3
名前ベース(MD5)のUUID
version 4
ランダム生成のUUID
version 5
名前ベース(SHA-1)のUUID

バージョン1は、IDを一般公開すると物理アドレスがバレてしまうので念のため注意してください。
バージョン2については、ここで語るには複雑すぎるので今回は省略します。

コアAPIによるUUID生成

Java1.5でjava.util.UUIDクラスが新規に追加されました。このクラスでは、バージョン3とバージョン4のみサポートしています。バージョン3とハッシュアルゴリズムが違うだけと思われるバージョン5も、この時点では仕様に無かったせいなのでしょうか、実装されていません。
バージョン1は、ネットワーク物理アドレスが必要ですが、Java1.5時点では取得することができませんでした。Java1.6ではjava.net.NetworkInterfaceにgetHardwareAddressメソッドが追加され、物理アドレスが取得できるようになりましたが、残念ながらJava1.7になってもバージョン1の生成メソッドは実装されていません。（放っとかれた？）


java.util.UUIDを使って生成するには、それぞれ次のようにします。
バージョン3は、nameUUIDFromBytes(byte[])で生成します。引数には、名前を表すデータのバイト配列を指定します。
実装を見てみると、引数のバイト列のMD5ハッシュ値を算出し、その値にversionとvariantを書きこむようになっています。
バージョン4は、 randomUUID()で生成します。
こちらは、java.security.SecureRandomで16バイトのランダム値を算出し、あとは同様にversionとvariantを書きこむようになっています。


詳しくは、JDKのソースを参照してください。


独自実装してみる

java.util.UUIDでは、実行効率やSerializable対応などで複雑な実装に見えますが、生成ロジックそのものはそれほど複雑では無さそうです。
ここでは、生成ロジックに焦点を絞って、考えてみます。
バージョン2は無しとしますので、残りはバージョン1と5の2種類です。


前準備として、ユーティリティメソッドを作ります。
UUIDの内部表現には、128ビット整数型が無いのでbyte[16]を使います。
toUUIDは、そのbyte[]とバージョン番号を渡すと、java.util.UUIDのインスタンスを生成してくれるファクトリメソッドです。

static UUID toUUID(int version, byte[] bytes) {
    bytes[6] &= 0x0F; // version
    bytes[6] |= (version << 4);
    bytes[8] &= 0x3F; // variant
    bytes[8] |= 0x80;
    return new UUID(toLongAs64bits(bytes, 0), toLongAs64bits(bytes, 8));
}
private static long toLongAs64bits(byte[] bytes, int offset) {
    long bits = 0L;
    for (int i = offset, n = offset + 8; i < n; i++) {
        bits <<= 8;
        bits |= bytes[i] & 0xFF;
    }
    return bits;
}

ここからは、このtoUUIDメソッドに渡すバイト列を生成するロジックだけを考えます。


まずは簡単な方から。
バージョン5は、MD5の代わりにSHA-1を使うだけで良さそうです。

static UUID nameUUIDFromBytesSHA1(byte[] bytes) {
    try {
        return toUUID(5, MessageDigest.getInstance("SHA-1").digest(bytes));
    } catch (NoSuchAlgorithmException ex) {
        throw new RuntimeException(ex);
    }
}

SHA-1そのものに見えます。
実際はversionとvariantフィールドで6ビット使いますので、素のSHA-1よりは「弱い」ハッシュです。



ではバージョン1です。
ここは、"How is an 〜"の"Time-based UUID / GUID"ページを参考に実装しています。

バイト配列への格納の部分だけを書きます。

static UUID timeUUID() {
    byte[] bytes = new byte[16];
    // timestamp
    final long ts = getCurrentTime();
    bytes[0] |= ts >> 24; // time_low
    bytes[1] |= ts >> 16;
    bytes[2] |= ts >> 8;
    bytes[3] |= ts;
    bytes[4] |= ts >> 40; // time_mid
    bytes[5] |= ts >> 32;
    bytes[6] |= (ts >> 56) & 0x0F; // time_hi
    bytes[7] |= ts >> 48;
    // clock ID
    final int clock = getClockId();
    bytes[8] |= (clock >> 8) & 0x3F;
    bytes[9] |= clock;
    // node ID
    System.arraycopy(getNodeId(), 0, bytes, 10, 6);
    return toUUID(1, bytes);
}

timestamp,clockID,nodeIDを払い出す下請けメソッドを実装します。
getCurrentTime()は、System.currentTimeMillis()ではなく、1970年1月1日と1582年10月15日の差分経過「ナノ秒」を返す必要があります。前述の参考ページによると、オフセット値として122192928000000000を使え、とあります。

return time * 10000L + 122192928000000000L;

getClockId()は、参考ページによると、初期値をランダムで生成し、あとはそれを使いまわすようです。timestampが重複した場合はこれをカウントアップするようですが...都合によりパスします。
初期値の生成はSecureRandomを使ってみました。

private static volatile int clockId = -1;

private static int getClockId() {
    if (clockId < 0) {
        SecureRandom ng = new SecureRandom();
        clockId = (int)(ng.nextDouble() * 0x4000);
    }
    return clockId;
}

getNodeId()は、java.net.NetworkInterface#getHardwareAddressを使うので、Java1.6以上が必要です。
ちょっとやっつけですが、最初に6バイトが取得できたものを返します。
最初にも書きましたが、このIDを公開すると、物理アドレスがバレてしまうので注意してください。

private static byte[] getNodeId() {
    try {
        for (Enumeration<NetworkInterface> en = NetworkInterface.getNetworkInterfaces(); en.hasMoreElements();) {
            byte[] addr = en.nextElement().getHardwareAddress();
            if (addr != null && addr.length >= 6) {
                return addr;
            }
        }
        return new byte[6];
    } catch (SocketException ex) {
        throw new RuntimeException(ex);
    }
}

これで一応完成です。
他の言語のUUID1もいくつか試したところ...同じにならないですね。正直、どれが正解かが分かりませんでした。
もし決定版があれば、その仕様に合わせて、細かい部分を微調整すれば良いでしょう。

同日のエントリに関連して...
JavaDBでuuid1()関数が使えるようにするために、このメソッドも作ります。

public static String uuid1() {
    return timeUUID().toString();
}