@sedatdemirAra

Rate limiting desenleri: token bucket'tan sliding window'a

Bir API'ye saniyede 10.000 istek geldiğinde ilk sorun performans değil, kimin ne kadar kaynak tükettiğini kontrol edememek. Üç yıl önce çalıştığım bir projede kullanıcı başına limit koymamız gerekti; fixed window ile başladık, pencere sınırında burst patlaması yaşadık, token bucket'a geçtik, sonunda sliding window log'a döndük. Bu yazıda o süreçte öğrendiklerimi, her algoritmanın gerçek davranışını ve Go ile Redis üzerinde çalışan implementasyonlarını paylaşıyorum.

Neden rate limiting?

Bir endpoint'e gelen trafiği sınırlamak iki ayrı problemi çözer: kaynak koruma ve adil kullanım. Kaynak koruma, tek bir istemcinin CPU veya veritabanı bağlantılarını tüketmesini engeller. Adil kullanım ise farklı kullanıcılar arasında eşit erişim sağlar. İkisi farklı granülarite gerektirir: IP bazlı sınırlama DDoS benzeri senaryolarda işe yararken, kullanıcı bazlı (API key veya JWT subject) sınırlama ticari kota yönetiminde gerekli olur.

IP bazlı limitin zayıf noktası NAT arkasındaki kullanıcılar. Bir şirket VPN'inin tüm trafiği tek IP'den çıkıyorsa, o IP'nin limiti düşük tutulduğunda meşru kullanıcılar bloklanır. Kullanıcı bazlı limit ise authentication gerektirir; anonim endpoint'lerde uygulanamaz. Pratikte ikisini birlikte kullanmak gerekir: anonim endpoint'lere IP bazlı, authenticated endpoint'lere kullanıcı bazlı.

Fixed window

En basit algoritma. Zamanı sabit pencerelere bölersin (örneğin 1 dakikalık dilimler), her pencerede bir sayaç tutarsın. Sayaç limite ulaşınca istek reddedilir.

package ratelimit

import (
	"sync"
	"time"
)

type FixedWindow struct {
	mu       sync.Mutex
	counts   map[string]int
	limit    int
	window   time.Duration
	currentW int64
}

func NewFixedWindow(limit int, window time.Duration) *FixedWindow {
	return &FixedWindow{
		counts: make(map[string]int),
		limit:  limit,
		window: window,
	}
}

func (fw *FixedWindow) Allow(key string) bool {
	fw.mu.Lock()
	defer fw.mu.Unlock()

	now := time.Now().UnixNano() / int64(fw.window)
	if now != fw.currentW {
		fw.currentW = now
		fw.counts = make(map[string]int)
	}

	if fw.counts[key] >= fw.limit {
		return false
	}
	fw.counts[key]++
	return true
}

Bu kodda pencere geçişinde tüm sayaçlar sıfırlanıyor. Problem şu: pencere sonunda 100 istek, yeni pencere başında 100 istek daha gelirse, 2 saniyelik bir aralıkta 200 istek geçer. Limiti 100/dakika olarak belirlemiş olsan bile gerçekte anlık yük iki katına çıkabilir. Buna "boundary burst" deniyor.

Sliding window log

Her isteğin zaman damgasını bir listeye kaydedip, son N saniye içindeki istek sayısını hesaplarsın. Boundary burst problemi yok çünkü pencere istemciye göre kayar.

Redis ile uygulaması ZSET (sorted set) kullanır:

package ratelimit

import (
	"context"
	"time"

	"github.com/redis/go-redis/v9"
)

type SlidingWindowLog struct {
	rdb    *redis.Client
	limit  int64
	window time.Duration
}

func NewSlidingWindowLog(rdb *redis.Client, limit int64, window time.Duration) *SlidingWindowLog {
	return &SlidingWindowLog{rdb: rdb, limit: limit, window: window}
}

func (sw *SlidingWindowLog) Allow(ctx context.Context, key string) (bool, error) {
	now := time.Now()
	windowStart := now.Add(-sw.window)

	pipe := sw.rdb.Pipeline()
	// Eski kayıtları sil
	pipe.ZRemRangeByScore(ctx, key, "-inf", formatTs(windowStart))
	// Mevcut sayıyı al
	countCmd := pipe.ZCard(ctx, key)
	_, err := pipe.Exec(ctx)
	if err != nil {
		return false, err
	}

	if countCmd.Val() >= sw.limit {
		return false, nil
	}

	// Yeni isteği ekle
	pipe2 := sw.rdb.Pipeline()
	pipe2.ZAdd(ctx, key, redis.Z{Score: float64(now.UnixMicro()), Member: now.UnixMicro()})
	pipe2.Expire(ctx, key, sw.window+time.Second)
	_, err = pipe2.Exec(ctx)
	return err == nil, err
}

