Rate Limiter

Algoritma token bucket dan sliding window beserta penempatannya dalam arsitektur.

Daftar isi

Rate limiter membatasi laju permintaan dari satu sumber, misalnya per pengguna, per API key, atau per alamat IP, sebelum beban mencapai layanan di belakangnya. Konsep pembatasan laju sebagai pelindung sistem sudah dibahas pada modul sistem asinkron, sehingga topik ini berfokus pada algoritma penegaknya. Dua algoritma yang paling umum, yaitu token bucket dan sliding window, dibedah dengan simulasi Python pada urutan permintaan yang sama, lalu ditutup dengan penempatan dalam arsitektur dan analisis mode kegagalan.

Kebutuhan dan semantik keputusan#

Rate limiter menjawab satu pertanyaan untuk setiap permintaan, yaitu IZIN atau TOLAK, dan jawaban itu harus sangat cepat karena pengecekannya berada di jalur setiap permintaan. Aturan batas dapat berbeda per sumber, misalnya 100 permintaan per menit untuk satu pengguna dan 10.000 permintaan per menit untuk satu kunci layanan. Sumber yang ditolak juga perlu tahu kapan percobaan berikutnya boleh dilakukan, sehingga penolakan bukan sekadar error.

Kontrak itu dinyatakan pada respons HTTP. Status 429 Too Many Requests, yang didefinisikan pada RFC 6585, menandai permintaan yang melewati batas, dan header Retry-After menyatakan sisa waktu tunggu dalam detik.

text Contoh: respons ketika batas terlampaui

HTTP/1.1 429 Too Many Requests
Retry-After: 12

Tanpa Retry-After, klien yang agresif cenderung mengulang permintaan seketika, sehingga beban justru bertambah tepat ketika sistem sedang menahan diri. Header itu mengubah penolakan menjadi instruksi yang dapat dijalankan klien dengan tertib. Selain itu, jawaban IZIN dan TOLAK harus konsisten untuk permintaan yang berjarak rapat, karena klien yang menguji ulang tidak boleh melihat kuota yang berpindah-pindah antarinstance.

Token bucket#

Token bucket menyimpan izin dalam bentuk token pada sebuah ember. Token ditambahkan pada laju tetap sampai ember penuh, dan setiap permintaan menghabiskan satu token. Permintaan diizinkan bila token tersedia, dan ditolak bila ember kosong. Apabila $x$ menyatakan jumlah token, $K$ kapasitas ember, $\rho$ laju pengisian, dan $\Delta t$ selang sejak pembaruan terakhir, jumlah token diperbarui dengan

x \leftarrow \min\left(K,\ x + \rho \cdot \Delta t\right)

Dua parameter itu memberi dua kemampuan yang berbeda. Laju $\rho$ menentukan rata-rata permintaan yang diperbolehkan dalam jangka panjang, sedangkan kapasitas $K$ menentukan kedalaman lonjakan yang ditoleransi sebelum penolakan terjadi. Ember yang penuh di awal membolehkan sekelompok permintaan lewat sekaligus, kemudian menegakkan laju rata-rata setelahnya.

Simulator berikut memakai jam virtual yang maju 0,25 detik pada setiap penekanan tombol Kirim permintaan. Tekan tombol itu berulang kali dan amati ember habis, lalu tekan Tunggu dua detik dan amati token terisi kembali sebagaimana rumus $\Delta t$ di atas.

Kode sumber demo

<!DOCTYPE html>
<html lang="id">
<head>
<meta charset="utf-8">
<title>Simulator token bucket</title>
<style>
  body { font-family: sans-serif; font-size: 14px; margin: 12px; }
  button { margin-right: 8px; padding: 6px 10px; cursor: pointer; }
  #ember { height: 18px; background: #e8f0fe; border: 1px solid #1a56db; margin: 8px 0; }
  #isi { height: 100%; background: #1a56db; }
  #status { margin: 4px 0; }
  #log { margin-top: 10px; background: #f5f5f5; border: 1px solid #ddd; height: 140px;
         overflow-y: auto; padding: 6px; font-family: monospace; font-size: 12px; }
