gofrs/uuid にパッチをだした - ちりもつもればミルキーウェイ

はじめに

どうも皆さんconvtoです。

最近UUIDとかをドカっと調べて色々比較するみたいな記事を書きました。

convto.hatenablog.com

で、このとき実はつかってるOSSへのcontributionチャンスを発見していて、今回はそのパッチを上げたぞ(マージされるかはわからんけど)という記事です。

ちなみにPRだしたのは gofrs/uuid です。こいつは satori/go.uuidのメンテがとまったっぽいのでforkしてメンテを引き継いだぞ！みたいな立ち位置のやつです

CVE-2021-3538 をちゃんと読む - ちりもつもればミルキーウェイで触れたCVEによって乗り換えた方も多いのではないでしょうか

だしたPR

四の五のいわずとりあえず上げたパッチはこれ

github.com

PR本文とかがすべてなんですが、ようは new-uuid-format のドラフトが更新されてたので、それに合わせて実装も最新にしといたでというやつです。

以下で背景から詳しく説明します。

UUIDv7とかいってるけどなにそれ

RFC4122でUUIDが定義されて、以降色々な文脈でグローバルに一意な識別子のために利用されてきました。

実はUUIDに新しいバージョン追加しようぜみたいなdraftが2年前くらいから出始めていて、そこではUUIDv6, UUIDv7, UUIDv8が提案されています！

trackerはこれ: https://datatracker.ietf.org/doc/draft-peabody-dispatch-new-uuid-format/

draftなら仕様変わるかもしれじゃん！なんで実装のパッチなげたの？

たまたま gofrs/uuid ではdraftであるUUIDv6とUUIDv7を実装してたのであった。完。

sortableかつ過去のUUIDと同じ形式でエンコードできるから需要ありそうだし、試験的に実装しだすライブラリがあること自体はそんなに違和感はないです。

実装したときのPRはこれなんだけど、ちゃんとまだdraftで変動しうる仕様であることに気を配っている雰囲気があるので、まあプロジェクトのスタンスとしてdraftは変わることを想定しつつ受け入れてるって感じのようです。

とにかく利用しているOSSがたまたま該当draftを取り込んでいて、しかも今年の3月に更新された仕様に追従できてないホカホカcontributionチャンスがあったので突撃した次第です。

Rev 02 と Rev 03 のUUIDv7仕様差分

gofrs/uuidではもともとRev 02の実装だったのを、今回Rev 03に合わせた実装に更新するパッチを投げました。

せっかくなのでそれぞれの差分について説明してみたいと思います。

まずこのdraftではUUIDv6, UUIDv7, UUIDv8についての仕様がまとめられていますが、今回つくったパッチに影響ある更新があったのはUUIDv7のみです。v6はgofrs/uuidにとっては(みたところ)実装に影響がなく、v8はgofrs/uuidで未実装なためです。

Rev 02 のUUIDv7仕様おさらい

UUIDv7について、Rev 02 では以下のようなレイアウトです

        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
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                            unixts                             |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |unixts |       subsec_a        |  ver  |       subsec_b        |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |var|                   subsec_seq_node                         |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                       subsec_seq_node                         |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

36 bits unix timestamp
12 bits subsec_a
- 後述する可変timestampのためのフィールドその1
4 bits version (v7 の場合は 0111 )
12 bits subsec_b
- 後述する可変timestampのためのフィールドその2
2 bits variant (互換のためのやつで、RFC4122やこのdraftで定義されてるのは 10 を使う)
62 bits subsec, sequence, pseudo-random
- さらなる可変timestampや、シーケンス番号、疑似乱数を置く

というかんじ。

全体としてはsortのためのtimestamp, メタ情報のためのversion/variant, 単位時間内での識別のためのsequence, ダメ押しで疑似乱数となっております。

(シーケンスがあるのはSnowflakeとかと似ているが、ちょっとくどいかなというのが個人的な所感。たしか乱数の衝突のための必要件数はrandom bit数Nに対して 2^N/2 で求められた記憶があり、充分なrandom bit数があれば単位時間に数億opに耐えれるとか普通にありえて、そういう状況ならシーケンスなくても実用上問題ないとおもうため。充分なrandom bitを含むUUIDv7の仕様にはいらんくないか？と前々から思っていた)

そしてさらに！draft rev 02 時点のUUIDv7は 可変精度のtimestamp を考慮した仕様になってます！ジーザス

millisec, microsec, nanosecの三択あり、それぞれによってレイアウトが異なります

millisec

        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
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                            unixts                             |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |unixts |         msec          |  ver  |          seq          |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |var|                         rand                              |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                             rand                              |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

timestampとrandomにだけ着目すると

48 bits millisec timestamp
62 bits rand

みたいなかんじ

microsec

        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
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                            unixts                             |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |unixts |         usec          |  ver  |         usec          |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |var|             seq           |            rand               |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                             rand                              |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

60 bits microsec timestamp
48 bits rand

nanosec

        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
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                            unixts                             |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |unixts |         nsec          |  ver  |         nsec          |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |var|             nsec          |      seq      |     rand      |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
       |                             rand                              |
       +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

74 bits nanosec timestamp
40 bits rand

みたいな感じです。ぐえーこれ実装側でサポートするのしんどいぞ〜

さらに、シーケンス獲得のために採番側でlockが必要で、実装のときに必要な考慮が多めの仕様でした。

Rev 03 UUIDv7 仕様！

全体的に納得行く感じに仕上がっていて個人的にはめちゃめちゃ嬉しい！サクッとレイアウトかくと

    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                             |
   +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

というかんじで、

48 bits millisec precision unix timestamp
74 bits rand

です。

衝突するための採番数もmillisec単位で 2^74/2 で137,438,953,472 (1374兆)くらい必要であり、実用上ほぼ問題にならないはず！そしてなくても衝突しないであろうシーケンスも滅びた。

sortのことを考えるならtimestamp精度もmillisecで充分であり、Rev 02とくらべて、個人的にはめちゃめちゃ納得感のある仕様にまとまってるぞ！

というわけで

new-uuid-format のdraftは興味がありちょいちょいwatchしてたんですが、気がついたらかなり良さげな仕様に更新されたRev 03のdraftが爆誕していたぞ！

かつ使ってるOSSがdraft段階の仕様を実装してるおませなprojectだったのでこれはcontributionチャンスだ！ということでPRを出してみました

まだメンテナから反応ないんだけどわりと取り込まれてほしい差分だから今週末くらいまで反応なければpingしてみようかな〜