概要
ユニークなID生成をしたい場面は多々ありますが、ユニークIDにはユースケースによって以下のような要件が出てきます。
- ユニーク
- 短い（＝データ量が少ない）
- 推測困難
- 分散性（ランダム性）
- 順序性（Lexicographical）
- 生成速度
それぞれの観点について説明し、最後にGoでオススメの選択肢を提示します。
ユニーク
ユニークIDというのでそのまんまではありますが、一番満たさなければいけない要件です。
特に現代におけるサービスでは高トラフィックをさばくためにスケール性を重視し、分散システムであっても衝突しないIDを求められます。
例えばMySQLのようなDBのauto_incrementを使う場合、そのDBがスケールしにくい＆SPoFといった課題があります。
Twitterで開発されたsnowflakeは以下のフォーマットになっており、
※instance = machine id
大量のツイートを扱うために以下の要件を満たしています。
- 分散システムで短期間に大量に発行しても衝突率を極力下げる
- 短い
- ツイート順に並べるため順序性を持つ
短い（＝データ量が少ない）
衝突率下げる簡単な方法は文字数を長くすることですが、一方で10億、100億といったオーダーになってくるとデータサイズが非常に大きな影響を与えます。
なのでできる限り短い＝データ量が少ないIDが良いです。
例えばUUIDは128bitsですが、先程のsnowflakeは64bitsで済みます。
推測困難
session idやtokenなどセキュアな値を生成したい場合です。
推測されてしまう値だとセキュリティ要件を満たさないので、暗号学的に安全な擬似乱数に基づいて生成したり、文字数を長くしたりすることが多いです。
よくUUIDが候補として挙がりますが、UUID(v4含む)自体はRFC的にセキュリティ要件を満たしません。
Do not assume that UUIDs are hard to guess; they should not be used as security capabilities (identifiers whose mere possession grants access), for example.
ref: https://www.ietf.org/rfc/rfc4122.txt
というのも「推測困難」の部分が実装に依存するからです。
言語、ライブラリによっては乱数の生成がmath.rand()を使うケースもあるため、中身を見るまでは分からないので注意が必要です。
またOWASPやOAuth RFCでは128bits以上のエントロピーを求めており、UUIDのrandom bitsが122bitsであることも要求水準を満たしていません。
なので各言語の暗号学的に安全な擬似乱数を用いて生成するのが良いでしょう。
分散性（ランダム性）
クラスタ構成のデータベースに保存する際に均等に各シャードに保存されることでホットスポットを防ぐ、といった目的です。
よくある対処法は保存する前にハッシュ化するやり方で、いくつかのデータベースでもドキュメントで推奨されています。
ハッシュ関数については
- Murmur
- FNV-1a
あたりが短くても均等に分散してくれそうです。
もしくは暗号学的に安全な擬似乱数に基づいて生成したUUIDを使うのが良いです。
順序性（Lexicographical）
生成した時系列に基づいて（タイムベース）ソートしたい要件はよくあります。
なのでsnowflakeのような先頭n bitsをタイムスタンプに基づいて生成するIDを使うのが良いです。
Instagramでも改良されていますが同じようなフォーマットで生成されています。
他にもUUIDに順序性をもたせたULIDという仕様があります。
生成速度
速度はどんなシステムにおいても求められます。
ユースケースの要件を満たすライブラリの中で実際に比較して測定するのが一番です。
Goならどのライブラリを選ぶか
ざっと調べた＆使用した感じで良さそうなのを挙げてみます。
バランス型
バランスの良い（ユニーク性、順序性、短め、速い）ID生成ライブラリは、タイムベースな
が良さそうです。
snowflakeをGoで書いた sonyflake の方がより短いIDを生成しますが、configの設定だったり自前で文字列に変換する手間があるので使いやすさの点も考慮してrs/xidが良いかなと。
ランダム性を重視
ランダム性を重視する場合はGoogleのuuidを使います。
また推測困難性についても、エントロピーが122bitsではあるもののcrypto/randを使ってるので、もし運用中のサービスでtokenとして使用していても即座にリプレースする必要はないでしょう。
推測困難
crypto/randを使って直接生成します。
以下は 128bits (16文字) の例です。
const length = 16 func generateToken() (string, error) { b := make([]byte, length) _, err := rand.Read(b) if err != nil { return "", err } return base64.RawURLEncoding.EncodeToString(b), nil }
文字列にする際はOpenID ConnectのnonceパラメータのようにURLに含まれることも考慮して、URLセーフなbase64.RawURLEncodingを使うのが良いです。
パフォーマンス
- xid
- sonyflake
- google/uuid
- crypto/rand直接
で検証してみました。
$ go test -bench . -benchmem goos: darwin goarch: amd64 pkg: github.com/jun06t/go-sample/guid cpu: Intel(R) Core(TM) i9-9980HK CPU @ 2.40GHz BenchmarkGenXID-16 9077187 114.6 ns/op 24 B/op 1 allocs/op BenchmarkGenSonyflake-16 31176 39110 ns/op 0 B/op 0 allocs/op BenchmarkGenUUID-16 1609730 742.2 ns/op 64 B/op 2 allocs/op BenchmarkGenToken-16 1511538 759.2 ns/op 64 B/op 3 allocs/op
xidが最も速かったです。
そしてsonyflakeは非常に遅かったです。
google/uuidやcrypto/randは擬似乱数を使用しているせいか、xidより6~7倍程度時間がかかっていました。
まとめ
ユニークIDにおける考慮すべき観点の説明と、Goでの選択肢を提示しました。
