Pemendek URL

Desain pemendek URL: hashing, penyimpanan, redirect, dan analisis kebutuhannya.

Daftar isi

Pemendek URL adalah layanan yang menukar tautan panjang dengan kode pendek, lalu mengirimkan redirect, yaitu respons yang menyuruh browser menuju tautan asalnya. Topik ini memandu perancangan layanan tersebut dengan kerangka yang sama seperti topik studi kasus lainnya, yaitu kebutuhan dan estimasi, antarmuka API, desain tingkat tinggi, pendalaman komponen, dan analisis mode kegagalan. Seluruh perhitungan dikerjakan oleh program Python yang dapat dieksekusi ulang, sehingga setiap angka pada topik ini dapat diperiksa kembali.

Kebutuhan dan estimasi#

Layanan ini membutuhkan tiga kemampuan fungsional. Pertama, menerima tautan panjang dan mengembalikan kode pendek yang belum pernah digunakan. Kedua, menerima kode pendek dan mengirimkan respons redirect ke tautan asalnya. Ketiga, mencatat jumlah kunjungan untuk setiap kode sebagai statistik minimal. Kebutuhan nonfungsionalnya ringkas karena pola bebannya sangat timpang, yaitu operasi baca jauh lebih sering daripada tulis, dan setiap redirect harus berlatensi rendah karena pengunjung menunggu sebelum halaman tujuan terbuka.

Estimasi memakai angka layanan internal berukuran sedang. Apabila 10 juta tautan baru dibuat per tahun dan setiap tautan dibaca 100 kali, totalnya menjadi 1 miliar redirect per tahun, atau sekitar 32 redirect per detik. Beban tulisnya kecil, sekitar 0,3 tautan baru per detik, sehingga tantangan desainnya bukan volume, melainkan ruang kode dan jalur baca yang tetap cepat. Ruang kode tumbuh eksponensial terhadap panjang kode karena setiap karakter base62, yaitu notasi bilangan dengan 62 simbol berupa angka, huruf kecil, dan huruf besar, membawa 62 kemungkinan, sehingga kode tujuh karakter sudah menyediakan $62^{7} \approx 3{,}5 \times 10^{12}$ kode berbeda.

Kode pendek dapat dihasilkan dengan dua cara. Cara pertama memotong keluaran hash, yaitu fungsi yang memetakan masukan berapa pun panjangnya menjadi nilai dengan panjang tetap, dari tautan panjangnya. Cara kedua mengenkode bilangan penghitung yang bertambah satu setiap tautan baru. Kedua cara ini dibedah dengan program pada bagian selanjutnya.

Antarmuka API#

Antarmuka pemendek URL cukup tiga endpoint. Pembuatan tautan memakai POST, redirect memakai GET pada kode pendeknya, dan statistik memakai GET terpisah agar jalur redirect tidak membawa beban tambahan.

text Contoh: API pemendek URL

POST /api/tautan
  isi    : {"url": "https://contoh.example/panduan/tulis-dokumen"}
  jawab  : {"kode": "4c91", "pendek": "https://pndk.example/4c91"}

GET /{kode}
  jawab  : 302 Found dengan header Location berisi tautan panjang
           404 Not Found apabila kode tidak terdaftar

GET /api/tautan/{kode}/statistik
  jawab  : {"klik": 15823, "dibuat": "2026-05-14"}

Status redirect yang dipilih menentukan nasib statistik. Status 301 menandai pemindahan permanen, sehingga browser menyimpan pemetaan itu dan kunjungan berikutnya tidak pernah melewati layanan pemendek lagi, sedangkan statistik klik kehilangan sebagian besar datanya. Status 302 menandai pemindahan sementara, sehingga browser bertanya kembali pada layanan setiap kali kode diakses. Karena pencatatan kunjungan termasuk kebutuhan fungsional, jalur redirect memilih 302. Pembuatan tautan sendiri dapat dibuat idempoten secara praktis, yaitu apabila tautan panjang yang sama dikirim lagi, layanan mengembalikan kode yang sudah ada setelah mencarinya lebih dahulu. Pilihan ini menghemat ruang kode dengan tambahan satu pencarian pada jalur tulis yang bebannya kecil.

