Carpe Diem

備忘録

ユースケースに応じたユニークなIDの生成

概要

ユニークなID生成をしたい場面は多々ありますが、ユニークIDにはユースケースによって以下のような要件が出てきます。

  • ユニーク
  • 短い(=データ量が少ない)
  • 推測困難
  • 分散性(ランダム性)
  • 順序性(Lexicographical)
  • 生成速度

それぞれの観点について説明し、最後にGoでオススメの選択肢を提示します。

ユニーク

ユニークIDというのでそのまんまではありますが、一番満たさなければいけない要件です。

特に現代におけるサービスではトラフィックをさばくためにスケール性を重視し、分散システムであっても衝突しないIDを求められます。

例えばMySQLのようなDBのauto_incrementを使う場合、そのDBがスケールしにくい&SPoFといった課題があります。

Twitterで開発されたsnowflakeは以下のフォーマットになっており、

f:id:quoll00:20210414042243p:plain ※instance = machine id

ref: Snowflake ID - Wikipedia

大量のツイートを扱うために以下の要件を満たしています。

  • 分散システムで短期間に大量に発行しても衝突率を極力下げる
  • 短い
  • ツイート順に並べるため順序性を持つ

短い(=データ量が少ない)

衝突率下げる簡単な方法は文字数を長くすることですが、一方で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()を使うケースもあるため、中身を見るまでは分からないので注意が必要です。

分散性(ランダム性)

クラスタ構成のデータベースに保存する際に均等に各シャードに保存されることでホットスポットを防ぐ、といった目的です。

よくある対処法は保存する前にハッシュ化するやり方で、いくつかのデータベースでもドキュメントで推奨されています。

ハッシュ関数については

  • Murmur
  • FNV-1a

あたりが短くても均等に分散してくれそうです。

security - Which hashing algorithm is best for uniqueness and speed? - Software Engineering Stack Exchange

もしくは暗号学的に安全な擬似乱数に基づいて生成したUUIDを使うのが良いです。

順序性(Lexicographical)

生成した時系列に基づいて(タイムベース)ソートしたい要件はよくあります。

なのでsnowflakeのような先頭n bitsをタイムスタンプに基づいて生成するIDを使うのが良いです。

Instagramでも改良されていますが同じようなフォーマットで生成されています。

生成速度

速度はどんなシステムにおいても求められます。

ユースケースの要件を満たすライブラリの中で実際に比較して測定するのが一番です。

Goならどのライブラリを選ぶか

ざっと調べた&使用した感じで良さそうなのを挙げてみます。

バランス型

バランスの良い(ユニーク性、順序性、短め、速い)ID生成ライブラリは、タイムベースな

github.com

が良さそうです。

snowflakeをGoで書いた sonyflake の方がより短いIDを生成しますが、configの設定だったり自前で文字列に変換する手間があるので使いやすさの点も考慮してrs/xidが良いかなと。

推測困難、ランダム性を重視

推測困難、ランダム性を重視する場合はGoogleのuuidを使います。

github.com

先程実装に依存する、と書きましたがこれは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               9779587               112.3 ns/op            24 B/op          1 allocs/op
BenchmarkGenSonyflake-16           31027             38974 ns/op               0 B/op          0 allocs/op
BenchmarkGenUUID-16              7776001               141.2 ns/op            64 B/op          2 allocs/op

xidが最も速かったです。
そしてsonyflakeは非常に遅かったです。
またgoogle/uuidが予想以上に速く、短さ・順序性を求めないケースではいろんな箇所で使えるなと感じました。

ベンチマークコード

まとめ

ユニークIDにおける考慮すべき観点の説明と、Goでの選択肢を提示しました。

参考