Kurzcode-Generierung: Base62 vs. Hash vs. Zufallscodes

Die Kurzcode-Generierung läuft auf vier Optionen hinaus: einen eindeutigen Zähler in Base62 kodieren, Zufallszeichen ziehen, einen Hash der URL kürzen oder ID-Bereiche von einem Koordinator vergeben lassen. Zähler kollidieren nie, sind aber erratbar. Zufallscodes sind nicht erratbar, brauchen aber einen Retry-Pfad. Hash-und-Kürzen ist die schwächste der vier, weil es früher kollidiert, als man erwartet, und Ihnen nichts bietet, was die anderen nicht bieten.

Die Zahlen entscheiden das meiste, deshalb rechnet dieser Beitrag sie durch. Ein Base62-Code mit 7 Zeichen hat genau 3.521.614.606.208 Werte, und ein zufälliger hat nach grob 2,2 Millionen Links eine Wahrscheinlichkeit von 50 % auf mindestens eine Kollision. Die erste Tatsache lässt 7 Zeichen riesig wirken. Die zweite ist die Geburtstagsschranke, und sie ist der Grund, warum "Billionen Möglichkeiten" nicht "keine Kollisionen" bedeutet.

Wenn Sie das ganze System um den Code herum (Speicherung, Weiterleitungen, Caching) wollen, beginnen Sie mit einen URL-Kürzer bauen. Dies ist die Detailansicht einer Entscheidung aus dieser Anleitung: woher der Kurzcode kommt.

Base62-Kodierung einer Auto-Increment-ID

Base62-Kodierung wandelt eine Zahl in eine Zeichenkette über die 62 Symbole 0-9, a-z, A-Z um. Es ist dieselbe Idee wie Hexadezimal mit einem größeren Alphabet, und es ist die kürzeste URL-sichere Textform einer Ganzzahl, die Satzzeichen vermeidet. Die ID 125 wird zu 21 (2 x 62 + 1), und 1,000,000 wird zu 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;
}

Die Stärke ist, dass die Eindeutigkeit von der Datenbank geerbt wird. Zeile 41.000.000 bekommt einen Code, und niemand sonst bekommt ihn je. Es gibt keine Retry-Schleife und keine Abfrage vor dem Einfügen. Die Codes wachsen außerdem langsam: IDs unter 62^6 ergeben Codes mit sechs oder weniger Zeichen, und der erste Code mit 7 Zeichen erscheint bei ID 56.800.235.584.

Die Schwäche ist die Preisgabe. Der Code ist die verkleidete Zeilennummer, decode("4c92") liefert also 1000000. Jeder kann Ihre Links zählen, Ihr Wachstum aus zwei Stichproben im Abstand einer Woche schätzen und jeden Code der Reihe nach durchlaufen. Für ein internes Tool ist das in Ordnung. Für einen öffentlichen Kürzer ist es eine kostenlose Scraping-API, was für die Risiken durch Open Redirects und Aufzählung zählt, die an anderer Stelle in diesem Blog behandelt werden.

Sie können die Reihenfolge verbergen, ohne die Eindeutigkeit zu verlieren, indem Sie die ID vor dem Kodieren durch eine umkehrbare Permutation schicken (ein kleines Feistel-Netzwerk ist die übliche Wahl). Seien Sie vorsichtig mit Abkürzungen. Eine Multiplikation mit einer Konstante modulo 62^7 sieht durchmischt aus, lässt aber die letzte Ziffer weiter hochzählen, was ein kurzer Test zeigt. Ein durchmischter Zähler ist Verschleierung, keine Geheimhaltung.

Zufallscodes: Schlüsselraum, Retries und die Geburtstagsschranke

Ein zufälliger Kurzcode zieht jedes Zeichen unabhängig aus dem Alphabet. Verwenden Sie eine kryptografische Quelle und eine unverzerrte Auswahl. randomInt(62) in Node macht das Rejection Sampling für Sie, während byte % 62 die Verteilung verzerrt, weil 256 kein Vielfaches von 62 ist.

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;
}

