Kısa Kod Üretimi: Base62, Hash ve Rastgele Kodlar

Kısa kod üretimi dört seçeneğe iner: benzersiz bir sayacı base62'de kodlamak, rastgele karakterler çekmek, URL'nin bir hash'ini kırpmak ya da bir koordinatörden kimlik aralıkları dağıtmak. Sayaçlar asla çakışmaz ama tahmin edilebilirdir. Rastgele kodlar tahmin edilemez ama bir yeniden deneme yoluna ihtiyaç duyar. Hash'leyip kırpmak dördünün en zayıfıdır, çünkü insanların beklediğinden daha erken çakışır ve size diğerlerinin vermediği hiçbir şey vermez.

Sayılar çoğuna karar verir; bu yüzden bu yazı onları adım adım işler. 7 karakterlik bir base62 kodunun tam olarak 3.521.614.606.208 değeri vardır ve rastgele bir kodun, kabaca 2,2 milyon bağlantıdan sonra en az bir çakışma olma şansı yüzde 50'dir. Birinci olgu 7 karakteri muazzam hissettirir. İkincisi doğum günü sınırıdır ve "trilyonlarca olasılık"ın neden "çakışma yok" anlamına gelmediğidir.

Koddan çevresindeki bütün sistemi (depolama, yönlendirmeler, önbellekleme) istiyorsanız, bir URL kısaltıcı nasıl inşa edilir yazısından başlayın. Bu, o adım adım anlatımdaki tek bir karara yakınlaştırma: kısa kod nereden geliyor.

Otomatik Artan Bir Kimliğin Base62 Kodlaması

Base62 kodlama, bir sayıyı 0-9, a-z, A-Z 62 sembolü üzerinden bir dizeye çevirir. Daha büyük bir alfabeyle onaltılık sistemle aynı fikirdir ve noktalama işaretlerinden kaçınan bir tamsayının en kısa URL güvenli metin biçimidir. 125 kimliği 21 (2 x 62 + 1) olur ve 1.000.000, 4c92 olur.

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

Güçlü yanı, benzersizliğin veritabanından miras alınmasıdır. 41.000.000. satır bir kod alır ve başka hiç kimse onu asla almaz. Bir yeniden deneme döngüsü yok ve eklemeden önce arama yok. Kodlar ayrıca yavaş büyür: 62^6'nın altındaki kimlikler altı karakter veya daha az kod verir ve ilk 7 karakterlik kod 56.800.235.584 kimliğinde görünür.

Zayıflığı açığa çıkmadır. Kod, kılık değiştirmiş satır numarasıdır; bu yüzden decode("4c92") 1000000 döndürür. Herkes bağlantılarınızı sayabilir, bir hafta arayla iki örnekten büyümenizi tahmin edebilir ve her kodu sırayla gezebilir. Dahili bir araç için bu sorun değil. Herkese açık bir kısaltıcı için bu bedava bir kazıma API'sidir; bu blogda başka yerde ele alınan açık yönlendirme ve sıralama riskleri için önemlidir.

Benzersizliği kaybetmeden sırayı, kodlamadan önce kimliği tersine çevrilebilir bir permütasyondan (olağan seçim küçük bir Feistel ağıdır) geçirerek gizleyebilirsiniz. Kısayollara dikkat edin. 62^7 modunda bir sabitle çarpmak karışık görünür ama son basamağın artmaya devam etmesini sağlar; hızlı bir test bunu gösterir. Karıştırılmış bir sayaç gizleme (obfuscation) demektir, gizlilik değil.

Rastgele Kodlar: Anahtar Uzayı, Yeniden Denemeler ve Doğum Günü Sınırı

Rastgele bir kısa kod, her karakteri alfabeden bağımsız çeker. Kriptografik bir kaynak ve yanlılıksız bir seçim kullanın. Node'daki randomInt(62) sizin için ret örneklemesi yapar; oysa byte % 62 dağılımı çarpıtır, çünkü 256, 62'nin katı değildir.

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

