ショートコードの生成:Base62、ハッシュ、ランダムコードの比較

ショートコードの生成は、4つの選択肢に集約されます。一意のカウンタを base62 でエンコードする、ランダムな文字を引く、URL のハッシュを切り詰める、コーディネーターから ID の範囲を配る、のいずれかです。カウンタは衝突しませんが、推測できます。ランダムなコードは推測できませんが、リトライの経路が必要です。ハッシュの切り詰めは4つの中で最も弱い方式です。思ったより早く衝突し、他の方式にないものは何も与えてくれないからです。

ほとんどは数字で決まるので、この記事ではそれを順に見ていきます。7 文字の base62 コードには、ちょうど 3,521,614,606,208 個の値があり、ランダムなコードは、約 220 万本のリンクの時点で、少なくとも1回衝突する確率が 50% になります。最初の事実は、7 文字を途方もなく大きく感じさせます。2番目の事実は誕生日問題の限界で、「何兆通りもある」ことが「衝突しない」ことを意味しない理由です。

コードの周りのシステム全体 (ストレージ、リダイレクト、キャッシュ) を知りたい場合は、URL 短縮ツールの作り方から始めてください。この記事は、その解説の中の1つの判断、つまりショートコードをどこから得るかを拡大したものです。

自動増分 ID の Base62 エンコーディング

base62 エンコーディングは、数値を 62 種類の記号 0-9、a-z、A-Z による文字列に変換します。アルファベットが大きい 16 進数と同じ考え方で、記号を使わずに整数を URL セーフな文字列にする最短の形式です。ID 125 は 21 (2 x 62 + 1)、1,000,000 は 4c92 になります。

const ALPHABET =
  "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";

export function encode(id: bigint): string {
  if (id === 0n) return ALPHABET[0];
  let out = "";
  while (id > 0n) {
    out = ALPHABET[Number(id % 62n)] + out;
    id /= 62n;
  }
  return out;
}

export function decode(code: string): bigint {
  let id = 0n;
  for (const ch of code) id = id * 62n + BigInt(ALPHABET.indexOf(ch));
  return id;
}

強みは、一意性がデータベースから受け継がれることです。41,000,000 行目には1つのコードが付き、他の誰にもそのコードは付きません。リトライのループも、挿入前の検索もありません。コードの長さの伸びもゆっくりで、62^6 未満の ID は6文字以下のコードになり、最初の 7 文字のコードは ID 56,800,235,584 で現れます。

弱点は、露出です。コードは行番号を言い換えたものにすぎないため、decode("4c92") は 1000000 を返します。誰でもリンクの数を数え、1週間離れた2つのサンプルから成長を推定し、すべてのコードを順に列挙できます。社内ツールなら問題ありません。公開の短縮ツールでは、無料のスクレイピング API になり、このブログの別の記事で扱っているオープンリダイレクトと列挙のリスクに関わります。

一意性を失わずに順序を隠すには、エンコードする前に、ID を可逆な置換に通します (小さな Feistel ネットワークが一般的な選択です)。近道には注意してください。62^7 を法とする定数の乗算は、かき混ぜたように見えますが、最後の桁が増え続けることが、簡単なテストで分かります。かき混ぜたカウンタは難読化であり、秘密ではありません。

ランダムコード:キー空間、リトライ、誕生日問題の限界

ランダムなショートコードは、アルファベットから、各文字を独立に引きます。暗号論的な乱数源と、偏りのない選択を使ってください。Node の randomInt(62) は棄却サンプリングを行いますが、byte % 62 は、256 が 62 の倍数ではないため、分布が偏ります。

import { randomInt } from "node:crypto";

export function randomCode(length = 7): string {
  let out = "";
  for (let i = 0; i < length; i++) out += ALPHABET[randomInt(62)];
  return out;
}

コードはどれくらいの長さにすべきでしょうか。キー空間は 62^length で、誕生日問題によれば、N 個の値から n 回ランダムに引いたとき、少なくとも1回重複する確率は、おおよそ 1 - e^(-n²/2N) です。これは、おおよそ sqrt(2N ln 2) 回の抽出で 50% に達します。誕生日問題が直感に反するのは、組み合わせの数が n の2乗で増えるからです。

最後の列が、運用上重要な数字です。規模が大きくなれば、全リンクの中での重複はほぼ確実ですが、コードが実際に経験するのは、1回の挿入が使用済みのスロットに当たることで、その確率はちょうど links / keyspace です。1億本のリンクと 7 文字なら、約 35,000 回の挿入に1回が衝突します。本番で目にすることになるので、リトライの経路が必要ですが、コストは小さいものです。