Desain tingkat tinggi#

Desainnya memisahkan jalur tulis dan jalur baca sejak load balancer, karena karakter bebannya berbeda. Jalur baca hanya membaca, sehingga dilayani oleh beberapa instance layanan redirect yang tidak menyimpan keadaan sama sekali, dengan cache di depan basis data. Jalur tulis memanggil penghitung kode untuk memperoleh nilai berikutnya, lalu menyimpan pasangan kode dan tautan panjang ke basis data.

Desain tingkat tinggi pemendek URL dengan jalur tulis dan jalur baca yang terpisah

Pemisahan ini membuat tiap jalur diskalakan sendiri. Layanan redirect yang tidak menyimpan keadaan dapat ditambah sewaktu-waktu tanpa koordinasi, sedangkan penghitung kode tetap satu sumber kebenaran untuk tulisan. Penghitung itulah satu-satunya komponen yang bekerja berurutan, dan kebutuhannya kecil, yaitu 0,3 tautan baru per detik pada estimasi, sehingga satu instance pun cukup. Cache menahan sebagian besar trafik baca karena tautan populer diakses berkali-kali, dan basis data hanya menerima cache miss beserta seluruh tulisan baru.

Penghitung kode dan base62#

Pendekatan penghitung memperlakukan kode pendek sebagai bilangan bulat yang dienkode base62. Berkas berikut mengonversi beberapa nilai penghitung menjadi kode dan mencetak kapasitas untuk beberapa panjang kode. Alfabetnya tersusun dari angka, huruf kecil, lalu huruf besar, sehingga urutan kode mengikuti urutan bilangannya.

python base62.py

"""Konversi bilangan penghitung menjadi kode base62 untuk pemendek URL.

Alfabet base62 tersusun dari angka, huruf kecil, lalu huruf besar, sehingga
urutan kode mengikuti urutan bilangan penghitungnya. Program mencetak tabel
contoh konversi dan kapasitas ruang kode untuk beberapa panjang kode.
"""

ALFABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"


def ke_base62(n: int) -> str:
    if n < 0:
        raise ValueError("penghitung tidak boleh negatif")
    if n == 0:
        return ALFABET[0]
    digit = []
    while n > 0:
        n, sisa = divmod(n, 62)
        digit.append(ALFABET[sisa])
    return "".join(reversed(digit))


if __name__ == "__main__":
    contoh = [0, 1, 9, 10, 35, 36, 61, 62, 3843, 3844, 999_999]
    print("penghitung -> kode")
    for n in contoh:
        print(f"{n:>9} -> {ke_base62(n)}")

    print()
    print("panjang kode   kapasitas kode berbeda")
    for panjang in range(4, 9):
        kapasitas = 62 ** panjang
        print(f"{panjang:>7}       {kapasitas:>23,}")

text Keluaran

penghitung -> kode
        0 -> 0
        1 -> 1
        9 -> 9
       10 -> a
       35 -> z
       36 -> A
       61 -> Z
       62 -> 10
     3843 -> ZZ
     3844 -> 100
   999999 -> 4c91

panjang kode   kapasitas kode berbeda
      4                    14,776,336
      5                   916,132,832
      6                56,800,235,584
      7             3,521,614,606,208
      8           218,340,105,584,896

Tabel konversi memperlihatkan pergantian digit, yaitu nilai 10 menjadi a, nilai 36 menjadi A, dan nilai 999.999 cukup ditulis 4c91. Kapasitas naik 62 kali untuk setiap karakter tambahan, dan kode tujuh karakter sudah menampung lebih dari 3,5 triliun tautan, jauh melampaui 10 juta tautan per tahun pada estimasi kebutuhan. Keunggulan pendekatan ini adalah kepastian keunikannya, karena dua tautan tidak pernah memperoleh kode yang sama tanpa perlu pemeriksaan apa pun. Kelemahannya, kode yang berurutan mudah ditebak, sehingga tautan pribadi tidak boleh mengandalkan kerahasiaan kodenya, dan layanan semacam itu menambahkan token acak terpisah alih-alih memperpanjang kode.

