​

1. Requirements Gathering and Problem Scoping (15-20% of evaluation)

• No hire: Starts designing without understanding the problem. Makes incorrect assumptions that fundamentally change the design.
• Lean no hire: Asks a few surface-level questions but misses critical requirements (scale, consistency, availability).
• Lean hire: Asks good questions, identifies the key requirements, and scopes the problem appropriately.
• Strong hire: Asks questions that reveal non-obvious constraints. Proactively identifies the hardest part of the problem before being prompted.

​

2. High-Level Design (25-30% of evaluation)

• No hire: Cannot produce a coherent end-to-end design. Major components are missing or misconnected.
• Lean no hire: Design works but is overly simplistic or missing critical components (no cache for a read-heavy system, no queue for async processing).
• Lean hire: Solid design with appropriate components. Data flow is clear. Handles the stated requirements.
• Strong hire: Design is elegant and scalable. Components are well-chosen for the access patterns. The candidate identifies the 2-3 critical paths and explains why they drive the architecture.

​

3. Deep Dive and Technical Depth (25-30% of evaluation)

• No hire: Cannot go deep on any component. Lacks understanding of basic data structures, algorithms, or protocols.
• Lean no hire: Can go somewhat deep but makes factual errors or proposes approaches that would not work in practice.
• Lean hire: Demonstrates solid depth on 1-2 components. Makes correct technical choices and can justify them.
• Strong hire: Demonstrates expert-level depth. Brings up non-obvious considerations (race conditions, hot partitions, clock skew). Could convincingly lead implementation of this system.

​

4. Trade-Off Discussion and Decision Quality (15-20% of evaluation)

• No hire: Makes choices without considering alternatives. Cannot articulate downsides of their own design.
• Lean no hire: Mentions alternatives but the comparison is shallow or incorrect.
• Lean hire: Presents clear trade-offs for major decisions. Connects choices to requirements.
• Strong hire: Trade-offs are nuanced and specific. The candidate identifies second-order consequences and explains when they would revisit decisions. Demonstrates the judgment you would want from a tech lead making real architecture choices.

​

5. Communication and Collaboration (10-15% of evaluation)

• No hire: Difficult to follow. Defensive or dismissive of feedback. Cannot adapt when the interviewer redirects.
• Lean no hire: Somewhat organized but misses cues from the interviewer. Does not adjust depth based on interviewer interest.
• Lean hire: Clear, structured communication. Responds well to hints and redirections.
• Strong hire: Exceptional communicator. Treats the interview as a collaborative design session. Makes the interviewer feel like they are working with a great colleague.

• Using LLMs for estimation sanity checks: Tools like ChatGPT and Claude can validate your back-of-envelope calculations in real-time. Paste your estimation and ask “Does this math check out for a system at Twitter’s scale?” The LLM will flag order-of-magnitude errors. This does not replace the skill of estimation — interviewers still want to see you do it — but it accelerates your practice iterations.
• Architecture diagram generation: Copilot and similar tools can generate PlantUML, Mermaid, or ASCII architecture diagrams from natural language descriptions. In practice, this means you can iterate on high-level designs faster during preparation. In the interview itself, you still draw by hand.
• Exploring trade-offs systematically: Ask an LLM “Give me 5 reasons to choose Cassandra over DynamoDB for a chat message store, and 5 reasons to choose the other way.” This forces you to consider angles you might have missed. Then critically evaluate the LLM’s output — it sometimes hallucinates capabilities or misses pricing details.
• The trap to avoid: Using LLMs to memorize answers rather than understand frameworks. An interviewer who asks “Why Cassandra?” and gets a memorized list of bullet points will immediately follow with “What is Cassandra’s compaction strategy and how does it affect write amplification?” If you cannot go deeper than the LLM-generated summary, the interviewer knows.
• In production system design: AI-assisted code generation (Copilot, Cursor) accelerates implementation but does not change architectural decisions. The systems in this chapter still need the same components — AI just helps you write the Lua scripts, the Kafka consumers, and the API endpoints faster. The design thinking remains human.

1. The Estimation Drill: A photo-sharing app has 200M daily active users. Each user uploads 2 photos per day (average 3MB each). How much new storage per day? Per year? What is the upload bandwidth requirement at peak (5x average)? Can a single server handle the upload throughput?
2. The Trade-Off Drill: You are choosing between PostgreSQL and DynamoDB for a user profile service. The access pattern is 95% reads by user ID, 5% writes. You expect 10M users and 50K reads/sec at peak. Argue for PostgreSQL in 3 sentences. Now argue for DynamoDB in 3 sentences. Which would you actually choose, and what is the deciding factor?
3. The Failure Mode Drill: You have a simple web app: Load Balancer, 3 API Servers, and 1 PostgreSQL database. Name every distinct failure scenario (there are at least 6) and the user impact of each. Which failure is the most dangerous and why?

​

Questions You Should Ask the Interviewer

​

Requirements You Should Lock Down

• Given a long URL, generate a unique short URL
• Given a short URL, redirect (HTTP 301/302) to the original
• Optional: custom aliases, expiration, click analytics

• High availability (redirects must not fail)
• Low latency (redirect < 100ms)
• Short URLs should not be guessable (no sequential IDs)

​

Back-of-Envelope Calculation

Assumptions:
  New URLs created per day:     100M
  Read-to-write ratio:          100:1
  Average URL length:           500 bytes
  Short URL length:             7 characters
  Data retention:               5 years

Write (Create):
  100M / 86,400 seconds         ~ 1,160 writes/sec
  Peak (3x):                    ~ 3,500 writes/sec

Read (Redirect):
  100:1 ratio                   ~ 116,000 reads/sec
  Peak (3x):                    ~ 350,000 reads/sec

Storage (5 years):
  100M/day x 365 x 5            = 182.5 billion URLs
  Each record ~ 600 bytes       = ~110 TB total
  (short_url + long_url + metadata)

Short URL keyspace:
  7 chars, Base62 (a-z A-Z 0-9) = 62^7 = 3.5 trillion
  182.5 billion << 3.5 trillion  -> 7 chars is sufficient

Cache (80/20 rule):
  20% of URLs generate 80% of traffic
  Daily read requests: 100M x 100 = 10B
  Cache 20% of daily unique URLs:
  100M x 0.2 x 600 bytes        = ~12 GB (fits in memory)

​

Component Architecture

                           ┌──────────────┐
                           │   Clients    │
                           └──────┬───────┘
                                  │
                           ┌──────▼───────┐
                           │ Load Balancer │
                           └──────┬───────┘
                                  │
                    ┌─────────────┼─────────────┐
                    │             │             │
             ┌──────▼──────┐ ┌───▼───┐ ┌──────▼──────┐
             │  API Server │ │  ...  │ │  API Server │
             └──────┬──────┘ └───┬───┘ └──────┬──────┘
                    │            │             │
                    └────────────┼─────────────┘
                                 │
                  ┌──────────────┼──────────────┐
                  │              │              │
           ┌──────▼──────┐ ┌────▼────┐ ┌──────▼──────┐
           │  Redis Cache │ │   DB   │ │  Analytics  │
           │  (read-thru) │ │(write) │ │   (Kafka)   │
           └─────────────┘ └────┬────┘ └─────────────┘
                                │
                         ┌──────▼──────┐
                         │ DB Read     │
                         │ Replicas    │
                         └─────────────┘

​

API Design

POST /api/v1/urls
  Body: { "long_url": "https://...", "custom_alias": "my-brand", "ttl": 3600 }
  Response: { "short_url": "https://short.ly/aB3x7Kp" }

GET /{short_url_key}
  Response: HTTP 302 Redirect → Location: https://original-long-url.com

GET /api/v1/urls/{short_url_key}/stats
  Response: { "clicks": 10432, "created_at": "...", "last_accessed": "..." }

​

The Core Problem: How to Generate a Unique 7-Character Key?

hash("https://example.com/very-long-path")
  → MD5: "a3f2b8c9d1e4..."
  → Base62 first 7: "aB3x7Kp"
  → Collision? Append counter: hash("https://...&1") → retry

counter = 1000000
Base62(1000000) = "4c92"  → pad to 7 chars: "004c92x"

KGS DB:
┌────────────┬────────┐
│    key     │  used  │
├────────────┼────────┤
│  aB3x7Kp  │ false  │
│  Zk9mW2q  │ true   │
│  ...       │  ...   │
└────────────┴────────┘

App Server starts → fetches 1000 keys from KGS → uses from local cache
When local cache runs low → fetch another batch

​

Database Choice

​

Caching Strategy

• Cache-aside with Redis: Check cache first, on miss read from DB and populate cache
• TTL: Set cache TTL to match URL expiration (or 24 hours for non-expiring URLs)
• Eviction: LRU — frequently accessed URLs stay hot, long-tail URLs get evicted
• Cache size: ~12 GB for 20% of daily URLs (fits a single Redis instance)

​

Bitly’s Architecture

• Key generation: Bitly uses a counter-based approach with Base62 encoding, allocating counter ranges to application servers to avoid coordination overhead. Each server gets a block of IDs and increments locally, only requesting a new block when the current one is exhausted.
• Storage: They migrated from MySQL to a distributed data store. Their link mapping data is sharded by the hash of the short URL key, ensuring even distribution across nodes.
• Caching: Bitly uses a multi-layer caching strategy. Popular links (the top 1-2% by click volume) are cached in memory on the application servers themselves. A shared Redis layer handles the next tier. The database is the fallback of last resort. Given the extreme read-to-write ratio, cache hit rates exceed 99%.
• Analytics pipeline: Click data flows through Kafka into a real-time processing pipeline. They decouple the redirect path (which must be sub-100ms) from analytics aggregation entirely. Click events are enriched asynchronously with geo, device, and referrer data.
• Global presence: Bitly uses Anycast DNS and edge servers in multiple regions to ensure redirects are fast worldwide. A redirect request in Tokyo does not need to round-trip to a US data center.

​

TinyURL’s Original Design

• Single MySQL database: All short-to-long URL mappings lived in a single MySQL instance with a B-tree index on the short key. For years, this was sufficient because the total dataset was small enough to fit in RAM.
• Sequential IDs: TinyURL used auto-incrementing MySQL IDs converted to a short alphanumeric string. This is the simplest possible approach and works until you need non-guessable URLs or multi-datacenter writes.
• No analytics: The original TinyURL had no click tracking at all. This dramatically simplified the architecture — a redirect was a single database lookup and an HTTP 301 response.
• Lesson: TinyURL proves that the simplest possible design can serve millions of users if the access pattern is simple enough (key-value lookup). The complexity in Bitly’s architecture exists because of analytics, custom domains, enterprise features, and global scale — not because URL shortening itself is hard.

• The system does not go down with it — it degrades gracefully. All reads fall through to the database read replicas. Latency increases from ~5ms (cache hit) to ~20-50ms (DB read). Users notice nothing.
• Risk: if cache is cold and all traffic suddenly hits the DB, you get a thundering herd. Mitigation: implement request coalescing (if 1,000 requests for the same key arrive simultaneously, only one hits the DB and the rest wait for its result) and bring the cache back incrementally using a warm-up script that pre-loads the top 20% of URLs by access frequency.

• Reads continue from replicas (redirects keep working). Writes (new URL creation) fail. This is acceptable for minutes — redirects are 100x more important than creates.
• Promote a read replica to primary (automated failover via PostgreSQL Patroni or DynamoDB’s built-in multi-AZ). Typical recovery: 15-30 seconds with automated failover.

• Application servers have locally cached batches of pre-generated keys (1,000+ keys each). They continue creating URLs from their local batch. You have minutes to hours before any server exhausts its cache, depending on batch size.
• If KGS stays down and local caches deplete, fall back to MD5 hash generation as a degraded-mode strategy.

• The bloom filter catches it before the DB write. Retry with a different key. If the bloom filter itself has a false positive, the DB’s unique constraint catches it. Two layers of defense, not one.

• Anycast DNS routes traffic to the nearest healthy data center. Cross-region replication ensures the URL database is available in multiple regions. Users in the affected region experience a brief DNS TTL delay (seconds) before traffic re-routes.

• DynamoDB and ElastiCache are gone. You are on a single EC2 instance (or a small VPS). The KGS becomes an in-process counter with local file persistence. Redis becomes an in-memory LRU cache within the application process. The database becomes SQLite or a single PostgreSQL instance. This forces you to think about what the essential architecture is versus what is scaling convenience. The answer: a single Go or Rust binary with an embedded cache and SQLite can handle 10K redirects/sec on a $20/month VPS.

• Now you need a user_id foreign key on every URL record and every click event. The analytics pipeline must support targeted deletion (not just append-only logs). Kafka retention policies are no longer sufficient — you need to be able to purge specific events from S3/Athena. This fundamentally changes the analytics storage from an immutable log to a mutable store, which means you might prefer a database-backed analytics pipeline over Kafka-to-S3.

• The entire CDN, Anycast DNS, and global replication discussion becomes irrelevant. A single PostgreSQL table behind an Nginx reverse proxy is the correct architecture. If you propose DynamoDB and CloudFront for 500 internal users, you have failed the judgment test. The interviewer is testing whether you can right-size, not whether you know the big architecture.

• Now you need authentication on the create endpoint, user attribution on click events, and an immutable audit log (append-only table or a service like AWS QLDB). The click event is no longer just analytics — it is a compliance record. This changes the priority: analytics can be eventually consistent, but the audit log must be durable and strongly consistent.

• Databases and storage — The NoSQL vs SQL decision, sharding strategies, and partition key design are covered in depth in APIs and Databases. Understanding when key-value access patterns favor NoSQL is critical here. For a deeper dive into DynamoDB’s partition key mechanics, single-table design, and when to choose DynamoDB over Cassandra, see Database Deep Dives.
• Caching — The Redis cache-aside pattern, eviction policies (LRU), and cache warming strategies are explored in Caching and Observability.
• Performance and scalability — Read replicas, horizontal scaling, and CDN usage for global latency reduction are covered in Performance and Scalability.
• Networking — HTTP redirect semantics (301 vs 302), DNS resolution, and Anycast routing are foundational networking concepts covered in Networking and Deployment.
• Reliability — Fail-safe patterns, graceful degradation, and the analytics buffering pattern connect to Reliability Principles.
• Cloud service patterns — The mapping of URL shortener components to AWS services (DynamoDB, ElastiCache, CloudFront, Kinesis) and cost optimization strategies are explored in Cloud Service Patterns. Understanding when to use DynamoDB on-demand vs provisioned capacity is a practical skill covered there.

