Dağıtık rate limiter

Problem

"Şirketin dışa açık bir API platformu var: satıcılar, iş ortakları ve mobil uygulama aynı gateway'den geçiyor. API key, kullanıcı, IP ve endpoint bazında limit koyabilen, 50 gateway pod'unda ve iki bölgede tutarlı çalışan bir rate limiter tasarla. Limit aşıldığında istemci ne zaman tekrar deneyeceğini bilmeli."

Algoritma tarafı (token bucket, sliding window, tek JVM içinde thread-safe implementasyon ve Redis Lua script'i) Kitap Bölüm 19'da live coding sorusu olarak çözüldü. Bu case aynı problemin sistem tarafıdır: limit nerede uygulanır, durum nerede tutulur, 50 pod nasıl aynı sayacı paylaşır, Redis her istekte çağrılabilir mi, Redis çökerse ne olur, kurallar nasıl değişir ve iki bölge nasıl koordine olur.

Mülakatçı bu soruda şunlara bakar: algoritma seçimini gereksinime bağlamak, atomikliği doğru yerde sağlamak, gecikme bütçesini hesaplamak, fail-open/fail-closed kararını bilinçli vermek ve rate limiter'ın kendisinin bir tek hata noktasına dönüşmemesi.

Netleştirme soruları ve varsayımlar

Kapsam dışı: L3/L4 DDoS koruması (bu CDN/edge katmanının işi; uygulama seviyesindeki rate limiter hacimsel bir saldırıyı karşılamaz), faturalandırma için kullanım sayımı.

Kapasite tahmini

Gateway tepe trafiği         : 500.000 istek/s (50 pod, pod başına ~10.000/s)
İstek başına kural            : ortalama 2 (API key + endpoint) -> 1.000.000 kontrol/s

Durum boyutu (token bucket)   : anahtar ~40 B + hash alanları (tokens, ts) + Redis yükü ≈ 150 B
Aktif istemci (son 1 dk)      : 2.000.000
Bellek                        : 2.000.000 x 2 kural x 150 B ≈ 600 MB  -> küçük

Karşılaştırma, sliding window log (dakikada 1.000 limit):
  anahtar başına en fazla 1.000 kayıt, sorted set'te kayıt başına ~60 B -> ~60 KB/anahtar
  2.000.000 anahtar x 60 KB ≈ 120 GB   -> log algoritması bu ölçekte pahalı

Redis yükü                    : 1.000.000 script çağrısı/s
  Lua script'i basit GET/SET'ten pahalıdır; shard başına güvenli tavanı yük testiyle
  ölçeriz. Ölçümde ~60.000 script/s çıktığını varsayalım: 1.000.000 / 60.000 ≈ 17 primary
Gecikme                       : aynı veri merkezinde Redis gidiş-dönüşü ~0,5-1 ms

Teşhis: Bellek sorun değil, çağrı sayısı ve gecikme sorun. Her isteği Redis'e götürmek 17+ shard'lık bir cluster ve her isteğe yaklaşık 1 ms demek. Bu yüzden tasarımın ana fikri: Redis'i doğru yerde kullanmak ve gereksiz çağrıları yerelde elemek.

API

Rate limiter dışarıya açık bir API değil, gateway'in içinde çalışan bir karar noktasıdır. İki arayüzü vardır.

Karar arayüzü (gateway filtresi veya ayrı bir gRPC servisi):

CheckRateLimit(domain="public-api",
               descriptors=[{api_key: "k_123", plan: "gold"}, {route: "POST /orders"}],
               cost=1)
-> { decision: ALLOW | DENY, remaining: 37, retryAfterMs: 0, matchedRule: "gold-orders-create" }

İstemciye dönen cevap:

HTTP/1.1 429 Too Many Requests
Retry-After: 2
RateLimit-Policy: "gold-orders";q=600;w=60
RateLimit: "gold-orders";r=0;t=2
Content-Type: application/problem+json

{ "type": "https://api.ornek.com/problems/rate-limited", "title": "Too Many Requests",
  "status": 429, "detail": "POST /orders için dakikada 600 istek limiti aşıldı." }

• 429 RFC 6585'te tanımlıdır; cevap bir Retry-After içerebilir ve cache'lenmemelidir.
• Retry-After saniye ya da HTTP tarihi alır. Saniye vermek saat farkı sorunlarından kaçınır.
• RateLimit ve RateLimit-Policy başlıkları IETF HTTPAPI çalışma grubunda hâlâ taslak (draft) aşamasındadır; yaygın kullanılan X-RateLimit-Limit/Remaining/Reset başlıkları ise standart değildir. Mülakatta "taslağı takip ederiz, mevcut istemciler için X-RateLimit-*'i de döneriz" demek yeterli.
• Kotası biten istemciye ne zaman tekrar deneyebileceğini söylemek, istemcilerin kör retry fırtınasını önler.

Kural yönetim arayüzü:

PUT /admin/v1/rate-limit-rules/gold-orders-create
{ "match": { "plan": "gold", "route": "POST /orders" },
  "algorithm": "TOKEN_BUCKET", "capacity": 100, "refillPerSecond": 10,
  "mode": "ENFORCE", "failMode": "OPEN" }

refillPerSecond: 10 dakikada 600 isteğe, capacity: 100 anlık 100'lük patlamaya karşılık gelir. mode alanı SHADOW olabilir: kural sadece "reddederdim" diye loglar ve metrik üretir, isteği geçirir.

Veri modeli

Kurallar (PostgreSQL'de kalıcı, gateway'lerde bellekte):

CREATE TABLE rate_limit_rules (
    id                 VARCHAR(64) PRIMARY KEY,
    domain             VARCHAR(64)  NOT NULL,
    match_json         JSONB        NOT NULL,   -- {"plan":"gold","route":"POST /orders"}
    algorithm          VARCHAR(32)  NOT NULL,   -- TOKEN_BUCKET, SLIDING_WINDOW, CONCURRENCY
    capacity           INT          NOT NULL,
    refill_per_second  NUMERIC(12,4) NOT NULL,
    mode               VARCHAR(16)  NOT NULL,   -- ENFORCE, SHADOW, DISABLED
    fail_mode          VARCHAR(16)  NOT NULL,   -- OPEN, CLOSED
    version            BIGINT       NOT NULL,
    updated_at         TIMESTAMPTZ  NOT NULL DEFAULT now()
);

Sayaç durumu (Redis Cluster, sadece geçici durum):

rl:{k_123}:gold-orders-create   -> HASH { tokens: 37.4, ts: 1792743574402 }   PEXPIRE ~ kovanın dolma süresi
rl:{k_123}:gold-global          -> HASH { tokens: ..., ts: ... }
rl:{ip:203.0.113.7}:anon        -> HASH ...

• {k_123} bir hash tag'dir: Redis Cluster sadece süslü parantez içini hash'ler, böylece aynı API key'in bütün kuralları aynı slot'a düşer ve tek bir Lua script'inde atomik olarak kontrol edilebilir.
• Sayaç durumu kalıcı veri değildir. Kaybolursa sonuç, kovanın dolu başlamasıdır; yani istemci birkaç saniyelik ekstra kota kazanır. Bu yüzden Redis'te kalıcılık (AOF) şart değildir.
• Her anahtarın TTL'i kovanın boştan dolmasına yetecek kadardır; işlem görmeyen anahtarlar kendiliğinden silinir.

Yüksek seviye tasarım

flowchart LR
    C[İstemciler] --> EDGE[CDN ve DDoS koruması]
    EDGE --> LB[Load balancer]
    LB --> GW[API gateway pod'ları]
    GW --> LL[Yerel limiter ve kural cache'i]
    GW -->|Lua script| R[(Redis Cluster)]
    GW --> SVC[Arka servisler]
    CFG[Kural yönetim servisi] --> PG[(PostgreSQL kurallar)]
    CFG -->|kural değişikliği yayını| GW
    GW -->|allow, deny, shadow metrikleri| MON[Prometheus ve alarm]

Bir isteğin yolu:

1. Gateway isteği kimlik doğrulamadan geçirir (API key, JWT). Kimliksiz istekler için anahtar IP'dir.
2. Bellekteki kural tablosundan eşleşen kurallar bulunur (kural seti küçüktür, her pod'da tam kopya).
3. Yerel ön limit: Pod kendi belleğinde kaba bir token bucket tutar. Bu, tek bir istemcinin bir pod'u boğmasını ve Redis'e anlamsız trafik gitmesini engeller.
4. Global karar: Redis'te tek bir Lua script çağrısı, istemcinin bütün kurallarını atomik olarak kontrol eder ve düşer.
5. Karar DENY ise 429; ALLOW ise istek arka servise gider. Her iki durumda RateLimit başlıkları eklenir.

Derinlemesine

Algoritma seçimi

Sliding window counter'ın formülü: önceki dakikada 42, şimdiki dakikanın 15. saniyesinde 18 istek varsa tahmini hız 42 x (45/60) + 18 = 49,5. Cloudflare bu yaklaşımı 270.000 farklı kaynaktan gelen 400 milyon istek üzerinde ölçtüğünde isteklerin yalnızca %0,003'ünün yanlışlıkla izin aldığını ya da reddedildiğini raporlamıştır. Yani "yaklaşık" çoğu zaman yeterince doğrudur.

Seçimim: API key ve kullanıcı kotaları için token bucket (Stripe da istek hızı limitleri için token bucket kullandığını anlatır); kimliksiz IP limitleri için sliding window counter; pahalı endpoint'ler için ek bir concurrency limiter. Tek bir algoritmaya kilitlenmek yerine kural başına algoritma seçilebilmesi, mülakatta güçlü bir sinyaldir.

Atomiklik: neden Lua script?

50 pod aynı anahtarı okuyup "37 token var, izin ver" derse ve ikisi de 36 yazarsa iki istek tek token harcamış olur. GET → hesapla → SET üç ayrı komut olduğu sürece bu yarış kaçınılmazdır. Redis bir Lua script'ini atomik çalıştırır: script çalışırken sunucu başka komut işlemez. Bu yüzden okuma, dolum hesabı ve düşme tek script'e konur:

-- KEYS[1] = kova anahtarı   ARGV[1] = capacity   ARGV[2] = refill (token/sn)   ARGV[3] = cost
local t = redis.call('TIME')
local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000)   -- ms
local capacity = tonumber(ARGV[1])
local rate = tonumber(ARGV[2]) / 1000                                   -- token/ms
local cost = tonumber(ARGV[3])

local state = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(state[1]) or capacity
local ts = tonumber(state[2]) or now
tokens = math.min(capacity, tokens + math.max(0, now - ts) * rate)

local allowed, retry_ms = 0, 0
if tokens >= cost then
  tokens = tokens - cost
  allowed = 1
else
  retry_ms = math.ceil((cost - tokens) / rate)
end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', KEYS[1], math.ceil(capacity / rate) + 1000)
return {allowed, math.floor(tokens), retry_ms}

Bu script Redis 7.0 üzerinde denendi: kapasite 10, dolum saniyede 5 iken art arda 12 çağrının ilk 10'u izin aldı, sonraki ikisi yaklaşık 200 ms'lik retry_ms ile reddedildi (saniyede 5 token, yani bir token 200 ms'de dolar); kapasite 50 iken 200 eşzamanlı istemciden tam 50 izin çıktı.

Üç tasarım detayı:

• Saat: Zaman redis.call('TIME') ile Redis'ten alınır. Gateway pod'larının saatleri birkaç milisaniye kayabilir; her pod kendi saatini gönderirse kova ileri geri gider. Redis 7'de script'ler komut etkileriyle replike edildiği için script içinde TIME kullanmak replikayı bozmaz.
• Birden fazla kural: Aynı API key'in kuralları hash tag ile aynı slot'ta olduğu için tek script hepsini kontrol eder: önce hepsinin yeterli token'ı var mı bakar, sonra hepsinden düşer. Böylece "dakika limiti izin verdi, saniye limiti reddetti ama dakika token'ı yine de harcandı" tutarsızlığı oluşmaz.
• Script yükleme: Gateway başlangıçta SCRIPT LOAD ile SHA'yı alır, her istekte EVALSHA gönderir; script metni her istekte ağdan geçmez. NOSCRIPT hatası gelirse (failover sonrası boş replika) script yeniden yüklenir.

Redis'e her istekte gitmek zorunda mıyız?

Her kontrol için bir gidiş-dönüş, 1 milyon çağrı/s ve istek başına yaklaşık 1 ms demek. Üç teknikle azaltılır:

1. Yerel ön limit: Her pod, her anahtar için kaba bir yerel kova tutar (ör. global limitin pod sayısına bölünmüşünün birkaç katı). Saniyede bin istek atan agresif bir istemci, Redis'e gitmeden pod'da reddedilir. Envoy dokümantasyonu da aynı deseni önerir: büyük patlamaları yerel token bucket emer, ince kontrolü global limit yapar.
2. Token kiralama (leasing): Pod, yüksek hacimli bir anahtar için Redis'ten tek seferde 50 token alır ve bunları yerelde harcar. Redis çağrısı 50'de bire iner. Bedeli kesinliktir: kiralanmış ama kullanılmamış token'lar başka pod'da beklerken diğer pod reddedebilir; kira süresi kısa tutulur (ör. 1 saniye) ve kalan iade edilir. Bu teknik yüksek hacimli büyük müşteriler için anlamlıdır; düşük hacimli anahtarlarda gereksizdir.
3. Az sayıda kalıcı bağlantı: Pod'dan Redis'e giden çağrılar her istekte yeni bağlantı açmadan, az sayıda kalıcı bağlantı üzerinden asenkron olarak çoklanır (Lettuce'un varsayılan çalışma biçimi tek bağlantı üzerinde komutları çoklamaktır); bağlantı kurma maliyeti kritik yoldan çıkar.

Mülakatta söylenecek denge: "Varsayılanım her istekte tek bir EVALSHA. Ölçüm Redis'in darboğaz olduğunu gösterirse önce yerel ön limit, sonra sadece büyük anahtarlar için token kiralama eklerim."

Limit nerede uygulanır?

Genel kota gateway'de, iş kuralı limitleri serviste uygulanır. Resilience4j'nin RateLimiter'ı instance içidir; 20 pod'un her biri ayrı sayar, bu yüzden global limit için tek başına yetmez (Kitap Bölüm 14).

Redis erişilemezse: fail-open mi, fail-closed mi?

Rate limiter koruma için vardır; korunan sistemden daha az erişilebilir olmamalıdır.

• Fail-open (varsayılan): Redis çağrısı kısa bir timeout'u (ör. 5 ms) aşar ya da hata dönerse istek geçer, bir metrik artar. Stripe da rate limiter hatalarının ve Redis kesintisinin API'yi bozmaması için hataların her seviyede yakalanıp fail-open olmasını önerir.
• Yerel moda düşmek: Tamamen açmak yerine pod yerel kovaya geçer (global limit / pod sayısı). Kesinlik azalır ama kötüye kullanım yine sınırlanır.
• Fail-closed: Giriş denemesi, SMS doğrulama kodu gönderme, kupon doğrulama gibi kötüye kullanıma açık endpoint'lerde Redis yoksa reddetmek daha güvenlidir.

Redis çağrısı bir circuit breaker arkasındadır: hata oranı artınca devre açılır, gateway Redis'i her istekte beklemeden doğrudan yerel moda geçer. Bu karar kural başına failMode alanıyla ayarlanır.

Çok bölge

İki bölge arasında senkron sayaç paylaşmak, her isteğe bölgeler arası gecikme (on milisaniyeler) eklemek demektir; kabul edilemez. Seçenekler:

• Bölge başına limit: Global limit bölgelere bölünür (trafik oranına göre, ör. %60/%40). Basit ve hızlıdır; bir bölge kapanırsa diğer bölgenin payı yükseltilmelidir.
• Asenkron senkronizasyon: Her bölge yerelde karar verir ve birkaç saniyede bir kullandığı miktarı diğer bölgeye yayınlar; her bölge kendi kovasından diğer bölgenin tüketimini düşer. Birkaç saniyelik pencerede limit aşılabilir.
• İstemciyi tek bölgeye sabitlemek: API key'in "ev bölgesi" vardır; trafik oraya yönlendirilir. Sayaç tek yerdedir ama bölgesel failover'da kova sıfırdan başlar.

Varsayılan seçimim bölge başına limit; sözleşmeye bağlı büyük müşteriler için asenkron senkronizasyon.

Kural değişikliği ve güvenli yayına alma

• Kurallar veritabanında versiyonlu tutulur; gateway'ler değişikliği push ile (ya da birkaç saniyede bir poll ederek) alır ve atomik olarak yeni kural setine geçer.
• Yeni bir kural önce SHADOW modda yayına alınır: kimi reddedeceği metrik ve loglarda görülür, kimse etkilenmez. Stripe da limitleri karanlıkta (dark launch) çalıştırıp engelleyeceği trafiği izlemeyi önerir.
• Kural başına bir kill switch vardır: yanlış bir kural büyük bir müşteriyi kestiğinde deploy beklemeden kapatılır.

İstemci tarafı: retry fırtınasını önlemek

429 alan istemci hemen ve sürekli tekrar denerse limit aşımı kendini besler. İstemci SDK'sı Retry-After'a uyar, yoksa exponential backoff + jitter uygular ve retry sayısını sınırlar (Kitap Bölüm 14). Reddedilen istekler token harcamaz; ama sürekli reddedilen bir istemci IP veya API key bazında daha sert bir "ceza" kuralına girebilir.

Gözlemlenebilirlik

• Kural başına allowed, denied, shadow_denied sayaçları; en çok reddedilen 20 anahtar.
• Redis script gecikmesi (p50/p99), timeout ve fail-open sayısı, circuit breaker durumu.
• Alarm: "fail-open oranı %1'i geçti" (koruma fiilen kapalı), "belirli bir planın red oranı aniden arttı" (yanlış kural ya da istemci hatası).

Darboğazlar, hatalar ve trade-off'lar

Trade-off özeti:

• Kesinlik ve gecikme: Her istekte global kontrol kesin ama 1 ms pahalı; yerel ön limit ve kiralama ucuz ama yaklaşık.
• Koruma ve erişilebilirlik: Fail-open sistemin ayakta kalmasını, fail-closed kötüye kullanımın önlenmesini seçer; endpoint başına karar verilir.
• Global ve bölgesel: Bölgeler arası senkron sayaç yerine birkaç saniyelik aşım kabul edilir.

Üç seviyede cevap

Soru: "50 pod'lu bir gateway'de kullanıcı başına dakikada 600 istek limitini nasıl uygularsın?"

Soru: "Redis çökerse rate limiter ne yapmalı?"

Soru: "Sliding window log mu, token bucket mı? Hangisini seçersin?"

Mülakatçı için

Takip soruları:

• Bir işlem 1 token değil, payload boyutuna göre değişken maliyetli. Script nasıl değişir?
• Concurrency limiter'da istek bittiğinde sayacı azaltmayı unutan bir pod çökerse ne olur? (İpucu: TTL'li kiralama.)
• Limitler müşteri sözleşmesinin parçası ve aşım faturalandırılacak. Hangi kararlar değişir?
• Rate limiter ile load shedding arasındaki fark nedir?

Seviye beklentisi: Mid seviyede Redis + Lua ile atomik token bucket ve 429 beklenir. Senior'dan maliyet hesabı, yerel/global denge, arıza modu, güvenli kural yayını ve çok bölge tartışması beklenir. "Bucket4j kullanırım" deyip mekanizmayı anlatamayan aday zayıftır; kütüphane adı ancak mekanizmadan sonra değer taşır.

Hızlı tekrar

Kaynaklar

• Alex Xu, System Design Interview: An Insider's Guide (Cilt 1): "Design a Rate Limiter" bölümü.
• Redis: INCR komutu ve rate limiter desenleri: INCR + EXPIRE yarışı ve Lua ile çözümü.
• Redis: Scripting with Lua: Script'in atomik çalışması ve anahtarların KEYS olarak verilmesi.
• Redis Cluster specification: Hash slot, hash tag ve asenkron replikasyonda yazma kaybı.
• RFC 6585, Section 4: 429 Too Many Requests: Status kodunun tanımı ve Retry-After.
• MDN: Retry-After: Başlığın sözdizimi ve kullanıldığı status kodları.
• IETF draft: RateLimit header fields for HTTP: RateLimit ve RateLimit-Policy taslağı.
• Cloudflare: How we built rate limiting capable of scaling to millions of domains: Sliding window counter ve doğruluk ölçümü.
• Stripe: Scaling your API with rate limiters: Dört limiter tipi, token bucket, fail-open ve dark launch.
• Envoy: Global rate limiting: Yerel ve global limitin birlikte kullanımı.