Design Case Studies

1. Khung tư duy thiết kế hệ thống

Mỗi case study đi theo 8 bước:

1. Clarify requirements — functional (tính năng) + non-functional (scale, latency, reliability). Hỏi nhiều ở bước này.
2. Capacity estimation — DAU, QPS read/write, storage, bandwidth.
3. API design — endpoint chính, request/response shape.
4. Data model — schema cho top entity, ước lượng size.
5. High-level architecture — vẽ box và arrow. Bắt đầu đơn giản (1 server + 1 DB), scale dần.
6. Detailed design — sharding, cache layer, queue, replication.
7. Identify bottleneck — đâu là bottleneck đầu tiên khi load tăng 10×?
8. Discuss trade-offs — mỗi quyết định có cost.

2. Case 1: URL Shortener (Bit.ly / TinyURL)

2.1. Requirements

Functional:

• POST /shorten nhận long URL, trả short URL.
• GET /{shortCode} redirect đến long URL.
• Optional: custom alias, expiration, analytics (click count).

Non-functional:

• Read >> Write (100:1).
• Latency thấp cho redirect (~10ms).
• Highly available — link không bao giờ broken.
• Short code không đoán được (security).

2.2. Capacity

• 500M URL mới/tháng → 500M/30/86400 ≈ 200/s write avg, peak ~1000/s.
• Read 100× = 20k/s avg, peak ~100k/s.
• Storage: 500M × 12 tháng × 5 năm = 30B URL. Mỗi URL ~500 byte → 15TB.
• Hot data (URL được click thường xuyên): ~100GB → fit Redis cluster.

2.3. API

POST /api/v1/shorten
Authorization: Bearer <api_key>
{ "long_url": "https://example.com/very/long/path?q=1", "custom_alias": null, "expire_at": null }

201 Created
{ "short_url": "https://sho.rt/abc1234", "short_code": "abc1234" }

# Redirect
GET /abc1234

302 Found
Location: https://example.com/very/long/path?q=1

2.4. Short code generation — quan trọng nhất

3 strategies:

2.4.a. Hash long URL (MD5/SHA, take 7 char)

(+) Deterministic — cùng URL = cùng short. (−) Collision có thể; cần check + retry. Conflict tăng theo time.

2.4.b. Random Base62 (a-zA-Z0-9, 7 chars = 62^7 ≈ 3.5T combination)

(+) Đơn giản, không đoán được. (−) Collision → check DB + retry. (−) Khó scale ngang nếu collision frequent.

2.4.c. Counter-based với Base62 encoding (Recommended)

Distributed counter (Snowflake-like, hoặc DB sequence) → Base62 encode → unique guaranteed.

// Snowflake-like ID: 64 bit
// [timestamp 41 bit][machine 10 bit][seq 12 bit]
// Capacity: 4096 ID/ms × 1024 machine = 4M ID/ms

const id = generateSnowflake();   // bigint unique
const shortCode = base62(id);     // "abc1234" (7 char ≈ enough)

function base62(n: bigint): string {
  const chars = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ';
  let result = '';
  while (n > 0n) {
    result = chars[Number(n % 62n)] + result;
    n /= 62n;
  }
  return result;
}

Vấn đề: counter sequential → predictable. Có thể obscure bằng pre-generated pool randomized, hoặc chỉ Base62 + thêm checksum.

2.5. Architecture

2.6. Data model

-- Postgres
CREATE TABLE urls (
  id            BIGINT PRIMARY KEY,             -- snowflake ID
  short_code    VARCHAR(10) UNIQUE NOT NULL,    -- base62(id) + nullable custom alias
  long_url      TEXT NOT NULL,
  user_id       BIGINT,                         -- nullable (anonymous OK)
  created_at    TIMESTAMPTZ NOT NULL DEFAULT NOW(),
  expire_at     TIMESTAMPTZ,
  click_count   BIGINT DEFAULT 0
);

CREATE INDEX idx_urls_short_code ON urls(short_code);
CREATE INDEX idx_urls_user ON urls(user_id) WHERE user_id IS NOT NULL;

Khi 30B row: shard theo short_code hash. 1000 shard logical, 10 physical Postgres.

2.7. Scaling decisions

