System Design Interview: Panduan Lengkap untuk Software Engineer

# === STEP 1: CLARIFY REQUIREMENTS (3-5 menit) ===
# Tanyakan hal-hal yang ambigu. Jangan langsung menggambar.
# Contoh pertanyaan:
#   - Berapa estimasi user per hari? (scale)
#   - Apa fitur utama yang harus ada? (functional)
#   - Berapa latency yang diharapkan? (non-functional)
#   - Read-heavy atau write-heavy?
#   - Konsistensi atau availability yang diprioritaskan?

# === STEP 2: ESTIMATION & BACK-OF-ENVELOPE (3-5 menit) ===
# Hitung estimasi kasar untuk memahami skala:
#   - Jumlah request per detik (QPS)
#   - Penyimpanan yang dibutuhkan per tahun
#   - Bandwidth yang dibutuhkan
#   - Jumlah server yang diperlukan
#
# Contoh: 10 juta user/hari, rata-rata 5 request/user
# QPS = 10M × 5 / 86400 ≈ 580 requests/detik
# Peak QPS ≈ 580 × 3 = 1,740 requests/detik

# === STEP 3: HIGH-LEVEL DESIGN (10-15 menit) ===
# Gambar arsitektur utama:
#   - Client → API Gateway → Services → Database
#   - Tentukan komponen mana yang dibutuhkan
#   - Definisikan API endpoint utama
#   - Pilih database yang sesuai
#   - Identifikasi di mana cache diperlukan

# === STEP 4: DEEP DIVE & TRADE-OFF (10-15 menit) ===
# Fokus pada komponen yang paling kritis:
#   - Bagaimana data di-shard di database?
#   - Strategi caching (write-through vs write-behind)?
#   - Bagaimana menangani failure scenario?
#   - Monitoring dan alerting?

# 1. ROUND ROBIN
# Setiap request didistribusikan secara berurutan
# Server: [A, B, C]
# Request 1 → A, Request 2 → B, Request 3 → C, Request 4 → A
# Cocok untuk: server dengan spesifikasi sama
# Kelemahan: Tidak memperhitungkan beban aktual server

# 2. WEIGHTED ROUND ROBIN
# Seperti round robin tapi server punya "bobot"
# Server: [A(weight=5), B(weight=3), C(weight=2)]
# A menerima 50% request, B 30%, C 20%
# Cocok untuk: server dengan spesifikasi berbeda

# 3. LEAST CONNECTIONS
# Request dikirim ke server yang paling sedikit koneksi aktif
# Server A: 10 connections, B: 5 connections, C: 8 connections
# Request baru → B (paling sedikit)
# Cocok untuk: request dengan durasi bervariasi

# 4. IP HASH
# Hash dari IP client menentukan server tujuan
# hash(client_ip) % num_servers
# Keuntungan: Session persistence (user selalu ke server sama)
# Cocok untuk: stateful application tanpa shared session

# 5. CONSISTENT HASHING
# Hash ring — meminimalkan redistribusi saat server ditambah/dihapus
# Cocok untuk: distributed cache, CDN
# Hanya ~1/N key yang perlu dipindahkan saat server berubah

# === WRITE-THROUGH ===
# Data ditulis ke cache DAN database secara bersamaan
# Keuntungan: Data selalu konsisten
# Kerugian: Write latency lebih tinggi (dua operasi)
#
# App → Cache + DB (simultan)
# Read: selalu dari cache

# === WRITE-BEHIND (WRITE-BACK) ===
# Data ditulis ke cache dulu, lalu async ke database
# Keuntungan: Write latency sangat rendah
# Kerugian: Risiko data loss jika cache crash sebelum flush
#
# App → Cache → DB (async, batched)
# Cocok untuk: write-heavy workload yang bisa toleransi sedikit data loss

# === WRITE-AROUND ===
# Data ditulis langsung ke database, tidak ke cache
# Cache hanya terisi saat cache miss (read-through)
# Keuntungan: Cache tidak dipenuhi data yang jarang dibaca
# Kerugian: Pertama kali read selalu lambat (cache miss)
#
# App → DB (langsung)
# App → Cache (miss) → DB → Cache (isi) → App

