Generarea codurilor scurte: base62, hash sau coduri aleatorii

Generarea codurilor scurte se reduce la patru opțiuni: codezi un contor unic în base62, tragi caractere aleatorii, trunchiezi un hash al URL-ului sau împarți intervale de ID-uri de la un coordonator. Contoarele nu produc niciodată coliziuni, dar sunt ușor de ghicit. Codurile aleatorii nu pot fi ghicite, dar au nevoie de o cale de reîncercare. Hash-și-trunchiază este cea mai slabă dintre cele patru, pentru că produce coliziuni mai devreme decât se așteaptă lumea și nu îți dă nimic ce nu îți dau celelalte.

Cifrele decid cea mai mare parte, așa că acest articol le parcurge. Un cod base62 de 7 caractere are exact 3,521,614,606,208 de valori, iar unul aleatoriu are o șansă de 50% de cel puțin o coliziune după aproximativ 2.2 milioane de linkuri. Primul fapt face ca 7 caractere să pară enorm. Al doilea este limita zilei de naștere și este motivul pentru care "trilioane de posibilități" nu înseamnă "fără coliziuni".

Dacă vrei întregul sistem din jurul codului (stocare, redirecționări, caching), începe cu cum construiești un scurtător de URL-uri. Acesta este zoom-ul pe o singură decizie din acel ghid: de unde vine codul scurt.

Codarea base62 a unui ID cu auto-incrementare

Codarea base62 convertește un număr într-un șir format din cele 62 de simboluri 0-9, a-z, A-Z. Este aceeași idee ca în hexazecimal, cu un alfabet mai mare, și este cea mai scurtă formă text sigură pentru URL a unui număr întreg, fără semne de punctuație. ID-ul 125 devine 21 (2 x 62 + 1), iar 1,000,000 devine 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;
}

Punctul forte este că unicitatea este moștenită de la baza de date. Rândul 41,000,000 primește un cod și nimeni altcineva nu-l va primi vreodată. Nu există buclă de reîncercare și nicio căutare înainte de inserare. Codurile cresc și ele lent: ID-urile sub 62^6 dau coduri de cel mult șase caractere, iar primul cod de 7 caractere apare la ID-ul 56,800,235,584.

Punctul slab este expunerea. Codul este numărul rândului în deghizare, așa că decode("4c92") returnează 1000000. Oricine îți poate număra linkurile, poate estima creșterea ta din două probe la o săptămână distanță și poate parcurge fiecare cod în ordine. Pentru un instrument intern, e în regulă. Pentru un scurtător public este un API de extragere în masă oferit gratuit, ceea ce contează pentru riscurile de redirecționare deschisă și de enumerare tratate în altă parte pe acest blog.

Poți ascunde ordinea fără să pierzi unicitatea trecând ID-ul printr-o permutare inversabilă (o mică rețea Feistel este alegerea obișnuită) înainte de codare. Ai grijă la scurtături. Înmulțirea cu o constantă modulo 62^7 pare amestecată, dar ultima cifră continuă să crească, lucru pe care un test rapid îl arată. Un contor amestecat este obfuscare, nu secretizare.

Coduri aleatorii: spațiul de chei, reîncercări și limita zilei de naștere

Un cod scurt aleatoriu extrage fiecare caracter independent din alfabet. Folosește o sursă criptografică și o alegere fără părtinire. randomInt(62) din Node face eșantionare cu respingere pentru tine, în timp ce byte % 62 deformează distribuția, pentru că 256 nu este multiplu de 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;
}

Cât de lung ar trebui să fie codul? Spațiul de chei este 62^lungime, iar problema zilei de naștere spune că, din n extrageri aleatorii dintre N valori, șansa de cel puțin o repetiție este de aproximativ 1 - e^(-n²/2N). Ajunge la 50% la aproximativ sqrt(2N ln 2) extrageri. Problema zilei de naștere este contraintuitivă pentru că perechile cresc cu pătratul lui n.

Ultima coloană este numărul important operațional. O repetiție între toate linkurile tale este aproape sigură la scară mare, dar ceea ce experimentează efectiv codul tău este o singură inserare care lovește un loc ocupat, iar această șansă este pur și simplu linkuri / spațiul de chei. La 100 de milioane de linkuri și 7 caractere, o inserare din aproximativ 35,000 intră în coliziune. O vei vedea în producție, deci ai nevoie de o cale de reîncercare, dar este ieftină.

Gestionarea coliziunilor: lasă baza de date să decidă

Tiparul care funcționează este inserează-apoi-reîncearcă, nu verifică-apoi-inserează. Două cereri pot verifica amândouă că aB3x9Qz este liber și apoi o pot scrie amândouă. O constrângere de unicitate pe coloana codului închide această cursă, iar inserarea eșuată este semnalul tău să tragi din nou.

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