Wie lang sollte der Code sein? Der Schlüsselraum ist 62^Länge, und das Geburtstagsproblem sagt, dass unter n Zufallsziehungen aus N Werten die Wahrscheinlichkeit für mindestens eine Wiederholung etwa 1 - e^(-n²/2N) beträgt. Sie erreicht 50 % bei etwa sqrt(2N ln 2) Ziehungen. Das Geburtstagsproblem ist kontraintuitiv, weil die Paare mit dem Quadrat von n wachsen.

Die letzte Spalte ist die betrieblich wichtige Zahl. Eine Wiederholung unter allen Ihren Links ist im großen Maßstab nahezu sicher, aber was Ihr Code tatsächlich erlebt, ist ein einzelnes Einfügen, das auf einen belegten Platz trifft, und diese Wahrscheinlichkeit beträgt schlicht Links / Schlüsselraum. Bei 100 Millionen Links und 7 Zeichen kollidiert etwa eines von 35.000 Einfügen. Sie werden es in der Produktion sehen, brauchen also einen Retry-Pfad, aber er ist billig.

Kollisionsbehandlung: Lassen Sie die Datenbank entscheiden

Das Muster, das funktioniert, ist Einfügen-dann-Wiederholen, nicht Prüfen-dann-Einfügen. Zwei Anfragen können beide prüfen, dass aB3x9Qz frei ist, und es dann beide schreiben. Eine Unique-Constraint auf der Code-Spalte schließt diese Race Condition, und das fehlgeschlagene Einfügen ist Ihr Signal, erneut zu ziehen.

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");
}

Hier führt tryInsert Ihr INSERT aus und gibt nur bei einem Unique-Violation-Fehler false zurück, nie bei anderen Fehlern. Wenn ein einzelnes Einfügen mit Wahrscheinlichkeit p kollidiert, scheitern alle Versuche mit Wahrscheinlichkeit p^Versuche. Am Punkt von 100 Mio. Links und 7 Zeichen ist p gleich 2,84 x 10^-5, drei Fehlschläge in Folge sind also etwa 2,3 x 10^-14. Begrenzen Sie die Versuche trotzdem. Wenn Sie je sehen, dass die Grenze erreicht wird, ist der Schlüsselraum fast voll oder die Zufallsquelle defekt, und ein lauter Fehler schlägt eine Endlosschleife.

Dieselbe Disziplin gilt für Idempotenz am Create-Endpunkt, denn eine wiederholte HTTP-Anfrage (Retry) darf keinen zweiten Link erzeugen. Rate-Limits und Idempotenz behandelt diese Hälfte.

Hash und Kürzen: Warum es früher kollidiert, als Sie denken

Die URL zu hashen wirkt attraktiv, weil es deterministisch ist: Dieselbe URL liefert immer denselben Code, sodass Sie eine Abfrage nach Duplikaten sparen können. Der Preis ist, dass ein Code nur begrenzt viele Bits zur Verfügung hat. 32 Bits eines Digest ergeben 2^32 = 4.294.967.296 Werte, und der Punkt mit 50 % Kollisionswahrscheinlichkeit liegt bei etwa 77.163 URLs. Keine Milliarden. Ein Base62-Ausschnitt mit 7 Zeichen (etwa 41,7 Bits) schiebt das auf grob 2,2 Millionen, was dem eines zufälligen Codes mit 7 Zeichen entspricht.

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");
}

Das Kürzen bricht den Hash also nicht. SHA-256 ist in Ordnung. Die Kollisionsresistenz der vollen 256 Bits überlebt es nur nicht, auf 41 Bits gekürzt zu werden. Sie erben das Verhalten von Zufallscodes, brauchen also weiterhin den Retry-Pfad, plus eine Regel, was bei einem Konflikt zu tun ist (salzen und neu hashen). Und der Determinismus arbeitet gegen Sie: Zwei Kunden, die dieselbe URL kürzen, bekommen denselben Code und damit denselben Klickstrom, es sei denn, Sie mischen eine Konto-ID hinein. Ich würde Hash-und-Kürzen in fast jedem Fall überspringen. Wenn Sie Deduplizierung wollen, suchen Sie die URL über eine Hash-Spalte und erzeugen Sie den Code trotzdem auf andere Weise.