# === CACHE-ASIDE (LAZY LOADING) ===
# Strategi paling umum. App yang mengatur sendiri kapan
# menulis/membaca dari cache.
# Read:
#   1. Cek cache → hit? return
#   2. Miss? query DB → tulis ke cache → return
# Write:
#   1. Tulis ke DB
#   2. Invalidate cache (hapus entry)
#   3. Biarkan cache terisi ulang saat read berikutnya

# === REPLICATION ===
# Menyalin data ke beberapa server untuk redundancy & read scaling

# 1. LEADER-FOLLOWER (Master-Slave)
# - Semua write ke leader
# - Read bisa dari follower (read replica)
# - Follower async/sync replikasi dari leader
# - Jika leader mati, follower bisa di-promote

# 2. MULTI-LEADER
# - Beberapa server bisa menerima write
# - Cocok untuk multi-region
# - Konflik write harus diselesaikan (conflict resolution)

# 3. LEADERLESS
# - Semua node bisa menerima read & write
# - Consensus: quorum read & write
# - Contoh: Amazon DynamoDB, Cassandra

# === SHARDING (PARTITIONING) ===
# Membagi data ke beberapa database server

# 1. RANGE-BASED SHARDING
# Data dibagi berdasarkan range nilai
# Shard 1: user_id 1-1,000,000
# Shard 2: user_id 1,000,001-2,000,000
# Risiko: Hotspot jika distribusi tidak merata

# 2. HASH-BASED SHARDING
# hash(key) % num_shards
# Distribusi lebih merata
# Tapi range query sulit

# 3. DIRECTORY-BASED SHARDING
# Lookup table: key → shard mapping
# Fleksibel tapi tambah satu layer lookup

// Producer — Mengirim task ke queue
// producer.js
const amqp = require('amqplib');

async function sendTask(task) {
  const connection = await amqp.connect('amqp://localhost');
  const channel = await connection.createChannel();
  const queue = 'task_queue';

  await channel.assertQueue(queue, { durable: true });
  channel.sendToQueue(queue, Buffer.from(JSON.stringify(task)), {
    persistent: true  // Pesan disimpan ke disk
  });

  console.log(`Task dikirim: ${task.id}`);
  await connection.close();
}

// Contoh penggunaan
sendTask({ id: 'task-001', action: 'resize_image', url: '/uploads/img1.jpg' });

// Consumer — Memproses task dari queue
// consumer.js
async function consumeTasks() {
  const connection = await amqp.connect('amqp://localhost');
  const channel = await connection.createChannel();
  const queue = 'task_queue';

  await channel.assertQueue(queue, { durable: true });
  channel.prefetch(1); // Proses 1 task sekaligus

  console.log('Menunggu task...');
  channel.consume(queue, async (msg) => {
    const task = JSON.parse(msg.content.toString());
    console.log(`Memproses task: ${task.id}`);

    try {
      await processTask(task);
      channel.ack(msg); // Beritahu queue: task selesai
    } catch (err) {
      channel.nack(msg, false, true); // Re-queue jika gagal
    }
  });
}

async function processTask(task) {
  // Simulasi proses berat
  await new Promise(resolve => setTimeout(resolve, 2000));
  console.log(`Task ${task.id} selesai`);
}

# 1. TOKEN BUCKET
# - Bucket berisi "token" dengan kapasitas tetap
# - Token diisi ulang dengan rate konstan (misal: 10 token/detik)
# - Setiap request mengambil 1 token
# - Jika bucket kosong, request ditolak (HTTP 429)
#
# Kapasitas: 10, Refill: 2/detik
# Request burst: 10 langsung diizinkan, lalu 2/detik
# Cocok untuk: burst traffic yang wajar

# 2. LEAKY BUCKET
# - Request masuk ke "bucket" (queue) dengan kapasitas tetap
# - Request diproses dengan rate konstan
# - Jika bucket penuh, request ditolak
#
# Rate konstan: 5 request/detik
# Cocok untuk: output rate yang harus stabil

# 3. FIXED WINDOW COUNTER
# - Membagi waktu ke window (misal: 1 menit)
# - Counter per window, reset saat window baru
# - Limit: 100 request per menit
#
# Masalah: Burst di boundary (2 window berturut-turut bisa = 2x limit)

