Memilih Algoritma Rate Limit API: Pelajaran Praktis dari Knuth

Untuk memilih algoritma rate limiting API, jangan hanya bertanya “mana yang paling cepat”. Pertanyaan yang lebih tepat adalah: seberapa akurat batas yang dibutuhkan, apakah burst traffic boleh terjadi, berapa biaya penyimpanan yang dapat diterima, dan bagaimana keputusan limit dibuat secara atomic di banyak instance aplikasi.

Artikel ini menggunakan karya The Art of Computer Programming (TAOCP) karya Donald E. Knuth sebagai konteks: desain algoritma perlu dianalisis berdasarkan model biaya dan batasannya, bukan dipilih karena terlihat populer. Fokusnya bukan merangkum buku, melainkan menerapkan kebiasaan berpikir tersebut pada rate limiting API di lingkungan produksi.

Model masalah rate limiting API

Rate limiter memutuskan apakah sebuah permintaan boleh diteruskan berdasarkan identitas, waktu, dan kapasitas yang tersedia. Identitas tersebut biasanya berupa pengguna, API token, alamat IP, tenant, atau kombinasi beberapa atribut.

Secara umum, sebuah kebijakan dapat ditulis sebagai 100 request per 60 detik. Namun kalimat itu belum menjelaskan beberapa hal penting:

• Apakah 100 request boleh dikirim sekaligus?
• Apakah batas dihitung per endpoint atau untuk seluruh API?
• Apakah semua request memiliki biaya yang sama?
• Bagaimana sistem berperilaku saat beberapa instance aplikasi menerima request yang sama secara bersamaan?
• Berapa lama klien harus menunggu setelah menerima respons 429 Too Many Requests?

Rate limiting juga berbeda dari concurrency limiting. Rate limiting membatasi jumlah operasi dalam interval waktu, sedangkan concurrency limiting membatasi jumlah operasi yang sedang berjalan. Endpoint ekspor laporan mungkin membutuhkan keduanya: jumlah permintaan dibatasi per menit dan jumlah pekerjaan aktif dibatasi agar worker tidak kehabisan sumber daya.

Perbandingan algoritma rate limiting

Tidak ada satu algoritma yang selalu unggul. Pilihan yang tepat bergantung pada bentuk traffic dan konsekuensi ketika request ditolak.

1. Fixed window counter

Fixed window membagi waktu menjadi interval tetap, misalnya menit 12:00:00–12:00:59. Counter dinaikkan untuk setiap request dan di-reset ketika window berganti.

window = floor(current_time / 60)
key = 'rate:' + identity + ':' + window
count = INCREMENT(key)
SET_EXPIRE(key, 120)

if count <= 100:
    allow()
else:
    reject_with_429()

Kelebihan: sederhana, murah, dan hanya memerlukan satu counter aktif per identitas. Algoritma ini cocok untuk kebijakan kasar seperti batas request per menit pada API internal.

Kelemahan utama: boundary effect. Klien dapat mengirim 100 request pada akhir satu window dan 100 request lagi pada awal window berikutnya. Dalam waktu yang sangat singkat, server menerima hampir dua kali kapasitas yang secara intuitif diharapkan.

Fixed window memiliki biaya penyimpanan rendah dan kompleksitas implementasi rendah, tetapi akurasinya rendah di sekitar batas window. Gunakan jika burst singkat dapat ditoleransi atau jika limit hanya berfungsi sebagai perlindungan dasar.

2. Sliding window

Sliding window mengevaluasi jumlah request dalam interval yang selalu bergerak. Untuk setiap request pada waktu t, sistem menghitung request yang terjadi pada rentang t - 60 detik hingga t.

Implementasi yang paling akurat menyimpan timestamp setiap request, misalnya menggunakan sorted set. Saat request baru datang, timestamp yang lebih lama dari window dihapus, lalu jumlah anggota yang tersisa dihitung.

key = 'rate:' + identity
now = current_time_in_milliseconds
cutoff = now - 60000

REMOVE_SCORES_LESS_THAN(key, cutoff)
count = COUNT(key)

if count < 100:
    ADD(key, unique_request_id, now)
    SET_EXPIRE(key, 120)
    allow()
else:
    reject_with_429()

Kelebihan: lebih akurat daripada fixed window dan tidak memiliki lonjakan boundary yang sama. Algoritma ini berguna ketika fairness dalam rentang waktu sangat penting.

