Phỏng Vấn System Design: Thiết Kế Rate Limiter Phân Tán Bằng Go

“Thiết kế rate limiter phân tán” là đề mà ba phút đầu đủ phân biệt người vận hành thật với người mới đọc blog. Bản thân limiter không khó; cái khó là các giả định đằng sau nó — ai bị giới hạn, chính xác tới đâu, điều gì xảy ra khi Redis chết.

1. Nhận đề: hỏi trước khi vẽ

Ba, bốn phút đầu mình chỉ hỏi. Mỗi câu trả lời đổi hẳn thiết kế.

Giới hạn theo chiều nào? User, API key, IP hay tenant? SaaS B2B tính quota theo tenant — bên trả tiền cũng là bên gây tải. API công khai thì theo API key. IP chỉ là tầng phụ: NAT gom hàng nghìn người vào một IP.

Ngân sách latency bao nhiêu? Limiter nằm trên critical path. p99 hệ thống 200ms thì tầng này phải dưới 5ms, và con số đó quyết định gọi Redis một, hai, hay không lần nào.

Cần chính xác tới đâu? “Đúng 1000 request/phút, không hơn một request” khác hẳn “đừng để tenant vượt quá gấp rưỡi”. Cái đầu buộc mọi request qua một điểm atomic. Cái sau cho phép cấp quota theo lô.

Redis chết thì fail-open hay fail-closed? Fail-open cho traffic đi thẳng vào hệ thống — nguy hiểm nếu limiter là thứ duy nhất che database. Fail-closed trả 429 cho mọi người — với API công khai là sự cố tự tạo.

Single-region hay multi-region? Multi-region thì mỗi region một Redis, hạn mức toàn cầu thành tổng xấp xỉ. Hoặc mọi region gọi về một Redis trung tâm — thêm 100–200ms, phá ngân sách latency.

Có cần burst không? Client mở trang bắn 20 request song song rồi im lặng mười giây là bình thường. Cửa sổ cứng 60 request/phút chặn oan.

Có cần xem trước quota? Nếu client cần X-RateLimit-Remaining thì quyết định cho qua phải mang số dư, tức script atomic trả về nhiều hơn một bit.

Mình chốt giả định thành một đoạn ngắn rồi xin interviewer xác nhận. Xây trên giả định sai là cách mất điểm nhanh nhất.

2. Requirements và back-of-envelope

Giả sử interviewer chốt: API đa tenant, 50.000 req/s ở đỉnh, p99 tầng limit dưới 5ms, cần burst, sai số vài phần trăm, single-region, Redis backend.

Key: 200.000 tenant nhân 8 nhóm route (không phải từng URL) ra 1,6 triệu key sống. Token bucket giữ tokens và ts trong một hash, cỡ 150 byte mỗi key — khoảng 240MB chưa kể replica, đủ để phải shard.

Độ trễ: một EVAL cùng availability zone tốn 0,2–0,5ms, vừa ngân sách 5ms; xuyên region thành 30–150ms, nên limiter không bao giờ gọi Redis xuyên region.

Throughput: Redis đơn luồng, một instance mạnh làm cỡ 100.000 lệnh đơn giản/giây, nhưng script Lua nặng hơn GET hay INCR, thực tế còn 50.000–80.000 lần chạy/giây. Với đỉnh 50.000 req/s, một shard quá sát ngưỡng — mình tính ba đến bốn shard.

3. Contract của middleware

Tầng rate limit là middleware bọc handler: chạy trước handler, trả về đúng một quyết định kèm metadata.

Key: rl:{tenant_id}:{route_class}:{window}. Mình dùng route_class (read, write, export) chứ không dùng đường dẫn thô: đường dẫn thô làm key bùng nổ theo query string và mở lỗ hổng — thêm một tham số lạ là có bucket mới, tức vượt hạn mức miễn phí.