• Cache hot URL — 80/20 rule: top 20% URL nhận 80% click. Redis cluster 100GB.
• CDN cache redirect — Cloudflare cache 302 response 1h → cực giảm tải app.
• Read replica — primary chỉ write, multiple replica cho read.
• Click count async — không UPDATE mỗi redirect. Push event vào Kafka, batch update mỗi phút.
• Geographic — multi-region với eventual consistency. URL ở 1 region, replicate đến region khác.

2.8. Trade-offs

• Counter-based dễ predict — nếu cần obscure, thêm random hoặc encrypt.
• 302 vs 301: 301 cache mạnh hơn ở browser nhưng mất analytics (browser không hit server lần sau). Bit.ly dùng 301; analytics service riêng lấy data từ Cloudflare logs.
• Strong vs eventual consistency: URL mới tạo có thể "không tìm thấy" 1-2 giây nếu đọc replica chưa apply. Mitigation: read primary cho recent write.

3. Case 2: Twitter Timeline (Fan-out)

3.1. Requirements

• User post tweet 280 char.
• User follow nhiều user khác.
• Home timeline: tweets từ followee, sorted by time, paginated.
• User profile: tweets của user đó.

3.2. Capacity

• 500M user, 100M DAU.
• Mỗi DAU đọc timeline 5 lần, post 0.5 tweet → 500M read, 50M write/day.
• Read peak ~10k QPS; write peak ~3k QPS.
• Mỗi tweet 1KB → 50GB/day, 18TB/year.
• Top user 100M follower (celebrity).

3.3. Bài toán cốt lõi: Timeline generation

Cách naive: SELECT tweets WHERE author_id IN (SELECT followee FROM follows WHERE follower=me) ORDER BY created DESC LIMIT 20.

Vấn đề: user follow 1000 người, mỗi lần view timeline phải scan tweets của 1000 user. 100M user view timeline → DB chết.

3.4. Hai pattern: Fan-out on Read vs Fan-out on Write

3.5. Twitter pattern: Hybrid

• User thường (< 1M follower): fan-out on write. Khi post, ghi tweet_id vào Redis list của mỗi follower (timeline:userId).
• Celebrity (> 1M follower): fan-out on read. Khi follower view timeline, merge tweets của celebrity họ follow with pre-computed list.

Hybrid tránh cả 2 vấn đề:

• Celebrity post → không phải ghi 100M entry (sẽ kẹt vài giây/phút).
• User thường read → không phải merge tweets của 1000 followee mỗi lần.

3.6. Architecture

3.7. Data store choices

• Tweets: Cassandra/ScyllaDB sharded by user_id — write-heavy, append-only natural fit. Or Postgres sharded.
• Follows: graph relations — Postgres or Cassandra với (follower_id, followee_id) composite key.
• Timeline cache: Redis cluster — list per user, 1000 entry mới nhất. TTL 30 ngày (active user).
• Tweet content cache: Redis với LRU eviction, hot tweet luôn ở RAM.

3.8. Optimizations

• Lazy fan-out — chỉ fan-out đến active user (login < 7 ngày). Inactive user lazy-load khi login lại.
• Read replica geographic — timeline cache ở region gần user.
• Tweet content shared — không duplicate tweet body trong mỗi follower's list. Chỉ lưu tweet_id, hydrate khi đọc.

3.9. Trade-offs

• Eventual consistency — tweet mới có thể delay 1-2 giây để xuất hiện trong timeline tất cả follower.
• Memory cost — 100M user × 1000 tweet_id × 8 byte = 800GB Redis cho timeline cache. Nhiều shard.
• Inactive user — nếu cache TTL hết, lazy regenerate khi login.

4. Case 3: Uber-like Geospatial Service

4.1. Requirements

• Driver send vị trí mỗi 4 giây.
• Rider request → tìm driver gần nhất trong vài giây.
• Surge pricing area — phát hiện high-demand zone.
• Realtime cập nhật vị trí driver trên map.

4.2. Capacity

• 10M driver active, mỗi cái gửi vị trí mỗi 4s → 2.5M write/s.
• Rider request 100k/s peak.
• Storage cho location history (90 ngày) huge.

4.3. Bài toán cốt lõi: tìm driver gần

