Bài 38: Distributed Rate Limiting — Multi-instance Đồng Nhất

Sau bài này bạn sẽ:

• Giải thích được tại sao in-memory rate limit phá vỡ giới hạn khi scale nhiều instance.
• Hiểu Redis làm central counter giải quyết vấn đề gì và tạo ra vấn đề gì.
• Biết ba vấn đề chính (latency, SPOF, hot key) và cách xử lý từng cái.
• Nắm được pattern local budget hybrid và khi nào nên dùng.
• Hiểu clock skew ảnh hưởng sliding window thế nào và cách tiếp cận pragmatic.

Giả sử bạn cài rate limit 100 request/phút per user bằng một dictionary trong bộ nhớ của process. Khi app chạy đơn lẻ, điều đó hoạt động đúng. Khi bạn scale lên 10 instance đứng sau load balancer, mỗi instance có một counter riêng biệt, hoàn toàn độc lập.

Một user gửi request, load balancer phân tán đều ra 10 instance. Mỗi instance thấy tối đa 100 request từ user đó trước khi chặn. Nhưng tổng thực tế user đã gửi được là 100 × 10 = 1000 request — gấp 10 lần giới hạn.

User → Load Balancer
         ├── Instance 0: counter=100 → BLOCK (nhưng đã qua 100 req)
         ├── Instance 1: counter=100 → BLOCK (thêm 100 req)
         ├── Instance 2: counter=100 → BLOCK (thêm 100 req)
         └── ... × 10 instance
Total thực tế đã pass: 1000 request (limit=100 bị phá vỡ 10x)
            

Vấn đề không chỉ là số nhân 10. Khi bạn autoscale theo traffic, số instance thay đổi động — giới hạn thực tế cũng thay đổi theo, hoàn toàn ngoài tầm kiểm soát. In-memory rate limit chỉ đúng ở môi trường single-process.

Giải pháp: thay vì mỗi instance giữ counter riêng, tất cả instance đọc/ghi vào cùng một Redis key. Counter nằm ở Redis — trở thành nguồn sự thật duy nhất (single source of truth) cho toàn cụm.

User → Load Balancer
         ├── Instance 0 ─┐
         ├── Instance 1 ─┤──→ Redis: INCR rate:user:42:1748390400 → 87
         ├── Instance 2 ─┤         (tất cả cùng đọc/ghi 1 key)
         └── ... × N    ─┘
Count = 87 (chính xác toàn cụm, không phải 87 × N)
            

Mọi INCR và check trong Redis là atomic theo mặc định (single-threaded command execution). Dùng Lua script thì nhiều lệnh trở thành một transaction không bị chen ngang. Các thuật toán cụ thể (fixed window, sliding window, token bucket, GCRA) đã được bàn ở bài 33–37. Bài này không lặp lại — focus vào các vấn đề nảy sinh do distributed.

Khi chuyển sang central Redis counter, ba vấn đề mới xuất hiện:

1. Latency: mỗi request cần 1 round-trip tới Redis.
2. SPOF: Redis down thì rate limit không chạy được.
3. Hot key: global counter tập trung ghi vào 1 key.

Mỗi request vào app cần gọi Redis để check/increment counter. Một round-trip Redis trong cùng datacenter thường mất 0.3–2 ms. Với QPS thấp đến vừa, con số này không đáng kể. Với hệ thống xử lý hàng chục nghìn request/giây, tình hình khác đi.

Một số điểm cụ thể:

• Redis CPU: 50,000 req/s × mỗi req 1 Lua call → Redis xử lý 50,000 ops/s chỉ riêng rate check. Redis single-threaded cho I/O, nhưng CPU vẫn có giới hạn.
• Network round-trip: nếu Redis đặt ở region hoặc AZ khác, latency tăng lên 5–20 ms per request — hoàn toàn không chấp nhận được.
• Connection pool: nếu pool cạn kiệt, request chờ connection → latency spike.