</style>
</head>
<body>
<p>Kapasitas 5 token, laju isi 1 token per detik, jam virtual maju 0,25 detik per permintaan.</p>
<p>
  <button id="kirim" type="button">Kirim permintaan</button>
  <button id="tunggu" type="button">Tunggu 2 detik</button>
</p>
<div id="ember"><div id="isi"></div></div>
<p id="status"></p>
<div id="log"></div>
<script>
  var KAPASITAS = 5, LAJU = 1.0;
  var token = KAPASITAS, jam = 0.0;
  function isiBar() {
    document.getElementById('isi').style.width = (token / KAPASITAS * 100) + '%';
    document.getElementById('status').textContent =
      'jam virtual: ' + jam.toFixed(2) + ' detik, token: ' + token.toFixed(2);
  }
  function log(teks) {
    var baris = document.createElement('div');
    baris.textContent = teks;
    document.getElementById('log').prepend(baris);
  }
  function maju(dt) {
    token = Math.min(KAPASITAS, token + LAJU * dt);
    jam += dt;
  }
  document.getElementById('kirim').addEventListener('click', function () {
    maju(0.25);
    if (token >= 1) {
      token -= 1;
      log('t=' + jam.toFixed(2) + '  IZIN   (sisa ' + token.toFixed(2) + ' token)');
    } else {
      log('t=' + jam.toFixed(2) + '  TOLAK  (sisa ' + token.toFixed(2) + ' token)');
    }
    isiBar();
  });
  document.getElementById('tunggu').addEventListener('click', function () {
    maju(2.0);
    log('t=' + jam.toFixed(2) + '  tunggu, token terisi menjadi ' + token.toFixed(2));
    isiBar();
  });
  isiBar();
  log('Siap. Tekan Kirim permintaan enam kali, lalu Tunggu 2 detik, lalu kirim lagi.');
</script>
</body>
</html>

Sliding window#

Sliding window menegakkan batas tanpa menyimpan token, melainkan dengan menghitung permintaan yang masih berada di dalam jendela waktu yang bergeser. Varian sliding window log mencatat waktu setiap permintaan yang diizinkan, membuang catatan yang lebih tua dari panjang jendela, dan menolak permintaan bila jumlah catatan yang tersisa sudah mencapai batas. Varian ini tepat, tetapi memorinya sebanding dengan jumlah permintaan per sumber.

Varian kedua, yaitu sliding window counter, memperkirakan jumlah permintaan dengan membagi waktu menjadi jendela tetap dengan panjang $T$ . Apabila $n_{p}$ menyatakan jumlah permintaan pada jendela tetap sebelumnya, $n_{k}$ pada jendela kini, dan $r$ porsi jendela sebelumnya yang masih berlaku, jumlah permintaan yang dihitung adalah

n \approx n_{p} \cdot r + n_{k}

Perkiraan ini hanya membutuhkan dua angka per sumber, sehingga memorinya konstan, tetapi presisinya menurun pada pola trafik yang tidak merata di dalam jendela. Pemilihannya menukar ketepatan dengan biaya, dan simulasi berikut memperlihatkan perbedaannya secara langsung.

Simulasi pada urutan permintaan yang sama#

Berkas berikut menjalankan token bucket dengan kapasitas 5 token dan laju isi 2 token per detik, serta sliding window log dengan batas 5 permintaan per 1,0 detik. Kedua pengaturan menargetkan laju rata-rata yang senilai, yaitu 2 permintaan per detik dengan toleransi lonjakan, dan 20 permintaan uji disusun manual tanpa bilangan acak.

python simulasi-rate-limiter.py

"""Simulasi dua algoritma rate limiter pada urutan permintaan yang sama.

Token bucket memakai kapasitas 5 token dengan pengisian ulang 2 token per
detik. Sliding window log memakai batas 5 permintaan dalam jendela 1,0
detik. Kedua pengaturan menargetkan laju rata-rata yang senilai, yaitu
2 permintaan per detik dengan toleransi lonjakan singkat.

Waktu permintaan ditetapkan manual tanpa bilangan acak, sehingga keluaran
dapat dihitung ulang.
"""