Zählerbereiche und Snowflake-artige IDs

Eine einzelne Auto-Increment-Spalte wird zum Engpass, wenn mehrere Schreiber in mehreren Regionen IDs brauchen. Zwei Muster vermeiden das, ohne die Eindeutigkeit aufzugeben.

Das erste sind Zählerbereiche. Ein Koordinator gibt jeder Anwendungsinstanz einen Block, sagen wir 1.000 IDs, und die Instanz kodiert sie lokal, ohne Roundtrip pro Link. Wenn eine Instanz stirbt, wird ihr ungenutzter Block einfach übersprungen. Lücken in einem Code-Raum von Billionen sind harmlos.

Das zweite ist eine Snowflake-artige ID: ein Zeitstempel, eine Maschinen-ID und eine Sequenz pro Millisekunde, in 64 Bit gepackt. Diese sortieren nach Erstellungszeit und brauchen keinen Koordinator. Der Haken bei Kurzlinks ist die Länge. Ein 64-Bit-Wert ist bis zu 18.446.744.073.709.551.615 groß, und da 62^10 = 839.299.365.868.340.224 kleiner ist als 2^64, braucht er bis zu 11 Base62-Zeichen. Das ist nicht sehr kurz. Snowflake-IDs passen besser zu Datenbankschlüsseln als zu öffentlichen Codes, deshalb halten die meisten Kürzer sie intern und nutzen einen separaten, kürzeren Code.

Beide erben das Problem der sequenziellen Erratbarkeit, weil beide von Konstruktion her geordnet sind. Verpacken Sie sie in eine Permutation oder nutzen Sie eine von ihnen nur als internen Primärschlüssel.

Eigene Codes und reservierte Wörter

Vanity-Slugs sind die eine Stelle, an der ein Mensch den Code wählt, und sie durchlaufen dieselbe Unique-Constraint wie alles andere. Die zusätzliche Arbeit ist die Validierung vor dem Einfügen. Ein eigener Back-Half wie /spring-sale muss gegen drei Dinge geprüft werden.

• Reservierte Wörter. Pfade, die Ihre Anwendung oder das Web bereits nutzt, dürfen nie beanspruchbar sein: api, admin, login, static, robots.txt, favicon.ico und .well-known. Ein Kürzer, der jemanden /login registrieren lässt, hat einen Generator für Phishing-Seiten gebaut.
• Kollisionen mit erzeugten Codes. Wenn ein Nutzer /aB3x9Qz nimmt, kann Ihr Zufallsgenerator später dieselbe Zeichenkette erzeugen. Die Unique-Constraint behandelt das, solange eigene und erzeugte Codes einen Namensraum teilen.
• Groß-/Kleinschreibung und Verwechslungen. Base62 unterscheidet Groß- und Kleinschreibung, /Ab und /ab sind also verschiedene Links. Entscheiden Sie, ob eigene Slugs ohne Beachtung der Schreibung verglichen werden, und erwägen Sie, Paare zu blockieren, die sich nur durch 0/O oder l/1 unterscheiden. Der Leitfaden zu Vanity-URLs behandelt die Markenseite.

Zufällige Codes mit 7 Zeichen können auch etwas Unglückliches buchstabieren. Lassen Sie erzeugte Codes durch eine kurze Sperrliste laufen und ziehen Sie bei einem Treffer neu. Es kostet fast nichts.

Aufzählung, Erratbarkeit und Datenschutz

Ein Kurzcode ist eine Adresse. Er ist kein Geheimnis, und keine Länge macht ihn zu einem. Trotzdem ist der Unterschied zwischen sequenziell und zufällig groß. Bei sequenziellen Codes trifft jeder Versuch einen aktiven Link. Bei 10 Millionen Links, zufällig über 62^7 Werte verteilt, trifft ein blinder Versuch mit Wahrscheinlichkeit 10.000.000 / 3.521.614.606.208 einen, etwa 1 zu 352.000. Ein Scanner braucht hunderttausende Anfragen pro Fund, was Rate-Limiting und Bot-Erkennung bestrafen können.

