Algoritma rate limiting: token bucket, sliding window
Empat cara menghitung "terlalu banyak", apa kelemahan masing-masing, dan apa yang harus dikirim ke client saat request ditolak
Sebelumnya, di lesson 0020, Anda memilih gaya API. Begitu API terbuka, satu client (bug di loop, scraper, pelanggan besar) bisa menghabiskan kapasitas yang seharusnya dibagi. Lesson ini mengajarkan algoritmanya. Di mana limiter dipasang dan bagaimana counter dibagi ke banyak server dibahas di studi kasus lesson 0029.
Retry-After sebagai jawaban ke client.
1. Token bucket: burst boleh, rata-rata dijaga
Bayangkan ember berisi token. Token ditambahkan dengan laju tetap (refill rate, misalnya 2 per detik) sampai ember penuh (kapasitas, misalnya 10). Setiap request mengambil satu token. Kalau ember kosong, request ditolak. AWS API Gateway memakai algoritma ini: throttling rate adalah laju token ditambahkan ke bucket, dan throttling burst adalah kapasitas bucket. [1]
Contoh: bucket penuh berisi 10 token, lalu 15 request datang bersamaan. Sepuluh lolos, lima ditolak, lalu request berikutnya hanya lolos 2 per detik. Inilah alasan token bucket populer: aplikasi yang wajar sesekali mengirim burst, dan itu tidak dihukum.
2. Leaky bucket: keluaran diratakan
Leaky bucket membalik sudut pandang: request masuk ke antrean, dan antrean dikuras dengan laju tetap. Yang keluar ke backend selalu rata.
Modul limit_req di nginx bekerja seperti ini; dokumentasinya menyebut metode "leaky bucket". Request yang melebihi laju ditunda, dan baru ditolak dengan error kalau jumlahnya melewati burst, yang default-nya nol. [2]
Cocok untuk melindungi backend yang hanya sanggup laju tertentu. Kekurangannya, burst yang sah ikut tertunda.
3. Fixed window dan sliding window: menghitung per jendela waktu
Fixed window counter adalah yang paling sederhana: satu counter per user per jendela (misalnya per detik atau per menit), dinaikkan setiap request, dan kedaluwarsa sendiri. Dokumentasi Redis memberi pola ini untuk INCR: key = IP + timestamp, INCR lalu EXPIRE, tolak kalau counter melewati 10 per detik. [3]
Kelemahannya ada di batas jendela. Dengan limit 100 per menit, client bisa mengirim 100 request di detik ke-59 dan 100 lagi di detik ke-61. Keduanya jatuh di jendela berbeda, jadi 200 request lolos dalam ±2 detik.
Sliding window menutup celah itu. Versi log menyimpan timestamp setiap request dan menghitung yang masih di dalam 60 detik terakhir; akurat, tapi memorinya sebanding dengan jumlah request. Versi counter lebih hemat: ia menimbang counter jendela sebelumnya dengan porsi waktu yang masih tumpang tindih.
| Algoritma | Memori per user | Burst | Kelemahan |
|---|---|---|---|
| Token bucket | 2 angka (token, waktu refill terakhir) | Boleh sampai kapasitas | Dua parameter perlu disetel |
| Leaky bucket | Antrean | Ditunda, lalu ditolak | Burst sah ikut terlambat |
| Fixed window | 1 counter | Bisa 2× limit di batas jendela | Tidak akurat di batas |
| Sliding window counter | 2 counter | Hampir akurat | Estimasi, bukan hitungan pasti |
Latihan 1 — Algoritma
Jawab tanpa scroll ke atas. Soal yang sama akan muncul lagi, diacak, di review 0026.
Kuis di lesson ini adalah feedback cepat, bukan bukti penguasaan; yang dicatat hanya hasil review 0026.
4. Apa yang dikirim ke client: 429 dan Retry-After
RFC 6585 mendefinisikan 429 Too Many Requests: user mengirim terlalu banyak request dalam rentang waktu tertentu ("rate limiting"). Response sebaiknya menjelaskan kondisinya dan boleh menyertakan header Retry-After yang menyatakan berapa lama menunggu. [4]
Nilai Retry-After berupa tanggal HTTP atau jumlah detik, misalnya Retry-After: 30. [5]
HTTP/1.1 429 Too Many Requests
Retry-After: 30
Content-Type: application/json
{"error": "rate_limited", "limit": "100 per menit"}Perhatikan: limit_req di nginx secara default membalas 503, bukan 429; ubah dengan limit_req_status 429;. [2] Client yang baik menunggu sesuai Retry-After, lalu memakai backoff (lesson 0022).
Latihan 2 — Response saat ditolak
5. Kapan tidak perlu
Sinyal yang membenarkan rate limiter: API terbuka untuk pihak luar, ada satu client yang memakai porsi kapasitas jauh di atas yang lain (misalnya satu API key = 40% traffic), ada endpoint yang mahal per request (login, pencarian, panggilan ke API berbayar), atau ada insiden overload yang disebabkan satu sumber. Tool internal untuk 50 karyawan tidak butuh rate limiter sendiri.
Biaya dan risiko: limit yang salah setel menolak user sah, dan itu terlihat sebagai outage. Limiter yang counter-nya disimpan di luar proses (misalnya Redis) menambah latency di setiap request dan menjadi dependency baru: kalau Redis mati, Anda harus memilih fail open (semua lolos) atau fail closed (semua ditolak).
Alternatif lebih murah: pakai fitur yang sudah ada di jalur request, yaitu limit_req di nginx atau throttling di API gateway, sebelum membangun layanan rate limiter sendiri. Counter di memori satu proses cukup kalau hanya ada satu server. Rate limiter terdistribusi baru dibenarkan kalau limit harus konsisten di banyak instance (lesson 0029).
Latihan lisan — Ucapkan dengan suara keras
Pasang timer dan jawab dengan suara keras, seolah sedang interview. Jangan buka jawaban contoh sebelum selesai. Soal ini juga ada di bank soal dan bisa ditarik review 0026.
"API publik kita perlu rate limiting 100 request per menit per API key. Algoritma apa yang Anda pilih, apa trade-off-nya, dan apa yang diterima client saat ditolak?" (60 detik)
Bandingkan dengan jawaban contoh dan checklist-nya
"Saya pilih token bucket: kapasitas, misalnya 20, menentukan burst yang boleh lewat sekaligus, dan refill 100 token per menit menentukan rata-rata. Burst singkat dari aplikasi yang wajar tetap lolos. Alternatifnya fixed window counter: paling sederhana, cukup INCR dan EXPIRE di Redis, tapi di batas window client bisa lolos dua kali limit. Sliding window counter menutup celah itu dengan menimbang window sebelumnya, dengan biaya satu counter tambahan. Leaky bucket meratakan ke laju tetap, cocok untuk melindungi backend yang rapuh, seperti limit_req di nginx. Saat ditolak, server membalas 429 Too Many Requests dengan header Retry-After, dan client menunggu sebanyak itu. Sebagai v1 saya pakai fitur rate limit di gateway atau nginx yang sudah ada; desain layanan terdistribusinya baru dibahas kalau satu node tidak cukup."
Checklist: apakah Anda menyebut…
- token bucket: kapasitas = burst, refill = laju rata-rata?
- fixed window sederhana tapi bisa lolos dua kali limit di batas window?
- sliding window atau leaky bucket sebagai pembanding dengan trade-off-nya?
- 429 Too Many Requests sebagai response saat ditolak?
- header Retry-After memberi tahu client berapa lama menunggu?
- v1 memakai fitur gateway/nginx yang sudah ada sebelum membangun layanan sendiri?
Lulus jika minimal 4 dari 6.
burst dan nodelay, ±10 menit.
Berikutnya, lesson 0022: sisi sebaliknya. Saat service Anda yang memanggil dependency yang lambat atau menolak, kapan menyerah, kapan mengulang, dan kapan berhenti mencoba?
Istilah: GLOSSARY.md (bagian "Reliabilitas & API") · Indeks: semua lesson System Design
Ada yang belum jelas? Tanyakan ke saya (agent) di terminal, misalnya: "Hitung ulang sliding window counter kalau sekarang detik ke-45", "Kenapa nginx memilih 503 sebagai default?"
Sumber: [1] AWS API Gateway: Throttle requests to your REST APIs · [2] nginx: Module ngx_http_limit_req_module · [3] Redis docs: INCR, pattern rate limiter · [4] RFC 6585 Additional HTTP Status Codes, §4 (429) · [5] RFC 9110 HTTP Semantics, §10.2.3 Retry-After