Gimana Cara Bikin URL Shortener?

9 min readJul 10, 2023

Siapa sih yang nggak pernah make tinyurl? bit.ly? goo.gl? Atau yang lainnya? Semua itu adalah layanan URL shortener. URL shortener adalah sebuah layanan yang memungkinkan kita untuk memendekkan URL yang panjang menjadi URL yang lebih pendek. URL yang lebih pendek ini akan mengarah ke URL yang panjang. URL yang lebih pendek ini biasanya lebih mudah diingat dan lebih mudah dituliskan. Selain itu, URL yang lebih pendek ini juga lebih mudah untuk dibagikan ke sosmed.

Sekarang pertanyaan nya, cara bikinnya tu gimana yah? Nah, di sini kita akan coba cari tau dan bikin implementasi sederhana URL shortener.

Requirements

Requirement phase nya kita simplify aja ya, yang penting temen2 dapet big picture nya. Let say URL pendek yang digenerate nanti terdiri dari kombinasi angka (0–9) dan karakter (a-z, A-Z) dan … udaah gitu doank xixi, kita ngga usah dulu ngomongin estimation, scalability, availability, dll.

High Level Design (API Endpoints)

POST /home
res: home page (landing page html)
POST /shorten
req body: {longUrl}
res body: {shortUrl}
GET /{shortUrl}
redirect to longUrl (either 301 or 302)

URL Redirecting

Karena nanti short url akan di redirect ke url aslinya, terlebih dahulu kita akan bahas perbedaan antara 301 dan 302 redirect.

Redirect 301 (Permanent Redirect) ini menunjukkan bahwa URL yang diminta “secara permanen” dipindahkan ke URL panjang. Karena pengalihan ini bersifat permanen, respons tersebut akan disimpan dalam cache browser, dan permintaan berikutnya untuk URL yang sama tidak akan dikirim ke aplikasi shortener URL. Sebaliknya, permintaan akan langsung dialihkan ke URL yang panjang.

Beda halnya dengan Redirect 302 (Temporary Redirect) yang berarti URL “sementara” dipindahkan ke URL panjang, sehingga permintaan berikutnya untuk URL yang sama akan dikirim terlebih dahulu ke aplikasi URL shortener. Kemudian, permintaan tersebut akan dialihkan ke URL tujuan.

Setiap metode pengalihan memiliki kelebihan dan kelemahannya. Jika prioritasnya adalah mengurangi beban server, menggunakan pengalihan 301 adalah pilihan yang tepat karena hanya permintaan pertama untuk URL yang sama yang dikirimkan ke layanan pemendek URL. Namun, jika analitik menjadi penting, pengalihan 302 merupakan pilihan yang lebih baik karena dapat melacak tingkat klik dan sumber klik dengan lebih mudah.

Cara paling intuitif untuk mengimplementasikan pengalihan URL adalah dengan menggunakan tabel hash. Dengan asumsi tabel hash menyimpan pasangan <shortURL, longURL>, pengalihan URL dapat diimplementasikan dengan langkah-langkah berikut:

Untuk mendapatkan URL panjang dari URL pendek, kita cukup mengambil nilai dari hash table menggunakan shortURL sebagai kunci. Jika tidak ada nilai yang dikembalikan, maka URL pendek tidak ada dalam tabel hash. Jika ada, maka kita dapat mengembalikan nilai yang sesuai (URL panjang)

URL Shortening

Kita asumsikan URL pendek terlihat seperti ini: www.tinyurl.com/{hashValue}. Untuk mendukung kasus penggunaan pemendekan URL, kita harus menemukan fungsi hash fx yang memetakan URL panjang menjadi hashValue.: www.tinyurl.com/{hashValue}. Untuk mendukung kasus penggunaan pemendekan URL, kita harus menemukan fungsi hash fx yang memetakan URL panjang menjadi hashValue.

longURL ➜ fx ➜ hashValue

Fungsi hash harus memenuhi persyaratan berikut:

Setiap longURL harus di-hash menjadi satu hashValue
Setiap hashValue harus dapat dipetakan kembali ke longURL tersebut.

Design Deep Dive

Data Model
Semua informasi disimpan dalam hash table. Ini adalah awal yang baik; namun, pendekatan ini tidak memungkinkan untuk real world system karena resource memori terbatas dan mahell >_< Pilihan yang lebih baik adalah menyimpan pemetaan <shortURL, longURL> dalam sebuah basis data relasional. Anggap aja tabel kita punya 3 kolom: id, shortURL, longURL. that’s it.

Hash Function
Hash function digunakan untuk menghasilkan hashValue dari longURL. Hash function harus menghasilkan nilai yang unik untuk setiap longURL. Jika dua longURL menghasilkan hashValue yang sama, kita harus menghasilkan hashValue yang berbeda. Ini disebut collision. Ketika collision terjadi, kita akan mencoba untuk menemukan slot yang kosong di tabel hash dan menyimpan nilai di sana.