Hạn mức không nhét vào key: config theo bảng tier + route_class, nạp vào bộ nhớ và refresh định kỳ, nên đổi quota không cần migrate.

type Decision struct {
	Allowed    bool
	Limit      int
	Remaining  int
	ResetAt    time.Time
	RetryAfter time.Duration
}

type Limiter interface {
	Check(ctx context.Context, key string, cost int) (Decision, error)
}

func RateLimit(l Limiter, keyFn func(*http.Request) string, fallback Decision) func(http.Handler) http.Handler {
	return func(next http.Handler) http.Handler {
		return http.HandlerFunc(func(w http.ResponseWriter, r *http.Request) {
			d, err := l.Check(r.Context(), keyFn(r), 1)
			if err != nil {
				// Redis lỗi: xử lý theo chính sách đã chốt ở phần làm rõ yêu cầu.
				// fallback là quyết định từ limiter cục bộ, không phải hằng số.
				d = fallback
			}

			h := w.Header()
			h.Set("X-RateLimit-Limit", strconv.Itoa(d.Limit))
			h.Set("X-RateLimit-Remaining", strconv.Itoa(max(d.Remaining, 0)))
			h.Set("X-RateLimit-Reset", strconv.FormatInt(d.ResetAt.Unix(), 10))

			if !d.Allowed {
				h.Set("Retry-After", strconv.Itoa(max(1, int(math.Ceil(d.RetryAfter.Seconds())))))
				w.WriteHeader(http.StatusTooManyRequests)
				return
			}
			next.ServeHTTP(w, r)
		})
	}
}

Ba chi tiết dễ sai. X-RateLimit-Reset là epoch giây tuyệt đối, Retry-After là số giây phải chờ — trộn hai thứ này khiến client retry sai. Header phải set cả khi request bị chặn. max(a, b) là builtin từ Go 1.21.

4. So sánh thuật toán và lý do chọn

Fixed window rẻ nhất — một INCR, một EXPIRE — nhưng lỗi biên. Hạn mức 60 request/phút cho phép 60 lúc 11:59:59 và 60 lúc 12:00:00. Tức 120 request trong hai giây.

Sliding window log chính xác tuyệt đối, đổi lại RAM tỉ lệ số request: 60 phần tử nhân 1,6 triệu key là gần trăm triệu phần tử. Chỉ hợp khi số key nhỏ, ví dụ chống brute-force theo tài khoản.

Sliding window counter xấp xỉ: hai biến đếm (cửa sổ hiện tại và trước) rồi nội suy theo thời gian trôi qua. Sai số vài phần trăm, tệ hơn khi traffic lệch hẳn về một phía, và không cho burst.

Token bucket giữ tốc độ nạp R token/giây và dung lượng B; request lấy một token, xô rỗng thì từ chối, cho burst tối đa B. State hai số. Mô hình khớp hành vi thật: im lặng rồi bùng nổ.

Leaky bucket xả tốc độ cố định qua hàng đợi. Làm phẳng traffic tốt, đổi lại thêm độ trễ xếp hàng và cần bộ nhớ cho queue — thực tế là traffic shaper hơn là limiter. Biến thể GCRA có state nhỏ ngang token bucket, là thứ redis-cell dùng.

Mình chọn token bucket vì ba lý do: cần burst nên fixed window và sliding counter không đáp ứng; state chỉ hai số nên RAM chấp nhận được; golang.org/x/time/rate implement đúng ngữ nghĩa này nên tầng local và Redis dùng chung một mô hình. Cái giá: hai trường state phải cập nhật nguyên tử — dẫn tới Lua ở mục 6.

5. Bản single-node bằng Go

Trước khi phân tán, mình luôn nói được bản chạy một máy.

type bucket struct {
	lim      *rate.Limiter
	lastSeen atomic.Int64 // unix nano
}

type localStore struct {
	mu      sync.RWMutex
	buckets map[string]*bucket
	rate    rate.Limit
	burst   int
	ttl     time.Duration
}

