Jawaban singkat untuk pertanyaan yang paling sering diajukan pembaca tentang topik ini.
Algoritma rate limiting mana yang dipakai? Fixed window, sliding window log dan counter, token bucket dan leaky bucket dibandingkan dengan hitungan dan kode TypeScript.
Matthews Wong
Software Engineer
Ringkasan Utama
Pakai token bucket jika client boleh melakukan burst tetapi harus tetap di bawah rata-rata jangka panjang, dan sliding window counter jika butuh batas keras per periode dengan memori kecil. Fixed window bisa meloloskan dua kali lipat limit di batas window, sedangkan leaky bucket menghaluskan traffic, bukan menolaknya.
Limit 100 request per menit terdengar seperti satu aturan, padahal ada setidaknya lima algoritma yang bisa menegakkannya, dan masing-masing berbeda pada kasus yang penting: apa yang terjadi di ujung menit, apakah client yang sepi boleh memakai kapasitas yang tersimpan, dan berapa byte state yang dihabiskan tiap pemanggil.
Tulisan ini membandingkan fixed window, sliding window log, sliding window counter, token bucket dan leaky bucket dengan hitungan tangan, lalu memberi token bucket TypeScript yang bisa dijalankan. Ini pendamping algoritma dari post implementasi NestJS dan Redis saya; di sini tidak ada yang bergantung pada framework. Angka dari pihak lain dicantumkan sumbernya.
Rate limiter menjawab satu pertanyaan per request: izinkan atau tolak. Algoritma menentukan bagaimana jawaban itu dihitung dari traffic sebelumnya. Tiga sifat membedakan pilihan yang ada: seberapa besar burst yang ditoleransi, seberapa akurat limit ditegakkan, dan seberapa besar state yang dibutuhkan tiap key (user, API key atau IP). Semua di bawah ini adalah tawar-menawar antara ketiganya.
Penolakan standarnya adalah HTTP 429 Too Many Requests, didefinisikan di RFC 6585, yang juga membolehkan header Retry-After agar client tahu kapan harus kembali. Pilihan algoritma menentukan angka apa yang bisa Anda isi di header itu dengan jujur. Untuk contoh, saya pakai satu limit: 100 request per 60 detik per API key.
Fixed window menyimpan satu counter per key per window yang selaras dengan jam. Request pertama dalam window membuat counter, tiap request menaikkannya, dan counter kedaluwarsa saat window berakhir. State-nya hanya satu integer dan di Redis cukup INCR plus EXPIRE. Murahnya itulah alasan algoritma ini biasanya dibuat pertama.
# Limit: 100 requests per 60 s, fixed windows aligned to the minute
12:00:00 - 12:00:58 client sends nothing
12:00:59 client sends 100 requests window 12:00 count = 100 -> all allowed
12:01:00 window 12:01 starts, count = 0
12:01:00 - 12:01:01 client sends 100 requests window 12:01 count = 100 -> all allowed
# 200 accepted in about 2 seconds. Allowed rate: 100 per minute.
# A sliding window would have rejected every request in the second batch.Kelemahannya ada di batas window. Counter di-reset di ujung window tanpa peduli apa yang terjadi tepat sebelumnya, sehingga client bisa menghabiskan satu kuota penuh di akhir window dan satu kuota penuh lagi di awal window berikutnya. Timeline di bawah menunjukkan 200 request diterima dalam sekitar dua detik terhadap limit 100 per menit, dua kali laju yang dimaksud.
Kasus terburuk fixed window adalah dua kali limit melintasi batas window. Jika limit melindungi sistem hilir yang benar-benar tumbang di 100 per menit, fixed window akan mengecewakan Anda tepat saat retry storm terjadi.
Sliding window log menyimpan timestamp setiap request yang diterima, membuang yang lebih tua dari 60 detik, lalu menghitung sisanya. Hasilnya akurat: pada setiap saat tidak ada lebih dari 100 request dalam 60 detik terakhir. Harganya memori sebanding dengan limit. Pada 100 request per menit, tiap key yang sibuk menyimpan hingga 100 timestamp, jadi 10.000 key sibuk berarti hingga 1.000.000 entri. Di Redis biasanya berupa sorted set per key.
Sliding window counter hanya menyimpan dua angka, hitungan window sebelumnya dan window sekarang, lalu memberi bobot pada yang sebelumnya sesuai seberapa banyak yang masih tumpang tindih dengan sliding window. Misalkan 84 request di menit lalu dan 36 sejauh ini di menit ini, pada detik ke-15. Tumpang tindih window sebelumnya adalah 45 dari 60 detik, yaitu 75 persen. Estimasinya 84 x 0,75 + 36 = 63 + 36 = 99. Itu di bawah 100, jadi satu request lagi diizinkan.
// Sliding window counter: two integers per key
// now = 15 s into the current minute, limit = 100
const overlap = 1 - 15 / 60; // 0.75 of the previous window still counts
const estimate = prevCount * overlap + currCount;
// = 84 * 0.75 + 36 = 99
if (estimate < 100) {
currCount += 1; // allowed; estimate is now 100
} else {
reject(429); // the next request would exceed the limit
}Pembobotan ini mengasumsikan request window sebelumnya tersebar merata, jadi sifatnya aproksimasi. Cloudflare menerbitkan analisis atas 400 juta request dari 270.000 sumber berbeda dan melaporkan 0,003 persen request salah diizinkan atau salah di-rate limit dengan pendekatan ini. Itu angka untuk traffic mereka, bukan jaminan untuk traffic Anda, tetapi menunjukkan galat aproksimasi kecil dalam praktik. Harganya dua counter per key.
Token bucket menampung hingga capacity token dan menambah token dengan refill rate yang tetap. Tiap request mengambil satu token; jika bucket kosong, request ditolak. Wikipedia menjelaskan struktur yang sama sebagai bucket untuk memeriksa kesesuaian terhadap batas laju dan burstiness, dan Stripe menggambarkan limiter miliknya sebagai satu bucket per user yang tokennya diambil tiap request dan diteteskan kembali pelan-pelan.
Hitungannya adalah daya tarik utamanya. Ambil capacity 10 dan refill 2 token per detik, yaitu 120 per menit berkelanjutan. Client yang datang ke bucket yang penuh boleh mengirim 10 request sekaligus, lalu dibatasi 2 per detik. Jika diam 20 detik, bucket seharusnya berisi 0 + 40 token tetapi dibatasi 10, jadi kapasitas tersimpan dibatasi oleh capacity. Dalam 60 detik apa pun, paling banyak yang bisa dikirim adalah 10 + 120 = 130. Capacity mengatur burst, refill mengatur rata-rata, dan keduanya bisa disetel terpisah.
Tidak perlu timer. Limiter hanya menyimpan jumlah token dan waktu update terakhir, lalu menghitung refill secara lazy dari selisih waktu di tiap request. Itu dua angka per key, sama dengan footprint sliding window counter.
Jangan beri bucket capacity yang sama dengan refill per detik kecuali memang ingin melarang burst. Capacity 1 dengan refill 2 per detik berarti jarak mulus 500 ms, yang akan membuat banyak client nyata terkena penolakan.
Leaky bucket bekerja sebagai antrean yang dikuras dengan laju konstan. Request masuk antrean dan keluar dengan laju tetap; jika antrean penuh, request baru dibuang. Ambil antrean 10 yang dikuras 2 per detik dan burst mendadak 15 request: 10 masuk antrean, 5 ditolak, dan request terakhir yang antre keluar setelah sekitar 10 / 2 = 5 detik. Output-nya mulus sempurna, itulah tujuannya, dan harganya adalah latensi.
Keduanya mudah tertukar karena Wikipedia mencatat bahwa leaky bucket sebagai meter setara dengan token bucket. Beda praktisnya ada pada nasib burst. Token bucket meloloskannya langsung lalu membatasi; antrean leaky bucket menyerap dan menunda. Pakai bentuk antrean jika yang ada di belakang limiter, seperti printer, payment gateway atau endpoint ERP lama, butuh aliran merata, bukan balasan cepat.
Pilih berdasarkan perilaku yang Anda butuhkan di ujung-ujungnya, lalu cek biaya state. Tabel ini meringkas lima algoritma untuk contoh 100 per menit, dengan state dihitung per key.
| Algoritma | State per key | Perilaku burst | Akurasi | Paling cocok untuk |
|---|---|---|---|---|
| Fixed window | 1 counter | Hingga 200 melintasi batas window | Longgar di batas | Proteksi abuse murah saat burst ganda tidak berbahaya |
| Sliding window log | Hingga 100 timestamp | Tidak pernah di atas 100 dalam 60 detik | Eksak | Batas ketat untuk key bervolume rendah tapi bernilai tinggi |
| Sliding window counter | 2 counter | Mendekati 100 dalam 60 detik | Aproksimasi, galat kecil | Kuota keras per periode pada skala besar |
| Token bucket | Token plus waktu update terakhir | Burst hingga capacity, lalu sebesar refill rate | Eksak menurut definisinya sendiri | API publik yang membolehkan burst tetapi membatasi rata-rata |
| Leaky bucket | Panjang antrean plus waktu kuras terakhir | Tidak ada burst keluar; kelebihan diantrekan atau dibuang | Laju output eksak | Melindungi backend yang butuh aliran merata |
Default saya untuk HTTP API di satu server adalah token bucket per API key, karena client nyata itu bursty dan page load yang menembakkan 8 panggilan sekaligus tidak seharusnya dihukum. Saya memilih sliding window counter saat kontraknya memang kuota, misalnya 1.000 panggilan per jam di sebuah paket, dan memakai bentuk leaky bucket hanya di depan sesuatu yang tidak tahan burst.
Algoritma baru setengah keputusan. Gunakan identitas terautentikasi sebagai key lebih dulu, seperti API key atau tenant, dan pakai IP hanya untuk traffic anonim, karena banyak kantor dan jaringan seluler berbagi satu alamat. Lalu jalani checklist ini untuk setiap limit. Versi NestJS dengan Redis dari gagasan ini ada di post saya sebelumnya tentang API rate limiting.
Baca implementasi NestJS dan Redis untuk API rate limiting
TypeScript di bawah adalah token bucket satu proses di balik angka pada bagian empat. Trace di komentarnya memakai capacity 10 dan 2 token per detik. Kode ini tidak aman lintas proses, karena dua instance masing-masing memegang bucket sendiri, dan butuh sweep untuk membuang key yang menganggur atau map akan tumbuh tanpa batas.
interface Bucket {
tokens: number;
updatedAt: number; // ms
}
export class TokenBucketLimiter {
private buckets = new Map<string, Bucket>();
constructor(
private readonly capacity: number, // burst size
private readonly refillPerSec: number, // sustained rate
private readonly now: () => number = () => Date.now(), // injectable for tests
) {}
take(key: string, cost = 1): { allowed: boolean; retryAfterSec: number } {
const t = this.now();
// A new key starts full: a quiet client may burst immediately.
const b = this.buckets.get(key) ?? { tokens: this.capacity, updatedAt: t };
// Lazy refill: no timer, just arithmetic on elapsed time, capped at capacity.
const elapsedSec = (t - b.updatedAt) / 1000;
b.tokens = Math.min(this.capacity, b.tokens + elapsedSec * this.refillPerSec);
b.updatedAt = t;
this.buckets.set(key, b);
if (b.tokens >= cost) {
b.tokens -= cost;
return { allowed: true, retryAfterSec: 0 };
}
// Honest Retry-After: time until enough tokens exist, rounded up.
const missing = cost - b.tokens;
return { allowed: false, retryAfterSec: Math.ceil(missing / this.refillPerSec) };
}
}
// Trace with capacity 10, refill 2/s:
// t = 0 s 10 calls -> all allowed, tokens = 0
// t = 0 s 11th call -> rejected, missing = 1, retryAfterSec = ceil(1 / 2) = 1
// t = 3 s tokens = min(10, 0 + 3 * 2) = 6 -> 6 more calls allowed
const limiter = new TokenBucketLimiter(10, 2);
const verdict = limiter.take("api-key-123");Pilih algoritma berdasarkan apa yang seharusnya dilakukan sebuah burst, bukan berdasarkan mana yang paling mudah ditulis. Fixed window cukup sampai batas window menjadi masalah, sliding window counter adalah kuota yang jujur, token bucket adalah default yang ramah untuk API, dan leaky bucket untuk melindungi sesuatu yang rapuh. Apa pun pilihannya, nyatakan laju berkelanjutan dan burst secara terpisah dan kembalikan Retry-After yang bisa Anda pertanggungjawabkan.
Sumber dan bacaan lanjutan