Hash Value Length
Nilai hash terdiri dari karakter-karakter [0–9, a-z, A-Z], yang berarti terdapat 10 + 26 + 26 = 62 karakter yang mungkin. Untuk menentukan panjang nilai hash, cari nilai n terkecil sedemikian sehingga 62^n ≥ 365 miliar. Sistem dapat mendukung hingga 365 miliar URL berdasarkan perkiraan kasar.

Ilustrasi dibawah menunjukkan panjang nilai hash dan jumlah maksimal URL yang dapat didukung.

N = 1, 62¹ = 62
N = 2, 62² = 3844
N = 3, 62³ = 238328
N = 4, 62⁴ = 14776336
N = 5, 62⁵ = 916132832
N = 6, 62⁶ = 56800235584
N = 7, 62⁷ = 3521614606208

kita akan bahas dua jenis fungsi hash untuk alat pemendek URL. Yang pertama adalah hash + collision resolution dan yang kedua adalah base 62 conversion. Mari kita lihat satu per satu.

Hash + collision resolution
Nah, untuk memendekkan URL panjang, kita harus punya fungsi hash yang bisa merubah URL panjang jadi string dengan 7 karakter. Solusi yang gampang sih pakai fungsi hash yang udah terkenal seperti CRC32, MD5, atau SHA-1. Details nya bisa cari di internet yup >_<

Pendekatannya yang pertama adalah mengambil 7 karakter pertama dari nilai hash; tapi, metode ini bisa menyebabkan bentrok hash. Untuk menyelesaikan bentrok hash, kita bisa secara rekursif menambahkan sebuah string yang sudah ditentukan sampai tidak ada lagi bentrok yang ditemukan.

Start ➜ input long url ➜ hash func ➜ short url ➜ exist in db? ➜ (no ➜ return short url) : (yes ➜ long url + predefined string) ➜ hash func … (repeat until no collision) ➜ return short url

Metode ini bisa menghilangkan collision/bentrok. Tapi, costly krna harus ngecek ke basis data apakah ada shortURL untuk setiap permintaan. Ada teknik yang namanya bloom filter yang bisa meningkatkan performa, tapi sekarang kita ga akan bahas itu.

Base 62 conversion
Konversi basis 62 adalah pendekatan lain yang umum digunakan untuk alat pemendek URL. Konversi basis 62 digunakan karena terdapat 62 karakter yang mungkin untuk nilai hash kita. Yuk, kita pakai contoh untuk menjelaskan bagaimana konversi ini bekerja: konversikan 1115710 (base 10) ke representasi basis 62.

Dari namanya, basis 62 adalah cara menggunakan 62 karakter untuk pengkodean. Pemetaan karakternya adalah: 0–0, …, 9–9, 10-a, 11-b, …, 35-z, 36-A, …, 61-Z, dengan ‘a’ mewakili 10, ‘Z’ mewakili 61, dan sebagainya.
1115710 = 2 x 62² + 55 x 62¹ + 59 x 62⁰ = [2, 55, 59] ➜ [2, T, X] dalam representasi basis 62.

Berikut proses konversi tersebut:

11157 / 62 = 179 (sisa 59) ➜ representasi di base 62 = X
179 / 62 = 2 (sisa 55) ➜ representasi di base 62 = T
2 / 62 = 0 (sisa 2) ➜ representasi di base 62 = 2

Short url nya menjadi https://tinyurl.com/2TX

Untuk aplikasi shortener url yang akan kita buat akan menggunakan Base 62 ini

URL Shortener Deep Dive

Berikut adalah flow dari aplikasi shortener URL yang akan kita buat:

Input berupa longURL
Sistem memeriksa apakah longURL ada dalam basis data.
Jika ada, berarti longURL sudah dikonversi menjadi shortURL sebelumnya. Dalam hal ini, ambil shortURL dari basis data dan kembalikan ke client.
Jika tidak ada, berarti longURL baru. ID unik baru (primary key) dihasilkan oleh unique ID generator.
Konversikan ID menjadi shortURL dengan konversi basis 62.
Buat record baru di db dengan ID, shortURL, dan longURL

Untuk memudahkan pemahaman alur tersebut, mari kita lihat contoh konkritnya:

Asumsikan longURL input adalah: https://sport.detik.com/sepakbola/liga-inggris/d-6813019/david-de-gea-resmi-tinggalkan-manchester-united
Generator ID unik menghasilkan ID: 2009215674938.
Konversikan ID menjadi shortURL menggunakan konversi basis 62. ID (2009215674938) dikonversi menjadi “zn9edcu”.
Simpan ke database

id | shortURL | longURL
2009215674938 | zn9edcu | https://sport.detik.com/sepakbola/liga-inggris/d-6813019/david-de-gea-resmi-tinggalkan-manchester-united

