UUIDv7の基礎 - レンコン畑でつかまえて

はじめに

そういえばいつぞやにPostgresでのUUIDv7の単調性の保証方法について解説しましたが、そもそもUUIDv7について書いてないなと思い返したので、昔の発表資料を再利用しつつブログにも書いておこうと思います。

そもそもUUIDってなんだっけというお話から入ろうと思います。

仕様から引用すると

A UUID is 128 bits long and is intended to guarantee uniqueness across space and time.

ということで、UUIDは128bitからなる識別子で、空間と時間にわたって一意性を保証します。

00000000-0000-0000-0000-000000000000みたいな見た目をしており、最新の仕様はRFC9562で規定されています。

UUIDはv1からv8まで規定されています。が、v2は仕様からはハブられているので仕様としては7種類です。まぁ、実務上だとv4とv7しか使わないと思うのでとりあえず2種類覚えておけば生きていけます。

v8はベンダー固有ということで、独自のUUID実装を表すバージョンとなっています。

バージョン	説明
UUIDv1	100ナノ秒単位のタイムスタンプ＋重複回避用のクロックシーケンス＋ノードID タイムスタンプを下位ビットから並べているせいで生成順にソート出来ない
UUIDv2	（RFC9562で規定されていないので割愛）
UUIDv3	名前空間内で名前から一意な値を生成する（MD5）
UUIDv4	（バージョンとバリアントフィールド以外）完全にランダム
UUIDv5	名前空間内で名前から一意な値を生成する（SHA-1）
UUIDv6	UUIDv1のタイムスタンプを上位ビットから並べて生成順にソート可能にしたもの
UUIDv7	ミリ秒単位のUNIXタイムスタンプ＋ランダム値で生成順にソート可能にしたもの
UUIDv8	君だけの最強のUUIDを実装しよう

上記の表のとおり、v7以外にタイムスタンプを使用している実装としてv1とv6があります。

そのうち、v1はビットフィールドを下位から並べているせいで解析をしないとソートが出来ません。ただし、一般的なガイダンスとしてUUIDの解析は避けることが推奨されています。（Section 6.12.）

また、v1とv6はともにグレゴリオエポックでタイムスタンプが実装されていますが、グレゴリオエポックをIEEE754で実装するのは結構大変です。仕様としてもグレゴリオエポックをIEEE754で実装するのはまれとしています。（Section 2.1.）

v1とv6はUUIDの衝突を防ぐ目的でUUIDを生成した端末のMACアドレスを含めますが、仕様としてはセキュリティの目的でMACアドレスをUUID内で使用すべきではないというスタンスです。（Section 8.）

また、v7はv1やv6に比べてエントロピー特性を改善しています。（Section 5.7.）

ということからRFC的にもタイムベースなUUIDを使う場合はv7を採用するべきとしています。（Section 5.6.）

v7はバージョンとバリアントを除くと、以下のフィールドから構成されます。

フィールド	説明
`unix_ts_ms`	48ビットで表現されたミリ秒単位のUnixエポックタイムスタンプ
`rand_a`	12ビットのランダムフィールド
`rand_b`	62ビットのランダムフィールド

unix_ts_msはミリ秒なので、同一ミリ秒内で複数回生成した場合は生成順のソート（単調性）を保証できなくなります。

せっかくタイムスタンプを使って単調性を保証できるようにしたのに、なんだか片手落ちですね。

でももう大丈夫

RFCでは追加の単調性を保証する以下の3つを提案しています。（Section 6.2. Monotonicity and Counters）

共通して以下の方法はrand_a（とrand_bの左側ビット）を使用して追加の単調性を保証します。ただし、いずれも状態を保持する必要があるため、基本的にはシングルノードを前提としています。

固定ビット長カウンターでは、rand_aの一部もしくは全部をカウンターとして使用して、タイムスタンプティック内で生成するたびにカウンターをインクリメントします。

また、桁数が不足するようであればrand_bの左側ビットもカウンターとして拡張します。

タイムスタンプティック内の初回生成時は普通にv7を生成し、2回目以降は前回生成した値にランダム値を加算していきます。

この場合、初回にあまりにも大きい値を生成してしまうとすぐにレンジを使いつぶしてしまうので、ramd_aパートを000で生成しておくといった工夫も必要になります。

rand_aを追加のタイムスタンプフィールドとし、サブミリ秒をエンコードして格納します。また、サブミリ秒が衝突した場合はサブミリ秒のティックを進めて衝突を回避します。

クロック精度がプラットフォームで変わるため、実装上はプラットフォーム毎に生成ロジックを変える必要があります。

おわり