Aici tryInsert rulează INSERT-ul tău și returnează false doar la o eroare de încălcare a unicității, niciodată la alte eșecuri. Dacă o singură inserare intră în coliziune cu probabilitatea p, toate încercările eșuează cu probabilitatea p^încercări. La punctul de 100M linkuri și 7 caractere, p este 2.84 x 10^-5, deci trei eșecuri la rând înseamnă aproximativ 2.3 x 10^-14. Plafonează oricum numărul de încercări. Dacă vezi vreodată că plafonul este atins, spațiul de chei este aproape plin sau sursa aleatorie este stricată, iar o eroare zgomotoasă bate o buclă infinită.

Aceeași disciplină se aplică idempotenței la endpoint-ul de creare, pentru că o cerere HTTP reîncercată nu trebuie să emită un al doilea link. Limitele de rată și idempotența acoperă această jumătate.

Hash și trunchiere: de ce intră în coliziune mai devreme decât crezi

Hashing-ul URL-ului pare atractiv pentru că este determinist: același URL produce mereu același cod, deci poți sări peste o căutare pentru duplicate. Costul este că un cod are doar atâția biți de cheltuit. Luarea a 32 de biți dintr-un rezumat dă 2^32 = 4,294,967,296 de valori, iar punctul de coliziune de 50% este la aproximativ 77,163 de URL-uri. Nu miliarde. O felie base62 de 7 caractere (cam 41.7 biți) împinge asta la aproximativ 2.2 milioane, la fel ca un cod aleatoriu de 7 caractere.

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

Așadar, trunchierea nu strică hash-ul. SHA-256 este în regulă. Rezistența la coliziuni a celor 256 de biți întregi pur și simplu nu supraviețuiește tăierii la 41 de biți. Moștenești comportamentul unui cod aleatoriu, deci ai tot nevoie de calea de reîncercare, plus o regulă pentru ce faci la o ciocnire (adaugi sare și refaci hash-ul). Iar determinismul lucrează împotriva ta: doi clienți care scurtează același URL primesc același cod și, deci, același flux de clicuri, dacă nu amesteci un ID de cont. Aș evita hash-și-trunchiază în aproape toate cazurile. Dacă vrei deduplicare, caută URL-ul după o coloană de hash și generează totuși codul pe altă cale.

Intervale de contor și ID-uri în stil Snowflake

O singură coloană cu auto-incrementare devine un blocaj când mai mulți scriitori din mai multe regiuni au nevoie de ID-uri. Două tipare evită asta fără să renunțe la unicitate.

Primul sunt intervalele de contor. Un coordonator dă fiecărei instanțe a aplicației un bloc, să zicem 1,000 de ID-uri, iar instanța le codează local, fără un drum dus-întors pentru fiecare link. Dacă o instanță moare, blocul ei nefolosit este pur și simplu sărit. Golurile într-un spațiu de coduri de ordinul trilioanelor sunt inofensive.

Al doilea este un ID în stil Snowflake: un timestamp, un ID de mașină și o secvență pe milisecundă, împachetate în 64 de biți. Acestea se sortează după momentul creării și nu au nevoie de coordonator. Problema pentru linkurile scurte este lungimea. O valoare pe 64 de biți poate ajunge la 18,446,744,073,709,551,615 și, cum 62^10 = 839,299,365,868,340,224 este mai mic decât 2^64, are nevoie de până la 11 caractere base62. Asta nu este foarte scurt. ID-urile Snowflake se potrivesc mai bine pentru chei de bază de date decât pentru coduri publice, așa că majoritatea scurtătoarelor le păstrează interne și folosesc un cod separat, mai scurt.

Ambele moștenesc problema ghicibilității secvențiale, pentru că ambele sunt ordonate prin construcție. Învelește-le într-o permutare sau folosește-le doar ca cheie primară internă.

Coduri personalizate și cuvinte rezervate

Sluguri de tip vanity sunt singurul loc unde un om alege codul, iar ele trec prin aceeași constrângere de unicitate ca orice altceva. Munca suplimentară este validarea înainte de inserare. Un back-half personalizat, cum ar fi /spring-sale, trebuie verificat în raport cu trei lucruri.