Giảm thiểu

• Đặt Redis gần app: cùng AZ, tốt nhất cùng host (Redis Cluster shard gần). Latency xuống <1 ms.
• Pipelining: nếu một request cần check nhiều limit (per-user, per-IP, per-endpoint), gộp thành 1 pipeline thay vì 3 round-trip riêng.
• Local hybrid: xem Section 7 — giảm 10–100× số lần gọi Redis.

# Pipelining: check 3 limit cùng lúc trong 1 round-trip
async def check_multi_limits(redis, user_id, ip, endpoint):
    pipe = redis.pipeline(transaction=False)
    now_window = int(time.time() // 60)

    pipe.incr(f"rl:user:{user_id}:{now_window}")
    pipe.expire(f"rl:user:{user_id}:{now_window}", 120)
    pipe.incr(f"rl:ip:{ip}:{now_window}")
    pipe.expire(f"rl:ip:{ip}:{now_window}", 120)
    pipe.incr(f"rl:ep:{endpoint}:{now_window}")
    pipe.expire(f"rl:ep:{endpoint}:{now_window}", 120)

    results = await pipe.execute()
    user_count = results[0]
    ip_count   = results[2]
    ep_count   = results[4]

    return user_count <= 100 and ip_count <= 200 and ep_count <= 5000
            

Pipeline không giảm số lệnh Redis thực thi, nhưng giảm số round-trip từ N xuống 1. Với ba limit trên, tiết kiệm 2/3 network latency.

Khi rate limit phụ thuộc hoàn toàn vào Redis, Redis down có nghĩa là rate limit không check được. Lúc đó bạn phải chọn một trong hai hướng:

Fail closed (deny khi Redis không phản hồi)

Mọi request đều bị chặn khi Redis unreachable. Ưu điểm: không có request nào vượt limit trong lúc Redis down. Nhược điểm: user hợp lệ bị block — Redis hiccup 5 giây sẽ block toàn bộ traffic 5 giây.

Fail closed phù hợp khi chi phí abuse cao hơn chi phí downtime: thanh toán, xác thực OTP, API tài chính.

Fail open (cho qua khi Redis không phản hồi)

Mọi request đều được phép khi Redis unreachable. Ưu điểm: availability không bị ảnh hưởng. Nhược điểm: trong thời gian Redis down, rate limit không hoạt động — kẻ abuse có thể tận dụng.

Fail open phù hợp khi availability quan trọng hơn và window Redis down ngắn: API đọc dữ liệu công khai, search API, CDN origin.

Pattern thực tế: fail open + local fallback

Thay vì chọn thuần fail open hay fail closed, dùng local counter làm fallback khi Redis down. Local counter không chính xác như Redis (mỗi instance đếm riêng lại), nhưng vẫn tốt hơn không có gì:

import time
import logging
from collections import defaultdict
from redis import ConnectionError, TimeoutError

# Local fallback counter (per-process, reset mỗi 60s)
_local_counts = defaultdict(lambda: {"count": 0, "window": 0})

def local_fallback_allow(user_id: str, limit: int) -> bool:
    now_window = int(time.time() // 60)
    entry = _local_counts[user_id]
    if entry["window"] != now_window:
        entry["count"] = 0
        entry["window"] = now_window
    entry["count"] += 1
    return entry["count"] <= limit

def is_allowed(redis, user_id: str, limit: int, window: int) -> bool:
    try:
        return redis_rate_limit(redis, user_id, limit, window)
    except (ConnectionError, TimeoutError) as e:
        logging.warning("Redis unreachable, fallback to local counter: %s", e)
        # Local limit = limit / N_instances (ước lượng)
        return local_fallback_allow(user_id, limit // 10)
            

Lưu ý: local limit trong fallback nên nhỏ hơn giới hạn thật (ví dụ chia cho số instance ước tính). Nếu có 10 instance và mỗi instance dùng local limit = limit/10, tổng vẫn xấp xỉ limit ban đầu.

Circuit breaker

Để tránh mọi request đều phải đợi timeout Redis khi Redis down, kết hợp với circuit breaker. Khi Redis timeout liên tục, circuit mở: mọi request dùng local fallback ngay, không thử Redis nữa. Sau thời gian nhất định, circuit half-open: thử lại Redis.

Bài 18 đã bàn hot key trong caching. Với rate limiting, vấn đề xuất hiện đặc biệt với global counter — ví dụ limit tổng số request/giây cho toàn hệ thống (không phân per-user).

Khi 50,000 req/s đổ vào app và mọi instance đều ghi vào key rl:global:1748390400, tất cả ghi tập trung vào một Redis slot. Đây là hot key điển hình: throughput ghi cao, không có cách spread tự nhiên.

Per-user key — tự nhiên spread

Với per-user rate limit (rl:user:{user_id}:{window}), các key khác nhau theo user_id — tự nhiên phân tán ra nhiều slot trong Redis Cluster. Đây là lý do per-user limit thường không gặp hot key.

Sharded global counter

Nếu cần global limit, thay vì 1 key, chia thành N sub-counter:

import random

N_SHARDS = 10

async def global_incr(redis, window: int) -> int:
    shard = random.randint(0, N_SHARDS - 1)
    key = f"rl:global:{window}:s{shard}"
    count = await redis.incr(key)
    await redis.expire(key, 120)
    return count

async def global_total(redis, window: int) -> int:
    keys = [f"rl:global:{window}:s{i}" for i in range(N_SHARDS)]
    values = await redis.mget(*keys)
    return sum(int(v or 0) for v in values)
            

Khi ghi: random chọn 1 trong N shard để INCR — ghi load spread ra N key. Khi đọc tổng để check: đọc tất cả N key và cộng lại (có thể pipeline). Trade-off: đọc tổng tốn N lần get thay vì 1, và count không tức thì chính xác (các shard được đọc tại các thời điểm hơi khác nhau). Với N = 10, đây thường là đủ để phá vỡ hot key bottleneck.

Với QPS cực cao, ngay cả 1 ms per request cũng trở thành nút cổ chai đáng kể. Một cách giảm số lần gọi Redis là local budget: mỗi instance "claim" một lô token từ Redis, dùng hết lô mới claim tiếp.

Ví dụ: global limit 1000 req/s, 10 instance. Thay vì mỗi request gọi Redis, mỗi instance claim 100 token một lần từ Redis, sau đó tự tiêu dùng local. Khi local budget hết, claim thêm 100 từ Redis. Số lần gọi Redis giảm từ 1000 × 10 = 10,000 xuống còn 10 × (1000/100) = 100 lần/giây — giảm 100×.

import asyncio
import time

class LocalBudgetRateLimiter:
    def __init__(self, redis, global_key: str, batch_size: int, global_limit: int):
        self.redis = redis
        self.global_key = global_key
        self.batch_size = batch_size
        self.global_limit = global_limit
        self._local_tokens = 0
        self._lock = asyncio.Lock()

    async def _claim_batch(self, window: int) -> int:
        """Claim batch_size tokens từ Redis. Trả về số token thực sự được cấp."""
        key = f"{self.global_key}:{window}"
        # Atomic: INCRBY và kiểm tra không vượt global_limit
        lua = """
        local current = redis.call('INCRBY', KEYS[1], ARGV[1])
        if current > tonumber(ARGV[2]) then
            local excess = current - tonumber(ARGV[2])
            local granted = tonumber(ARGV[1]) - excess
            if granted < 0 then granted = 0 end
            redis.call('DECRBY', KEYS[1], excess)
            return granted
        end
        redis.call('EXPIRE', KEYS[1], 120)
        return tonumber(ARGV[1])
        """
        granted = await self.redis.eval(lua, 1, key, self.batch_size, self.global_limit)
        return int(granted)

    async def is_allowed(self) -> bool:
        async with self._lock:
            if self._local_tokens > 0:
                self._local_tokens -= 1
                return True
            window = int(time.time() // 60)
            granted = await self._claim_batch(window)
            if granted <= 0:
                return False
            # Dùng 1 token ngay, giữ phần còn lại
            self._local_tokens = granted - 1
            return True
            

Trade-off

Local budget không chính xác tuyệt đối:

• Waste: một instance claim 100 token nhưng chỉ dùng 30 (traffic giảm đột ngột), 70 token bị waste — tổng thực tế nhỏ hơn global limit.
• Overshoot nhỏ: khi nhiều instance claim cùng lúc gần limit, có thể tổng vượt một chút trước khi Lua script cắt lại.
• Window boundary: khi sang window mới, instance vẫn có local token từ window cũ — cần reset local budget theo window.

Với QPS bình thường đến cao (dưới 10,000 req/s per instance), central Redis đã đủ. Local hybrid phù hợp khi Redis latency trở thành bottleneck thực sự đo được — không phải tối ưu sớm.

Một biến thể rõ ràng hơn của local budget là token reservation: instance claim trước một batch từ Redis, tiêu dùng local, hết lại claim. Logic đơn giản hơn vì không cần Lua phức tạp — chỉ cần INCRBY atomic:

# Pseudocode
local_tokens = 0

function allow():
    if local_tokens > 0:
        local_tokens -= 1
        return ALLOW

    # Claim batch từ Redis
    new_total = INCRBY redis_key batch_size
    if new_total > global_limit:
        # Vượt limit — trả lại phần vượt
        DECRBY redis_key (new_total - global_limit)
        return DENY

    local_tokens = batch_size - 1  # -1 vì request hiện tại tiêu 1
    return ALLOW
            

Điểm khác biệt với Section 7: phần "trả lại token" không hoàn toàn chính xác trong môi trường concurrent nhiều instance (race condition nhỏ), nhưng thực tế sai số chấp nhận được. Nếu cần chính xác tuyệt đối, dùng Lua script như Section 7.

Khi dùng Redis Cluster, key được hash vào một trong 16,384 slot, mỗi slot thuộc về một master node. Per-user key (rl:user:{user_id}:{window}) tự động phân tán: các user_id khác nhau hash vào các slot khác nhau, load spread tốt.

Lua script với nhiều key trong Cluster

Lua script trong Redis Cluster có ràng buộc: tất cả key trong script phải thuộc cùng một slot. Nếu script dùng key rl:user:42:tokens và rl:user:42:ts (hai key cho token bucket), chúng phải cùng slot.

Redis Cluster dùng hash tag để kiểm soát điều này: phần trong dấu {} của key xác định slot, phần còn lại bị bỏ qua khi hash.

# Không có hash tag: hai key có thể khác slot
# "rl:user:42:tokens" và "rl:user:42:ts" → có thể khác slot

# Dùng hash tag {user:42}: đảm bảo cùng slot
key_tokens = "rl:{user:42}:tokens"
key_ts     = "rl:{user:42}:ts"
# Cả hai đều hash theo "user:42" → cùng slot → Lua script hợp lệ
            

Với sliding window log hay token bucket cần 2–3 key cùng lúc, hash tag là bắt buộc khi dùng Cluster.

Global counter trong Cluster

Global counter 1 key sẽ rơi vào 1 slot của 1 node — không tận dụng được Cluster. Cách tiếp cận: sharded counter (Section 6) với hash tag khác nhau cho từng shard để spread ra nhiều node:

# Mỗi shard có hash tag riêng → các node khác nhau
keys = [f"rl:{{global-s{i}}}:{window}" for i in range(10)]
# "global-s0", "global-s1", ... hash vào các slot khác nhau
            

Sliding window và token bucket đều cần timestamp để tính: "khi nào window bắt đầu", "bao lâu kể từ lần refill cuối". Mỗi instance dùng đồng hồ local của process — và đồng hồ các máy không hoàn toàn đồng bộ.

Clock skew vài millisecond thường không gây vấn đề với window 60 giây. Nhưng có một số tình huống đáng chú ý:

• Sliding window 1 giây (high-precision): skew 50ms trên window 1000ms = sai số 5% — có thể chấp nhận hoặc không, tuỳ yêu cầu.
• Instance bị drift đồng hồ: VM bị suspend/resume, container sau migration — đồng hồ có thể lệch vài giây.

Dùng Redis TIME thay đồng hồ local

Redis có lệnh TIME trả về Unix timestamp microsecond từ server. Dùng Redis TIME làm nguồn clock duy nhất:

# Lấy timestamp từ Redis thay vì time.time()
async def get_redis_time(redis) -> float:
    seconds, microseconds = await redis.time()
    return seconds + microseconds / 1_000_000
            

Nhưng có một giới hạn quan trọng: Redis không cho phép gọi TIME trong Lua script (non-deterministic — sẽ phá vỡ replication). Cách xử lý là gọi TIME trước rồi truyền vào script qua ARGV:

async def redis_rate_limit_with_server_time(redis, user_id: str, limit: int) -> bool:
    # Lấy server time trước
    seconds, microseconds = await redis.time()
    now_ms = seconds * 1000 + microseconds // 1000

    lua = """
    local key = KEYS[1]
    local now_ms = tonumber(ARGV[1])
    local limit  = tonumber(ARGV[2])
    local window = 60000  -- 60 giây tính bằng ms

    -- sliding window log logic (rút gọn)
    redis.call('ZREMRANGEBYSCORE', key, 0, now_ms - window)
    local count = redis.call('ZCARD', key)
    if count < limit then
        redis.call('ZADD', key, now_ms, now_ms)
        redis.call('EXPIRE', key, 120)
        return 1
    end
    return 0
    """
    result = await redis.eval(lua, 1, f"rl:user:{user_id}", now_ms, limit)
    return bool(result)
            

Lưu ý: truyền now từ app qua ARGV không loại bỏ hoàn toàn skew — chỉ là app đọc TIME từ Redis rồi truyền lại. Nếu instance A đọc TIME, sau đó gọi Lua 5ms sau, timestamp vẫn là của lúc đọc. Kết hợp NTP trên toàn bộ máy chủ là biện pháp pragmatic nhất.

Thực tế

NTP đồng bộ đồng hồ các instance — skew thường dưới 10ms trong môi trường cloud. Với window ≥1 giây, đây là đủ. Nếu cần độ chính xác cao hơn (window 100ms), dùng PTP (Precision Time Protocol) hoặc đồng hồ hardware synchronized.

Khi app deploy ở nhiều region (us-east, eu-west, ap-southeast), mỗi region có Redis cluster riêng. Request từ một user có thể đến bất kỳ region nào — và count không được sync giữa các Redis.

Ba hướng tiếp cận, mỗi cái có trade-off riêng:

Region-local limit

Mỗi region có limit độc lập. User có limit 1000/phút → thực tế có thể gửi tới 1000 × N_region. Đây là cách đơn giản nhất và được chấp nhận trong hầu hết use case. Lý do: user thường chỉ kết nối tới 1 region gần nhất — latency khiến việc phân tán giả tạo qua nhiều region không dễ. Nếu cần bảo vệ khỏi abuse mạng, giới hạn per-region đã đủ. Giới hạn thật sự (abuse nghiêm trọng) thường được xử lý ở tầng khác (IP ban, WAF).

Global Redis (cross-region)

Đặt Redis ở một region, tất cả region gọi qua. Latency tăng 50–150ms per request (cross-region round-trip). Không thực tế cho production traffic cao.

CRDT-based counter

CRDT (Conflict-free Replicated Data Type) counter có thể merge từ nhiều region mà không cần coordination. Redis 7.x chưa có CRDT counter built-in (chỉ có ở Redis Enterprise). Tự implement CRDT counter đủ phức tạp để cần cân nhắc kỹ. Đây là giải pháp phù hợp khi cần global accuracy thật sự và đội kỹ thuật đủ mạnh.

Quyết định thực tế

Hầu hết hệ thống chọn region-local limit. Nếu limit per-region được set thấp đủ so với mục tiêu bảo vệ, hiệu quả vẫn đủ tốt trong thực tế.

Distributed rate limiting cần được monitor ở ít nhất ba tầng:

Tầng application

• Rate limit hit count: số lần request bị chặn (HTTP 429) per user, per IP, per endpoint. Spike bất thường → có thể là attack hoặc bug trong client.
• Fallback activation rate: số lần local fallback kích hoạt thay Redis. Fallback rate cao → Redis đang có vấn đề.

Tầng Redis

• Latency P99 của rate check command: nếu P99 vượt 5ms, cần xem lại Lua script complexity hoặc Redis load.
• Hot key detection: dùng redis-cli --hotkeys (yêu cầu maxmemory-policy allkeys-lfu hoặc volatile-lfu) để phát hiện key bị ghi nhiều bất thường.
• ops/sec per command: INFO commandstats — xem EVAL, INCR, ZADD chiếm bao nhiêu % tổng ops.

Tầng consistency

• Log sample: thỉnh thoảng log actual count từ Redis cùng với decision allow/deny → verify logic đúng.
• Alert khi rate limit hit rate tăng đột biến trong thời gian ngắn — có thể là DDoS hoặc lỗi deploy.

Anti-pattern

• In-memory counter khi multi-instance: limit thực tế = giới hạn × số instance. Thường được phát hiện muộn khi traffic tăng.
• Fail closed mặc định không có kế hoạch: Redis hiccup thường xuyên xảy ra (deploy, GC pause, network blip) — fail closed thuần sẽ block user hợp lệ mà không báo lỗi rõ ràng.
• Global counter 1 key cho toàn hệ thống: toàn bộ ghi tập trung vào 1 Redis slot. Hot key bottleneck rõ ràng khi QPS cao.
• Không xử lý clock skew: sliding window với đồng hồ không sync sẽ có sai số nhỏ nhưng khó debug. Đặc biệt nguy hiểm khi container được reschedule sang host khác.
• 1 Redis call per request ở QPS rất cao: 100,000 req/s × 1 Lua eval/req = 100,000 eval/s trên 1 Redis instance. Redis có thể saturate CPU trước khi network hoặc memory.

Best practice

• Per-user key: tự nhiên spread load trên Cluster, tránh hot key.
• Fail open + local fallback counter: availability không bị ảnh hưởng khi Redis transient failure.
• Circuit breaker trước Redis: tránh mọi request phải đợi timeout khi Redis down.
• Local hybrid budget chỉ khi đã đo được Redis latency là bottleneck thực sự.
• Hash tag trong Cluster: đảm bảo multi-key Lua script hợp lệ.
• NTP sync: đủ cho hầu hết use case (window ≥1s).
• Monitor P99 latency + fallback rate: hai metric quan trọng nhất.

Bảng dưới tóm tắt khi nào chọn gì:

Central Redis là lựa chọn mặc định. Local hybrid là tối ưu có chủ ý khi đã xác định Redis latency là bottleneck qua đo đạc thực tế, không phải tối ưu phòng ngừa.

Bài tiếp theo

Bài 39 áp dụng rate limiting vào một bài toán cụ thể: login protection — chống brute force mật khẩu với Redis, xử lý lockout per-user, per-IP và các edge case như IP shared (NAT), progressive delay.

Tham khảo

• Redis Docs — INCR
• Redis Docs — TIME
• Redis Cluster Specification — Hash slots & hash tags
• Redis Docs — EVAL (Lua scripting)
• Stripe Engineering — Scaling your API with rate limiters
• Kong — How to design a scalable rate limiting algorithm