Desain Pemendek URL

Dalam bab ini, kita akan membahas pertanyaan wawancara desain sistem yang menarik dan klasik: merancang layanan pemendekan URL seperti tinyurl.

Langkah 1 - Pahami masalah dan tetapkan cakupan desain

Pertanyaan wawancara desain sistem sengaja dibiarkan terbuka. Untuk merancang sistem yang dirancang dengan baik, penting untuk mengajukan pertanyaan klarifikasi.

Wawancara

Kandidat

Pewawancara

Bisakah Anda memberikan contoh cara kerja pemendek URL?

Asumsikan URL https://www.systeminterview.com/q=chatsystem&c=loggedin&v=v3&l=long adalah URL asli. Layanan Anda membuat alias dengan panjang yang lebih pendek: https://tinyurl.com/y7keocwj. Jika Anda mengklik alias tersebut, Anda akan dialihkan ke URL asli.

Berapa volume lalu lintasnya?

100 juta URL dihasilkan per hari.

Berapa panjang URL yang dipersingkat?

Sesingkat mungkin.

Karakter apa saja yang diperbolehkan dalam URL yang dipersingkat?

URL yang dipersingkat dapat berupa kombinasi angka (0-9) dan karakter (a-z, A-Z).

Bisakah URL yang dipersingkat dihapus atau diperbarui?

Untuk menyederhanakannya, mari kita asumsikan URL yang dipersingkat tidak dapat dihapus atau diperbarui.

Berikut adalah beberapa contoh penggunaan dasar:

  1. Pemendekan URL: jika URL panjang => menghasilkan URL yang jauh lebih pendek

  2. Pengalihan URL: jika URL lebih pendek => mengalihkan ke URL asli

  3. Pertimbangan ketersediaan tinggi, skalabilitas, dan toleransi kesalahan

Estimasi perkiraan

  • Operasi tulis: 100 juta URL dihasilkan per hari.

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

  • Operasi baca: Dengan asumsi rasio operasi baca terhadap operasi tulis adalah 10:1, operasi baca per detik: 1160 x 10 = 11.600

  • Dengan asumsi layanan pemendek URL akan berjalan selama 10 tahun, ini berarti kita harus mendukung 100 juta x 365 x 10 = 365 miliar data.

  • Asumsikan panjang URL rata-rata adalah 100.

  • Kebutuhan penyimpanan selama 10 tahun: 365 miliar x 100 byte = 36,5 TB

Penting bagi Anda untuk membahas asumsi dan perhitungan dengan pewawancara agar Anda berdua memiliki pemahaman yang sama.

Langkah 2 - Usulkan desain tingkat tinggi dan dapatkan persetujuan

Di bagian ini, kami membahas titik akhir API, pengalihan URL, dan alur pemendekan URL.

API Endpoints

API endpoints memfasilitasi komunikasi antara klien dan server. Kami akan merancang API dengan gaya REST. Jika Anda belum terbiasa dengan API restful, Anda dapat merujuk ke materi eksternal, seperti yang ada di materi referensi [1]. Sebuah pemendek URL membutuhkan dua titik akhir API.

  • URL shortening Pemendekan URL. Untuk membuat URL pendek baru, klien mengirimkan permintaan POST, yang berisi satu parameter: URL panjang asli. API-nya terlihat seperti ini:
    POST api/v1/data/shorten

- request parameter: {longUrl: longURLString}
- return: shortURL
  • URL redirectiong Pengalihan URL. Untuk mengalihkan URL pendek ke URL panjang yang sesuai, klien mengirimkan permintaan GET. API-nya terlihat seperti ini:
    GET api/v1/shortUrl

- return: longURL for HTTP redirection

URL Redirecting

Gambar 1 menunjukkan apa yang terjadi ketika Anda memasukkan tinyurl ke peramban. Setelah server menerima permintaan tinyurl, URL pendek akan diubah menjadi URL panjang dengan pengalihan 301.

../_images/figure-8-1-GSSWK66W.svg

Komunikasi terperinci antara klien dan server ditunjukkan pada Gambar 2.

../_images/figure-8-2-KMMJ65HT.webp

Satu hal yang perlu dibahas di sini adalah pengalihan 301 vs. pengalihan 302.

