System Design 3: Design a URL Shortener

Mendesain Layanan Pemendek URL seperti tinyurl

Pendahuluan

Sekarang kita akan membahas salah satu pertanyaan yg klasik dalam wawancara system design: Merancang layanan pemendek URL, seperti TinyURL.

Langkah 1 - Memahami Masalah dan Menentukan Ruang Lingkup Desain

Pertanyaan dalam wawancara system design sengaja dibuat terbuka. Untuk merancang sistem yang baik, penting untuk mengajukan pertanyaan klarifikasi.

Kandidat: Bisa berikan contoh bagaimana layanan pemendek URL bekerja? Pewawancara: Misalnya, ada URL asli: https://www.systeminterview.com/q=chatsystem&c=loggedin&v=v3&l=long. Layanan ini akan membuat alias yang lebih pendek, seperti: https://tinyurl.com/y7keocwj. Jika pengguna mengklik alias tersebut, mereka akan diarahkan ke URL asli.

Kandidat: Berapa volume trafiknya? Pewawancara: Layanan ini menghasilkan 100 juta URL per hari.

Kandidat: Seberapa pendek URL yang dihasilkan? Pewawancara: Sependek mungkin.

Kandidat: Karakter apa saja yang diperbolehkan dalam URL yang dipersingkat? Pewawancara: URL yang dipersingkat bisa terdiri dari kombinasi angka (0-9) dan huruf (a-z, A-Z).

Kandidat: Apakah URL yang sudah dipersingkat bisa dihapus atau diperbarui? Pewawancara: Untuk menyederhanakan desain, kita anggap URL yang sudah dibuat tidak bisa dihapus atau diperbarui.

Kasus Penggunaan Utama

1. Pemendekan URL → Diberikan URL panjang → Menghasilkan URL pendek.

2. Pengalihan URL → Diberikan URL pendek → Mengarahkan ke URL asli.

3. Ketersediaan tinggi (high avaibility), skalabilitas, dan toleransi kesalahan.

Estimasi Kasar (Back-of-the-Envelope Estimation)

• Operasi penulisan: 100 juta URL dibuat setiap hari.

• Operasi penulisan per detik: 100juta / 24 / 3600 = 1160

• Operasi pembacaan: Jika rasio baca : tulis = 10 : 1, maka: 1160 × 10 = 11.600 operasi

• Total URL yang harus didukung dalam 10 tahun: 100 juta × 365 hari × 10 tahun = 365 miliar record atau data

• Asumsi rata-rata panjang URL = 100 karakter.

• Total kebutuhan penyimpanan selama 10 tahun: 365 miliar × 100 byte = 365 TB

Penting untuk menjelaskan asumsi dan perhitungan ini kepada pewawancara agar memiliki pemahaman yang sama.

Langkah 2 - Mengusulkan High Level Architecture dan Mendapatkan Persetujuan

Pada bagian ini, kita akan membahas endpoint API, alur pengalihan URL (URL redirecting), dan alur pemendekan URL (URL shortening).

Endpoint API

Endpoint API digunakan untuk komunikasi antara klien dan server. Kita akan menggunakan pendekatan RESTful API. Jika belum familiar dengan RESTful API, bisa merujuk ke sumber lain.

Layanan pemendek URL memerlukan dua endpoint utama:

1. Pemendekan URL Untuk membuat URL pendek baru, klien mengirimkan permintaan POST dengan parameter URL panjang (long URL). Endpoint:

   POST /api/v1/data/shorten

   • Request Body:

     {
       "longUrl": "https://example.com/some/long/url"
     }

   • Response:

     {
       "shortUrl": "https://tinyurl.com/y7keocwj"
     }

2. Pengalihan URL Untuk mengarahkan URL pendek ke URL panjangnya, klien mengirim permintaan GET ke URL pendek. Endpoint:

   /api/v1/{shortUrl}

   • Response:

     • Mengembalikan URL panjang dengan redirect HTTP.

Pengalihan URL (URL Redirecting)

Saat pengguna memasukkan URL pendek di browser, server akan menerjemahkannya menjadi URL panjang dan melakukan redirect.

Terdapat dua jenis redirect HTTP yang dapat digunakan:

1. 301 Redirect (Permanent Redirect)

   • Menunjukkan bahwa URL telah dipindahkan secara permanen.

   • Browser akan menyimpan (cache) hasil redirect, sehingga permintaan berikutnya langsung menuju ke server tujuan tanpa melewati layanan pemendek URL.

   • Keuntungan: Mengurangi beban server pemendek URL.

   • Kekurangan: Tidak bisa melacak statistik klik secara akurat.

