Rate Limiting Algorithms: Token Bucket vs Leaky Bucket vs Sliding Window

Di artikel sebelumnya kita udah ngobrol soal kenapa rate limiting itu penting banget. Nah, sekarang kita masuk ke bagian yang lebih seru: algoritmanya sendiri. 🤔

Nyatanya, bikin rate limiter itu bukan sekadar ngecek request_count > 100. Di balik setiap API Gateway modern—kayak Kong, NGINX, atau Cloudflare—ada perhitungan matematis yang nentuin gimana trafik kalian diperlakukan.

Ada empat algoritma yang paling sering dipakai di industri. Karakternya beda-beda, dan salah milih bisa bikin kuota kalian bocor atau pengguna asli malah kena blokir. Yuk, kita bedah satu-satu!

Token bucket, si favorit yang fleksibel

Token Bucket jadi standar de facto di sebagian besar API Gateway modern, termasuk AWS API Gateway dan Google Cloud Armor.

Cara kerjanya gampang. Bayangin satu ember dengan kapasitas token terbatas, misalnya 10 token.

• Tiap detik, sistem nambah token baru ke ember dengan laju konstan (misal 2 token/detik). Kalau embernya udah penuh, token barunya tumpah dan dibuang percuma.
• Setiap request HTTP dari klien harus ngambil 1 token biar boleh lewat.
• Token masih ada? Silakan diproses. Token habis? Request-nya langsung ditolak dengan 429 Too Many Requests.

Enaknya, algoritma ini ramah banget sama burst. Kalau klien diem beberapa detik, embernya ngisi penuh. Dia bisa nembak 10 request sekaligus dalam 1 milidetik tanpa ditolak, selama rata-rata jangka panjangnya tetap sesuai kuota.

Trade-off-nya: kalian mesti tuning dua parameter sekaligus. Bucket size nentuin seberapa besar burst yang ditoleransi, refill rate nentuin seberapa cepat kuotanya balik. Salah angka dikit, limiternya bisa kerasa terlalu longgar atau malah terlalu galak.

Leaky bucket, yang doyan ngerapiin antrean

Kalau Token Bucket ngatur jumlah token, Leaky Bucket ngatur laju keluaran request (throughput smoothing).

Ibaratnya ember berlubang kecil di dasarnya.

• Request dari klien masuk kayak air dituang dari atas, ditampung di antrean FIFO.
• Air netes keluar dari lubang dasar dengan laju stabil, misal tepat 5 request per detik, seberapa pun derasnya tuangan di atas.
• Kalau tuangannya kebanyakan sampai embernya meluap, air yang luber langsung dibuang—request-nya ditolak dengan 429.

Kelebihannya: alirannya jadi sangat stabil (constant rate). Cocok banget dipasang di depan service yang sensitif ke beban mendadak, misal sistem pembayaran perbankan warisan (legacy system) yang nggak sanggup nerima lonjakan.

Kekurangannya keras: dia nggak toleran sama burst sama sekali. Request yang sebenarnya sah malah nambah latensi karena harus ngantre di buffer, padahal server kalian masih sanggup kok ngelayanin.

Fixed window counter, simpel tapi ada jebakannya

Ini algoritma paling gampang dan paling sering ditulis developer pemula.

Waktu dibagi jadi jendela-jendela tetap (fixed time window), misal per menit: 00:00-00:01, 00:01-00:02, dan seterusnya.

• Tiap request di interval itu nambah counter sebesar 1.
• Kalau counter-nya lewat ambang batas (misal 100 req/menit), request berikutnya ditolak sampai jendelanya berganti dan counter-nya di-reset ke 0.

Masalahnya ada di jahitan antar-jendela. Anggap kuotanya 100 req/menit:

• Klien nembak 100 request di detik 00:59. Lolos semua.
• Klien nembak 100 request lagi di detik 01:01. Lolos juga, soalnya counter-nya baru di-reset.

Hasilnya, server nerima 200 request cuma dalam rentang 2 detik! Kapasitas yang kalian rencanain buat satu menit penuh, dilahap habis dalam sekejap. Inilah yang namanya boundary spike, dan pas lagi flash sale, dia bisa bikin backend kalian tumbang. 😅

Sliding window counter, akurat tanpa boros memori

Buat nutup celah boundary spike tanpa harus nyimpen log tiap request—itu namanya Sliding Window Log, dan boros memori—industri pindah ke pendekatan Sliding Window Counter.

