Rate Limiting?

Apa Itu Rate Limiting?

Secara sederhana, Rate Limiting adalah sebuah mekanisme kontrol untuk membatasi seberapa sering seseorang (atau sebuah layanan) dapat melakukan suatu tindakan dalam periode waktu tertentu.

Tujuannya adalah untuk:

• Stabilitas: Mencegah satu pengguna membebani server dan membuatnya down (misalnya, serangan DDoS).

• Keamanan: Mencegah serangan brute force (misal, mencoba-coba password ribuan kali).

• Keadilan (Fairness): Memastikan semua pengguna mendapatkan "jatah" sumber daya yang adil.

• Biaya: Mengontrol biaya penggunaan API pihak ketiga.

Berikut adalah evolusi algoritma rate limiter, dari yang paling dasar hingga yang paling ideal.

---

1. Fixed Window Counter (Penghitung Jendela Tetap)

Ini adalah algoritma rate limiter yang paling sederhana dan paling dasar.

Penjelasan

Algoritma ini membagi waktu menjadi "jendela" (Windows) dengan durasi tetap (misal, 1 menit). Setiap jendela memiliki counter (penghitung) yang akan bertambah setiap kali ada request masuk.

Jika counter dalam jendela tersebut telah mencapai batas limit, semua request berikutnya dalam jendela itu akan ditolak. Ketika jendela waktu baru dimulai, counter akan di-reset kembali ke nol.

Ilustrasi / Analogi

Bayangkan sebuah loket bioskop yang memiliki aturan: "Hanya menjual 100 tiket per jam."

• Dari jam 10:00:00 hingga 10:59:59, loket akan menghitung tiket yang terjual.

• Jika 100 tiket sudah terjual pada jam 10:45:00, loket akan tutup.

• Siapa pun yang datang antara 10:45:01 dan 10:59:59 akan ditolak.

• Tepat pada jam 11:00:00, counter di-reset ke 0, dan loket mulai menjual 100 tiket lagi.

Flow Algoritma

1. Sebuah request masuk dari pengguna (misal, IP 1.2.3.4).

2. Tentukan window waktu saat ini (misal, 10:01:00).

3. Ambil counter untuk 1.2.3.4 pada window 10:01:00.

4. Jika counter < limit (misal, 100):

   • Naikkan counter (misal, counter++).

   • Izinkan request.

5. Jika counter >= limit:

   • Tolak request.

6. Saat waktu memasuki window baru (misal, 10:02:00), counter untuk 10:01:00 dibuang atau di-reset.

Kelebihan

• Sangat Sederhana: Mudah diimplementasikan dan dipahami.

• Hemat Memori: Hanya perlu menyimpan satu counter untuk setiap pengguna per window.

Kekurangan & Problem

• Problem Utama: Lonjakan di Tepi Jendela (Edge Burst): Ini adalah kelemahan fatalnya.

  • Misal, limit 100 request/menit.

  • Pengguna A mengirim 100 request pada jam 10:01:59. (Diizinkan)

  • Pada jam 10:02:00, counter di-reset.

  • Pengguna A mengirim lagi 100 request pada jam 10:02:01. (Diizinkan)

  • Hasilnya: Server menerima 200 request hanya dalam 2 detik! Ini jelas melanggar tujuan rate limiting dan bisa membuat server down.

---

2. Sliding Log (Log Geser)

Algoritma ini memperbaiki masalah burst pada Fixed Window dengan cara yang lebih presisi.

Penjelasan

Alih-alih menghitung jumlah, algoritma ini menyimpan catatan waktu (timestamp) dari setiap request pengguna dalam sebuah log atau list.

Saat request baru masuk, sistem akan:

1. Menghapus semua timestamp yang lebih tua dari durasi limit (misal, lebih tua dari 1 menit yang lalu).

2. Menghitung jumlah timestamp yang tersisa.

3. Jika jumlahnya kurang dari limit, request diizinkan dan timestamp baru ditambahkan ke log.

