はじめに
分散システムやってるとどこからでも安全に採番できる強い衝突耐性をもったuuid的なほげほげidがほしくなります。
世にほげほげidはたくさんありますが、適当にREADMEとかよんでもみんな「これイケてるで！」「uuidとかより文字数すくないで！」「sortableでうれしいで！」とかそういうことばっかいっててどの程度衝突耐性があるのかよくわからん問題があります
今回はほげほげidの構成要素の調査と衝突耐性をざっとまとめて比較しようと思います。
比較する項目
ざっくり
- random bit数
- 衝突耐性
- ソートできるか
- その他メモ
みたいな感じで整理して比較していきます。
衝突耐性は
- 衝突確率P=0.5のときの必要な試行回数
- 乱数以外の識別要素
の2つで評価します。たとえばtimestampとか入れてるやつは暗号学的な安全性には寄与しないけど実用上はある精度の時刻で識別できて衝突耐性上がってるよな〜とかそういう感じです。利用される疑似乱数は暗号学的に理想的なものを想定します。
衝突確率は Birthday problem をみてみると以下で近似値を求められるっぽい。
これで計算すれば衝突確率P=0.5のときの試行回数nがわかりそうなんだけど、少しでも計算サボりたいからもうちょい簡単なのを探すと Auth0にいい記事を見つけた。ざっくりP=0.5なら
が試行回数らしい。簡単じゃん。記事で紹介されてる内容もわかりやすいしこれでいこう。
比較対象は適当に選びました。僕がこういう系の文脈のプログラムはGoで読み書きするのに慣れてるので、信頼できるGo実装があれば元ネタ言語がなんであれGo版読んでるのであしからず
TL;DR
せっかちな人のための比較表だけ先にあげとく
| random bit | P=0.5の試行回数 | 乱数以外の識別要素 | Sortable | Note | |
|---|---|---|---|---|---|
| UUID v4 | 2122 | 261 ≒ 230京 | なし | No | hexと区切りで36文字 |
| ULID | 280 | 240 ≒ 1兆 | msec精度timestamp | Yes | base32で26文字 |
| UUID v7 | 274 | 237 ≒ 1374億 | msec精度timestamp | Yes | hexと区切りで36文字, draft中なので参考程度に |
| nanoid | 2126 | 263 ≒ 920京 | なし | No | base64で21文字 |
| xid(mongo object id) | 224 | 212 = 4096 | sec精度timestamp, プロセス単位 | Yes | base32で20文字 |
| Snowflake | なし | 衝突しない | シーケンシャルid, machine id | Yes | 事前登録したworkerでのみ採番可 |
適当に目的にあったものを使えばいいんじゃなかろうか。今後しらない未知のほげほげIDに出くわしても同様の軸で評価できそう。
あとはbyteサイズとかも評価項目に入れても良かったけど、まあだいたい16byte前後とかだから表にいれるのはサボった。それぞれ詳細に見るとこではちゃんとbyte数も調べてるよ。
UUID v4
とりあえず充分ランダムな衝突耐性の強いidという文脈でこいつを避けては通れないのでやっていく
RFC4122ちゃんと読んだことなくてせっかくなので全部読んだ。ざっくりuuidのバージョンごとの仕様をまとめると
- v1
- v2
- v3
- v4
- 16byte random値とる
- versionとvariantの位置だけ上書き
- v1とくらべると、versionとvariant以外は全部乱数 or 高精度疑似乱数というだけ
- 122bitが乱数なので、理想的な暗号学的な乱数を想定すると衝突確率P=0.5のとき 261 の衝突耐性がある
- v5
- v3のsha-1 hash版
という感じ。v1はMACアドレス依存だしシーケンスつくるのにlock必要だしたいへ〜んという感じでござった
v3, v5はベースとなるnameの一意性の担保は自分でやらなきゃいけないので、イメージとしてはすでに一意なものをuuid形式にできるぞくらいの認識が良さそう。
というわけでなにも考えずにグローバルで一意なIDを採番できるのはuuid v4だけで、その評価は以下の感じである
| random bit | P=0.5の試行回数 | 乱数以外の識別要素 | Sortable | Note |
|---|---|---|---|---|
| 2122 | 261 ≒ 230京 | なし | No | hexと区切りで36文字 |
uuid v4 にまつわるよくある課題に触れておくと、b-tree index とかとそこそこ相性がわるいことが挙げられる。
ざっと説明するとuuid v4は毎回ランダムに割り当てられるから時間的局所性がなくて、primary keyとかにuuid v4つかうと連続して書き込まれるデータがindex上はあっちこっちに行ったりするので、書き込み時に触らなきゃいけないディスクがランダムアクセスになりがちでパフォーマンスによくない。時間的局所性があるとOS側で一定まとめてシーケンシャルアクセスにしたりしてくれるんだけどね。
逆にこの時間的局所性がない特徴はシャーディングとかのキーにするには非常に向いている。なんも気にせずに勝手に理想的に散らばるはずなので。
たとえばspannerとかはkeyをuuidにすることを推奨してたはずだけど、あれは裏でkeyを引っ掛けて物理的に分散させてデータ配置させてるからなはず。
ULID
uuid v4 はsortableじゃなくて困り事があったので、timestamp bitsを前半に入れてsortableにしちゃおう！というやつ
byteレイアウトを発見したのでそのまま貼る
0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 32_bit_uint_time_high | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 16_bit_uint_time_low | 16_bit_uint_random | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 32_bit_uint_random | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | 32_bit_uint_random | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
要は
- 全16byte(uuidとおなじ)
- 48bit unixtime timestamp(msec精度)
- 80bit random
というだけでめちゃめちゃ単純。脳筋sortableや！
encodingもuuidよりコンパクトで、uuidはhexとブロックごとのハイフンで36文字？とかだけどこっちはbase32で26文字っぽい。
とはいえ容量が重要ならencodeせずにバイトで書き込めばいいのでencodingの容量は個人的には正直そんなに気にならない。
random bitがuuid v4比較で40bitすくない。そのかわりuuid v4が未来永劫に渡って衝突耐性を持たなきゃアカンのにくれべて、こっちはmsec精度の衝突耐性でよい。まあ短時間にアホほどid発番しなければ実用上問題になることはないだろう。
これも評価すると
| random bit | P=0.5の試行回数 | 乱数以外の識別要素 | Sortable | Note |
|---|---|---|---|---|
| 280 | 240 ≒ 1兆 | msec精度timestamp | Yes | base32で26文字 |
UUID v7
IETFにDraftがでてる。2020 Febから出てて現在version 3まででてる。最新は今年の3月にでた
https://datatracker.ietf.org/doc/draft-peabody-dispatch-new-uuid-format/
v6, v7, v8 が提案されてるけど、v7 がお気に入りなのでこれだけ紹介
version, variantはいままでのuuidとおなじ。これもレイアウトあるのでペタリ
0 1 2 3 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | unix_ts_ms | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | unix_ts_ms | ver | rand_a | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ |var| rand_b | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | rand_b | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
ようは
- 48bit timestamp
- 74bit random
というつくり。やりたいことはほぼulidとおなじだけど、uuidは互換のためにversionとveriantが必要なのでそのぶん6bit randomが小さいというかんじ。
| random bit | P=0.5の試行回数 | 乱数以外の識別要素 | Sortable | Note |
|---|---|---|---|---|
| 274 | 237 ≒ 1374億 | msec精度timestamp | Yes | hexと区切りで36文字, draft中なので参考程度に |
これだけみるとulidのほうが良さげに見えるけど、もしdraftが通れば正式にuuidのように振る舞えるので過去採番したuuid資産があるなら途中からしれっとv7に変えたりできる。(エンコードされた文字列の形式とかはコンパチなはずなので)
そうかんがえるとこいつも悪くない選択肢に思える。はよ標準化されてたも
余談だけどdraft1とかの段階ではtimestampがいくつかの選択肢から精度が選べて可変でめんどかったり、timestamp単位の一意性の担保のためにシーケンスがあったり(なのでuuid v1とおなじでlockが必要だった)で実装が面倒そうな仕様だったんですが、draft重ねるうちに整理されてってdraft3の段階ではめちゃめちゃコンパクトないい感じの仕様になっててにっこりした
nanoid
ちゃんとしたspecは調べた感じみあたらなかったが、uuid相当のrandom bit(126bit)を備えつつ、encodingもbase64にして文字数節約！みたいな雰囲気っぽい。
126bitってめちゃめちゃ半端でバイト単位で考えて16byteあるとするとあと2bitあまるんですが、レイアウトがどこにも書いてないのでわからん。実装もjs読み慣れてないのでよくわからぬ。けどbase64で21文字ってことは 21 * 6 = 126 で計算あうので、多分126bitサイズであってるんだろう。で中身は全部random値ですと言う感じっぽい。
| random bit | P=0.5の試行回数 | 乱数以外の識別要素 | Sortable | Note |
|---|---|---|---|---|
| 2126 | 263 ≒ 920京 | なし | No | base64で21文字 |
まあこれだけみるとコンパクトだしuuidよりrandom bit多いしと思うが、さっきも言ったようにuuidは数bit無駄にして互換性をとることを重視してるので一概にどっちがいいとは言えん感じ。
xid(mongo object id)
spec: 独自実装なのでなし(byte表現はmongoのobject idなるものとコンパチっぽい。こまかいフォールバック先の挙動はことなるんだろうが https://www.mongodb.com/docs/manual/reference/method/ObjectId/ )
実装: https://github.com/rs/xid
文字表現はmongo object idはhexで24文字で、xidはbase32で20文字のよう。
レイアウトは
- 全12byte
- String() はbase32でencodeして20文字
というかんじ。実装はこのあたり
https://github.com/rs/xid/blob/5cbb911d27d5efc5f0be784aac766db82ebd067f/id.go#L146-L164
面白いところとしては、暗号学的な乱数からは3byteしかとってないこと。
timestampとかprocess単位のunique性があるから実用上は問題なさそうだけど、同一マシンで単位時間だと衝突確率P=0.5のときに212くらいの採番能力てことで、わりとぶつかりそうで結構強気。
サイズも12byteしかなくてわりかしコンパクトである。
32bit unix epochをもってるからsortableで、かつprocessやマシンを区別してユニークということっぽい。
sortableにしたいのはわかるけど、マシンとかプロセスの情報埋め込むのよくわかんない
元ネタがmongodbみたいな分散ストレージの文脈で生まれてるから、どこで採番されたのかわかるとデータの物理的な配置を考えるときに都合良かったのかな？よくわからん
1秒単位で同一マシンにてめちゃくちゃid採番したい！みたいなユースケースではそこそこ衝突すると思います。同一マシン同一プロセス単位時間内なら 224 の空間しかないのでそこそこぶつかりうる
ちゃんとREADMEにも暗号学的に安全じゃないからそのへん気にするなら /dev/urandom なり crypto/rand つかえよって書いてある
Xid is dependent on the system time, a monotonic counter and so is not cryptographically secure. If unpredictability of IDs is important, you should not use Xids. It is worth noting that most other UUID-like implementations are also not cryptographically secure. You should use libraries that rely on cryptographically secure sources (like /dev/urandom on unix, crypto/rand in golang), if you want a truly random ID generator.
最終的な評価はこんなかんじ！
| random bit | P=0.5の試行回数 | 乱数以外の識別要素 | Sortable | Note |
|---|---|---|---|---|
| 224 | 212 = 4096 | sec精度timestamp, プロセス単位 | Yes | base32で20文字 |
Snowflake
- spec: ?
- 実装: https://github.com/twitter-archive/snowflake/tree/b3f6a3c6ca8e1b6847baa6ff42bf72201e2c2231 (当時のソース)
本元みるかぎりなんかもうちょっと整理して改めてopen sourceにするよみたいなこといってるので、現段階で評価するのはあんまフェアじゃない気もするけど個人的なメモなので無視しておく(インフラ依存があるみたいな言及が気になる) https://github.com/twitter-archive/snowflake
公式なスペックが見当たらなかったのでとりあえずannounceをみる https://blog.twitter.com/engineering/en_us/a/2010/announcing-snowflake
これみるかぎり、twitterが使うためにつくったやつなので達成したい課題は結構twitterならではみたいな雰囲気ある
- 高可用性
- Sortable
- 秒間数万opに耐える
- 採番したidは64bit以下(twitter内の互換の都合上)
uuidは128bitだからつかえんし、zookeeperとかも検討したけど性能要件みたせなかったでとのこと
構成としては
- timestamp
- ワーカー番号
- シーケンス番号
でなりたってるっぽい。シーケンスがあるってことはシーケンスを管理する主体者が必要なはず。それでインフラ依存があるみたいな話か
announceには具体的なレイアウトの記載がない！
当時の実装 読もうとしたけどScalaは慣れてないので、READMEサクッと読むことにする
- 41bit timestamp
- 10bit machine id
- 12bit シーケンス(都度rolloverで、同一timestamp内でrolloverを保護する機能つきとのこと)
ほんでクロック同期をNTPにたよってるとのこと。NTPくん整合性担保の文脈ではガンガンズレるしいい印象がまったくないが、ID採番の文脈なら許容できるぞということかな(多少時系列崩れた採番してもtransaction管理してるわけでもなしに、大きな影響ないってことだろう)
これシーケンスの採番の仕組みがイマイチわかってないが、慣れないScalaコードをチラ見した感じだとclass内部にメンバとして持ってるっぽいから、オンメモリで管理してるオーラを感じる。
事前にworkerとしてserverを登録する仕組みで、worker同士は10bit machine idで区別されるから、それぞれのworkerで好き勝手シーケンシャルidを発行してもぶつからない！ってことだな。でド頭のtimestampでそれらは大まかなソートが可能！的な
まあ8byteの大きさでtwitterレベルの書き込み量に対して一意である！というのが要件として厳しいのでシーケンシャルに頼らざる得なくて、とはいえ1台しか採番できないとスループット追いつかないからmachine識別子も持たせてスケールできるようにしたって感じかな
| random bit | P=0.5の試行回数 | 乱数以外の識別要素 | Sortable | Note |
|---|---|---|---|---|
| なし | 衝突しない | シーケンシャルid, machine id | Yes | 事前登録したworkerでのみ採番可 |
まとめ
いろいろ見たので比較表をつくると以下の感じ
| random bit | P=0.5の試行回数 | 乱数以外の識別要素 | Sortable | Note | |
|---|---|---|---|---|---|
| UUID v4 | 2122 | 261 ≒ 230京 | なし | No | hexと区切りで36文字 |
| ULID | 280 | 240 ≒ 1兆 | msec精度timestamp | Yes | base32で26文字 |
| UUID v7 | 274 | 237 ≒ 1374億 | msec精度timestamp | Yes | hexと区切りで36文字, draft中なので参考程度に |
| nanoid | 2126 | 263 ≒ 920京 | なし | No | base64で21文字 |
| xid(mongo object id) | 224 | 212 = 4096 | sec精度timestamp, プロセス単位 | Yes | base32で20文字 |
| Snowflake | なし | 衝突しない | シーケンシャルid, machine id | Yes | 事前登録したworkerでのみ採番可 |
個人的なまとめとしては
- sortableを重視するなら現状ではULID押し
- UUID v7が今のすがたでdraft通ったらそっちを使いそう
- シャーディングのkeyにしたいとか分散しててほしい意図があるなら UUID v4 押し
- nanoidもいいけど有効bitそんなに変わらん
- 今後別のversionの UUID 使いたくなったときヌルっと変えれたほうがうれしい
- エンコーディング後の文字が少ないことを売りにしてるやつが意外とおおい
- sortableなやつはたいていtimestampを入れるかわりにrandom bitを減らしてるっぽい
- 単位時間でハチャメチャ採番するusecaseだとrandom bitの数見て単位時間に何件くらいなら衝突しないとみなせるのか計算してから採用するのをおすすめ
- まあ実用上問題になることはないとおもうが、CPUぶん回して採番の向こう側に行く使い方なら計算しとけ
