Pembatasan laju

Pembatasan laju (rate limiting) membatasi jumlah permintaan yang boleh dilayani dari satu sumber dalam rentang waktu tertentu, misalnya 60 permintaan per menit dari satu alamat IP pada sebuah API. Topik ini membangun dua implementasi di atas Redis menggunakan redis-py, yaitu fixed window (jendela tetap) dengan penghitung INCR dan sliding window (jendela bergeser) dengan sorted set. Kedua demo dijalankan dengan urutan waktu yang dibuat tetap, sehingga keputusan diizinkan atau ditolak dapat direproduksi persis. Setelah membaca topik ini, kelemahan lonjakan (burst) pada fixed window serta perbandingan keakuratan terhadap biaya menjadi dasar untuk memilih pola yang sesuai.

Konsep pembatasan laju di Redis#

Pembatasan laju dipindahkan ke Redis karena kuota perlu diputuskan oleh satu pihak yang sama untuk seluruh instance aplikasi. Aplikasi yang berjalan pada beberapa instance server tidak dapat mengandalkan variabel di memorinya masing-masing, karena setiap instance menghitung kuota secara terpisah dan jumlahnya melampaui batas yang ditetapkan. Ketika kuota disimpan di Redis, seluruh instance membaca dan menulis penghitung yang sama, sehingga batas berlaku untuk keseluruhan aplikasi.

Operasi yang digunakan pada topik ini bersifat atomik, yakni penambahan dan pembuangan dilakukan sepenuhnya oleh server tanpa jeda baca lalu tulis di sisi klien, sehingga dua permintaan yang datang bersamaan tetap menghasilkan penghitungan yang benar. Contoh yang digunakan adalah pembatasan permintaan API per alamat IP dengan key ratelimit:ip:10.0.0.5, bentuk yang mengikuti pola penamaan objek:identitas. Agar urutan percobaan pendek dan mudah dihitung ulang, batas demo ditetapkan lima permintaan per jendela 60 detik, sedangkan pola yang sama berlaku untuk batas produksi seperti 60 permintaan per menit.

Fixed window dengan INCR dan EXPIRE#

