Worked designs — rate limiter + search

1import time23class TokenBucket:4	def __init__(self, rate_per_s: float, burst: float):5		self.rate = rate_per_s6		self.burst = burst7		self.tokens = burst8		self.t = time.monotonic()910	def allow(self, n: float = 1.0) -> bool:11		now = time.monotonic()12		self.tokens = min(self.burst, self.tokens + (now - self.t) * self.rate)13		self.t = now14		if self.tokens >= n:15			self.tokens -= n16			return True17		return False1819# 100 req/s sustained, burst 20020bucket = TokenBucket(100, 200)2122ALGORITHM TRADEOFF23Algorithm              Pros                    Cons                     Pick when24---------------------  ----------------------  -----------------------  ---------------------25Fixed window           trivial, 1 counter      2× boundary burst        low-stakes / debug26Sliding log            exact                   O(n) memory/key          strict low-QPS quotas27Sliding window counter good approx, O(1) mem   edge error               general API limits28Token bucket           burst + sustained       two params               API gateways default29Leaky bucket           smooth egress           adds latency             outbound shaping

1-- Redis token bucket sketch (atomic via Lua in prod)2-- KEYS[1] = rl:{user}3-- refill based on rate; compare tokens; decr4-- Alternative simple fixed window:5INCR rl:user:123:20260715T12006EXPIRE rl:user:123:20260715T1200 607-- if count > LIMIT → 42989# Placement: edge (IP, coarse) → gateway (API key) → service (expensive ops)10# Return headers: Retry-After, X-RateLimit-Remaining when product allows11# Fail open vs fail closed if Redis is down — pick by abuse risk vs availability

1# Tiny inverted index sketch (interview-scale)2from collections import defaultdict34class InvertedIndex:5	def __init__(self):6		self.postings = defaultdict(set)  # term -> doc_ids7		self.docs = {}89	def add(self, doc_id, text):10		self.docs[doc_id] = text11		for term in tokenize(text):12			self.postings[term].add(doc_id)1314	def search(self, query):15		terms = tokenize(query)16		if not terms:17			return []18		sets = [self.postings[t] for t in terms]19		hits = set.intersection(*sets) if sets else set()20		return rank(hits, query, self.docs)2122def tokenize(text):23	return [t for t in text.lower().split() if t]

1RANKING SIGNALS (altitude)2Signal                 Type           Cost        Staleness OK?3---------------------  -------------  ----------  ---------------4BM25 / lexical         static         low         hours5Freshness              time           medium      minutes6Popularity / CTR       behavioral     high        hours7Personalization        behavioral     high        days8Embedding similarity   ML inference   very high   days910# Classic SWE: BM25 + business features. Deep LTR/embeddings → ml-system-design companion.

1# Typeahead capacity → design (heuristic)2peak_qps = 30_0003# trie ~20–50 GB compressed class for large corpora → few boxes + replicas4# budget: ~5ms trie + ~5ms rank + network headroom inside 100ms p995# DECISIONS: in-memory structure, hot-prefix cache >95% hit, nightly rebuild + incremental counts6GET /suggest?q=pre&limit=10 → [{q, score}]

1SEARCH PIPELINE (interview board)2OLTP write → CDC/queue → analyzer → inverted index segments3Query → tokenize → retrieve postings → BM25 → (optional LTR) → hydrate SoT4Typeahead → trie/FST → popularity rank → cache56Freshness SLO example: 99% of docs searchable within 30s of commit7Delete SLO: deleted docs not returned after 60s (hydrate filter sooner)

1RATE LIMIT DECISION LOG2Need                         Pick3---------------------------  ---------------------------4Burst + sustained            token bucket5Simple debug quota           fixed window (know 2× edge)6Exact low-QPS                sliding log7Multi-node hard quota        Redis/atomic or owner shard8Abuse-only soft limit        local approx OK9Export expensive             cost-based tokens1011SEARCH DECISION LOG12Need                         Pick13---------------------------  ---------------------------14Free text retrieval          inverted index derived15Freshness seconds            NRT segments + CDC16Prefix suggest <100ms        in-memory FST/trie + cache17Deletes                      tombstone + hydrate filter18ML re-rank                   second stage / ML track1920Reported anchors: Stripe rate limiters; Cloudflare counting; Slack search hybrid.

1RATE LIMIT PICKER2burst+sustained → token bucket (default API)3simple/debug → fixed window (warn 2x boundary)4exact low QPS → sliding log5multi-node hard quota → Redis Lua / owner shard6abuse soft → local approximate OK7expensive export → cost-based tokens8Redis down → fail open (avail) vs closed (abuse) by risk910PLACEMENT11edge IP/bot → gateway user/key → service expensive op → dependency bulkhead12headers: Retry-After, remaining, reset1314SEARCH PIPELINE15OLTP commit → CDC/queue → analyze → inverted segments → serve16query: tokenize → postings → BM25 → optional LTR → hydrate SoT17freshness SLO e.g. 30s searchable; deletes filtered on hydrate sooner1819TYPEAHEAD2030k QPS peak class → in-memory trie/FST + hot prefix cache21hot prefix 'a' replicated; nightly rebuild + incremental counts22p99 budget <100ms: few ms lookup + rank + network2324REPORTED ANCHORS25Stripe rate limiters; Cloudflare counting at edge;26Slack hybrid search; Lucene/ES segment mental model2728COMPOSE WITH OTHER DESIGNS29feed/chat/marketplace all need limits on expensive reads30search never replaces SoT; never LIKE% primary at scale