この記事は Go3 Advent Calendar 2017 の6日目の記事です。

はじめに

DBに保存するデータのIDやセッションIDなどの一意なIDを、分散したWebアプリ上で発行することで、発行処理をスケールさせたいといったケースがあります。
そういったケースでは、UUIDやSnowflakeなどの使用例が良く紹介されています。
この記事では、Go製のライブラリで、Goアプリから簡単に使用できるID Generatorである「xid」について紹介します。
このxidは自分が仕事で開発しているシステムでも採用しています。

GitHubリポジトリ: https://github.com/rs/xid

xidについて

詳しくはGitHubのREADMEの書かれていますが、その中から一部抜粋して紹介します。

binaryのformat

全体で12bytesで、先頭から以下のように構成されています。

4bytes: Unix timestamp (秒単位)
3bytes: ホストの識別子
2bytes: プロセスID
3bytes: ランダムな値からスタートしたカウンタの値

生成される文字列

20文字のlower caseの英数字。([0-9a-v]{20})

例: b8hpcg8hv3amvi9dol0g

特徴

サイズがUUIDより小さく、Snowflakeより大きい
設定が不要
生成されるバイナリや文字列がsortable
ホスト/プロセスごとに秒間16,777,216 (24 bits)のユニークなIDを発行可能
Lockを使用しない

など

使い方

コード:

package main

import (
    "fmt"

    "github.com/rs/xid"
)

func main() {
    // idを生成
    guid := xid.New()
    fmt.Println(guid.String())

    // binaryの各partの情報
    machine := guid.Machine()
    pid := guid.Pid()
    time := guid.Time()
    counter := guid.Counter()
    fmt.Printf("machine: %v, pid: %v, time: %v, counter: %v\n", machine, pid, time, counter)
}

実行結果:

b8hpcg8hv3amvi9dol0g
machine: [17 248 213], pid: 28617, time: 2017-12-03 15:14:25 +0900 JST, counter: 2999617

xidの実装を見てみる

まず、ID型が12bytesの配列として定義されています。

// ID represents a unique request id
type ID [rawLen]byte

const rawLen = 12 // binary raw len

新しいIDを生成する部分は以下の New() のようになっており、先頭から各part (unix timestamp, machineID, pid, counter) の値を埋めていることがわかります。

// objectIDCounter is atomically incremented when generating a new ObjectId
// using NewObjectId() function. It's used as a counter part of an id.
// This id is initialized with a random value.
var objectIDCounter = randInt()

// machineId stores machine id generated once and used in subsequent calls
// to NewObjectId function.
var machineID = readMachineID()

// pid stores the current process id
var pid = os.Getpid()

// New generates a globaly unique ID
func New() ID {
    var id ID
    // Timestamp, 4 bytes, big endian
    binary.BigEndian.PutUint32(id[:], uint32(time.Now().Unix()))
    // Machine, first 3 bytes of md5(hostname)
    id[4] = machineID[0]
    id[5] = machineID[1]
    id[6] = machineID[2]
    // Pid, 2 bytes, specs don't specify endianness, but we use big endian.
    id[7] = byte(pid >> 8)
    id[8] = byte(pid)
    // Increment, 3 bytes, big endian
    i := atomic.AddUint32(&objectIDCounter, 1)
    id[9] = byte(i >> 16)
    id[10] = byte(i >> 8)
    id[11] = byte(i)
    return id
}

以下の String() が、文字列表現を取得する部分です。
custom versionのbase32 encodingを使用して、12bytesの配列 (ID) から20文字の文字列表現を生成しています。

const (
    encodedLen = 20 // string encoded len

    // encoding stores a custom version of the base32 encoding with lower case letters.
    encoding = "0123456789abcdefghijklmnopqrstuv"
)

// String returns a base32 hex lowercased with no padding representation of the id (char set is 0-9, a-v).
func (id ID) String() string {
    text := make([]byte, encodedLen)
    encode(text, id[:])
    return string(text)
}

// encode by unrolling the stdlib base32 algorithm + removing all safe checks
func encode(dst, id []byte) {
    dst[0] = encoding[id[0]>>3]
    dst[1] = encoding[(id[1]>>6)&0x1F|(id[0]<<2)&0x1F]
    dst[2] = encoding[(id[1]>>1)&0x1F]
    // 以下省略
    // ...
}

IDから各part (unix timestamp, machineID, pid, counter) を取得する部分の実装です。

// Time returns the timestamp part of the id.
// It's a runtime error to call this method with an invalid id.
func (id ID) Time() time.Time {
    // First 4 bytes of ObjectId is 32-bit big-endian seconds from epoch.
    secs := int64(binary.BigEndian.Uint32(id[0:4]))
    return time.Unix(secs, 0)
}

// Machine returns the 3-byte machine id part of the id.
// It's a runtime error to call this method with an invalid id.
func (id ID) Machine() []byte {
    return id[4:7]
}

// Pid returns the process id part of the id.
// It's a runtime error to call this method with an invalid id.
func (id ID) Pid() uint16 {
    return binary.BigEndian.Uint16(id[7:9])
}

// Counter returns the incrementing value part of the id.
// It's a runtime error to call this method with an invalid id.
func (id ID) Counter() int32 {
    b := id[9:12]
    // Counter is stored as big-endian 3-byte value
    return int32(uint32(b[0])<<16 | uint32(b[1])<<8 | uint32(b[2]))
}

文字列表現からIDに戻すことも可能で、以下の実装になっています。

// FromString reads an ID from its string representation
func FromString(id string) (ID, error) {
    i := &ID{}
    err := i.UnmarshalText([]byte(id))
    return *i, err
}

まとめ

Go製のUnique ID Generator「xid」について、特徴、使い方、実装などを紹介しました。
他のID生成方法との比較についてはあまり取り上げなかったので、以下の記事などを参照していただくと良いかと思います。

ユースケースに合う場合はぜひxidを使用してみてください。