func (s *localStore) limiterFor(key string) *rate.Limiter {
	now := time.Now().UnixNano()

	s.mu.RLock()
	b, ok := s.buckets[key]
	s.mu.RUnlock()
	if ok {
		b.lastSeen.Store(now)
		return b.lim
	}

	s.mu.Lock()
	defer s.mu.Unlock()
	if b, ok := s.buckets[key]; ok { // kiểm tra lại sau khi lấy write lock
		b.lastSeen.Store(now)
		return b.lim
	}
	b = &bucket{lim: rate.NewLimiter(s.rate, s.burst)}
	b.lastSeen.Store(now)
	s.buckets[key] = b
	return b.lim
}

rate.NewLimiter(rate.Limit, int) nhận tốc độ token/giây và dung lượng xô; xô đầy lúc khởi tạo nên request đầu tiên burst ngay. rate.Every(d) tương đương rate.Limit(1/d.Seconds()). rate.Limit(0) chặn tất cả, rate.Inf cho qua tất cả.

Map chỉ an toàn nếu có janitor: goroutine mỗi phút xoá key có lastSeen cũ hơn TTL (thường 2 * burst / rate). Không có nó, map phình vô hạn, và kẻ tấn công chỉ cần gửi hàng triệu key khác nhau là hết RAM — nên thêm trần số phần tử hoặc evict LRU.

Allow() từ chối ngay khi hết token; Wait(ctx) giữ request tới khi có token, biến limiter thành hàng đợi — mỗi request chờ chiếm một goroutine và một connection đúng lúc hệ thống quá tải. Mình dùng Allow cho API công khai, Wait cho background job nơi backpressure là mong muốn. ReserveN trả về *Reservation; Delay() cho biết phải chờ bao lâu — đúng thứ để tính Retry-After.

6. Phân tán: vì sao không thể đọc rồi ghi

Trên một instance, một mutex là đủ. Trên nhiều instance, cách ngây thơ là GET số token, tính trong Go rồi SET lại: hai instance có thể cùng thấy còn token và cùng cho qua — hạn mức vượt đúng bằng số instance. Ở 50.000 req/s, cửa sổ race vài trăm micro giây đủ lọt hàng trăm request mỗi phút.

WATCH/MULTI/EXEC đúng về logic nhưng mỗi lần đụng độ phải thử lại toàn bộ, và dưới tải cao tỉ lệ retry tăng theo tranh chấp. Lua là một round-trip cho cả đọc, tính, ghi và đặt TTL.

Lua atomic vì Redis xử lý lệnh đơn luồng và trong lúc script chạy nó không chen lệnh client khác vào giữa — không xen kẽ, chứ không phải rollback kiểu transaction. Hệ quả: script chạy lâu sẽ chặn cả server, nên giữ O(1).

-- KEYS[1]: key rate limit
-- ARGV[1]: rate (token/giây)  ARGV[2]: burst  ARGV[3]: cost  ARGV[4]: ttl (giây)
local key   = KEYS[1]
local rate  = tonumber(ARGV[1])
local burst = tonumber(ARGV[2])
local cost  = tonumber(ARGV[3])
local ttl   = tonumber(ARGV[4])

-- Dùng đồng hồ của Redis làm nguồn thời gian duy nhất cho mọi instance.
local t   = redis.call('TIME')
local now = tonumber(t[1]) + tonumber(t[2]) / 1000000

local data   = redis.call('HMGET', key, 'tokens', 'ts')
local tokens = tonumber(data[1])
local ts     = tonumber(data[2])

if tokens == nil then
  tokens = burst
  ts     = now
end

local delta = now - ts
if delta < 0 then delta = 0 end        -- bảo vệ trước trường hợp đồng hồ lùi
tokens = math.min(burst, tokens + delta * rate)

local allowed = 0
if tokens >= cost then
  tokens  = tokens - cost
  allowed = 1
