Korte codes genereren: base62 vs hash vs willekeurige codes

Korte codes genereren komt neer op vier opties: een unieke teller in base62 coderen, willekeurige tekens trekken, een hash van de URL afkappen of ID-reeksen uitdelen vanuit een coördinator. Tellers botsen nooit maar zijn raadbaar. Willekeurige codes zijn niet raadbaar maar hebben een retrypad nodig. Hashen en afkappen is de zwakste van de vier, omdat het eerder botst dan mensen verwachten en je niets geeft wat de andere niet geven.

De getallen beslissen het grootste deel, dus dit artikel werkt ze door. Een base62-code van 7 tekens heeft precies 3.521.614.606.208 waarden, en een willekeurige heeft een kans van 50% op minstens één botsing na ruwweg 2,2 miljoen links. Het eerste feit laat 7 tekens enorm aanvoelen. Het tweede is de verjaardagsgrens, en daarom betekent "biljoenen mogelijkheden" niet "geen botsingen".

Wil je het hele systeem rond de code (opslag, redirects, caching), begin dan bij hoe je een URL-verkorter bouwt. Dit is de zoom op een beslissing uit die uitleg: waar de korte code vandaan komt.

Base62-codering van een auto-increment-ID

Base62-codering zet een getal om in een string over de 62 symbolen 0-9, a-z, A-Z. Het is hetzelfde idee als hexadecimaal met een groter alfabet, en het is de kortste URL-veilige tekstvorm van een geheel getal die leestekens vermijdt. De ID 125 wordt 21 (2 x 62 + 1), en 1,000,000 wordt 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;
}

De kracht is dat uniciteit door de database wordt geërfd. Rij 41.000.000 krijgt één code en niemand anders krijgt hem ooit. Er is geen retrylus en geen opzoeking vóór het invoegen. Codes groeien ook langzaam: ID's onder 62^6 geven codes van zes tekens of minder, en de eerste code van 7 tekens verschijnt bij ID 56.800.235.584.

De zwakte is blootstelling. De code is het rijnummer in vermomming, dus decode("4c92") geeft 1000000. Iedereen kan je links tellen, je groei schatten uit twee steekproeven met een week ertussen en elke code in volgorde aflopen. Voor een interne tool is dat prima. Voor een openbare verkorter is het een gratis scrape-API, wat ertoe doet voor de risico's van open redirects en opsomming die elders op deze blog worden behandeld.

Je kunt de volgorde verbergen zonder uniciteit te verliezen door de ID vóór het coderen door een inverteerbare permutatie te halen (een klein Feistel-netwerk is de gebruikelijke keuze). Wees voorzichtig met sluiproutes. Vermenigvuldigen met een constante modulo 62^7 ziet er door elkaar geschud uit maar laat het laatste cijfer oplopen, wat een snelle test laat zien. Een door elkaar geschudde teller is verhulling, geen geheimhouding.

Willekeurige codes: sleutelruimte, retries en de verjaardagsgrens

Een willekeurige korte code trekt elk teken onafhankelijk uit het alfabet. Gebruik een cryptografische bron en een onbevooroordeelde keuze. randomInt(62) in Node doet de rejection sampling voor je, terwijl byte % 62 de verdeling scheeftrekt omdat 256 geen veelvoud van 62 is.

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

Hoe lang moet de code zijn? De sleutelruimte is 62^lengte, en het verjaardagsprobleem zegt dat bij n willekeurige trekkingen uit N waarden de kans op minstens één herhaling ongeveer 1 - e^(-n²/2N) is. Het bereikt 50% bij ruwweg sqrt(2N ln 2) trekkingen. Het verjaardagsprobleem is contra-intuïtief omdat het aantal paren met het kwadraat van n groeit.

De laatste kolom is het getal dat operationeel telt. Een herhaling tussen al je links is op schaal vrijwel zeker, maar wat je code werkelijk meemaakt, is één invoeging die op een bezette plek stuit, en die kans is gewoon links / sleutelruimte. Bij 100 miljoen links en 7 tekens botst ongeveer een op de 35.000 invoegingen. Je ziet het in productie, dus je hebt een retrypad nodig, maar het is goedkoop.

Botsingsafhandeling: laat de database beslissen

