Bài 36: Token Bucket — Pattern API Phổ Biến

• Hiểu cơ chế Token Bucket: capacity, refill rate, lazy refill.
• Viết được Lua script atomic cho Token Bucket trên Redis.
• Triển khai variable cost (request nặng tốn nhiều token).
• So sánh được Token Bucket với Sliding Window Counter (bài 35) — khi nào dùng cái nào.
• Nhận biết các anti-pattern phổ biến và cách tránh.

Hình dung một cái xô (bucket) chứa token. Xô có sức chứa tối đa N token. Token được bỏ vào đều đặn với tốc độ R token mỗi giây, nhưng không vượt quá N.

Mỗi request đến lấy ra 1 token (hoặc nhiều hơn nếu request "nặng"). Nếu xô còn đủ token → cho phép. Nếu không đủ → từ chối.

• Capacity (N): sức chứa tối đa của bucket, đồng thời là kích thước burst tối đa.
• Refill rate (R): token/giây nạp vào bucket — cũng chính là sustained rate tối đa cho phép.
• Cho phép burst: nếu user idle lâu, bucket tích đầy token; user có thể gửi N request liên tiếp ngay.
• Throttle sau burst: sau khi dùng hết bucket, rate bị giới hạn về R request/giây.

Đây là điểm khác biệt cốt lõi với window-based (bài 33–35): window-based đếm request trong khoảng thời gian cố định; Token Bucket kiểm soát tốc độ và cho phép burst ngắn.

Token Bucket được định nghĩa hoàn toàn bởi 2 con số:

Ví dụ: capacity=100, refill_rate=10/s:

• User có thể burst 100 request ngay lập tức (nếu bucket đang đầy).
• Sau khi dùng hết, sustained rate = 10 request/giây.
• Mỗi 10 giây idle → bucket đầy trở lại (100 ÷ 10 = 10 giây).

Quy tắc ngón tay cái: capacity nên lớn hơn refill_rate để có burst headroom thực sự. Nếu capacity == refill_rate (ví dụ cả hai là 10), bucket không bao giờ tích được hơn 1 giây worth of token → không có burst → hành vi gần giống Leaky Bucket (bài 37).

Một câu hỏi tự nhiên: ai nạp token vào bucket? Nếu dùng cron job chạy mỗi giây để INCR mọi key → không scale được khi có hàng triệu user.

Lazy refill giải quyết vấn đề này: không nạp liên tục, chỉ tính khi có request đến.

Công thức:

tokens = min(capacity, last_tokens + elapsed × rate)

Trong đó elapsed = now - last_refill là thời gian tính bằng giây kể từ lần tính cuối.

Redis key chỉ lưu 2 field:

• tokens: số token còn lại (float, có thể là 5.3 nếu refill chưa đầy 1 token).
• last: timestamp (giây, float) của lần tính token cuối.

Không có background job, không có INCR định kỳ. Bucket "refill" ảo — chỉ khi request đến mới tính số token mới dựa trên thời gian trôi qua.

Giống các bài trước trong nhóm này (bài 32–35), logic kiểm tra + cập nhật phải là atomic. Nếu không, 2 request đến cùng lúc có thể cùng đọc được tokens = 1, cùng pass, rồi cùng ghi tokens = 0 — dẫn đến allow nhầm.

Lua script dưới đây nhận time qua ARGV (không dùng redis.call('TIME') trong Lua vì lệnh không xác định — vi phạm replication):

-- KEYS[1] = bucket key (vd "tb:user:42")
-- ARGV[1] = capacity (N)
-- ARGV[2] = refill_rate (token/giây)
-- ARGV[3] = now (epoch giây, float)
-- ARGV[4] = requested (số token cần lấy, thường 1)

local capacity  = tonumber(ARGV[1])
local rate      = tonumber(ARGV[2])
local now       = tonumber(ARGV[3])
local requested = tonumber(ARGV[4])

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

-- Bucket mới: khởi tạo đầy
if tokens == nil then
    tokens = capacity
    last   = now
end

