Edited at
Go3Day 6

Go製のUnique ID Generator「xid」について

More than 1 year has passed since last update.

この記事は 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を使用してみてください。