Bài 33: Fixed Window — Đơn Giản & Nhược Điểm Burst

• Nắm cơ chế Fixed Window: chia thời gian thành cửa sổ cố định, đếm request, reset khi sang cửa sổ mới.
• Triển khai được Fixed Window với INCR + EXPIRE và phiên bản Lua atomic đảm bảo tính nguyên tử.
• Hiểu key design dùng window number trong key để tự reset mà không cần cron job hay cleanup.
• Viết được code Python hoàn chỉnh: is_allowed(), HTTP response headers, FastAPI middleware.
• Phân tích được nhược điểm burst boundary: tại sao 2x limit có thể lọt qua tại ranh giới hai cửa sổ.
• Biết Fixed Window phù hợp khi nào và khi nào nên chuyển sang Sliding Window.

Fixed Window chia trục thời gian thành các khoảng bằng nhau (window), mỗi khoảng có một counter riêng. Khi request đến, thuật toán:

1. Xác định cửa sổ hiện tại (dựa trên timestamp).
2. Tăng counter của cửa sổ đó lên 1.
3. Nếu counter vượt limit → deny request.
4. Khi sang cửa sổ mới, counter mới bắt đầu từ 0 (counter cũ tự expire).

Ví dụ với window 60 giây và limit 100 request/phút:

Cửa sổ 12:00:00 – 12:00:59  → counter_A, max 100
Cửa sổ 12:01:00 – 12:01:59  → counter_B, max 100
Cửa sổ 12:02:00 – 12:02:59  → counter_C, max 100

Request thứ 101 trong cùng một cửa sổ bị deny. Đúng 12:01:00, counter_B bắt đầu từ 0 và request lại được chấp nhận. Ranh giới cứng này vừa là điểm mạnh (đơn giản) vừa là điểm yếu (burst).

Cách đơn giản nhất dùng INCR để tăng counter và EXPIRE để đặt TTL:

# Pseudo-code — KHÔNG atomic, chỉ để minh hoạ luồng
key = f"rl:{user_id}:{current_minute}"   # key chứa identifier của window
count = redis.incr(key)                  # tăng counter, tạo key nếu chưa có (INCR trả về giá trị mới)
if count == 1:
    redis.expire(key, 60)                # chỉ set TTL khi key vừa được tạo
if count > limit:
    deny()                               # trả 429
else:
    allow()

Tại sao EXPIRE chỉ set khi count == 1? Nếu set mỗi lần thì TTL bị reset sau mỗi request, key sẽ không bao giờ hết hạn khi có traffic liên tục. Chỉ set một lần khi key được tạo để TTL chạy từ đầu window.

Vấn đề của đoạn code trên: INCR và EXPIRE là hai lệnh riêng biệt. Nếu process crash sau INCR nhưng trước EXPIRE, key sẽ tồn tại vĩnh viễn trong Redis và user bị block mãi mãi. Đây chính xác là vấn đề atomicity đã bàn trong bài 32 — giải pháp là Lua script.

Lua script chạy atomic trên Redis server — INCR và EXPIRE xảy ra trong cùng một lần thực thi, không có lệnh nào khác chen vào giữa:

-- KEYS[1]: tên key rate limit (vd "rl:user123:28057")
-- ARGV[1]: limit (vd "100")
-- ARGV[2]: window size tính bằng giây (vd "60")
local current = redis.call('INCR', KEYS[1])
if current == 1 then
    -- Key vừa được tạo, đặt TTL bằng window size
    redis.call('EXPIRE', KEYS[1], ARGV[2])
end
if current > tonumber(ARGV[1]) then
    return 0  -- deny
end
return 1      -- allow

Script trả về 1 nếu request được phép, 0 nếu bị deny. Điểm quan trọng: INCR luôn chạy trước khi check — counter tăng kể cả khi request cuối cùng bị deny. Đây là hành vi đúng: counter phản ánh số request đã cố gắng, không phải số request thành công.

Với redis-py, đăng ký script một lần khi khởi động application, tái sử dụng nhiều lần:

import redis

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

FIXED_WINDOW_LUA = """
local current = redis.call('INCR', KEYS[1])
if current == 1 then
    redis.call('EXPIRE', KEYS[1], ARGV[2])
end
if current > tonumber(ARGV[1]) then
    return 0
end
return 1
"""

# Đăng ký script — sha được cache phía server
fixed_window_script = r.register_script(FIXED_WINDOW_LUA)

Key cần chứa đủ thông tin để xác định window duy nhất. Pattern chuẩn:

import time

def fixed_window_key(user_id: str, window_seconds: int = 60) -> str:
    # Window number = unix timestamp chia nguyên cho window size
    # Mọi timestamp trong cùng cửa sổ đều cho cùng window number
    # Ví dụ window=60: ts=1748390400 → 1748390400//60 = 29139840
    #                   ts=1748390459 → 1748390459//60 = 29139840 (cùng window)
    #                   ts=1748390460 → 1748390460//60 = 29139841 (window mới)
    window = int(time.time()) // window_seconds
    return f"rl:{user_id}:{window}"

Cách này có một số đặc điểm quan trọng:

• Tự reset không cần cron: khi sang window mới, key mới được tạo từ đầu. Key cũ tự expire nhờ TTL = window_seconds.
• Không conflict giữa các user: key chứa user_id (hoặc IP, API key) nên mỗi user có counter độc lập.
• Không cần cleanup: TTL bằng window size đảm bảo key hết hạn ngay sau khi window kết thúc.
• Predictable: biết user_id và thời điểm, tính được đúng key đang được dùng — dễ debug.

Với window 1 giây (window_seconds=1), burst impact giảm nhỏ nhưng số key/giây tăng theo số user. Cân nhắc theo traffic thực tế.

import time
import redis

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

FIXED_WINDOW_LUA = """
local current = redis.call('INCR', KEYS[1])
if current == 1 then
    redis.call('EXPIRE', KEYS[1], ARGV[2])
end
if current > tonumber(ARGV[1]) then
    return 0
end
return 1
"""

_script = r.register_script(FIXED_WINDOW_LUA)


def fixed_window_key(user_id: str, window_seconds: int) -> str:
    window = int(time.time()) // window_seconds
    return f"rl:{user_id}:{window}"


def is_allowed(user_id: str, limit: int = 100, window: int = 60) -> bool:
    key = fixed_window_key(user_id, window)
    result = _script(keys=[key], args=[limit, window])
    return bool(result)


# --- Sử dụng ---
if is_allowed("user_123"):
    print("request allowed")
else:
    print("429 Too Many Requests")

Hàm is_allowed() trả True nếu request được phép, False nếu bị deny. Mọi lần gọi chỉ tốn 1 round-trip Redis (Lua script).

Đây là nhược điểm cốt lõi cần hiểu kỹ trước khi quyết định dùng Fixed Window cho bất kỳ use case nào.

Scenario

Limit: 100 request/phút.

• 12:00:30 → 12:00:59 (30 giây cuối của window 12:00): user gửi đúng 100 request. Tất cả được chấp nhận.
• 12:01:00 → 12:01:30 (30 giây đầu của window 12:01): window mới, counter về 0. User gửi tiếp 100 request. Tất cả được chấp nhận.
• Kết quả: 200 request trong vòng 60 giây (từ 12:00:30 đến 12:01:30).

Thuật toán không vi phạm gì — mỗi window vẫn chỉ có 100 request. Nhưng nhìn từ góc độ thực tế, hệ thống nhận 2x limit trong một khoảng 60 giây liên tiếp.

Minh hoạ timeline

          12:00:00                    12:01:00                    12:02:00
             |                            |                            |
Window 12:00 |....................XXXXXXXXXX|
Window 12:01 |                   |XXXXXXXXXX....................|
                                 ↑
                          Ranh giới window
             |←————— 30s ————————|←————— 30s ————————|
                    100 request         100 request
             |←——————————————— 60 giây ——————————————→|
                              200 request tổng cộng

X = request được chấp nhận
. = không có request

Tại sao đây là vấn đề thực tế

Một client có thể có tool tự động phát hiện thời điểm ranh giới window (bằng cách quan sát header X-RateLimit-Reset) và chủ động dồn request vào đó. Với limit 100/phút, chỉ cần 2 burst là client nhận được 200 request hợp lệ trong 60 giây — gấp đôi mức giới hạn khai báo.

Ở hệ thống có limit thấp (10 OTP/phút, 5 login attempt/phút) hay cost-critical (mỗi request gọi LLM API), 2x burst này không chấp nhận được.

RFC 6585 và thực tế production thường kèm các header để client biết trạng thái rate limit:

import time
from typing import Tuple

GET_COUNT_LUA = """
local val = redis.call('GET', KEYS[1])
if val == false then return 0 end
return tonumber(val)
"""
_get_count = r.register_script(GET_COUNT_LUA)