2. 302 Redirect (Temporary Redirect)

   • Menunjukkan bahwa URL dipindahkan sementara.

   • Browser tidak menyimpan cache, sehingga setiap permintaan selalu melewati server pemendek URL sebelum diarahkan ke URL panjang.

   • Keuntungan: Bisa digunakan untuk melacak klik dan sumber traffic.

   • Kekurangan: Beban server lebih tinggi dibanding 301 redirect.

Pemilihan antara 301 dan 302 tergantung pada kebutuhan:

• Jika ingin mengurangi beban server → Gunakan 301 Redirect.

• Jika ingin melacak statistik kunjungan → Gunakan 302 Redirect.

Secara teknis, implementasi pengalihan URL dapat dilakukan menggunakan hash table yang menyimpan pasangan nilai <shortURL, longURL>.

hashTable.get(shortURL)  
redirect(longURL)

Pemendekan URL (URL Shortening)

URL pendek yang dihasilkan biasanya memiliki format seperti ini:

https://tinyurl.com/{hashValue}

Agar dapat membuat URL pendek, kita perlu fungsi hash yang mengubah long URL menjadi hashValue, seperti ilustrasi berikut:

hashValue = f(longURL)

Fungsi hash harus memenuhi kriteria berikut:

• Setiap long URL harus memiliki hashValue unik.

• Setiap hashValue dapat dikonversi kembali ke long URL.

Detail mengenai algoritma hash akan dibahas lebih lanjut di bagian deep dive.

Langkah 3 - Desain Mendalam

Sampai tahap ini, kita telah membahas desain tingkat tinggi untuk pemendekan URL dan pengalihan URL. Sekarang, kita akan mendalami aspek teknis berikut:

1. Model Data

2. Fungsi Hash

3. Alur Pemendekan URL

4. Alur Pengalihan URL

---

Model Data

Pada desain tingkat tinggi, kita menyimpan pasangan <shortURL, longURL> dalam hash table. Namun, pendekatan ini tidak efisien karena:

• Keterbatasan memori: Menyimpan semua data di memori bisa menjadi mahal.

• Data yang harus persist: Informasi harus tetap ada meskipun sistem restart.

Solusi yang lebih baik adalah menggunakan database relasional untuk menyimpan pasangan shortURL ↔ longURL.

Desain Tabel Database

Tabel sederhana untuk menyimpan URL pendek bisa memiliki tiga kolom utama:

• id (Primary Key, Auto Increment)

• short_url (VARCHAR, unik)

• long_url (TEXT, menyimpan URL asli)

CREATE TABLE urls (
    id BIGINT PRIMARY KEY AUTO_INCREMENT,
    short_url VARCHAR(10) UNIQUE NOT NULL,
    long_url TEXT NOT NULL
);

Dengan struktur ini, kita bisa mengambil, menyimpan, dan mengelola URL secara efisien.

Fungsi Hash

Fungsi hash digunakan untuk mengubah URL panjang menjadi URL pendek, yang disebut sebagai hashValue.

Panjang hashValue

Hash value terdiri dari karakter [0-9, a-z, A-Z], sehingga ada (10 + 26 + 26) = 62 kemungkinan karakter. Untuk menentukan panjang yang cukup untuk mendukung 365 miliar URL, kita harus mencari n terkecil sehingga: 62 ^ n ≥ 365 miliar

Panjang (n)	Maksimal URL yang Didukung
1	62 ^ 1 = 62
2	62 ^ 2 = 3,844
3	62 ^ 3 = 238,328
4	62 ^ 4 = 14,776,336
5	62 ^ 5 = 916,132,832
6	62 ^ 6 = 56,800,235,584
7	62 ^ 7 = 3,521,614,606,208 = ~ 3.5 triliun

Ketika n = 7, nilai 62^7 ≈ 3,5 triliun, yang lebih dari cukup untuk menampung 365 miliar URL. Oleh karena itu, panjang hashValue yang digunakan adalah 7 karakter.

Kita akan mengeksplorasi dua jenis fungsi hash untuk layanan pemendek URL:

1. “Hash + Collision Resolution”

2. “Base 62 Conversion”

Mari kita bahas satu per satu.

Hash + Penyelesaian Tabrakan (Collision Resolution)

Untuk mempersingkat URL panjang, kita harus mengimplementasikan fungsi hash yang mengonversi URL panjang menjadi string sepanjang 7 karakter.

Pendekatan Awal