• Cuvinte rezervate. Căile pe care aplicația ta sau web-ul le folosesc deja nu trebuie niciodată să poată fi revendicate: api, admin, login, static, robots.txt, favicon.ico și .well-known. Un scurtător care lasă pe cineva să înregistreze /login a construit un generator de pagini de phishing.
• Coliziuni cu codurile generate. Dacă un utilizator ia /aB3x9Qz, generatorul tău aleatoriu poate produce mai târziu același șir. Constrângerea de unicitate rezolvă asta, atâta timp cât codurile personalizate și cele generate împart un singur spațiu de nume.
• Majuscule și caractere asemănătoare. Base62 face diferența între litere mari și mici, deci /Ab și /ab sunt linkuri diferite. Decide dacă sluguri personalizate se compară fără a ține cont de majuscule și ia în calcul blocarea perechilor care diferă doar prin 0/O sau l/1. Ghidul despre URL-uri vanity acoperă partea de branding.

Codurile aleatorii de 7 caractere pot forma și ceva nepotrivit. Trece codurile generate printr-o scurtă listă de blocare și extrage din nou la o potrivire. Costă aproape nimic.

Enumerare, ghicibilitate și confidențialitate

Un cod scurt este o adresă. Nu este un secret și nicio lungime nu-l transformă în unul. Totuși, diferența dintre secvențial și aleatoriu este mare. Cu coduri secvențiale, fiecare încercare nimerește un link activ. Cu 10 milioane de linkuri răspândite aleatoriu pe 62^7 valori, o încercare oarbă nimerește unul cu probabilitatea 10,000,000 / 3,521,614,606,208, cam 1 din 352,000. Un scaner are nevoie de sute de mii de cereri pentru fiecare găsire, lucru pe care limitarea ratei și detecția boților îl pot pedepsi.

Dacă o destinație trebuie să rămână privată, codul trebuie să fie o capabilitate. Asta înseamnă cel puțin 128 de biți de aleatoriu, ceea ce în base62 înseamnă 22 de caractere (62^22 este aproximativ 2^131; 21 de caractere dau doar aproximativ 2^125). Are nevoie și de o verificare reală a accesului în spate. Ghidul OWASP despre referințe directe nesigure la obiecte spune același lucru: identificatorii imprevizibili ajută, dar autorizarea este controlul. Linkurile protejate prin parolă sau cu expirare sunt pentru cazurile în care un cod scurs ar dăuna. Lista de verificare pentru securitatea unui scurtător de URL-uri enumeră controalele de asociat, iar mecanica funcționării scurtătoarelor explică de ce doar codul nu poate purta niciodată încredere.

Sursa de aleatoriu contează din același motiv. Un generator cu sămânță, necriptografic, poate fi prezis din câteva ieșiri, așa că folosește CSPRNG-ul platformei, ca în fragmentul de mai sus. Pentru alternative gata făcute, nanoid implementează abordarea alegerii fără părtinire, cu alfabet și lungime configurabile.

Ce abordare alegi

Alege după ce trebuie să supraviețuiască codul.

• Instrument intern, volum mic: base62 al unui ID cu auto-incrementare. Simplu, fără coliziuni, iar ghicibilitatea nu contează.
• Scurtător public, o singură bază de date: coduri aleatorii de 7 caractere cu inserare și reîncercare. Aș începe de aici. Tabelul de mai sus arată că șansele de coliziune rămân minuscule ani de zile, iar trecerea la 8 caractere mai târziu este o schimbare dintr-o linie care păstrează valid fiecare link existent.
• Scrieri multi-regiune: intervale de contor sau ID-uri Snowflake drept cheie internă, plus o permutare sau un cod aleatoriu pentru ceea ce vede publicul.
• Hash-și-trunchiază: doar dacă ai nevoie de coduri deterministe și, atunci, tratează-l ca pe un cod aleatoriu cu o poveste de reîncercare mai proastă.

Orice alegi, stochează codul într-o coloană cu index unic și ține generarea departe de calea redirecționării, unde un cache pe două niveluri face munca adevărată (articolul despre latența p95 arată cum arată acea cale când este reglată). Dacă preferi să nu deții generarea codurilor, gestionarea coliziunilor și listele de cuvinte rezervate, API-ul Elido primește o destinație și returnează un link scurt, cu back-half-uri personalizate validate pentru tine. Vezi planurile când vrei să încerci.

Alte articole de pe blog

• Cum construiești un scurtător de URL-uri - arhitectura completă pe care acest articol o detaliază.
• Cum funcționează scurtătoarele de URL-uri - introducerea conceptuală.
• Ce este un back-half personalizat? - jumătatea aleasă de om a spațiului de coduri.
• Strategia de cache pentru redirecționările URL - ce se întâmplă după ce codul există.
• Vulnerabilități de redirecționare deschisă - de ce codul ar trebui să se mapeze pe o destinație stocată.
• Lista de verificare pentru securitatea unui scurtător de URL-uri