# 4. SLIDING WINDOW LOG
# - Menyimpan timestamp setiap request
# - Saat request baru, hapus timestamp yang sudah di luar window
# - Hitung jumlah request yang tersisa
# - Lebih akurat tapi butuh memory lebih besar

# 5. SLIDING WINDOW COUNTER
# - Kombinasi fixed window + sliding window
# - Weighted count dari window sebelumnya
# - 70% window lama + 100% window baru = smoothing
# - Cocok untuk: implementasi production yang efisien

# rate_limiter.py — Implementasi Token Bucket di Redis
import redis
import time

class TokenBucketRateLimiter:
    def __init__(self, redis_client, capacity, refill_rate):
        """
        capacity: maksimum token dalam bucket
        refill_rate: jumlah token yang ditambah per detik
        """
        self.redis = redis_client
        self.capacity = capacity
        self.refill_rate = refill_rate

    def is_allowed(self, key):
        """Cek apakah request diizinkan untuk key tertentu"""
        now = time.time()
        bucket_key = f"rate_limit:{key}"

        # Gunakan Lua script untuk atomicity
        lua_script = """
        local key = KEYS[1]
        local capacity = tonumber(ARGV[1])
        local refill_rate = tonumber(ARGV[2])
        local now = tonumber(ARGV[3])
        local requested = tonumber(ARGV[4])

        local data = redis.call('HMGET', key, 'tokens', 'last_refill')
        local tokens = tonumber(data[1]) or capacity
        local last_refill = tonumber(data[2]) or now

        -- Hitung token baru berdasarkan waktu yang berlalu
        local elapsed = now - last_refill
        local new_tokens = elapsed * refill_rate
        tokens = math.min(capacity, tokens + new_tokens)

        -- Cek apakah cukup token
        if tokens >= requested then
            tokens = tokens - requested
            redis.call('HMSET', key, 'tokens', tokens, 'last_refill', now)
            redis.call('EXPIRE', key, 3600)  -- TTL 1 jam
            return 1  -- Allowed
        else
            redis.call('HMSET', key, 'tokens', tokens, 'last_refill', now)
            redis.call('EXPIRE', key, 3600)
            return 0  -- Denied
        end
        """

        result = self.redis.eval(lua_script, 1, bucket_key,
                                  self.capacity, self.refill_rate, now, 1)
        return result == 1

# Contoh penggunaan
r = redis.Redis(host='localhost', port=6379)
limiter = TokenBucketRateLimiter(r, capacity=100, refill_rate=10)

# Di middleware web framework
for request in incoming_requests:
    user_id = request.headers.get('X-User-ID')
    if limiter.is_allowed(user_id):
        process_request(request)
    else:
        return Response(status=429, body="Rate limit exceeded")

// api-gateway.js — Simple API Gateway dengan Express
const express = require('express');
const { createProxyMiddleware } = require('http-proxy-middleware');
const rateLimit = require('express-rate-limit');
const jwt = require('jsonwebtoken');

const app = express();

// === MIDDLEWARE: Rate Limiting ===
const limiter = rateLimit({
  windowMs: 15 * 60 * 1000,  // 15 menit
  max: 100,                   // 100 request per window
  message: { error: 'Too many requests, coba lagi nanti' }
});
app.use(limiter);

// === MIDDLEWARE: Authentication ===
const authMiddleware = (req, res, next) => {
  // Skip auth untuk public endpoints
  if (req.path.startsWith('/api/auth') || req.path === '/health') {
    return next();
  }

  const token = req.headers.authorization?.replace('Bearer ', '');
  if (!token) {
    return res.status(401).json({ error: 'Token tidak ditemukan' });
  }

  try {
    const decoded = jwt.verify(token, process.env.JWT_SECRET);
    req.user = decoded;  // Attach user info ke request
    next();
  } catch (err) {
    return res.status(401).json({ error: 'Token tidak valid' });
  }
};

app.use(authMiddleware);

// === ROUTE PROXY ===
// User Service
app.use('/api/users', createProxyMiddleware({
  target: 'http://user-service:3001',
  changeOrigin: true,
  pathRewrite: { '^/api/users': '/users' }
}));

// Product Service
app.use('/api/products', createProxyMiddleware({
  target: 'http://product-service:3002',
  changeOrigin: true,
  pathRewrite: { '^/api/products': '/products' }
}));