Pendekatan sederhana adalah menggunakan fungsi hash yang sudah dikenal, seperti CRC32, MD5, atau SHA-1. Namun, berdasarkan hasil perbandingan di Tabel 8-2, bahkan CRC32—yang menghasilkan hash terpendek—masih terlalu panjang (lebih dari 7 karakter).

Bagaimana Cara Memendekkannya?

Pendekatan pertama adalah mengambil 7 karakter pertama dari nilai hash. Namun, metode ini dapat menyebabkan tabrakan hash (hash collision), di mana dua URL berbeda menghasilkan hash yang sama.

Untuk mengatasi tabrakan:

1. Jika terjadi tabrakan, kita dapat menambahkan string tertentu (misalnya angka atau karakter tambahan) secara rekursif sampai hash yang dihasilkan unik.

2. Namun, cara ini membutuhkan banyak kueri ke database untuk memeriksa apakah shortURL sudah ada.

Optimasi dengan Bloom Filter

Agar lebih efisien, kita dapat menggunakan Bloom Filter. Bloom Filter adalah teknik probabilistik hemat ruang yang dapat memeriksa apakah suatu elemen sudah ada dalam suatu set tanpa harus selalu melakukan kueri ke database.

Konversi Base 62

Pendekatan lain yang umum digunakan dalam layanan pemendek URL adalah konversi basis angka, khususnya Base 62.

Apa Itu Base 62?

Base 62 digunakan karena ada 62 kemungkinan karakter yang dapat digunakan untuk membentuk hashValue:

• 0-9 → untuk angka (0-9)

• a-z → untuk huruf kecil (10-35)

• A-Z → untuk huruf besar (36-61)

Bagaimana Cara Kerjanya?

Konversi ini memungkinkan kita untuk mengubah angka dalam sistem bilangan desimal (Base 10) menjadi Base 62.

Contoh: Misalkan kita ingin mengonversi 11157 (Base 10) ke Base 62.

• 11157 dibagi dengan 62 secara berulang untuk mendapatkan representasi Base 62: 11157 base 10 = 2×62^2 + 55×62^1 + 59×62^0 Hasilnya adalah [2, 55, 59], yang dikonversi menjadi [2, T, X] dalam Base 62.

Conversation Proses

Perbandingan dua pendekatan untuk menghasilkan short URL:

1. Hash + Collision Resolution

   • Panjang URL pendek tetap.

   • Tidak memerlukan ID unik.

   • Kemungkinan terjadi tabrakan (collision) sehingga harus diselesaikan.

   • Sulit untuk menebak URL pendek berikutnya.

2. Base 62 Conversion

   • Panjang URL pendek tidak tetap, tergantung pada ID.

   • Bergantung pada generator ID unik.

   • Tidak ada kemungkinan tabrakan karena setiap ID unik.

   • Mudah ditebak jika ID bertambah secara berurutan, yang bisa menjadi masalah keamanan.

Base 62 conversion dipilih sebagai metode untuk URL shortening karena memberikan efisiensi dalam pembuatan URL pendek dengan memastikan setiap ID unik. Berikut adalah alur kerja untuk proses URL shortening dengan Base 62 conversion:

1. Menerima Permintaan

   • Pengguna mengirimkan permintaan ke endpoint API untuk memperpendek URL.

   • Contoh: POST /api/v1/data/shorten dengan payload { "longUrl": "https://example.com" }.

2. Menyimpan Data di Database

   • Server menyimpan URL asli (longUrl) dalam database.

   • Setiap entri mendapatkan ID unik (auto-increment dari database).

3. Mengubah ID menjadi Base 62

   • ID yang dihasilkan diubah ke dalam format Base 62 menggunakan karakter [0-9a-zA-Z].

   • Contoh: ID 1000000 dikonversi ke Base 62 menjadi 4c92.

4. Menghasilkan Short URL

   • Base 62 hash (4c92) ditambahkan ke domain layanan URL shortener.

   • Contoh hasil: https://short.ly/4c92.

5. Mengembalikan Short URL ke Klien

   • API mengembalikan URL pendek ke pengguna.

Flow

---

URL Redirecting Deep Dive 🚀

URL redirecting harus dirancang dengan efisien karena jumlah read requests jauh lebih tinggi daripada write requests. Oleh karena itu, kita menggunakan caching untuk mempercepat pencarian short URL.

Alur Kerja URL Redirecting

1. User Mengakses Short URL

   • Contoh: Pengguna mengklik link https://tinyurl.com/zn9edcu.

2. Load Balancer Mendistribusikan Request

   • Load balancer meneruskan permintaan ke salah satu web server yang tersedia.