Fixed window membagi waktu menjadi segmen berdurasi tetap, misalnya 0 sampai 60 detik dan 60 sampai 120 detik, lalu menetapkan satu key penghitung untuk setiap segmen. Nomor jendela dihitung dari pembagian bulat waktu sekarang terhadap durasi jendela, int(now // 60), dan nomor itu menjadi akhiran key, sehingga jendela 0 menyimpan penghitung ratelimit:ip:10.0.0.5:0 dan jendela 1 menyimpan ratelimit:ip:10.0.0.5:1. Setiap permintaan memanggil INCR pada key jendelanya, dan balasannya adalah jumlah permintaan yang tercatat sejauh ini. Permintaan diizinkan bila jumlah itu tidak melebihi batas dan ditolak setelahnya. Penghitung tidak pernah perlu diatur ulang secara manual karena jendela baru menggunakan key baru, sedangkan key jendela lama menghilang sendiri.

Key jendela lama menghilang karena masa hidupnya dipasang dengan EXPIRE tepat ketika INCR mengembalikan 1, artinya hanya pada permintaan pertama jendela tersebut. Durasinya sama dengan lebar jendela, sehingga key terhapus setelah jendelanya berlalu dan memori tidak menumpuk untuk alamat IP yang berhenti mengirim. Waktu sekarang pada demo berikut tidak diambil dari jam, tetapi disisipkan sebagai parameter now agar keputusan setiap permintaan sama pada setiap eksekusi.

import redis

r = redis.Redis(host="127.0.0.1", port=6379, decode_responses=True)
KEY = "ratelimit:ip:10.0.0.5"
BATAS = 5     # maksimum permintaan per jendela
JENDELA = 60  # durasi satu jendela dalam detik


def boleh_permintaan(now):
    # setiap jendela memiliki key penghitung sendiri
    key_jendela = f"{KEY}:{int(now // JENDELA)}"
    jumlah = r.incr(key_jendela)
    # masa hidup dipasang sekali, tepat pada permintaan pertama jendela
    if jumlah == 1:
        r.expire(key_jendela, JENDELA)
    return jumlah <= BATAS, jumlah


# bersihkan key demo agar urutan keputusan selalu sama
r.delete(f"{KEY}:0", f"{KEY}:1")

urutan_waktu = [0.2, 0.4, 0.9, 58.6, 59.8, 59.9, 60.1, 60.4, 60.7, 61.2]
for now in urutan_waktu:
    diizinkan, jumlah = boleh_permintaan(now)
    status = "diizinkan" if diizinkan else "ditolak"
    print(f"t={now:5.1f}  jendela {int(now // JENDELA)}  ke-{jumlah}  {status}")

t=  0.2  jendela 0  ke-1  diizinkan
t=  0.4  jendela 0  ke-2  diizinkan
t=  0.9  jendela 0  ke-3  diizinkan
t= 58.6  jendela 0  ke-4  diizinkan
t= 59.8  jendela 0  ke-5  diizinkan
t= 59.9  jendela 0  ke-6  ditolak
t= 60.1  jendela 1  ke-1  diizinkan
t= 60.4  jendela 1  ke-2  diizinkan
t= 60.7  jendela 1  ke-3  diizinkan
t= 61.2  jendela 1  ke-4  diizinkan

Keluaran memperlihatkan satu jendela penuh yang berakhir dengan penolakan. Lima permintaan pertama mengisi jendela 0 sampai batasnya, dan permintaan ke-6 pada t=59.9 ditolak karena penghitung jendela itu sudah mencapai lima. Pada t=60.1, waktu sekarang melewati batas jendela, sehingga key penghitung berpindah ke ratelimit:ip:10.0.0.5:1 dan penghitungnya mulai dari 1. Empat permintaan berikutnya langsung diizinkan.

Kelemahan lonjakan di batas jendela#

Pengembalian kuota yang serentak adalah sumber kelemahan fixed window. Kuota jendela 0 masih dapat digunakan sampai detik terakhir, sedangkan jendela 1 langsung menyediakan kuota baru, sehingga klien yang menunggu batas jendela dapat menggunakan dua kuota sekaligus dalam waktu yang sangat pendek. Pada keluaran demo, lima permintaan diizinkan dalam rentang t=59.8 sampai t=61.2, yaitu 1,4 detik yang membentang di kedua sisi batas jendela, meskipun batasnya lima permintaan per 60 detik. Dalam kasus terburuk, jumlah permintaan yang lolos di sekitar satu batas jendela mencapai dua kali batas. Diagram berikut membandingkan perilaku kedua pola pada garis waktu yang sama.

Bagian atas diagram menunjukkan penghitung terpisah per jendela dengan titik merah sebagai permintaan yang ditolak. Bagian bawah menunjukkan kotak jendela yang bergerak bersama waktu sekarang.

Sliding window dengan sorted set#

Sliding window menggantikan penghitung per jendela dengan riwayat permintaan yang bergerak mengikuti waktu sekarang. Satu sorted set menyimpan waktu setiap permintaan sebagai skornya, dan anggotanya diberi nama unik seperti req-1 serta req-2 agar permintaan yang beruntun tidak saling menimpa. Pada setiap permintaan baru, entri yang berumur mencapai lebar jendela dibuang dengan ZREMRANGEBYSCORE, kemudian ZCARD menghitung permintaan yang masih hidup dalam jendela. Permintaan diizinkan bila jumlah itu masih di bawah batas, dan ZADD menyimpan waktunya sebagai anggota baru. Masa hidup key tetap dipasang dengan EXPIRE, sehingga riwayat milik alamat IP yang berhenti mengirim terhapus sendiri.

import redis

r = redis.Redis(host="127.0.0.1", port=6379, decode_responses=True)
KEY = "ratelimit:ip:10.0.0.5"
BATAS = 5     # maksimum permintaan dalam jendela bergeser
JENDELA = 60  # lebar jendela dalam detik


def boleh_permintaan(nomor, now):
    # buang permintaan yang berumur mencapai lebar jendela
    r.zremrangebyscore(KEY, "-inf", now - JENDELA)
    jumlah = r.zcard(KEY)
    if jumlah < BATAS:
        r.zadd(KEY, {f"req-{nomor}": now})
        # masa hidup menjaga key milik klien yang berhenti mengirim
        r.expire(KEY, JENDELA)
        return True, jumlah + 1
    return False, jumlah


# bersihkan key demo agar urutan keputusan selalu sama
r.delete(KEY)

urutan_waktu = [0.5, 2.0, 55.0, 58.5, 59.0, 60.2, 62.0]
for nomor, now in enumerate(urutan_waktu, start=1):
    diizinkan, jumlah = boleh_permintaan(nomor, now)
    status = "diizinkan" if diizinkan else "ditolak"
    print(f"t={now:5.1f}  req-{nomor}  aktif {jumlah}  {status}")

t=  0.5  req-1  aktif 1  diizinkan
t=  2.0  req-2  aktif 2  diizinkan
t= 55.0  req-3  aktif 3  diizinkan
t= 58.5  req-4  aktif 4  diizinkan
t= 59.0  req-5  aktif 5  diizinkan
t= 60.2  req-6  aktif 5  ditolak
t= 62.0  req-7  aktif 4  diizinkan

Keluaran menegaskan perbedaannya dengan fixed window. Permintaan ke-6 pada t=60.2 masih ditolak karena lima permintaan sebelumnya seluruhnya berumur di bawah 60 detik, sedangkan fixed window pada demo sebelumnya sudah mengizinkan kembali di t=60.1. Pada t=62.0, permintaan pertama dan kedua berumur 60 detik atau lebih sehingga keduanya dibuang dari sorted set, jumlah aktif turun menjadi tiga, dan permintaan ke-7 diizinkan dengan empat permintaan aktif. Kuota kembali sedikit demi sedikit mengikuti umur setiap permintaan, bukan serentak di batas jendela.

Memilih antara keakuratan dan biaya#

Perbandingan kedua pola menyangkut ketepatan penghitungan di satu sisi dan biaya di sisi lain. Fixed window menyimpan satu penghitung kecil per jendela dan mengeksekusi INCR pada setiap permintaan plus EXPIRE sekali di awal jendela, sehingga biayanya paling murah. Sliding window menyimpan satu anggota untuk setiap permintaan dalam jendela, sehingga memorinya tumbuh mengikuti frekuensi permintaan, dan setiap permintaan mengeksekusi tiga perintah. Tabel berikut merangkum perbedaannya.

Pemilihan juga bergantung pada frekuensi permintaan klien, karena satu anggota tersimpan untuk setiap permintaan dalam jendela. Batas yang longgar dengan klien yang ramai menaikkan biaya memori sliding window. Batas dan pola keduanya perlu ditinjau bersama sejak awal.

Ringkasan#

• Fixed window menyimpan penghitung INCR per jendela pada key berakhiran nomor jendela, dan EXPIRE dipasang sekali pada permintaan pertama sehingga key lama terhapus sendiri.
• Kuota pada fixed window kembali serentak, sehingga klien dapat menggunakan hingga dua kali batas di sekitar batas jendela.
• Sliding window menyimpan waktu setiap permintaan sebagai skor anggota sorted set, membuang entri tua dengan ZREMRANGEBYSCORE, lalu menghitung sisa kuota dengan ZCARD.
• Fixed window paling hemat biaya dan cocok untuk pelindung kasar, sedangkan sliding window lebih akurat dengan memori serta perintah per permintaan yang lebih besar.

Referensi#

• INCR — Redis — Perintah penghitung atomik yang menjadi inti fixed window.
• EXPIRE — Redis — Pemasangan masa hidup key yang menjaga key penghitung terhapus sendiri.
• ZADD — Redis — Penambahan anggota beserta skornya pada sorted set.
• ZREMRANGEBYSCORE — Redis — Pembuangan anggota yang skornya berada di luar rentang, digunakan untuk entri yang lewat jendela.
• ZCARD — Redis — Penghitungan anggota sorted set untuk membaca jumlah permintaan aktif.
• Sorted sets — Redis — Dokumentasi tipe data sorted set beserta pengurangan anggota menurut skor.