Kelemahan: penyimpanan dan operasi meningkat seiring jumlah request. Pada identitas dengan traffic tinggi, menyimpan satu item untuk setiap request dapat mahal. Sliding window berbasis bucket waktu mengurangi biaya tersebut, tetapi akurasinya menjadi pendekatan, bukan pencatatan penuh.

3. Leaky bucket

Leaky bucket memodelkan request sebagai air yang masuk ke dalam wadah dengan kapasitas terbatas. Air keluar pada laju konstan. Dalam sistem API, request dapat dimasukkan ke antrean untuk diproses secara stabil atau langsung ditolak ketika antrean penuh.

Algoritma ini cocok untuk shaping, yaitu meratakan traffic agar downstream menerima beban yang lebih konsisten. Namun, jika implementasinya menggunakan antrean, keputusan allow tidak selalu berarti request segera diproses. Sistem perlu mempertimbangkan batas waktu, kapasitas worker, dan kemungkinan pekerjaan menjadi kedaluwarsa.

Kelebihan: output rate stabil dan burst dapat diratakan. Kelemahan: membutuhkan antrean atau state tambahan, dapat meningkatkan latency, dan tidak ideal untuk endpoint interaktif yang seharusnya segera mendapat respons.

4. Token bucket

Token bucket memiliki kapasitas token tertentu. Token diisi kembali pada laju tetap. Setiap request mengambil satu token atau sejumlah token sesuai biayanya. Jika token habis, request ditolak atau ditunda.

elapsed = now - last_refill
available = min(capacity, tokens + elapsed * refill_rate)

if available >= request_cost:
    tokens = available - request_cost
    last_refill = now
    allow()
else:
    deficit = request_cost - available
    retry_after = ceil(deficit / refill_rate)
    reject_with_429(retry_after)

Kelebihan: mendukung burst terkontrol melalui kapasitas bucket, sambil menjaga rata-rata laju request melalui refill_rate. State yang diperlukan relatif kecil, biasanya hanya jumlah token dan waktu pengisian terakhir.

Kelemahan: konfigurasi kapasitas dan refill rate harus dipilih dengan benar. Jika kapasitas terlalu besar, burst tetap dapat membebani database atau layanan downstream. Jika terlalu kecil, klien sah dapat sering menerima penolakan.

Ringkasan trade-off

Memilih algoritma berdasarkan kebutuhan produksi

Gunakan fixed window untuk limit sederhana yang tidak memerlukan fairness ketat. Contohnya, membatasi akses endpoint administratif dengan jumlah request rendah.

Gunakan sliding window ketika definisi “N request dalam setiap N detik terakhir” harus mendekati akurat. Perhatikan ukuran state dan lakukan pembatasan tambahan untuk identitas ber-volume tinggi.

Gunakan leaky bucket ketika tujuan utama adalah menstabilkan beban downstream. Biasanya algoritma ini lebih tepat berada di depan worker atau antrean pekerjaan daripada di endpoint yang menuntut respons cepat.

Gunakan token bucket sebagai pilihan umum untuk API publik yang perlu mengizinkan burst kecil tetapi tetap mengendalikan rata-rata traffic. Parameter capacity menentukan burst maksimum, sedangkan refill_rate menentukan pemulihan kapasitas.

Dalam praktik, satu sistem dapat memakai beberapa lapisan. Misalnya, token bucket per API token untuk kuota client, fixed window per IP untuk perlindungan kasar, dan concurrency limit pada endpoint yang menjalankan query mahal. Lapisan tersebut harus memiliki tujuan berbeda; jangan menambahkan limiter tanpa memahami interaksi antar-lapisan.

Desain key dan atomicity pada Redis

Menentukan identitas limiter

Key limiter harus mencerminkan unit yang ingin dilindungi. Contoh pola yang eksplisit:

rl:v1:tenant:{tenant_id}:token:{token_id}:route:{route_group}
rl:v1:ip:{normalized_ip}:route:{route_group}
rl:v1:user:{user_id}:global

Beberapa prinsip yang perlu diterapkan:

• Prioritaskan API token atau user ID untuk pengguna terautentikasi; IP saja tidak cukup karena satu jaringan dapat dipakai banyak pengguna.
• Gunakan IP sebagai lapisan tambahan untuk endpoint publik, tetapi pertimbangkan proxy tepercaya saat membaca X-Forwarded-For. Jangan mempercayai header tersebut dari klien secara langsung.
• Kelompokkan route berdasarkan biaya, bukan hanya URL. Endpoint pencarian murah dan endpoint ekspor laporan sebaiknya tidak selalu berbagi budget.
• Normalisasi format identitas dan gunakan versi key agar perubahan kebijakan tidak mencampur state lama dan baru.
• Hindari memasukkan data sensitif mentah ke key. Gunakan ID internal atau hash yang memiliki panjang terkendali.

Atomicity di sistem terdistribusi

Increment, pemeriksaan limit, dan pembaruan expiry tidak boleh dipisah menjadi beberapa round trip biasa. Dua instance aplikasi dapat membaca counter yang sama, keduanya melihat kapasitas masih tersedia, lalu keduanya mengizinkan request sehingga limit terlampaui.

Redis menyediakan operasi atomic tertentu, tetapi rangkaian operasi tetap perlu dieksekusi sebagai satu unit. Gunakan Lua script atau mekanisme atomic lain yang sesuai dengan deployment Redis Anda. Berikut pseudocode bergaya Lua untuk token bucket; detail integrasi seperti serialisasi angka, TTL, dan penanganan error harus disesuaikan dengan client yang digunakan.

-- Pseudocode atomic token bucket
state = HGETALL(key)
now = server_time()

capacity = policy.capacity
tokens = state.tokens or capacity
last = state.last or now
elapsed = max(0, now - last)
refilled = min(capacity, tokens + elapsed * policy.refill_rate)

if refilled < policy.cost then
    deficit = policy.cost - refilled
    retry_after = ceil(deficit / policy.refill_rate)
    return { 0, retry_after, refilled }
end

new_tokens = refilled - policy.cost
HSET(key, 'tokens', new_tokens, 'last', now)
EXPIRE(key, policy.state_ttl)
return { 1, 0, new_tokens }

Waktu sebaiknya berasal dari sumber yang konsisten, misalnya waktu server Redis dalam script, bukan jam lokal setiap instance aplikasi yang mungkin mengalami perbedaan. Jika Redis tidak tersedia, tentukan kebijakan fail-open atau fail-closed secara sadar. Fail-open menjaga availability tetapi melemahkan perlindungan; fail-closed melindungi resource tetapi dapat menolak traffic sah saat dependency bermasalah.

Respons HTTP, Retry-After, dan pengalaman klien

Ketika limit terlampaui, gunakan status 429 Too Many Requests. Sertakan header yang membantu klien memperbaiki perilakunya, misalnya:

HTTP/1.1 429 Too Many Requests
Retry-After: 12
Content-Type: application/json

{ "error": "rate_limit_exceeded", "retry_after": 12 }

Nilai Retry-After dapat berupa jumlah detik atau tanggal HTTP. Jumlah detik biasanya lebih mudah dihasilkan oleh limiter. Untuk fixed window, nilainya dapat dihitung sampai awal window berikutnya. Untuk token bucket, gunakan waktu sampai token yang diperlukan tersedia. Pembulatan ke atas mencegah klien mencoba kembali terlalu dini.

Jika API memiliki header kuota seperti limit, remaining, dan reset, dokumentasikan maknanya secara tepat. Pada sliding window atau token bucket, nilai reset tidak selalu berupa satu timestamp sederhana. Jangan mengirim angka yang tampak presisi tetapi tidak sesuai dengan algoritma sebenarnya.

Mencegah bypass dan penyalahgunaan

Rate limiter yang hanya berada di satu route mudah dilewati dengan mengganti endpoint, format URL, atau kredensial. Terapkan kebijakan di lapisan yang konsisten dan normalisasi atribut sebelum membuat keputusan.

• Kelompokkan alias endpoint yang melakukan operasi sama ke dalam route group yang sama.
• Terapkan limit global per token atau tenant selain limit per route.
• Batasi pembuatan token, rotasi kredensial, dan endpoint autentikasi secara terpisah.
• Gunakan limit berbasis biaya untuk operasi yang berbeda tingkat bebannya. Contohnya, query kompleks dapat mengonsumsi lebih banyak token.
• Jangan mengandalkan user-agent atau IP sebagai satu-satunya identitas karena keduanya mudah dipalsukan atau berbagi banyak pengguna.
• Pastikan gateway, load balancer, dan aplikasi sepakat tentang identitas client serta daftar proxy yang dipercaya.
• Berikan pengecualian hanya melalui kebijakan terkontrol, bukan dengan melewati middleware secara diam-diam.

