PENALGO

Giao diện

Token Bucket — Thuật toán giới hạn tốc độ ​

Ngày 21 tháng 10 năm 2016, cuộc tấn công DDoS vào Dyn DNS bằng botnet Mirai đã đánh sập Twitter, GitHub, Netflix, và hàng chục dịch vụ lớn — lưu lượng tấn công đạt 1.2 Tbps. Lớp phòng thủ đầu tiên mà mọi hệ thống cần có trước khi nghĩ đến firewall hay WAF chính là rate limiting. Và thuật toán phổ biến nhất cho rate limiting là Token Bucket.

Token Bucket cân bằng giữa hai yêu cầu mâu thuẫn: cho phép burst traffic hợp lệ (người dùng mở 10 tab cùng lúc) nhưng vẫn chặn lạm dụng (bot gửi 10,000 request/giây). Nginx, AWS API Gateway, Cloudflare, Kong — tất cả đều triển khai biến thể của thuật toán này.

Hiểu Token Bucket không chỉ giúp bạn cấu hình rate limit đúng cách, mà còn là nền tảng để thiết kế bất kỳ hệ thống nào cần kiểm soát tốc độ: từ API throttling đến network QoS, từ message queue đến CPU scheduler.

Bức tranh tư duy ​

Hình dung một bể chứa nước mưa ở vùng nông thôn Việt Nam. Bể có sức chứa tối đa (capacity), nước mưa rơi đều đặn vào bể (refill rate), và mỗi lần tưới vườn lấy ra một gáo nước (consume). Khi bể đầy, nước mưa tràn ra ngoài — không tích thêm được. Khi bể cạn, phải đợi mưa rơi thêm mới tưới được tiếp.

text
              ┌────────────────────────┐
              │      BỂ CHỨA TOKEN     │
              │   Sức chứa: 10 token   │
              │  ┌─────────────────┐   │
   Nạp thêm  │  │ ●●●●●●●●●●     │   │    Tiêu thụ
  (2 token/s) │  │ (hiện tại: 10)  │   │  (1 token/request)
       →      │  └─────────────────┘   │      →
              └────────────────────────┘

Thời điểm 0: Bể đầy (10 token)
Thời điểm 0: 5 request đến → tiêu 5 token → còn 5
Thời điểm 1: Nạp 2 token → 7 token
Thời điểm 1: 10 request đến → tiêu 7, 3 request BỊ TỪ CHỐI
Thời điểm 2: Nạp 2 token → 2 token sẵn sàng

Điểm khác biệt cốt lõi: Token Bucket cho phép burst — nếu bể đầy, bạn có thể tưới nhiều lần liên tiếp. Đây là ưu điểm so với Leaky Bucket (nước chảy đều đặn, không burst).

📌 Khi nào analogy không còn chính xác

Bể nước thật có nước rơi liên tục. Token Bucket trong code thường tính token "lười" (lazy refill) — chỉ tính số token mới khi có request đến, dựa trên thời gian đã trôi qua. Không có background thread nào thực sự "đổ token" vào bể.

Cốt lõi kỹ thuật ​

Cơ chế Lazy Refill ​

Thay vì chạy timer nạp token đều đặn (tốn tài nguyên), Token Bucket tính token tại thời điểm nhận request:

text
tokens_mới = min(capacity, tokens_hiện_tại + (thời_gian_trôi × refill_rate))

Đây là kỹ thuật lazy evaluation — chỉ tính khi cần. Từ góc nhìn bên ngoài, kết quả giống hệt timer-based refill.

Hai tham số cốt lõi ​

Tham sốÝ nghĩaVí dụ thực tế
capacityKích thước burst tối đa50 request cùng lúc (mở nhiều tab)
refill_rateTốc độ bền vững (sustained rate)10 request/giây trung bình

Triển khai cơ bản ​

cpp
#include <chrono>
#include <mutex>
#include <algorithm>

class TokenBucket {
    double capacity_;
    double refillRate_;
    double tokens_;
    std::chrono::steady_clock::time_point lastRefill_;
    std::mutex mtx_;

public:
    TokenBucket(double capacity, double refillRate)
        : capacity_(capacity), refillRate_(refillRate),
          tokens_(capacity),
          lastRefill_(std::chrono::steady_clock::now()) {}

