同一ミリ秒に生成したULIDの順序は誰が保証するのか

ULIDは「タイムスタンプを先頭に持つので生成順にソートできる」とよく説明されますが、これは半分しか正しくありません。同一ミリ秒内に複数生成した場合、タイムスタンプ部分が完全に同じ値になるため、並び順を決めるのはランダム部分の大小だけになり、生成した順序とは無関係にバラつきます。この問題に対してULIDの仕様は「モノトニック（単調増加）モード」という解決策を用意していますが、これは通常モードとは別の関数を明示的に呼ばないと有効になりません。npm の ulid パッケージの実装を読みながら、何が起きているのかを確認します。

通常モードで順序が崩れる理由

ULIDは48bitのミリ秒タイムスタンプと80bitのランダム値を連結し、Crockford's Base32で26文字に符号化します。文字列としての大小比較がそのままタイムスタンプの大小比較になるのは、先頭10文字がタイムスタンプ部分だからです。ところが同一ミリ秒内でfactory()が返す生成関数を複数回呼ぶと、先頭10文字は毎回同じになり、残り16文字（80bit）は呼び出しごとに新しい乱数で埋まります。文字列としての大小はこのランダム部分の値次第で決まるため、3回目に生成したULIDが1回目より文字列順で前に来ることが普通に起こります。1ミリ秒は短いと思いがちですが、ループでまとめて発行するような処理では簡単に同一ミリ秒内に収まります。

monotonicFactoryのインクリメント処理

ulidパッケージのmonotonicFactoryは、直前に生成したタイムスタンプとランダム部分を関数のクロージャ内に保持しておき、次の呼び出し時のタイムスタンプが前回以下だった場合に限り、ランダム部分をインクリメントしてから返します。

return function ulid(seedTime) {
  if (isNaN(seedTime)) {
    seedTime = Date.now();
  }
  if (seedTime <= lastTime) {
    const incrementedRandom = (lastRandom = incrementBase32(lastRandom));
    return encodeTime(lastTime, TIME_LEN) + incrementedRandom;
  }
  lastTime = seedTime;
  const newRandom = (lastRandom = encodeRandom(RANDOM_LEN, currPrng));
  return encodeTime(seedTime, TIME_LEN) + newRandom;
};

ここでの判定はseedTime === lastTimeではなくseedTime <= lastTimeです。つまりシステムクロックが何らかの理由で巻き戻った場合も「時間が進んでいない」とみなしてインクリメント処理に入ります。タイムスタンプの単調増加を、クロックそのものではなくこの関数が呼ばれた順序で保証している格好です。

インクリメント本体のincrementBase32は、16文字のランダム部分をCrockford's Base32の32進数として扱い、最下位の文字から+1する処理です。

export function incrementBase32(str) {
  let done = undefined;
  let index = str.length;
  let char;
  let charIndex;
  const maxCharIndex = ENCODING_LEN - 1;
  while (!done && index-- >= 0) {
    char = str[index];
    charIndex = ENCODING.indexOf(char);
    if (charIndex === maxCharIndex) {
      str = replaceCharAt(str, index, ENCODING[0]);
      continue;
    }
    done = replaceCharAt(str, index, ENCODING[charIndex + 1]);
  }
  if (typeof done === "string") {
    return done;
  }
  throw createError("cannot increment this string");
}

最下位の文字がZ（Crockford's Base32で最大値）であれば0に戻して桁上がりし、一つ左の文字を見るという、10進数の筆算でやる繰り上がりと同じ処理を32進数でやっているだけです。これにより、同一ミリ秒内で生成された複数のULIDは、ランダム部分が1ずつ増える形で必ず文字列順に並びます。

80bitを使い切るとどうなるか

incrementBase32のwhileループは、16文字すべてがZで繰り上がりが先頭まで突き抜けるとdoneが文字列にならず、最終的にthrow createError("cannot increment this string")に到達します。つまり同一ミリ秒内で80bit（約1.2 × 10^24通り）の組み合わせを使い切ると、新しいULIDを発行する関数はタイムスタンプを進めるのではなく例外を投げて止まります。現実的なアプリケーションで1ミリ秒に2^80回ULIDを生成する状況はまず発生しませんが、「枯渇したら自動でタイムスタンプをずらしてくれる」という挙動ではない点は、無限にリトライできる設計ではないことを意味します。

UUID v7はここをどう扱っているか

UUID v7を定義するRFC 9562は、同一ミリ秒内の順序保証についてオプションの実装方法を3つ挙げているだけで、どれを採用するかはライブラリの実装者に委ねられています。固定bit数のカウンタをrand_aフィールドに置く方法や、ULIDと同じくランダムビットをインクリメントしていく方法などが候補として並んでいますが、仕様としてどれかに決まっているわけではありません。一方でULIDは、仕様書の中に「モノトニックなULID」という変種を明記し、ランダム部分をインクリメントするという具体的なアルゴリズムまで仕様レベルで決めています。実装によって挙動が変わらないという点では、ULIDの方が「同一ミリ秒内の順序」について踏み込んだ設計をしていると言えます。

実務での扱い方