Ilustrasi / Analogi

Bayangkan sebuah satpam yang menjaga pintu dengan aturan: "Hanya 5 orang boleh masuk dalam 60 detik terakhir."

• Satpam memegang papan tulis yang mencatat waktu persis setiap orang masuk (misal: 10:01:15, 10:01:30, 10:01:45, ...).

• Saat Anda datang jam 10:02:00:

  1. Satpam menghapus semua catatan waktu sebelum 10:01:00 (karena sudah > 60 detik lalu).

  2. Dia menghitung sisa catatan di papan.

  3. Jika sisa catatan ada 4, Anda diizinkan masuk, dan satpam mencatat waktu Anda: 10:02:00.

  4. Jika sisa catatan sudah ada 5, Anda ditolak.

Flow Algoritma

1. Sebuah request masuk dari pengguna (IP 1.2.3.4).

2. Ambil log (list timestamp) untuk 1.2.3.4.

3. Tentukan batas waktu (misal, WaktuSekarang - 60 detik).

4. Hapus semua timestamp dari log yang lebih tua dari batas waktu tersebut.

5. Hitung jumlah timestamp yang tersisa (count).

6. Jika count < limit:

   • Tambahkan timestamp baru (WaktuSekarang) ke log.

   • Izinkan request.

7. Jika count >= limit:

   • Tolak request.

Kelebihan

• Sangat Akurat: Ini adalah implementasi rate limiting yang paling presisi. Tidak ada masalah edge burst sama sekali.

Kekurangan & Problem

• Sangat Boros Memori: Harus menyimpan timestamp untuk setiap request. Jika limit adalah 10.000 request/jam, Anda harus menyimpan 10.000 timestamp per pengguna.

• Mahal Secara Komputasi: Setiap request memicu operasi baca, filter/hapus, dan tulis pada sebuah list. Ini bisa menjadi lambat, terutama pada sistem terdistribusi (butuh locking yang mahal).

---

3. Sliding Window Counter (Penghitung Jendela Geser)

Ini adalah algoritma hybrid yang mencoba mendapatkan efisiensi memori dari Fixed Window dan akurasi dari Sliding Log. Ini adalah salah satu yang paling populer di dunia nyata.

Penjelasan

Algoritma ini adalah kompromi cerdas. Kita tetap menggunakan counter (seperti Fixed Window), tapi kita "menghaluskan" perhitungannya dengan melihat window sebelumnya.

Caranya adalah dengan memperkirakan jumlah request di "jendela geser" dengan menggunakan data dari dua window tetap (window saat ini dan window sebelumnya).

Rumus Perkiraan:

Rate = (Counter_Window_Sebelumnya * Persentase_Window_Sebelumnya_yg_Tersisa) + Counter_Window_Saat_Ini

💡 Ilustrasi / Analogi

Kembali ke loket 100 tiket/jam.

• Data yang disimpan:

  • Jam 09:00 - 09:59: Terjual 80 tiket.

  • Jam 10:00 - 10:59: Terjual 40 tiket (sejauh ini).

• Sebuah request datang pada jam 10:15:00.

• Window jam 10:00 baru berjalan 25% (15 dari 60 menit). Window jam 09:00 masih "relevan" 75% sisanya.

• Satpam menghitung:

  • Dari jam 09:00: (80 tiket * 75% relevan) = 60

  • Dari jam 10:00: (40 tiket) = 40

  • Total perkiraan = 60 + 40 = 100

• Karena sudah 100, request baru ditolak. Ini jauh lebih akurat daripada Fixed Window.

Flow Algoritma

1. Sebuah request masuk.

2. Ambil counter untuk window saat ini (C_current) dan window sebelumnya (C_previous).

3. Hitung persentase window saat ini yang telah berlalu (misal, 15 detik dari 60 detik = 25% atau 0.25).