-- Lazy refill: tính token tích lũy kể từ lần tính cuối
local elapsed = math.max(0, now - last)
tokens = math.min(capacity, tokens + elapsed * rate)

-- Kiểm tra và tiêu thụ token
local allowed = 0
if tokens >= requested then
    tokens  = tokens - requested
    allowed = 1
end

-- Ghi lại state
redis.call('HMSET', KEYS[1], 'tokens', tokens, 'last', now)

-- TTL: thời gian để bucket refill đầy từ 0 token + 1 giây buffer
redis.call('EXPIRE', KEYS[1], math.ceil(capacity / rate) + 1)

return { allowed, tokens }

Script trả về { allowed, tokens }: allowed = 1 nếu cho phép, tokens là số token còn lại sau request — dùng cho response header.

Lưu ý: tokens là float. Sau elapsed = 0.3s với rate = 10, bucket nhận thêm 3 token. Điều này cho phép phân giải thời gian mịn hơn so với chỉ nạp integer.

import time
import redis

r = redis.Redis(host='localhost', port=6379, decode_responses=True)

TOKEN_BUCKET_LUA = """
local capacity  = tonumber(ARGV[1])
local rate      = tonumber(ARGV[2])
local now       = tonumber(ARGV[3])
local requested = tonumber(ARGV[4])

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

if tokens == nil then
    tokens = capacity
    last   = now
end

local elapsed = math.max(0, now - last)
tokens = math.min(capacity, tokens + elapsed * rate)

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

redis.call('HMSET', KEYS[1], 'tokens', tokens, 'last', now)
redis.call('EXPIRE', KEYS[1], math.ceil(capacity / rate) + 1)

return { allowed, tokens }
"""

_bucket_script = r.register_script(TOKEN_BUCKET_LUA)


def check_token_bucket(
    user_id: str,
    capacity: int = 100,
    rate: float = 10.0,
    requested: int = 1,
) -> tuple[bool, float]:
    """
    Trả về (allowed, tokens_remaining).
    allowed=True nếu request được phép.
    tokens_remaining là số token còn lại sau request.
    """
    now = time.time()
    key = f"tb:{user_id}"
    result = _bucket_script(keys=[key], args=[capacity, rate, now, requested])
    allowed = bool(result[0])
    tokens_remaining = float(result[1])
    return allowed, tokens_remaining


# --- Ví dụ sử dụng trong FastAPI / Flask middleware ---
def rate_limit_middleware(user_id: str, endpoint_cost: int = 1):
    allowed, remaining = check_token_bucket(
        user_id=user_id,
        capacity=100,
        rate=10.0,
        requested=endpoint_cost,
    )
    if not allowed:
        # Tính thời gian phải chờ để có đủ endpoint_cost token
        wait_seconds = endpoint_cost / 10.0
        raise RateLimitError(retry_after=int(wait_seconds) + 1)
    return remaining

register_script lưu SHA của script; lần gọi sau dùng EVALSHA thay vì gửi lại toàn bộ script — tiết kiệm bandwidth.

Cấu hình: capacity=10, rate=1 token/giây.

Nhận xét: 10 request đầu được pass ngay (burst). Sau đó hệ thống chỉ cho phép 1 request/giây (sustained rate = rate). User idle 9 giây sau đó lại có thể burst 9 request.

Token Bucket tự nhiên hỗ trợ "request nặng tốn nhiều token" — chỉ cần thay đổi requested:

# Endpoint rẻ: 1 token
allowed, _ = check_token_bucket(user_id, requested=1)

# Endpoint đắt (export, bulk operation): 5 token
allowed, _ = check_token_bucket(user_id, requested=5)

# LLM inference: cost tỷ lệ với số token output
output_tokens = 500  # từ response của model
allowed, _ = check_token_bucket(user_id, requested=output_tokens)

Ví dụ thực tế:

• AWS API Gateway: burst limit và rate limit riêng biệt cho từng method — GET thường rẻ hơn POST nặng.
• LLM API: rate limit theo token (input + output) chứ không phải theo số request.
• Bulk export: export 1000 record tốn nhiều tài nguyên hơn query 1 record → set cost cao hơn để giữ fair use.