Sekarang PR nya adalah bagaimana men generate ID unik, apalagi untuk sistem terdistribusi, ini cukup tricky dan challenging.

URL Redirecting Deep Dive

Flow pengalihan URL kira-kira seperti ini:

Pengguna mengklik tautan URL pendek: https://tinyurl.com/zn9edcu.
Load balancer meneruskan permintaan ke server web (kalau kita pasang lb dan multiple server), kasus kita kali ini hanya 1 server/instance saja.
Jika shortURL sudah ada di cache, kembalikan longURL secara langsung (cache seperti redis, memcached, dll) bisa digunakan untuk mempercepat proses retrieval.
Jika shortURL tidak ada di cache, ambil longURL dari basis data. Jika tidak ada di basis data, kemungkinan pengguna memasukkan shortURL yang tidak valid.
Masukkan longURL ke cache.
longURL dikembalikan kepada pengguna.

Untuk aplikasi yang akan kita buat tidak akan menggunakan database langsung biar proses development nya lebih cepat hehe, kita akan store di map aja (memory datastore)

Unique ID Generator Approach

Sekarang kita kelarin dulu masalah unique id generator approach yang akan kita gunakan.

UUID
UUID (Universally Unique Identifier) adalah cara lain yang mudah untuk mendapatkan ID yang unik. UUID adalah angka 128-bit yang digunakan untuk mengidentifikasi informasi dalam sistem komputer. UUID memiliki kemungkinan collision yang sangat rendah. Mengutip dari Wikipedia, “setelah menghasilkan 1 miliar UUID setiap detik selama sekitar 100 tahun, kemungkinan menciptakan duplikat tunggal akan mencapai 50%”. Berikut adalah contoh UUID: 09c93e62–50b4–468d-bf8a-c07e1040bfb2. UUID dapat dihasilkan secara independen tanpa koordinasi antara server.

Kelebihan:
• Menghasilkan UUID sederhana. Tidak ada koordinasi antara server yang diperlukan sehingga tidak akan ada masalah sinkronisasi.
• Sistem ini mudah untuk diskalakan karena setiap server web bertanggung jawab untuk menghasilkan ID yang mereka gunakan. Generator ID dapat dengan mudah diskalakan dengan server web.

Kekurangan:
• ID memiliki panjang 128 bit, tetapi kebutuhan kita adalah 64 bit.
• ID tidak meningkat seiring waktu.
• ID bisa bukan angka.

Ticker server
Flicker mengembangkan Ticker server untuk menghasilkan kunci primer yang terdistribusi. Ide dari sistem ini adalah menggunakan fitur auto_increment terpusat pada satu server basis data tunggal (Server Tiket).

Kelebihan:
• ID berupa angka.
• Mudah diimplementasikan, dan berfungsi untuk aplikasi skala kecil hingga menengah.

Kekurangan:
• Satu titik kegagalan. Server tiket tunggal berarti jika server tiket mengalami masalah, semua sistem yang bergantung padanya akan mengalami masalah. Untuk menghindari satu titik kegagalan, kita dapat mengatur beberapa server tiket. Namun, ini akan memperkenalkan tantangan baru seperti sinkronisasi data.

Twitter snowflake approach
Pendekatan-pendekatan yang disebutkan di atas memberikan kita beberapa gagasan tentang bagaimana sistem-sistem pembangkitan ID yang berbeda bekerja. Namun, tidak satupun dari mereka memenuhi persyaratan kita secara spesifik; oleh karena itu, kita memerlukan pendekatan lain. Sistem pembangkitan ID unik yang disebut “snowflake” dari Twitter dapat memenuhi persyaratan kita.

Divide and conquer is our friend. Alih-alih menghasilkan ID secara langsung, kita membagi ID menjadi bagian-bagian yang berbeda.

Setiap bagian dijelaskan di bawah ini:
• Sign Bit: 1 bit. Selalu bernilai 0. Ini di reserve untuk penggunaan di masa depan. Potensial digunakan untuk membedakan antara angka bertanda dan angka tak bertanda.
• Timestamp: 41 bit. Milidetik sejak epoch. menggunakan epoch default Twitter snowflake yaitu 1288834974657, setara dengan 4 November 2010, 01:42:54 UTC.
• ID Datacenter: 5 bit, memberi kita 2 ^ 5 = 32 pusat data.
• ID Machine: 5 bit, memberi kita 2 ^ 5 = 32 mesin per pusat data.
• Sequence Number: 12 bit. Untuk setiap ID yang dihasilkan pada mesin/proses tersebut, nomor urutan ditingkatkan sebesar 1. Nomor ini diatur ulang menjadi 0 setiap millisecond.

Untuk aplikasi yang akan dibangun, kita akan gunakan package snowflake (https://github.com/bwmarrin/snowflake)