    bool allow(double tokensNeeded = 1.0) {
        std::lock_guard<std::mutex> lock(mtx_);
        refill();
        if (tokens_ >= tokensNeeded) {
            tokens_ -= tokensNeeded;
            return true;
        }
        return false;
    }

private:
    void refill() {
        auto now = std::chrono::steady_clock::now();
        double elapsed = std::chrono::duration<double>(
            now - lastRefill_).count();
        tokens_ = std::min(capacity_, tokens_ + elapsed * refillRate_);
        lastRefill_ = now;
    }
};
python
import time
from threading import Lock


class TokenBucket:
    """Token Bucket rate limiter — thread-safe, O(1) mỗi request."""

    def __init__(self, capacity: float, refill_rate: float) -> None:
        self.capacity = capacity
        self.refill_rate = refill_rate
        self.tokens = capacity
        self._last_refill = time.monotonic()
        self._lock = Lock()

    def allow(self, tokens_needed: float = 1.0) -> bool:
        with self._lock:
            self._refill()
            if self.tokens >= tokens_needed:
                self.tokens -= tokens_needed
                return True
            return False

    def _refill(self) -> None:
        now = time.monotonic()
        elapsed = now - self._last_refill
        self.tokens = min(
            self.capacity,
            self.tokens + elapsed * self.refill_rate
        )
        self._last_refill = now
java
public class TokenBucket {
    private final double capacity;
    private final double refillRate;
    private double tokens;
    private long lastRefillNanos;

    public TokenBucket(double capacity, double refillRate) {
        this.capacity = capacity;
        this.refillRate = refillRate;
        this.tokens = capacity;
        this.lastRefillNanos = System.nanoTime();
    }

    public synchronized boolean allow(double tokensNeeded) {
        refill();
        if (tokens >= tokensNeeded) {
            tokens -= tokensNeeded;
            return true;
        }
        return false;
    }

    private void refill() {
        long now = System.nanoTime();
        double elapsed = (now - lastRefillNanos) / 1e9;
        tokens = Math.min(capacity, tokens + elapsed * refillRate);
        lastRefillNanos = now;
    }
}
go
package ratelimit

import (
    "sync"
    "time"
)

type TokenBucket struct {
    capacity   float64
    refillRate float64
    tokens     float64
    lastRefill time.Time
    mu         sync.Mutex
}

func NewTokenBucket(capacity, refillRate float64) *TokenBucket {
    return &TokenBucket{
        capacity:   capacity,
        refillRate: refillRate,
        tokens:     capacity,
        lastRefill: time.Now(),
    }
}

func (tb *TokenBucket) Allow(tokensNeeded float64) bool {
    tb.mu.Lock()
    defer tb.mu.Unlock()

    tb.refill()
    if tb.tokens >= tokensNeeded {
        tb.tokens -= tokensNeeded
        return true
    }
    return false
}

func (tb *TokenBucket) refill() {
    now := time.Now()
    elapsed := now.Sub(tb.lastRefill).Seconds()
    tb.tokens = min(tb.capacity, tb.tokens+elapsed*tb.refillRate)
    tb.lastRefill = now
}

func min(a, b float64) float64 {
    if a < b { return a }
    return b
}

Token Bucket vs Leaky Bucket ​

Đặc điểmToken BucketLeaky Bucket
Burst✅ Cho phép burst đến capacity❌ Xử lý đều đặn, không burst
Hình dạng trafficBursty, theo đợtSmooth, đều đặn
Use caseAPI rate limitingNetwork QoS, traffic shaping
Triển khaiĐơn giản hơnCần queue cho request chờ
Sản phẩm dùngNginx, AWS API GatewayNetwork switch, tc (Linux)

Thực chiến ​

Tình huống: Multi-Key Rate Limiter cho API Gateway ​

Bối cảnh: API gateway phục vụ 10,000 user đồng thời. Mỗi user được phép 100 request/phút, burst tối đa 20 request cùng lúc. Cần per-user limiting, không phải global.

Mục tiêu: Rate limiter trả về HTTP 429 kèm header Retry-After khi user vượt giới hạn.

python
import time
from threading import Lock


class PerUserRateLimiter:
    """Rate limiter per-user với Retry-After header support."""

    def __init__(self, capacity: float, refill_rate: float) -> None:
        self.capacity = capacity
        self.refill_rate = refill_rate
        self._buckets: dict[str, tuple[float, float]] = {}
        self._lock = Lock()

    def check(self, user_id: str) -> tuple[bool, float]:
        """
        Kiểm tra và tiêu thụ token.

        Returns:
            (allowed, retry_after_seconds)
        """
        now = time.monotonic()

        with self._lock:
            tokens, last_refill = self._buckets.get(
                user_id, (self.capacity, now)
            )

            # Lazy refill
            elapsed = now - last_refill
            tokens = min(self.capacity, tokens + elapsed * self.refill_rate)

            if tokens >= 1.0:
                tokens -= 1.0
                self._buckets[user_id] = (tokens, now)
                return True, 0.0

            # Tính thời gian chờ
            deficit = 1.0 - tokens
            retry_after = deficit / self.refill_rate
            self._buckets[user_id] = (tokens, now)
            return False, retry_after