from collections import deque

KAPASITAS_TOKEN = 5
LAJU_ISI = 2.0          # token per detik
BATAS_JENDELA = 5       # permintaan per jendela
PANJANG_JENDELA = 1.0   # detik

PERMINTAAN = [
    0.0, 0.1, 0.2, 0.3, 0.4, 0.5, 0.6,
    0.8, 1.0, 1.2,
    2.0, 2.1, 2.5,
    3.0, 3.1, 3.2, 3.3, 3.4, 3.5, 3.6,
]


class TokenBucket:
    def __init__(self):
        self.token = float(KAPASITAS_TOKEN)
        self.waktu_terakhir = PERMINTAAN[0]

    def izinkan(self, t):
        self.token = min(KAPASITAS_TOKEN, self.token + LAJU_ISI * (t - self.waktu_terakhir))
        self.waktu_terakhir = t
        if self.token >= 1.0:
            self.token -= 1.0
            return True
        return False


class SlidingWindowLog:
    def __init__(self):
        self.catatan = deque()

    def izinkan(self, t):
        while self.catatan and self.catatan[0] <= t - PANJANG_JENDELA:
            self.catatan.popleft()
        if len(self.catatan) < BATAS_JENDELA:
            self.catatan.append(t)
            return True
        return False


if __name__ == "__main__":
    bucket = TokenBucket()
    log = SlidingWindowLog()
    print(f"{'t (detik)':>9}   {'token bucket':<12}  sliding log")
    for t in PERMINTAAN:
        k_bucket = "IZIN" if bucket.izinkan(t) else "TOLAK"
        k_log = "IZIN" if log.izinkan(t) else "TOLAK"
        print(f"{t:>9.1f}   {k_bucket:<12}  {k_log}")

text Keluaran

t (detik)   token bucket  sliding log
      0.0   IZIN          IZIN
      0.1   IZIN          IZIN
      0.2   IZIN          IZIN
      0.3   IZIN          IZIN
      0.4   IZIN          IZIN
      0.5   IZIN          TOLAK
      0.6   TOLAK         TOLAK
      0.8   TOLAK         TOLAK
      1.0   IZIN          IZIN
      1.2   TOLAK         IZIN
      2.0   IZIN          IZIN
      2.1   IZIN          IZIN
      2.5   IZIN          IZIN
      3.0   IZIN          IZIN
      3.1   TOLAK         IZIN
      3.2   TOLAK         IZIN
      3.3   TOLAK         IZIN
      3.4   TOLAK         TOLAK
      3.5   IZIN          IZIN
      3.6   TOLAK         TOLAK

Perbedaan keduanya terlihat pada empat tempat. Pada detik pertama, token bucket mengizinkan enam permintaan karena ember penuh di awal, sedangkan sliding log tepat lima sesuai batas jendelanya. Pada $t = 1{,}2$ , log mengizinkan permintaan yang ditolak oleh bucket, karena catatan lama telah bergeser keluar dari jendela sementara token belum terisi kembali. Pada $t = 3{,}1$ sampai $t = 3{,}4$ , log masih mengizinkan empat permintaan beruntun karena permintaan pada awal detik kelima sudah keluar dari jendela, sedangkan bucket kehabisan token pada keempatnya. Kesimpulannya konsisten dengan teorinya, yaitu token bucket menoleransi lonjakan sebesar kapasitas ember, sedangkan sliding log menegakkan batas jendela yang kaku, dan sliding window counter berada di tengah dengan memori konstan tetapi hasil perkiraan.

Penempatan dalam arsitektur#

Rate limiter dapat ditempatkan pada tiga titik. Pengecekan di sisi klien tidak dapat dipercaya karena klien yang jahat melewatkannya, sehingga penegakan selalu di sisi server. Penegakan terpusat pada gerbang, yaitu di load balancer atau gateway API, memberi satu titik kebijakan untuk seluruh layanan, sedangkan penegakan sebagai middleware di dalam layanan membolehkan aturan yang spesifik terhadap perilaku layanan itu.