301 redirect. Pengalihan 301 menunjukkan bahwa URL yang diminta dipindahkan "secara permanen" ke URL yang panjang. Karena dialihkan secara permanen, browser menyimpan respons tersebut dalam cache, dan permintaan selanjutnya untuk URL yang sama tidak akan dikirim ke layanan pemendek URL. Sebaliknya, permintaan dialihkan langsung ke server URL yang panjang.

302 redirect. Pengalihan 302 berarti URL dipindahkan "sementara" ke URL yang panjang, artinya permintaan selanjutnya untuk URL yang sama akan dikirim ke layanan pemendek URL terlebih dahulu. Kemudian, permintaan tersebut dialihkan ke server URL yang panjang.

Setiap metode pengalihan memiliki kelebihan dan kekurangannya masing-masing. Jika prioritasnya adalah mengurangi beban server, penggunaan pengalihan 301 masuk akal karena hanya permintaan pertama dari URL yang sama yang dikirim ke server pemendek URL. Namun, jika analitik penting, pengalihan 302 adalah pilihan yang lebih baik karena dapat melacak rasio 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 perintah berikut:

  • Dapatkan longURL: longURL = hashTable.get(shortURL)

  • Setelah Anda mendapatkan longURL, lakukan pengalihan URL.

URL shortening

Mari 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 ke hashValue, seperti yang ditunjukkan pada Gambar 3.

../_images/figure-8-3-YHOCRGSP.svg

Gambar merepresentasikan sistem pemendekan URL yang disederhanakan. Kotak persegi panjang berlabel 'longURL' yang berisi teks 'longURL' merepresentasikan URL asli yang panjang. Sebuah panah menunjuk dari kotak ini ke kotak persegi panjang kedua yang berisi simbol fungsi matematika 'ƒ(x)', yang merepresentasikan fungsi hash. Fungsi ini menerima 'longURL' sebagai input. Di bawah kotak 'ƒ(x)', sebuah panah yang mengarah ke bawah berlabel 'hash' menghubungkannya ke kotak persegi panjang ketiga, yang menampilkan URL yang dipersingkat: 'https://tinyurl.com/qtj5opu'. Teks 'Viewer does not support full SVG' terdapat di bawah kotak URL yang dipersingkat, yang menunjukkan keterbatasan tampilan gambar, bukan keterbatasan sistem itu sendiri. Diagram keseluruhan mengilustrasikan proses memasukkan URL panjang, menerapkan fungsi hash (ƒ(x)) untuk menghasilkan hash pendek, lalu menggunakan hash tersebut untuk membuat URL yang lebih pendek dan mudah diakses.

Fungsi hash harus memenuhi persyaratan berikut:

  • Setiap longURL harus di-hash ke satu hashValue.

  • Setiap hashValue dapat dipetakan kembali ke longURL.

Desain detail fungsi hash dibahas secara mendalam.

Langkah 3 - Pendalaman Desain

Sejauh ini, kita telah membahas desain tingkat tinggi pemendekan URL dan pengalihan URL. Di bagian ini, kita akan membahas secara mendalam hal-hal berikut: model data, fungsi hash, pemendekan URL, dan pengalihan URL.

Model Data

Dalam desain tingkat tinggi, semuanya disimpan dalam tabel hash. Ini merupakan titik awal yang baik; namun, pendekatan ini tidak layak untuk sistem dunia nyata karena sumber daya memori terbatas dan mahal. Pilihan yang lebih baik adalah menyimpan pemetaan <shortURL, longURL> dalam basis data relasional. Gambar 4 menunjukkan desain tabel basis data sederhana. Versi tabel yang disederhanakan berisi 3 kolom: id, shortURL, longURL.

../_images/figure-8-4-3R6D55TD.svg

Fungsi hash

Fungsi hash digunakan untuk melakukan hash dari URL panjang ke URL pendek, juga dikenal sebagai hashValue.

Panjang nilai hash

HashValue terdiri dari karakter dari [0-9, a-z, A-Z], yang berisi 10 + 26 + 26 = 62 karakter yang mungkin. Untuk mengetahui panjang hashValue, cari n terkecil sehingga 62^n ≥ 365 miliar. Sistem harus mendukung hingga 365 miliar URL berdasarkan estimasi batas bawah. Tabel 1 menunjukkan panjang hashValue dan jumlah maksimal URL yang dapat didukungnya.

n

Maximal number of URLs

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 trillion

8

62^8 = 218,340,105,584,896