衝突の処理:判断はデータベースに任せる

機能するパターンは、挿入してからリトライする方式であり、確認してから挿入する方式ではありません。2つのリクエストが、どちらも aB3x9Qz が空いていることを確認し、その後どちらも書き込む可能性があります。コードの列に一意制約を付ければ、その競合は閉じられ、挿入の失敗が、もう一度引き直すための合図になります。

export async function createWithRetry(
  tryInsert: (code: string) => Promise<boolean>, // false = unique violation
  attempts = 5,
): Promise<string> {
  for (let i = 0; i < attempts; i++) {
    const code = randomCode();
    if (await tryInsert(code)) return code;
  }
  throw new Error("could not allocate a short code");
}

ここで tryInsert は INSERT を実行し、一意制約違反のエラーの場合にのみ false を返し、他の失敗では返しません。1回の挿入が確率 p で衝突するなら、すべての試行が失敗する確率は p^attempts です。1億本のリンク、7 文字の時点では、p は 2.84 x 10^-5 なので、3回連続で失敗する確率は約 2.3 x 10^-14 です。それでも試行回数には上限を設けてください。上限に達するのを見たら、キー空間がほぼ満杯か、乱数源が壊れているので、無限ループよりも、目立つエラーのほうがましです。

同じ規律は、作成エンドポイントの冪等性にも当てはまります。リトライされた HTTP リクエストが、2つ目のリンクを発行してはならないからです。その半分は、レート制限と冪等性で扱っています。

ハッシュと切り詰め:思ったより早く衝突する理由

URL をハッシュ化するのは、決定的であるため魅力的に見えます。同じ URL は常に同じコードになるので、重複を調べる検索を省けます。代償は、コードが使えるビット数に限りがあることです。ダイジェストの 32 ビットを取ると、2^32 = 4,294,967,296 個の値になり、衝突確率が 50% になる点は約 77,163 個の URL です。数十億ではありません。7 文字の base62 の断片 (約 41.7 ビット) なら、これが約 220 万に伸びますが、これはランダムな 7 文字のコードと同じです。

import { createHash } from "node:crypto";

export function hashCode(url: string, length = 7): string {
  const digest = createHash("sha256").update(url).digest();
  const n = digest.readBigUInt64BE(0) % 62n ** BigInt(length);
  return encode(n).padStart(length, "0");
}

つまり、切り詰めがハッシュを壊すのではありません。SHA-256 は問題ありません。256 ビット全体の衝突耐性が、41 ビットに切り詰められると維持されないだけです。ランダムなコードの挙動を引き継ぐので、リトライの経路が必要になり、さらに衝突したときの規則 (ソルトを加えて再ハッシュする) も必要です。そして、決定性は不利に働きます。2人の顧客が同じ URL を短縮すると、同じコード、したがって同じクリックストリームになり、アカウント ID を混ぜない限りそれは避けられません。ほぼすべての場合、ハッシュの切り詰めは避けます。重複を排除したいなら、ハッシュ列で URL を検索し、コードは別の方法で生成してください。

カウンタの範囲と Snowflake 方式の ID

複数のリージョンの複数の書き込み側が ID を必要とすると、単一の自動増分列はボトルネックになります。一意性を手放さずにそれを避ける、2つのパターンがあります。

1つ目は、カウンタの範囲です。コーディネーターが、各アプリケーションインスタンスに、たとえば 1,000 個の ID のブロックを配り、インスタンスはリンクごとの往復通信なしに、ローカルでそれらをエンコードします。インスタンスが落ちた場合、使われなかったブロックは単にスキップされます。何兆もあるコード空間の中の欠番は、無害です。

2つ目は、Snowflake 方式の ID です。タイムスタンプ、マシン ID、ミリ秒ごとのシーケンスを 64 ビットに詰め込んだものです。これらは作成時刻順に並び、コーディネーターを必要としません。ショートリンクにとっての問題は長さです。64 ビットの値は最大 18,446,744,073,709,551,615 で、62^10 = 839,299,365,868,340,224 は 2^64 より小さいため、最大 11 文字の base62 が必要になります。あまり短くありません。Snowflake の ID は、公開コードよりデータベースのキーに適しているため、ほとんどの短縮ツールは、それらを内部にとどめ、別の、より短いコードを使います。

どちらも、構造上順序があるため、連番の推測されやすさという問題を引き継ぎます。置換で包むか、内部の主キーとしてのみ使ってください。

カスタムコードと予約語

バニティスラッグは、人間がコードを選ぶ唯一の場所であり、他のすべてと同じ一意制約を通ります。追加の作業は、挿入前の検証です。/spring-sale のようなカスタムバックハーフは、3つの点について確認する必要があります。

