TypeID - Stripe ID に着想を得た、型安全で K-ソート可能なグローバル一意識別子

 (github.com/jetpack-io)
2 ポイント 投稿者 GN⁺ 2023-06-29 | 1件のコメント | WhatsAppで共有
  • TypeIDは UUIDv7 を拡張した型安全な識別子で、Stripe API の prefix 利用方式に着想を得たグローバル一意識別子形式
  • 正式な文字列は小文字文字列で、最大 63 文字の小文字 snake_case ASCII type prefix、_ 区切り文字、修正版 base32 でエンコードされた 26 文字の UUIDv7 suffix の 3 つの部分で構成
  • type prefix により、user ID を post ID が必要な場所で誤って使うことを防ぎ、デバッグ時に識別子がどのエンティティ型を指しているのかをすぐに把握可能
  • TypeID は UUID の上位集合であり、型情報を取り除いてデコードすると有効な UUIDv7 が得られる構造
  • K-ソート可能なためデータベースの主キーとして使用でき、完全にランダムなグローバル ID である UUIDv4 と比べて、データベース locality の低下問題を減らすことが目的
  • base32 エンコーディングは URL 安全性、大文字小文字の非区別、曖昧な文字の回避、ダブルクリックで選択しやすいこと、UUID の従来の hex エンコーディングより短い長さといった特性を持つ
  • 公式実装は Go、SQL、TypeScript で提供されており、最新の spec バージョンは v0.3.0
  • コマンドラインツールで TypeID の生成、既存 TypeID の UUID デコード、UUID の TypeID エンコードを実行可能
    • typeid new prefix で新しい TypeID を生成
    • typeid decode prefix_01h2xcejqtf2nbrexx3vqjhp41 で type と uuid を出力
    • typeid encode prefix 0188bac7-4afa-78aa-bc3b-bd1eef28d881 で TypeID を生成
  • Jetify の TypeID Converter では、TypeID 文字列を UUID に変換したり、prefix:UUID 形式から TypeID に変換したりできる

関連記事

