System Design interview questions and answers

User types: www.codejump.io
     ↓
DNS Resolver asks: "What IP is codejump.io?"
     ↓
DNS returns: 76.76.21.21
     ↓
Browser connects to: 76.76.21.21

┌─── Server 1
Client ──▶ Load     │
           Balancer ├─── Server 2
                    │
                    └─── Server 3

Without cache:
Request → API → Database (50ms) → Response

With cache:
Request → API → Cache HIT (1ms) → Response
                Cache MISS → Database (50ms) → Store in cache → Response

HTTP:  Client ──plaintext──▶ Server   (anyone can read)
HTTPS: Client ──encrypted──▶ Server   (only client & server can read)

Vertical scaling (Scale Up):
  Server: 4 CPU, 16 GB RAM
       ↓
  Server: 32 CPU, 128 GB RAM
  (same machine, more powerful)

Horizontal scaling (Scale Out):
  1 server
       ↓
  3 servers behind a load balancer
  (more machines, same spec)

GET    /challenges         → list challenges
GET    /challenges/:id     → get one challenge
POST   /challenges         → create a challenge
PATCH  /challenges/:id     → update a challenge
DELETE /challenges/:id     → delete a challenge

TTL = 1 second  → near real-time data, but 1 DB query per second per key
TTL = 10 min    → 10 min of potential staleness, but few DB queries
TTL = 24 hours  → max cache efficiency, data may be a day old

Vertical scaling:
  Server: 8 cores, 64 GB RAM → 64 cores, 512 GB RAM
  (Expensive, has physical limits)

Horizontal sharding:
  users table (100M rows) → Shard by user_id
  Shard 0: user_id 0..24M  → DB Server A
  Shard 1: user_id 25M..49M → DB Server B
  Shard 2: user_id 50M..74M → DB Server C
  Shard 3: user_id 75M..99M → DB Server D

