同じミリ秒に作った ULID 1000件は、並べ替えると生成順にならない

背景

自分のツールサイトに ULID をまとめて生成するページを置いています。
https://hashitosystem.com/tools/ulid/
ボタンを押すと、最大1000件を一気に作って1行ずつ並べる、というだけのツールです。
「ULID は並べ替えると時刻順になる」とよく聞くので、なんとなく「1000件も作った順に並ぶんだろう」と思い込んでいました。
実際に並べ替えてみたら、ぜんぜん違いました…。
仕様を読み直したら、ちゃんと書いてあったので整理しておきます。

ULID をざっくり

ULID は、時刻順に並べられるように設計された128ビットの識別子だ。
仕様は GitHub で公開されています。
https://github.com/ulid/spec
前半48ビットが UNIX 時刻（ミリ秒）、後半80ビットが乱数で、これを Crockford の Base32（I・L・O・U を除いた32文字）で26文字にしたものです。
時刻部が10文字、乱数部が16文字になる。

よく比べられる UUID（ランダムに作る128ビットの識別子で、v4 は全体がほぼ乱数）と違って、先頭が時刻なので文字列のまま辞書順に並べると時刻順になります。
データベースの主キーにしたとき、新しい行が末尾に寄るのが嬉しい、というのが ULID がよく使われる理由だと思います。

試したこと

ツールの生成処理を Node.js にそのまま移して、同じ Date.now() で1000件作り、sort() したら作った順と一致するかを数えました。
encodeTime が時刻部、encodeRandom が乱数部を作る関数で、ツール本体と同じ書き方です。

const crypto = require('node:crypto');
const ENC = '0123456789ABCDEFGHJKMNPQRSTVWXYZ'; // Crockford Base32

function encodeTime(t, len) {
  let s = '';
  for (let i = len - 1; i >= 0; i--) { const mod = t % 32; s = ENC[mod] + s; t = (t - mod) / 32; }
  return s;
}
function encodeRandom(len) {
  const bytes = crypto.randomBytes(len);
  let s = '';
  for (let i = 0; i < len; i++) s += ENC[bytes[i] % 32];
  return s;
}
const ulid = (now) => encodeTime(now, 10) + encodeRandom(16);

const now = Date.now();
const arr = [];
for (let i = 0; i < 1000; i++) arr.push(ulid(now));
const sorted = [...arr].sort();
let same = 0;
for (let i = 0; i < arr.length; i++) if (arr[i] === sorted[i]) same++;
console.log('生成順のまま並んでいる位置:', same, '/ 1000');
console.log(arr.slice(0, 3));

Node.js v24 で実行した結果です。

生成順のまま並んでいる位置: 0 / 1000
[
  '01M4HV3A1D4WZRFKBBQ62T7DND',
  '01M4HV3A1DT3X119G0BFTENGED',
  '01M4HV3A1DDM6E0P7B59A2FCSD'
]

時刻部の 01M4HV3A1D は全部同じで、その後ろの乱数部だけで並び順が決まっている。
乱数なので、作った順とはまったく関係のない順番になります（0件なのはたまたまで、毎回少しは変わるはずです）。

仕様にも、同じミリ秒の中では並び順は保証されない、とはっきり書かれていました。
「時刻順に並ぶ」はミリ秒の粒度まで、ということですね。

同じミリ秒でも順番を保つ（monotonic）

仕様には、これを解決するための monotonic（単調増加）という生成方法も書かれています。
同じミリ秒にもう一度作るときは、乱数を引き直さずに前回の乱数部に1を足す、というものだ。
乱数部が全部 Z で桁あふれするときは、生成を失敗させる（エラーにする）と決められています。

下記は、上のコードの encodeTime と encodeRandom をそのまま使った monotonic 版です。
前回の時刻と乱数部をクロージャに持っておき、時刻が同じなら乱数部の末尾から繰り上げながら1を足します。

function makeMonotonic() {
  let lastTime = -1, lastRand = null;
  return function (now) {
    if (now === lastTime) {
      const r = lastRand.split('');
      let i = r.length - 1;
      while (i >= 0) {
        const v = ENC.indexOf(r[i]);
        if (v < 31) { r[i] = ENC[v + 1]; break; }
        r[i] = '0'; i--; // Z なら 0 にして上の桁へ繰り上げ
      }
      if (i < 0) throw new Error('random overflow');
      lastRand = r.join('');
    } else {
      lastTime = now;
      lastRand = encodeRandom(16);
    }
    return encodeTime(now, 10) + lastRand;
  };
}

const mono = makeMonotonic();
const arr2 = [];
for (let i = 0; i < 1000; i++) arr2.push(mono(now));
const s2 = [...arr2].sort();
let same2 = 0;
for (let i = 0; i < 1000; i++) if (arr2[i] === s2[i]) same2++;
console.log('単調増加版:', same2, '/ 1000');
console.log(arr2.slice(0, 3));

結果は下記です。

単調増加版: 1000 / 1000
[
  '01M4HV3A1DMTV4XHQGY5FHEMMZ',
  '01M4HV3A1DMTV4XHQGY5FHEMN0',
  '01M4HV3A1DMTV4XHQGY5FHEMN1'
]

末尾が MZ → N0 → N1 と1ずつ増えていて、Z の次で繰り上がっているのがわかると思います。
1000件すべてが作った順のまま並びました。

どちらを使うか

monotonic にすると、同じミリ秒の ULID は前の1件から推測できるようになります（乱数部が1違うだけなので）。
ID から次の ID を当てられたくない用途では、これは弱点です。
逆に、ログのように「同じミリ秒でも発生順に並んでほしい」用途では、monotonic でないと意味がありません。
私のツールはテストデータ用にまとめて作るのが主な使い道なので、いまは乱数を毎回引き直す方式のままにしています。
ちなみに乱数部は bytes[i] % 32 で文字を選んでいますが、256 は 32 で割り切れるので、この割り算で特定の文字が出やすくなる偏りは生じません。

結論

ULID を辞書順に並べて時刻順になるのはミリ秒単位までで、同じミリ秒に作った分は乱数部の大小で並ぶので、生成順は保たれません。
同じミリ秒の中でも順番を保ちたいなら、仕様の monotonic 方式どおり前回の乱数部に1を足し、桁あふれしたら生成を失敗させます。
推測されにくさが要るなら毎回引き直す、発生順が要るなら monotonic、と用途で選ぶのが正解です。

---

本記事はAI補助で執筆した、個人開発の紹介記事です。