3. Cek Cache

   • Web server pertama-tama mencari short URL di cache (misalnya, Redis).

   • Jika ditemukan, langsung kembalikan long URL ke pengguna untuk dilakukan redirect.

4. Cache Miss: Cek Database

   • Jika short URL tidak ditemukan di cache, server akan mencarinya di database.

   • Jika ditemukan, long URL dikembalikan ke pengguna dan disimpan kembali di cache untuk akses cepat di masa depan.

5. Jika Short URL Tidak Ada

   • Jika tidak ada di database, kirimkan HTTP 404 Not Found karena kemungkinan URL tidak valid.

6. User Dialihkan ke Long URL

   • Browser pengguna secara otomatis diarahkan ke long URL melalui HTTP 301 (permanent redirect) atau HTTP 302 (temporary redirect).

---

Optimasi Kinerja dengan Cache

Untuk meningkatkan performa, kita bisa menerapkan: ✅ Redis atau Memcached sebagai cache untuk menyimpan mapping <shortURL, longURL>. ✅ Cache Expiration agar entri yang jarang digunakan bisa dibersihkan secara otomatis. ✅ Bloom Filter untuk mengurangi beban database dengan mendeteksi URL yang tidak ada lebih awal.

Wrap-up: URL Shortener System Design 🎉

Kita telah membahas berbagai aspek penting dalam desain sistem URL Shortener, mulai dari API design, data model, hash function, URL shortening, hingga URL redirecting. Berikut adalah beberapa poin tambahan yang bisa didiskusikan lebih lanjut:

---

1️⃣ Rate Limiting untuk Keamanan 🔒

Agar sistem tidak dibanjiri permintaan dari pengguna jahat (malicious users), kita bisa menerapkan rate limiting berdasarkan: ✅ IP address – Membatasi jumlah request dari satu IP dalam periode tertentu. ✅ API key – Mengharuskan pengguna terotentikasi untuk membuat short URL dalam jumlah besar. ✅ Sliding Window Rate Limiter – Menggunakan Redis untuk membatasi request per detik/menit.

📌 Referensi: Jika ingin mempelajari lebih lanjut, bisa melihat bab "Design a Rate Limiter" di Chapter 4.

---

2️⃣ Web Server Scaling ⚖️

Karena web tier bersifat stateless, kita bisa menambahkan atau menghapus server dengan mudah menggunakan: ✅ Load Balancer (Nginx, HAProxy, AWS ALB, GCP Load Balancer, dsb.) ✅ Auto-scaling groups untuk menyesuaikan jumlah server berdasarkan trafik. ✅ Containerization (Docker, Kubernetes) untuk deployment yang lebih fleksibel.

---

3️⃣ Database Scaling 🗄️

Agar database dapat menangani trafik yang tinggi, kita bisa menerapkan: ✅ Replication – Database sekunder (read replicas) untuk menangani beban baca tinggi. ✅ Sharding – Membagi data menjadi beberapa bagian berdasarkan pola tertentu (misalnya, hash dari shortURL). ✅ Caching (Redis, Memcached) – Untuk mengurangi query langsung ke database.

---

4️⃣ Analytics & Monitoring 📊

Menambahkan fitur tracking & analytics bisa memberikan wawasan bisnis seperti: ✅ Berapa banyak orang yang mengklik link ini? ✅ Kapan waktu klik terbanyak? ✅ Dari mana asal trafiknya (referrer tracking)?

🔥 Teknologi yang bisa digunakan:

• Google Analytics, Mixpanel, atau Matomo untuk analisis pengguna.

• Prometheus + Grafana untuk pemantauan performa sistem.

---

5️⃣ Availability, Consistency, & Reliability 🏗️

Dalam sistem berskala besar, tiga konsep ini menjadi pertimbangan utama: ✅ Availability (Ketersediaan) – Sistem harus tetap bisa diakses meskipun ada gangguan (redundansi, failover, load balancing). ✅ Consistency (Konsistensi) – Data harus tetap sinkron antara berbagai server (CAP Theorem: Strong vs. Eventual Consistency). ✅ Reliability (Keandalan) – Sistem harus bisa menangani lonjakan trafik tanpa downtime besar (distributed system best practices).

---

🎯 Kesimpulan

🚀 Kita telah membangun desain yang skalabel, aman, dan efisien untuk URL Shortener. Jika ada waktu tambahan, kita bisa mendiskusikan lebih dalam tentang optimasi query, latensi cache, atau deployment pipeline! 🔥