Pembanding kode dari hash#

Pendekatan hash bekerja sebaliknya. Nilai hash dari tautan panjang dihitung, dipotong sepanjang kode yang diinginkan, lalu dipetakan ke base62. Pemotongan inilah sumber risikonya, karena dua tautan berbeda dapat memperoleh kode yang sama, kejadian yang disebut tabrakan. Perkiraan jumlah pasangan tabrakan mengikuti paradoks ulang tahun, yaitu $\frac{n^{2}}{2m}$ untuk $n$ tautan dan ruang kode berukuran $m$ .

Berkas berikut membandingkan kedua pendekatan pada 10.000 tautan dengan kode empat karakter. Panjang kode sengaja dipendekkan dari contoh sebelumnya agar tabrakan benar-benar terlihat pada jumlah tautan yang kecil.

python pembanding-hash.py

"""Pembanding dua cara menghasilkan kode pendek: penghitung dan hash.

Kode sepanjang 4 karakter base62 sengaja dipilih agar tabrakan hash
benar-benar terlihat pada jumlah tautan yang kecil. Kode hash diambil
dari sha256 URL panjang yang dipotong, sedangkan kode penghitung
diambil dari bilangan urutan pendaftaran tautan.
"""

import hashlib

ALFABET = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
PANJANG_KODE = 4
JUMLAH_TAUTAN = 10_000


def ke_base62(n: int, panjang: int) -> str:
    digit = []
    for _ in range(panjang):
        n, sisa = divmod(n, 62)
        digit.append(ALFABET[sisa])
    return "".join(reversed(digit))


def kode_dari_hash(url: str) -> str:
    ringkas = hashlib.sha256(url.encode()).digest()
    nilai = int.from_bytes(ringkas, "big") % (62 ** PANJANG_KODE)
    return ke_base62(nilai, PANJANG_KODE)


if __name__ == "__main__":
    print(f"jumlah tautan : {JUMLAH_TAUTAN:,}")
    print(f"panjang kode  : {PANJANG_KODE} karakter (ruang {62 ** PANJANG_KODE:,} kode)")
    print()

    kode_penghitung = {ke_base62(i, PANJANG_KODE) for i in range(JUMLAH_TAUTAN)}
    print(f"penghitung    : {len(kode_penghitung):,} kode unik, tabrakan 0")

    kode_hash = {kode_dari_hash(f"https://contoh.example/artikel/{i}")
                 for i in range(JUMLAH_TAUTAN)}
    tabrakan = JUMLAH_TAUTAN - len(kode_hash)
    estimasi = JUMLAH_TAUTAN * (JUMLAH_TAUTAN - 1) / (2 * 62 ** PANJANG_KODE)
    print(f"hash          : {len(kode_hash):,} kode unik, tabrakan {tabrakan}")
    print(f"estimasi tabrakan (n^2 / 2m): {estimasi:.1f}")

text Keluaran

jumlah tautan : 10,000
panjang kode  : 4 karakter (ruang 14,776,336 kode)

penghitung    : 10,000 kode unik, tabrakan 0
hash          : 9,995 kode unik, tabrakan 5
estimasi tabrakan (n^2 / 2m): 3.4

Keluarannya memperlihatkan lima tabrakan nyata pada kode hash, dekat dengan estimasi 3,4 yang menghitung perkiraan jumlah pasangan tabrakan, sedangkan penghitung menghasilkan 10.000 kode unik tanpa pemeriksaan apa pun. Setiap tabrakan pada kode hash harus ditangani dengan memeriksa penyimpanan saat pembuatan dan mengulang perhitungan dengan salt, yaitu tambahan acak pada masukan hash, apabila kode sudah dimiliki tautan lain. Pendekatan hash tetap masuk akal bila kode tidak boleh membeberkan urutan pendaftaran tautan, tetapi biaya pemeriksaan tabrakan selalu melekat padanya.

Penyimpanan dan cache#