Naive: SELECT driver WHERE distance(loc, rider_loc) < 5km ORDER BY distance LIMIT 10.

Vấn đề: tính khoảng cách cho 10M driver mỗi request → cực chậm. Cần spatial index.

4.4. Geohash — bảng trị giá vàng

Chia trái đất thành lưới chữ nhật. Mỗi ô có hash unique. Hash càng dài, ô càng nhỏ.

• 5 char (~5km × 5km): "9q5cs".
• 6 char (~1km × 1km): "9q5csb".
• 7 char (~150m × 150m): "9q5csbf".

Đặc tính: prefix giống → vị trí gần. 9q5cs chứa mọi vị trí 9q5cs*.

4.5. Architecture

4.6. Redis GEO commands

GEOADD drivers -122.4194 37.7749 driver-123        # San Francisco
GEOADD drivers -73.9857 40.7484 driver-456         # New York

# Tìm driver trong 5km của rider:
GEORADIUS drivers -122.4180 37.7758 5 km WITHCOORD WITHDIST COUNT 10 ASC

# Output: list (driver-id, distance, [lon, lat])

Redis GEO dùng sorted set + geohash internal. Cực nhanh — < 1ms cho hàng triệu driver.

4.7. Sharding theo region

1 Redis cluster cho mỗi region (US-West, US-East, EU, APAC). Driver mặc định trong cluster region của họ. Cross-region rare (chuyến bay đến nơi khác).

Sharding theo geohash level cao (vd: 4 char = 50km × 50km) cũng được — nhưng phức tạp khi driver di chuyển cross-shard.

4.8. Quad-tree (alternative)

Cây 4 nhánh — mỗi node chia khu vực thành 4 quadrant. Khi node quá đông, split. Điều chỉnh density tự động — vùng đông (downtown) nhiều node nhỏ, vùng thưa (rural) ít node lớn.

Phù hợp khi mật độ không đều. Geohash đơn giản hơn nhưng kém adaptive.

4.9. Surge pricing detection

Stream rider request và driver count theo geohash → real-time aggregation:

area_demand_supply_ratio = rider_requests_5min / available_drivers
if ratio > threshold: surge multiplier 1.5-3x

Implementation: Kafka stream + Flink/Kafka Streams aggregation per geohash bucket.

4.10. Trade-offs

• Update frequency vs cost: 4s update là balance giữa accuracy (driver location) và load. Faster = more accurate, more load.
• Geohash boundary: 2 vị trí cách 100m có thể có geohash hoàn toàn khác (ranh giới cell). Workaround: search 9 cell adjacent.
• Eventual consistency: rider thấy driver ở vị trí 4s trước. Acceptable.
• Hot region (đông user) tách shard riêng.

5. Case 4: Netflix-like Video Streaming

5.1. Requirements

• User upload + view video.
• Multiple resolution (240p, 480p, 720p, 1080p, 4K).
• Adaptive bitrate streaming.
• Low latency play start (< 2s).
• Recommendation.

5.2. Capacity

• 200M user, 100M concurrent peak.
• Average 2 hour/day stream.
• 1080p ≈ 5 Mbps → 100M × 5 Mbps = 500 Tbps peak — Internet-scale bandwidth.
• Storage: 5000 movies × 5 resolutions × ~10GB = 250TB.

5.3. Component chính

1. Upload service — multipart upload to S3.
2. Transcoding pipeline — async, Kafka job → video transcoder workers (FFmpeg) sinh nhiều resolution.
3. Storage — S3 cho master file, CDN cho delivery.
4. CDN — Open Connect (Netflix custom) hoặc CloudFront.
5. Adaptive streaming — HLS / DASH protocol.
6. Recommendation — ML pipeline với user history.

5.4. Adaptive Bitrate Streaming (HLS)

Video chia thành chunks 2-10s. Mỗi chunk có nhiều resolution version. Client tự chọn version theo bandwidth thực tế.

video.m3u8 (manifest):
  #EXTM3U
  #EXT-X-STREAM-INF:BANDWIDTH=500000,RESOLUTION=480x270
  240p/playlist.m3u8
  #EXT-X-STREAM-INF:BANDWIDTH=2000000,RESOLUTION=1280x720
  720p/playlist.m3u8
  #EXT-X-STREAM-INF:BANDWIDTH=5000000,RESOLUTION=1920x1080
  1080p/playlist.m3u8

