この記事は Gunosy Advent Calendar 2019 の24日目の記事です。昨日の記事は@hongmhoonさんの iOSデバッグ中LLDBコマンドでUIView(Controller)を作って表示してみるでした。

はじめに

広告技術部のGunosyAdsチームの会田(@ryoaita)です。主にGoの広告の配信サーバーの開発を担当しています。

みなさんがお使いのGoのUUIDのライブラリはなんですか？私は最近使っているのは github.com/gofrs/uuid です。ネタに詰まったので、JavaScript向けのSDKで実装したことのあるUUID4の生成処理をGoで実装してみました。

UUID4ってなんだっけ？

UUIDはコンピューターシステム上で一意に識別するためのIDです。UUIDの実体は128ビットの数値です。我々がよく目にする xxxxxxxx-xxxx-xxxx-Nxxx-xxxxxxxxxxxx の形式の文字列のUUIDは128ビットの数値を16進法で表現したものです。現行のUUIDの規格はRFC 4122にまとめられています。

このUUIDにはアルゴリズムの違う複数のバージョンがあり、そのうち乱数によって生成されるバージョンが4、つまりUUID4になります。

UUIDのデータレイアウト

128ビットで表現されるUUIDの各オクテット(バイト)のレイアウトはRFCの4.1.2に記述されています。

   Field                  Data Type     Octet  Note
                                        #

   time_low               unsigned 32   0-3    The low field of the
                          bit integer          timestamp

   time_mid               unsigned 16   4-5    The middle field of the
                          bit integer          timestamp

   time_hi_and_version    unsigned 16   6-7    The high field of the
                          bit integer          timestamp multiplexed
                                               with the version number

   clock_seq_hi_and_rese  unsigned 8    8      The high field of the
   rved                   bit integer          clock sequence
                                               multiplexed with the
                                               variant

   clock_seq_low          unsigned 8    9      The low field of the
                          bit integer          clock sequence

   node                   unsigned 48   10-15  The spatially unique
                          bit integer          node identifier

これをGoの構造体っぽくしたのが下のコードです。

type UUID struct {
    timeLow               uint32
    timeMid               uint16
    timeHiAndVersion      uint16
    ClockSeqHiAndReserved uint8
    ClockSeqLow           uint8
    Node                  [6]uint8
}

しかし、実際にはUUID4では clock_seq_hi_and_reserved と time_hi_and_version の一部のビットしか考慮しません。

UUID4のアルゴリズム

Version4のアルゴリズムはRFCの4.4で説明されています。

4.4.  Algorithms for Creating a UUID from Truly Random or
      Pseudo-Random Numbers

   The version 4 UUID is meant for generating UUIDs from truly-random or
   pseudo-random numbers.

   The algorithm is as follows:

   o  Set the two most significant bits (bits 6 and 7) of the
      clock_seq_hi_and_reserved to zero and one, respectively.

   o  Set the four most significant bits (bits 12 through 15) of the
      time_hi_and_version field to the 4-bit version number from
      Section 4.1.3.

   o  Set all the other bits to randomly (or pseudo-randomly) chosen
      values.

つまり、128ビット(16バイト)の乱数を生成して、6オクテット目の上位4ビットに4.1.3で説明されているバージョン番号を、8オクテット目の上位2ビットに01にセットするとUUID4になります。

4.1.3のバージョンの説明がこちらです。

4.1.3.  Version

   The version number is in the most significant 4 bits of the time
   stamp (bits 4 through 7 of the time_hi_and_version field).

   The following table lists the currently-defined versions for this
   UUID variant.

   Msb0  Msb1  Msb2  Msb3   Version  Description

    0     0     0     1        1     The time-based version
                                     specified in this document.

    0     0     1     0        2     DCE Security version, with
                                     embedded POSIX UIDs.

    0     0     1     1        3     The name-based version
                                     specified in this document
                                     that uses MD5 hashing.

    0     1     0     0        4     The randomly or pseudo-
                                     randomly generated version
                                     specified in this document.

    0     1     0     1        5     The name-based version
                                     specified in this document
                                     that uses SHA-1 hashing.

自分で実装してみる

以上を踏まえてGoに実装したのが下のサンプルです。

package main

import (
    "crypto/rand"
    "encoding/hex"
    "fmt"
    "io"
)

type UUID [16]byte

func (uuid UUID) String() string {
    buf := make([]byte, 36)
    hex.Encode(buf[:8], uuid[:4])
    buf[8] = '-'
    hex.Encode(buf[9:13], uuid[4:6])
    buf[13] = '-'
    hex.Encode(buf[14:18], uuid[6:8])
    buf[18] = '-'
    hex.Encode(buf[19:23], uuid[8:10])
    buf[23] = '-'
    hex.Encode(buf[24:], uuid[10:])
    return string(buf)
}

func NewV4() (UUID, error) {
    var uuid UUID
    if _, err := io.ReadFull(rand.Reader, uuid[:]); err != nil {
        return uuid, err
    }
    uuid[6] = (uuid[6] & 0x0F) | 0x40
    uuid[8] = (uuid[8] & 0x3F) | 0x80
    return uuid, nil
}

func main() {
    uuid, _ := NewV4()
    fmt.Println(uuid)
}

出力結果の例がこちらです。