# Tích hợp với Flask/FastAPI
def rate_limit_middleware(limiter: PerUserRateLimiter):
    """Middleware pattern cho web framework."""
    def middleware(request, call_next):
        user_id = request.headers.get("X-User-ID", request.client.host)
        allowed, retry_after = limiter.check(user_id)

        if not allowed:
            return JSONResponse(
                status_code=429,
                content={"error": "Vượt giới hạn tốc độ"},
                headers={"Retry-After": str(int(retry_after) + 1)},
            )
        return call_next(request)
    return middleware

Phân tích:

  • Per-user bucket thay vì global → 1 user lạm dụng không ảnh hưởng user khác
  • Lazy refill: không cần background thread, bucket chỉ tính token khi bị truy vấn
  • Retry-After header giúp client biết khi nào thử lại thay vì retry bừa
  • Vấn đề memory: 10,000 user × tuple 2 float ≈ 160KB — chấp nhận được. Với 10M user, cần LRU eviction

Tình huống: Cấu hình Nginx Rate Limiting ​

Bối cảnh: Reverse proxy Nginx bảo vệ backend API. Cho phép 10 request/giây trung bình, burst 20 request.

nginx
# Khai báo zone rate limit — 10MB shared memory, 10 req/s per IP
limit_req_zone $binary_remote_addr zone=api_limit:10m rate=10r/s;

server {
    location /api/ {
        # burst=20: cho phép tối đa 20 request "xếp hàng"
        # nodelay: xử lý burst ngay, không delay
        limit_req zone=api_limit burst=20 nodelay;

        # Trả 429 thay vì 503 mặc định
        limit_req_status 429;

        proxy_pass http://backend;
    }

    # Endpoint quan trọng — rate limit chặt hơn
    location /api/auth/login {
        limit_req zone=api_limit burst=5 nodelay;
        limit_req_status 429;
        proxy_pass http://backend;
    }
}

Phân tích:

  • $binary_remote_addr dùng 4 bytes/IP thay vì text IP — tiết kiệm memory
  • 10m shared zone chứa ~160,000 IP states — đủ cho hầu hết hệ thống
  • nodelay quan trọng: không có nó, burst request bị delay giả tạo, gây timeout client
  • Login endpoint rate limit chặt hơn — chống brute-force password

Sai lầm điển hình ​

❌ Sai lầm 1: Global rate limit thay vì per-user ​

Vấn đề: Dùng một bucket duy nhất cho toàn bộ hệ thống.

python
# SAI: 1 user spam → tất cả user bị chặn
global_bucket = TokenBucket(capacity=1000, refill_rate=100)

def handle_request(request):
    if not global_bucket.allow():
        return error_429()

Tại sao sai: User A gửi 1,000 request/giây → quota cạn → User B (bình thường) cũng bị từ chối. Trong production, đây là denial-of-service nội bộ.

python
# ĐÚNG: Mỗi user có bucket riêng
per_user_limiter = PerUserRateLimiter(capacity=20, refill_rate=10)

def handle_request(request):
    user_id = extract_user_id(request)
    allowed, retry = per_user_limiter.check(user_id)
    if not allowed:
        return error_429(retry_after=retry)

❌ Sai lầm 2: Capacity quá thấp — chặn traffic hợp lệ ​

Vấn đề: Đặt capacity = 1 trong khi browser mở trang web gửi 5-10 request đồng thời.

python
# SAI: Người dùng bình thường bị chặn 80% request
config = TokenBucket(capacity=1, refill_rate=10)
# Browser mở trang → HTML + 5 API calls + 3 images = 9 request
# → 8 request bị reject ngay lập tức!

Tại sao sai: Capacity cần phản ánh burst pattern hợp lệ. Trình duyệt, mobile app, và microservice đều gửi request theo đợt.

python
# ĐÚNG: Capacity đủ cho burst hợp lệ
config = TokenBucket(capacity=30, refill_rate=10)
# Browser burst 9 request → tất cả được phục vụ
# Sustained rate vẫn giới hạn 10 req/s