Rate limiting bukan pengganti autentikasi, otorisasi, validasi input, WAF, atau perlindungan terhadap biaya query. Ia adalah salah satu lapisan pengendalian beban dan abuse.

Observability dan debugging

Log setiap penolakan dengan data yang cukup untuk diagnosis, tetapi hindari menyimpan token rahasia. Field yang berguna antara lain identitas ter-hash, route group, algoritma, policy version, instance, hasil allow atau deny, remaining capacity, dan alasan penolakan.

Metrik yang sebaiknya dipantau:

• Rasio respons 429 per route, tenant, dan jenis identitas.
• Jumlah request yang diizinkan dan ditolak.
• Latency operasi limiter, termasuk latency Redis.
• Distribusi nilai remaining token atau counter.
• Jumlah key aktif dan penggunaan memori untuk sliding window.
• Timeout, error, serta keputusan fail-open atau fail-closed.

Tambahkan tracing pada operasi limiter agar dapat dibedakan apakah latency berasal dari aplikasi, Redis, atau downstream. Saat menyelidiki keluhan “limit terlalu ketat”, periksa zona waktu, unit milidetik versus detik, policy yang terpilih, identitas yang terbentuk, dan apakah retry client menghormati Retry-After.

Strategi pengujian abuse dan traffic burst

Pengujian tidak cukup dengan mengirim request berurutan dari satu client. Uji perilaku di boundary, konkurensi, dan kegagalan dependency.

1. Uji baseline: kirim request di bawah limit dan pastikan semuanya diizinkan dengan header yang konsisten.
2. Uji tepat pada limit: kirim jumlah request sama dengan kapasitas, lalu request tambahan untuk memastikan keputusan deny sesuai kebijakan.
3. Uji boundary fixed window: kirim traffic di akhir dan awal window. Dokumentasikan bahwa hasil tersebut adalah konsekuensi algoritma, bukan bug tak terduga.
4. Uji burst token bucket: kirim burst sebesar kapasitas bucket, kemudian lanjutkan traffic konstan dan verifikasi pemulihan sesuai refill rate.
5. Uji concurrency: jalankan banyak worker secara bersamaan pada key yang sama dan periksa bahwa jumlah token yang dikonsumsi tidak melebihi kapasitas akibat race condition.
6. Uji multi-instance: arahkan request ke beberapa instance aplikasi untuk memastikan state tidak menjadi limiter lokal yang mudah dilewati.
7. Uji identitas: verifikasi pemisahan antar-user, tenant, token, IP, dan route group.
8. Uji Redis gagal atau lambat: pastikan keputusan fail-open atau fail-closed sesuai risiko endpoint.
9. Uji retry client: pastikan klien tidak melakukan retry agresif tanpa backoff dan jitter setelah menerima 429.

Gunakan traffic sintetis dengan identitas yang terkontrol dan jangan melakukan pengujian abuse terhadap sistem pihak lain. Untuk endpoint mahal, ukur bukan hanya jumlah request, tetapi juga beban database, antrean, CPU, memori, dan latency downstream.

Kesimpulan pemilihan

Jika kebutuhan Anda sederhana dan biaya state harus minimal, mulai dengan fixed window sambil memahami efek boundary. Jika fairness pada interval berjalan menjadi prioritas, pilih sliding window dan rencanakan biaya penyimpanannya. Jika traffic harus diratakan menuju worker atau layanan downstream, leaky bucket lebih sesuai. Untuk API publik yang membutuhkan burst terkontrol dan state kecil, token bucket sering menjadi kompromi praktis.

Pelajaran praktis dari Knuth adalah membandingkan algoritma berdasarkan model penggunaan nyata: operasi per request, ukuran state, perilaku pada kasus terburuk, konkurensi, dan konsekuensi kegagalan. Rate limiter yang baik bukan yang paling kompleks, melainkan yang perilakunya dapat dijelaskan, diuji, diamati, dan selaras dengan kapasitas sistem yang dilindunginya.

Referensi

• The Art of Computer Programming — Donald E. Knuth
• RFC 6585: Additional HTTP Status Codes