Kod ne kadar uzun olmalı? Anahtar uzayı 62^uzunluk'tur ve doğum günü problemi, N değerden n rastgele çekilişte en az bir tekrarın şansının yaklaşık 1 - e^(-n²/2N) olduğunu söyler. Kabaca sqrt(2N ln 2) çekilişte yüzde 50'ye ulaşır. Doğum günü problemi, çiftler n'nin karesiyle büyüdüğü için sezgiye aykırıdır.

Son sütun operasyonel olarak önemli olan sayıdır. Tüm bağlantılarınız arasında bir tekrar ölçekte neredeyse kesindir, ama kodunuzun gerçekte yaşadığı şey tek bir eklemenin dolu bir yuvaya çarpmasıdır ve bu şans yalnızca bağlantılar / anahtar uzayıdır. 100 milyon bağlantıda ve 7 karakterde, yaklaşık 35.000 eklemede biri çakışır. Bunu üretimde göreceksiniz; bu yüzden bir yeniden deneme yoluna ihtiyacınız var, ama ucuz.

Çakışma Yönetimi: Kararı Veritabanına Bırakın

Çalışan örüntü, önce kontrol et sonra ekle değil, ekle sonra yeniden dene'dir. İki istek de aB3x9Qz kodunun boş olduğunu kontrol edip sonra ikisi de yazabilir. Kod sütunundaki bir benzersizlik kısıtı bu yarışı kapatır ve başarısız ekleme yeniden çekmeniz için sinyalinizdir.

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

Burada tryInsert, INSERT'ünüzü çalıştırır ve yalnızca bir benzersizlik ihlali hatasında false döndürür, diğer hatalarda asla. Tek bir ekleme p olasılıkla çakışıyorsa, tüm denemeler p^deneme olasılıkla başarısız olur. 100M bağlantı, 7 karakter noktasında p 2,84 x 10^-5'tir; bu yüzden art arda üç başarısızlık yaklaşık 2,3 x 10^-14'tür. Yine de denemeleri sınırlayın. Sınırın aşıldığını görürseniz, anahtar uzayı neredeyse dolu ya da rastgele kaynak bozuktur ve yüksek sesli bir hata sonsuz bir döngüden iyidir.

Aynı disiplin oluşturma uç noktasındaki idempotency için de geçerlidir, çünkü yeniden denenen bir HTTP isteği ikinci bir bağlantı üretmemelidir. Hız sınırları ve idempotency o yarıyı kapsar.

Hash'le ve Kırp: Neden Düşündüğünüzden Erken Çakışır

URL'yi hash'lemek cazip görünür çünkü deterministiktir: aynı URL her zaman aynı kodu verir; böylece kopyalar için bir aramayı atlayabilirsiniz. Bedeli, bir kodun harcayacak yalnızca bu kadar biti olmasıdır. Bir özetin 32 bitini almak 2^32 = 4.294.967.296 değer verir ve yüzde 50 çakışma noktası yaklaşık 77.163 URL'dir. Milyarlar değil. 7 karakterlik bir base62 dilimi (yaklaşık 41,7 bit) bunu kabaca 2,2 milyona iter; bu, rastgele 7 karakterlik bir kodla aynıdır.

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

Yani kırpma hash'i bozmaz. SHA-256 iyidir. Tam 256 bitin çakışma direnci, 41 bite kesilmeye dayanmaz, hepsi bu. Rastgele kod davranışını miras alırsınız; bu yüzden yine yeniden deneme yoluna ve bir çakışmada ne yapılacağına dair bir kurala (tuzla ve yeniden hash'le) ihtiyacınız var. Ve determinizm size karşı çalışır: aynı URL'yi kısaltan iki müşteri aynı kodu ve dolayısıyla aynı tıklama akışını alır; bir hesap kimliği karıştırmadığınız sürece. Hash'le ve kırp yöntemini neredeyse her durumda atlardım. Kopya tespiti istiyorsanız, URL'yi bir hash sütunuyla arayın ve kodu yine başka bir yolla üretin.

