ULIDとは？ソート可能な一意識別子を解説する
ランダムなUUIDv4を主キーとして挿入するたびに、その値はデータベースのインデックス上の予測できない位置に着地する。これを数百万回繰り返すと、インデックスは断片化し、キャッシュは荒れ、書き込みは遅くなる。ULIDはこの問題を解決するが、UUIDで気に入っていた性質を犠牲にはしない。中央のコーディネーターなしで、どこからでも生成できる点はそのままに、値が散らばるのではなく時系列順に着地するようになる。
では、26文字の文字列がどうやって自分自身を時間順に並べるのか。それこそがこの仕組みの肝であり、ULIDを使う前に理解しておく価値がある。
ULID（Universally Unique Lexicographically Sortable Identifier）とは、26文字のCrockford Base32で表記される128ビットの識別子だ。先頭10文字はミリ秒単位のタイムスタンプを、末尾16文字はランダムなビットをエンコードする。そのため、後から生成されたULIDは、ただの文字列として比較したときに必ず先に生成されたものより後に並ぶ。オフラインで生成できるソート可能な一意識別子である。
このガイドでは、その内部を分解していく。アナトミーを1文字ずつデコードし、本当にソートされることを証明し、データベース上の利点を支えるB-treeの数理を示し、埋め込まれたタイムスタンプが何を漏らすのかを正直に検討する。読みながらULID 生成ツールで実際の値を試せる。生成し、デコードし、UUIDに変換してみるとよい。
ULIDとは何か
ULID（Universally Unique Lexicographically Sortable Identifier）とは、UUIDよりもソートしやすく、よりコンパクトな代替として設計された128ビットの識別子だ。26文字のCrockford Base32で表記される。先頭10文字はUnix epochからの経過ミリ秒を表す48ビットのタイムスタンプを保持し、残りの16文字は80ビットのランダム性を保持する。時間が先頭に来るため、文字列は時系列順にソートされる。
この最後の性質こそ、このフォーマットが存在する理由だ。UUIDv4は完全にランダムで、一意性の点では優れているが、1秒違いで生成された2つのIDの間には何の関係もない。ULIDは、調整不要でどこでも生成できるモデルを保ったまま、その上に時間順序を加える。だからULIDの列は、追加の手間なしに自然と生成時刻順に並ぶ。
フォーマットを一目で見るとこうなる。
| 項目 | 値 |
|---|---|
| ビット数 | 128 |
| エンコード | 26文字のCrockford Base32 |
| 構成 | 48ビットのタイムスタンプ + 80ビットのランダム性 |
各要素の中身は以降の節で埋めていく。エンコードとソート可能性はそれぞれ独立した節に値するので、Base32と順序の証明はこの後すぐに扱う。まずは構成からだ。
ULIDのアナトミー：48ビットの時刻 + 80ビットのランダム性
ULIDの26文字は、きれいに2つの半分に分かれる。先頭10文字がタイムスタンプ、末尾16文字がランダム部分だ。代表的な例を並べると、その境界は一目瞭然である。
01ARYZ6S41 TSV4RRFFQ69G5FAV
└────────┘ └──────────────┘
10 chars 16 chars
48-bit ms 80-bit random
timestamp2つのコンポーネント、2つの役割。一方は「いつ」を記録し、もう一方は「一意性」を保証する。それぞれをデコードしていこう。
48ビットのタイムスタンプ（先頭10文字）
先頭の10文字は48ビットの整数をエンコードする。それは、ULIDが生成された瞬間のUnix epochからの経過ミリ秒だ。仕様書に載っている代表的な例をそのまま取り上げよう。
01ARYZ6S41 -> 1469918176385 ms -> 2016-07-30T22:36:16.385Zこれは実際に可逆なデコードだ。01ARYZ6S41TSV4RRFFQ69G5FAVをデコーダーに貼り付ければ、ちょうど2016-07-30T22:36:16.385Zが返ってくる。時刻コンポーネントはハッシュではなく素のデータなので、読み取りにコストはかからない。
人がつまずきがちな細かな点が1つある。ULIDの最初の文字は必ず0から7の間になる。Crockford文字は5ビットを保持し、48ビットは5の倍数ではない。タイムスタンプは10文字が運べる50ビットのうち下位48ビットを占め、最初の文字の上位2ビットは恒久的にゼロのまま残る。2つのゼロビットによって、その文字の値は7が上限となる。もし8以上で始まるULIDを見かけたら、それは不正な値だ。
80ビットのランダム性（末尾16文字）
残りの16文字は80ビットのランダム性を運び、この半分が一意性を生み出している。これらのビットは暗号学的に安全なソースから得るべきだ。ブラウザではMath.randomではなくcrypto.getRandomValuesを使う。この違いは重要だ。Math.randomは攻撃者が値を推測したり衝突させたりできる程度に予測可能だが、CSPRNGはそうではない。
80ビットとはどれほどの余地なのか。おおよそ1.2 × 10²⁴通りの値があり、しかもそれはミリ秒あたりだ。たとえ単一のミリ秒の中で数百万のULIDを生成しても、2つが同じ80ビットを引く確率はごくわずかなままにとどまる。タイムスタンプと違い、この半分にはデコードできる意味はない。すべてのULIDを区別することだけを目的とした、ただのノイズである。
CrockfordのBase32：なぜULIDはI, L, O, Uを外すのか
ULIDはCrockfordのBase32でエンコードされる。これは32個のシンボルからなるアルファベットで、数字0〜9と、4文字を除いた英字A〜Zで構成される。
0123456789ABCDEFGHJKMNPQRSTVWXYZ欠けている文字はI, L, O, Uだ。3文字は数字に似ているため除かれている。IとLは1に、Oは0に似ているので、画面上でULIDを読む人が英字を数字と取り違えずに済む。その裏返しとして入力には寛容だ。準拠したデコーダーはIとLを1に、Oを0に戻し、文字列全体を大文字・小文字を区別せずに扱う。Uは別の理由で除外されている。偶然にも不快な単語を綴ってしまうのを避けるためだ。
ビットの計算がもう1つの理由だ。各Base32文字は5ビットをエンコードするのに対し、16進数の文字は4ビットしかエンコードしない。1文字あたり5ビットで128ビットを詰め込むなら26文字で済む。同じ128ビットを、UUIDのように1文字あたり4ビットで詰め込むと32文字に加えて4つのハイフンが要り、合計36文字になる。だからULIDはUUIDより明確に短く、ハイフンもないので、エスケープなしでURL、ファイル名、ヘッダーにそのまま収まる。
CrockfordのBase32は、1文字あたり5ビットをエンコードする32個のシンボル（0〜9と、I, L, O, Uを除いたA〜Z）からなるアルファベットだ。ULIDはこれを使って128ビットを、大文字・小文字を区別しないURLセーフな26文字に詰め込む。そして決定的に重要なのは、このアルファベットが昇順に並んでいることだ。これこそが、エンコードされた文字列を生のビットと同じ順序でソートさせる仕組みである。
なぜULIDは時間順にソートされるのか
多くの記事はULIDが時間順にソートされると述べる。だがなぜそうなるのかを示すものは少ない。そこで、実際の論証を示そう。これは、すでに手元にある2つの事実に基づいている。タイムスタンプが値の最上位部分であること、そしてCrockfordのアルファベットが昇順に並んでいることだ。
この2つを組み合わせると、次の等価の連鎖が得られる。
string compare == 128-bit integer compare == creation-time compare左から右へ読もう。2つのULIDを1文字ずつ比較すること（文字列ソートのやり方）は、それらの背後にある128ビット整数を比較するのと同じ答えを与える。なぜならアルファベットが順序を保つからだ。「より上位の」文字は常により大きい値を意味する。128ビット整数を比較することは、生成時刻を比較するのと同じ答えを与える。なぜならタイムスタンプが最上位ビットに位置し、比較を支配するからだ。ランダムな末尾は、同じミリ秒内での同点を決着させるだけの役割しか持たない。文字列の順序、ビットの順序、時間の順序は、すべて同じ順序なのである。
簡単な実演をしよう。1ミリ秒違いで生成された2つのULIDだ。
01ARYZ6S41... (created at T)
01ARYZ6S42... (created at T + 1 ms)10文字目が1から2へと刻まれ、ただのテキストソートが2番目を1番目の後に並べる。タイムスタンプ列も特別な比較器も要らない。次の節で詳しく述べる実務上の見返りは、たった1行だ。ORDER BY idが、追加のインデックスなしに行を時系列順で返す。
データベースの主キーとしてのULID：B-treeの局所性
ここがULIDの真価を発揮する場面だ。ほとんどのリレーショナルデータベースは主キーのインデックスをB-treeとして格納する。そして、新しいキーがそのツリーのどこに着地するかが、挿入のコストを決める。
ランダムなUUIDv4は、挿入のたびに予測できないどこかに着地する。
UUIDv4： 新しいキーはそれぞれランダムなリーフページを狙う。そのページはしばしば満杯なので、エンジンはページを分割し、行の半分を別の場所にコピーし、ツリーのあちこちのページを汚す。数百万行を通じてこれがインデックスを断片化させ、有用なページをバッファキャッシュから追い出し、挿入のスループットを引き下げる。（具体的なインデックスのページ分割の数値、書き込みの多いテーブルでは典型的に2〜10倍の差については、比較ガイドを参照してほしい。）
時刻を先頭に置いたULIDは、毎回末尾に着地する。
ULID： 上位ビットがタイムスタンプなので、新しいキーはそれぞれ前のものより大きく、インデックスの右端かその近くに追加される。挿入はシーケンシャルなまま、ページ分割はほぼ消え、インデックスはコンパクトに保たれ、ある時間幅にわたるレンジスキャンは連続したページの並びを読む。
UUIDの調整不要な生成と、オートインクリメント整数の挿入局所性の両方が手に入る。しかも、推測しやすいシーケンシャルなカウンターを露出させることはない。ランダムな末尾が、次の値を正確には隠し続けるからだ。
ストレージのヒント： 128ビットは26文字のテキストフィールドではなく、16バイナリバイトとして格納する。PostgreSQLではuuid列、MySQLではBINARY(16)だ。テキストフィールドは領域を無駄にし、インデックスを肥大化させる。Base32文字列へのエンコードは、人やURLが目にする境界でだけ行う。生成ツールのConvertタブは、まさにこのためにULIDをUUIDに変換してくれる。2つの形式は同じ128ビットだからだ。
単調なULID：ミリ秒内での厳密な順序
ソート可能性の証明には、正直に言うと1つの隙間がある。単一のミリ秒の中では、通常のULIDは厳密には順序付けられていない。それらは同じ10文字の時刻プレフィックスを共有するが、80ビットのランダムな末尾は独立に引かれるため、同じミリ秒の2つのULIDのどちらが先にソートされるかは、本質的にコイン投げだ。たいていの用途ではこれで問題ない。サブミリ秒のレートでも厳密な順序が必要なときには、問題になる。
単調生成がこの隙間を埋める。ルールは単純だ。あるミリ秒の最初のULIDは通常どおり新しいランダム性を得て、その同じミリ秒内の後続のULIDはすべて、直前の80ビットのランダム値を取り、それに1を加える（ビッグエンディアンの整数として扱い、必要に応じて上位ビットへ繰り上げる）ことで生成される。したがって各値は、その1つ前の値より厳密に大きくなる。
単一のミリ秒内で生成されたバッチを見れば確認できる。最後の文字だけが動いている。
01KVT0F720ZK9N4T2QX7VR8WMC
01KVT0F720ZK9N4T2QX7VR8WMD
01KVT0F720ZK9N4T2QX7VR8WME…WMC < …WMD < …WMEが保証される。これは、行がミリ秒クロックが刻むより速く生成されうるときに常に重要になる。高スループットの挿入、イベントログ、タイトなループ内のメッセージIDなどだ。クロックが次のミリ秒に進むと、生成は新しいランダム性に戻り、このサイクルが繰り返される。
ULID対UUID：どちらをいつ使うか
多くの人が実際に抱えてやってくる問いは、ULID対UUIDだ。ここに的を絞った比較を示す。ULIDと、現実的に天秤にかけるであろう2つのUUIDバージョンとの対比だ。（SnowflakeやNanoIDを含む5者の意思決定マトリクス全体については、ULID、UUID、Snowflakeの完全な比較を参照してほしい。）
| 項目 | ULID | UUIDv4 | UUIDv7 |
|---|---|---|---|
| 長さ | 26文字 | 36文字 | 36文字 |
| エンコード | Crockford Base32 | ハイフン区切りの16進数 | ハイフン区切りの16進数 |
| 時間順にソート可能？ | はい | いいえ | はい |
| タイムスタンプを埋め込む？ | はい（48ビットms） | いいえ | はい（48ビットms） |
| 標準化されている？ | コミュニティ仕様 | RFC 9562 | RFC 9562 |
| 最適な用途 | 短くソート可能なID | 不透明なランダムID | UUID形式でソート可能なID |
文章で言えば、最短でURLセーフ、かつソート可能な文字列が欲しいときはULIDを選ぶ。埋め込まれた時刻を持たない、不透明で完全にランダムな識別子が欲しいときはUUIDv4を選ぶ。たとえば、いつ作成されたかを明かしたくない公開トークンなどだ。時間順序が必要だが標準のUUID形式の中にとどまる必要があるとき、つまりバージョンビットとバリアントビットを固定の位置に置き、そのまま収められるネイティブなuuid列が必要なときはUUIDv7を選ぶ。
3つともすべて128ビットなので、ULID ↔ UUIDの変換はどちらの向きにも可逆だ。ULIDとulid vs uuid v7の関係は、見かけより近い。UUIDv7は、本質的に、ULIDが先駆けた時刻先頭の同じ発想を、IETFが標準化したものだからだ。もしそもそもUUIDに不慣れなら、まず基礎から始めて、それからこの比較に戻ってくるとよい。
プライバシーのトレードオフ：ULIDは生成時刻を漏らす
埋め込まれたタイムスタンプは、誰がそのIDを読むかによって、機能にもなれば漏洩にもなる。ULIDを持っている人は誰でも、たった一手でタイムスタンプをデコードし、そのレコードが生成された正確なミリ秒を知ることができる。あなたのデータベースへのアクセスは一切要らない。
自分のシステムの内部であれば、これは純粋な利点だ。レコードをその場で監査でき、順序付けはタダで手に入り、デバッグも楽になる。だが公開向けの識別子では、これは本物の情報開示になる。生成時刻そのものがビジネス上機微でありうるし、時間をかけてサンプリングされた一握りのULIDは、あなたの生成レートを漏らす。1秒あたりにいくつの注文、アカウント、メッセージを生み出しているか、という競合やスクレイパーが推定したがる類の情報だ。
公平を期すなら、これはUUIDv1より狭い漏洩だ。UUIDv1は歴史的に生成マシンのMACアドレスを埋め込んでいた。ULIDが露出するのは時刻だけで、ハードウェアの素性は決して露出しない。それでも、よく検討すべきだ。単純な緩和策はこうだ。ULIDは内部に留め、順序が問題にならない公開向けのIDには、完全にランダムなUUIDv4を渡す。
ULIDでよくある落とし穴
ULIDの厄介事のほとんどは、フォーマットのバグではなく、避けられる一握りのエンジニアリング判断だ。繰り返し現れるものを挙げる。
- 同じミリ秒の通常のULIDが順序付けられていると思い込む。 それらは時刻プレフィックスを共有するが、独立したランダムな末尾を持つので、順序は未定義だ。対処： サブミリ秒のレートで厳密な順序が必要なときは単調モードを使う。
- ULIDを26文字のテキストとして格納する。 領域を無駄にし、インデックスを膨らませる。対処： 128ビットを16バイト（
uuid/BINARY(16)）として格納し、Base32へのエンコードは境界でだけ行う。 - ULID→UUID変換がv4やv7として報告されると期待する。 変換は同じビットを再エンコードするだけで、UUIDのバージョンフィールドとバリアントフィールドを設定しない。だからそれらを検査するライブラリは、タグ付けされたバージョンを見つけられない。対処： 結果を不透明な128ビット値として扱うか、タグが必要なら本物のUUIDv7を生成する。
- ランダム性を
Math.randomで埋める。 予測可能で、衝突しうる。対処： 常にcrypto.getRandomValuesのようなCSPRNGを使う。 - タイムスタンプの漏洩を検討せずにULIDを公開する。 上のプライバシーの節を参照。対処： 内部にはULID、公開IDにはランダムなUUIDv4を。
I,L,O,UをULIDに手入力する。 これらの文字はアルファベットになく、打ち直しはエラーを招く。対処： ULIDはコピーし、打ち直さない。
FAQ
ULIDはUUIDのような公式の標準なのか？
いいえ。ULIDはGitHubで公開されたコミュニティ仕様であり、IETFのRFCではない。広く実装され安定しているが、その背後に標準化団体はない。標準化された時間順の識別子が必要なら、UUIDv7（RFC 9562）が同じ発想を公式のUUID形式の中に適用している。
ULIDは何文字で、なぜUUIDより短いのか？
26文字、UUIDの36文字に対してだ。ULIDはCrockford Base32を使い、1文字あたり5ビットを詰め込む。UUIDの16進数は4ビットしか詰め込めず、さらに4つのハイフンを加える。したがって同じ128ビットでも、Base32なら少ない文字数で済み、そのどれもURLエスケープを必要としない。
2つのULIDが衝突することはあるのか？
実質的に決して起きない。1ミリ秒の中で、ULIDは80ビットのランダム性を持つ。おおよそ1.2 × 10²⁴通りなので、ミリ秒あたり数百万を生成しても、衝突の確率はごくわずかなままにとどまる。唯一の要件は、暗号学的に安全なRNGがランダム性を埋めることだ。Math.randomはこの保証を無効にする。
ULIDをPostgreSQLやMySQLに格納できるか？
できる。ULIDは128ビットなので、UUID形式に変換してuuid列（PostgreSQL）またはBINARY(16)（MySQL）に格納し、Base32文字列のレンダリングは境界でだけ行う。ネイティブなULID列型は存在しないが、UUID表現も同じ16バイトのコストで済み、インデックスをコンパクトに保つ。
ULIDは大文字・小文字を区別するのか？
正規の形は大文字だが、Crockford Base32は入力では大文字・小文字を区別しない。デコーダーは小文字も同じように読み、I/Lを1に、Oを0にマップする。等価判定やインデックスでの予期せぬ事態を避けるには、格納や比較の前に1つのケースに正規化しておくとよい。
48ビットのタイムスタンプはいつか枯渇するのか？
とても長い間しない。48ビットのミリ秒は、カウンターがオーバーフローするまでに10889年に達する。だからタイムスタンプコンポーネントは、現実のどんなアプリケーションにとっても事実上将来にわたって安全だ。フォーマットが余地を使い果たすずっと前に、あなたはシステムも言語もデータベースも入れ替えているだろう。
サーバーなしでブラウザやモバイルでULIDを生成できるか？
できる。それが中核的な利点だ。ULIDは中央のコーディネーターを必要としないので、どんなノード、エッジワーカー、ブラウザ、デバイスでも、自分のクロックと安全なRNGから1つを生成できる。異なるマシンで生成された値も、その後で時間順にきちんと並ぶ。タイムスタンプがID自身の中に存在するからだ。
まとめ
ULIDは、特定の現実的な問題、つまりランダムなキーがインデックスを断片化させる問題を、分散的な生成を奪うことなく解決する。その仕組みは覚えておく価値がある。
- ULIDは48ビットのミリ秒タイムスタンプ + 80ビットのランダム性であり、26文字のCrockford Base32としてエンコードされる。
- 時間順にソートされるのは、タイムスタンプが最上位のコンポーネントであり、アルファベットが順序を保つからだ。文字列の順序が時間の順序に等しい。
- その順序付けが、ランダムなUUIDv4に欠けている挿入局所性をB-treeに与え、書き込みを速く、インデックスをコンパクトに保つ。
- 同じミリ秒内で生成されるIDに厳密な順序が必要なときは、単調モードを使う。
- 公開向けの識別子としてULIDを露出する前に、タイムスタンプの漏洩を検討する。
- 標準のUUID形式の中にとどまらなければならないときは、代わりにUUIDv7を選ぶ。
実際に使う準備ができたら、ULID 生成ツールを開いて、ブラウザ内だけでULIDを生成し、デコードし、変換してみてほしい。サーバーなし、アップロードなし、何も保存されない。