def rate_limit_headers(
    user_id: str, limit: int = 100, window: int = 60
) -> Tuple[int, dict]:
    """
    Trả về (http_status, headers).
    Gọi _script để tăng counter và check, sau đó tính remaining.
    """
    w = int(time.time()) // window
    key = f"rl:{user_id}:{w}"
    allowed = bool(_script(keys=[key], args=[limit, window]))

    # Đọc counter hiện tại để tính remaining
    # Lưu ý: current có thể > limit nếu bị deny
    current = int(_get_count(keys=[key]) or 0)
    remaining = max(0, limit - current)

    # reset_at = unix timestamp của đầu window kế tiếp
    reset_at = (w + 1) * window

    headers = {
        "X-RateLimit-Limit": str(limit),
        "X-RateLimit-Remaining": str(remaining),
        "X-RateLimit-Reset": str(reset_at),
    }
    if not allowed:
        headers["Retry-After"] = str(reset_at - int(time.time()))
        return 429, headers
    return 200, headers

Lưu ý: cần thêm 1 lần GET để đọc counter cho X-RateLimit-Remaining. Nếu muốn tối ưu, có thể gộp vào Lua script và trả về cả current lẫn allowed trong một lần gọi.

FastAPI middleware

from fastapi import FastAPI, Request
from fastapi.responses import JSONResponse

app = FastAPI()


def get_user_id(request: Request) -> str:
    # Trong production: lấy từ JWT, API key, hoặc IP fallback
    return request.headers.get("X-User-Id") or request.client.host


@app.middleware("http")
async def rate_limit_middleware(request: Request, call_next):
    user_id = get_user_id(request)
    status, headers = rate_limit_headers(user_id, limit=100, window=60)

    if status == 429:
        return JSONResponse(
            status_code=429,
            content={"error": "rate limit exceeded", "retry_after": headers.get("Retry-After")},
            headers=headers,
        )

    response = await call_next(request)
    # Gắn header vào response thành công
    for k, v in headers.items():
        response.headers[k] = v
    return response

Middleware áp dụng cho mọi endpoint. Trường hợp cần limit khác nhau theo endpoint (login stricter hơn profile), tách logic ra thành dependency injection hoặc decorator riêng.

Ưu điểm

• Memory cực thấp: mỗi user chỉ cần 1 key (1 integer counter) tại một thời điểm. Với 1 triệu user đang active, tổng memory ước khoảng 50-100 MB (key name + integer + TTL overhead).
• Tốc độ cao: 1 round-trip Lua script, không có thao tác list/sorted set phức tạp.
• Tự cleanup: TTL tự xóa key cũ, không cần cron job hay script cleanup riêng.
• Đơn giản, dễ debug: nhìn vào key trong Redis là biết ngay user đó đã gửi bao nhiêu request trong window hiện tại.

Giới hạn

• Burst boundary: 2x limit có thể lọt qua tại ranh giới hai cửa sổ liền kề (đã phân tích ở mục 7).
• Reset cứng: client biết chính xác khi nào counter reset (qua X-RateLimit-Reset) và có thể khai thác điều đó.
• Không phân tán tự nhiên: trong môi trường multi-node, nếu dùng nhiều Redis instance, cần Redis Cluster hoặc consistent hashing để đảm bảo cùng user luôn đến cùng shard — không thì counter bị tách.

Khi nào Fixed Window chấp nhận được

• Limit không strict — 2x burst thoáng qua không gây hại (vd general API, không phải anti-abuse).
• Window nhỏ (1-5 giây) — burst chỉ xảy ra ở ranh giới hẹp, impact nhỏ.
• Internal service-to-service call, không phải endpoint public.
• Yêu cầu đơn giản, ưu tiên dễ vận hành hơn là chính xác tuyệt đối.

Khi nào không nên dùng Fixed Window

• Anti-abuse strict: login, OTP, password reset — 2x burst là không thể chấp nhận.
• Cost-critical: mỗi request gọi external API tốn tiền.
• Bảo vệ endpoint yêu cầu chính xác tuyệt đối theo thời gian thực → Sliding Window (bài 34-35).

Anti-patterns

• GET rồi mới INCR:

  # SAI — race condition
  count = r.get(key)
  if int(count or 0) >= limit:
      deny()
  else:
      r.incr(key)  # hai request đồng thời có thể cùng vượt qua GET check

• INCR + EXPIRE non-atomic:

  # SAI — key stuck nếu crash giữa chừng
  r.incr(key)
  r.expire(key, 60)  # nếu dòng này không chạy, key không bao giờ hết hạn

