System Design: Idempotency, Locking và Rate Limiting

Trong distributed systems, LUÔN có thể:
  - Request gửi đi nhưng không biết server nhận chưa
  - Response về nhưng client không nhận được
  - Timeout → client retry → server nhận 2 lần

→ Idempotent operation: thực hiện nhiều lần = thực hiện 1 lần

HTTP Methods:
  GET, HEAD, PUT, DELETE: idempotent
  POST: KHÔNG idempotent (tạo resource mới mỗi lần)
  PATCH: có thể hoặc không (tùy implementation)

Client tạo unique idempotency key cho mỗi operation:
  Key = UUID (random, generated client-side)

Request:
  POST /payments
  Idempotency-Key: 550e8400-e29b-41d4-a716-446655440000
  { "amount": 100, "currency": "USD" }

Server logic:
  1. Lookup idempotency key trong cache/DB
  2. Nếu tìm thấy → trả về cached response (không process lại)
  3. Nếu không tìm thấy:
     - Process payment
     - Store (key → response) với TTL (e.g., 24h)
     - Trả về response

  ┌─────────────────────────────────────────────────────┐
  │  idempotency_keys table                             │
  │  key        | status      | response | created_at  │
  │  550e8400.. | PROCESSING  |          | 2024-01-01  │
  │  550e8400.. | COMPLETED   | {...}    | 2024-01-01  │
  └─────────────────────────────────────────────────────┘

Race condition (concurrent requests với same key):
  → Dùng SELECT FOR UPDATE hoặc distributed lock
  → Chỉ 1 request được process, others chờ và nhận cached response

Database level:
  INSERT ... ON CONFLICT DO NOTHING  (PostgreSQL)
  INSERT IGNORE INTO ...             (MySQL)
  Unique constraint trên idempotency_key column

Versioning:
  UPDATE SET version = version + 1 WHERE version = expected_version
  → Nếu version không match → noop (đã processed)

Natural idempotency:
  "Set balance to $100" → idempotent
  "Add $100 to balance" → NOT idempotent
  → Prefer absolute values over relative operations khi có thể

Event consumers:
  Track processed event IDs
  IF event_id already processed → skip
  ELSE process AND mark as processed (atomically)

Vấn đề: Nhiều instances của cùng service cùng chạy
  → Cùng cron job chạy trên 2 instances → duplicate work
  → Cùng inventory record bị update → race condition
  → Leader election trong cluster

Distributed lock = mutex across multiple processes/machines

Simple Redis Lock:
  SET lock:resource_id <unique_value> NX PX 30000
  → NX = only set if not exists
  → PX 30000 = expire sau 30 seconds (TTL)

  Nếu SET thành công → lock acquired
  Nếu thất bại → lock held by someone else → retry hoặc fail

Release (PHẢI dùng Lua script để atomic):
  // WRONG - race condition!
  if redis.get(key) == my_value:
      redis.del(key)

  // CORRECT - atomic Lua script:
  if redis.call("get", key) == ARGV[1] then
      return redis.call("del", key)
  else
      return 0
  end

Redlock Algorithm (multiple Redis instances):
  Dùng N=5 independent Redis instances (không phải cluster)
  1. Get current time t1
  2. Try to acquire lock trên tất cả N instances (với short timeout)
  3. Count successful acquisitions
  4. Nếu acquired > N/2 (majority) AND elapsed_time < lock_TTL
     → Lock acquired!
  5. Nếu không → release tất cả và retry

  Safety: lock chỉ valid nếu majority hold it
  → Chịu được N/2 - 1 node failures

Vấn đề với Redis lock:
  Process A acquire lock
  Process A bị GC pause dài
  Lock TTL expire
  Process B acquire lock
  Process A tiếp tục (GC xong) → nghĩ vẫn hold lock!
  → A và B cùng "hold lock" → unsafe!

Fencing Token giải quyết:
  Lock service trả về monotonically increasing token khi grant lock
  Client gửi token theo mọi request đến resource
  Resource server reject requests với outdated token

  A gets token=33
  B gets token=34 (A's lock expired)
  A resumes, sends request with token=33
  Resource: 33 < 34 (last seen) → REJECT A!
  B's requests with token=34 → ACCEPTED

  Storage: lưu "last seen fencing token" và reject < last_seen

ZooKeeper Distributed Lock:
  Tạo ephemeral sequential node: /locks/resource-0000000001
  List tất cả children → nếu mình là smallest → lock acquired
  Nếu không → watch node ngay trước mình → chờ notification

  Ephemeral = tự xóa khi client disconnect
  → Tự động release lock nếu process crash

  Sequential + watch → tránh herd effect
  (không phải tất cả clients wake up khi lock released)

etcd Lock:
  Dùng lease (TTL-based), revoke khi không cần
  Hỗ trợ transactions (compare-and-swap)
  Dùng Raft → strong consistency
  Used in: Kubernetes leader election

Token Bucket:
  Bucket có capacity N tokens
  Tokens được thêm vào với rate R (tokens/second)
  Mỗi request tiêu thụ 1 token
  Nếu bucket empty → reject request

  Cho phép bursts (nếu bucket đang đầy)
  Pro: smooth rate, allows bursts
  Used in: AWS API Gateway

  tokens = min(capacity, tokens + rate × elapsed_time)
  if tokens >= 1: tokens -= 1; allow
  else: reject

Leaky Bucket:
  Queue với capacity N
  Requests được xử lý với constant rate R
  Nếu queue đầy → reject

  Tạo constant output rate (không allow bursts)
  Use case: network traffic shaping

Sliding Window Log:
  Lưu timestamp của mỗi request
  Khi request mới: xóa timestamps ngoài window
  Đếm số timestamps còn lại
  Nếu < limit → allow

  Chính xác nhất, nhưng tốn memory

Fixed Window Counter:
  Đếm requests trong window cố định (e.g., 1 phút)
  Vấn đề: spike tại boundary
  01:59:30 — 100 requests (Window 1, limit 100)
  02:00:30 — 100 requests (Window 2, limit 100)
  → Effective 200 requests trong 1 phút thực sự!

Sliding Window Counter:
  Kết hợp Fixed Window + rate từ previous window
  current_count + prev_count × (window_size - elapsed) / window_size
  → Approximate sliding window, ít memory hơn log

Single server: lưu counter trong memory
Multi-server: cần shared state

Redis-based:
  INCR request_count:{user_id}:{minute}
  EXPIRE request_count:{user_id}:{minute} 60
  → Atomic, distributed, fast

  Vấn đề: Redis round trip mỗi request (~1ms)
  → Có thể dùng Redis pipelines hoặc Lua scripts

Local + Global:
  Mỗi server lưu local counter
  Periodically sync lên Redis (e.g., mỗi 100ms)
  → Allow some overage nhưng giảm Redis calls
  → Eventual rate limiting

Sliding Window với Redis:
  ZADD key <timestamp> <request_id>
  ZREMRANGEBYSCORE key 0 <(now - window)>
  ZCARD key → current count
  → Exact sliding window nhưng tốn memory