Het patroon dat werkt, is invoegen-en-opnieuw-proberen, niet controleren-en-invoegen. Twee verzoeken kunnen allebei controleren dat aB3x9Qz vrij is en hem dan allebei schrijven. Een unieke beperking op de codekolom sluit die race, en het mislukte invoegen is je signaal om opnieuw te trekken.

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 voert tryInsert je INSERT uit en geeft alleen false terug bij een fout door een unieke schending, nooit bij andere fouten. Als een enkele invoeging met kans p botst, mislukken alle pogingen met kans p^pogingen. Op het punt van 100M links en 7 tekens is p gelijk aan 2,84 x 10^-5, dus drie mislukkingen achter elkaar zijn ongeveer 2,3 x 10^-14. Begrens de pogingen toch. Zie je ooit dat de limiet wordt bereikt, dan is de sleutelruimte bijna vol of de willekeurige bron kapot, en een luide fout is beter dan een oneindige lus.

Dezelfde discipline geldt voor idempotentie op het create-endpoint, omdat een opnieuw verzonden HTTP-verzoek geen tweede link mag maken. Ratelimieten en idempotentie behandelt die helft.

Hashen en afkappen: waarom het eerder botst dan je denkt

De URL hashen ziet er aantrekkelijk uit omdat het deterministisch is: dezelfde URL levert altijd dezelfde code op, dus je kunt een opzoeking naar duplicaten overslaan. De prijs is dat een code maar zoveel bits te besteden heeft. 32 bits van een digest nemen geeft 2^32 = 4.294.967.296 waarden, en het botsingspunt van 50% ligt bij ongeveer 77.163 URL's. Geen miljarden. Een base62-stuk van 7 tekens (ongeveer 41,7 bits) tilt dat naar ruwweg 2,2 miljoen, hetzelfde als een willekeurige code van 7 tekens.

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

Afkappen breekt de hash dus niet. SHA-256 is prima. De botsingsweerstand van de volledige 256 bits overleeft het inkorten tot 41 bits gewoon niet. Je erft het gedrag van willekeurige codes, dus je hebt nog steeds het retrypad nodig, plus een regel voor wat je bij een botsing doet (zout toevoegen en opnieuw hashen). En determinisme werkt tegen je: twee klanten die dezelfde URL verkorten, krijgen dezelfde code en dus dezelfde klikstroom, tenzij je een account-ID meemengt. Ik zou hashen en afkappen in bijna alle gevallen overslaan. Wil je ontdubbelen, zoek de URL dan op via een hashkolom en genereer de code toch op een andere manier.

Tellerreeksen en Snowflake-achtige ID's

Een enkele auto-increment-kolom wordt een knelpunt wanneer meerdere schrijvers in meerdere regio's ID's nodig hebben. Twee patronen vermijden dat zonder uniciteit op te geven.

Het eerste zijn tellerreeksen. Een coördinator geeft elke applicatie-instantie een blok, zeg 1.000 ID's, en de instantie codeert ze lokaal zonder heen-en-weer per link. Als een instantie sterft, wordt zijn ongebruikte blok gewoon overgeslagen. Gaten in een coderuimte van biljoenen zijn onschuldig.

Het tweede is een Snowflake-achtige ID: een tijdstempel, een machine-ID en een reeks per milliseconde samengepakt in 64 bits. Deze sorteren op aanmaaktijd en hebben geen coördinator nodig. Het addertje voor korte links is lengte. Een waarde van 64 bits is maximaal 18.446.744.073.709.551.615, en omdat 62^10 = 839.299.365.868.340.224 kleiner is dan 2^64, heeft ze tot 11 base62-tekens nodig. Dat is niet erg kort. Snowflake-ID's passen beter bij databasesleutels dan bij openbare codes, dus de meeste verkorters houden ze intern en gebruiken een aparte, kortere code.

Beide erven het probleem van opeenvolgende raadbaarheid, omdat beide per constructie geordend zijn. Wikkel ze in een permutatie, of gebruik er een alleen als interne primaire sleutel.

Eigen codes en gereserveerde woorden

Vanity-slugs zijn de enige plek waar een mens de code kiest, en ze lopen door dezelfde unieke beperking als al het andere. Het extra werk is validatie vóór het invoegen. Een eigen achterdeel zoals /spring-sale moet op drie dingen worden gecontroleerd.