Basis data yang cocok untuk layanan ini sederhana, yaitu penyimpanan kunci-nilai dengan kode sebagai kunci dan tautan panjang, waktu pembuatan, serta penghitung klik sebagai isinya. Kode dan tautan panjang tidak pernah berubah setelah dibuat, sehingga cache dapat menyimpan entri lama dengan TTL panjang tanpa menimbulkan masalah invalidasi. Angka yang berubah hanyalah penghitung klik, dan angka itu tidak perlu segar di cache. Pencatatan klik sendiri dikirim melalui queue agar jalur redirect tidak menunggu tulisan selesai, sehingga latensinya tetap pendek.

Dengan entri yang tidak berubah dan cache negatif untuk kode yang tidak ada, basis data hanya menerima tulisan baru, pembaruan statistik yang boleh tertunda, dan cache miss dari kode yang jarang dibaca. Ketiganya berorde kecil dibandingkan dengan 32 redirect per detik pada estimasi, sehingga basis data berukuran wajar sudah menutup kebutuhan bertahun-tahun.

Mode kegagalan#

Basis data mati. Redirect untuk kode yang masih tersimpan di cache tetap berjalan, sedangkan sisanya menerima error. Replika baca pada basis data dan cache yang hangat membatasi dampaknya, tetapi tautan yang jarang dibaca memang tidak terselamatkan.
Cache mati. Seluruh trafik baca jatuh ke basis data, sehingga latensi naik dan throughput turun, tetapi layanan tetap berjalan. Kapasitas basis data direncanakan mampu menanggung beban puncak tanpa cache, atau cache diberi cadangan instance.
Penghitung kode mati. Tulisan baru gagal, sedangkan redirect tidak terpengaruh sama sekali. Nilai terakhir penghitung disimpan secara permanen agar layanan tulis dapat melanjutkan penomoran tanpa menghasilkan kode ganda setelah pulih.
Queue statistik mati. Kunjungan tetap dilayani dan redirect tidak tertunda, tetapi sebagian klik tidak tercatat. Kehilangan sebagian data statistik biasanya dapat diterima, dan keputusan itu perlu dinyatakan secara eksplisit pada desain.

Kesalahan umum#

Mengirimkan status 301 padahal statistik diinginkan. Browser menyimpan pemetaan 301 secara permanen, sehingga kunjungan berikutnya tidak pernah tercatat. Perbaikannya adalah memakai 302 pada jalur redirect.
Merencanakan panjang kode tanpa menghitung kapasitasnya. Kode terlalu pendek mempersempit ruang dan mempercepat habisnya, sedangkan kode terlalu panjang memboroskan setiap penulisan tautan. Kapasitas pada tabel base62 menjadi dasar pilihannya.
Memakai kode dari hash tanpa pemeriksaan tabrakan. Dua tautan berbeda dapat mengarah ke satu kode dan salah satu tautannya tidak pernah terjangkau. Pemeriksaan pada penyimpanan wajib ada bila pendekatan hash dipilih.
Mengarahkan kode yang tidak terdaftar ke halaman utama. Perilaku itu menyembunyikan tautan rusak dari pembuatnya dan membuat trafik pemindai terlihat seperti kunjungan sah. Respons 404 yang jelas lebih informatif bagi keduanya.

Ringkasan#

Estimasi menunjukkan beban tulis yang kecil, sekitar 0,3 tautan baru per detik, dan beban baca sekitar 32 redirect per detik, sehingga desainnya berpusat pada jalur baca yang cepat.
Kode dari penghitung base62 unik tanpa pemeriksaan, sedangkan kode dari hash yang dipotong menanggung risiko tabrakan sebesar $\frac{n^{2}}{2m}$ dan wajib diperiksa.
Status 302 menjaga statistik tetap utuh karena browser selalu bertanya kembali pada layanan, dan cache dengan TTL panjang menahan sebagian besar trafik baca karena isinya tidak berubah.

Referensi#

Uniform Resource Identifier (URI): Generic Syntax — IETF — Spesifikasi bentuk URI yang menjadi dasar tautan panjang dan kode pendeknya.
302 Found — MDN Web Docs — Perilaku status 302 sebagai redirect sementara dan konsekuensinya terhadap cache browser.