Với window-based, variable cost phải được implement bằng cách nhân INCR (phức tạp hơn). Token Bucket xử lý nó tự nhiên.

Mỗi lần Lua script chạy, nó set EXPIRE cho bucket key:

redis.call('EXPIRE', KEYS[1], math.ceil(capacity / rate) + 1)

Công thức này tính thời gian tối đa để bucket refill từ 0 đến đầy: capacity / rate giây. Cộng thêm 1 giây buffer.

Ví dụ: capacity=100, rate=10 → EXPIRE = ceil(100/10) + 1 = 11s.

Nếu user ngừng gửi request:

• Không có request nào đến → Lua không chạy → EXPIRE không được reset.
• Sau 11 giây, key tự xóa.
• Request tiếp theo sẽ tạo bucket mới, khởi tạo đầy token.

Đây là cơ chế cleanup tự nhiên — không cần scan key hay job dọn dẹp. Redis memory tự giải phóng khi user inactive.

Client cần biết trạng thái rate limit để xử lý retry đúng cách. Các header phổ biến:

def build_rate_limit_headers(
    capacity: int,
    tokens_remaining: float,
    requested: int,
    rate: float,
    allowed: bool,
) -> dict:
    headers = {
        "X-RateLimit-Limit": str(capacity),
        "X-RateLimit-Remaining": str(int(tokens_remaining)),
    }
    if not allowed:
        # Thời gian chờ để có đủ token cho request hiện tại
        wait_seconds = math.ceil(requested / rate)
        headers["Retry-After"] = str(wait_seconds)
    return headers

Lưu ý:

• X-RateLimit-Remaining là số token còn lại — khác với window-based (số request còn lại trong window). Client cần hiểu ngữ nghĩa này.
• Retry-After ước tính dựa trên requested / rate — là thời gian tối thiểu để có đủ token. Thực tế có thể sớm hơn nếu user có token tích lũy từ trước.
• Không cần X-RateLimit-Reset (timestamp reset window) vì Token Bucket không có window — refill liên tục.

Cả hai đều dùng Lua atomic và có thể scale theo chiều ngang. Lựa chọn phụ thuộc vào yêu cầu burst tolerance, không phải khả năng kỹ thuật.

Nên dùng Token Bucket

• API public cho phép burst ngắn — user click nhanh vẫn OK, nhưng sustained rate bị giới hạn.
• Request có cost khác nhau (lightweight vs heavy endpoint).
• LLM API hoặc bất kỳ service nào rate limit theo "đơn vị công việc" chứ không phải số request.
• Đây là lựa chọn mặc định cho hầu hết public API rate limiting.

Cân nhắc thay thế

• Cần smooth tuyệt đối, không burst: Leaky Bucket (bài 37) — mỗi request được xử lý đều đặn, không có burst.
• Cần đếm chính xác request trong window: Sliding Window Log (bài 34) — không xấp xỉ, chính xác tuyệt đối.
• Rate limit gắn với billing: Sliding Window (Log hoặc Counter) rõ ràng hơn về ngữ nghĩa "X request trong Y phút".

Anti-patterns

• Non-atomic: HMGET + tính + HMSET riêng: race condition kinh điển. Hai request đến đồng thời cùng đọc tokens = 1, cùng pass, cùng ghi tokens = 0 → allow 2 request thay vì 1.

  # SAI — không atomic
  data = r.hmget(key, 'tokens', 'last')   # đọc
  tokens = compute_tokens(data, now)       # tính
  if tokens >= 1:
      r.hmset(key, {'tokens': tokens - 1, 'last': now})  # ghi (race ở đây)

• Dùng redis.call('TIME') trong Lua: lệnh TIME là non-deterministic — Redis replica có thể thực thi Lua với TIME khác nhau → replication không nhất quán. Luôn truyền now qua ARGV từ application.
• Capacity = refill rate: ví dụ capacity=10, rate=10/s — bucket chỉ tích được 1 giây worth of token. Nếu user idle 0.5s thì chỉ có 5 token. Không có burst headroom thực sự, hành vi gần giống Leaky Bucket.
• Quên EXPIRE: nếu Lua script không set EXPIRE, key tồn tại mãi mãi. Với hàng triệu user, memory Redis tăng không ngừng.
• Float precision trong comparison: do tokens là float, tránh so sánh tokens == 0; dùng tokens < requested. Trường hợp tokens = 0.9999... do rounding vẫn không đủ cho requested = 1.

