はじめに
一口メモシリーズ。表題通り。単調増加に関するオプションの幅がかなり広い。のでそれをざっとまとめます。
昨今OSSやらなんやらで uuid v7 に関する議論をある程度みかけますが、このオプションの幅の広さを知っていると、ある選択に対して「いいですね...」と思えて玄人っぽいのでおすすめです。
それではやっていきます
uuid v7 の説明
RFC9562 Section 5.7 にて定義されている uuid version
同 RFC Fig 11 から引用すると、レイアウトは次の通り:
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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
ようは uuid によって定められている version および variant 以外の部分について
- 前半 48 bits を timestamp
- 後半を 74bits を rand
にて埋めたレイアウトとなっています。これによってある程度のランダム空間による衝突耐性と、時系列によりソート可能な性質を持ちます。
これは uuid の利用先で B Tree およびその派生アルゴリズムでデータを保持するようなケースにおいて、局所性のあるデータの読み書きにメリットがあります。
ただ同一tick間に複数回採番があると、単調増加である保証はできません。後半が rand なのでそれはそうですね。この部分について、RFCでは単調性を保持するいくつかの手法を optional で紹介しています。
RFC にて提示されているオプションとその説明
RFCではこんな感じの説明がなされています:
https://www.rfc-editor.org/rfc/rfc9562.html#section-5.7-2
- An OPTIONAL sub-millisecond timestamp fraction (12 bits at maximum) as per Section 6.2 (Method 3).
- An OPTIONAL carefully seeded counter as per Section 6.2 (Method 1 or 2).
- Random data for each new UUIDv7 generated for any remaining space.
ざっくり流れで言うと、「OPTIONALで timestamp 12 bits 増やしてもいいよ。そのときは rand を削ってね」「さらに単調増加カウンタみたいなのを仕込んでもいいよ。これも rand 向け空間つかったりするよ」「のこりは rand で埋めてね」と言う感じです。
それぞれ詳細についてもさっくり紹介します。
rand_a を潰して timestamp 精度を最大 12 bits 上げる
Section 6.2 (Method 3) にて紹介されている手法。
ようは rand_a を左端から削っていき、その空間を timestamp の解像度を上げるために使っちゃおう！というやつです。
単調増加を念頭に入れているので、もちろん rand_a の 12 bits 全て使わない場合も左側から割り当てる必要があります。じゃないと順序通り並ばないため。
あとは単に時刻の解像度をあげてtickの衝突可能性を減らしてるだけなことにも注意が必要です。このアプローチは実用上は発生確率が大きく減るので意味がありますが、衝突自体はあり得る状態のままです。
RFCでは具体的な計算手法についても紹介していますが、それはここでは省略します。
rand_a の左端から、同一 timestamp 間のカウンタを固定bitで入れる
Section 6.2 (Method 1) で紹介されている。単調増加のカウンタを入れてしまう方法。
想定採番スピードによってどのくらいの空間を確保するかが実装者の裁量。カウンタをめっちゃ増やしたい時は rand_b 空間まで入っちゃってもいいよと MAY で言及されています。
In the event that more counter bits are required, the most significant (leftmost) bits of rand_b MAY be used as additional counter bits.
カウンタ系、パッと聞くといいじゃんな気持ちになりますが、厳密にやるにはロックが必要です。かつ分散システム上ならグローバルロックとかもしたくなるけど、そんなことしてる間にmsec経過しちゃいそうですね。ロックとるとしてもどこまでやるか？の論点があって地味に考えることが多いです。
同一tickなら rand 一度だけ振って、後続は値を単調増加カウンタとして扱う
Section 6.2 (Method 2) で紹介されてる。
tick衝突時に、さっき降った rand に適当に値を追加してしまう案。同じ空間を同一tickならカウンタとしても使っちゃう方法。
追加する値も通常ランダムに決定するが、予想されても困らないなら +1 とかに固定してもいいよ！とされていた。
単位時間あたりの採番数が多いバッチみたいなシナリオなら、rand_b も使うといいよみたいな言及がある。
UUIDv7's rand_b section SHOULD be utilized with this method to handle batch UUID generation during a single timestamp tick.
オプションの幅が広く実装者の選択の余地が大きい
先ほど説明したオプションを、実装者が求める性質に合わせて選択して実装する形になります。
柔軟に作るなら複数オプションサポートして選択可能にしたいだとか、とにかく競合したくないのでカウンタを選ぶだとか、何かしらの意思決定をする必要があります。
それぞれ解決できる課題、解決できない課題、実装コスト、などが異なる。例えばカウンタとかはパッと聞くと便利そうに見えますが、ちゃんとやるならロックが必要で複雑化します。厳密にやるならグローバルロックなど必要ですがそんなことやってる間にmsecくらい経過しちゃうよ...などあり、ロックのとり方にもグラデーションがありそうです。timestamp精度向上は簡素だし機能しますが、発生確率が下がるだけで問題自体は発生しうる状態のままです。
uuid v7 を実装するということは、この取捨選択を理解し、得たい性質や捨ててもよい性質を見極めて RFC で言及されているそれぞれのオプションの一部もしくは複数を実装する意思決定をする、ということに他なりません。
uuid v7 は単調増加に関するオプションがかなり幅が広い定義になっていて、実装者にその意思決定の負担があります。実装自体はコンパクトになりがちですが、この何かを捨てる意思決定をしっかりやって方針を揃えて実装するのは簡単ではないです！
最後に
uuid v7 は実装者の裁量がかなり大きく、得たい性質に合わせて意思決定する必要があることを説明しました。
これはまあ、実運用上ありえる様々な要求にそれぞれのバランスで応えられるようにしているよ！ということなのでそれ自体には特に異論はないです。が、それをメンテしているソフトウェアでしっかり意思決定するのは利用文脈などにもよるので結構むずかしいです。
このあたりふんわり把握しておくと uuid v7 実装を見かけたとき「そうじゃよな」「わかるよ」「いいじゃん...」などの感想が持てるようになり便利だと思います。