• 予約語。アプリケーションや Web がすでに使っているパスは、決して取得できてはいけません。api、admin、login、static、robots.txt、favicon.ico、.well-known です。誰かが /login を登録できる短縮ツールは、フィッシングページの生成器を作ったことになります。
• 生成されたコードとの衝突。ユーザーが /aB3x9Qz を取得した場合、ランダムなジェネレーターは、後で同じ文字列を生成する可能性があります。カスタムコードと生成コードが1つの名前空間を共有している限り、一意制約がそれを処理します。
• 大文字小文字と紛らわしい文字。base62 は大文字小文字を区別するため、/Ab と /ab は別のリンクです。カスタムスラッグを大文字小文字を区別せずに比較するかどうかを決め、0/O や l/1 だけが異なる組み合わせをブロックすることも検討してください。ブランディングの側面は、バニティ URL のガイドで扱っています。

ランダムな 7 文字のコードが、不都合な単語を綴ってしまうこともあります。生成したコードを短いブロックリストに通し、一致したら引き直してください。ほとんどコストはかかりません。

列挙、推測されやすさ、プライバシー

ショートコードはアドレスです。秘密ではなく、どんな長さでもそうはなりません。それでも、連番とランダムの差は大きなものです。連番のコードなら、すべての推測が有効なリンクに当たります。1,000 万本のリンクが 62^7 個の値にランダムに散らばっている場合、当てずっぽうの推測が1本に当たる確率は 10,000,000 / 3,521,614,606,208、つまり約 35 万分の 1 です。スキャナーは、1件見つけるのに数十万回のリクエストが必要で、レート制限とボット検知で、それを罰することができます。

転送先を非公開にしなければならない場合、コードはケーパビリティでなければなりません。つまり、少なくとも 128 ビットのランダム性が必要で、base62 では 22 文字です (62^22 は約 2^131 で、21 文字では約 2^125 にしかなりません)。その背後に、本物のアクセス確認も必要です。安全でない直接オブジェクト参照に関する OWASP の指針も同じ点を述べています。予測できない識別子は役立ちますが、制御となるのは認可です。パスワード付きや期限付きのリンクは、コードが漏れると困る場合のためのものです。URL 短縮ツールのセキュリティチェックリストに、組み合わせるべき対策が一覧になっており、URL 短縮ツールの仕組みは、コードだけでは信頼を担えない理由を説明しています。

乱数源が重要なのも、同じ理由です。シード付きの非暗号論的なジェネレーターは、いくつかの出力から予測できるため、上のコードのように、プラットフォームの CSPRNG を使ってください。既製の代替品としては、nanoid が、アルファベットと長さを設定できる、偏りのない選択の方式を実装しています。

どの方式を選ぶか

コードが何に耐えなければならないかで選んでください。

• 社内ツール、少量: 自動増分 ID の base62。単純で、衝突がなく、推測されやすさは問題になりません。
• 公開の短縮ツール、データベース1つ: ランダムな 7 文字のコードと、挿入してリトライする方式。私ならここから始めます。上の表は、衝突の確率が何年も小さいままであることを示しており、後で 8 文字にするのは、既存のすべてのリンクを有効に保つ、1行の変更です。
• マルチリージョンでの書き込み: 内部キーにはカウンタの範囲か Snowflake の ID を使い、公開側には置換かランダムなコードを使います。
• ハッシュの切り詰め: 決定的なコードが必要な場合のみ。その場合は、リトライの事情がより悪い、ランダムなコードとして扱ってください。

何を選んでも、コードは一意インデックス付きの列に保存し、生成はリダイレクトの経路から外してください。そこでは2層のキャッシュが実際の仕事をしています (p95 レイテンシの解説は、その経路がチューニングされるとどう見えるかを示しています)。コード生成、衝突処理、予約語リストを自分で持ちたくない場合は、Elido の API が転送先を受け取ってショートリンクを返し、カスタムバックハーフは検証されます。試してみたくなったら、プランを見ることができます。

関連記事

• URL 短縮ツールの作り方 - この記事が拡大して扱っている、アーキテクチャ全体。
• URL 短縮ツールの仕組み - 概念の入門。
• カスタムバックハーフとは? - コード空間の、人間が選ぶ半分。
• URL リダイレクトのキャッシュ戦略 - コードが存在した後で何が起きるか。
• オープンリダイレクトの脆弱性 - コードが保存済みの転送先に対応づけられるべき理由。
• URL 短縮ツールのセキュリティチェックリスト