Assumption: 100M photo uploads/day (Instagram's actual scale)

Daily storage:
  100M photos/day × 3 MB/photo
  = 300,000 TB/day
  = 300 TB/day

5-year storage:
  300 TB/day × 365 days × 5 years
  = 300 × 1,825
  = 547,500 TB
  ≈ 547 PB ≈ 550 PB

Without queue (tight coupling):
User submits code → API calls Judge0 → waits 3s → responds
                 ↳ If Judge0 is slow, API is slow
                 ↳ If Judge0 is down, request fails

With queue (decoupled):
User submits code → API puts job in queue → responds immediately (< 100ms)
                                Queue → Worker picks job → calls Judge0
                                      → stores result → notifies client via WS

The attack:
  searchTerm = "'; DROP TABLE products; --"
  
  Query becomes:
  SELECT * FROM products WHERE name = ''; DROP TABLE products; --'
  
  Executed as two statements:
  1. SELECT * FROM products WHERE name = ''   → no results (harmless)
  2. DROP TABLE products                        → DELETES ALL PRODUCTS! 💥
  -- comment ignores the trailing '

The fix — parameterized queries:
  // ❌ String interpolation — NEVER do this
  const query = `SELECT * FROM products WHERE name = '${searchTerm}'`;
  
  // ✅ Parameterized query (PostgreSQL)
  const result = await client.query(
    'SELECT * FROM products WHERE name = $1',
    [searchTerm]
  );
  // The DB treats $1 as data, never as SQL code
  // Input: "'; DROP TABLE products; --"
  // DB searches for a product literally named "'; DROP TABLE products; --"
  
  // ✅ With Prisma (ORM — always parameterized by default)
  const result = await prisma.product.findMany({
    where: { name: searchTerm } // safe
  });
  
  // ❌ Prisma raw — unsafe version
  await prisma.$queryRawUnsafe(`SELECT * FROM products WHERE name = '${searchTerm}'`);
  
  // ✅ Prisma raw — safe version with tagged template
  await prisma.$queryRaw`SELECT * FROM products WHERE name = ${searchTerm}`;

Bad shard key: country_code
  → Users in the US are 40% of all users
  → Shard for US handles 40% of all traffic
  → Massive hot shard!

Good shard key: user_id (hash-based)
  → Random distribution across shards
  → Each shard handles ~equal load

Concurrent streamers:
  200M × 5% = 10 million concurrent streams

Bandwidth:
  10,000,000 streams × 5 Mbps
  = 50,000,000 Mbps
  = 50,000 Gbps
  = 50 Tbps

50 Tbps is enormous — how does Netflix handle it?

Netflix's architecture:
  ~50 Tbps would overwhelm any single CDN.
  Solution: Netflix Open Connect — their own CDN.
  
  Netflix ISP partners: Netflix installs physical servers
  (Open Connect Appliances) inside ISPs.
  
  Traffic flows:
    Instead of: Netflix cloud → public internet → ISP → user
    It becomes:  Netflix OCA (inside ISP) → user
  
  ~95% of Netflix traffic is delivered from within ISPs,
  not from Netflix's own datacenters.
  Each OCA is a ~500TB disk array caching popular content.
  
  Peak internet bandwidth is roughly 500 Tbps total for all global traffic.
  Netflix at 50 Tbps = ~10% of global internet bandwidth.

-- Tables:
users:    id=1 Alice, id=2 Bob
orders:   user_id=1 (Alice's order), user_id=1 (Alice's order 2)
-- Bob has no orders

INNER JOIN (only matching rows):
SELECT u.name, o.id
FROM users u
INNER JOIN orders o ON o.user_id = u.id;
-- Result: Alice, order1 | Alice, order2
-- Bob is excluded (no matching order)

LEFT JOIN (all left rows + matches):
SELECT u.name, o.id
FROM users u
LEFT JOIN orders o ON o.user_id = u.id;
-- Result: Alice, order1 | Alice, order2 | Bob, NULL
-- Bob is included with NULL order

XSS types:

Reflected XSS:
  Malicious script in URL parameter → server echoes it back in response
  User must click a crafted link for it to execute
  Example: https://site.com/search?q=<script>alert(1)</script>

Stored (Persistent) XSS: ← our case
  Script stored in database → served to every visitor
  Most dangerous — no crafted link needed
  Our comment: stored once, executes for every user who loads the page

DOM-based XSS:
  Client-side JavaScript reads URL/hash and inserts it into the DOM
  Never reaches the server
  Example: page.html#<img src=x onerror=alert(1)>

Prevention:
  1. Output encoding (primary defense):
     React does this automatically for JSX expressions:
     <p>{comment.text}</p>  ← React HTML-encodes the text
     <script> becomes &lt;script&gt; → not executed
     
  2. Content Security Policy (CSP) header:
     Content-Security-Policy: script-src 'self'
     Blocks inline scripts even if injected
     
  3. Input sanitization for HTML fields:
     If users CAN write HTML (rich text editor), use DOMPurify:
     const clean = DOMPurify.sanitize(userHtml);
     
  4. HttpOnly cookie flag:
     Set-Cookie: session=xxx; HttpOnly
     Prevents document.cookie from reading session cookie
     (mitigates cookie theft even if XSS succeeds)

Why the naive query fails at scale:
  User follows 500 people, who collectively post 10,000 tweets/day
  Table size: 500M users × 500 follows = 250B rows in follows table
  tweets table: 500M DAU × 5 tweets/day = 2.5B tweets/day
  
  IN (500 follower IDs) → DB must:
  1. Execute the subquery (SELECT from 250B-row follows table)
  2. Use those IDs to filter the 2.5B-row tweets table
  3. Sort by time across results from 500 different authors
  
  Even with indexes: each user request = expensive multi-table join
  At 300M DAU requesting feeds every 5 minutes = 1M queries/second

Twitter's timeline table approach:
  CREATE TABLE user_timeline (
    user_id   BIGINT,     -- the reader's ID
    tweet_id  BIGINT,     -- the tweet to show
    created_at TIMESTAMP, -- for sorting (or use tweet_id as timestamp is encoded)
    PRIMARY KEY (user_id, tweet_id)
  );
  
  Feed request: SELECT tweet_id FROM user_timeline
                WHERE user_id = 123 ORDER BY created_at DESC LIMIT 20
  
  Single-table, indexed query on user_id → extremely fast
  Timeline rows are pre-populated by the fan-out service when tweets are created

Tweet data:
  Stored separately: tweet_id → tweet content
  Timeline table only stores IDs → small rows, fast I/O
  Content fetched in bulk: SELECT * FROM tweets WHERE id IN (20 tweet_ids)

Causal dependency chain:
  Alice writes comment C1: "great post!"    (event A)
  Bob reads comment C1                       (sees A)
  Bob writes reply C2: "Thanks!"            (event B — causally depends on A)

  Carol reads and sees C2 ("Thanks!") but NOT C1 ("great post!")
  → B without A is causally inconsistent → confusing!

Causal consistency guarantee:
  Operations are ordered by causality:
    writes are seen by others in the order that
    respects the "happened-before" relationship.

  If you see "Thanks!" (B), you must also see "great post!" (A)
  because B causally depends on A.

Implementation:
  Vector clocks: each write tagged with a version vector
  e.g., C1 = {alice: 1}, C2 = {alice: 1, bob: 1}
  
  Replicas only expose C2 after they've applied C1.

User A posts a tweet
  → Find all A's followers (N users)
  → Write to each follower's feed table
  
Read feed: SELECT * FROM feeds WHERE user_id = me LIMIT 20; → instant
Write tweet: 1 INSERT + N INSERT into feed tables → expensive for celebrities (10M followers)

Saga: Order Placement

Step 1: Inventory Service ── ReserveItems ──▶ SUCCESS
        publishes: ItemsReservedEvent

Step 2: Payment Service ── ChargeCard ──▶ SUCCESS
        publishes: PaymentCompletedEvent

Step 3: Shipping Service ── CreateShipment ──▶ FAILURE (address invalid)
        publishes: ShipmentFailedEvent

Compensation (reverse order):
  Payment Service receives ShipmentFailedEvent
  → Executes: RefundPayment (compensating transaction)
  → publishes: PaymentRefundedEvent

  Inventory Service receives PaymentRefundedEvent
  → Executes: ReleaseItems (compensating transaction)
  → Order is fully rolled back

Short polling (worst):
  Every 1s: Browser → GET /prices → Server responds immediately
  Overhead: 1 HTTP request + response per second per user
  At 10,000 users: 10,000 requests/second just for polling!

Long polling (better):
  Browser → GET /prices → Server holds connection open
  Server responds only when price changes
  Browser immediately sends another long-poll
  Overhead: lower, but complex server-side connection management

SSE (good for unidirectional push):
  Browser → GET /prices (persistent connection)
  Server sends: data: {"BTC": 65432}\n\n
  Server sends: data: {"BTC": 65501}\n\n
  Native browser support via EventSource API
  Automatic reconnect built-in
  Works over HTTP/2 (many SSE streams per connection)

WebSocket (best for bidirectional):
  Client ↔ Server (full-duplex, low overhead frames)
  Use when client also sends data (chat, collaborative editing, game input)

MTBF (Mean Time Between Failures): average time the system runs without failing
MTTR (Mean Time To Repair):        average time to restore after a failure

Availability = MTBF / (MTBF + MTTR)
             = 720 / (720 + 3)
             = 720 / 723
             ≈ 0.9958
             ≈ 99.58%

Architecture of a distributed web crawler:

1. Seed URLs → Frontier Queue (Redis list or Kafka topic)
   Contains: URLs to crawl next
   Priority: high-priority domains (news sites) ahead of others

2. Crawler Workers (N parallel workers):
   Loop:
     url = frontier.pop()
     if seen_filter.contains(url): skip  ← deduplication
     content = fetch_with_timeout(url, timeout=5s)
     respect_robots_txt(url, content)
     links = extract_links(content)
     store_content(url, content, timestamp)
     new_urls = filter_links(links, is_new=True)
     frontier.push(new_urls)
     seen_filter.add(url)

3. Deduplication — the core challenge:
   Approach 1: Hash set in Redis
     seen = redis.sadd("crawled", url) → 1 if new, 0 if seen
     1B URLs × 100 bytes/URL = 100 GB → too large for single Redis
     
   Approach 2: Bloom filter (space-efficient, probabilistic)
     1B URLs with 1% false positive rate → ~1.2 GB (vs 100 GB hash set)
     Tradeoff: 1% of pages might be skipped due to false positives (acceptable)
     Redis module: RedisBloom
   
   Approach 3: URL fingerprinting
     Normalize URL + hash to 64-bit integer
     Distribute fingerprints across sharded hash sets

4. Politeness (critical!):
   Crawlers must respect robots.txt
   Add delay between requests to same domain (1+ second)
   Respect Crawl-delay directive
   Identify as a bot in User-Agent header

Distributed work:
   Partition URLs by domain hash → each worker owns specific domains
   → No two workers crawl the same domain simultaneously
   → Natural politeness enforcement

Scenario with 2 replicas (R1 and R2), inventory = 1:

  User A reads R1: stock = 1 → adds to cart
  User B reads R2: stock = 1 → adds to cart (concurrent)

  Both writes committed locally on their respective replicas.
  Replication runs: conflict! Both decremented from 1.
  Final inventory: -1 (oversold)

Resolution strategies:

  1. Conflict detection + compensation:
     Detect oversell during order confirmation.
     Cancel one order; send apology email + coupon.
     Amazon uses this for inventory management.

  2. Last-writer-wins (LWW):
     Timestamp-based: whichever write is newer wins.
     One user's cart update is silently overwritten.
     Risk: data loss without notification.

  3. Vector clock merge:
     Application logic decides how to merge conflicting writes.
     Shopping cart: union of items (Amazon Dynamo paper approach).

  4. Conditional writes / Compare-and-swap:
     "UPDATE inventory SET stock = 0 WHERE stock = 1 AND ..."
     Only one of the two concurrent writes succeeds (atomic CAS).
     Turns eventual into optimistic locking — stronger guarantee.

Timeline:
t=0ms:  Write user.name="Alice" → Replica 1 updated
t=50ms: Read from Replica 2 → returns "Bob" (stale!) ← inconsistency window
t=100ms: Replica 2 receives update → now returns "Alice"

Token Bucket (10 req/s, burst capacity 20):

  Bucket: [●●●●●●●●●●●●●●●●●●●●] 20 tokens (full)

  User sends 15 requests in 0.1 seconds (burst):
    15 tokens consumed → bucket: [●●●●●] 5 tokens
    All 15 requests allowed! (burst capacity honored)

  Tokens refill: +10 tokens/second
  After 1.5 seconds: bucket is full again at 20

  User sends 30 requests in 0.1 seconds (too many):
    20 tokens consumed → bucket empty
    10 requests rejected with 429 Too Many Requests