Sayaç Aralıkları ve Snowflake Tarzı Kimlikler

Birkaç bölgedeki birkaç yazıcının kimliğe ihtiyacı olduğunda tek bir otomatik artan sütun darboğaz olur. İki örüntü, benzersizlikten vazgeçmeden bundan kaçınır.

Birincisi sayaç aralıklarıdır. Bir koordinatör her uygulama örneğine, diyelim 1.000 kimlikli bir blok verir ve örnek bunları bağlantı başına bir gidiş dönüş olmadan yerelde kodlar. Bir örnek ölürse, kullanılmayan bloğu basitçe atlanır. Trilyonlarca kodluk bir uzaydaki boşluklar zararsızdır.

İkincisi Snowflake tarzı bir kimliktir: 64 bite paketlenmiş bir zaman damgası, bir makine kimliği ve milisaniye başına bir dizi numarası. Bunlar oluşturma zamanına göre sıralanır ve bir koordinatör gerektirmez. Kısa bağlantılar için tuzak uzunluktur. 64 bitlik bir değer en fazla 18.446.744.073.709.551.615'tir ve 62^10 = 839.299.365.868.340.224, 2^64'ten küçük olduğu için en fazla 11 base62 karakter gerektirir. Bu pek kısa değil. Snowflake kimlikleri herkese açık kodlardan çok veritabanı anahtarlarına uyar; bu yüzden çoğu kısaltıcı onları dahili tutar ve ayrı, daha kısa bir kod kullanır.

İkisi de sıralı tahmin edilebilirlik sorununu miras alır, çünkü ikisi de yapısı gereği sıralıdır. Onları bir permütasyonla sarın ya da yalnızca birini dahili birincil anahtar olarak kullanın.

Özel Kodlar ve Ayrılmış Sözcükler

Vanity slug'ları, kodu bir insanın seçtiği tek yerdir ve diğer her şeyle aynı benzersizlik kısıtından geçerler. Ek iş, eklemeden önce doğrulamadır. /spring-sale gibi bir özel arka yarı üç şeye karşı kontrol edilmelidir.

• Ayrılmış sözcükler. Uygulamanızın veya web'in zaten kullandığı yollar asla talep edilebilir olmamalıdır: api, admin, login, static, robots.txt, favicon.ico ve .well-known. Birinin /login kaydetmesine izin veren bir kısaltıcı, bir kimlik avı sayfası üreticisi inşa etmiştir.
• Üretilen kodlarla çakışmalar. Bir kullanıcı /aB3x9Qz alırsa, rastgele üreticiniz daha sonra aynı dizeyi üretebilir. Özel ve üretilen kodlar tek bir ad alanını paylaştığı sürece benzersizlik kısıtı bunu halleder.
• Büyük/küçük harf ve benzerler. Base62 büyük/küçük harfe duyarlıdır; bu yüzden /Ab ve /ab farklı bağlantılardır. Özel slug'ların büyük/küçük harfe duyarsız karşılaştırılıp karşılaştırılmayacağına karar verin ve yalnızca 0/O veya l/1 ile ayrılan çiftleri engellemeyi düşünün. Vanity URL rehberi markalama tarafını kapsar.

Rastgele 7 karakterlik kodlar talihsiz bir şey de hecelenebilir. Üretilen kodları kısa bir engelleme listesinden geçirin ve eşleşmede yeniden çekin. Neredeyse hiçbir şeye mal olmaz.

Sıralama, Tahmin Edilebilirlik ve Gizlilik

Bir kısa kod bir adrestir. Bir sır değildir ve hiçbir uzunluk onu bir sır yapmaz. Yine de sıralı ile rastgele arasındaki fark büyüktür. Sıralı kodlarda her tahmin canlı bir bağlantıya isabet eder. 62^7 değer arasına rastgele dağılmış 10 milyon bağlantıyla, kör bir tahminin birine isabet etme olasılığı 10.000.000 / 3.521.614.606.208, yaklaşık 352.000'de 1'dir. Bir tarayıcı bulgu başına yüz binlerce isteğe ihtiyaç duyar; hız sınırlama ve bot tespiti bunu cezalandırabilir.