func formatTs(t time.Time) string {
	return time.Now().Format("20060102150405") // Sadece score olarak kullanıldığı için
}

Bir düzeltme: yukarıdaki formatTs fonksiyonu hatalı bir yaklaşım, score olarak doğrudan float64(t.UnixMicro()) kullanmak daha doğru. Düzeltilmiş hali:

func (sw *SlidingWindowLog) Allow(ctx context.Context, key string) (bool, error) {
	now := time.Now()
	windowStart := float64(now.Add(-sw.window).UnixMicro())
	nowScore := float64(now.UnixMicro())

	pipe := sw.rdb.Pipeline()
	pipe.ZRemRangeByScore(ctx, key, "-inf", formatFloat(windowStart))
	countCmd := pipe.ZCard(ctx, key)
	_, err := pipe.Exec(ctx)
	if err != nil {
		return false, err
	}

	if countCmd.Val() >= sw.limit {
		return false, nil
	}

	pipe2 := sw.rdb.Pipeline()
	pipe2.ZAdd(ctx, key, redis.Z{Score: nowScore, Member: nowScore})
	pipe2.Expire(ctx, key, sw.window+time.Second)
	_, err = pipe2.Exec(ctx)
	return err == nil, err
}

Slidng window log'un dezavantajı bellek. Her istek bir ZSET entry tüketir. Dakikada 1000 istek limitinde, 1000 kullanıcı için 1 milyon ZSET entry tutuluyor. Yüksek trafikli sistemlerde bu maliyet kabul edilemez hale gelebilir.

Sliding window counter

Fixed window'un bellek verimliliğiyle sliding window log'un doğruluğunu birleştiren bir yaklaşım. İki ardışık fixed window'un sayaçlarını ağırlıklı ortalama ile birleştirir.

Formül: istek_sayısı = önceki_pencere_sayacı * (1 - geçen_süre/pencere_süresi) + mevcut_pencere_sayacı

Bu yöntem Cloudflare'in rate limiting implementasyonunda kullanılıyor (Cloudflare blog, 2017). Bellek kullanımı fixed window ile aynı: kullanıcı başına iki integer. Doğruluk sliding window log kadar kesin değil ama boundary burst problemini büyük ölçüde ortadan kaldırıyor.

Token bucket

Bir kova düşün, içinde belirli sayıda jeton var. Her istek bir jeton tüketir. Kovaya sabit bir hızla jeton eklenir. Kova boşaldığında istekler reddedilir. Burst'e izin verirsin ama uzun vadede ortalama hız sabit kalır.

package ratelimit

import (
	"sync"
	"time"
)

type TokenBucket struct {
	mu         sync.Mutex
	tokens     float64
	max        float64
	refillRate float64 // jeton/saniye
	lastRefill time.Time
}

func NewTokenBucket(max float64, refillRate float64) *TokenBucket {
	return &TokenBucket{
		tokens:     max,
		max:        max,
		refillRate: refillRate,
		lastRefill: time.Now(),
	}
}

func (tb *TokenBucket) Allow() bool {
	tb.mu.Lock()
	defer tb.mu.Unlock()

	now := time.Now()
	elapsed := now.Sub(tb.lastRefill).Seconds()
	tb.tokens += elapsed * tb.refillRate
	if tb.tokens > tb.max {
		tb.tokens = tb.max
	}
	tb.lastRefill = now

	if tb.tokens < 1 {
		return false
	}
	tb.tokens--
	return true
}

Token bucket'ın güçlü yanı burst kontrolü. max değeri anlık burst kapasitesini, refillRate uzun vadeli ortalama hızı belirler. Bir API'ye saniyede 10 istek limiti koyarken, anlık 50 isteğe kadar burst'e izin vermek istiyorsan max=50, refillRate=10 yaparsın. Bu esneklik sliding window'da yok.

AWS API Gateway, Stripe API ve GitHub API token bucket varyantları kullanıyor. HTTP yanıtlarında X-RateLimit-Remaining header'ı kalan jeton sayısını gösterir.

Token bucket Redis ile dağıtık hale getirmek

Tek sunucuda in-memory token bucket yeterli. Birden fazla sunucu varsa Redis'e taşımak gerekir. Lua script ile atomik hale getirmek şart, aksi halde race condition oluşur:

-- token_bucket.lua
local key = KEYS[1]
local max_tokens = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])

local data = redis.call('HMGET', key, 'tokens', 'last_refill')
local tokens = tonumber(data[1]) or max_tokens
local last_refill = tonumber(data[2]) or now

local elapsed = now - last_refill
tokens = math.min(max_tokens, tokens + elapsed * refill_rate)

if tokens < 1 then
    redis.call('HSET', key, 'tokens', tokens, 'last_refill', now)
    redis.call('EXPIRE', key, math.ceil(max_tokens / refill_rate) + 1)
    return 0
