関連スライド
Meta XR SDK(V66-74)でQuestアプリを開発
あうぜん
1.2M
各ページのテキスト
UUIDv7における連続発行時の単調性の保証方法 @jyuch
自己紹介 • @jyuch • 都内でデータエンジニアをしています 2
アジェンダ • UUIDの基本 • 単調性を保証するためにRFCで提案されている方法 3
UUIDの基本 4
UUID A UUID is 128 bits long and is intended to guarantee uniqueness across space and time. • 128bitからなる識別子 • 空間と時間にわたって一意性を保証する • 00000000-0000-0000-0000-000000000000 みたいな見た目 • 最新の仕様はRFC9562で規定されている 5
UUIDの各バージョン UUIDv1 100ナノ秒単位のタイムスタンプ＋重複回避用のクロックシーケンス＋ノードID タイムスタンプを下位ビットから並べているせいで生成順にソート出来ない UUIDv2 （RFC9562で規定されていないので割愛） UUIDv3 名前空間内で名前から一意な値を生成する（MD5） UUIDv4 （バージョンとバリアントフィールド以外）完全にランダム UUIDv5 名前空間内で名前から一意な値を生成する（SHA-1） UUIDv6 UUIDv1のタイムスタンプを上位ビットから並べて生成順にソート可能にしたもの UUIDv7 ミリ秒単位のUNIXタイムスタンプ＋ランダム値で生成順にソート可能にしたもの UUIDv8 ベンダー固有 6
（UUIDv6ではなく）UUIDv7を採用するモチベーション • UUIDv1は解析しないとソート出来ない • 一般的なガイダンスとして、UUIDの解析は避ける（Section 6.12.） • UUIDv1 / UUIDv6のタイムスタンプは実装が大変 • グレゴリオエポックをIEEE754で実装することはまれ（Section 2.1.） • UUIDv1 / UUIDv6は実装によってはMACアドレスが露出する • MACアドレスをUUID内で使用すべきではない（Section 8.） • UUIDv1 / UUIDv6はUUIDv7と比べてエントロピーが小さい • UUIDv7でエントロピー特性を改善している（Section 5.7.） タイムベースなUUIDを使用するならUUIDv7を採用するべき（Section 5.6.） 7
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 | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ Figure 11: UUIDv7 Field and Bit Layout unix_ts_ms rand_a rand_b 00000000-0000-7000-8000-000000000000 ver var 8
UUIDv7のフィールド及びビットレイアウト フィールド 説明 unix_ts_ms 48ビットで表現されたミリ秒単位のUnixエポックタイムスタンプ rand_a 12ビットのランダムフィールド rand_b 62ビットのランダムフィールド UUIDv7のタイムスタンプはミリ秒精度 ナイーブに実装すると同一ミリ秒内で生成順にソート出来なくなる （単調性が保証できなくなる） 9
追加の単調性を保証するためにRFCで提案されている方法 10
追加の単調性を保証するためにRFCで提案されている方法 RFCでは以下の3つが提案されている （Section 6.2. Monotonicity and Counters） • 固定ビット長カウンター（Method 1） • 単調増加するランダム値（Method 2） • 追加のクロック精度の導入（Method 3） いずれもrand_a（とrand_bの左側ビット）を使用してソート可能にしている また、いずれもシングルノードでの生成を想定している 11
固定ビット長カウンター • rand_aの全体もしくは一部をカウンターとして使用 • さらにカウンター長が必要ならrand_bの一部も使用する • タイムスタンプティック内で生成するたびにカウンターをインクリメントする 00000000-0000-7000-8???-???????????? 00000000-0000-7001-8???-???????????? 00000000-0000-7002-8???-???????????? 00000000-0000-7003-8???-???????????? 12
単調増加するランダム値 • タイムスタンプティック内で生成するたびにランダム値を加算 • 初回はふつうにUUIDv7を生成 • 同一タイムスタンプティック内であれば、前回の値にランダム値を加算 00000000-0000-7000-8000-000000000000 +5 00000000-0000-7000-8000-000000000005 +2 00000000-0000-7000-8000-000000000007 +3 00000000-0000-7000-8000-00000000000A 13
追加のクロック精度の導入 • rand_aを追加のタイムスタンプフィールドとして使用 • rand_aにはサブミリ秒をエンコードして格納する • PostgreSQLのuuidv7()ではプラットフォームで精度が変わる • OSから供給されるクロックの精度が変わるから • Linuxではナノ秒を12ビットにエンコード • Windows / Mac OSではマイクロ秒を10ビットにエンコード • サブミリ秒が衝突した場合はティックを進めて衝突を回避する 14
まとめ • タイムベースのUUIDを使うならUUIDv7を使う • UUIDv1 / UUIDv6は互換性が必要な用途以外では非推奨 • タイムスタンプはミリ秒精度 • サブミリ秒を取り出せる場合もあるが、生成側の実装依存 • 実装によっては同一ミリ秒内でも単調性を保証する • RFCで提案しているのは以下の方法 • 固定ビット長カウンター • 単調増加するランダム値 • 追加のクロックの導入 15