RATE-LIMITING ALGORITHMS SYSTEM-DESIGN BACKEND API SCALABILITY DISTRIBUTED-SYSTEMS SECURITY PERFORMANCE BEST-PRACTICES ARCHITECTURE RESILIENCE

Rate Limiting Algorithms: Membangun Sistem yang Adil dan Efisien dengan Token Bucket dan Leaky Bucket

⏱️ 14 menit baca
👨‍💻

Rate Limiting Algorithms: Membangun Sistem yang Adil dan Efisien dengan Token Bucket dan Leaky Bucket

1. Pendahuluan

Di dunia web development yang serba cepat, aplikasi kita seringkali menghadapi berbagai tantangan. Salah satunya adalah lonjakan traffic yang tak terduga, serangan berbahaya (seperti DDoS), atau sekadar perilaku pengguna yang berlebihan. Tanpa perlindungan yang tepat, server kita bisa kewalahan, performa menurun drastis, atau bahkan down sama sekali.

Di sinilah Rate Limiting berperan penting. Jika Anda pernah membaca artikel sebelumnya tentang “Rate Limiting: Melindungi API dan Aplikasi Anda dari Beban Berlebih & Serangan”, Anda pasti sudah tahu mengapa Rate Limiting itu krusial. Ini adalah mekanisme untuk mengontrol seberapa sering sebuah user, IP address, atau aplikasi dapat mengakses suatu resource dalam periode waktu tertentu. Tujuannya jelas: menjaga stabilitas, keadilan, dan ketersediaan sistem kita.

Namun, memahami mengapa Rate Limiting itu penting hanyalah permulaan. Pertanyaan selanjutnya adalah: bagaimana kita mengimplementasikannya? Di balik konsep Rate Limiting, ada berbagai algoritma yang bisa kita gunakan, masing-masing dengan karakteristik dan kegunaannya sendiri.

Dalam artikel ini, kita akan menyelam lebih dalam ke dua algoritma Rate Limiting paling populer dan praktis: Token Bucket dan Leaky Bucket. Kita akan memahami cara kerjanya, membedakan kelebihan dan kekurangannya, serta melihat contoh konkret implementasinya. Siap membangun sistem yang lebih tangguh? Mari kita mulai!

2. Mengapa Kita Butuh Algoritma Rate Limiting?

Bayangkan Anda memiliki sebuah gerbang tol. Konsep Rate Limiting adalah tentang memastikan tidak terlalu banyak mobil yang melewati gerbang itu dalam satu waktu. Tapi bagaimana cara kerjanya di belakang layar? Apakah ada penjaga yang menghitung setiap mobil? Atau ada sistem otomatis yang mengatur kecepatan?

Tanpa algoritma yang jelas, implementasi Rate Limiting bisa jadi kacau:

Algoritma Rate Limiting menyediakan kerangka kerja yang terstruktur untuk menjawab pertanyaan-pertanyaan ini. Mereka memberikan aturan main yang konsisten tentang kapan sebuah request boleh lewat, dan kapan harus ditolak atau ditunda.

📌 Penting: Pemilihan algoritma yang tepat sangat bergantung pada kebutuhan spesifik aplikasi Anda. Ada yang lebih cocok untuk traffic bursty (lonjakan singkat), ada pula yang ideal untuk menjaga throughput yang stabil.

3. Algoritma Token Bucket: Fleksibilitas dengan Bursting

Algoritma Token Bucket adalah salah satu yang paling sering digunakan karena fleksibilitasnya dalam menangani burst traffic.

💡 Analogi: Bayangkan sebuah ember (bucket) yang secara konstan diisi dengan koin (token) dengan kecepatan tertentu. Ember ini memiliki kapasitas maksimum.

Cara Kerja Token Bucket:

  1. Token Generation: Token dihasilkan secara periodik dan ditambahkan ke dalam ember. Misalnya, 10 token per detik.
  2. Bucket Capacity: Ember memiliki ukuran maksimum (misalnya, 100 token). Jika ember penuh, token baru yang dihasilkan akan dibuang.
  3. Request Consumption: Setiap kali ada request masuk, ia mencoba “mengambil” satu token dari ember.
  4. Decision:
    • ✅ Jika ada token tersedia, request berhasil lewat, dan satu token diambil dari ember.
    • ❌ Jika tidak ada token tersedia, request ditolak (atau di-queue, tergantung implementasi).

Kelebihan Token Bucket:

Kekurangan Token Bucket:

Contoh Implementasi Konseptual (Pseudo-code):

class TokenBucket:
    def __init__(self, capacity, fill_rate):
        self.capacity = capacity # Kapasitas maksimum ember
        self.fill_rate = fill_rate # Jumlah token per detik
        self.tokens = capacity # Jumlah token saat ini di ember
        self.last_refill_time = time.time()

    def allow_request(self, tokens_needed=1):
        now = time.time()

        # Hitung berapa banyak token yang harus diisi sejak terakhir
        time_passed = now - self.last_refill_time
        tokens_to_add = time_passed * self.fill_rate

        # Tambahkan token, tapi jangan melebihi kapasitas
        self.tokens = min(self.capacity, self.tokens + tokens_to_add)
        self.last_refill_time = now

        # Cek apakah ada cukup token
        if self.tokens >= tokens_needed:
            self.tokens -= tokens_needed
            return True
        else:
            return False

# Contoh penggunaan:
bucket = TokenBucket(capacity=10, fill_rate=1) # 10 request/detik, burst 10
# Dalam 1 detik, bisa memproses 10 request, tapi jika ada 15 request dalam 0.1 detik,
# 10 akan lewat dan 5 akan ditolak (jika ember kosong)

Use Case: API publik yang mengizinkan 100 request per menit, tetapi juga dapat menangani lonjakan 20 request dalam satu detik sesekali.

4. Algoritma Leaky Bucket: Aliran Konstan yang Teratur

Berbeda dengan Token Bucket, algoritma Leaky Bucket berfokus pada menstabilkan output rate dari sistem Anda.

💡 Analogi: Bayangkan sebuah ember (bucket) yang memiliki lubang bocor di bagian bawahnya. Air (request) masuk ke dalam ember, tapi hanya bisa keluar melalui lubang bocor dengan kecepatan konstan.

Cara Kerja Leaky Bucket:

  1. Request Arrival: Setiap request yang masuk akan “dimasukkan” ke dalam ember.
  2. Bucket Capacity: Ember memiliki kapasitas maksimum. Jika ember penuh, request baru akan ditolak.
  3. Constant Output Rate: Request “keluar” dari ember (diproses) dengan kecepatan yang konstan, terlepas dari seberapa cepat request masuk.
  4. Decision:
    • ✅ Jika ember tidak penuh, request berhasil masuk ke ember dan akan diproses sesuai laju bocor.
    • ❌ Jika ember penuh, request ditolak.

Kelebihan Leaky Bucket:

Kekurangan Leaky Bucket:

Contoh Implementasi Konseptual (Pseudo-code):

import collections

class LeakyBucket:
    def __init__(self, capacity, leak_rate):
        self.capacity = capacity # Kapasitas maksimum ember
        self.leak_rate = leak_rate # Jumlah request keluar per detik
        self.bucket = collections.deque() # Antrian request di ember
        self.last_leak_time = time.time()

    def allow_request(self):
        now = time.time()

        # Hitung berapa banyak request yang harus keluar sejak terakhir
        time_passed = now - self.last_leak_time
        requests_to_leak = int(time_passed * self.leak_rate)

        # Keluarkan request dari ember
        for _ in range(requests_to_leak):
            if self.bucket:
                self.bucket.popleft()
            else:
                break
        self.last_leak_time = now

        # Cek apakah ember penuh
        if len(self.bucket) < self.capacity:
            self.bucket.append(now) # Tambahkan request ke ember
            return True
        else:
            return False

# Contoh penggunaan:
bucket = LeakyBucket(capacity=5, leak_rate=1) # Memproses 1 request/detik, queue maks 5
# Jika 10 request datang dalam 0.1 detik, 5 akan di-queue dan 5 akan ditolak.
# 5 request yang di-queue akan diproses satu per satu dalam 5 detik ke depan.

Use Case: Sistem yang mengirim notifikasi ke user (misalnya, email). Anda ingin memastikan hanya 10 notifikasi yang dikirim per detik untuk menghindari blacklist dari penyedia email, terlepas dari seberapa cepat notifikasi dihasilkan.

5. Perbandingan Token Bucket vs. Leaky Bucket: Kapan Memilih yang Mana?

Memilih antara Token Bucket dan Leaky Bucket bergantung pada kebutuhan spesifik aplikasi Anda. Berikut adalah ringkasan perbandingan dan panduan penggunaannya:

Fitur / KriteriaToken BucketLeaky Bucket
Toleransi Burst✅ Sangat Baik❌ Buruk
Output TrafficBursty (tidak rata)Stabil dan Rata
Kapan DigunakanAPI publik, layanan yang butuh fleksibilitasBackend kritis, resource terbatas, sistem antrian
Fokus UtamaMengontrol input rate dengan toleransi burstMengontrol output rate yang stabil
Potensi LatencyRendah (kecuali ember kosong)Bisa tinggi (saat ember penuh)

🎯 Kapan Memilih Token Bucket?

🎯 Kapan Memilih Leaky Bucket?

Pertimbangan Lanjutan:

6. Implementasi Praktis dengan Redis

Untuk sistem terdistribusi, mengimplementasikan Rate Limiting hanya di memori aplikasi (in-memory) tidak akan berfungsi karena setiap instance aplikasi akan memiliki “ember” atau “token”nya sendiri. Kita membutuhkan state yang dibagikan. Redis adalah pilihan yang sangat populer untuk ini karena kecepatannya.

Mari kita lihat contoh konseptual implementasi Token Bucket menggunakan Redis:

import redis
import time

# Asumsikan koneksi Redis
r = redis.Redis(host='localhost', port=6379, db=0)

def token_bucket_redis(key, capacity, fill_rate, tokens_needed=1):
    # Key unik untuk setiap klien/endpoint (misal: "rate_limit:user:123" atau "rate_limit:ip:192.168.1.1")

    # Gunakan pipeline atau LUA script untuk operasi atomik
    # Ini penting agar tidak ada race condition
    script = """
    local key = KEYS[1]
    local capacity = tonumber(ARGV[1])
    local fill_rate = tonumber(ARGV[2])
    local tokens_needed = tonumber(ARGV[3])
    local now = tonumber(ARGV[4])

    local last_refill_time = tonumber(redis.call('HGET', key, 'last_refill_time')) or 0
    local current_tokens = tonumber(redis.call('HGET', key, 'tokens')) or capacity

    local time_passed = now - last_refill_time
    local tokens_to_add = time_passed * fill_rate

    current_tokens = math.min(capacity, current_tokens + tokens_to_add)

    if current_tokens >= tokens_needed then
        current_tokens = current_tokens - tokens_needed
        redis.call('HSET', key, 'tokens', current_tokens)
        redis.call('HSET', key, 'last_refill_time', now)
        return 1 -- Allowed
    else
        redis.call('HSET', key, 'tokens', current_tokens) -- Update tokens even if denied
        redis.call('HSET', key, 'last_refill_time', now)
        return 0 -- Denied
    end
    """

    # Eksekusi LUA script
    result = r.eval(script, 1, key, capacity, fill_rate, tokens_needed, time.time())

    return bool(result)

# Contoh penggunaan:
user_id = "user:123"
limit_capacity = 100 # Token bucket capacity
limit_fill_rate = 100 / 60 # 100 token per menit (sekitar 1.66 token per detik)

if token_bucket_redis(f"rate_limit:{user_id}", limit_capacity, limit_fill_rate):
    print("✅ Request diperbolehkan.")
else:
    print("❌ Request ditolak (Rate Limit terlampaui).")
    # Di sini bisa kirim HTTP 429 Too Many Requests

Kode di atas menggunakan Lua script untuk Redis. Mengapa? Karena operasi HGET, HSET, dan logika penghitungan harus dilakukan secara atomik. Artinya, semua langkah harus selesai sebagai satu unit, tanpa intervensi dari klien lain. Ini mencegah race condition yang bisa terjadi jika kita melakukan HGET dan HSET secara terpisah dari kode aplikasi.

✅ Tips Praktis:

Kesimpulan

Rate Limiting adalah pilar penting dalam membangun aplikasi web yang tangguh, adil, dan performa tinggi. Dengan memahami algoritma di baliknya seperti Token Bucket dan Leaky Bucket, Anda kini memiliki senjata ampuh untuk melindungi aplikasi Anda dari berbagai ancaman dan beban berlebih.

Ingat, Token Bucket sangat cocok untuk skenario yang membutuhkan toleransi terhadap burst traffic, sementara Leaky Bucket unggul dalam menciptakan aliran traffic output yang stabil dan teratur. Pilihan ada di tangan Anda, sesuaikan dengan karakteristik dan kebutuhan sistem Anda.

Mulai sekarang, jangan hanya tahu apa itu Rate Limiting, tapi juga bagaimana mengimplementasikannya dengan cerdas. Sistem Anda akan berterima kasih!

🔗 Baca Juga