end

tokens = tokens - 1
redis.call('HSET', key, 'tokens', tokens, 'last_refill', now)
redis.call('EXPIRE', key, math.ceil(max_tokens / refill_rate) + 1)
return 1

Go tarafından bu scripti çağırmak:

func (tb *DistributedTokenBucket) Allow(ctx context.Context, key string) (bool, error) {
	now := float64(time.Now().UnixMicro()) / 1_000_000.0
	result, err := tb.rdb.Eval(ctx, luaScript, []string{key}, tb.max, tb.refillRate, now).Int()
	if err != nil {
		return false, err
	}
	return result == 1, nil
}

Lua script Redis'te atomik çalışır; MULTI/EXEC'e gerek kalmaz.

Edge ortamlarda rate limiting

Cloudflare Workers veya Vercel Edge Functions gibi ortamlarda rate limiting farklı bir zorluk taşır. Her edge lokasyonu bağımsız çalışır; merkezi bir Redis'e erişmek latency ekler. İki strateji var:

  1. Lokal in-memory sayaç tutup belirli aralıklarla merkeze senkronize etmek. Bu "approximate" rate limiting sağlar. Cloudflare'in kendi rate limiting ürünü bu yaklaşımı kullanır.

  2. Upstash Redis gibi edge-native bir veri deposu kullanmak. Upstash'in @upstash/ratelimit paketi sliding window counter algoritmasını edge'de çalıştırır ve global olarak tek bir Redis'e yazır. Latency ~5-15ms civarında kalır çünkü Upstash'in edge proxy'leri var.

Hono.js gibi edge-first framework'lerle birlikte Upstash rate limiting middleware'i kullanmak yaygın bir desen. Cloudflare Workers ve D1 üzerinde çalışan API'lerde bu kombinasyonu tercih ediyorum.

Edge'de token bucket yerine sliding window counter tercih etmek daha mantıklı. Token bucket'ın state'i (kayan noktalı jeton sayısı ve son refill zamanı) her istekte güncellenmeli; sliding window counter'da ise iki integer yeterli. Daha az Redis round-trip, daha düşük maliyet.

Hangi algoritmayı ne zaman seçmeli?

Fixed window: Prototip veya düşük trafikli internal API'ler. Boundary burst kabul edilebilir durumda. Implementasyonu 20 satır.

Sliding window log: Doğruluğun kritik olduğu ödeme API'leri veya finansal sistemler. Bellek maliyetine katlanılabiliyorsa en kesin sonuç bunu verir.

Sliding window counter: Çoğu production API için doğru denge. Cloudflare, Stripe ve birçok API gateway bu algoritmayı kullanır.

Token bucket: Burst'e kontrollü izin verilmesi gereken durumlar. Kullanıcıya "saniyede 10, burst 50" gibi iki parametreli limit tanımlamak gerektiğinde tek seçenek bu.

HTTP header'ları ve istemci bilgilendirme

Rate limiting uygularken istemciye kalan hakkını bildirmek iyi pratiktir. IETF RFC 6585 429 Too Many Requests status kodunu tanımlar. Yanıt header'ları için henüz kesinleşmiş tek bir standart yok ama yaygın kullanım şu:

X-RateLimit-Limit: 100
X-RateLimit-Remaining: 42
X-RateLimit-Reset: 1719849600
Retry-After: 30

Retry-After header'ı RFC 7231'de tanımlı ve 429 yanıtlarında gönderilmesi önerilir. İstemci bu değere bakarak yeniden deneme zamanlamasını ayarlayabilir.

Güvenlik katmanıyla birlikte düşünmek

Rate limiting tek başına yeterli değil. Bir saldırgan IP adreslerini döndürerek IP bazlı limiti aşabilir. Kimlik doğrulama katmanıyla birlikte kullanıcı bazlı limit eklemek gerekir. Login endpoint'lerinde ise rate limiting'i CSP ve güvenlik header'larıyla birlikte düşünmek doğru yaklaşım.

Bir de şu var: rate limiter'ın kendisi bir darboğaz olmamalı. In-memory çözümler mikrosaniye mertebesinde çalışır ama tek sunucuyla sınırlıdır. Redis çözümleri dağıtık çalışır ama her istekte ağ round-trip ekler. Token bucket için ortalama 2 Redis komutu (HMGET + HSET) gerekir; Lua script ile bunu tek round-trip'e indirmek, yüksek trafikte fark yaratır.

Doğru algoritma seçimi trafiğin şekline bağlı. Burst toleransı gereken yerde token bucket, kesin doğruluk gereken yerde sliding window log, geri kalan her yerde sliding window counter iyi çalışır. Hangisini seçerseniz seçin, önce in-memory prototipini yazıp davranışını test edin; sonra Redis'e taşıyın.