Best practices

• Luôn dùng Lua script để đảm bảo atomic — không pipeline thủ công HMGET + HMSET.
• Truyền now qua ARGV, không gọi TIME trong Lua.
• Set capacity > rate để có burst headroom rõ ràng.
• Set EXPIRE = ceil(capacity/rate) + 1 để cleanup tự động.
• Trả tokens_remaining trong response header để client biết trạng thái.
• Dùng variable cost cho endpoint nặng thay vì rate limit riêng cho từng endpoint.

Tổng kết

• Token Bucket kiểm soát rate bằng mô hình capacity + refill rate, không phải đếm theo window.
• Lazy refill tính token khi request đến: tokens = min(capacity, last_tokens + elapsed × rate).
• Redis lưu 2 field: tokens (float) và last (timestamp). Lua script đảm bảo atomic.
• Variable cost (requested > 1) cho request nặng là tính năng tự nhiên của model này.
• EXPIRE tự động cleanup key khi user inactive.

Quiz 4 câu

1. User có bucket capacity=20, rate=2/s. Lúc T=0 bucket có 5 token. T=3s user gửi 1 request. Tính số token còn lại sau request và cho biết kết quả ALLOW hay DENY.
2. Tại sao không nên gọi redis.call('TIME') trong Lua script của Token Bucket? Thay vào đó truyền time như thế nào?
3. Khác biệt nào khiến Token Bucket phù hợp hơn Sliding Window Counter cho LLM API rate limiting?
4. Cấu hình capacity=5, rate=5/s. Mô tả burst behavior và giải thích tại sao đây là cấu hình không lý tưởng.

Đáp án gợi ý

1. elapsed = 3s. tokens = min(20, 5 + 3×2) = min(20, 11) = 11. Sau request: 11 - 1 = 10. Kết quả: ALLOW, còn 10 token.
2. redis.call('TIME') trả về system time của Redis instance tại thời điểm thực thi Lua. Trên Redis replica, lệnh này bị coi là non-deterministic — replica có thể thực thi với time khác → replication log không đồng nhất → có thể gây inconsistency. Giải pháp: lấy time.time() ở application, truyền vào qua ARGV[3].
3. LLM API rate limit theo số token output (đơn vị biến đổi mỗi request), không phải số request. Token Bucket hỗ trợ requested = output_tokens tự nhiên — 1 request ngắn tốn ít token, 1 request dài tốn nhiều. Sliding Window Counter phải INCRBY với cost mỗi request, phức tạp hơn và ngữ nghĩa kém tự nhiên.
4. Với capacity=5, rate=5/s: bucket refill 5 token trong 1 giây — thời gian refill đầy là 1 giây. User chỉ có thể burst 5 request, sau đó phải đợi refill. Nếu user idle 0.2s thì chỉ có 1 token. Không có headroom tích lũy — user idle 1 ngày cũng chỉ có 5 token. Đây là cấu hình không lý tưởng vì capacity bằng rate, hành vi gần giống Leaky Bucket nhưng thiếu tính năng smoothing thực sự. Nếu muốn 5 req/s sustained: set capacity=50 (burst 10s), rate=5/s.

Bài tiếp theo

Bài 37 giới thiệu Leaky Bucket và GCRA — thuật toán làm mượt traffic tuyệt đối, không burst, phù hợp với bài toán smoothing thay vì tolerance.

Tham khảo

• Redis Docs — Lua scripting API
• Redis Docs — Lệnh HMGET
• Redis Docs — Lệnh HMSET
• Redis Docs — Lệnh EXPIRE
• AWS API Gateway — Request Throttling (Token Bucket)
• Stripe Engineering Blog — Scaling your API with rate limiters (2017)
• redis-py Documentation