Idenya: hitung estimasi request di jendela geser saat ini, dengan nimbrung proporsi dari jendela sebelumnya.

$$\text{Estimated Requests} = \text{Count}{\text{current}} + \left( \text{Count}{\text{previous}} \times (1 - \text{Overlap Ratio}) \right)$$

Contoh, kuota 100 req/menit:

• Jendela sebelumnya (00:00-01:00) nyatet 80 request.
• Sekarang jam 01:15, artinya kita baru 25% masuk ke jendela saat ini. Sisanya 75% masih nempel ke jendela sebelumnya.
• Di jendela saat ini udah ada 30 request baru.

Perkiraan trafik dalam 1 menit terakhir: 30 + (80 × 0.75) = 30 + 60 = 90 request.

Karena 90 masih di bawah 100, request-nya dilolosin.

Pendekatan ini akurat banget, masalah boundary spike-nya hilang, dan cuma butuh penyimpanan dua angka counter per klien. Bandingin sama Sliding Window Log yang harus nyimpen timestamp tiap request—jauh lebih hemat.

Jadi gimana, udah mulai kebayang bedanya? Belum selesai, masih ada bagian serunya nih. 😎

Kapan pilih yang mana?

Implementasi praktis: token bucket dengan Redis dan Lua

Di sistem microservices terdistribusi, kita wajib pakai shared store kayak Redis biar kuota klien tetap sinkron lintas semua pod instance API Gateway.

Biar nggak ada race condition—dua request baca token barengan terus dua-duanya lolos—seluruh logika cek dan ambil token harus jalan atomik lewat Lua Script:

-- Redis Lua Script untuk Token Bucket
local key = KEYS[1]
local limit = tonumber(ARGV[1])        -- Kapasitas maksimum ember (cth: 10)
local current_time = tonumber(ARGV[2]) -- Timestamp saat ini dalam detik
local refill_rate = tonumber(ARGV[3])  -- Token per detik (cth: 2)

-- Ambil data bucket: [tokens, last_updated]
local data = redis.call("HMGET", key, "tokens", "last_updated")
local tokens = tonumber(data[1])
local last_updated = tonumber(data[2])

if tokens == nil then
    tokens = limit
    last_updated = current_time
else
    -- Hitung penambahan token sejak request terakhir
    local delta = math.max(0, current_time - last_updated)
    tokens = math.min(limit, tokens + (delta * refill_rate))
    last_updated = current_time
end

-- Periksa apakah token mencukupi
if tokens >= 1 then
    tokens = tokens - 1
    redis.call("HSET", key, "tokens", tokens, "last_updated", last_updated)
    redis.call("EXPIRE", key, 3600) -- TTL 1 jam
    return 1 -- Izinkan request
else
    redis.call("HSET", key, "tokens", tokens, "last_updated", last_updated)
    return 0 -- Tolak request (429)
end

Integrasi sederhananya di aplikasi backend (FastAPI / Python):

import time
import redis
from fastapi import FastAPI, HTTPException, Request

app = FastAPI()
r = redis.Redis(host="localhost", port=6379, db=0)

# Load script Lua ke Redis
rate_limit_lua = r.register_script(open("token_bucket.lua").read())

@app.middleware("http")
async def rate_limit_middleware(request: Request, call_next):
    client_ip = request.client.host
    key = f"rate_limit:{client_ip}"

    # Kapasitas 10 token, refill 2 token per detik
    allowed = rate_limit_lua(keys=[key], args=[10, int(time.time()), 2])

    if not allowed:
        raise HTTPException(status_code=429, detail="Too Many Requests. Pelan-pelan ya!")

    return await call_next(request)

Jadi, algoritma mana yang cocok buat kalian?

Pada akhirnya, nggak ada algoritma yang menang di semua situasi. Token Bucket juara buat API publik karena ramah burst. Leaky Bucket menang kalau kalian butuh aliran yang benar-benar rata. Fixed Window cuma cocok buat proteksi kasar yang nggak butuh presisi tinggi. Sliding Window Counter jadi kompromi paling seimbang buat kuota ketat per jam atau per hari.

Yang paling penting, hitungan kuotanya disimpan di shared store dan diperiksa secara atomik. Soalnya rate limiter yang salah hitung gara-gara race condition itu kayak kasir yang ngitung duit sambil merem—kelihatan jalan, tapi saldonya udah kacau dari awal.

Selamat memilih algoritma ria, dan semoga bucket kalian nggak pernah bocor pas jam sibuk! 👋