❌ Sai lầm 3: Không trả Retry-After header ​

Vấn đề: Từ chối request mà không cho client biết khi nào thử lại.

python
# SAI: Client retry ngay → vẫn bị chặn → retry lại → DDoS chính server
if not bucket.allow():
    return {"error": "Rate limited"}, 429

Tại sao sai: Không có Retry-After, client thường retry ngay lập tức hoặc theo exponential backoff mù. Hàng nghìn client retry cùng lúc tạo thundering herd — tệ hơn traffic ban đầu.

python
# ĐÚNG: Header Retry-After cho client biết chính xác
allowed, wait_time = bucket.try_acquire()
if not allowed:
    return (
        {"error": "Vượt giới hạn", "retry_after": round(wait_time, 1)},
        429,
        {"Retry-After": str(int(wait_time) + 1)}
    )

❌ Sai lầm 4: Dùng wall-clock time thay vì monotonic clock ​

Vấn đề: Dùng time.time() hoặc System.currentTimeMillis() để tính elapsed time.

python
# SAI: NTP sync có thể đẩy clock lùi → elapsed âm → token "vô hạn"
self._last_refill = time.time()
# ...
elapsed = time.time() - self._last_refill  # Có thể âm!

Tại sao sai: Wall-clock bị NTP điều chỉnh. Nếu clock nhảy lùi 1 giờ, elapsed = -3600 giây, token trở thành số âm rất lớn → mọi request bị chặn. Nếu clock nhảy tới, token được nạp quá nhiều → rate limit vô hiệu.

python
# ĐÚNG: Monotonic clock không bị NTP ảnh hưởng
self._last_refill = time.monotonic()  # Python
# System.nanoTime()                    // Java
# std::chrono::steady_clock            // C++
# time.Now()                           // Go (đã monotonic)

Under the Hood ​

Hiệu năng ​

Thao tácTimeSpaceGhi chú
allow() — single bucketO(1)O(1)Chỉ 1 phép trừ + 1 phép so sánh
Per-user lookupO(1) amortizedO(U)U = số user đang active, HashMap
Nginx limit_reqO(1)O(M)M = kích thước shared memory zone
Redis redis-cellO(1)O(K)K = số key, GCRA algorithm

Nội bộ triển khai ​

Lazy refill vs Timer-based refill: Lazy refill (tính token khi có request) tốt hơn timer (background thread nạp token) vì:

  • Không tốn CPU khi không có traffic
  • Không cần timer/goroutine cho mỗi bucket
  • Exact same behavior từ góc nhìn bên ngoài

Thread-safety: Lock trên mỗi bucket (fine-grained locking) tốt hơn 1 lock cho tất cả bucket. Contention chỉ xảy ra khi 2 request của cùng 1 user đến đồng thời — rất hiếm so với global lock.

Distributed rate limiting: Single-server Token Bucket không đủ khi có nhiều server. Giải pháp:

  • Redis centralized: Mỗi server call Redis trước khi cho phép request. Thêm ~1ms latency nhưng chính xác.
  • Sliding window counter trên Redis: INCR key + EXPIRE — đơn giản hơn nhưng kém chính xác ở ranh giới window.
  • Local + sync: Mỗi server có local bucket, đồng bộ định kỳ với Redis. Nhanh hơn nhưng overshoot ~10%.

Trade-offs ​

Khi NÊN dùng Token BucketKhi KHÔNG NÊN dùng
API rate limiting per-user/per-IPTraffic shaping cần output đều đặn (→ Leaky Bucket)
Cho phép burst traffic hợp lệStrict real-time constraint (→ fixed window)
Resource protection (DB connection, file handle)Distributed system cần chính xác tuyệt đối (→ Redis sliding window)
Đơn giản, ít overheadCần priority queue cho request chờ

Checklist ghi nhớ ​

✅ Checklist triển khai

Thiết kế rate limiter

  • [ ] Xác định refill_rate từ SLA/capacity: "API chịu được bao nhiêu req/s?"
  • [ ] Đặt capacity dựa trên burst pattern hợp lệ: browser, mobile, microservice
  • [ ] Per-user/per-IP bucket — KHÔNG dùng global bucket
  • [ ] Luôn trả Retry-After header khi reject

Triển khai

  • [ ] Dùng monotonic clock (time.monotonic, System.nanoTime, steady_clock)
  • [ ] Thread-safe: lock per-bucket, không global lock
  • [ ] Lazy refill: tính token khi có request, không dùng background timer
  • [ ] Memory cleanup: LRU eviction cho bucket không active