end

redis.call('HSET', key, 'tokens', string.format('%.6f', tokens), 'ts', string.format('%.6f', now))
redis.call('EXPIRE', key, ttl)

local wait = 0
if allowed == 0 then
  wait = (cost - tokens) / rate
end

return { allowed, math.floor(tokens), math.ceil(wait * 1000) }

var tokenBucket = redis.NewScript(luaSource)

func (l *RedisLimiter) Check(ctx context.Context, key string, cost int) (Decision, error) {
	res, err := tokenBucket.Run(ctx, l.rdb, []string{key},
		l.ratePerSec, l.burst, cost, l.ttlSeconds).Int64Slice()
	if err != nil {
		return Decision{}, err
	}
	return Decision{
		Allowed:    res[0] == 1,
		Remaining:  int(res[1]),
		RetryAfter: time.Duration(res[2]) * time.Millisecond,
	}, nil
}

Hai bẫy trong script. Số trong Lua là double và HSET chuyển thành chuỗi theo biểu diễn mặc định, nên mình format tường minh bằng string.format('%.6f', ...). TTL phải lớn hơn burst / rate; nếu ngắn hơn, key hết hạn giữa chừng, bucket tạo lại với xô đầy, tenant vượt hạn mức âm thầm.

Biến thể INCR cũng hay được hỏi, bản đúng phải là một script duy nhất:

-- Fixed window atomic: INCR và PEXPIRE trong cùng một lần chạy script
local n = redis.call('INCR', KEYS[1])
if n == 1 then
  redis.call('PEXPIRE', KEYS[1], ARGV[1])
end
if n > tonumber(ARGV[2]) then
  return { 0, 0 }
end
return { 1, tonumber(ARGV[2]) - n }

Điểm interviewer muốn nghe: INCR và EXPIRE gọi như hai lệnh riêng rẽ là không atomic. Nếu tiến trình chết hay connection đứt giữa hai lệnh, key tồn tại mãi không có TTL: biến đếm không bao giờ reset, tenant bị chặn vĩnh viễn, bộ nhớ rò rỉ. Tránh bằng cách gộp vào Lua, SET key 0 EX <n> NX trước khi INCR, hoặc EXPIRE key <n> NX trong Redis 7.

7. Kiến trúc hai tầng để giảm round-trip

flowchart LR
  C["Client"] --> MW["Go middleware"]
  MW --> L{"Local bucket<br/>RAM, ~µs"}
  L -- "còn token" --> OK["Handler xử lý"]
  L -- "cạn cục bộ" --> RD[("Redis<br/>token bucket qua Lua EVAL<br/>atomic, ~1ms")]
  RD -- "còn token" --> OK
  RD -- "hết" --> R429["429 + Retry-After"]
  RD -. "đồng bộ quota định kỳ" .-> L

Gọi Redis cho mọi request là đúng nhưng đắt: 50.000 round-trip mỗi giây, mỗi cái là một cơ hội tăng latency; kiến trúc hai tầng đổi xấp xỉ lấy latency.

Chia tĩnh: hạn mức toàn cục chia đều số instance, mỗi instance quyết định cục bộ. Rẻ, nhưng sai khi tải không đều: instance nhận gấp ba lưu lượng từ chối sớm trong khi tổng còn thừa quota.

Cho thuê theo lô: instance giữ xô cục bộ, chỉ gọi Redis khi cần nạp thêm — xin một lô 200 token rồi tiêu dần, nên với tenant lớn một round-trip phục vụ 200 request. Cái giá: over-admission biên bằng số instance nhân kích thước lô, và quota chưa tiêu của instance chết bị treo tới khi lease hết hạn.

Đồng bộ bất đồng bộ: đếm ở local rồi đẩy lên Redis mỗi 100ms — rẻ nhất về latency, tệ nhất về chính xác, vì một đợt tăng vọt trong 100ms nhân số instance có thể vượt hạn mức rất xa.

