data-registryによるRevision ID生成アルゴリズムにUUID v7を選択した。

背景

資源評価に利用するデータの永続化を担うdata-registryの開発をすすめている。

前回の記事では、冪等性キー生成に用いるハッシュアルゴリズムを選んだ。 本記事では、永続化処理が実行される際のRevision IDの生成方法について考える。

要件

現時点で、data-registryには下記のユースケースが見つかっている:

• 版の履歴閲覧: あるデータセットの変更履歴を時系列で表示したい
• データ登録要求の並行受信: 複数人のユーザーが複数シナリオを並列計算し、それらのクライアントからの登録要求を受信した

上記から、Revision IDの生成は、以下の要件を満たす必要がある:

ここで、不変性（SR002）については実装の責務として考慮外とし、残りの要件を満たすID生成アルゴリズムを選定する。 アルゴリズムには複数の候補が考えうるが、詳細な検討の手間を軽減するには、まず時系列順序付け可能性を根拠に選択肢を刈り込むとよさそう。

候補アルゴリズム

ID群が時系列で順序付けされるためには、IDは時刻情報を含むtimestamp-basedな手法で生成される必要がある。

これに着目すると、例えばNanoidやUUID v3, v4, v5, v8は検討対象から除外でき、候補としては下記が残る:

• 連番
• Snowflake ID
• UUID v7

なお、timestamp-basedな手法としてはUUID v1およびv6も含まれるが、これらと比較した場合にはv7が推奨されている（スーパー意訳）ため検討候補から除外した。

候補アルゴリズムの比較検討

連番（✘ 不採用）

その名の通り、連番の整数をIDに使う方法。

ID: 1, 2, 3, 4, ...

この手法の利点はストレージのオーバーヘッドが少ないことだろう。 表現はシンプルだが、それを実現するアーキテクチャや実装は必ずしもシンプルとは限らない。 2種類の実現方法「データベースレベル」「アプリケーションレベル」それぞれについて、pros/consを整理してみる。

方法A: データベースレベル

PostgreSQL の SERIAL/BIGSERIAL（自動採番機能）を利用する方法。

• pros:
  • ✔ 採番の責務をデータベースに持たせられる
  • ✔ ロック時間が短い
• cons:
  • ✘ 単一のprimary writerに依存
  • ✘ スケーラビリティ: 並行タスクが全て同じDBに集約

方法B: アプリケーションレベル

採番の責務をアプリケーションで持つ構成。 この方法をとるとデータベースについては水平スケールが自由になるが、結局ほアプリケーションレベルに移ってきた採番の責務がボトルネックになる。

つまり、連番形式は宿命的に「最後の値は何か」というグローバルな状態管理に依存する方法で、この状態は必ずどこかに集約されることになる。 結果として、SR020（分散生成可能性）を満たさないため不採用とする。

Snowflake ID（✘ 不採用）

Twitterなどの大規模分散システムで運用実績のある手法。

ID: 175638572750991360
     ├─ timestamp(ms)
     ├─ machine id
     └─ sequence

• pros:
  • ✔ 大規模分散システムでの運用実績あり
  • ✔ ストレージ効率がよい
• cons:
  • ✘ Machine IDの事前割り当てが必須（新規マシン追加時に管理が必要）
  • ✘ 各machineが自身のsequenceを管理する必要がある

ストレージ効率の良さは魅力的だが、プラットフォームの潜在ユーザーの規模を考慮すると、machine IDの割り当てなどの運用オーバーヘッド増加がペイされるとは考えにくい。 data-registryにおける採用は見送ることにする。

UUID v7（✔ 採用）

UUIDの一つ。 タイムスタンプベースのフィールドを備えつつ、同タイプの先行バージョン（v1およびv6）に比べてランダム特性が向上している。

ID: 0189a5c5-a92b-7b47-b5ad-e6c3cb6c41e9
   └─ from timestamp ─┘

• pros:
  • ✔ 決定的に生成できるため各ノードで独立生成可能
  • ✔ 高いB-tree局所性による高速書き込み
  • ✔ 標準性（cf: RFC 9562）
  • ✔ エコシステム充実: Clojureでもライブラリを利用可能
• cons:
  • ✘ タイムスタンプ衝突にはランダム¹部分のみで対処する必要がある
    • TODO: ランダム部分のビット長が最悪ケースをカバーするか確認する

短所もあるものの、これらはdata-registryのユースケースにおいては問題にならないかもしれないので、実際に試算してみる。

同タイムスタンプ内における一意性違反リスク

UUID v7では、同じミリ秒内に複数のIDを生成する場合、一意性の保証はランダム部分（74ビット）で対処する必要がある。 この問題をキューイングなどのアーキテクチャで解決しない場合において、UUID v7のエントロピー性能がdata-registryの最悪ケースをカバーできるかを見積もる。

この問題は誕生日問題と同じなので、並行プロセス数を\(n\)は、ランダム部分のビット長を\(b\)とすると、衝突確率は下式で表される:

いま1,000,000の並行プロセス（1,000ユーザー × 1,000シミュレーション）が同ミリ秒内にIDを生成する場合、\(n = 10^6\)、\(b = 74\)なので、衝突確率は

となり、ピーク時リクエストに対してアーキテクチャによる緩衝を挟まない場合にも、UUID v7のエントロピー性能は充分な安全マージンを持つことがわかった。

以上から、data-registryにおけるRevision IDの生成したアルゴリズムにはUUID v7を採用する。

所感

本記事でも、前回の記事と同様に、最悪ケースに対するキャパシティ見積もりに基づいて技術選定した。 実際には、最悪ケースに対してアーキテクチャ的な解決を挟まない場合にはID衝突以前に別の問題（スループットなど）が生じそうだが、ひとまずの物理的な猶予は把握できた。 大規模アーキテクチャにおける成功例: Snowflake IDも一応は検討したが、個人開発における運用性を考えると選べなかった。

次回は、Revision IDと冪等性キーの永続化方法について考える予定。