Ketika n = 7, 62 ^ n = ~3,5 triliun, 3,5 triliun lebih dari cukup untuk menampung 365 miliar URL, sehingga panjang hashValue adalah 7.

Kita akan membahas dua jenis fungsi hash untuk pemendek URL. Yang pertama adalah "hash + resolusi tabrakan", dan yang kedua adalah "konversi basis 62". Mari kita bahas satu per satu.

Hash + resolusi tabrakan

Untuk mempersingkat URL yang panjang, kita perlu menerapkan fungsi hash yang meng-hash URL panjang menjadi string 7 karakter. Solusi sederhananya adalah menggunakan fungsi hash yang umum digunakan seperti CRC32, MD5, atau SHA-1. Tabel berikut membandingkan hasil hash setelah menerapkan berbagai fungsi hash pada URL ini: https://en.wikipedia.org/wiki/Systems_design

Hash function

Hash value (Hexadecimal)

CRC32

5cb54054

MD5.

5a62509a84df9ee03fe1230b9df8b84e

SHA-1.

0eeae7916c06853901d9ccbefbfcaf4de57ed85b

Seperti yang ditunjukkan pada Tabel 2, bahkan nilai hash terpendek (dari CRC32) pun terlalu panjang (lebih dari 7 karakter). Bagaimana kita bisa membuatnya lebih pendek?

Pendekatan pertama adalah mengumpulkan 7 karakter pertama dari sebuah nilai hash; namun, metode ini dapat menyebabkan tabrakan hash. Untuk mengatasi tabrakan hash, kita dapat menambahkan string baru yang telah ditentukan sebelumnya secara rekursif hingga tidak ada lagi tabrakan yang ditemukan. Proses ini dijelaskan pada Gambar 5.

../_images/figure-8-5-KWG6EFZC.svg

Metode ini dapat menghilangkan tabrakan; namun, membutuhkan biaya yang mahal untuk melakukan kueri pada basis data guna memeriksa keberadaan shortURL untuk setiap permintaan. Sebuah teknik yang disebut filter bloom [2] dapat meningkatkan kinerja. Filter bloom adalah teknik probabilistik yang efisien ruang untuk menguji apakah suatu elemen merupakan anggota suatu himpunan. Lihat materi referensi [2] untuk detail lebih lanjut.

Konversi basis 62

Konversi basis adalah pendekatan lain yang umum digunakan untuk pemendek URL. Konversi basis membantu mengonversi angka yang sama di antara sistem representasi angka yang berbeda. Konversi basis 62 digunakan karena terdapat 62 kemungkinan karakter untuk hashValue. Mari kita gunakan contoh untuk menjelaskan cara kerja konversi: konversi 1115710 ke representasi basis 62 (1115710 mewakili 11157 dalam sistem basis 10).

  • Dari namanya, basis 62 adalah cara menggunakan 62 karakter untuk pengkodean. Pemetaannya adalah: 0-0, ..., 9-9, 10-a, 11-b, ..., 35-z, 36-A, ..., 61-Z, di mana 'a' mewakili 10, 'Z' mewakili 61, dst.

  • 11157 (10) = 2 x 622 + 55 x 621 + 59 x 620 = [2, 55, 59] -> [2, T, X] dalam representasi basis 62. Gambar 6 menunjukkan proses percakapan.
    ../_images/figure-8-6-OHTOBFS7.svg

  • Jadi, URL pendeknya adalah https://tinyurl.com/2TX

Perbandingan kedua pendekatan

Tabel 3 menunjukkan perbedaan kedua pendekatan tersebut.

Hash + collision resolution

Base 62 conversion

Fixed short URL length.

Short URL length is not fixed. It goes up with the ID.

Does not need a unique ID generator.

This option depends on a unique ID generator.

Collision is possible and needs to be resolved.

Collision is not possible because ID is unique.

It’s not possible to figure out the next available short URL because it doesn’t depend on ID.

It is easy to figure out what is the next available short URL if ID increments by 1 for a new entry. This can be a security concern.

URL shortening deep dive

Sebagai salah satu bagian inti sistem, kami ingin alur pemendekan URL menjadi sederhana dan fungsional secara logis. Konversi basis 62 digunakan dalam desain kami. Kami membuat diagram berikut (Gambar 7) untuk mendemonstrasikan alurnya.