Bir hedefin gizli kalması gerekiyorsa, kodun bir yetki (capability) olması gerekir. Bu, en az 128 bit rastgelelik demektir; base62'de bu 22 karakterdir (62^22 yaklaşık 2^131'dir; 21 karakter yalnızca yaklaşık 2^125 verir). Ayrıca arkasında gerçek bir erişim kontrolüne ihtiyaç duyar. OWASP'ın güvensiz doğrudan nesne referansları üzerine rehberi aynı noktayı yapar: tahmin edilemez tanımlayıcılar yardımcı olur, ama yetkilendirme kontroldür. Parola korumalı veya süresi dolan bağlantılar, sızan bir kodun zarar vereceği durumlar içindir. URL kısaltıcı güvenlik kontrol listesi onunla eşleştirilecek kontrolleri listeler ve kısaltıcıların nasıl çalıştığının mekaniği kodun tek başına neden asla güven taşıyamayacağını açıklar.

Rastgelelik kaynağı aynı nedenle önemlidir. Tohumlanmış, kriptografik olmayan bir üretici birkaç çıktıdan tahmin edilebilir; bu yüzden yukarıdaki kod parçasındaki gibi platformun CSPRNG'sini kullanın. Hazır alternatifler için nanoid, yanlılıksız seçim yaklaşımını yapılandırılabilir bir alfabe ve uzunlukla uygular.

Hangi Yaklaşım Seçilmeli

Kodun neye dayanması gerektiğine göre seçin.

• Dahili araç, düşük hacim: otomatik artan bir kimliğin base62'si. Basit, çakışmasız ve tahmin edilebilirlik önemli değil.
• Herkese açık kısaltıcı, tek veritabanı: ekle ve yeniden dene ile rastgele 7 karakterlik kodlar. Burada başlardım. Yukarıdaki tablo çakışma olasılıklarının yıllarca çok küçük kaldığını gösterir ve daha sonra 8 karaktere geçmek, mevcut her bağlantıyı geçerli tutan tek satırlık bir değişikliktir.
• Çok bölgeli yazmalar: dahili anahtar olarak sayaç aralıkları veya Snowflake kimlikleri, ayrıca herkese açık olarak görünen için bir permütasyon veya rastgele kod.
• Hash'le ve kırp: yalnızca deterministik kodlara ihtiyacınız varsa ve o zaman bunu daha kötü bir yeniden deneme hikâyesi olan rastgele bir kod olarak ele alın.

Ne seçerseniz seçin, kodu benzersiz indeksli bir sütunda saklayın ve üretimi, iki katmanlı bir önbelleğin gerçek işi yaptığı yönlendirme yolunun dışında tutun (p95 gecikme yazısı o yolun ayarlandığında neye benzediğini gösterir). Kod üretimine, çakışma yönetimine ve ayrılmış sözcük listelerine sahip olmak istemiyorsanız, Elido'nun API'si bir hedef alır ve bir kısa bağlantı döndürür; özel arka yarılar sizin için doğrulanır. Denemek istediğinizde planlara bakın.

Blogda İlgili Yazılar

• Bir URL kısaltıcı nasıl inşa edilir - bu yazının yakınlaştırdığı tam mimari.
• URL kısaltıcılar nasıl çalışır - kavramsal giriş.
• Özel arka yarı nedir? - kod uzayının insanın seçtiği yarısı.
• URL yönlendirmeleri için önbellek stratejisi - kod var olduktan sonra olanlar.
• Açık yönlendirme zafiyetleri - kodun neden saklanmış bir hedefe eşlenmesi gerektiği.
• URL kısaltıcı güvenlik kontrol listesi