Wenn ein Ziel privat bleiben muss, muss der Code eine Berechtigung (Capability) sein. Das bedeutet mindestens 128 Bit Zufälligkeit, in Base62 sind das 22 Zeichen (62^22 sind etwa 2^131; 21 Zeichen ergeben nur etwa 2^125). Es braucht außerdem eine echte Zugriffsprüfung dahinter. OWASPs Leitfaden zu unsicheren direkten Objektreferenzen macht denselben Punkt: Unvorhersagbare Kennungen helfen, aber die Autorisierung ist die Kontrolle. Passwortgeschützte oder ablaufende Links sind für die Fälle, in denen ein durchgesickerter Code schaden würde. Die Sicherheits-Checkliste für URL-Kürzer listet die Kontrollen auf, die dazugehören, und die Mechanik, wie Kürzer funktionieren, erklärt, warum der Code allein nie Vertrauen tragen kann.

Die Zufallsquelle zählt aus demselben Grund. Ein mit einem Seed gestarteter, nicht kryptografischer Generator lässt sich aus wenigen Ausgaben vorhersagen, verwenden Sie also den CSPRNG der Plattform, wie im obigen Snippet. Als fertige Alternative implementiert nanoid den Ansatz der unverzerrten Auswahl mit konfigurierbarem Alphabet und konfigurierbarer Länge.

Welchen Ansatz Sie wählen sollten

Wählen Sie danach, was der Code überstehen muss.

• Internes Tool, geringes Volumen: Base62 einer Auto-Increment-ID. Einfach, kollisionsfrei, und die Erratbarkeit spielt keine Rolle.
• Öffentlicher Kürzer, eine Datenbank: zufällige Codes mit 7 Zeichen mit Einfügen-und-Wiederholen. Hier würde ich beginnen. Die obige Tabelle zeigt, dass die Kollisionswahrscheinlichkeit jahrelang winzig bleibt, und der spätere Wechsel auf 8 Zeichen ist eine Ein-Zeilen-Änderung, die jeden bestehenden Link gültig hält.
• Schreibzugriffe in mehreren Regionen: Zählerbereiche oder Snowflake-IDs als internen Schlüssel, plus eine Permutation oder einen Zufallscode für das, was die Öffentlichkeit sieht.
• Hash-und-Kürzen: nur, wenn Sie deterministische Codes brauchen, und dann als Zufallscode mit schlechterer Retry-Geschichte behandeln.

Was auch immer Sie wählen: Speichern Sie den Code in einer Spalte mit Unique-Index und halten Sie die Generierung vom Weiterleitungspfad fern, wo ein zweistufiger Cache die eigentliche Arbeit leistet (der Beitrag zur p95-Latenz zeigt, wie dieser Pfad im optimierten Zustand aussieht). Wenn Sie lieber nicht selbst für Code-Generierung, Kollisionsbehandlung und Listen reservierter Wörter zuständig sein möchten, nimmt Elidos API ein Ziel entgegen und liefert einen Kurzlink zurück, wobei eigene Back-Halves für Sie validiert werden. Sehen Sie sich die Pläne an, wenn Sie es ausprobieren möchten.

Weiterführend im Blog

• Einen URL-Kürzer bauen - die vollständige Architektur, in die dieser Beitrag hineinzoomt.
• Wie URL-Kürzer funktionieren - die konzeptionelle Einführung.
• Was ist ein eigener Back-Half? - die von Menschen gewählte Hälfte des Code-Raums.
• Cache-Strategie für URL-Weiterleitungen - was passiert, nachdem der Code existiert.
• Open-Redirect-Schwachstellen - warum der Code auf ein gespeichertes Ziel abbilden sollte.
• Sicherheits-Checkliste für URL-Kürzer