4. Hitung persentase tumpang tindih dari window sebelumnya (percentage_previous = 1 - 0.25 = 0.75).

5. Hitung estimasi count = (C_previous * percentage_previous) + C_current.

6. Jika count < limit:

   • Naikkan C_current (increment C_current++).

   • Izinkan request.

7. Jika count >= limit:

   • Tolak request.

Kelebihan

• Keseimbangan Terbaik: Memberikan akurasi yang sangat baik (hampir se-akurat Sliding Log) dengan penggunaan memori yang sangat efisien (hanya 2 counter per pengguna).

• Performa Tinggi: Tidak ada pemrosesan list yang berat, hanya matematika sederhana.

Kekurangan & Problem

• Tetap Estimasi: Ini bukan 100% akurat. Masih ada kemungkinan burst kecil di edge case tertentu, tapi jauh lebih baik daripada Fixed Window.

• Sedikit lebih rumit untuk diimplementasikan daripada Fixed Window.

---

Token Bucket (Ember Token)

Algoritma ini sangat populer dan berfokus pada fleksibilitas, terutama dalam mengizinkan burst (lonjakan).

Penjelasan

Bayangkan sebuah ember (bucket) dengan kapasitas tetap. Ember ini secara konstan diisi ulang dengan "token" pada kecepatan yang tetap (misal, 10 token per detik).

• Setiap request yang masuk harus "membayar" 1 token dari ember.

• Jika ember penuh, token baru yang datang akan dibuang (tidak meluap).

• Jika request datang dan ember kosong, request ditolak.

Kuncinya: Algoritma ini mengizinkan lonjakan request. Jika ember memiliki kapasitas 100 token dan sedang penuh, pengguna bisa langsung mengirim 100 request sekaligus (menghabiskan semua token). Setelah itu, mereka harus menunggu ember diisi ulang (10 request/detik).

Ilustrasi / Analogi

Ini adalah analogi klasiknya:

• Anda punya ember (kapasitas 100 token).

• Ada keran yang meneteskan 10 token/detik ke ember.

• Setiap request yang mau lewat harus mengambil 1 token.

• Jika Anda tidak mengirim request selama 10 detik, ember akan terisi penuh (100 token).

• Anda kemudian bisa mengirim 100 request secara instan.

• Setelah itu, ember Anda kosong. Anda harus menunggu 1 detik untuk bisa mengirim 10 request lagi (atau 0.1 detik untuk 1 request).

⚙Flow Algoritma

1. Setiap pengguna punya bucket dengan: capacity, refill_rate, current_tokens, dan last_refill_timestamp.

2. Saat request masuk:

3. Hitung berapa lama sejak refill terakhir: duration = now - last_refill_timestamp.

4. Hitung token baru yang harus ditambahkan: new_tokens = duration * refill_rate.

5. Update token di ember: current_tokens = min(capacity, current_tokens + new_tokens).

6. Update last_refill_timestamp = now.

7. Jika current_tokens >= 1:

   • Kurangi token: current_tokens = current_tokens - 1.

   • Izinkan request.

8. Jika current_tokens < 1:

   • Tolak request.

Kelebihan

• Mengizinkan Burst: Sangat baik untuk traffic yang tidak merata. Memberi toleransi pada lonjakan sesaat selama rata-rata jangka panjangnya tetap terjaga.

• Sangat fleksibel (bisa mengatur kapasitas burst dan rate jangka panjang).

• Mudah dipahami.

Kekurangan & Problem

• Dua Parameter: Membutuhkan penyesuaian 2 parameter (bucket size dan refill rate) yang bisa jadi rumit untuk diseimbangkan.

• Membutuhkan lebih banyak state (data) untuk disimpan per pengguna dibandingkan Sliding Window Counter.

---

5. Leaky Bucket (Ember Bocor)

Algoritma ini adalah kebalikan dari Token Bucket. Fokusnya bukan mengizinkan burst, tapi menghaluskan burst.

Penjelasan