Production checklist

  • [ ] Monitoring: log rate limit events (user_id, remaining tokens, retry_after)
  • [ ] Nginx: limit_req_status 429 — mặc định là 503, gây nhầm với server error
  • [ ] Nginx: nodelay cho burst — tránh delay giả tạo
  • [ ] Distributed: Redis hoặc sliding window counter nếu nhiều server

Bài tập luyện tập ​

Bài 1: Triển khai TokenBucket cơ bản — Foundation ​

Đề bài: Viết class TokenBucket với capacity=5, refill_rate=1 token/giây. Gọi allow() 5 lần liên tiếp → đều trả True. Gọi lần thứ 6 → trả False. Đợi 2 giây → gọi 2 lần → đều True.

🧠 Quiz

Câu hỏi kiểm tra: Sau khi bucket cạn hoàn toàn (0 token), cần đợi bao lâu để gọi được 3 request liên tiếp?

  • [ ] A. 1 giây (refill_rate = 1/s, capacity = 5)
  • [ ] B. 2 giây (1 token/s × 2 = 2 token, không đủ 3)
  • [x] C. 3 giây (1 token/s × 3 = 3 token, đủ cho 3 request)
  • [ ] D. 5 giây (phải đợi đầy bucket) Giải thích: Mỗi giây nạp 1 token. Cần 3 token cho 3 request → đợi 3 giây. Không cần đợi đầy bucket — chỉ cần đủ token cho số request cần thiết.
💡 Gợi ý
  • Dùng time.monotonic() để tính thời gian
  • _refill() gọi trước mỗi allow()
  • tokens = min(capacity, tokens + elapsed * rate)
✅ Lời giải
python
import time

class TokenBucket:
    def __init__(self, capacity: float, refill_rate: float) -> None:
        self.capacity = capacity
        self.refill_rate = refill_rate
        self.tokens = capacity
        self._last = time.monotonic()

    def allow(self) -> bool:
        now = time.monotonic()
        self.tokens = min(
            self.capacity,
            self.tokens + (now - self._last) * self.refill_rate
        )
        self._last = now
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

# Test
bucket = TokenBucket(5, 1)
results = [bucket.allow() for _ in range(6)]
assert results == [True, True, True, True, True, False]

time.sleep(2)
assert bucket.allow() is True
assert bucket.allow() is True

Phân tích: Time O(1) mỗi lần gọi, Space O(1). Lưu ý: không thread-safe — production cần thêm Lock.

Bài 2: Per-User Rate Limiter — Intermediate ​

Đề bài: Mở rộng bài 1 thành PerUserRateLimiter. Mỗi user có bucket riêng. Trả về (allowed: bool, retry_after: float).

💡 Gợi ý
  • Dùng dict[str, TokenBucket] hoặc dict[str, tuple[float, float]]
  • Lazy create bucket khi user lần đầu gửi request
  • retry_after = (tokens_needed - current_tokens) / refill_rate
✅ Lời giải
python
import time
from threading import Lock

class PerUserRateLimiter:
    def __init__(self, capacity: float, refill_rate: float) -> None:
        self.capacity = capacity
        self.refill_rate = refill_rate
        self._buckets: dict[str, tuple[float, float]] = {}
        self._lock = Lock()

    def check(self, user_id: str) -> tuple[bool, float]:
        now = time.monotonic()
        with self._lock:
            tokens, last = self._buckets.get(
                user_id, (self.capacity, now)
            )
            tokens = min(
                self.capacity, tokens + (now - last) * self.refill_rate
            )
            if tokens >= 1:
                self._buckets[user_id] = (tokens - 1, now)
                return True, 0.0
            retry = (1 - tokens) / self.refill_rate
            self._buckets[user_id] = (tokens, now)
            return False, retry

Phân tích: Time O(1) amortized (HashMap lookup), Space O(U) với U = số user. Thread-safe nhờ Lock. Production cần thêm LRU eviction cho user không active để tránh memory leak.

Liên kết học tiếp ​

📚 Bài liên quan

Bài liên quan trong Penalgo

Từ khóa glossary: token bucket, leaky bucket, rate limiting, burst control, refill rate, capacity, lazy refill, monotonic clock, thundering herd

Tìm kiếm liên quan: giới hạn tốc độ API, nginx rate limit, cấu hình rate limiter, chống DDoS, throttling

Professional Engineering Standards | © 2025 HPN Corporation