• EXPIRE set mỗi request: TTL bị reset liên tục, key không bao giờ expire khi có traffic đều.
• Window quá lớn: window 1 giờ → burst impact lớn (2× 1 giờ = 2 giờ worth của request trong 1 khoảng thời gian). Window nhỏ hơn giảm impact.
• Không dùng Lua cho strict limit: nếu limit thực sự cần chính xác (login, OTP), INCR non-atomic không đủ.

Best practices

• Dùng Lua script atomic — luôn đảm bảo INCR và EXPIRE xảy ra cùng nhau.
• Đặt window number trong key — tự reset không cần cleanup.
• TTL = window size — key cũ tự biến mất sau 1 window.
• Kèm HTTP headers (X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset) để client xử lý đúng.
• Dùng Fixed Window khi yêu cầu đơn giản; chuyển sang Sliding Window khi cần chính xác về burst.

Fixed Window là điểm xuất phát tốt để hiểu rate limiting: cơ chế rõ ràng, code ngắn, hiệu quả bộ nhớ cao. Nhược điểm burst boundary — cho phép 2x limit tại ranh giới — là lý do cần hiểu kỹ trước khi áp dụng cho endpoint nhạy cảm.

Chuỗi quyết định ngắn gọn:

• Burst 2x chấp nhận được → Fixed Window.
• Cần chính xác, không burst → Sliding Window (bài 34-35).

Quiz

1. Tại sao EXPIRE chỉ cần set khi INCR trả về 1 (tức là key vừa được tạo), không phải mỗi lần request?
2. Với limit 50 request/phút, mô tả chính xác một scenario mà Fixed Window để lọt 100 request trong 60 giây liên tiếp.
3. Nếu window size là 1 giây thay vì 60 giây, burst boundary problem có biến mất không? Giải thích tại sao có/không.
4. Trong đoạn Lua script, tại sao counter vẫn tăng ngay cả khi request bị deny (counter > limit)?
5. Kể 2 use case mà Fixed Window phù hợp và 2 use case mà không nên dùng.

Đáp án gợi ý

1. Nếu set EXPIRE mỗi request, TTL liên tục bị reset. Key sẽ không bao giờ hết hạn khi traffic đều đặn, counter tích lũy mãi mãi. Chỉ set một lần khi key mới tạo (count == 1) thì TTL chạy từ đầu window, key hết hạn đúng lúc window kết thúc.
2. User gửi 50 request trong 30 giây cuối của window A (counter_A = 50, chưa vượt limit). Đúng khi sang window B, counter_B = 0. User gửi tiếp 50 request trong 30 giây đầu window B. Tổng: 100 request trong 60 giây, nhưng mỗi window chỉ thấy 50 — đều hợp lệ.
3. Burst boundary không biến mất, chỉ nhỏ hơn về impact. Với window 1 giây, burst tối đa là 2× limit/giây thay vì 2× limit/phút. Ranh giới vẫn tồn tại mỗi giây, nhưng khoảng thời gian burst chỉ là ~1-2 giây thay vì ~1-2 phút, ít nguy hiểm hơn với hầu hết use case.
4. Counter phải phản ánh số request đã cố gắng (attempted), không phải số được phép. Nếu counter không tăng khi deny, một user gửi request liên tục sau khi vượt limit sẽ luôn thấy counter không thay đổi và không có dấu hiệu "bị block". Hơn nữa, nếu counter reset bởi TTL rồi user gửi request mới, count mới bắt đầu từ đúng số thực tế.
5. Phù hợp: (a) general API endpoint không nhạy cảm, burst 2x không gây hại; (b) internal service-to-service call với window nhỏ. Không nên dùng: (a) login/OTP/password reset — burst có thể bị khai thác; (b) endpoint gọi external service tính phí theo request.

Bài tiếp theo

Bài 34 giải quyết burst boundary bằng Sliding Window Log: lưu timestamp của từng request, kiểm tra chính xác trong N giây trước. Chính xác hơn Fixed Window nhưng tốn memory nhiều hơn — bài 34 phân tích trade-off đó.

Tham khảo

• Redis Docs — Lệnh INCR
• Redis Docs — Lệnh EXPIRE
• Redis Docs — Lua scripting API
• Redis Blog — Rate Limiting with Redis (Part 1)
• RFC 6585 — Additional HTTP Status Codes (429 Too Many Requests)
• FastAPI Docs — Middleware