Token Bucket Algorithm: Mekanisme Rate Limiting & Implementasi

Definisi Token Bucket

Token Bucket adalah algoritma yang digunakan dalam jaringan komputer dan sistem perangkat lunak untuk mengontrol jumlah permintaan (request) yang dikirim ke sebuah layanan dalam rentang waktu tertentu. Algoritma ini memungkinkan adanya burstiness (lonjakan trafik) selama token masih tersedia di dalam 'ember' (bucket), namun tetap membatasi rata-rata laju permintaan sesuai dengan kapasitas pengisian token.

Mekanisme Kerja

Algoritma ini bekerja dengan prinsip sederhana: sebuah bucket memiliki kapasitas maksimum (b). Token ditambahkan ke dalam bucket dengan laju konstan (r) per detik. Setiap kali permintaan masuk, sistem akan memeriksa apakah ada token yang tersedia di dalam bucket:

• Jika token tersedia: Permintaan diizinkan (diteruskan), dan satu token dikurangi dari bucket.
• Jika token habis: Permintaan ditolak (HTTP 429 Too Many Requests) atau diantrekan.

Implementasi Kode (Python)

import time

class TokenBucket:
    def __init__(self, capacity, refill_rate):
        self.capacity = capacity
        self.refill_rate = refill_rate
        self.tokens = capacity
        self.last_refill = time.time()

    def consume(self):
        now = time.time()
        elapsed = now - self.last_refill
        self.tokens = min(self.capacity, self.tokens + elapsed * self.refill_rate)
        self.last_refill = now

        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

Perbandingan: Token Bucket vs Leaky Bucket

Perbedaan mendasar terletak pada cara menangani lonjakan trafik. Token Bucket mengizinkan lonjakan selama kapasitas bucket mencukupi, sedangkan Leaky Bucket memaksa trafik keluar dengan laju yang benar-benar konstan, sehingga seringkali menyebabkan antrean panjang atau pembuangan paket (packet loss) jika input terlalu cepat.

Matriks Perbandingan

Kelebihan dan Kekurangan

Kelebihan: Sangat fleksibel untuk menangani trafik yang tidak stabil namun tetap menjaga rata-rata penggunaan sumber daya server. Mudah diimplementasikan menggunakan Redis untuk sistem terdistribusi.

Kekurangan: Memerlukan manajemen state (jumlah token) yang akurat. Jika menggunakan sistem terdistribusi, sinkronisasi state antar node bisa menjadi tantangan performa (latency).