../_images/figure-8-7-A3ZKM2XP.svg

  1. longURL adalah inputnya.

  2. Sistem memeriksa apakah longURL ada di dalam basis data.

  3. Jika ya, berarti longURL telah dikonversi menjadi shortURL sebelumnya. Dalam hal ini, ambil shortURL dari basis data dan kembalikan ke klien.

  4. Jika tidak, longURL tersebut baru. ID unik baru (kunci utama) dihasilkan oleh generator ID unik.

  5. Konversikan ID ke shortURL dengan konversi basis 62.

  6. Buat baris basis data baru dengan ID, shortURL, dan longURL.

Untuk memudahkan pemahaman alur, mari kita lihat contoh konkret.

  • Dengan asumsi longURL input adalah: https://en.wikipedia.org/wiki/Systems_design

  • Generator ID unik mengembalikan ID: 2009215674938.

  • Konversikan ID ke shortURL menggunakan konversi basis 62. ID (2009215674938) dikonversi menjadi "zn9edcu".

  • Simpan ID, shortURL, dan longURL ke dalam basis data seperti yang ditunjukkan pada Tabel 4.

id

shortURL

longURL

2009215674938

zn9edcu

https://en.wikipedia.org/wiki/Systems_design

Generator ID unik terdistribusi patut disebutkan. Fungsi utamanya adalah menghasilkan ID unik global, yang digunakan untuk membuat shortURL. Dalam lingkungan yang sangat terdistribusi, mengimplementasikan generator ID unik cukup menantang. Untungnya, kami telah membahas beberapa solusi dalam bab "Merancang Generator ID Unik dalam Sistem Terdistribusi". Anda dapat merujuk kembali untuk menyegarkan ingatan Anda.

URL redirecting deep dive

Gambar 8 menunjukkan desain detail pengalihan URL. Karena lebih banyak pembacaan daripada penulisan, pemetaan <shortURL, longURL> disimpan dalam cache untuk meningkatkan kinerja.

../_images/figure-8-8-VBPJ6PXY.webp

Alur pengalihan URL diringkas sebagai berikut: 1. Pengguna mengklik tautan URL pendek: https://tinyurl.com/zn9edcu 2. Penyeimbang beban meneruskan permintaan ke server web. 3. Jika URL pendek sudah ada di cache, kembalikan URL panjang secara langsung. 4. Jika URL pendek tidak ada di cache, ambil URL panjang dari basis data. Jika tidak ada di basis data, kemungkinan pengguna memasukkan URL pendek yang tidak valid. 5. URL panjang dikembalikan ke pengguna.

Langkah 4 - Penutup

Dalam bab ini, kita membahas desain API, model data, fungsi hash, pemendekan URL, dan pengalihan URL.

Jika ada waktu luang di akhir wawancara, berikut beberapa poin pembahasan tambahan.

Pembatas laju: Masalah keamanan potensial yang mungkin kita hadapi adalah pengguna jahat mengirimkan permintaan pemendekan URL dalam jumlah yang sangat besar. Pembatas laju membantu memfilter permintaan berdasarkan alamat IP atau aturan pemfilteran lainnya. Jika Anda ingin menyegarkan ingatan Anda tentang pembatasan laju, lihat bab "Merancang Pembatas Laju".

Penskalaan Server Web: Karena tingkat web bersifat stateless, mudah untuk menskalakan tingkat web dengan menambahkan atau menghapus server web.

Penskalaan Basis Data: Replikasi dan sharding basis data adalah teknik umum.

Analisis: Data semakin penting untuk kesuksesan bisnis. Mengintegrasikan solusi analitik ke pemendek URL dapat membantu menjawab pertanyaan penting seperti berapa banyak orang yang mengklik tautan? Kapan mereka mengklik tautan tersebut? dll.

Ketersediaan, konsistensi, dan keandalan. Konsep-konsep ini merupakan inti dari kesuksesan sistem besar mana pun. Kami telah membahasnya secara detail di bab "Skala Dari Nol Hingga Jutaan Pengguna", mohon segarkan ingatan Anda tentang topik-topik ini.

Selamat telah mencapai sejauh ini! Sekarang, beri tepuk tangan untuk diri Anda sendiri. Kerja bagus!

Referensi

[1] A RESTful Tutorial: https://www.restapitutorial.com/index.html

[2] Bloom filter: https://en.wikipedia.org/wiki/Bloom_filter