1件のコメント

 
GN⁺ 2023-06-29
Hacker Newsのコメント

  • いくつか提案がある: prefix文字列は手遅れになる前に固定して文書化したほうがよい
    Go実装を見る限り小文字ASCIIなので問題なさそうだが、article-comment のような複合型では曖昧さがある
    複雑なプロジェクトやORMでは区切り文字を避けにくいので、単一の区切り文字を許可することを検討する価値がある
    Go実装にはテストがないが、単体テストしやすいコードなのでぜひ追加すべき
    GoではGoogleのUUID実装のように、きちんとしたパース関数と内部バイト配列を使うのが適切で、文字列はレンダリングとprefixにだけ使うほうがよい
    現在のパースは寛容すぎて、suffixが空だと生成モードに入るように見えるし、SplitN 後のインデックス参照はアンダースコアがないとパニックになりそうだ
    設計そのものは粗探しをしようと思ったが、結局はトレードオフのsweet spotをうまく捉えているように思える

    • base32エンコーディングのような最も複雑な部分にはテストがある: https://github.com/jetpack-io/typeid-go/blob/main/base32/bas...
      それでも指摘はその通りで、言語実装が増えるほど相互互換性の確認が必要になるので、より厳密なテストスイートを追加する予定
      prefixに関しては、許可する文字集合を仕様で定義していない点が懸念なのか気になっている
    • READMEで他の実装を募集しているので、テストスイートがあるとサードパーティコードにも有益
    • その後、かなり徹底したテストを実装した: https://github.com/jetpack-io/typeid-go/blob/main/typeid_tes...
      そして仕様でもprefixを明確化した
    • このためのテストを書いてみるつもり
    • prefixが固定のものだと誤解したようだ
      prefixは利用するドメインに応じて決めるもの

  • この方式を何年も使ってきたが、違いが2つある
    1つ目は、人が実際に値を手入力するとは想定していないので、l と 1 の混同はそれほど気にしていないこと
    その代わり、単語、とくに罵倒語が偶然できる可能性を減らすため、eiou の母音を除いた base32 を使っている
    2つ目は、ソルト入りのbase32文字2文字をチェックサムとして追加していること
    値が誤りだったり悪意あるものだったりする場合でも、データストアを問い合わせるまでもなく判定できるのに、他の実装がなぜこれをやらないのか分からない

    • 数年前、自動生成パスワードで analrita が出てきて抗議を受けたことがある
      除外文字に a も入れることを検討してよいかもしれない
    • チェックサム追加には賛成だが、「誤りや悪意」という部分が気になる
      人が手入力しない前提なら、誤って不正な値が入る経路が何なのか疑問
      コピー＆ペーストのミスや、ページが大文字でレンダリングするケースはあるかもしれないが、base32なら大文字小文字を正規化すれば済む
      また、2バイトで暗号学的に安全でないチェックサムが、悪意あるケースでどう役立つのかも気になる
    • チェックサムのアイデアは興味深い
      TypeID仕様に含めるべきか検討している
    • 数か月前、エンコーディング方式の一部として2つ目の方式を実装した
      データベース問い合わせをどれだけ減らせたかは分からないが、デコード中により曖昧なエラーに陥らない点は良いと思う

  • 本文とは別に「Crockford's alphabet」へのリンクがある: https://www.crockford.com/base32.html
    この base32 体系では、英数字のうち 1 と紛らわしい I、L、0 と紛らわしい O、そして U を除外している
    ページでは U を除いた理由を「偶発的な猥褻さ」だとしているが、いったいどういう意味なのかわからない

    • Crockford が冗談っぽく書いたもの
      紛らわしくない英数字でまともな base32 アルファベットを作るなら、O、I、L だけ外せばよい
      それでも 33 文字残るので、もう 1 文字減らす必要があり、何を外しても構わないから最後に削る文字へ適当な理由を付けたようなもの
      ユーザーに見える ID ならまったく的外れな理由でもないが、もちろん完璧な防止にはまったくならない
    • I と O をすでに除外し、さらに U まで外すと、荒っぽく見える 3 文字や 4 文字の組み合わせをかなり多く排除できる
      もちろん A があるのでまだ可能な組み合わせはあるが、可能性はかなり低い
    • 真のラテン語原理主義者にとっては、U はキケロの時代には存在しなかったので、猥褻に近いほど下品な文字である
    • こういうのは他にもある: base58 は Satoshi/Bitcoin の方式 https://en.wikipedia.org/wiki/Binary-to-text_encoding#Base58、「base62」は Keybase の saltpack https://github.com/keybase/saltpack、有名な「Adobe 85」 https://en.wikipedia.org/wiki/Ascii85、basE91 https://base91.sourceforge.net
      会社では QR コード向けに新しい「基数」をいくつも定義したが、個人的にはコンピューターサイエンスであまり活用されていない領域だと思う
    • Crockford より 4 年ほど前に、同僚とほぼ同じ文字集合を考え出したことがある
      URL スラッグの問題を解いていて、長さがかなり長かったので、1 バイトあたり 5 ビットなら手書き転記の不便を減らせると考えた
      結局、さらに数文字を削る余裕があり、みんなが帰宅したあとに二人で座って、罵倒語の侮辱度を順位付けしながら削る文字を決めた
      その後、侮蔑表現のほうがより大きな問題だと説得して、u の代わりに n を削る方向へ重きを置いた
      tggr はただかわいいだけだが、n**r は複数の HR チームと気まずい会話をしなければならない問題だった
      最終的な文字集合は今では少しあいまいだが、たいてい [a-z][0-9] を扱い、URL に使えない記号や読み上げにくい記号が多かった
      記憶では 0、l、1 をすべて除外し、転記はすべて大文字かすべて小文字で行われると想定していた気がする
      0o は問題ではなく、1L も同様だった

  • Crockford エンコーディングはあまり好きではない
    実際、この方式でエンコードされた値を技術サポートしたり分析したりすると、明らかな失敗だったと感じた
    このアルファベットは、電話で識別子を読み上げるような、実際にはまれな目的に合わせて設計されており、曖昧さを持ち込んでいる
    エンコード文字列そのものでログを grep したり突き合わせたりする状況では災難で、ハイフンまで許すためコピー&ペーストや改行に関するエラーの大きな原因にもなる
    オブジェクト識別子を直接タイプすることはまれだが、アプリケーション・チャット・フォーラムの間でコピー&ペーストし、メールで送り、ログファイルで検索することはよくある
    こうした条件では発音しやすさは無意味で、大文字小文字を区別しないことは邪魔になり、一貫性とペースト耐性・改行耐性が必要になる
    base58 はこうした要件により適した全単射エンコーディングで、しかもより短い
    Stripe に触発されて、ここ数年 user_1BzGURpnHGn6oNru84B3Ri のような型プレフィックス付き base58 エンコード UUID をオブジェクト識別子として使っている
    ただし、Douglas Crockford の base32 エンコーディングは 20 年前、利用環境がかなり異なっていた時代に設計された点は考慮すべきだ

    • base58 や base64url も検討し、より短いエンコーディングは気に入っていた
      ただ、大文字小文字の区別を前提にしたくなかったので、最終的には base32 側に傾いた
      たとえば ID をファイル名として使いたいこともあるし、大文字小文字を区別しないファイルシステムに縛られた環境かもしれない
      TypeID は Crockford アルファベットを常に小文字で使っているのであって、Crockford エンコーディング規則全体を使っているわけではない
      TypeID ではハイフンは許可されず、曖昧な文字を別の文字で書いて同じ ID を複数の方法でエンコードすることも許されない
    • 電話で識別子を読み上げることはまれだという点には同意する
      ただし、スクリーンショットや画面共有に映った識別子や、識別子を簡単に取り出せない別のデバイスから、たまに手入力することはある
    • base58 や KSUID が使う base62 には利点が多い
      Crockford base32 も動作はするが、そこまで気に入ってはいない
      個人的には型プレフィックス付き KSUID を使うのが第一候補だ
      base62 エンコードの 160 ビット K-整列可能 ID が得られ、互換性のために 128 ビット ID がどうしても必要な場合でなければよく合う
    • Crockford Base32 にハイフンがどこにあるのかわからない: https://en.wikipedia.org/wiki/Base32#Crockford's_Base32
      好きな base32 エンコーディングは z-base-32 で、見た目がより楽だと感じる: https://philzimmermann.com/docs/human-oriented-base-32-encod...
      base58 の最大の問題は、整数にはよく合うが暗号鍵のような任意のバイナリデータにはあまり向かず、大文字小文字を区別する文字列は見栄えがよくない点だ

  • すっきりしている
    「型安全な」prefix が気に入った
    うちの ORM では、似たようなものとして DB 内の整数 ID にエンティティごとのタグを自動で付ける方式を tagged ids と呼んでいた: https://joist-orm.io/docs/advanced/tagged-ids
    区切り文字には : を使っていたが、ダブルクリックでコピー＆ペーストする観点では _ を使わなかったのを少し後悔している
    理論上は、Joist に「DB の UUID カラム」を「ドメインモデルの TypeID」に変換させるのもとても簡単なはずだが、現状ではユーザー側の設定だけではできなさそうだ
    それでも良いアイデアだ

    • Reddit も似ているが、文字列長に最適化された方式を使っている
      要素 ID は t3_15bfi0 のような形で、t3_ は型 prefix だ
      t3 は投稿、t1 はコメント、t5 はサブレディットで、残りは自動増分主キーの base36 エンコーディングになっている
    • うちの会社の型付き内部 ID システムは最初はコロンを区切り文字にしていたが、すぐにピリオド（.）へ変更した
      コロンは URL エンコーディングで % エンコードされて ID の長さが増え、URL が不格好で長くなってかなりいらだった

  • UUIDv7 はここ数年 HN で人気だが、いつ正式な標準になって、ライブラリ・データベース・そのほかのエコシステムがいつネイティブ対応するのか気になる

    • どんな対応を期待しているのかよく分からない
      ほとんどのソフトウェアは UUID 内部の特定ビットを気にしないので、今日でも使えるはずだ
      特定ビットを気にするソフトウェアがあるなら UUIDv4 のように見せかければよく、そうしたビットもランダムに生成できる
      生成手順が必要なら自分で書けばよく、難しくない
    • IETF では標準化の最終段階にあるようだ: https://datatracker.ietf.org/doc/draft-ietf-uuidrev-rfc4122b...
    • 草案と改善を重ねてきており、標準化にはかなり近づいていて、すでに多くのライブラリがサポートしているか新機能を追加している
      たとえば私は Dart の UUID ライブラリをメンテしているが、最新のベータ版メジャーリリースには v6、v7、カスタム v8 が入っている
      実装一覧もどこかにあり、そのページにはライブラリメンテナー一覧として載っているので、新しい草案が出るたびに著者たちへの通知を受け取っている

  • 「ダブルクリックでコピー＆ペーストできる」という点が良い
    細部が重要だ

  • UUID には少し不満がある
    なぜ UUID のバージョニングのような儀式をせず、単に 時間 + 乱数 を組み合わせてはいけないのか分からない
    局所性が重要でないなら 128 ビット乱数をそのまま使えばいい
    経験上、多くの人は UUID を人間が読みやすい16進表現、しかもハイフン付きで保存すべきだと思っているようだ
    データベース、ネットワーク、メモリで空間を無駄にしすぎる

    • 同じことを考えた人は多い
      たとえば ULID https://github.com/ulid/spec はより短く、時間を保持して辞書順に並べ替えられる
    • UUID まわりでは、1つのユースケースが全体を代表しており、したがって最良の UUID 形式は1つだ、という言い方をしがちな傾向がある
      現実には他の工学的問題と同じで、要件を書き出して何が解決してくれるかを見ればよい
      さまざまな形式の利点を読むのは、他人が苦労して学んだことを活用できるので役に立つ
      ソート可能性や時間ベースの局所性は自然には思いつかないかもしれないが、必要なら、プロジェクトの4年後にそのデータを捨ててしまったと気づくより前に知っておいたほうがずっとよい
      UUID 形式の中には小さなセキュリティ問題を自ら持ち込むものもあり、UUID v1 の MAC アドレス漏えいのようなものは避けたほうがよい
      既存の解決策が適切なユースケースなら、そのまま使えばよい
      そうでなければ、あまり気にしなくてよい
      個人的には、UUID を最も多く使っている場所では「一意な文字列だけ送ってくれ、安心したければ好きな UUID ライブラリを使ってくれ」と指定していた
      このシステムではデータソースごとに固有の形式があるようだが、それでも問題ない
      1日数万件程度なので規模の問題もなく、UUID でソートする必要もない
      実際の識別子というよりは送信側がメッセージごとに作る一意トークンで、複数のキューがある異種システムで下流への重複到着を検知するためのものだ
      グローバルな一意性も不要で、小さなシャード内で一意ならよく、原理的には時間が経って繰り返されても構わない
      ただし単純さのため、システムは全期間で一意になるよう維持している
      自分で生成する場合は /dev/urandom からデータを読み、base64 でエンコードし、== で終わらない長さを選んでいた
      これも実際の問題のためではなく、見た目の理由だ
    • 時間と乱数を組み合わせても、グローバルな一意性を保証できるわけではない
    • 個人的に価値のある UUID 標準は、単純な乱数である v4 だけだと思う
      それでもなぜハイフンが必要なのかはいまだによく分からないし、他のバージョンには大した意味がないと思う
    • ハイフンの最悪な点は、全体をダブルクリックで簡単にコピー＆ペーストできないことだ

  • UUIDv7やUUIDがどうしても必要でないなら、https://github.com/segmentio/ksuid ははるかに大きなキー空間を提供する
    名前空間が必要なら文字列の prefix を付ければよく、KSUID の衝突可能性はどのバージョンの UUID よりもはるかに小さい
    ソート可能なタイムスタンプを持つ汎用 ID ジェネレーターの中では ksuid が最も良く、ほとんどの言語にライブラリがある
    UUID v1〜v7 は無駄が大きい

    • 型 prefix 付きの KSUID を生成する薄い JavaScript パッケージを公開してある
      追加のビット数を許容できるなら、たいていは問題ないだろうが、KSUID は優れた形式だ
      [1] https://github.com/sophiabits/resource-id
    • ULID に移った理由は、常に小文字なので大文字小文字を区別せずに扱えるからだ
    • 人気のある ksuid ライブラリをいくつかメンテナンスしており、実際に使っているので ksuid は気に入っている
      ただし ksuid の大きな問題は 160 ビットで、PostgreSQL などのデータベースのネイティブ UUID 型に収まらず、性能コストが生じる点だ
      1: https://github.com/svix/rust-ksuid
      2: https://github.com/svix/python-ksuid

  • K-ソート可能というのは素晴らしい概念で、緩やかに順序づけられたキーは多くのユースケースを解決してくれる
    型付きの圧縮文字列表現も気に入っている
    ただ、UUID v7 の意図しない副作用として、セキュリティ問題が多く生じるのではないかと心配している
    UUID をトークンとして使うべきではないし、DB の主キーにもそう使うべきではないが、実際にはそうされている
    UUID v4 は実質的に暗号学的乱数なので、これまで多くのセキュリティ脆弱性が偶然見逃されてきたのだと思う
    UUID v7 では実際の乱数データは 32 ビットに戻るのだと思っていて、UUID は推測可能だという点を開発者によく教育する必要があると考えていた
    修正: v7 UUID の推測可能性については私の見間違いだったようだ
    草案では乱数ビットに CSPRNG を推奨しており、エントロピーは最低 74 ビットで、「推測不可能」になるよう設計されていると書かれている
    セキュリティ関連の用途には「UUID v4」を使えとは書かれているが、おそらくタイムスタンプに関する意味合いなのだろう

    • 興味深い ユーザビリティの問題がある
      UUIDv4 と UUIDv7 という名前だと、どちらがデータベース向きで、どちらがワンタイムトークン向きかをずっと覚えていなければならず、混乱が延々と続くのではないかと思う
      後方互換性のある解決策もよく分からない
      Elixir では v4 UUID を作るときに UUID.uuid4() 関数を使う
      理論上はコード中の利用箇所をスキャンできるだろうが、こうしたことはどれもエラーの可能性を高める
    • 使いどころがあるのは分かるが、過去に v1 や v5 のような部分的に順次な UUID に出会うたびに、いつも誤用されていた
      v3 のようなハッシュベースのものも同様だった
      v4 は単純で、誤用されにくい