04 ยท Rate Limiter Design karo¶
TL;DR
- Rate limiter ek client (user, IP, API key, device) ki ek time window mein requests ki limit lagata hai; extra requests ko HTTP 429 Too Many Requests milta hai.
- Ise server side rakho, aam taur pe middleware / API gateway mein โ client pe kabhi bharosa mat karo.
- Paanch algorithms: token bucket (bursts chalenge, sabse popular), leaky bucket (smooth fixed outflow), fixed window (simple, par window edges pe 2ร burst), sliding log (exact, memory khaata hai), sliding window counter (approximate, sasta โ aksar best choice).
- Counters Redis mein (in-memory,
INCR+EXPIRE), aur race conditions se bachne ke liye check-and-update ko Lua script se atomic banao. - Rules config files mein (limiter cache karta hai); clients ko
X-RateLimit-*/Retry-Afterheaders se quota batao; limiter khud toote toh fail open.
Intuition: metro ka turnstile¶
Bheed waale metro station pe turnstiles ek-ek karke logon ko andar jaane dete hain. Jab platform bhar jaata hai, staff kuch gates band kar deta hai taaki overflow na ho โ log wait karte hain ya doosra raasta lete hain. Andar wale logon ko bahar ki bheed se koi nuksaan nahi hota.
Rate limiter tumhari API ka wahi turnstile hai. Rules ke examples:
- Ek user 1 second mein max 2 posts kar sakta hai.
- Ek IP se din mein max 10 accounts.
- Ek device hafte mein max 5 baar reward claim kar sakta hai.
- Ek phone number pe 10 minute mein max 3 OTP.
Kyun chahiye?¶
- Resource starvation / DoS rokna โ galti se (retry loop mein phansa buggy client) ya jaan-bujh ke. Lagbhag har public API (GitHub, Twitter/X, Google APIs, Stripe) limits lagata hai.
- Cost control โ kam servers; aur sabse important, paid third-party APIs (credit check, SMS, payments, LLM calls) jo har request ka paisa lete hain, unki raksha.
- Overload rokna โ bots aur badtameez users ko filter karo taaki genuine traffic tez rahe.
- Fairness โ multi-tenant system mein ek bhaari tenant baaki sab ko slow na kare.
Step 1 ยท Problem scope karo¶
Clarifying baatcheet
Tum: Hum apni HTTP APIs bacha rahe hain, ya kisi aur ko jaane waali calls limit kar rahe hain? โ Interviewer: Apni public APIs. Tum: Client ki pehchaan kaise โ API key, user, IP? โ I: Sab; alag endpoints alag keys use karte hain. Tum: Traffic roughly kitna? โ I: Peak pe kuch lakh requests per second. Tum: Ek server ya load balancer ke peeche poori fleet? โ I: Badi fleet, do regions mein. Tum: Strict limits, ya thoda overshoot chalega? โ I: Zyada tar endpoints pe thoda overshoot theek; login strict hona chahiye. Tum: Kya clients ko bacha hua quota pata chalna chahiye? โ I: Haan, response mein bhejo.
Requirements
| Functional | Non-functional |
|---|---|
| Configurable key (user, IP, API key, endpoint) pe requests limit karo | Low latency โ requests noticeably slow na hon (< 1โ2 ms extra) |
| Ek saath kai rules (per endpoint, per tier) | Accurate โ zyada excess andar na aaye; genuine users block na hon |
| Throttled clients ko saaf batao (429 + headers) | Memory-efficient โ millions of keys |
| Distributed โ saare API servers / processes mein shared | |
| Fault-tolerant โ limiter ka cache mar jaaye toh bhi API chalti rahe |
Step 2 ยท Rate limiter rehta kahan hai?¶
flowchart LR
subgraph A["Option 1 ยท client side"]
c1[Client with limiter] --> s1[API servers]
end
subgraph B["Option 2 ยท har API server ke andar"]
c2[Client] --> s2["API servers<br/>(code mein limiter)"]
end
subgraph C["Option 3 ยท middleware / API gateway"]
c3[Client] --> g["Rate limiter<br/>middleware / gateway"] --> s3[API servers]
end
- Client side โ bharosemand nahi: koi bhi client requests modify ya forge kar sakta hai, aur aksar client tumhare control mein nahi hota. (SDKs ka khud-throttle karna achhi baat hai, par uspe depend mat karo.)
- API server ke andar โ poora control, par har service khud implement karegi, aur state share na ho toh limits per-process ho jaati hain.
- Middleware / API gateway โ common answer. Gateways (Kong, Envoy, NGINX, AWS API Gateway, Apigee) pehle se auth, TLS termination, IP allow-lists karte hain โ rate limiting yahan naturally fit hoti hai.
Example: limit = 2 req/s. Client ek second mein 3 requests bhejta hai โ middleware pehli do aage bhej deta hai aur teesri ko khud 429 Too Many Requests de deta hai.
Kaise decide karein โ judgement call hai, toh batao kya tumhe kis taraf le jaayega:
- Auth/TLS ke liye pehle se gateway chal raha hai? Toh wahi natural ghar hai โ ek hop, ek config.
- Koi unusual algorithm ya per-request cost weighting chahiye? Khud banana (library ya sidecar) poora control deta hai; off-the-shelf gateways ka menu fixed hota hai.
- Hot-path cost โ check har request pe chalta hai, toh tumhare runtime mein sasta hona chahiye (DC ke andar Redis round trip โ 0.5โ1 ms).
- Team size โ chhoti team ke liye managed gateway aksar sahi hai; apna banana aur chalana asli kaam hai.
Paanch algorithms¶
Theory padhne se pehle sabse popular waale ko mehsoos karo:
1 ยท Token bucket¶
Ek bucket mein max capacity tokens aa sakte hain. Ek refiller fixed refill rate pe tokens daalta hai; bucket full ho toh extra tokens bah jaate hain. Har request ek token leti hai; bucket khaali ho toh request reject.
flowchart LR
R["Refiller<br/>+r tokens/sec"] --> B[("Bucket<br/>capacity = C")]
Q[Request] --> D{token hai?}
B --- D
D -->|haan: 1 lo| OK[API ko bhejo]
D -->|nahi| X[Drop โ 429]
Worked trace โ capacity 5, har 2 second mein 1 token (:02, :04, :06 โฆ pe add hota hai), bucket 10:00:00 pe full:
| Time | Event | Pehle tokens | Decision | Baad mein tokens |
|---|---|---|---|---|
| 10:00:00 | 4 requests (page load) | 5 | โ โ โ โ | 1 |
| 10:00:01 | 2 requests | 1 | โ โ | 0 |
| 10:00:02 | +1 refill, 1 request | 0 โ 1 | โ | 0 |
| 10:00:03 | 1 request | 0 | โ 429 | 0 |
| 10:00:12 | +5 refills (5 pe cap) | 0 โ 5 | โ | 5 |
| 10:00:12 | 5 requests | 5 | โ โ โ โ โ | 0 |
10:00:00 ka burst aaram se nikal gaya (capacity ka yahi matlab hai), par lagatar rate kabhi 2 second mein 1 request se zyada nahi ho sakta.
Asal mein background "refiller" ki zaroorat nahi. tokens aur lastRefillTime store karo, aur har request pe beete time ke hisaab se lazily refill karo:
public final class TokenBucket {
private final long capacity;
private final double refillPerNano; // har nanosecond mein kitne tokens
private double tokens;
private long lastRefill;
public TokenBucket(long capacity, double tokensPerSecond) {
this.capacity = capacity;
this.refillPerNano = tokensPerSecond / 1_000_000_000.0;
this.tokens = capacity; // full se shuru: shuruaati burst allowed
this.lastRefill = System.nanoTime();
}
public synchronized boolean tryAcquire() {
long now = System.nanoTime();
tokens = Math.min(capacity, tokens + (now - lastRefill) * refillPerNano);
lastRefill = now;
if (tokens >= 1) { tokens -= 1; return true; }
return false;
}
}
Parameters: bucket size (max burst) aur refill rate (lagatar rate).
Kitne buckets? Har (key, rule) ka ek:
- Per-endpoint rules: "1 post/sec, 150 friend-adds/din, 5 likes/sec" โ har user ke 3 buckets.
- Per-IP throttling โ har IP ka ek bucket.
- Global cap ("total 10,000 req/s") โ ek shared global bucket.
| โ Fayde | โ Nuksaan |
|---|---|
| Simple, memory-efficient (har key ke 2 numbers) | Do parameters jinhe tune karna tricky ho sakta hai |
| Chhote bursts chalte hain (capacity tak) jabki average rate enforce hota hai | Agar downstream ko smooth load chahiye toh bursts problem hain |
Kaun use karta hai: AWS API Gateway, Stripe (aur bahut saare).
2 ยท Leaky bucket¶
Jaise chhed waali baalti: requests ek fixed size ki FIFO queue mein aati hain; ek worker use fixed outflow rate pe khaali karta hai. Queue full ho toh nayi requests drop.
flowchart LR
Q[Aati hui requests] --> F{queue full?}
F -->|nahi| QU[["FIFO queue (size N)"]]
F -->|haan| X[Drop โ 429]
QU -->|"fixed rate: r req/sec"| P[Processor / API]
Parameters: bucket (queue) size aur outflow rate.
| โ Fayde | โ Nuksaan |
|---|---|
| Memory bounded (queue size) | Burst queue ko purani requests se bhar deta hai; nayi drop hoti hain chahe zyada important hon |
| Ekdum smooth output โ jab downstream ko stable rate chahiye (jaise payment provider jo exactly 100 TPS allow karta hai) | Queueing latency badhti hai; do parameters tune karne hain |
Kaun use karta hai: Shopify ki API (leaky-bucket style). Networking mein traffic shaping ka classic algorithm bhi yahi hai.
Token vs leaky bucket ek line mein
Token bucket average rate limit karta hai aur bursts allow karta hai. Leaky bucket constant output rate enforce karta hai aur bursts ko queue mein sokh leta hai.
3 ยท Fixed window counter¶
Time ko fixed windows mein baant do (jaise har calendar second ya minute). Har window ka ek counter; har request use badhati hai; limit pe pahunche toh agli window shuru hone tak reject.
// Redis-style: key = "rl:{user}:{epochMinute}"
long window = System.currentTimeMillis() / 60_000;
String key = "rl:" + userId + ":" + window;
long count = redis.incr(key);
if (count == 1) redis.expire(key, 60); // window ki pehli hit TTL set karti hai
boolean allowed = count <= LIMIT;
Edge problem. Limit = 100 per minute, windows round minutes pe shuru hoti hain. Ek script 9:14:50 se 9:14:59 ke beech 100 requests bhejti hai, phir 9:15:00 se 9:15:09 ke beech 100 aur. Har window ko exactly 100 dikhti hain โ sab allowed. Par boundary ke aas-paas ke 20 seconds mein 200 requests nikal gayi: per-minute limit ka double.
| โ Fayde | โ Nuksaan |
|---|---|
| Bahut memory-efficient (har key ka 1 counter) | Window edges pe limit ka 2ร tak |
| Samajhna aur banana aasaan | Sabka quota ek hi pal mein reset โ thundering herd |
| Round time units pe reset kuch products ke liye fit hai ("1,000 calls/din") |
4 ยท Sliding window log¶
Edge problem ko exactly fix karta hai. Har key ke liye request timestamps ka log rakho (jaise Redis sorted set, score = timestamp). Har request pe:
now โ windowse purane timestamps hatao.- Nayi request ka timestamp jodo.
- Log size โค limit โ allow; warna reject.
Trace โ limit 10 second mein 3 requests (log har request store karta hai, accept ho ya na ho):
| Aayi | Cleanup + insert ke baad log | Size | Decision |
|---|---|---|---|
| 12:00:01 | [:01] | 1 | โ |
| 12:00:03 | [:01, :03] | 2 | โ |
| 12:00:04 | [:01, :03, :04] | 3 | โ |
| 12:00:07 | [:01, :03, :04, :07] | 4 | โ (timestamp phir bhi store) |
| 12:00:12 | window (12:00:02, 12:00:12] โ :01 hata โ [:03, :04, :07, :12] | 4 | โ |
| 12:00:15 | :03, :04 hate โ [:07, :12, :15] | 3 | โ |
public boolean allow(String key, long nowMs) {
Deque<Long> log = logs.computeIfAbsent(key, k -> new ArrayDeque<>());
synchronized (log) {
while (!log.isEmpty() && log.peekFirst() <= nowMs - WINDOW_MS) log.pollFirst();
log.addLast(nowMs); // is variant mein rejected requests bhi log hoti hain
return log.size() <= LIMIT;
}
}
Step 2 mein chhupa ek design choice
Upar waala variant rejected requests ko bhi log karta hai โ toh jo client lagatar thok raha hai woh blocked hi rehta hai (retry karne ki saza). Bahut implementations sirf accepted requests log karti hain, jisse purani requests expire hote hi client wapas aa sakta hai. Batao tum kaunsa chun rahe ho.
| โ Fayde | โ Nuksaan |
|---|---|
| Exact โ koi bhi rolling window limit cross nahi karti | Memory khaata hai: har request ki ek entry (100 req/min limit ร 1M users = 100M timestamps) |
| Har request pe cleanup ka kaam |
5 ยท Sliding window counter (hybrid)¶
Sirf do fixed-window counters rakho โ current aur previous โ aur rolling count ka estimate lagao yeh maan ke ki previous window ki requests barabar phaili thi:
Example: limit 10/min. Pichle minute mein 8 requests thi; current minute mein ab tak 4. Ek nayi request current minute ke 40% pe aati hai โ rolling window ab bhi pichle minute ke aakhri 60% ko cover karti hai.
estimated = 4 + 8 ร 0.6 = 8.8 โ 8.8 < 10 โ allow (current 5 ho gaya). Usi pal do aur requests aayein toh estimate 10.8
pahunchega โ doosri reject. (Raw estimate compare karo ya round up/down โ policy choice hai; round down thoda zyada lenient hai.)
public synchronized boolean allow(String key, long nowMs) {
long window = nowMs / WINDOW_MS;
double elapsedFraction = (nowMs % WINDOW_MS) / (double) WINDOW_MS;
long curr = counters.getOrDefault(key + ":" + window, 0L);
long prev = counters.getOrDefault(key + ":" + (window - 1), 0L);
double estimated = curr + prev * (1.0 - elapsedFraction);
if (estimated >= LIMIT) return false;
counters.merge(key + ":" + window, 1L, Long::sum); // (Redis mein purani windows TTL se expire)
return true;
}
| โ Fayde | โ Nuksaan |
|---|---|
| Edge spikes smooth karta hai (previous window ka average use karta hai) | Approximate โ maanta hai previous window uniform thi |
| Memory-efficient โ har key ke 2 counters | Jahan har request pe strict limit chahiye wahan nahi chalega |
Practice mein approximation kitna bura hai? Cloudflare ne 40 crore requests pe naapa: sirf 0.003% galti se allow ya rate-limit hui. Isliye yeh aksar best default hai.
Algorithm comparison¶
| Algorithm | Memory / key | Accuracy | Bursts | Kab best |
|---|---|---|---|---|
| Token bucket | O(1) โ tokens + timestamp | Achhi | โ capacity tak | General APIs; bursts theek hain |
| Leaky bucket | O(queue size) | Achhi | โ queue mein smooth | Downstream ko constant rate chahiye |
| Fixed window | O(1) โ 1 counter | โ edges pe 2ร | โ edge bursts | Simple quotas ("1,000/din") |
| Sliding log | O(limit) timestamps | โ exact | โ | Chhoti limits jo exact honi chahiye (OTP, login attempts) |
| Sliding window counter | O(1) โ 2 counters | โ (99.997%) | Smooth | High-volume APIs โ usual best pick |
High-level architecture¶
Saare algorithms ko ek hi primitive chahiye: har key ka tez, shared counter with expiry. Database bahut slow hai (disk). Redis jaisa in-memory store ideal hai: tez hai aur time-based expiry support karta hai.
INCR keyโ counter ko atomically badhao (na ho toh 1 se bana do).EXPIRE key secondsโ timeout ke baad key apne aap delete.
flowchart LR
C[Client] --> M{{Rate limiter<br/>middleware}}
M <-->|"counter lao / badhao"| R[(Redis)]
M -->|limit ke andar| API[API servers]
M -->|limit ke bahar| X["429 Too Many Requests"]
- Client request rate-limiter middleware ko bhejta hai.
- Middleware Redis se sahi bucket ka counter laata hai aur limit check karta hai.
- Limit cross โ reject (429). Andar โ API servers ko forward aur counter increment.
Step 3 ยท Deep dive¶
Rules: kahan rehte hain aur dikhte kaise hain¶
Rules aam taur pe config files (YAML) mein likhe jaate hain aur disk / config service mein store hote hain. Ek illustrative format, Envoy ki open-source rate-limit service ke descriptor-based config jaisa:
domain: public_api
descriptors:
- key: plan
value: free
rate_limit: { unit: minute, requests_per_unit: 60 } # free tier: har API key 60 calls/min
- key: plan
value: pro
rate_limit: { unit: minute, requests_per_unit: 1000 } # paid tier
---
domain: otp
descriptors:
- key: phone_number
rate_limit: { unit: hour, requests_per_unit: 5 } # har phone pe ghante mein max 5 OTP
Workers samay-samay pe disk/config service se rules kheench ke rate limiter ke andar local cache mein rakhte hain, taaki hot path pe rule lookup ka kharcha zero ho.
Clients ko batana ki woh throttle hue¶
HTTP 429 Too Many Requests headers ke saath return karo taaki samajhdaar clients ruk sakein:
| Header | Matlab |
|---|---|
X-RateLimit-Limit |
Client ek window mein kitni calls kar sakta hai |
X-RateLimit-Remaining |
Current window mein kitni bachi hain |
X-RateLimit-Retry-After (ya standard Retry-After) |
Retry se pehle kitne second rukna hai |
(Ek IETF draft inhe RateLimit-Limit, RateLimit-Remaining, RateLimit-Reset ke naam se standardise kar raha hai.)
Throttled requests drop ki ja sakti hain, ya baad mein process karne ke liye enqueue (jaise spike mein throttle hue orders gayab nahi hone chahiye).
Detailed design¶
flowchart TB
subgraph CFG[Rules]
D[(Rules disk /<br/>config service pe)] --> WK[Workers] --> RC[(Rules cache)]
end
C[Client] --> RL{{Rate limiter middleware}}
RC --> RL
RL <--> RD[("Redis<br/>counters + timestamps")]
RL -->|allowed| API[API servers]
RL -->|"rejected: 429 + headers"| C
RL -.->|"option: throttled ko enqueue"| MQ[[Message queue]]
Problem 1 โ race conditions¶
Do API servers ek hi user ki requests ek hi pal mein handle karte hain. Limit = 4, counter = 3.
Server A: GET counter โ 3 Server B: GET counter โ 3
Server A: 3 < 4 โ allow, SET 4 Server B: 3 < 4 โ allow, SET 4
Result: 5 requests allowed, counter bolta hai 4. โ
Read-check-write atomic nahi hai. Fixes:
- Locks โ sahi par slow; har request pe distributed lock latency maar deta hai.
- Atomic operations โ pehle
INCRphir check (INCRnaya value atomically return karta hai). - Redis mein Lua scripts โ Redis script ko atomically chalata hai, toh poora read-modify-write ek step mein.
- Sliding log ke liye
MULTI/Lua block ke andar Redis sorted sets.
Token-bucket check ek atomic Lua script ki tarah:
-- KEYS[1] = bucket key ; ARGV = capacity, refill_per_sec, now_ms, cost
local cap = tonumber(ARGV[1])
local rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local cost = tonumber(ARGV[4])
local b = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(b[1]) or cap
local ts = tonumber(b[2]) or now
tokens = math.min(cap, tokens + (now - ts) / 1000 * rate) -- lazy refill
local allowed = 0
if tokens >= cost then tokens = tokens - cost; allowed = 1 end
redis.call('HMSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', KEYS[1], math.ceil(cap / rate * 1000) * 2)
return { allowed, math.floor(tokens) }
Java se Jedis/Lettuce ke through EVALSHA se call karo (script ek baar load hoti hai aur SHA se refer hoti hai).
Problem 2 โ kai limiters ke beech synchronisation¶
Tum kai rate-limiter instances chalaoge. Stateless web tiers ke saath, ek client ki lagatar requests alag-alag limiter instances pe ja sakti hain. Agar har instance counters local memory mein rakhe, toh client ko apni limit ka Nร mil jaayega.
- Sticky sessions (client ko hamesha same limiter pe bhejo) โ chalta hai par na scalable, na flexible. Bacho.
- Centralised data store (Redis) โ saare instances same counters share karte hain. โ Standard answer.
Problem 3 โ performance¶
- Multi-data-center / edge: door ke users ke liye door waale Redis ki latency zyada hai. Rate limiters ko users ke paas edge locations pe rakho (Cloudflare saikdon edge servers pe limiting chalata hai) aur traffic sabse paas waale pe bhejo.
- DCs ke beech eventual consistency: regions ke across counters async sync karo; sync ke dauraan thoda over-allowance low latency ke liye acceptable trade hai.
- Local pre-check: har instance pe ek chhota local token bucket rakho jo zyada tar decisions le aur samay-samay pe Redis se reconcile kare โ kam network round-trips, thodi inaccuracy ki keemat pe.
Problem 4 โ monitoring¶
Metrics collect karo ye check karne ke liye ki limiter effective hai:
- Algorithm sahi hai? Agar flash-sale ka bursty traffic bahut drop ho raha hai, toh strict window ki jagah token bucket (jo bursts sehta hai) better ho sakta hai.
- Rules sahi hain? Agar bahut saari genuine requests ko 429 mil raha hai, rules zyada strict hain โ dheele karo.
- Track karo: har rule pe allowed vs throttled, p99 added latency, Redis errors, top throttled keys (abuse detection).
Failure mode: fail open ya fail closed?¶
Redis unreachable ho toh requests allow karein (fail open) ya block (fail closed)? Zyada tar APIs ke liye: fail open โ perfect limiting se availability zyada important hai, aur requirement thi ki limiter ki failure system ko na giraye. Security-critical limits (login attempts, OTP sends) ke liye fail closed ya conservative local fallback limiter socho.
Step 4 ยท Wrap up โ extra topics¶
- Hard vs soft limits. Hard: threshold kabhi cross nahi. Soft: thodi der ke liye cross ho sakta hai (bursty par benign traffic ke liye kaam ka).
- Doosri layers pe limiting. Humne Layer-7 (HTTP) limiter banaya. Layer 3 pe IP se
iptables/firewalls se bhi limit kar sakte ho โ sasta, par mota (users ya endpoints nahi dikhte). OSI layers: physical, data link, network (3), transport (4), session, presentation, application (7). - Client best practices limit se bachne ke liye:
- Responses cache karo taaki baar-baar call na karni pade.
- Limits samjho aur thode time mein bursts mat bhejo.
- 429s/errors pakdo aur gracefully recover karo.
- Exponential backoff + jitter ke saath retry karo,
Retry-Afterka respect karte hue.
- Tiered limits โ free vs paid plans ke alag buckets; SaaS mein per-tenant fairness.
Interviewer follow-ups¶
Public REST API ke liye token bucket ya sliding window counter? Justify karo.
General public API ke liye main token bucket lunga agar chhote genuine bursts allow karne hain (page load pe kai calls jaati hain) O(1) memory ke saath, ya sliding window counter agar edge spikes ke bina smooth "N per minute" semantic chahiye. Dono per key O(1) hain aur Redis mein atomically banana aasaan hai. Fixed window (edge bursts) aur sliding log (memory) se bachunga jab tak limit chhoti aur exact na chahiye (login attempts).
Counters waala Redis cluster down ho gaya. Kya hoga?
Limiter ko fail open karna chahiye: error/timeout jaldi pakdo (tight client timeout ~5โ10 ms), request allow karo, metric emit karo aur alert karo. Optionally conservative limits ke saath per-instance in-memory limiter pe fall back karo taaki abusive clients kuch had tak ruke rahein. Redis ko replicas + automatic failover (Sentinel/Cluster) ke saath chalao taaki aisa kam ho.
3 regions ke across har user ka 1 global quota kaise rate-limit karoge?
Options: (1) har user ko ek home region pe route karo jo uska counter own kare (simple, accurate); (2) har region local counter rakhe aur asynchronously sync kare โ sync lag ke dauraan thoda over-limit chalne do; (3) quota ko regions mein baant do (jaise recent traffic share se) aur samay-samay pe rebalance karo. Strict global accuracy ke liye har request pe cross-region round trip chahiye โ bahut slow โ isliye approximate enforcement accept karte hain.
10M users aur har ek ke 3 rules ke counters ko kitni memory chahiye?
Sliding window counter: har (user, rule) ke 2 counters. Key ~40 bytes + value 8 bytes + Redis overhead ~50 bytes โ 100 B per counter โ 10M ร 3 ร 2 ร 100 B = 6 GB โ chhote Redis cluster mein aaram se. Limit 100 waale sliding log ko per key 100 entries tak chahiye โ ~100ร zyada (saikdon GB).
Agar limiter auth se pehle chalta hai toh user ID kahan se aayega?
Ya toh limiting gateway mein authentication ke baad chalao (taaki verified user/API key padh sake), ya layered limits: auth se pehle mota per-IP limit (auth service ko credential stuffing se bachata hai), phir auth ke baad per-user / per-key limits.
Kya rejected requests client ke against count honi chahiye?
Policy choice hai. Unhe count karna (sliding-log variant jaisa) un clients ko saza deta hai jo 429 ignore karke thokte rehte
hain. Na count karna sahi retry karne waale clients ke liye friendly hai. Abuse-sensitive endpoints pe count karo; normal APIs
pe usually nahi โ aur Retry-After publish karo taaki achhe clients wait karein.
Common mistakes¶
Inse bacho
- Limiter sirf client pe lagana.
- Counters ke liye relational database (har request pe disk latency).
- Bina atomicity ke get-then-set โ race conditions extra requests andar aane dete hain.
- Load balancer ke peeche per-instance in-memory counters โ har client ko Nร limit.
- Yeh batana bhool jaana ki limiter khud fail ho toh kya hoga.
- 429 + retry info ki jagah 500/403 return karna.
Practice¶
Practice 1 โ Token bucket trace karo
Capacity 3, refill 1 token/second, t=0 pe full. Requests t = 0, 0, 0, 0, 0.5, 1.2, 1.3, 3.0 pe aati hain. Kaunsi allow hongi?
Solution. t=0: tokens 3 โ allow (2), allow (1), allow (0), reject (0). t=0.5: tokens 0.5 โ reject. t=1.2: tokens 1.2 โ allow (0.2). t=1.3: tokens 0.3 โ reject. t=3.0: tokens 0.3 + 1.7 = 2.0 โ allow (1.0). 8 mein se 5 allowed.
Practice 2 โ Sliding window counter
Limit 100/min. Pichla minute: 84 requests. Current minute: ab tak 36. Ek request current minute ke 25% pe aati hai. Allow ya reject?
Solution. Previous ke saath overlap = 75%. Estimate = 36 + 84 ร 0.75 = 36 + 63 = 99 < 100 โ allow (count 37). Usi pal agli request ka estimate 100 โ reject.
Practice 3 โ OTP limiter design karo
Requirements: har phone pe 10 minute mein max 3 OTP requests, din mein max 10, aur har IP pe ghante mein max 100. Kaunse algorithm(s) aur data structures?
Solution. Chhoti limits jo exact honi chahiye โ 10-minute rule ke liye Redis sorted sets mein sliding window log
(ZREMRANGEBYSCORE, ZADD, ZCARD ek Lua script mein). Daily rule โ phone:yyyy-mm-dd se keyed fixed window counter
(calendar-day semantics theek hai). IP rule โ sliding window counter. Teeno atomically check karo; koi bhi fail ho toh
reject; Redis down ho toh fail closed (SMS mein paisa lagta hai aur abuse ka target hai).
Practice 4 โ Leaky bucket sizing
Downstream payment gateway exactly 50 TPS allow karta hai. Flash sales mein tumhara checkout traffic ~20 seconds ke liye 200 TPS pe peak karta hai. Limiter design karo.
Solution. Gateway ke aage 50/s pe drain hone waala leaky bucket. 200/s ka 20 s spike 4,000 requests laata hai, jinme se spike ke dauraan 1,000 drain hoti hain โ drops se bachne ke liye queue ko ~3,000 slots chahiye, aur aakhri request ~60 s wait karti hai. Synchronous checkout ke liye yeh bahut lamba hai โ order accept karo, payment enqueue karo, "processing" return karo, aur complete hone pe notify karo; ya sale ke aage waiting-room lagao.
Revision checklist¶
- Rate limiting kyun chahiye (DoS, cost, overload, fairness) samjha sakta hoon.
- Client-side, in-server aur gateway placement compare kar sakta hoon.
- Paancho algorithms trace, pros/cons aur kab use karna hai ke saath samjha sakta hoon.
- Fixed-window edge problem numbers se dikha sakta hoon aur sliding-window-counter estimate nikaal sakta hoon.
- Redis, rules cache aur headers waale 429 responses ke saath architecture bana sakta hoon.
- Race condition samjha ke atomic ops / Lua se fix kar sakta hoon.
- Instances aur data centers ke across limiters sync karna, aur fail-open vs fail-closed pata hai.