Rate limiter sebagai gerbang pada jalur permintaan dengan aturan batas di cache terdistribusi

Keputusan arsitektur yang tersisa adalah tempat keadaan kuota disimpan. Keadaan di memori lokal setiap instance paling cepat karena tanpa panggilan jaringan, tetapi kuota melebar karena setiap instance menghitung sendiri, sehingga batas 100 per menit menjadi 100 dikali jumlah instance. Keadaan di cache terdistribusi, seperti pada modul cache terdistribusi, menjaga kuota tetap presisi lintas instance dengan tambahan satu panggilan jaringan pada setiap permintaan. Kompromi yang lazim adalah menghitung batas di cache terdistribusi hanya untuk sumber yang dikenai kontrak kuota, dan mengandalkan hitungan lokal untuk selebihnya.

Mode kegagalan#

Rate limiter terpusat mati. Pilihan yang tersisa adalah fail open, yaitu mengizinkan semua permintaan dan mencatat kejadiannya, atau fail closed, yaitu menolak semuanya. Layanan publik umumnya memilih fail open dengan batas lokal sebagai cadangan, karena ketersediaan lebih bernilai daripada kepastian kuota.
Sumber aturan tidak tersedia. Rate limiter memakai aturan default yang konservatif alih-alih menolak semua permintaan, dan aturan bawaan itu dinyatakan dalam kode, bukan diambil dari penyimpanan yang sedang mati.
Jam antarinstance bergeser. Jendela waktu yang dihitung dari jam lokal setiap instance saling meleset, sehingga sumber waktu diambil dari satu tempat, atau keadaan kuota dihitung dengan interval monotonic lokal per instance.
Cache terdistribusi lambat. Pengecekan kuota menambah latensi setiap permintaan, sehingga panggilannya diberi batas waktu, dan keputusan saat batas waktu habis dinyatakan eksplisit, umumnya fail open.

Kesalahan umum#

Memakai jendela tetap tanpa bobot. Klien yang menghabiskan kuota pada detik terakhir satu jendela dan mengulanginya pada detik pertama jendela berikutnya memperoleh lonjakan hampir dua kali batas. Perbaikannya adalah counter berbobot atau sliding window log.
Mengunci batas pada alamat IP saja. Banyak pengguna sah berbagi satu alamat pada jaringan kantor atau seluler, sehingga kuota alamat itu habis untuk pengguna yang tidak berhubungan. Batas dipindahkan ke identitas yang lebih halus, misalnya API key, bila tersedia.
Menolak tanpa header Retry-After. Klien yang baik pun tidak tahu kapan boleh mencoba lagi, dan yang agresif mengulang seketika. Sertakan sisa waktu tunggu pada setiap penolakan.
Memasang kapasitas ember terlalu kecil. Trafik sah yang wajar berlonjakan, misalnya saat halaman memanggil beberapa endpoint sekaligus, langsung ditolak. Kapasitas dikalibrasi dari pola puncak yang masih dianggap sah.

Ringkasan#

Token bucket menegakkan laju rata-rata $\rho$ dengan toleransi lonjakan sebesar kapasitas $K$ , sedangkan sliding window log menegakkan batas jendela yang kaku dengan memori sebanding jumlah permintaan.
Sliding window counter memperkirakan $n_{p} \cdot r + n_{k}$ dengan memori konstan, sehingga menjadi titik tengah antara ketepatan log dan kehematan token bucket.
Penempatannya di gerbang atau middleware, dengan keadaan kuota di memori lokal yang murah tetapi melebar atau di cache terdistribusi yang presisi tetapi menambah panggilan jaringan.
Saat komponen pendukung mati, pilihan fail open atau fail closed harus dinyatakan eksplisit, bukan muncul sebagai kebetulan implementasi.

Referensi#

Additional HTTP Status Codes — IETF — Definisi status 429 Too Many Requests untuk penolakan rate limiter.
Token bucket — Wikipedia — Penjelasan algoritma token bucket dan parameternya.
Module ngx_http_limit_req_module — NGINX — Contoh penegakan laju dengan metode leaky bucket pada gerbang HTTP.