Multi-region: mỗi region một bucket, và một bucket toàn cục cấp lô token cho từng region theo chu kỳ — token bucket phân cấp. Càng đẩy kiểm tra về local thì latency càng thấp, chính xác càng giảm; hard limit tuyệt đối thì mọi request phải qua một check atomic đồng bộ.

8. Cạm bẫy production

Hot key. Tenant chiếm 20% lưu lượng có key rơi vào đúng một hash slot, làm nóng một shard trong khi các shard khác rảnh — Redis Cluster phân mảnh theo hash slot, không chọn được chỗ đặt key. Cách xử lý: tách key thành k phần tử với hậu tố ngẫu nhiên rồi chia token đều, hoặc cấp cụm Redis riêng cho tenant.

Clock skew. Mỗi instance tự lấy time.Now() thì lệch vài trăm mili giây làm bucket phân kỳ. Để Redis làm nguồn thời gian duy nhất: script dùng redis.call('TIME'), instance chỉ gửi tham số. Script chạy trên master nên không lo replica lag.

Redis mất kết nối. Fail-open thì mất lá chắn, fail-closed thì tự tạo sự cố. Thực dụng là tầng dự phòng cục bộ: khi Redis lỗi, mỗi instance chuyển sang hạn mức bằng tổng chia số instance, chấp nhận xấp xỉ và ghi metric chế độ suy giảm; kèm circuit breaker timeout 20–50ms.

Thundering herd khi reset. Fixed window reset mọi key cùng một mốc wall-clock, nên hàng nghìn client vừa bị chặn đồng loạt thử lại. Token bucket đỡ hơn vì hồi phục liên tục theo từng key. Thêm hai biện pháp rẻ: lệch mốc cửa sổ theo hash của key, và Retry-After có jitter.

9. Observability: đo gì để biết limiter còn sống

Ba nhóm metric: bộ đếm allow/deny tách theo scope (tenant, toàn cục, IP) và tier; histogram độ trễ của chính tầng limit, vì ngân sách 5ms chỉ có ý nghĩa nếu được đo; và bộ đếm lỗi Redis. Đừng gắn nhãn theo tenant id thô — vài trăm nghìn tenant là vài trăm nghìn time series.

Alert trên tỉ lệ deny tăng bất thường (config sai hoặc bị tấn công), lỗi Redis khác không, và p99 của EVAL vượt ngân sách. Deny thấp bất thường cũng đáng alert: thường là limiter vừa ngừng hoạt động.

Kiểm chứng gồm ba phần: load test xác nhận p99 trong ngân sách và số request nhận mỗi cửa sổ khớp hạn mức trong biên sai số định trước; chaos test tắt Redis để xác nhận fail-open không đẩy database vượt giới hạn an toàn; unit test truyền thời gian tường minh vào AllowN/ReserveN.

10. Chốt lại, và mấy câu follow-up hay gặp

Mình không cần interviewer nhớ là mình biết Lua. Đáng nhớ hơn là mọi lựa chọn đều quy về một trade-off nói ra được: token bucket vì cần burst; Lua vì cần đọc–tính–ghi nguyên tử; hai tầng vì giảm round-trip; giờ Redis vì cần nguồn thời gian chung.

Vài câu follow-up hay gặp:

• Giới hạn cả IP và user? Hai tầng độc lập, từ chối nếu bất kỳ tầng nào từ chối; kiểm tra tầng cục bộ trước.
• Request nặng và nhẹ tính giống nhau? Không: cost vào script (nặng 10, nhẹ 1), tương ứng AllowN ở tầng local.
• Muốn hard limit tuyệt đối? Bỏ lease, mọi request qua một check atomic đồng bộ, chấp nhận round-trip.

Còn nếu chỉ giữ lại được một thứ từ buổi đó: mấy câu hỏi làm rõ đầu giờ không phải thủ tục cho có. Chúng là thiết kế.