• Gereserveerde woorden. Paden die je applicatie of het web al gebruikt, mogen nooit claimbaar zijn: api, admin, login, static, robots.txt, favicon.ico en .well-known. Een verkorter die iemand /login laat registreren, heeft een generator van phishingpagina's gebouwd.
• Botsingen met gegenereerde codes. Als een gebruiker /aB3x9Qz neemt, kan je willekeurige generator later dezelfde string produceren. De unieke beperking handelt het af, zolang eigen en gegenereerde codes één naamruimte delen.
• Hoofdletters en lookalikes. Base62 is hoofdlettergevoelig, dus /Ab en /ab zijn verschillende links. Beslis of eigen slugs hoofdletterongevoelig worden vergeleken, en overweeg paren te blokkeren die alleen verschillen door 0/O of l/1. De gids over vanity-URL's behandelt de merkkant.

Willekeurige codes van 7 tekens kunnen ook iets ongelukkigs spellen. Haal gegenereerde codes door een korte blokkadelijst en trek opnieuw bij een treffer. Het kost bijna niets.

Opsomming, raadbaarheid en privacy

Een korte code is een adres. Het is geen geheim, en geen lengte maakt er een van. Toch is het verschil tussen opeenvolgend en willekeurig groot. Bij opeenvolgende codes raakt elke gok een levende link. Met 10 miljoen links willekeurig verspreid over 62^7 waarden raakt een blinde gok er een met kans 10.000.000 / 3.521.614.606.208, ongeveer 1 op 352.000. Een scanner heeft honderdduizenden verzoeken per vondst nodig, wat ratelimiting en botdetectie kunnen afstraffen.

Als een bestemming privé moet blijven, moet de code een capability zijn. Dat betekent minstens 128 bits willekeur, wat in base62 22 tekens is (62^22 is ongeveer 2^131; 21 tekens geven maar ongeveer 2^125). Het heeft ook een echte toegangscontrole erachter nodig. De richtlijnen van OWASP over onveilige directe objectverwijzingen maken hetzelfde punt: onvoorspelbare identificatoren helpen, maar autorisatie is de controle. Met wachtwoord beveiligde of verlopende links zijn voor de gevallen waarin een gelekte code zou schaden. De beveiligingschecklist voor URL-verkorters somt de controles op die je ermee combineert, en de werking van verkorters legt uit waarom de code alleen nooit vertrouwen kan dragen.

De willekeurige bron telt om dezelfde reden. Een geseede, niet-cryptografische generator kan uit een paar uitvoerwaarden worden voorspeld, dus gebruik de CSPRNG van het platform, zoals in het fragment hierboven. Voor kant-en-klare alternatieven implementeert nanoid de onbevooroordeelde keuze met een instelbaar alfabet en instelbare lengte.

Welke aanpak je moet kiezen

Kies op wat de code moet overleven.

• Interne tool, laag volume: base62 van een auto-increment-ID. Eenvoudig, botsingsvrij, en de raadbaarheid maakt niet uit.
• Openbare verkorter, één database: willekeurige codes van 7 tekens met invoegen-en-opnieuw-proberen. Ik zou hier beginnen. De tabel hierboven laat zien dat de botsingskansen jarenlang minuscuul blijven, en later naar 8 tekens gaan is een wijziging van één regel die elke bestaande link geldig houdt.
• Schrijven in meerdere regio's: tellerreeksen of Snowflake-ID's als interne sleutel, plus een permutatie of willekeurige code voor wat het publiek ziet.
• Hashen en afkappen: alleen als je deterministische codes nodig hebt, en behandel het dan als een willekeurige code met een slechter retryverhaal.

Wat je ook kiest, sla de code op in een kolom met een unieke index en houd het genereren van het redirectpad af, waar een cache met twee lagen het echte werk doet (het verslag over p95-latentie toont hoe dat pad eruitziet als het is afgesteld). Wil je liever geen eigenaar zijn van codegeneratie, botsingsafhandeling en lijsten met gereserveerde woorden, dan neemt de API van Elido een bestemming aan en geeft een korte link terug, met eigen achterdelen die voor je worden gevalideerd. Bekijk de plannen als je het wilt proberen.

Gerelateerd op de blog

• Hoe je een URL-verkorter bouwt - de volledige architectuur waar dit artikel op inzoomt.
• Hoe URL-verkorters werken - de conceptuele inleiding.
• Wat is een eigen achterdeel? - de door mensen gekozen helft van de coderuimte.
• Cachestrategie voor URL-redirects - wat er gebeurt nadat de code bestaat.
• Kwetsbaarheden door open redirects - waarom de code naar een opgeslagen bestemming moet verwijzen.
• Beveiligingschecklist voor URL-verkorters