System design

System design

Capacity, trade-offs, and request paths you can defend on a whiteboard.

• Geospatial Indexing

  6 studies
  1. 1.Geospatial Indexing — Cells, Trees & Proximity at ScaleRide-hail, delivery, and maps live or die on nearby search. Index lat/lng with cells (geohash, S2, H3), adaptive trees (quadtree), or MBR trees (R-tree). Always fan out neighbors and filter true distance.
  2. 2.Geohash — Prefix Locality, Encoding, Precision & Edge CasesGeohash turns lat/lng into a base32 string (or interleaved int) whose shared prefixes mean spatial locality — until a cell border. Encode cheaply, pick precision from radius, fan out neighbors, then haversine-filter.
  3. 3.Quadtrees & Space Partitioning — Adaptive Cells, Density & UpdatesQuadtrees split a 2D region into four children when a capacity threshold is hit. Depth follows density — downtown deep, desert shallow. Cheap in-process; awkward as a durable cross-service shard key for moving objects.
  4. 4.R-Trees & R-star — MBRs, Bulk Load & Range/KNN QueriesR-trees index rectangles via nested minimum bounding rectangles. Databases (PostGIS GiST) use them for range, intersect, and kNN. Bulk-load static POIs; do not page-split a moving fleet — keep cells for membership.
  5. 5.S2 & H3 — Hierarchical Hex/Cell IDs (Uber/Lyft-Style Designs)S2 maps the sphere to Hilbert-ish cell IDs; H3 is a hex hierarchy with k-rings. Ride-hail and delivery key membership, shards, and heatmaps by those IDs. Pick hex for uniform rings, S2 for spherical coverings — this is public architecture, not one private paper.
  6. 6.Location Services — Nearby Search, Dispatch Shards & HotspotsIndexes are useless without ingest, cell shards, bounded fan-out, ranking, and airport-scale hotspot splits. Nearby is encode plus k-ring plus haversine; assignment needs CAS on the driver. Cells, not one global tree, carry the fleet.

• Push Notifications

  6 studies
  1. 1.Push Notifications Architecture — APNs, FCM & Event-Driven AlertsMobile push is a distributed system: token registries, APNs/FCM provider APIs, priority and collapse, rich-content extensions, abuse-safe critical alerts, and a funnel from send to engagement. This hub maps the cluster. In-app realtime and durable buses are cousins — cross-link, do not re-teach.
  2. 2.iOS Notification Service Extension — Rich Content, Mute Rules & Time BudgetsNSE runs briefly before iOS presents a remote notification. You get a short wall-clock budget to mutate title/body/attachments or apply mute rules. Timeout or crash fail-open: the user still sees the original payload.
  3. 3.FCM & Multi-Platform Fan-out — Tokens, Topics, Collapse Keys & PriorityFCM is a common fan-out plane for Android (and often a pass-through toward APNs/web). Interviews test token lifecycle, topics vs device multicast, collapse keys, priority, and how your service abstracts APNs vs FCM behind one outbound pipeline.
  4. 4.Critical & Time-Sensitive Alerts — Interruption Levels, Channels & Abuse ControlsCritical and time-sensitive paths bypass Focus/DND in limited, entitlement-gated ways. Interviews look for product judgment: which events deserve interrupt, how Android channels and iOS interruption levels differ, and how you stop abuse that would get the app removed or all notifications disabled.
  5. 5.End-to-End Notification Analytics — Send, Delivery, Receipt & EngagementPush without a funnel is flying blind. Senior interviews expect queued → accepted → delivered → displayed → opened → engaged, plus clock skew, attribution, privacy (no PII in payloads), and tracing notification_id across services. Provider accept is not 'the user saw it'.
  6. 6.Reliability, Dedup & Idempotency — Retries, Provider Receipts & Device StateRetries without idempotency create duplicate banners; provider receipts without token hygiene create silent loss. Persist send intent, keep notification_id stable, classify retryable vs terminal errors, and run a device state machine. Exactly-once bus theory lives in Kafka + idempotency clusters — cross-link, do not re-teach.

• Rate limiting

  6 studies
  1. 1.Rate Limiting: Token Bucket, Leaky Bucket & Sliding WindowFixed-window 2× burst; sliding O(1) counter; token vs leaky bucket; Redis+Lua; 429/Retry-After.
  2. 2.Token Bucket vs Leaky Bucket vs Sliding WindowThree classic limiters: token bucket (burst + sustained rate), leaky bucket (smooth drain), sliding window (fairer than fixed windows). Interviews want tradeoffs, not just names.
  3. 3.Redis + Lua Atomic Rate LimitersDistributed limiters need atomic read-modify-write. Redis + Lua (EVAL/EVALSHA) runs check+debit in one script so concurrent replicas cannot both undercount. Prefer hash tags for Cluster slot affinity; keep scripts short.
  4. 4.Distributed Rate Limits Across GatewaysA limit of 100 req/s per key means nothing if each of N gateway pods enforces it on its own: the real limit becomes N x 100 and changes every time the fleet autoscales. Accurate limits need one shared counter (Redis with an atomic Lua script); fast limits need a local check that costs no network hop. Production systems layer them: the edge drops obvious abuse, a local per-pod bucket rejects clear overage for free, and a global Redis bucket enforces the real quota. When Redis is slow or down, degrade to the local share and alert, instead of either blocking everything or admitting everything.
  5. 5.HTTP 429, RateLimit Headers & Retry-AfterRejecting a request is half the job; the response has to tell the client what to do next. Reply 429 Too Many Requests (RFC 6585) with a Retry-After header (RFC 9110) that says when capacity will exist, and publish the budget on every response so good clients slow down before they hit the wall: the legacy X-RateLimit-Limit, Remaining and Reset triple, or the IETF RateLimit-Policy and RateLimit fields. Clients must honor Retry-After, add random jitter, and use exponential backoff when no header is present; otherwise every throttled client comes back in the same second and the 429s arrive in waves.
  6. 6.Fairness, Quotas & Noisy NeighborsA single global RPS limit protects the servers but not the tenants: whoever sends the most wins the budget, so one batch job can push every other customer into 429s. Fairness needs two layers. Admission control gives each tenant its own quota on each scarce dimension (rate, concurrency, burst, usage per billing period), so a 429 hits only the tenant over its quota. Scheduling then shares the workers among admitted requests with weighted fair queuing (in practice deficit round robin), with a strict priority lane for critical traffic, so a deep queue from one tenant cannot starve the rest.