Live coding · Concurrency · Tasarım

Kullanıcı başına rate limiter

ZorHedef 25 dk

Backend live coding'de sık sorulan klasik

00:00/ 25:00 hedefÖnce kendin çöz; ipuçlarını sırayla aç.

Kupon doğrulama endpoint'i botlar tarafından deneniyor. Mülakatçı: "Her kullanıcı dakikada en fazla 5 istek atabilsin. Önce tek instance için thread-safe bir rate limiter yaz, sonra dağıtık hale nasıl getireceğini konuşalım."

Görevler

  1. boolean tryAcquire(String userId) metodunu yaz: izin verilirse true.
  2. Thread-safe olmalı (aynı kullanıcıdan eşzamanlı istekler).
  3. Zaman kaynağını test edilebilir yap (System.nanoTime'a doğrudan bağımlı olma).
  4. Kısa bir test ya da test senaryosu yaz.
  5. Bellek büyümesini ve çok pod'lu durumu yorum olarak tartış.
Başlangıç kodu
public class RateLimiter {

    public RateLimiter(int maxRequests, Duration window /* , zaman kaynağı? */) {
    }

    public boolean tryAcquire(String userId) {
        return true;
    }
}
İpucu 1

Algoritma seç: fixed window (basit, pencere sınırında 2x patlama), sliding window log (kesin, bellek pahalı), token bucket (yaygın, akıcı).

İpucu 2

Kullanıcı başına state: ConcurrentHashMap<String, Bucket>. Bucket'ı computeIfAbsent ile al, güncellemeyi bucket üzerinde synchronized ile yap (ya da compute içinde atomik güncelle).

İpucu 3

Zamanı LongSupplier nanoClock ya da Clock ile enjekte et; testte sahte saat ilerlet. Boşta kalan kullanıcıların bucket'larını temizle (Caffeine expireAfterAccess). Çok pod: Redis + Lua (INCR + EXPIRE ya da token bucket script).

Referans çözümü göster
Çözüm
public final class TokenBucketRateLimiter {

    private final long capacity;
    private final double refillPerNano;
    private final LongSupplier nanoClock;                 // test edilebilirlik için enjekte
    private final ConcurrentHashMap<String, Bucket> buckets = new ConcurrentHashMap<>();

    public TokenBucketRateLimiter(long capacity, Duration refillPeriod, LongSupplier nanoClock) {
        if (capacity <= 0) throw new IllegalArgumentException("capacity must be positive");
        this.capacity = capacity;
        this.refillPerNano = (double) capacity / refillPeriod.toNanos();
        this.nanoClock = nanoClock;
    }

    public boolean tryAcquire(String key) {
        Bucket bucket = buckets.computeIfAbsent(key, k -> new Bucket(capacity, nanoClock.getAsLong()));
        synchronized (bucket) {                            // sadece bu kullanıcının bucket'ı kilitlenir
            long now = nanoClock.getAsLong();
            bucket.tokens = Math.min(capacity, bucket.tokens + (now - bucket.lastRefillNanos) * refillPerNano);
            bucket.lastRefillNanos = now;
            if (bucket.tokens >= 1) {
                bucket.tokens -= 1;
                return true;
            }
            return false;
        }
    }

    private static final class Bucket {
        private double tokens;
        private long lastRefillNanos;
        Bucket(double tokens, long lastRefillNanos) { this.tokens = tokens; this.lastRefillNanos = lastRefillNanos; }
    }
}

// ===== Test =====
class TokenBucketRateLimiterTest {

    private final AtomicLong now = new AtomicLong();
    private final TokenBucketRateLimiter limiter =
            new TokenBucketRateLimiter(5, Duration.ofMinutes(1), now::get);

    @Test
    void allowsFiveThenRejects() {
        for (int i = 0; i < 5; i++) assertThat(limiter.tryAcquire("u1")).isTrue();
        assertThat(limiter.tryAcquire("u1")).isFalse();
        assertThat(limiter.tryAcquire("u2")).isTrue();      // kullanıcılar bağımsız
    }

    @Test
    void refillsOverTime() {
        for (int i = 0; i < 5; i++) limiter.tryAcquire("u1");
        now.addAndGet(Duration.ofSeconds(12).toNanos());    // 60 sn / 5 = 12 sn'de bir token
        assertThat(limiter.tryAcquire("u1")).isTrue();
        assertThat(limiter.tryAcquire("u1")).isFalse();
    }
}
// Not: Bu çözüm, 16 thread ve 1000 eşzamanlı istekle tam 100 izin verdiği doğrulanarak test edildi.
Açıklama: neden böyle?
AlgoritmaArtıEksi
Fixed window (dakika başına sayaç)Çok basit; Redis'te INCR + EXPIREPencere sınırında 2x patlama (00:59'da 5, 01:00'de 5)
Sliding window logKesinKullanıcı başına zaman damgası listesi; bellek pahalı
Sliding window counterİyi yaklaşık, ucuzYaklaşık değer
Token bucketKısa patlamalara izin verir, ortalama hızı korur; yaygınBiraz daha fazla state
  • Thread-safety: Map'in thread-safe olması yetmez; bucket'ın "oku-hesapla-yaz" adımı da atomik olmalı. Kilit kullanıcı başına olduğu için farklı kullanıcılar birbirini beklemez.
  • Bellek: Map sonsuza kadar büyür; milyonlarca kullanıcıda bellek sızıntısı olur. Caffeine expireAfterAccess(window) ile boşta kalan bucket'lar silinir.
  • Dağıtık sistem: 10 pod'da her pod kendi sayacını tutarsa limit 10 katına çıkar. Redis'te atomik bir Lua script (token bucket) ya da API gateway seviyesinde limit (Nginx, Envoy, Spring Cloud Gateway RedisRateLimiter). Redis erişilemezse fail-open mı fail-closed mı? Kupon için fail-closed, ürün listesi için fail-open.
  • HTTP: Reddedilen istek 429 Too Many Requests + Retry-After header'ı alır.
  • Doğru algoritma (token bucket / sliding window / fixed window) ve doğru limit davranışı
  • Kullanıcı başına state: ConcurrentHashMap + computeIfAbsent
  • Thread-safety: bucket güncellemesi atomik (synchronized / compute / CAS)
  • Zaman kaynağı enjekte edilebilir (Clock / LongSupplier / Ticker)
  • Test: sahte zamanla limit ve yenilenme senaryosu
  • Bellek (boşta kalan key'leri temizleme) ve dağıtık senaryo (Redis + Lua / gateway)
  • Pencere sınırı problemini (fixed window) bir örnekle anlatır mısın?
  • Redis'e her istekte gitmek latency ekliyor. Nasıl azaltırsın? (lokal ön-limit + Redis, batch)
  • Limit kullanıcı yerine IP'ye göre olsaydı hangi problemler çıkar? (NAT, mobil operatörler)