// Order Service
app.use('/api/orders', createProxyMiddleware({
  target: 'http://order-service:3003',
  changeOrigin: true,
  pathRewrite: { '^/api/orders': '/orders' }
}));

// === Health Check ===
app.get('/health', (req, res) => {
  res.json({ status: 'ok', timestamp: new Date().toISOString() });
});

app.listen(8080, () => {
  console.log('API Gateway berjalan di port 8080');
});

# Write: 100 juta URL/bulan = ~40 URL/detik
# Read:  10 miliar redirect/bulan = ~4000 redirect/detik
# Peak:  3x average = ~12,000 redirect/detik

# Storage (5 tahun):
# 100M × 12 bulan × 5 tahun = 6 miliar URL
# Per URL: ~500 bytes (long_url + short_code + metadata)
# Total: 6B × 500 = 3 TB storage

# Bandwidth:
# Read: 4000 × 500 bytes = 2 MB/detik = 16 Mbps
# Ini sangat manageable untuk 1-2 server

# Short code:
# 6 karakter alphanumeric (a-z, A-Z, 0-9) = 62^6 = ~56 miliar kombinasi
# Cukup untuk 6 miliar URL dengan margin besar

# QPS breakdown:
# Write QPS: 40 → 1 database server cukup
# Read QPS: 4000 → Butuh cache untuk mengurangi beban DB

# === API ENDPOINTS ===

# POST /api/shorten
# Body: { "long_url": "https://example.com/very/long/path", "custom_alias": "mylink" }
# Response: { "short_url": "https://sho.rt/aB3xY2", "short_code": "aB3xY2" }

# GET /:short_code
# Response: 301 Redirect ke long_url

# GET /api/stats/:short_code
# Response: { "total_clicks": 15432, "unique_visitors": 8234, "created_at": "..." }

# === DATABASE SCHEMA ===
# Table: urls
#   id          BIGINT PRIMARY KEY AUTO_INCREMENT
#   short_code  VARCHAR(10) UNIQUE INDEX
#   long_url    TEXT NOT NULL
#   user_id     BIGINT FK → users.id
#   created_at  TIMESTAMP DEFAULT NOW()
#   expires_at  TIMESTAMP NULL
#   click_count BIGINT DEFAULT 0

# Table: click_analytics
#   id          BIGINT PRIMARY KEY AUTO_INCREMENT
#   short_code  VARCHAR(10) INDEX
#   ip_address  VARCHAR(45)
#   user_agent  TEXT
#   referer     TEXT
#   country     VARCHAR(2)
#   clicked_at  TIMESTAMP DEFAULT NOW()

# shortener.py — Strategi generate short code
import hashlib
import string
import random

CHARSET = string.ascii_letters + string.digits  # 62 karakter

# === STRATEGI 1: HASH-BASED ===
# MD5/SHA256 dari long_url, ambil 6 karakter pertama
# Masalah: Collision jika URL sama → perlu cek DB dulu
def hash_based(long_url):
    hash_val = hashlib.md5(long_url.encode()).hexdigest()
    # Konversi ke base62, ambil 6 karakter
    num = int(hash_val[:12], 16)
    code = ''
    while num > 0 and len(code) < 6:
        code = CHARSET[num % 62] + code
        num //= 62
    return code

# === STRATEGI 2: COUNTER-BASED ===
# Auto-increment counter, konversi ke base62
# Keuntungan: Unik, tidak collision
# Masalah: Predictable, bisa ditebak URL berikutnya
def counter_based(counter):
    code = ''
    while counter > 0:
        code = CHARSET[counter % 62] + code
        counter //= 62
    return code.zfill(6)  # Pad ke 6 karakter

# === STRATEGI 3: RANDOM + CHECK ===
# Generate random, cek uniqueness di DB
# Paling sederhana tapi perlu collision check
def random_based():
    return ''.join(random.choices(CHARSET, k=6))

# === STRATEGI 4: PRE-GENERATED KEY SERVICE (REKOMENDASI) ===
# Pre-generate jutaan unique key, simpan di DB/key service
# Saat ada request, ambil 1 key dari pool
# Tidak ada collision, tidak perlu check
# Kekurangan: Butuh infrastruktur key service tambahan