Bayangkan sebuah ember yang memiliki lubang kecil di bagian bawahnya. Air (request) keluar dari lubang itu dengan kecepatan yang konstan (misal, 10 tetes/detik).

• Request yang masuk adalah air yang dituangkan ke dalam ember.

• Sebuah processor akan mengambil request dari ember pada rate yang tetap (lubang bocor).

• Jika request datang terlalu cepat (air dituang lebih cepat daripada lubang bocor), ember akan penuh.

• Jika ember sudah penuh, request baru (air baru) akan tumpah (ditolak).

Intinya, algoritma ini menggunakan Antrian (Queue). Request dimasukkan ke antrian, dan diproses satu per satu pada rate yang stabil.

Ilustrasi / Analogi

Seperti namanya.

• Air (request) masuk ke ember dari atas.

• Ember mengeluarkan air (processing) dari bawah dengan rate 10 tetes/detik, tidak peduli seberapa deras air di atas.

• Jika air dituang terlalu deras (burst), permukaan air di ember akan naik (antrian memanjang).

• Jika ember penuh (antrian penuh), air yang baru dituang akan ditolak.

Flow Algoritma

1. Gunakan antrian (Queue) FIFO (First-In, First-Out) dengan kapasitas tetap (misal, 100).

2. Sebuah worker (proses terpisah) mengambil item dari antrian pada rate tetap (misal, 10 request/detik).

3. Saat request masuk:

4. Periksa jumlah item di antrian (queue_size).

5. Jika queue_size < capacity:

   • Masukkan request ke dalam antrian (Enqueue).

   • Request akan diproses oleh worker nanti.

6. Jika queue_size >= capacity:

   • Tolak request (antrian penuh).

Kelebihan

• Menjamin Rate Pemrosesan yang Stabil: Sangat baik untuk melindungi layanan backend (misal, database) yang tidak boleh menerima lonjakan traffic. Traffic "dihaluskan" (smoothed out).

• Sangat terprediksi.

Kekurangan & Problem

• Tidak Mengizinkan Burst: Request yang datang dalam lonjakan akan mengalami latensi (karena harus mengantri) atau langsung ditolak. Ini tidak ideal jika burst sesaat sebenarnya bisa ditangani.

• Request yang lama di antrian bisa jadi timeout sebelum sempat diproses.

• Implementasinya lebih kompleks karena membutuhkan queue dan worker yang berjalan terpisah.

---

Tabel Perbandingan

Algoritma	Akurasi	Efisiensi Memori	Mengizinkan Burst?	Kompleksitas	Kasus Penggunaan Ideal
Fixed Window	Rendah	Sangat Tinggi	Tidak (dan menyebabkan burst di tepi)	Sangat Rendah	Analitik sederhana, rate limiting yang tidak kritis.
Sliding Log	Sempurna	Sangat Rendah	Ya (secara alami)	Tinggi	Saat akurasi 100% adalah harga mati (jarang).
Sliding Window	Tinggi	Tinggi	Tidak (menghaluskan burst di tepi)	Sedang	Rate limiting API publik standar. (Contoh: Nginx, Redis)
Token Bucket	Tinggi	Sedang	Ya (Sengaja)	Sedang	Saat Anda ingin mengizinkan lonjakan (misal, upload file). (Contoh: AWS)
Leaky Bucket	Tinggi	Sedang	Tidak (Menghaluskan)	Tinggi	Melindungi worker atau database dari lonjakan input.

Mana yang Paling Sempurna?

Tidak ada satu algoritma yang "paling sempurna" untuk semua kasus.

• Untuk Rate Limiting API secara umum, Sliding Window Counter sering dianggap sebagai pilihan terbaik karena memberikan keseimbangan yang nyaris sempurna antara akurasi, performa, dan efisiensi memori.

• Jika Anda ingin mengizinkan burst (karena traffic pengguna memang naik-turun), Token Bucket adalah pilihan yang lebih baik.