​

Questions You Should Ask the Interviewer

​

Requirements You Should Lock Down

• Rate limit requests based on configurable rules (user ID, IP, API key)
• Support multiple rate limit tiers (free: 10 req/min, pro: 1000 req/min)
• Return proper HTTP 429 with Retry-After header when limit is exceeded
• Rate limit rules can be updated without redeployment

• Very low latency (added overhead < 1ms per request)
• Must work across distributed servers (shared state)
• Highly available — if the rate limiter fails, requests should pass through (fail-open)

​

Back-of-Envelope Calculation

Assumptions:
  Active users:                 10M
  Average requests per user:    500/day
  Total requests/day:           5 billion
  Peak QPS:                     ~175,000 req/sec (3x average)

Rate limiter overhead:
  Each check = 1 Redis round-trip  ~ 0.5ms
  At 175K QPS:                     ~ 175K Redis ops/sec
  Redis single instance handles:   ~ 100K ops/sec
  → Need 2-3 Redis instances (or Redis Cluster)

Storage per user (sliding window):
  Key: "user:12345:api:/search"     ~ 50 bytes
  Value: sorted set of timestamps   ~ 200 bytes (for 100 entries)
  Total per user (10 endpoints):    ~ 2.5 KB
  10M users:                        ~ 25 GB
  → Fits in Redis cluster

​

Where to Place the Rate Limiter

Option A: API Gateway (Recommended for most cases)
  Client → API Gateway [Rate Limiter] → App Servers

Option B: Middleware in Application
  Client → App Server → [Rate Limiter Middleware] → Handler

Option C: Sidecar (Service Mesh)
  Client → Envoy Proxy [Rate Limit] → App Server

​

Component Architecture

  Client Request
       │
       ▼
  ┌──────────────┐     ┌─────────────────┐
  │ API Gateway  │────▶│  Rules Engine    │
  │ (rate check) │     │  (config store)  │
  └──────┬───────┘     └─────────────────┘
         │
    ┌────▼────┐
    │  Redis  │  ← Centralized rate limit state
    │ Cluster │
    └────┬────┘
         │
    Pass │ Reject
    ┌────▼────┐  ┌─────────────────┐
    │  App    │  │  HTTP 429       │
    │ Servers │  │  Retry-After: X │
    └─────────┘  └─────────────────┘

​

Rate Limit Headers (RFC 6585)

HTTP/1.1 429 Too Many Requests
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1672531200
Retry-After: 30

​

Comparing Four Rate Limiting Algorithms

Window: 12:00:00 - 12:01:00 → counter = 87/100
Window: 12:01:00 - 12:02:00 → counter = 0/100 (reset)

Redis ZSET: user:123 → [12:00:01, 12:00:05, 12:00:33, ...]
New request at 12:01:10:
  Remove all timestamps < 12:00:10
  Count remaining: 45
  If 45 < 100 → ALLOW, add 12:01:10

Previous window (12:00-12:01): 84 requests
Current window  (12:01-12:02): 36 requests
Current time:   12:01:15 → 25% into current window

Weighted count = 84 * 0.75 + 36 = 99
Limit = 100 → ALLOW (barely)

Bucket capacity: 100 tokens
Refill rate:     100 tokens/minute
Current tokens:  23

Request arrives → 23 > 0 → ALLOW, tokens = 22

​

Distributed Rate Limiting: The Hard Part

-- Atomic rate limit check in Redis
local key = KEYS[1]
local limit = tonumber(ARGV[1])
local window = tonumber(ARGV[2])

local current = redis.call('INCR', key)
if current == 1 then
    redis.call('EXPIRE', key, window)
end

if current > limit then
    return 0  -- REJECTED
else
    return 1  -- ALLOWED
end

​

Cloudflare’s Rate Limiting at Scale

• Edge-first enforcement: Rate limiting happens at Cloudflare’s edge servers, not at a centralized service. Each data center runs its own rate limiting logic. This is critical because sending every request to a central rate limiter would add unacceptable latency and create a single point of failure.
• Sliding window counters: Cloudflare uses a sliding window approach similar to Algorithm 3 above. They chose this because it provides good accuracy with minimal memory per client, which matters when you are tracking millions of unique IPs and API keys simultaneously.
• Approximate counting across data centers: Since rate limiting is distributed, a user hitting multiple Cloudflare data centers (due to Anycast routing) could theoretically exceed their global limit. Cloudflare handles this with periodic synchronization between edge nodes — they trade perfect accuracy for speed. The result is rate limits that are “approximately correct” within a small margin, which is acceptable for virtually all use cases.
• Configurable actions: When a rate limit is exceeded, Cloudflare supports multiple responses: block (HTTP 429), challenge (show a CAPTCHA), JS challenge (verify browser), or simulate (log only, for testing rules before enforcement). This flexibility is a great interview detail to mention when discussing rate limiter behavior.
• IP reputation scoring: Beyond simple rate counting, Cloudflare layers in threat intelligence. An IP with a known bad reputation gets a lower effective rate limit. This hybrid approach (rate limiting + reputation) is more effective than either technique alone.

​

Stripe’s Rate Limiting API

• Token bucket algorithm: Stripe uses a token bucket implementation for their API rate limits. Each API key gets a bucket with a defined capacity (e.g., 100 requests per second for live mode). Tokens refill at a steady rate. This allows short bursts (useful when a merchant processes a batch of charges) while enforcing a sustained rate limit.
• Tiered limits by endpoint: Not all API endpoints have the same rate limit. Creating a payment intent might be limited to 100/sec, while listing events could allow 1000/sec. Stripe separates read-heavy endpoints from write-heavy ones because the cost to Stripe’s backend is different.
• Graceful headers: Stripe returns RateLimit-Limit, RateLimit-Remaining, and RateLimit-Reset headers on every response (not just 429s). This allows well-behaved clients to self-throttle before hitting the limit. They also return a Retry-After header on 429 responses with a specific number of seconds to wait.
• Idempotency keys for retries: Stripe’s rate limiting is designed to work hand-in-hand with their idempotency key system. When a client gets rate-limited and retries, the idempotency key ensures the retry does not create a duplicate charge. This is a subtle but important integration point between rate limiting and application semantics.
• Load shedding at scale: When Stripe’s systems are under extreme load, they implement progressive load shedding — first throttling lower-priority traffic (webhooks, list operations) before restricting payment-critical paths. This priority-based approach is more sophisticated than a flat rate limit and is worth mentioning in interviews when discussing production-grade systems.

• This is why you chose fail-open. All requests pass through without rate limiting. Your backend services are temporarily unprotected. Mitigation: have a secondary, local in-memory rate limiter on each API server as a fallback. It will not be globally consistent, but it provides per-server protection. A server-local token bucket with 10x the normal per-user limit acts as a safety net.
• Alert immediately. Redis recovery is your top priority.

• If using Redis Cluster, keys on the failed shard become inaccessible. Some users are rate-limited correctly; others are not. This is worse than a total failure because the inconsistency is silent.
• Mitigation: monitor rate limiter health with a canary key that you check every second. If the canary read fails, switch the entire rate limiter to local-only mode until Redis is healthy.

• The rate limiter cannot check state. With fail-open, requests pass through. With fail-closed, all requests are rejected (an outage).
• This is the core argument for fail-open: a network partition should not become a denial-of-service against your own users.

• Fixed window counters may reset at different times on different servers, allowing a user to briefly exceed their limit by hitting different servers at the window boundary.
• Mitigation: use Redis server time (TIME command) for all timestamp comparisons, not the application server’s clock. The sliding window counter algorithm is also more tolerant of small clock differences because it interpolates between windows.

• Redis processes commands sequentially (single-threaded for commands). At extreme rates from a single user, the Lua script executes fast (~0.1ms) but the network round-trip dominates. This is not a real concern in practice — Redis handles 100K+ ops/sec, which means a single user would need to send 100K+ req/sec to cause contention.
• If this is a DDoS scenario, you need upstream protection (CDN-level blocking, IP reputation) before the request ever reaches your rate limiter.

• Static rules files are no longer sufficient. You need a rules service that is queried per request or cached with aggressive invalidation. The rate limit check becomes: look up tenant_id to tier, look up tier to limits, apply the algorithm. A tier change mid-window means you either apply the new limit immediately (possibly rate-limiting a user who just upgraded) or finish the current window at the old limit. The product decision here has architectural implications — discuss both options.

• This eliminates synchronous Redis calls on every request. You need a local in-memory rate limiter on each server, periodically synced with a global state. Each server maintains its own sliding window counter and reports to a central aggregator every 1-5 seconds. You accept ~5% accuracy loss for zero added latency on allowed requests. Only rejected requests see the overhead (the 429 response). This is the Cloudflare edge model.

• The rate limit key now includes geography: user:123:US:/api/search. You need to resolve the user’s geography at the edge (GeoIP lookup from CloudFront or Cloudflare) and pass it to the limiter. The rules engine becomes a matrix: (user_tier, region, endpoint) -> limit. This is a real-world pattern — many API providers have geography-specific rate limits for regulatory reasons.

• You cannot use Redis for every rate limit check at this price. Options: move to a local in-memory limiter with periodic Redis sync (reduces Redis ops by 90%), use DynamoDB on-demand for rate limit state (cheaper for bursty workloads), or use AWS API Gateway’s built-in rate limiting and eliminate the custom limiter entirely for most endpoints. The cost constraint forces you to evaluate the buy-vs-build decision with real numbers.

• APIs and HTTP — Rate limit headers (X-RateLimit-*, Retry-After), HTTP 429 semantics, and API versioning are covered in APIs and Databases.
• Networking — Understanding TCP connection management, load balancing algorithms, and how API gateways work is foundational. See Networking and Deployment.
• Caching — Redis as both a cache and a data structure server, TTL management, and eviction policies are covered in Caching and Observability.
• Concurrency and distributed state — Race conditions, atomic operations (Lua scripts), distributed locking, and clock synchronization are covered in Messaging, Concurrency, and State. The clock skew discussion in this problem connects directly to the logical clocks and vector clocks covered in Distributed Systems Theory — understanding why wall-clock time is unreliable in distributed systems is essential for designing correct rate limiting across multiple servers.
• Reliability — Fail-open vs fail-closed, circuit breakers, and graceful degradation patterns connect to Reliability Principles.
• Security — Rate limiting as a defense against DDoS and brute-force attacks connects to Auth and Security.
• Cloud service patterns — AWS API Gateway’s built-in throttling, WAF rate-based rules, and the decision framework for managed vs custom rate limiting are explored in Cloud Service Patterns.

​

Questions You Should Ask the Interviewer

​

Requirements You Should Lock Down

• 1-to-1 messaging with delivery confirmation
• Group chat (up to 500 members)
• Online/offline presence indicators
• Message history (persistent, searchable)
• Push notifications for offline users

• Real-time delivery (< 200ms for online users)
• Message ordering guarantees (per-conversation)
• 99.99% message delivery (no lost messages)
• Support 50M concurrent connections

​

Back-of-Envelope Calculation

Assumptions:
  Daily Active Users (DAU):     50M
  Concurrent connections:       10% of DAU = 5M
  Messages per user per day:    40
  Total messages/day:           2 billion
  Average message size:         200 bytes
  Group chats per user:         5 (average 20 members)

Throughput:
  2B messages / 86,400 sec      ~ 23,000 messages/sec
  Peak (5x):                    ~ 115,000 messages/sec

WebSocket connections:
  5M concurrent connections
  Each connection ~ 10 KB memory
  Per server (10K connections): ~ 100 MB
  Servers needed:               5M / 10K = 500 WebSocket servers

Storage (1 year):
  2B messages/day x 365 x 200 bytes = ~146 TB/year
  With indexes and metadata:          ~200 TB/year

Presence (heartbeat):
  5M users sending heartbeat every 30 sec
  = 166K heartbeat events/sec

​

Component Architecture

 ┌──────────┐  ┌──────────┐  ┌──────────┐
 │ Client A │  │ Client B │  │ Client C │
 └────┬─────┘  └────┬─────┘  └────┬─────┘
      │  WebSocket   │             │
      └──────────────┼─────────────┘
                     │
              ┌──────▼──────┐
              │   Gateway   │  ← Connection routing + auth
              │   (HAProxy) │
              └──────┬──────┘
                     │
      ┌──────────────┼──────────────┐
      │              │              │
 ┌────▼────┐   ┌────▼────┐   ┌────▼────┐
 │  Chat   │   │  Chat   │   │  Chat   │
 │Server 1 │   │Server 2 │   │Server 3 │   ← Hold WebSocket connections
 └────┬────┘   └────┬────┘   └────┬────┘
      │              │              │
      └──────────────┼──────────────┘
                     │
      ┌──────────────┼──────────────┐
      │              │              │
 ┌────▼────┐   ┌────▼────┐   ┌────▼────┐
 │  Redis  │   │ Message │   │ Presence │
 │ Pub/Sub │   │  Store  │   │ Service  │
 └─────────┘   └─────────┘   └──────────┘

​

Message Flow (1-to-1)

1. User A sends message via WebSocket to Chat Server 1
2. Chat Server 1:
   a. Persists message to Message Store (Cassandra)
   b. Looks up which Chat Server holds User B's connection
   c. Publishes message to Redis Pub/Sub channel for User B