720p/playlist.m3u8:
  #EXTM3U
  #EXTINF:6.0
  segment-001.ts
  #EXTINF:6.0
  segment-002.ts
  ...

Network slow → client tự switch xuống 480p, không buffer. Network OK → 1080p.

5.5. CDN strategy

Netflix có Open Connect — CDN custom tích hợp ISP. Cache video phổ biến ngay tại ISP datacenter → user nhận từ "ISP local server" thay đường dài.

Cache hit rate Netflix 95%+. Origin chỉ phục vụ video hiếm.

5.6. Recommendation

2 component:

• Offline batch — Spark job hằng ngày, train ML model, generate top 100 recommendation per user.
• Online realtime — A/B test, contextual (giờ trong ngày, device).

Recommendation pre-computed lưu Cassandra: (user_id) → [movie_ids]. View hiển thị → đọc nhanh.

5.7. Architecture

5.8. Trade-offs

• Storage cost — multi-resolution chiếm 2-3× single. Worth cho UX.
• Encode time — 1 movie = vài giờ transcode. Acceptable async.
• Pre-positioning — Open Connect push popular content đến ISP đêm low-traffic.

6. Case 5: Notification Service (Email / SMS / Push)

6.1. Requirements

• Multi-channel: email, SMS, push notification (iOS, Android), in-app.
• Trigger từ nhiều service: order confirmation, password reset, marketing campaign.
• Throttling — không spam user.
• User preferences — opt-out per channel.
• Delivery tracking — sent, delivered, opened, clicked.
• Retry on failure.

6.2. Capacity

• 100M user.
• 10 notification/user/day → 1B notification/day.
• Avg 12k/s, peak 100k/s (marketing burst).
• Multi-region.

6.3. Architecture

6.4. Component

6.4.a. Notification Service core

• Subscribe Kafka events (order.created, password.reset_requested, ...).
• Map event → template + channels.
• Hydrate user data (name, email, phone) from User Service.
• Check user preferences — opt-out?
• Apply throttling — user nhận < X notification/hour.
• Dedup — same notification ID → only send once (idempotency).
• Push to channel-specific queue.

6.4.b. Channel workers

• Pool workers per channel (email, SMS, push).
• Pull from queue, call external API (SendGrid, Twilio, FCM).
• Retry với exponential backoff khi fail.
• DLQ sau 3-5 retry.
• Update tracking DB với delivery status.

6.4.c. Tracking

Cassandra schema:

CREATE TABLE notifications (
  id UUID,
  user_id BIGINT,
  channel TEXT,           -- email, sms, push
  template_id TEXT,
  status TEXT,            -- queued, sent, delivered, opened, clicked, failed
  sent_at TIMESTAMP,
  delivered_at TIMESTAMP,
  opened_at TIMESTAMP,
  PRIMARY KEY ((user_id), id)
) WITH CLUSTERING ORDER BY (id DESC);

Partition by user_id → query "lịch sử notification của user" nhanh.

6.5. Idempotency — critical

Notification gửi 2 lần là tệ (user nhận 2 email cùng nội dung). Producer phải gửi với notification_id unique:

// Producer
const notifId = `order.confirmed:${orderId}`;
await kafka.send({
  topic: 'notifications',
  messages: [{
    key: notifId,    // Kafka idempotent producer
    value: JSON.stringify({ user_id, type: 'order.confirmed', data: {...} }),
  }],
});

// Consumer (Notification Service)
async function process(event) {
  const notifId = event.id;
  const exists = await db.query('SELECT 1 FROM notifications WHERE id=$1', [notifId]);
  if (exists.rowCount > 0) return;   // already processed
  // ... send notification
  await db.query('INSERT INTO notifications (id, ...) VALUES ($1, ...)', [notifId, ...]);
}

6.6. Throttling logic

async function shouldThrottle(userId: number, channel: string): Promise<boolean> {
  const key = `notif_count:${userId}:${channel}:${Math.floor(Date.now() / 3600_000)}`;
  const count = await redis.incr(key);
  if (count === 1) await redis.expire(key, 3600);

  const limit = channel === 'email' ? 5 : channel === 'sms' ? 2 : 20;
  return count > limit;
}

