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


この記事は [Go3 Advent Calendar 2017](https://qiita.com/advent-calendar/2017/go3) の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を使用しない

など

# 使い方
コード:

```go
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の配列として定義されています。

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

const rawLen = 12 // binary raw len
```

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

```go
// 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文字の文字列表現を生成しています。

```go
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) を取得する部分の実装です。

```go
// 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に戻すことも可能で、以下の実装になっています。

```go
// 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生成方法との比較についてはあまり取り上げなかったので、以下の記事などを参照していただくと良いかと思います。

- [ID生成大全](https://qiita.com/kawasima/items/6b0f47a60c9cb5ffb5c4)
- [Generating good unique ids in Go](https://blog.kowalczyk.info/article/JyRZ/generating-good-unique-ids-in-go.html)
- [xidのREADME](https://github.com/rs/xid/blob/master/README.md)

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