3. Chat Server 2 (holding User B's connection):
   a. Receives message from Redis Pub/Sub
   b. Pushes message to User B via WebSocket
4. If User B is offline:
   a. Message is stored in an "undelivered" queue
   b. Push notification sent via APNS/FCM

​

Deep Dive 1: WebSocket vs Long-Polling

​

Deep Dive 2: Message Storage and Partitioning

Table: messages
┌──────────────────┬───────────────┬────────────┬──────────┬─────────┐
│ conversation_id  │  message_id   │  sender_id │   body   │  ts     │
│  (partition key) │ (clustering)  │            │          │         │
├──────────────────┼───────────────┼────────────┼──────────┼─────────┤
│  conv_abc123     │  msg_001      │  user_A    │  "Hey!"  │  17...  │
│  conv_abc123     │  msg_002      │  user_B    │  "Hi!"   │  17...  │
└──────────────────┴───────────────┴────────────┴──────────┴─────────┘

Partition key: conversation_id
  → All messages for a conversation are on the same node
  → Efficient range query: "Get last 50 messages for conversation X"

Clustering key: message_id (time-based UUID / Snowflake ID)
  → Messages within a partition are sorted by time
  → Supports efficient pagination

​

Deep Dive 3: Online Presence (Heartbeat Mechanism)

Presence Flow:
1. User connects → status set to "online" in Redis
   HSET presence user:123 '{"status":"online","server":"chat-02","ts":...}'

2. Client sends heartbeat every 30 seconds
   → Redis TTL refreshed: EXPIRE presence:user:123 60

3. If no heartbeat for 60 seconds → TTL expires → user is "offline"

4. When User A opens chat with User B:
   → Check Redis: HGET presence user:456
   → Subscribe to presence changes for contacts

​

WhatsApp: 100B+ Messages/Day with ~50 Engineers

• Erlang/OTP: WhatsApp’s backend is built on Erlang, a language designed for telecom systems that need massive concurrency and fault tolerance. A single Erlang server can handle 2-3 million concurrent connections because Erlang processes are lightweight (a few hundred bytes each, compared to threads that cost megabytes). This is why 50 engineers could operate what would require hundreds of engineers in a Java or Python stack.
• Message storage philosophy: WhatsApp treats the server as a delivery mechanism, not a storage system. Messages are stored on the server only until they are delivered to the recipient’s device. Once the recipient acknowledges receipt, the message is deleted from the server. This “transient store” approach dramatically reduces storage requirements and simplifies the architecture.
• XMPP-based protocol (modified): WhatsApp started with the XMPP messaging protocol and heavily modified it for mobile efficiency. Their custom protocol minimizes battery drain and data usage — critical for WhatsApp’s user base in markets with limited data plans.
• No read receipts stored server-side: The blue check marks (read receipts) are end-to-end signals between devices. The server facilitates delivery but does not store read state. This is another example of pushing complexity to the edges and keeping the server simple.
• Mnesia for routing: WhatsApp uses Erlang’s built-in Mnesia database for connection routing — mapping which user is connected to which server. Mnesia is an in-memory distributed database that replicates across Erlang nodes, giving sub-millisecond lookups without an external dependency like Redis.
• FreeBSD over Linux: WhatsApp chose FreeBSD for their servers, partly because of superior network stack performance for their specific workload (millions of concurrent TCP connections). This is an unconventional choice that paid off — it shows that sometimes the right tool is not the popular tool.

​

Discord’s Message Storage

• Migration from MongoDB to Cassandra: Discord initially stored messages in MongoDB. As they scaled, MongoDB’s single-primary-per-shard model created write bottlenecks for hot channels. They migrated to Cassandra, which distributes writes evenly across nodes. The partition key is (channel_id, bucket) where bucket is a time window, preventing any single partition from growing unbounded.
• Bucket strategy: Each bucket covers a fixed time period (approximately 10 days of messages). When a user scrolls back through history, Discord fetches the appropriate bucket. New messages always write to the current bucket. This means the “hot” data (recent messages) is always on a small number of partitions, keeping reads fast.
• Data services layer: Discord added a data services layer between their API and Cassandra. This layer handles request coalescing — if 1,000 users in the same channel all request the same messages at the same time (e.g., after a server outage), the data services layer deduplicates these into a single Cassandra read and fans the result back to all requesters. Without this, a thundering herd could overwhelm Cassandra.
• ScyllaDB migration: Discord later migrated from Cassandra to ScyllaDB (a C++ reimplementation of Cassandra’s protocol) for better tail latency performance. Cassandra’s JVM garbage collection pauses caused p99 latency spikes that affected user experience. ScyllaDB, being C++ with a shard-per-core architecture, eliminated GC pauses entirely.

• All 10K users get disconnected simultaneously. Each client’s reconnection logic kicks in (exponential backoff with jitter). The load balancer routes reconnections to healthy servers.
• Critical: the Message Store (Cassandra) has all messages persisted. When users reconnect, they request messages since their last received message ID. No messages are lost — they were persisted before the server acknowledged them to the sender. This is why you write to the database before forwarding to the recipient.
• Risk: thundering herd on reconnection. 10K clients reconnecting simultaneously can overwhelm the remaining servers. Mitigation: client-side exponential backoff with random jitter (reconnect between 1-10 seconds, not all at once).

• Inter-server message routing stops. If User A is on Chat Server 1 and User B is on Chat Server 3, messages cannot be forwarded.
• Short-term: messages queue up on the sending server. Long-term: fall back to a polling mechanism where Chat Servers periodically check the Message Store for undelivered messages for their connected users.
• Alternative: run Redis Pub/Sub as a cluster with Sentinel for automatic failover. Recovery is typically under 30 seconds.

• Cassandra is designed for this — it uses a quorum-based consistency model. With a replication factor of 3 and quorum reads/writes, the system tolerates one node failure per partition.
• If too many nodes fail and quorum is lost: messages cannot be persisted. The Chat Server must buffer messages in memory and retry. Return a “message pending” status to the sender instead of “delivered.” This is an honest UX that users understand — they see a clock icon instead of a check mark.

• The heartbeat TTL is 60 seconds, so in the worst case, a user appears online for up to 60 seconds after going offline. This is acceptable for most chat applications — WhatsApp and Telegram both have similar tolerances.
• In the other direction (user appears offline but is online), this happens if a heartbeat is lost. The next heartbeat in 30 seconds corrects it. This is why presence should always be treated as “best effort” and never used for critical decisions.

• Messages sent within each region continue to work. Cross-region messages queue up and deliver once the partition heals.
• The critical design decision: do you allow both regions to accept writes (risk message ordering conflicts) or do you designate one region as primary (risk write unavailability in the secondary)? For chat, allowing both regions to accept writes with per-conversation ordering (guaranteed by partition key) is the better choice. Cross-conversation ordering does not matter.

• Server-side search is now impossible. The server stores encrypted blobs. Key exchange happens via the Signal Protocol (double-ratchet). Group chat encryption becomes significantly harder — you need the Sender Keys protocol where each group member maintains a session with the sender. Message editing and deletion must be handled as encrypted “edit” or “tombstone” events. The presence system is unaffected (metadata, not content). This is how WhatsApp and Signal work.

• The fan-out model from the original design breaks at 10K members. You cannot push messages to 10K Redis Pub/Sub channels. Instead, use a channel-centric model: members subscribe to the channel, and the Chat Server maintains a channel subscription map. A message published to a channel is broadcast to all servers that have at least one subscriber for that channel (typically far fewer than 10K servers). This is Discord’s approach. The presence system also changes — you cannot show individual online status for 10K members, so you show “X members online” as an aggregate.

• User-facing “delete” becomes a soft delete (hidden from UI, still in storage). The Cassandra TTL strategy from the original design must be disabled. Storage grows linearly forever — at 2B messages/day, that is ~5 PB over 7 years. You need a tiered storage strategy: hot (last 30 days in Cassandra), warm (30 days to 1 year in S3), cold (1-7 years in S3 Glacier). The audit trail must be immutable. Encryption key management becomes critical — you must be able to decrypt 7-year-old messages, which means key rotation must preserve old keys.

• Offline-first architecture becomes mandatory. Messages are stored locally on the device first, then synced when connectivity returns. You need a conflict resolution protocol for messages created offline by multiple users. Vector clocks or Lamport timestamps per conversation ensure causal ordering. Message payloads must be compact (Protocol Buffers instead of JSON). The app must work in a “compose and queue” mode where the user types and the message is sent later. This is WhatsApp’s design philosophy.

• Networking — WebSocket protocol, TCP connection management, HTTP long-polling, and SSE are covered in Networking and Deployment.
• Messaging and concurrency — Pub/Sub patterns, message queues, fan-out strategies, and exactly-once vs at-least-once delivery guarantees are explored in Messaging, Concurrency, and State.
• Databases — Cassandra data modeling, partition key design, hot partition mitigation, and the migration story (MongoDB to Cassandra to ScyllaDB) connect to APIs and Databases. For a deeper exploration of Cassandra vs ScyllaDB partition strategies, wide-row design, and when to choose time-series-optimized databases, see Database Deep Dives.
• Caching — Redis for Pub/Sub, presence state, and connection routing connects to Caching and Observability.
• Performance — WebSocket connection scaling, heartbeat optimization, and lazy vs active presence evaluation connect to Performance and Scalability.
• Security — End-to-end encryption, authentication of WebSocket connections, and the Signal Protocol connect to Auth and Security.
• Real-time systems — WebSocket lifecycle management, heartbeat protocols, presence tracking, and the trade-offs between push (WebSocket), pull (long-polling), and hybrid delivery models are core real-time patterns explored in Real-Time Systems. The chat system is the canonical real-time system design problem.
• Cloud service patterns — The decision between API Gateway WebSocket APIs and custom WebSocket servers on ECS, NLB vs ALB for persistent connections, and SNS Mobile Push integration are practical AWS patterns covered in Cloud Service Patterns.

​

Questions You Should Ask the Interviewer

​

Requirements You Should Lock Down

• Users create posts (text + images/video)
• Users follow other users (asymmetric follow model)
• Home feed shows posts from followed users, ranked by relevance
• Support likes, comments, shares (interaction signals)

• Feed generation latency < 500ms
• Support 500M DAU
• Handle celebrity accounts (10M+ followers)
• Feed should feel “fresh” (updates within minutes of posting)

​

Back-of-Envelope Calculation

Assumptions:
  DAU:                          500M
  Average follows per user:     200
  Average posts per user/day:   2
  Total posts/day:              1 billion
  Average post size:            1 KB (text + metadata)
  Average feed fetch/day:       10 per user

Write (post creation):
  1B / 86,400                   ~ 11,600 posts/sec
  Peak (5x):                    ~ 58,000 posts/sec

Read (feed fetch):
  500M x 10 / 86,400           ~ 58,000 feed fetches/sec
  Peak (5x):                    ~ 290,000 feed fetches/sec

Fan-out calculation (the critical number):
  Average user: 200 followers
    → 1 post = 200 fan-out writes
  Celebrity (1M followers):
    → 1 post = 1,000,000 fan-out writes
    → 10 celebrities posting = 10M writes instantly

Storage for pre-computed feeds:
  500M users x 500 post IDs x 8 bytes = 2 TB
  (Only store post IDs in feed, not full content)

​

The Two Fundamental Approaches

Fan-Out on Write (Push Model):
  User posts → immediately write to all followers' feed caches
  ┌──────────┐    ┌──────────────────┐    ┌───────────────┐
  │  Post    │───▶│  Fan-out Service │───▶│ Feed Cache    │
  │  Service │    │  (async workers) │    │ (per-user)    │
  └──────────┘    └──────────────────┘    └───────────────┘
  Pro: Feed reads are instant (pre-computed)
  Con: Write amplification; celebrity post = millions of writes

Fan-Out on Read (Pull Model):
  User opens feed → query all followed users' posts in real-time
  ┌──────────┐    ┌──────────────────┐    ┌───────────────┐
  │  Feed    │───▶│  Aggregation     │───▶│ Post Storage  │
  │  Request │    │  Service         │    │ (per-user)    │
  └──────────┘    └──────────────────┘    └───────────────┘
  Pro: No write amplification; simple writes
  Con: Slow read (must merge 200+ sorted lists at read time)

​

Hybrid Architecture (Recommended)

┌──────────────────────────────────────────────────────────────────┐
│                       Hybrid News Feed                           │
│                                                                  │
│  Normal user posts (< 10K followers):                           │
│    → Fan-out on WRITE to all followers' caches                   │
│                                                                  │
│  Celebrity posts (> 10K followers):                              │
│    → Do NOT fan out; store in celebrity post cache               │
│    → At read time, merge celebrity posts with pre-computed feed  │
└──────────────────────────────────────────────────────────────────┘

  ┌──────────┐
  │  User    │──── Creates post
  └────┬─────┘
       │
  ┌────▼─────────────────────┐
  │  Post Service            │
  │  (writes to Post DB)     │
  └────┬─────────────────────┘
       │
       ├── followers < 10K ──▶ Fan-out workers ──▶ Feed Cache
       │                                           (Redis sorted set)
       │
       └── followers > 10K ──▶ Celebrity Post Cache
                                (read at feed-fetch time)

  Feed Fetch:
  ┌──────────┐    ┌─────────────────┐
  │  Client  │───▶│ Feed Service    │
  └──────────┘    │ 1. Read cache   │
                  │ 2. Merge celebs │
                  │ 3. Rank/sort    │
                  │ 4. Return top N │
                  └─────────────────┘

​

Deep Dive 1: The Hybrid Fan-Out Strategy

Redis sorted set per user:
ZADD feed:user:789 <timestamp_score> <post_id>

Keep only the most recent 500 entries:
ZREMRANGEBYRANK feed:user:789 0 -501

​

Deep Dive 2: Feed Ranking

Score(post) = w1 * recency
            + w2 * affinity(user, author)
            + w3 * engagement(likes, comments, shares)
            + w4 * content_type_preference
            + w5 * diversity_penalty

Where:
  recency    = exponential decay from post creation time
  affinity   = how often user interacts with author
  engagement = normalized like/comment/share count
  diversity  = penalize seeing 5 posts from same author in a row

​

Deep Dive 3: Caching and CDN for Media

Caching layers:
┌──────────────────────────────────────────────────┐
│  Layer 1: CDN (images, videos, static assets)    │
│  Layer 2: Feed Cache (Redis - post IDs per user) │
│  Layer 3: Post Cache (Redis - post content)      │
│  Layer 4: Social Graph Cache (who follows whom)  │
│  Layer 5: Database (source of truth)             │
└──────────────────────────────────────────────────┘

Cache invalidation strategy:
- Feed cache: append-only (new posts added, old posts expire via ZREMRANGEBYRANK)
- Post cache: invalidate on edit/delete (rare operations)
- Social graph cache: invalidate on follow/unfollow

​

Facebook’s News Feed Ranking Evolution

• 2006 — Chronological feed: The original News Feed was purely chronological. If your friend posted, it appeared in your feed sorted by time. Simple, but as users added hundreds of friends, the feed became noisy and engagement dropped.
• 2009 — EdgeRank: Facebook introduced EdgeRank, a relatively simple scoring formula: Score = Affinity x Weight x Decay. Affinity measured how close you were to the poster (based on interactions). Weight reflected the content type (photos ranked higher than text). Decay was a time-based exponential falloff. EdgeRank was essentially the formula we described in the ranking section above.
• 2013+ — Machine learning replaces EdgeRank: Facebook replaced the hand-tuned formula with a machine learning model that considers thousands of signals. The model predicts the probability that you will engage with (like, comment, share, click) each candidate post. Posts are ranked by predicted engagement score.
• Fan-out architecture: Facebook uses a hybrid fan-out model very similar to what we designed above. Normal users get fan-out-on-write (their posts are pushed to followers’ pre-computed feeds). Celebrities and pages with millions of followers use fan-out-on-read (their posts are merged at feed-fetch time). The threshold is dynamic and adjusts based on system load.
• Aggregator service: Facebook’s feed generation pipeline has a dedicated aggregation service (called “Multifeed”) that merges posts from multiple sources: the pre-computed feed cache, celebrity posts fetched on-read, ads injected by the ad auction, and “story bumping” (resurfacing older posts that are getting new comments). This merge step is where the ranking model runs.
• Feed cache (TAO + Memcache): Facebook built a custom distributed cache called TAO (The Associations and Objects cache) specifically for social graph data. Feed data lives in a combination of TAO, Memcache, and MySQL. The caching hierarchy is: L1 (in-process cache on the web server) to L2 (Memcache cluster in the same region) to L3 (TAO for social graph queries) to L4 (MySQL as source of truth).

​

Twitter’s Timeline Architecture

• Original approach (fan-out on write): For years, Twitter used aggressive fan-out-on-write. When you tweeted, a fleet of workers would push your tweet ID into the timelines of all your followers stored in Redis. This worked well because reads were instant — opening Twitter just meant reading a pre-computed list from Redis.
• The celebrity problem: This approach broke for users like Lady Gaga or Barack Obama with 30M+ followers. A single tweet triggered 30 million Redis writes. During events like the Super Bowl or elections, the fan-out queue would back up by minutes or even hours, meaning some users would see tweets with significant delay.
• Migration to hybrid: Twitter moved to a hybrid model around 2012-2013. Most users (those with fewer followers than a dynamic threshold) still get fan-out-on-write. High-follower accounts are excluded from fan-out. When you open your timeline, Twitter’s timeline service merges your pre-computed timeline with recent tweets from the high-follower accounts you follow.
• Timeline cache: Twitter stores timelines in a massive Redis cluster. Each user’s timeline is a Redis list of tweet IDs (not full tweet content). At read time, the IDs are hydrated by fetching the tweet content from a separate Tweet Store service. This separation means the timeline cache stays small (just IDs and scores) while tweet content is cached independently.
• Ranking and relevance: Twitter introduced algorithmic ranking (“top tweets”) alongside the chronological timeline. The ranking model considers engagement signals, recency, your past interactions with the author, and content type. Users can toggle between ranked and chronological views — a product decision that has architectural implications (you need to support both code paths).

• Users’ pre-computed feeds are gone. Every feed fetch becomes a fan-out-on-read: query the Post DB for recent posts from all followed users, merge, rank, and return. This is 100-1000x slower than a cache hit.
• Mitigation: multi-tier caching. L1 cache on the web server (in-process, last 5 minutes of feeds), L2 is the Redis cluster. If L2 dies, L1 buys you time for a percentage of users. For users not in L1, serve a degraded feed (e.g., top trending posts for everyone) while Redis recovers.
• Recovery priority: warm the cache for the most active users first (those currently online), not all 500M users. Use the active user list from the presence/session service to prioritize.

• New posts are being created but not distributed to followers’ feeds. Users see stale feeds. The Kafka queue grows.
• This is expected during traffic spikes (Super Bowl, elections, breaking news). Mitigation: auto-scale fan-out workers based on Kafka consumer lag. Set alerting thresholds: lag > 5 minutes triggers scaling, lag > 30 minutes triggers an incident.
• Graceful degradation: if fan-out lag exceeds a threshold, temporarily switch all users to fan-out-on-read. The feed will be slightly slower but always fresh. Switch back to fan-out-on-write once workers catch up.

• Fall back to chronological ordering. The feed still loads — it is just not ranked. Users see recent posts from people they follow, sorted by time. This is a perfectly acceptable degraded experience. Many users actually prefer chronological feeds.
• The important principle: the ranking service should be stateless and horizontally scalable, sitting behind a load balancer. A single instance failure should not affect any users. Only a total cluster failure causes degradation.

• If you are using the hybrid model correctly, this is a non-event. Celebrity posts are not fanned out — they live in the celebrity post cache and are merged at read time. The celebrity’s 10M followers experience zero additional latency because no fan-out occurs for this post.
• This is precisely why the hybrid model exists. Under pure fan-out-on-write, this celebrity post would add 10M items to an already-backed-up queue.

• Post content fetches slow down. Feeds still load (post IDs come from the Feed Cache) but individual posts render as “loading” on the client.
• Mitigation: aggressive caching of post content. Popular posts (anything with > 100 likes in the past hour) should be in the Post Cache (Redis) with very high TTL. Cache hit rate for viral content should be 99.9%+.

• Pre-computed feeds now have a write-back problem. When a post is flagged, you must scan and remove it from potentially millions of pre-computed feed caches. This is expensive. Alternative: do not embed post content in feeds — store only post IDs. The Feed Service hydrates IDs to content at read time, checking a “blocked posts” set before returning. A blocked post simply returns nothing, creating a seamless removal. This is how Facebook and Instagram handle content moderation at scale — the moderation decision propagates instantly because the content fetch is decoupled from the feed cache.

• Two separate feed generation paths. The “Following” feed is the hybrid fan-out model from the original design. The “For You” feed is entirely fan-out-on-read: a recommendation service generates candidate posts from a broader pool (not just followed users), scores them, and returns the top N. The “For You” path requires a real-time ML inference service (SageMaker, TensorFlow Serving). The two feeds share the post cache but have completely different generation pipelines. The switching must be instant — both feeds should be pre-warmed or quickly generatable.

• The celebrity fan-out problem vanishes entirely. Pure fan-out-on-write works perfectly at 50K users. The ranking service is unnecessary — chronological is fine for enterprise. But the compliance requirement adds a new dimension: posts cannot be truly deleted (only soft-deleted from user-facing views), the audit trail must be immutable, and access control must respect organizational hierarchies (a post in the “Engineering” group should not be visible to “Sales” unless explicitly shared). The entire feed architecture simplifies dramatically, but the access control layer becomes the hardest part.

• The biggest costs in a feed system: (1) Redis cluster for pre-computed feeds (memory is expensive at scale), (2) fan-out workers (compute for write amplification), (3) CDN for media delivery. Cost reduction strategies: stop pre-computing feeds for inactive users (users who have not logged in for 14 days) — this can reduce Redis usage by 40-60%. Reduce the feed cache depth from 500 to 200 post IDs per user. Move fan-out workers to Spot instances (they are stateless and retry-safe). Compress media more aggressively (AVIF instead of JPEG saves 30-50% bandwidth). Each of these trades a small UX degradation for a measurable cost reduction.

• Caching — Multi-tier caching (CDN, Redis feed cache, post cache, social graph cache), cache invalidation strategies, and cache warming are covered in depth in Caching and Observability.
• Messaging and async processing — Kafka-based fan-out workers, consumer lag monitoring, and async event processing connect to Messaging, Concurrency, and State.
• Databases — Choosing between Redis sorted sets for feed storage, Cassandra for post storage, and the social graph data model connect to APIs and Databases. For a deeper exploration of graph databases (Neptune) vs adjacency list patterns in DynamoDB for social graph modeling, and the trade-offs between wide-column stores and document databases for post storage, see Database Deep Dives.
• Performance — CDN for media delivery, feed latency optimization, and the trade-off between pre-computation and on-demand computation connect to Performance and Scalability.
• Design patterns — The push/pull/hybrid pattern is a fundamental distributed systems design pattern explored in Design Patterns.
• Scalability estimation — The back-of-envelope math for fan-out write amplification connects to Capacity, Git, and Pipelines.
• Distributed systems theory — The fan-out problem is fundamentally about write amplification and eventual consistency. Understanding CAP theorem trade-offs (the feed cache is eventually consistent with the post store) and how read-your-writes consistency affects the posting user’s experience connects to Distributed Systems Theory.
• Cloud service patterns — DynamoDB Streams for event-driven fan-out, SageMaker for real-time ranking inference, Neptune for social graph queries, and the serverless fan-out pattern are AWS-specific implementations explored in Cloud Service Patterns.

​

Questions You Should Ask the Interviewer

​

Requirements You Should Lock Down

• Schedule one-time tasks for immediate or delayed execution
• Schedule recurring tasks using cron expressions
• Retry failed tasks with configurable backoff (max 3 retries)
• Dead-letter queue for tasks that exceed retry limit
• Task status tracking: pending, scheduled, running, completed, failed, dead
• Cancel or pause scheduled/recurring tasks

• At-least-once execution guarantee (with idempotency support)
• Handle 10M task executions per day
• Scheduling accuracy: within 1 second of target time
• Horizontal scaling of both scheduler and workers
• No single point of failure

​

Back-of-Envelope Calculation

Assumptions:
  Tasks scheduled per day:      10M
  One-time tasks:               60% (6M)
  Recurring tasks:              40% (4M definitions, generating 50M executions/day)
  Total executions per day:     56M
  Average task duration:        5 seconds
  Peak task burst:              10x average

Throughput:
  56M / 86,400                  ~ 650 tasks/sec average
  Peak (10x):                   ~ 6,500 tasks/sec

Worker capacity:
  Each worker handles 1 task at a time for 5 seconds
  Worker throughput: 12 tasks/min = 720 tasks/hour
  Peak needs: 6,500 concurrent tasks
  Workers needed: 6,500 (at peak, with 1 task per worker)
  With 10 tasks/worker (async): ~650 workers at peak

Task storage:
  56M tasks/day x 1 KB avg = 56 GB/day
  30-day retention: ~1.7 TB
  Completed tasks archived to cold storage after 7 days

Queue depth:
  At peak, 6,500 tasks queued per second
  If workers process in 5 seconds: ~32,500 tasks in queue at any time

​

Component Architecture

┌─────────────────────────────────────────────────────────────────┐
│                  Distributed Task Scheduler                     │
│                                                                 │
│  ┌──────────┐       ┌──────────────┐       ┌───────────────┐   │
│  │  Client  │──────▶│  Task API    │──────▶│  Task Store   │   │
│  │  (SDK)   │       │  (REST/gRPC) │       │  (PostgreSQL) │   │
│  └──────────┘       └──────────────┘       └───────┬───────┘   │
│                                                     │           │
│                     ┌──────────────┐                │           │
│                     │  Scheduler   │◀───────────────┘           │
│                     │  (Leader)    │                             │
│                     └──────┬───────┘                             │
│                            │  Enqueues due tasks                │
│                     ┌──────▼───────┐                             │
│                     │  Task Queue  │                             │
│                     │  (Redis /    │                             │
│                     │   SQS)       │                             │
│                     └──────┬───────┘                             │
│                            │                                     │
│              ┌─────────────┼─────────────┐                      │
│              │             │             │                       │
│         ┌────▼────┐  ┌────▼────┐  ┌────▼────┐                  │
│         │Worker 1 │  │Worker 2 │  │Worker N │                  │
│         └────┬────┘  └────┬────┘  └────┬────┘                  │
│              │             │             │                       │
│              └─────────────┼─────────────┘                      │
│                            │                                     │
│                     ┌──────▼───────┐                             │
│                     │  Dead Letter │                             │
│                     │  Queue (DLQ) │                             │
│                     └──────────────┘                             │
└─────────────────────────────────────────────────────────────────┘

​

API Design

POST   /api/v1/tasks              — Schedule a new task
GET    /api/v1/tasks/{id}         — Get task status
DELETE /api/v1/tasks/{id}         — Cancel a task
PATCH  /api/v1/tasks/{id}/pause   — Pause a recurring task
GET    /api/v1/tasks?status=failed — List tasks by status

Task payload:
{
  "task_type": "send_email",
  "payload": { "to": "user@example.com", "template": "welcome" },
  "schedule": {
    "type": "delayed",          // "immediate" | "delayed" | "cron"
    "run_at": "2026-04-10T10:00:00Z",
    "cron": null                // "0 */6 * * *" for recurring
  },
  "retry_policy": {
    "max_retries": 3,
    "backoff": "exponential",   // "fixed" | "exponential"
    "initial_delay_sec": 10
  },
  "timeout_sec": 300,
  "idempotency_key": "email-welcome-user-123"
}

​

Deep Dive 1: Task State Machine

                  ┌───────────┐
                  │  PENDING   │  ← Task created, not yet due
                  └─────┬─────┘
                        │ (run_at time reached)
                  ┌─────▼─────┐
                  │ SCHEDULED  │  ← Placed in task queue
                  └─────┬─────┘
                        │ (worker picks up)
                  ┌─────▼─────┐
          ┌───────│  RUNNING   │───────┐
          │       └─────┬─────┘       │
          │ (success)   │    (failure + retries left)
    ┌─────▼─────┐       │       ┌─────▼─────┐
    │ COMPLETED  │       │       │ RETRYING   │
    └───────────┘       │       └─────┬─────┘
                        │             │ (back to SCHEDULED)
                        │             └──────▶ SCHEDULED
                        │
                        │ (failure + no retries left)
                  ┌─────▼─────┐
                  │   DEAD     │  ← Moved to DLQ
                  └───────────┘

Additional states:
  CANCELLED — user cancelled the task
  PAUSED    — recurring task paused by user

​

Database Schema

CREATE TABLE tasks (
    id              UUID PRIMARY KEY,
    idempotency_key VARCHAR(255) UNIQUE,
    task_type       VARCHAR(100) NOT NULL,
    payload         JSONB NOT NULL,
    status          VARCHAR(20) NOT NULL DEFAULT 'PENDING',
    priority        INT DEFAULT 0,

    -- Scheduling
    schedule_type   VARCHAR(20) NOT NULL,  -- immediate/delayed/cron
    run_at          TIMESTAMPTZ,
    cron_expression VARCHAR(100),
    next_run_at     TIMESTAMPTZ,           -- For recurring tasks

    -- Execution tracking
    attempt         INT DEFAULT 0,
    max_retries     INT DEFAULT 3,
    timeout_sec     INT DEFAULT 300,
    locked_by       VARCHAR(100),          -- Worker ID holding the lock
    locked_at       TIMESTAMPTZ,
    started_at      TIMESTAMPTZ,
    completed_at    TIMESTAMPTZ,
    error_message   TEXT,

    created_at      TIMESTAMPTZ DEFAULT NOW(),
    updated_at      TIMESTAMPTZ DEFAULT NOW()
);

-- Index for scheduler to find due tasks efficiently
CREATE INDEX idx_tasks_pending ON tasks (next_run_at)
    WHERE status IN ('PENDING', 'RETRYING');

-- Index for status queries
CREATE INDEX idx_tasks_status ON tasks (status, created_at);

​

Deep Dive 2: Distributed Locking for Task Pickup

BEGIN;
-- Atomically claim the next available task
UPDATE tasks
SET status = 'RUNNING',
    locked_by = 'worker-042',
    locked_at = NOW(),
    attempt = attempt + 1
WHERE id = (
    SELECT id FROM tasks
    WHERE status IN ('SCHEDULED')
      AND next_run_at <= NOW()
    ORDER BY priority DESC, next_run_at ASC
    LIMIT 1
    FOR UPDATE SKIP LOCKED
)
RETURNING *;
COMMIT;

-- Scheduler enqueues tasks (score = execution timestamp)
ZADD task_queue <run_at_timestamp> <task_id>

-- Worker atomically pops the next due task
ZPOPMIN task_queue

-- Worker sets a lock with TTL (lease)
SET lock:task:<task_id> worker-042 EX 300 NX

Lease renewal loop (in worker):
while task_is_running:
    sleep(lease_ttl / 3)
    EXPIRE lock:task:<task_id> lease_ttl  # Renew

​

Deep Dive 3: Failure Handling and Idempotency

next_retry_at = NOW() + initial_delay * (2 ^ attempt_number)

Attempt 1: retry after 10 seconds
Attempt 2: retry after 20 seconds
Attempt 3: retry after 40 seconds
Attempt 4: max retries exceeded → move to DLQ

POST /tasks with idempotency_key = "charge-order-456"
→ If key exists and task is COMPLETED → return existing result
→ If key exists and task is RUNNING   → return "in progress"
→ If key does not exist               → create new task

-- Move exhausted task to DLQ
UPDATE tasks
SET status = 'DEAD',
    completed_at = NOW(),
    error_message = 'Max retries exceeded: <last error>'
WHERE id = :task_id;

INSERT INTO dead_letter_queue (task_id, original_payload, failure_reason, dead_at)
VALUES (:task_id, :payload, :error, NOW());

​

Uber’s Cadence / Temporal

• Workflow as code: Unlike traditional task schedulers that treat tasks as independent units, Cadence/Temporal models entire workflows as code. A workflow function can call activities (individual tasks), wait for signals, set timers, and branch on conditions — all while being fully durable. If the worker crashes mid-workflow, the framework replays the workflow function from the event history to resume exactly where it left off.
• Event sourcing under the hood: Every state change in a workflow is persisted as an event in a history. The workflow’s current state is reconstructed by replaying this event history. This is fundamentally different from the state-machine-in-a-database approach we designed above. It is more flexible (arbitrary workflow logic instead of predefined states) but more complex to reason about.
• Task queues with sticky execution: Temporal uses task queues to dispatch activities to workers. It supports “sticky execution” — once a worker starts processing a workflow, subsequent activities in that workflow are preferentially routed to the same worker. This improves cache locality (workflow context is already in memory) and reduces replay overhead.
• Visibility and search: Temporal provides a built-in visibility layer that indexes workflow metadata (status, type, start time, custom search attributes) into Elasticsearch. Operators can search for workflows across millions of executions. This is the observability layer that is often an afterthought in custom task schedulers.
• Multi-cluster replication: For disaster recovery, Temporal supports active-passive replication across clusters. Workflows in a failed cluster can be resumed in the standby cluster. This is critical for Uber’s ride-booking workflows — a datacenter failure cannot cause rides to be lost.
• At Uber’s scale: At peak, Uber’s Cadence deployment handled hundreds of thousands of workflow executions per second across multiple Cassandra clusters totaling petabytes of event history. The system managed everything from ride lifecycle to financial settlement to promotional offer expiration.

​

Apache Airflow’s Architecture

• DAG-based scheduling: Airflow represents workflows as Directed Acyclic Graphs (DAGs). Each node is a task (e.g., “extract data from S3”, “run Spark job”, “load into warehouse”) and edges represent dependencies. The scheduler traverses the DAG, executing tasks only when their upstream dependencies are complete.
• Scheduler architecture: Airflow’s scheduler is a loop that runs every few seconds: (1) parse all DAG files to discover task dependencies, (2) identify tasks whose dependencies are met and whose scheduled time has arrived, (3) place those tasks into a queue (Celery, Kubernetes, or a local executor). The scheduler was historically single-threaded and a bottleneck, but Airflow 2.0+ supports multiple schedulers with database-level locking (similar to the SKIP LOCKED pattern we described above).
• Executor model: Airflow separates scheduling from execution. The executor is pluggable: CeleryExecutor distributes tasks to a fleet of Celery workers via Redis/RabbitMQ, KubernetesExecutor spins up a new pod for each task (strong isolation but higher overhead), and LocalExecutor runs tasks as subprocesses on the scheduler machine (fine for small deployments).
• Metadata database (PostgreSQL/MySQL): All task state, DAG definitions, execution history, and scheduling metadata live in a relational database. This is the source of truth. The choice of PostgreSQL or MySQL is deliberate — Airflow needs ACID transactions for state machine transitions, exactly as we discussed in Problem 5.
• XCom for inter-task communication: Tasks can pass small amounts of data to downstream tasks via “XComs” (cross-communications) stored in the metadata database. For large datasets, tasks write to external storage (S3, GCS) and pass only the reference via XCom. This pattern of passing pointers instead of payloads is a common production optimization.
• Limitations: Airflow is designed for batch workflows (run this ETL every hour), not for real-time event-driven tasks. It has no native concept of responding to events or running sub-second-latency tasks. For those use cases, Temporal or a custom solution (like the one we designed) is more appropriate.

• This is the most dangerous failure. No new tasks get enqueued from PENDING to SCHEDULED. Tasks already in the queue continue to be processed by workers, but no new tasks are picked up from the database.
• Mitigation: leader election with automatic failover. Run 2-3 scheduler instances. Only one is active (the leader), the others are on standby. Use PostgreSQL advisory locks or Redis Redlock for leader election. When the leader’s lock expires (because it crashed), a standby instance acquires the lock and becomes the new leader within seconds.
• Detection: the standby schedulers monitor the leader’s heartbeat. Additionally, a canary task (a no-op task scheduled every minute) serves as an end-to-end health check. If the canary does not execute within 2 minutes, alert on-call.

• The task is stuck in RUNNING state. The lease (lock TTL) expires after the configured timeout. The zombie detector (a periodic scheduler job) identifies tasks where locked_at + timeout_sec < NOW() and status = RUNNING. These zombie tasks are moved back to SCHEDULED if retries remain, or to DEAD if they are exhausted.
• The task may have partially completed before the crash. This is why idempotency is non-negotiable — the retry must be safe to execute even if the first attempt partially succeeded. Example: if the task is “charge customer $50,” the payment system must use an idempotency key so the retry does not double-charge.

• Workers cannot pull new tasks. Tasks accumulate in PostgreSQL with status SCHEDULED but no queue to feed them to workers.
• Short-term mitigation: workers fall back to polling PostgreSQL directly using the SELECT ... FOR UPDATE SKIP LOCKED query. This is slower (10-100x less throughput than Redis) but functional.
• Long-term: Redis Sentinel or Redis Cluster with automatic failover. Recovery in under 30 seconds for most configurations.

• This is the worst-case scenario. Task state is lost (or temporarily inaccessible). New tasks cannot be created. Task status updates from workers fail.
• Workers that are currently executing tasks continue to run (they already have the task payload). But they cannot report completion, so tasks will appear as zombies after lease expiry and get retried — making idempotency even more critical.
• Mitigation: PostgreSQL with streaming replication and automatic failover (Patroni, RDS Multi-AZ). Recovery time: 15-30 seconds. Data loss: zero or near-zero (depending on synchronous vs async replication).

• After exhausting retries, the task lands in the DLQ. But the recurring schedule generates a new execution for the next interval, which also fails and also lands in the DLQ. You now have a DLQ filling up with the same failing task.
• Mitigation: circuit breaker pattern for recurring tasks. After N consecutive failures (across multiple scheduled executions), automatically PAUSE the recurring task and alert the task owner. Require manual re-enablement after the root cause is fixed. This prevents a single broken dependency from flooding the DLQ and masking other legitimate failures.

• The simple queue model breaks. You now need a DAG execution engine. Each task has a depends_on field listing prerequisite task IDs. The scheduler evaluates task readiness by checking whether all dependencies are in COMPLETED state. This requires a topological sort on the dependency graph. Cycles must be detected and rejected at submission time. At this point, you are building Airflow or Temporal. In an interview, acknowledge this and explain when to buy vs build: “If we need DAG execution, I would evaluate Temporal or Step Functions before building custom, because correct DAG scheduling with failure handling is a solved problem that is hard to get right.”

• Global deduplication becomes the hard problem. The idempotency key must be checked globally, not per-region. Options: (1) use a global DynamoDB table with a unique constraint on the idempotency key (cross-region replication with conflict resolution), (2) designate a single “coordinator region” that owns task deduplication and fans out execution to regional workers, or (3) partition tasks by a deterministic key (e.g., hash of idempotency key modulo 3 regions) so each task has exactly one “owning” region. Option 3 is the most scalable but requires re-routing submissions to the owning region.

• A single worker pool cannot handle both. Sub-second tasks need lightweight workers (Lambda functions) that spin up and down instantly. 24-hour tasks need persistent workers (ECS tasks) with lease renewal, heartbeats, and checkpointing. The scheduler routes tasks to different worker pools based on estimated duration. The lease-based locking pattern from the original design must support configurable TTLs — a 60-second TTL for sub-second tasks, a 1-hour TTL with renewal for long-running tasks. Checkpointing allows a long-running task to resume from its last checkpoint after a worker failure, rather than restarting from scratch.

• Per-tenant queues or per-tenant priority within a shared queue. The simplest approach: each tenant gets a fair-share allocation of worker capacity. If you have 100 workers and 10 active tenants, each tenant gets 10 workers. Burst capacity is allocated from an overflow pool. Critical tasks bypass the per-tenant queue and go to a dedicated high-priority queue (similar to the notification system’s priority routing). This is the multi-tenancy pattern used by managed services like AWS Step Functions and Temporal Cloud.

• Databases — PostgreSQL advisory locks, SELECT FOR UPDATE SKIP LOCKED, ACID transactions for state machine integrity, and schema design connect to APIs and Databases. For a deeper dive into PostgreSQL’s locking mechanisms (advisory locks, row-level locks, SKIP LOCKED internals) and when to choose PostgreSQL over DynamoDB for transactional workloads, see Database Deep Dives.
• Messaging and queues — Redis as a task queue, Kafka for event-driven architectures, dead-letter queues, and at-least-once delivery guarantees are covered in Messaging, Concurrency, and State.
• Reliability — Leader election, automatic failover, circuit breaker patterns, and graceful degradation connect to Reliability Principles.
• Distributed systems theory — The leader election for the scheduler, the fencing token pattern for zombie task detection, and the impossibility of exactly-once delivery in distributed systems are core consensus and consistency concepts explored in Distributed Systems Theory. The Raft or Paxos consensus protocols that underpin PostgreSQL’s Patroni failover and Redis’s Sentinel are covered there in depth.
• Observability — Task status dashboards, DLQ depth alerting, canary tasks, and execution latency metrics connect to Caching and Observability.
• Design patterns — The state machine pattern, lease-based locking, idempotency keys, and exponential backoff with jitter are fundamental patterns explored in Design Patterns.
• Deployment — Blue-green deployments for worker code updates, draining in-flight tasks, and zero-downtime deploys connect to Networking and Deployment.
• Cloud service patterns — Step Functions for workflow orchestration, EventBridge Scheduler for managed cron, SQS for task queuing with native DLQ support, and the “buy vs build” decision framework for task scheduling are AWS-specific patterns explored in Cloud Service Patterns.

​

Questions You Should Ask the Interviewer

​

Requirements You Should Lock Down

• Send notifications across four channels: push (iOS + Android), email, SMS, and in-app
• Support priority levels: critical (immediate), high (within 1 minute), normal (within 5 minutes), low (batched hourly)
• Respect user channel preferences (opt-in/opt-out per channel per notification type)
• Deduplicate notifications within a configurable time window (default: 1 hour)
• Rate limit per-user per-channel (e.g., max 5 push notifications per hour for marketing)
• Notification templates with variable substitution and localization support
• Delivery tracking: sent, delivered, opened, clicked

• Deliver critical notifications within 10 seconds
• Handle 1 billion notifications per day (normal load), 10 billion during peak events
• 99.9% delivery rate (at-least-once per channel)
• Graceful degradation if one channel provider is down (do not block other channels)

​

Back-of-Envelope Calculation

Assumptions:
  Total notifications/day:         1 billion (normal), 10 billion (peak)
  Channel distribution:
    Push:    40% = 400M/day
    In-app:  30% = 300M/day
    Email:   20% = 200M/day
    SMS:     10% = 100M/day (most expensive, reserved for critical)

Throughput:
  1B / 86,400                      ~ 11,600 notifications/sec (average)
  Peak (10x):                      ~ 116,000 notifications/sec

Per-channel peak throughput:
  Push:   ~46,000/sec
  In-app: ~35,000/sec
  Email:  ~23,000/sec
  SMS:    ~12,000/sec

Storage (notification history, 90-day retention):
  1B/day x 90 days x 500 bytes     = ~45 TB
  (notification ID, user_id, type, channel, status, timestamps, metadata)

User preferences store:
  500M users x 1 KB preferences     = 500 GB
  (channel prefs, notification type prefs, quiet hours, locale)

Deduplication window:
  Track last 1 hour of notification hashes per user
  500M users x avg 10 notifications/hour x 32 bytes hash = ~160 GB
  → Fits in a Redis cluster

​

Component Architecture

┌─────────────────────────────────────────────────────────────────────────┐
│                      Notification System                                 │
│                                                                         │
│  ┌──────────┐    ┌────────────────┐    ┌──────────────────┐             │
│  │ Services │───▶│ Notification   │───▶│  Validation &    │             │
│  │ (callers)│    │ API            │    │  Enrichment      │             │
│  └──────────┘    └────────────────┘    └────────┬─────────┘             │
│                                                  │                       │
│                                          ┌───────▼────────┐             │
│                                          │  Priority       │             │
│                                          │  Router         │             │
│                                          └───────┬────────┘             │
│                           ┌──────────────────────┼──────────────┐       │
│                           │                      │              │       │
│                    ┌──────▼──────┐    ┌──────────▼──┐   ┌──────▼─────┐ │
│                    │  Critical   │    │  Normal     │   │  Low       │ │
│                    │  Queue      │    │  Queue      │   │  Queue     │ │
│                    └──────┬──────┘    └──────┬──────┘   └──────┬─────┘ │
│                           │                  │                 │       │
│                    ┌──────▼──────────────────▼─────────────────▼─────┐ │
│                    │           Channel Dispatcher                     │ │
│                    │  ┌────────┐ ┌───────┐ ┌──────┐ ┌────────────┐  │ │
│                    │  │  Push  │ │ Email │ │ SMS  │ │  In-App    │  │ │
│                    │  │ Worker │ │Worker │ │Worker│ │  Worker    │  │ │
│                    │  └───┬────┘ └───┬───┘ └──┬───┘ └─────┬──────┘  │ │
│                    └──────┼──────────┼────────┼────────────┼─────────┘ │
│                           │          │        │            │           │
│                    ┌──────▼──┐ ┌─────▼──┐ ┌──▼─────┐ ┌───▼────────┐ │
│                    │APNs/FCM│ │SES/    │ │SNS/   │ │WebSocket  │ │
│                    │        │ │Sendgrid│ │Twilio │ │/SSE       │ │
│                    └────────┘ └────────┘ └───────┘ └───────────┘ │
│                                                                         │
│  ┌──────────────────────┐  ┌────────────────────┐                       │
│  │  User Preferences    │  │  Dedup + Rate      │                       │
│  │  Service             │  │  Limiter           │                       │
│  └──────────────────────┘  └────────────────────┘                       │
└─────────────────────────────────────────────────────────────────────────┘

​

API Design

POST /api/v1/notifications
  Body: {
    "user_id": "user_123",
    "notification_type": "order_shipped",
    "priority": "high",
    "channels": ["push", "email"],       // Optional override; default from user prefs
    "template_id": "order_shipped_v2",
    "template_vars": {
      "order_id": "ORD-789",
      "tracking_url": "https://..."
    },
    "idempotency_key": "order-shipped-ORD-789",
    "schedule_at": null,                 // null = immediate, or ISO timestamp
    "aggregate_key": "post_likes:post_456"  // For batching similar notifications
  }

POST /api/v1/notifications/bulk
  Body: {
    "user_ids": ["user_123", "user_456", ...],
    "notification_type": "breaking_news",
    ...
  }

GET /api/v1/users/{user_id}/notifications
  Response: paginated list of in-app notifications

PATCH /api/v1/users/{user_id}/preferences
  Body: {
    "channels": { "push": true, "email": true, "sms": false },
    "quiet_hours": { "start": "22:00", "end": "07:00", "timezone": "America/New_York" },
    "notification_types": {
      "marketing": { "push": false, "email": true },
      "order_updates": { "push": true, "email": true, "sms": true }
    }
  }

​

Deep Dive 1: Priority-Based Routing and Queue Architecture

CRITICAL (P0): 2FA codes, security alerts, payment failures
  → SLA: < 10 seconds
  → Dedicated high-priority queue
  → Bypass rate limiting (but not dedup)
  → Never batched or aggregated

HIGH (P1): Order updates, direct messages, mentions
  → SLA: < 1 minute
  → Normal queue with priority ordering
  → Subject to rate limiting

NORMAL (P2): Social updates, content recommendations
  → SLA: < 5 minutes
  → Normal queue, processed after P0/P1
  → Subject to rate limiting and aggregation

LOW (P3): Marketing emails, weekly digests, surveys
  → SLA: < 1 hour
  → Batch queue, processed during off-peak hours
  → Heavily rate-limited, aggregated

Critical Queue (SQS FIFO or dedicated Kafka topic)
  → Dedicated worker pool (always running, never scaled down)
  → Independent of normal queue depth

Normal Queue (SQS Standard or Kafka topic, partitioned by channel)
  → Auto-scaling worker pool based on queue depth
  → Priority ordering within the queue if using Kafka (P1 before P2)

Batch Queue (SQS Standard with delayed visibility)
  → Workers process during configured windows
  → Aggregation happens before dispatch

​

Deep Dive 2: Deduplication and Idempotency

SET dedup:{idempotency_key} 1 EX 3600 NX
→ If SET succeeds (NX = only if not exists): process the notification
→ If SET fails (key already exists): return "already processed", skip

content_hash = SHA256(user_id + notification_type + template_id + key_vars)

Check: SISMEMBER user_dedup:{user_id} {content_hash}
→ If member exists: duplicate within the dedup window, skip
→ If not: SADD user_dedup:{user_id} {content_hash}
         EXPIRE user_dedup:{user_id} 3600

INCR aggregate:{user_id}:{aggregate_key}
EXPIRE aggregate:{user_id}:{aggregate_key} 300

If count == 1: start a 5-minute timer
If count > 1:  do nothing (timer is already running)

When timer fires:
  count = GET aggregate:{user_id}:{aggregate_key}
  Send single notification: "{count} people liked your post"
  DEL aggregate:{user_id}:{aggregate_key}

​

Deep Dive 3: User Preferences and Channel Selection

Channel Selection Algorithm:
1. Start with the requested channels (from API call)
2. If no channels specified, use defaults for this notification_type
3. Filter by user preferences:
   - Remove channels the user has opted out of globally
   - Remove channels the user has opted out of for this notification_type
4. Apply quiet hours:
   - If current time is within user's quiet hours:
     - CRITICAL: deliver anyway (2FA codes cannot wait)
     - HIGH: deliver push/in-app but defer email/SMS to end of quiet hours
     - NORMAL/LOW: defer all channels to end of quiet hours
5. Apply channel-specific rules:
   - SMS: only for critical and user-opted-in notification types (cost control)
   - Email: check bounce status; do not send to addresses that have bounced 3+ times
   - Push: check if user has a registered device token; fall back to in-app if not
6. Return the filtered list of channels to dispatch to

​

Deep Dive 4: Per-User Rate Limiting

Rate limits (configurable per notification_type):
  Push:  max 5 per hour for marketing, unlimited for critical
  Email: max 3 per day for marketing, max 10 per day total
  SMS:   max 2 per day total (cost control)
  In-app: unlimited (user controls their own inbox)

Implementation (sliding window counter in Redis):
  key = ratelimit:{user_id}:{channel}:{window}
  INCR key
  if first increment: EXPIRE key {window_seconds}
  if count > limit: reject (queue for later or drop based on priority)

​

LinkedIn’s Notification Infrastructure

• Unified notification platform: LinkedIn built a centralized notification service that all product teams use. Teams do not build their own notification dispatch — they call the platform API with a notification type, user ID, and template variables. The platform handles channel selection, preference filtering, rate limiting, dedup, and delivery. This centralization is critical: without it, different teams implement conflicting rate limiting logic and users get bombarded.
• Relevance scoring: Before dispatching, LinkedIn runs each notification through a relevance model that predicts whether the user will engage with it. Low-relevance notifications are silently dropped or downgraded to in-app only. This is a notification-specific ranking model similar to the feed ranking model — it considers the user’s historical engagement with this notification type, time of day, and current notification load.
• Volume capping: LinkedIn enforces strict per-user per-day limits across all notification types. Even if 50 different product features want to notify a user, the total push notification count per day is capped. This forces product teams to compete for notification “budget” and naturally selects for the most relevant notifications.
• Email digests: Rather than sending individual emails for every event, LinkedIn batches low-priority notifications into periodic digest emails (daily or weekly, based on user preference). The digest engine aggregates events, deduplicates, and selects the most relevant items for the digest. This reduces email volume by 10x while maintaining engagement.
• Delivery feedback loop: LinkedIn tracks open rates, click-through rates, and unsubscribe rates per notification type per channel. If a notification type’s engagement drops below a threshold, it is automatically flagged for review. If a user stops engaging with push notifications for 30 days, LinkedIn reduces push volume to that user. This closed-loop system prevents notification fatigue at scale.

​

WhatsApp Business Notifications

• Template-only messaging: Businesses can only send notifications using pre-approved message templates. This eliminates spam by design and ensures every notification the user receives is structured, relevant, and expected. Templates must be approved by WhatsApp before they can be used.
• Rate limiting by business quality: Each business account has a quality score based on user feedback (blocks, reports). High-quality businesses can send more notifications; low-quality businesses get throttled. This feedback-driven rate limiting is more sophisticated than simple request counting.
• Delivery windows: WhatsApp enforces a 24-hour conversation window. A business can only send template messages outside of a conversation window. Within a conversation (user has responded in the last 24 hours), the business can send free-form messages. This window-based approach balances business needs with user experience.

• Critical notifications (2FA) must still reach the user. Fall back to SMS for critical notifications when push delivery fails (check delivery receipt status from APNs/FCM within 30 seconds; if undelivered, escalate to SMS). For non-critical notifications, queue and retry when the provider recovers.
• Monitor APNs/FCM delivery rates. A sudden drop (from 98% to 50%) indicates a partial outage. Switch to the alternative channel (email) for high-priority notifications during the outage.

• Email providers throttle when you send too fast or your bounce rate spikes. Implement adaptive sending rate: start slow, increase until you hit the provider’s feedback signal (HTTP 429 or bounce rate > 2%). Back off and retry with exponential delay.
• Have a secondary email provider configured and ready. If the primary is throttled for more than 5 minutes, route email traffic to the secondary. This dual-provider setup costs negligibly more but provides critical redundancy.

• Without dedup, duplicate notifications will be sent. This is the worst outcome for SMS (costs money) and bad for user experience on all channels.
• Short-term: fall back to database-level dedup (check a dedup table in PostgreSQL with a unique constraint on idempotency_key). This is 10-100x slower but prevents duplicates.
• For SMS specifically: always check the database, not just Redis, before sending. The cost of a duplicate SMS (and potential regulatory issues) justifies the extra latency.

• The normal processing pipeline cannot handle 100x volume instantly. Implement backpressure: the notification API returns HTTP 202 (accepted, processing asynchronously) and queues all notifications. Workers process at their maximum sustainable rate.
• Prioritize by priority level: critical notifications process first, marketing notifications are automatically deferred during high-volume events.
• Auto-scale workers based on queue depth. Set CloudWatch alarms for queue depth and use ECS Service Auto Scaling or Lambda concurrency to add capacity within minutes.

• Notifications already in the queue were evaluated against old preferences. When the channel worker processes the notification, it does a final preference check just before dispatch. This “double-check” pattern ensures the user’s latest opt-out is respected, even if the notification was queued before the preference change.
• This adds one Redis/DB read per dispatch but prevents the most common user complaint: “I opted out but still received a notification.”

• The user preferences model expands from simple opt-in/opt-out to a regulatory rules engine. Each country has a profile: Canada requires explicit opt-in for marketing SMS (CASL), Germany has strict quiet hours (no marketing before 8 AM or after 9 PM local time, GDPR), India requires a DND (Do Not Disturb) registry check before sending SMS. The channel selection algorithm from the original design becomes: apply country-specific rules AFTER user preferences, not before. This means you need the user’s country of residence (not just their current location) and a regulatory rules database that is updated by your legal team. The notification API should reject requests that violate country-specific rules, returning a clear error to the caller.

• Webhooks add a new “channel” with unique failure characteristics: the destination URL may be slow, unreliable, or completely down. You need per-webhook retry policies with exponential backoff, a circuit breaker per webhook URL (if it fails 5 times in a row, stop trying and alert the customer), and a webhook delivery log that customers can inspect. Webhook payloads must be signed (HMAC-SHA256) so the receiver can verify authenticity. The webhook delivery infrastructure is essentially a separate system from the notification system — it looks more like a task scheduler with per-destination queues.

• SMS cost optimization: (1) Replace SMS with push notifications wherever possible — push is free, SMS costs $0.01-$0.05 per message. For any notification where the user has push enabled, never send SMS. (2) Batch low-priority SMS into daily digests. Instead of 5 separate SMS for 5 order updates, send one SMS at end of day: “You had 5 order updates today. Check the app for details.” (3) Use short codes and toll-free numbers (cheaper per-message than long codes). (4) Negotiate volume discounts with your SMS provider — at $1.2M/year, you have leverage. (5) Implement SMS verification before sending: if a phone number has bounced 3 times, remove it from the SMS channel. Each of these is a real optimization used by companies like Uber and DoorDash.

• This adds an inference step to the notification pipeline: before template rendering, the system calls an LLM (or a fine-tuned small model) to generate personalized content. Latency implications: an LLM call adds 200ms-2s per notification. For critical notifications (2FA), skip personalization. For marketing notifications, batch the LLM calls — generate personalized content for a cohort of users in bulk, then dispatch. The LLM call must be in the non-blocking path (after queuing, before dispatch), not in the API request path. Content moderation of LLM-generated text is non-negotiable — every generated message must pass through a toxicity filter before sending. This is how LinkedIn and Spotify personalize notification copy at scale.

• APIs and HTTP — RESTful API design for the notification endpoint, webhook delivery patterns, and HTTP status codes (202 Accepted for async processing) are covered in APIs and Databases.
• Messaging and queues — Priority queues, dead-letter queues, at-least-once delivery guarantees, and the fan-out dispatch pattern connect to Messaging, Concurrency, and State.
• Databases — DynamoDB for user preferences and notification history, partition key design for time-series notification data, and the trade-off between Redis and DynamoDB for dedup storage connect to Database Deep Dives.
• Caching — Redis for dedup state, user preference caching with TTL-based invalidation, and template caching connect to Caching and Observability.
• Reliability — Multi-provider failover for SMS/email, graceful degradation when a channel is down, and the “double-check” pattern for preferences connect to Reliability Principles.
• Security — Notification opt-out compliance (CAN-SPAM, GDPR, TCPA), secure delivery of sensitive content (2FA codes), and rate limiting as abuse prevention connect to Auth and Security.
• Real-time systems — In-app notification delivery via WebSocket, presence-aware channel selection (push to online users, email to offline users), and real-time delivery tracking connect to Real-Time Systems.
• Distributed systems theory — Deduplication in distributed systems (idempotency guarantees across retries), exactly-once delivery semantics, and the CAP theorem implications for the preference cache connect to Distributed Systems Theory.
• Cloud service patterns — SNS for push notifications, SES for email, Pinpoint for SMS, SQS for priority queuing, and the cost optimization strategies for high-volume notification delivery are AWS-specific patterns explored in Cloud Service Patterns.

​

Question

​

Strong Answer

• Fan-out on write means when a user publishes a post, you immediately push that post ID into every follower’s pre-computed feed cache (typically a Redis sorted set). The read path becomes trivially fast — just read from the cache. The cost is write amplification: one post from a user with 1,000 followers generates 1,000 writes. For a system where the vast majority of users have a few hundred followers, this is the correct default because reads outnumber writes by 10-100x, and you want reads to be sub-50ms.
• Fan-out on read means you store posts per-author and at read time you query all followed authors, merge their posts, rank, and return the top N. There is zero write amplification — one post is one write. But the read path is expensive: if I follow 300 users, the system must scatter-gather 300 queries, merge-sort the results, and return. At scale, this is too slow for a good user experience (500ms+ for a feed load).
• The decision breaks down at the celebrity boundary. A user with 10 million followers posting once means 10 million cache writes. During peak events — an election, a Super Bowl halftime tweet — that can mean hundreds of millions of writes in a burst that backs up your fan-out queue by minutes or hours. This is exactly the problem Twitter faced publicly. The solution is a hybrid: fan-out on write for normal users (say, under 10K followers), and fan-out on read for celebrities. At read time, you merge the pre-computed feed with a small number of celebrity post lookups. The threshold should be dynamic based on current system load — during peak traffic, lower the threshold to reduce write pressure.
• Real-world example: Facebook, Twitter/X, and Instagram all converged on this hybrid approach independently. Twitter documented their migration from pure fan-out-on-write to hybrid around 2012-2013 specifically because of the celebrity problem. The fact that three of the largest feed systems arrived at the same architecture is strong evidence that the hybrid is the correct design for this problem class.

​

Follow-up: How do you decide the exact follower threshold for switching from push to pull?

• During normal load, you might fan out for users with up to 50K followers because the queue has spare capacity.
• During a traffic spike (breaking news, sporting event), you lower the threshold to 5K or even 1K to protect the fan-out workers from falling behind.
• The simplest implementation is a single configuration value that the fan-out service reads each batch: MAX_FANOUT_FOLLOWERS. Monitor Kafka consumer lag — when lag exceeds 5 minutes, automatically lower the threshold. When lag returns to normal, raise it.
• A more sophisticated approach uses a cost function: fanout_cost = follower_count * current_queue_depth_factor. If the cost exceeds a budget, defer to read-time merge. This makes the system self-tuning.

​

Follow-up: What happens to the user experience during the transition period when you change the threshold?

• Users who follow someone with 20K followers were previously getting that person’s posts via their pre-computed feed cache. Now that person is suddenly treated as a “celebrity” and their posts must be merged at read time.
• If the feed service does not know to look up this author’s posts, they simply disappear from the feed until the next full read-time merge.
• The fix: maintain a per-user “celebrity list” that is updated when the threshold changes. When a user’s feed is fetched, the Feed Service checks both the pre-computed cache AND the celebrity list. The celebrity list is rebuilt periodically or on threshold change.
• There is also a cache warming concern: when you raise the threshold back, posts from those users need to be fanned out again. You do not retroactively fan out old posts — you start from the next post. Users may see a slight discontinuity in their feed timeline. In practice, this is barely noticeable because feed ranking surfaces the most relevant content regardless of delivery mechanism.

​

Going Deeper: How would you handle the edge case where a normal user suddenly goes viral (10 followers yesterday, 5 million followers today)?

• Detection: Run a periodic job (every 5-10 minutes) that checks follower counts against the current threshold. Flag users who have crossed the threshold as “newly promoted” celebrities.
• Transition: Stop fan-out for the newly promoted user immediately. Their future posts use the pull model. Existing posts already in followers’ caches remain there (no need to remove them).
• The dangerous window: If the user posts during the time between crossing the threshold and detection (up to 10 minutes), the fan-out service attempts to push to millions of followers. This is exactly the kind of burst that can back up the queue. Mitigation: add a pre-flight check in the fan-out worker itself — before processing a fan-out event, re-check the author’s current follower count. If it now exceeds the threshold, skip the fan-out and let the read path handle it. This adds one extra lookup per fan-out event but protects against the race condition.
• WhatsApp and Telegram sidestep this entirely by not having a public feed — every message is point-to-point or to a defined group. The viral celebrity problem is unique to open social graphs.

​

Question

​

Strong Answer

• Second 0 — Redis dies. The application servers’ Redis clients start getting connection refused errors or timeouts. How quickly they detect this depends on the client configuration — a health check interval of 1-2 seconds with a connection timeout of 500ms means detection within 2-3 seconds.
• Seconds 1-3 — Cache misses begin. Every redirect request that would have been a cache hit now falls through to the database. Latency jumps from ~5ms (cache hit) to ~20-50ms (database read). Users probably do not notice yet because 50ms is still fast for a redirect.
• Seconds 3-10 — Thundering herd risk. Here is where it gets dangerous. If your system processes 350K reads/sec at peak and your cache hit rate was 99%, that means only ~3,500 reads/sec were hitting the database. Now ALL 350K reads/sec hit the database simultaneously. A typical PostgreSQL instance handles ~10K TPS, a DynamoDB table in on-demand mode scales up but not instantly. You are looking at a potential 100x spike to the database.
• The mitigation that matters: request coalescing (also called collapsed forwarding). If 1,000 requests for the same popular short URL arrive within a 100ms window, only ONE request hits the database. The other 999 wait for that single query to return and share the result. This is not a theoretical optimization — it is the difference between your database surviving and falling over. Libraries like singleflight in Go or similar patterns in other languages implement this.
• Seconds 10-30 — Stabilization. With request coalescing, the database load is manageable but elevated. Latency is higher than normal (50-100ms per redirect instead of 5ms). You are degraded but functional. The monitoring system fires alerts for the Redis outage and elevated database latency.
• Recovery plan: Do NOT just restart Redis and let it fill up organically. A cold cache with 350K reads/sec means the database stays under heavy load for potentially hours while the cache warms. Instead, run a cache warming script that pre-loads the top 20% of URLs by access frequency (this 20% generates 80% of traffic). You can derive this from access logs or a pre-computed popularity ranking. Load these into Redis before routing traffic back to it. Then switch traffic back to the cache-first path. The warm-up should take minutes, not hours.
• From the user’s perspective: Redirects were maybe 30-50ms slower for a few minutes. They almost certainly did not notice. This is the power of graceful degradation — the system got worse, not broken.

​

Follow-up: What if it is not a total Redis failure but a partial one — say, 1 out of 3 Redis cluster nodes goes down?

• With Redis Cluster, each node owns a subset of the hash slots (the keyspace). When one node dies, all keys on that node become inaccessible. The other two nodes continue serving their keys fine.
• This means some short URLs resolve instantly from cache (their keys are on healthy nodes) and others are slow (their keys were on the dead node). The inconsistency is invisible to monitoring that only tracks averages — your average latency might look fine while one-third of users experience degraded performance.
• Detection: track cache hit rate per node or per hash slot range, not just globally. A sudden drop from 99% to 66% is the signature of a single-node failure in a 3-node cluster.
• Redis Cluster has automatic failover (if you have replicas configured): the replica of the failed master gets promoted to master within 10-30 seconds. During the failover window, requests for keys on that shard fail. Your application code should handle this with a fallback to database read — the same cache-miss path, but triggered by a Redis error rather than a cache miss.
• The lesson: always configure at least one replica per master in a Redis Cluster. The cost is 2x the memory, but the availability improvement is enormous.

​

Follow-up: How would you design the cache warming script? What are the pitfalls?

• Data source: You need to know which URLs are “hot.” Options: (1) maintain a real-time access counter in the database or a separate analytics system, (2) parse recent access logs, or (3) use the previous cache contents if you have periodic snapshots (Redis RDB dumps). Option 1 is most reliable. Option 3 is fastest but only works if you have regular backups.
• Pace the warming: If you dump 20 million key-value pairs into Redis as fast as possible, you saturate Redis’s network bandwidth and CPU during the load. Rate-limit the warming to ~50K writes/sec (about half Redis’s capacity) so the node can simultaneously serve live traffic.
• Stale data risk: The warming script reads from the database, but URLs may have been created, modified, or expired since the data was read. For a URL shortener this is low risk (URLs are mostly immutable), but for a system with mutable data, you need to validate freshness. Set a short TTL on warmed entries (say, 5 minutes) so stale entries expire quickly and get refreshed from the database.
• The biggest pitfall: warming the cache while traffic is still hitting the database. You need to coordinate the cutover — warm the cache, then redirect traffic to use it. If traffic starts using the cache while it is only 10% warmed, you get a 90% miss rate, which is barely better than no cache.

​

Question

​

Strong Answer

• At-most-once: Fire and forget. Send the message, do not retry. If the message is lost, it is gone. Simple and fast, but lossy. Use case: logging, metrics collection, non-critical analytics events. You accept that some data is lost.
• At-least-once: Send the message, wait for an acknowledgment. If you do not receive the ack within a timeout, retransmit. The problem: the receiver may have processed the message and sent the ack, but the ack was lost. You retransmit, and the receiver processes it again. You get duplicates. Use case: anything where losing a message is unacceptable (payment processing, task execution, order fulfillment). You accept potential duplicates and design for them.
• Exactly-once: Each message is processed exactly one time. No duplicates, no losses. Sounds ideal, but here is why it is effectively impossible in an unreliable network.

• The practical equivalent: At-least-once delivery plus idempotent processing. You guarantee the message is delivered at least once (with retries), and you guarantee that processing it multiple times has the same effect as processing it once. The receiver maintains a deduplication table — when it processes a message, it records the message ID. On subsequent deliveries, it checks the ID and skips reprocessing. From the outside, this looks like exactly-once, which is why Kafka calls its consumer semantics “exactly-once” — it is really at-least-once with built-in dedup and transactional writes.
• Real-world example: In the task scheduler, a worker picks up a “charge customer $50” task. It calls the payment API with an idempotency key. The payment succeeds. The worker tries to mark the task as COMPLETED, but the network times out. The zombie detector eventually re-enqueues the task. Another worker picks it up and calls the payment API with the same idempotency key. The payment system recognizes the key and returns the original result without charging again. From the customer’s perspective, they were charged exactly once.

​

Follow-up: How does Kafka achieve what it calls “exactly-once semantics” if true exactly-once is impossible?

• Kafka achieves exactly-once within the Kafka ecosystem by combining three mechanisms: idempotent producers (each message has a sequence number, the broker deduplicates), transactional writes (a producer can write to multiple partitions atomically), and transactional consumers (a consumer reads and writes offsets in the same transaction).
• What this means concretely: a Kafka Streams application that reads from topic A, processes the message, and writes to topic B will do so exactly once — even if the consumer crashes and restarts. The offset commit and the output write happen in the same transaction.
• What this does NOT mean: if your Kafka consumer calls an external system (sends an email, writes to a database, calls an API), Kafka has no way to make that external call idempotent. If the consumer crashes after calling the external system but before committing the offset, the message will be reprocessed and the external system will be called again. Exactly-once only applies to the Kafka-to-Kafka path.
• This is why the task scheduler design combines at-least-once delivery with application-level idempotency keys — because the “task” typically involves calling external systems where Kafka’s transactional guarantees do not extend.

​

Follow-up: What are the performance implications of idempotency? It sounds like you need a lookup on every operation.

• Every idempotent operation requires a read-before-write: check the dedup table, then execute if the key is new. This doubles the number of I/O operations on the critical path.
• The dedup table grows over time: if you process 56 million tasks per day and store idempotency keys for 7 days, you have ~400 million entries in the dedup table. At ~50 bytes per entry, that is ~20 GB — easily fits in Redis or a dedicated DynamoDB table.
• TTL is essential: idempotency keys should expire after a reasonable window (1 hour to 7 days depending on the use case). Without TTL, the dedup table grows unbounded. The TTL must be longer than the maximum retry window — if your retry policy allows retries for up to 1 hour, the idempotency key must live for at least 1 hour.
• In practice, the overhead is minimal: the dedup check is a single key lookup in Redis or DynamoDB (~1ms). Compared to the task execution itself (seconds to minutes), 1ms of overhead is negligible. The correctness guarantee is worth far more than the performance cost.
• Where it gets expensive: high-throughput, low-latency systems where every microsecond matters (trading systems, game servers). In those cases, you might accept at-most-once for non-critical operations and reserve idempotent at-least-once for operations that must not be duplicated (trades, inventory decrements).

​

Question

​

Strong Answer

• Concrete example: In the chat system, conversation_id is the partition key. Most conversations have a few hundred messages per day. But a group chat for a 500-person company channel might receive 50,000 messages per day — all hitting the same partition. That single partition is handling 100x the load of an average partition.
• Another example: In DynamoDB, each partition supports ~3,000 Read Capacity Units and ~1,000 Write Capacity Units per second. If a celebrity’s user feed receives 10,000 reads/sec, a single partition cannot handle it, regardless of how much total capacity you have provisioned.

• DynamoDB: Use CloudWatch Contributor Insights, which identifies the most-accessed partition keys. It shows the top N partition keys by read/write volume over a time window. If one key accounts for more than 10% of total traffic, that is a hot partition.
• Cassandra: Monitor per-partition read/write latencies using nodetool cfstats or through your monitoring system (Prometheus with Cassandra exporter). Look for P99 latency spikes that are localized to specific nodes. The nodetool toppartitions command samples and reports the most accessed partitions.
• General approach: Instrument your application to log partition key access patterns. Aggregate in your analytics pipeline and set alerts for skew beyond a threshold (e.g., any single key exceeding 5x the average).

• Write sharding (adding a suffix): Append a random suffix to the partition key. Instead of conversation_id = "chat_ABC", use conversation_id = "chat_ABC#3" (where 3 is a random number from 0-9). This spreads writes across 10 partitions. The cost: reads must scatter-gather across all 10 sub-partitions and merge results. This is the standard DynamoDB pattern for handling hot keys.
• Time-based sub-partitioning: For the chat system specifically, use (conversation_id, year_month) as a composite partition key. Current messages go to the current month’s partition; historical queries read from older partitions. This naturally distributes the growing dataset and keeps the “hot” partition (current month) manageable.
• Caching the hot partition: Put a cache (Redis, DAX) in front of the hot partition. If a celebrity’s profile is accessed 10K times per second, cache it in Redis and let 99% of reads hit the cache. Only 1% (100 reads/sec) reach the database partition.
• Application-level routing: If you know certain entities will always be hot (celebrity accounts, viral posts), route them to a dedicated, scaled-up data store separate from the main database. This is effectively application-level sharding by hotness.

​

Follow-up: In DynamoDB specifically, does adaptive capacity solve the hot partition problem, or do you still need to worry about it?

• Adaptive capacity allows DynamoDB to reallocate unused throughput from cold partitions to hot ones. If you have 10,000 RCUs provisioned across 10 partitions and one partition needs 5,000 RCUs while the others need 500 each, adaptive capacity can handle that redistribution.
• However, there are hard limits. A single partition cannot exceed its per-partition throughput limits (~3,000 RCU, ~1,000 WCU), regardless of adaptive capacity. If your hot partition genuinely needs 10,000 RCUs, adaptive capacity cannot help — you need write sharding or a cache.
• DynamoDB’s on-demand mode is more generous with burst handling (up to 2x your previous peak), but the per-partition limits still apply.
• The practical implication: for most workloads, adaptive capacity means you do not need to worry about moderate hotspots. But for extreme hotspots (celebrity accounts, viral content, flash sales), you still need explicit mitigation strategies.

​

Follow-up: How would you design the partition key for a notification system where some users receive 100x more notifications than others?

• Option 1: User ID as partition key with write sharding: Use user_id#shard as the partition key, where shard is computed as hash(notification_id) % N. For high-volume users, set N=10; for normal users, N=1 (no sharding). The application knows each user’s shard count from a user metadata table.
• Option 2: Time-based partitioning: Use user_id#date as the partition key. Each day gets a new partition. This naturally bounds partition size and keeps recent notifications (the ones users actually read) on a small number of partitions.
• Option 3: Separate hot and cold storage: Keep the last 24 hours of notifications in a Redis sorted set per user (fast reads, no partition limits). Older notifications live in DynamoDB with time-based partitioning. Most notification reads are for recent items, so the Redis layer handles 95%+ of reads.
• In my experience, Option 2 is the best balance of simplicity and effectiveness. It works without requiring the application to track per-user shard counts, and it naturally gives you a retention/archival boundary (delete partitions older than 90 days).

​

Question

​

Strong Answer

• Under extreme contention (say, 100K requests/sec all hitting the same rate limit key for a popular API endpoint), the Lua script still works correctly because of Redis’s single-threaded model. Each script execution takes ~0.05-0.1ms. At 100K ops/sec, the total time spent executing Lua scripts for this key is ~5-10 seconds per second of wall-clock time — which is impossible. In practice, Redis pipelines and batches these, and the throughput limit is Redis’s overall ops/sec capacity (~100K-200K ops/sec for simple commands on a single instance), not per-key contention.
• The real bottleneck is network round-trips, not Lua execution. Each rate limit check requires one network round-trip from the API server to Redis (~0.5ms in the same AZ). At 100K requests/sec, that is 100K round-trips. If you have 10 API servers, each sends 10K requests/sec to Redis, which is well within Redis’s capacity.
• When Redis becomes the bottleneck: If you need more than ~200K rate limit checks per second, a single Redis instance is insufficient. Solutions: Redis Cluster (shard by rate limit key) or multiple Redis instances with client-side routing. Since rate limit keys are typically user_id:endpoint, the key distribution is naturally uniform across shards.

• Long-running Lua script blocks everything: Redis blocks all other commands while a Lua script runs. If your script has a bug (infinite loop) or does expensive operations (large ZRANGEBYSCORE), it blocks the entire Redis instance. Mitigation: keep Lua scripts minimal (ours is 6 lines), and set the lua-time-limit config (default 5 seconds) to kill runaway scripts.
• Memory growth: If you use sliding window log (storing every timestamp in a sorted set), a hot key can accumulate millions of entries. The Lua script that cleans up old entries (ZREMRANGEBYSCORE) runs in O(log N + M) where M is the number of removed entries. For very hot keys, this cleanup can be expensive. This is another reason to prefer the sliding window counter algorithm — it uses only two counters per window, not a growing sorted set.

• Local in-memory rate limiting: Each API server maintains its own token bucket per user. No network round-trip, sub-microsecond latency. The trade-off: limits are enforced per-server, not globally. A user hitting 10 different servers gets 10x the effective limit. Use this as a secondary defense layer alongside Redis, or as a fallback when Redis is down.
• Envoy/Istio rate limiting in the service mesh: The sidecar proxy handles rate limiting with its own shared state (typically backed by Redis). The advantage is that rate limiting is decoupled from application code.
• Cell-based rate limiting (Cloudflare’s approach): Each edge node limits independently and periodically synchronizes counts to a coordination layer. Gives approximate global enforcement with zero cross-node latency for the check itself.

​

Follow-up: How would you implement a sliding window counter in Redis using Lua, and why does it beat the sorted set approach at scale?

• Maintain two keys per rate limit: counter:{key}:{current_window} and counter:{key}:{previous_window}. Each is a simple integer counter with a TTL equal to 2x the window size.
• When a request arrives, the Lua script calculates the weighted count: weighted = previous_count * (1 - elapsed_fraction_of_current_window) + current_count. If weighted is under the limit, increment the current window counter and allow.
• Total Redis memory per rate limit: 2 keys with integer values — roughly 100 bytes. Compare that to the sorted set approach where you store a timestamp per request: 100 requests/minute per user means 100 entries of ~32 bytes each = 3,200 bytes. At 10 million users, that is 32 GB for sorted sets vs 1 GB for sliding window counters. A 32x memory reduction.
• The accuracy trade-off: the sliding window counter is an approximation. It assumes requests in the previous window were uniformly distributed, which may not be true if traffic is bursty within a window. In practice, the error is less than 1%, which is acceptable for all but the most precise rate limiting needs (financial transaction limits).

​

Follow-up: If Redis is unavailable and you fail-open, how do you prevent abuse during the outage window?

• Local rate limiters as secondary defense: Each API server runs a local in-memory token bucket. Set the local limit to 10x the normal per-user limit (generous, to avoid false positives from traffic distribution unevenness). This catches obvious abuse (thousands of requests/sec from one user) even without Redis.
• Monitor and respond: Alert immediately on Redis failure. The average Redis recovery (with Sentinel or Cluster auto-failover) is 15-30 seconds. During this window, the local rate limiter is your only defense.
• Post-incident analysis: After Redis recovers, run an anomaly detection query on access logs during the outage window. Identify users who significantly exceeded their normal rate. Take retroactive action (warn, temporarily restrict) if abuse is detected.
• Circuit breaker with delayed close: After Redis comes back, do not immediately trust it. Use a circuit breaker that transitions from open (fail-open) to half-open (test Redis with a canary key every second) to closed (normal operation) over 30-60 seconds. This prevents thrashing if Redis is flapping.

​

Question

​

Strong Answer

• A typical server handles ~10K-50K concurrent WebSocket connections depending on the language runtime and how much processing happens per message. At 10K per server, you need 500 servers. At 50K per server (Erlang, Go, or optimized Node.js), you need 100 servers.
• Use a Network Load Balancer (Layer 4), not an Application Load Balancer (Layer 7), for WebSocket connections. NLB passes through TCP connections directly, adding minimal overhead. ALB terminates and re-establishes connections, adding latency and memory overhead.
• Connection assignment is typically random (NLB round-robin or least-connections). There is no need for sticky sessions at the LB level because the routing table (below) handles message delivery.

• When a user connects, the Chat Server registers the mapping user_id -> server_id in a shared store (Redis hash map). When the user disconnects, the mapping is removed.
• This routing table is the single most critical piece of infrastructure. Every message delivery starts with a lookup: “Which server holds User B’s connection?” The lookup must be sub-millisecond.
• Redis is ideal here: HSET connections user:B "chat-server-42" gives O(1) lookups. With 5 million entries at ~50 bytes each, the table is ~250 MB — trivially fits in memory.

1. User A sends a message via WebSocket to Chat Server 1.
2. Chat Server 1 persists the message to the Message Store (Cassandra).
3. Chat Server 1 looks up User B’s server: HGET connections user:B returns chat-server-3.
4. Chat Server 1 publishes the message to a Redis Pub/Sub channel that Chat Server 3 subscribes to. Alternatively, Chat Server 1 makes a direct gRPC call to Chat Server 3.
5. Chat Server 3 receives the message and pushes it to User B via the WebSocket connection.

• Redis Pub/Sub: Each Chat Server subscribes to a channel named after itself (e.g., channel:chat-server-3). Senders publish to the target server’s channel. Pros: decoupled, simple. Cons: Redis Pub/Sub is fire-and-forget (no persistence), so if a server misses a message (brief disconnection from Redis), the message is lost. Also, every Chat Server subscribes to its own channel, so Redis maintains 500 subscriptions — lightweight.
• Direct gRPC: Chat Servers call each other directly via gRPC using the routing table. Pros: point-to-point, no broker, lower latency. Cons: creates O(N^2) potential connections between servers, and requires service discovery.
• My recommendation: Redis Pub/Sub for simplicity. The fire-and-forget limitation is mitigated because messages are already persisted to Cassandra before routing. If a message is lost in Pub/Sub, the recipient client’s reconnection logic catches up from the database.

​

Follow-up: What happens when a Chat Server crashes and 10K users need to reconnect?

• 10K clients detect the disconnection (TCP reset or heartbeat timeout) and trigger their reconnection logic. If they all reconnect immediately, the load balancer distributes 10K new connection requests across remaining servers in a burst.
• Client-side mitigation: exponential backoff with jitter. Each client waits random(0, min(2^attempt * 100ms, 30s)) before reconnecting. This spreads the 10K reconnections over 10-30 seconds instead of hitting all at once.
• Server-side: When a client reconnects (to a different server now), it sends its last received message ID. The new server fetches all messages since that ID from Cassandra and pushes them. This “catch-up” ensures zero message loss.
• Routing table cleanup: The dead server’s entries in the routing table become stale. The stale entries will cause message delivery to fail (publishing to a Pub/Sub channel nobody subscribes to). Two cleanup strategies: (1) set a TTL on routing entries and refresh with heartbeats, or (2) have each Chat Server periodically validate its own entries on startup and remove stale ones from the previous instance.
• Capacity headroom: This is why you should not run Chat Servers at 100% connection capacity. If each server handles 10K connections and you have 500 servers, you are at 100% capacity — a single server failure means 10K users cannot reconnect (all other servers are full). Run at 80% capacity (servers handle 8K each), leaving 20% headroom for redistributing connections during failures.

​

Follow-up: How would you handle the routing table during a Redis outage?

• Short-term (seconds): Chat Servers cache a local copy of recent routing lookups. If Server 1 recently looked up that User B is on Server 3, it uses the cached result. This works for ongoing conversations but fails for new conversations.
• Fallback broadcast: If the routing table is unavailable, fall back to broadcasting the message to ALL Chat Servers. Each server checks if it holds the recipient’s connection and delivers if yes, ignores if no. This is O(N) where N is the number of servers, which is expensive but functional. At 500 servers, you are sending 500 messages instead of 1 for each chat message — a 500x overhead. Acceptable for a brief outage, catastrophic if prolonged.
• Redis HA: This is why the routing table must be in a highly available Redis setup (Sentinel with automatic failover, or Redis Cluster with replicas). Target recovery time: under 15 seconds. The broadcast fallback covers the gap.
• Alternative: Use a consistent hashing ring to deterministically assign users to servers. No routing table needed — you compute server = hash(user_id) % N. The problem: rebalancing when servers are added or removed causes mass disconnection and reconnection. Consistent hashing minimizes this (only ~1/N users are affected), but it is still disruptive. Most production systems prefer the routing table approach for its flexibility.

​

Question

​

Strong Answer