Marketing campaign cần special path — bulk send nhưng vẫn respect user preference.

6.7. Trade-offs

• At-least-once — accept may duplicate, dedup at consumer. Easier than exactly-once.
• Eventual delivery — notification có thể delay 1-30s normal, nhiều phút khi external API down (retry).
• Cost — SMS đắt ($0.005/SMS). Marketing cần budget cap.
• Provider redundancy — primary SendGrid + backup AWS SES. Nếu primary down, switch.

7. Interview Tips

7.1. Quy tắc phỏng vấn 45-60 phút

1. 5 phút: clarify requirements (functional + non-functional). Đừng bỏ qua. Senior phỏng vấn cố tình mơ hồ — bạn phải hỏi.
2. 5 phút: capacity estimation. Show "back-of-envelope" math. Tự tin với số liệu.
3. 5 phút: API + data model. Top 3-5 endpoint + key schema.
4. 15 phút: high-level architecture. Vẽ box và arrow. Bắt đầu đơn giản (1 server + 1 DB), evolve theo bottleneck.
5. 15 phút: deep dive 1-2 component (interviewer thường chọn).
6. 5 phút: bottleneck + optimization + monitoring.
7. 5 phút: trade-offs + ask questions.

7.2. Lời khuyên

• Bắt đầu đơn giản. Đừng vẽ kiến trúc Twitter-scale ngay khi prompt là "design TODO list". Evolve theo nhu cầu.
• Think out loud. Senior muốn biết tư duy bạn, không chỉ kết quả cuối.
• Trade-off mọi quyết định. "Tôi chọn Postgres vì cần ACID, mặc dù MongoDB scale tốt hơn." Show awareness.
• Capacity math thật. Đừng nói "scalable" mà không có số. "10k QPS" là minimum.
• Hỏi lại khi mơ hồ. "Read-heavy hay write-heavy?" "Latency target?" "Multi-region?".
• Đừng buzzword bingo. Đừng nói "Kafka + Kubernetes + microservice" cho TODO app.
• Acknowledge limit. "Tôi không quen specific X, but here's how I'd approach it."

7.3. Pattern phỏng vấn phổ biến

• Design Twitter / Instagram (timeline)
• Design URL Shortener / Pastebin (key-value, ID gen)
• Design Uber / Lyft (geospatial)
• Design YouTube / Netflix (video streaming, CDN)
• Design WhatsApp / Discord (real-time chat)
• Design Google Drive / Dropbox (file storage, sync)
• Design Search (autocomplete, ranking)
• Design Notification Service
• Design Rate Limiter
• Design Distributed Cache
• Design Stock Exchange (low-latency)
• Design Recommendation Engine

Resources:

• "System Design Interview" — Alex Xu (book series).
• "Designing Data-Intensive Applications" — Martin Kleppmann.
• Engineering blog: Stripe, Discord, Uber, Cloudflare, Netflix, Shopify, GitHub.
• HighScalability.com — case studies từ tech giant.
• System Design Primer (GitHub repo).

8. Bài tập

1. Design "WhatsApp" — real-time chat 500M user. Phải xử lý: 1-1 chat, group chat 256 người, online status, typing indicator, message persist + sync cross-device, end-to-end encryption.
2. Design "Google Drive" — file storage và sync. 100M user, file đến 5GB, sync cross-device realtime, conflict resolution, version history.
3. Design "Distributed rate limiter" — service mà 1000+ instance dùng chung counter. Cho 10k QPS / API key. Latency < 5ms.
4. Design "Search autocomplete" — gợi ý 10 query phổ biến khi user gõ. 5 tỉ query/day. Gợi ý < 100ms. Trending term cập nhật trong giờ.
5. Design "Stock Exchange order matching engine" — match buy/sell order trong < 1ms. 10k order/s. Strict ordering. Atomic execution.
6. Design "Discord-like" — real-time chat, voice, video. 200M user. Cassandra + Erlang/Elixir/Rust. Phân tích trade-off vs WhatsApp design.
7. Cho 1 case study bất kỳ ở mục 7.3, viết detailed design 1 trang theo khung 8 bước. Practice 1 case/tuần trong 2 tháng.

9. Quiz