Belajar System Design - Design Distributed Rate Limiter

#Pendahuluan

Setelah di episode 22 kita mendesain news feed, pada episode ini kita mendesain komponen yang melindungi sistem dari abuse: distributed rate limiter. Rate limiter membatasi jumlah request dari satu client dalam periode waktu tertentu — mencegah DDoS, abuse, dan traffic burst yang bisa mempengaruhi availability.

Rate limiter sederhana (single instance) mudah dibuat. Tapi rate limiter yang bekerja di banyak instance server — dan memberikan limit yang konsisten — adalah masalah distributed systems yang menarik.

#Requirements

#Functional Requirements

Limit per user: maksimal N request per detik/menit.
Distributed: limit berlaku lintas semua server (bukan per-instance).
HTTP headers: beri tahu client tentang limit dan sisa quota.
Graceful: request yang di-limit dapat retry-after info.

#Non-Functional Requirements

Low latency: rate limit check harus sangat cepat (<5ms).
Accuracy: akurat meskipun concurrent requests.
Scale: handle 100K+ QPS rate limit checks.

#Algoritma

#Token Bucket

Token bucket algorithm

Bucket size: 10 tokens
Refill rate: 2 tokens/detik
 
Request 1-10: langsung proses (tokens 10 → 0)
Request 11: ditolak (tokens 0, belum refill)
Setelah 1 detik: tokens refill 2 → request 11-12 bisa proses

Kelebihan: memungkinkan burst (sampai bucket size), refill rate stabil. Implementasi: Redis dengan TTL untuk refill.

#Sliding Window Log

Sliding window log

Window: 60 detik
Limit: 100 requests
 
Untuk setiap request:
1. Hapus semua timestamp lebih tua dari 60 detik lalu
2. Hitung sisa timestamp dalam window
3. Jika count < 100: proses, tambahkan timestamp
4. Jika count >= 100: ditolak

Kelebihan: akurat (tidak ada window boundary issue). Kekurangan: memory tinggi (simpan semua timestamp).

#Sliding Window Counter

Sliding window counter

Window: 60 detik, limit: 100
 
Hitung weighted average:
prev_window_count = 80
curr_window_count = 30
elapsed = 30 detik (setengah window)
 
weighted_count = prev × ((60-30)/60) + curr = 80 × 0.5 + 30 = 70
70 < 100 → proses

Kelebihan: memory-efficient (hanya 2 counter per window), reasonable accuracy. Kekurangan: estimasi, bukan exact.

#Arsitektur

#Centralized (Redis-Based)

100%

Redis-based rate limiter

Redis key: "rate:{user_id}:{window}"
Value: counter (sliding window) atau timestamps (log)
 
Lua script atomic:
1. Get current count
2. If count >= limit: return REJECT
3. Increment count
4. Set TTL (window duration)
5. Return ALLOW

#Local (Per-Instance + Sync)

Local rate limiter

Setiap instance punya local rate limiter
Periodik sync counters ke central store
 
Kelebihan: very low latency (local check)
Kekurangan: limit bisa melebihi target (sync delay)

#Perbandingan

Aspek	Centralized	Local + Sync
Latency	1-5ms (network ke Redis)	<1ms (local)
Accuracy	Sangat akurat	Over-limit possible (5-10%)
Complexity	Rendah (single source)	Tinggi (sync logic)
Scale	Redis cluster	Tambahan instance tanpa bottleneck

#Race Condition Handling

#Masalah

Race condition

Concurrent request:
  Thread 1: GET count = 99
  Thread 2: GET count = 99
  Thread 1: SET count = 100 (ALLOW)
  Thread 2: SET count = 100 (ALLOW) → MELEBIHI LIMIT!

#Solusi: Lua Script Atomic

Redis Lua script (atomic)

local key = KEYS[1]
local limit = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
 
local current = redis.call('GET', key) or 0
if current >= limit then
    return 0  -- REJECT
end
redis.call('INCR', key)
redis.call('EXPIRE', key, window)
return 1  -- ALLOW

Lua script di Redis dieksekusi secara atomic — tidak ada race condition.

#Solusi: Redis MULTI/EXEC

Redis transaction

MULTI
GET rate:user:123:window
INCR rate:user:123:window
EXPIRE rate:user:123:window 60
EXEC

#HTTP Headers

Rate limit response headers

# Request berhasil:
HTTP/1.1 200 OK
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 45
X-RateLimit-Reset: 1692163200
 
# Request ditolak:
HTTP/1.1 429 Too Many Requests
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1692163200
Retry-After: 30

Tip

Untuk distributed rate limiter, gunakan Redis Lua script untuk atomicity. Sliding window counter adalah trade-off terbaik antara accuracy dan memory. Selalu expose X-RateLimit-* headers agar client bisa handle rate limiting gracefully.

#Penutup

Inti yang harus dibawa pulang:

Token bucket: burst-friendly, refill rate stabil; bagus untuk API rate limiting.
Sliding window counter: memory-efficient, reasonable accuracy; bagus untuk distributed.
Centralized (Redis): akurat, single source of truth; local: lebih cepat tapi over-limit possible.
Lua script atomic: mengatasi race condition di Redis — wajib untuk distributed rate limiter.
HTTP headers: X-RateLimit-* dan Retry-After untuk client communication.

Di episode 24 selanjutnya kita akan membahas case study: design distributed file storage (Dropbox/Google Drive) — chunk storage, delta sync, conflict resolution, dan WebSocket untuk notifikasi. File storage adalah tantangan tentang sync, versioning, dan conflict resolution!