İstek sınırlama (rate limiting): token bucket ve kayan pencere

Bir API'ye sınır koymanın en kolay yolu sabit pencere sayacı: dakikanın başında sayacı sıfırla, her istekte bir artır, sınırı aşınca 429 dön. Kolay olduğu kadar da kırılgan. Dakika sınırı 60 ise, istemci 12:00:59'da 60 istek, 12:01:00'da 60 istek daha gönderebilir — iki saniyelik pencerede 120 istek geçer. Sınırı koyduğunuz kaynağın umursadığı şey dakika değil, o iki saniye.

Bu kenar etkisini çözen iki yaygın yaklaşım var: token bucket ve kayan pencere.

Token bucket: kova sabit hızda doluyor

Her anahtar için iki sayı tutuyorsunuz — kovadaki jeton miktarı ve son doldurma zamanı. İstek geldiğinde geçen süre kadar jeton ekliyor, kapasiteyi aşmıyor, bir jeton düşürebiliyorsanız isteği geçiriyorsunuz.

// kapasite: kovanın alabileceği en fazla jeton (ani yığılma payı)
// hiz: saniyede eklenen jeton (sürekli izin verilen oran)
function tuket(durum, simdi, kapasite, hiz) {
  const gecen = (simdi - durum.sonDolum) / 1000;
  const jeton = Math.min(kapasite, durum.jeton + gecen * hiz);
  if (jeton < 1) {
    return { gecti: false, jeton, sonDolum: simdi, bekle: (1 - jeton) / hiz };
  }
  return { gecti: true, jeton: jeton - 1, sonDolum: simdi, bekle: 0 };
}

Buradaki kapasite ve hiz ayrımı, token bucket'ı sabit pencereden ayıran şey. Kapasite ani yığılmaya ne kadar izin vereceğinizi, hiz ise uzun vadede kabul ettiğiniz oranı söylüyor. Kapasiteyi hiz ile eşitlerseniz yığılma payını sıfırlamış olursunuz; kapasiteyi hizin on katı yaparsanız istemci on saniyelik sessizlikten sonra on katı istek gönderebilir.

İki sayı tutmanın avantajı bellekte. İstemci başına iki alan yeterli, istek geçmişi tutulmuyor.

Kayan pencere: iki farklı şey aynı adla anılıyor

Kayan pencere adı altında iki ayrı yöntem var ve maliyetleri birbirinden çok farklı.

Kayan pencere kaydı her isteğin zaman damgasını saklıyor. Sınır kontrolü, pencereden eski damgaları atıp kalanı saymaktan ibaret. Kesin sonuç veriyor, ama bellek maliyeti istek sayısıyla doğru orantılı: dakikada 1000 istek sınırı, aktif istemci başına 1000 kayıt demek.

// zamanlar: artan sıralı zaman damgası dizisi
function kayitlaKontrol(zamanlar, simdi, pencereMs, sinir) {
  const esik = simdi - pencereMs;
  while (zamanlar.length && zamanlar[0] <= esik) zamanlar.shift();
  if (zamanlar.length >= sinir) return false;
  zamanlar.push(simdi);
  return true;
}

Kayan pencere sayacı ise iki sabit pencere sayacını ağırlıklandırıyor. Şu anki pencerenin sayacına, bir önceki pencerenin sayacından pencerede kalan oran kadarını ekliyorsunuz.

function agirlikliSayim(oncekiSayac, simdikiSayac, simdi, pencereMs) {
  const gecen = simdi % pencereMs;          // pencerenin başından beri geçen süre
  const oran = 1 - gecen / pencereMs;        // önceki pencereden kalan pay
  return oncekiSayac * oran + simdikiSayac;
}

Bu yaklaşım isteklerin pencere içinde eşit dağıldığını varsayıyor, dolayısıyla yaklaşık sonuç veriyor. Karşılığında istemci başına iki tamsayı tutuyor. Çoğu HTTP API'si için bu takas makul; kesinliğin para karşılığı olduğu yerlerde (kotalı faturalama gibi) değil.

Dağıtık ortamda okuma ve yazma arasındaki boşluk

Tek süreçte çalışan kod doğru sonuç veriyorsa bu, işlemin bölünemez olmasından. Redis üzerinde aynı mantığı iki komuta bölerseniz — önce GET, sonra SET — iki sunucunun aynı anda okuyup aynı anda geçirmesi mümkün. Token bucket'ta bu, sınırın sunucu sayısı kadar katlanması demek.

Çözüm, kararı tek bir bölünemez adımda vermek. Redis'te Lua betiği bu işi görüyor:

-- KEYS[1]: anahtar, ARGV: simdi, kapasite, hiz
local d = redis.call('HMGET', KEYS[1], 'jeton', 'ts')
local jeton = tonumber(d[1]) or tonumber(ARGV[2])
local ts = tonumber(d[2]) or tonumber(ARGV[1])
local gecen = (tonumber(ARGV[1]) - ts) / 1000
jeton = math.min(tonumber(ARGV[2]), jeton + gecen * tonumber(ARGV[3]))
if jeton < 1 then
  redis.call('HMSET', KEYS[1], 'jeton', jeton, 'ts', ARGV[1])
  return 0
end
redis.call('HMSET', KEYS[1], 'jeton', jeton - 1, 'ts', ARGV[1])
redis.call('EXPIRE', KEYS[1], 3600)
return 1

Betiği her istekte göndermek yerine SCRIPT LOAD ile bir kez yükleyip EVALSHA ile çağırın. EXPIRE satırını atlamayı denemeyin; atarsanız bir daha hiç görülmeyecek istemci anahtarları bellekte birikir.

Zaman damgasını istemciden değil sunucudan almak da önemli. Redis'in TIME komutu betiği belirlenimsiz hale getirdiği için, zamanı ARGV ile dışarıdan geçirmek yaygın yol; bu durumda uygulama sunucularının saatlerinin birbirine yakın olması gerekiyor.

Anahtarı neye göre seçiyorsunuz

Algoritmadan önce cevaplanması gereken soru bu. IP adresine sınır koyarsanız aynı kurumsal ağın arkasındaki yüzlerce kullanıcıyı tek kovaya doldurmuş olursunuz. Kullanıcı kimliğine sınır koyarsanız oturum açmamış istekleri korumamış olursunuz. Pratikte iki katman birden kuruluyor: kimliksiz trafiğe geniş bir IP sınırı, kimlikli trafiğe daha dar bir kullanıcı sınırı.

Ters vekil arkasındaysanız istemci IP'sini X-Forwarded-For başlığından okurken başlığın tamamına güvenmeyin — istemci kendi başlığını ekleyebilir. Kendi vekilinizin yazdığı konuma göre sabit bir konumdan okuyun.

Cevabı nasıl döndüreceksiniz

429 dönerken Retry-After başlığını da yazın; saniye cinsinden bekleme süresi HTTP anlambiliminde tanımlı ve istemci kütüphanelerinin çoğu bunu okuyor. Token bucket'ta bu değer zaten elinizde: bir jetonun dolması için gereken süre.

X-RateLimit-Limit ve X-RateLimit-Remaining gibi başlıklar standart değil, yerleşmiş bir alışkanlık. Yazacaksanız adlarını belgeleyin, sonradan değiştirmeyin.

Hangisi

Kamuya açık bir HTTP API'si koruyorsanız token bucket seçin — bellek maliyeti sabit, ani yığılma payı ayarlanabilir ve istemciye vereceğiniz bekleme süresi hesaptan çıkıyor. Kotanın faturalandırıldığı yerde kayan pencere kaydını tercih edin, bellek maliyetini kabul edin. Kayan pencere sayacı ise ikisinin arasında duruyor: yaklaşık sonuç yetiyorsa sabit pencerenin kenar etkisini ucuza kapatıyor.

Hangisini seçerseniz seçin, kararı tek bir bölünemez adımda verdiğinizden emin olun. Yanlış algoritma sınırı kabaca korur; bölünmüş bir okuma-yazma hiç korumaz.