Bài 35: Sliding Window Counter — Cân Bằng Accuracy & Memory

Hai bài trước đã trình bày hai thái cực:

• Fixed Window (bài 33): chỉ cần 1 counter/user. Memory tối thiểu. Nhưng mỗi boundary window là điểm yếu — client có thể gửi 2× limit bằng cách gửi đúng cuối window cũ và đầu window mới.
• Sliding Log (bài 34): lưu timestamp từng request vào sorted set. Chính xác tuyệt đối. Nhưng mỗi user tiêu tốn bộ nhớ tỷ lệ với số request trong window — 1M user × 100 request/phút ≈ 7 GB RAM.

Sliding Window Counter là thuật toán trung gian: chỉ cần 2 counter/user (memory gần Fixed Window) nhưng xấp xỉ cửa sổ trượt tốt hơn đáng kể so với Fixed Window.

Thay vì lưu timestamp từng request, thuật toán chỉ giữ 2 giá trị:

• current_count: số request trong fixed window hiện tại.
• previous_count: số request trong fixed window vừa qua.

Khi cần kiểm tra, thuật toán ước lượng số request thực sự nằm trong cửa sổ trượt 60 giây gần nhất:

• Toàn bộ current_count chắc chắn nằm trong cửa sổ (vì vẫn thuộc window hiện tại).
• Một phần previous_count nằm trong cửa sổ — phần bao nhiêu phụ thuộc vào đã trôi qua bao nhiêu giây trong window hiện tại.

Giả định request phân bố đều trong previous window (xem phần Accuracy Analysis về khi nào giả định này không đúng).

Công thức

estimated = current_count + previous_count × ((window - elapsed_in_current) / window)

• elapsed_in_current: số giây đã trôi trong window hiện tại (= now % window).
• (window - elapsed) / window: tỷ lệ previous window còn nằm trong cửa sổ trượt.

Ví dụ cụ thể

Cấu hình: limit 100 request/phút, window = 60 giây.

Thời điểm kiểm tra: 12:01:15 → elapsed = 15 giây trong window 12:01.

• Window 12:01 (hiện tại): 30 request.
• Window 12:00 (trước): 80 request.

Cửa sổ trượt 60 giây bao gồm đoạn [12:00:15, 12:01:15]. Phần window 12:00 nằm trong đó là từ 12:00:15 đến 12:01:00 — tức 75% window 12:00.

weight    = (60 - 15) / 60 = 0.75
estimated = 30 + 80 × 0.75 = 30 + 60 = 90

90 < 100 → ALLOW

Nếu current_count = 50 thì estimated = 50 + 60 = 110 > 100 → DENY.

Đọc 2 counter và increment phải là một thao tác atomic (bài 32 đã giải thích lý do). Lua script trong Redis đảm bảo điều này.

-- KEYS[1] = current window key  (vd "rl:user123:26710")
-- KEYS[2] = previous window key (vd "rl:user123:26709")
-- ARGV[1] = limit
-- ARGV[2] = window_sec
-- ARGV[3] = elapsed_in_current_sec (số giây đã trôi trong window hiện tại)

local current  = tonumber(redis.call('GET', KEYS[1]) or '0')
local previous = tonumber(redis.call('GET', KEYS[2]) or '0')
local window   = tonumber(ARGV[2])
local elapsed  = tonumber(ARGV[3])

local weight    = (window - elapsed) / window
local estimated = current + previous * weight

if estimated >= tonumber(ARGV[1]) then
    return 0  -- denied
end

-- Tăng counter window hiện tại
redis.call('INCR', KEYS[1])
-- TTL = window * 2 để previous window vẫn còn sống khi cần đọc
redis.call('EXPIRE', KEYS[1], window * 2)
return 1  -- allowed

Một số điểm quan trọng:

• or '0' xử lý trường hợp key chưa tồn tại — GET trả nil, Lua chuyển thành '0'.
• EXPIRE window * 2 đảm bảo key KEYS[1] sẽ trở thành previous window trong vòng window giây tới và vẫn cần sống thêm window giây nữa.
• Không cần đặt EXPIRE cho KEYS[2] — đã được đặt khi nó còn là current window.

import time
import redis

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

LUA_SCRIPT = """
local current  = tonumber(redis.call('GET', KEYS[1]) or '0')
local previous = tonumber(redis.call('GET', KEYS[2]) or '0')
local window   = tonumber(ARGV[2])
local elapsed  = tonumber(ARGV[3])

local weight    = (window - elapsed) / window
local estimated = current + previous * weight

if estimated >= tonumber(ARGV[1]) then
    return 0
end

redis.call('INCR', KEYS[1])
redis.call('EXPIRE', KEYS[1], window * 2)
return 1
"""

_limiter = r.register_script(LUA_SCRIPT)

def is_allowed(user_id: str, limit: int = 100, window: int = 60) -> bool:
    now = time.time()
    current_window  = int(now // window)       # vd 26710 (số phút kể từ epoch)
    previous_window = current_window - 1
    elapsed = now % window                     # giây đã trôi trong window hiện tại

    current_key  = f"rl:{user_id}:{current_window}"
    previous_key = f"rl:{user_id}:{previous_window}"

    result = _limiter(
        keys=[current_key, previous_key],
        args=[limit, window, elapsed],
    )
    return bool(result)


# Ví dụ sử dụng
if is_allowed("user123"):
    print("Request allowed")
else:
    print("Rate limit exceeded")

Key design: rl:{user_id}:{window_number} — window number tăng tự nhiên theo thời gian, không cần logic rotate thủ công. Window 60 giây → window number = int(now // 60).

Trả về thông tin rate limit qua response headers để client có thể điều chỉnh tốc độ gửi request.

def get_rate_limit_headers(
    user_id: str,
    limit: int = 100,
    window: int = 60
) -> dict[str, str]:
    now = time.time()
    current_window  = int(now // window)
    previous_window = current_window - 1
    elapsed = now % window

    current_key  = f"rl:{user_id}:{current_window}"
    previous_key = f"rl:{user_id}:{previous_window}"

    current  = int(r.get(current_key) or 0)
    previous = int(r.get(previous_key) or 0)

    weight    = (window - elapsed) / window
    estimated = current + previous * weight

    remaining = max(0, limit - int(estimated))
    reset_at  = int((current_window + 1) * window)  # epoch seconds khi window kế tiếp bắt đầu

    return {
        "X-RateLimit-Limit":     str(limit),
        "X-RateLimit-Remaining": str(remaining),
        "X-RateLimit-Reset":     str(reset_at),
    }

X-RateLimit-Reset ở đây là thời điểm đầu window kế tiếp. Một số API dùng "giây còn lại" thay vì Unix timestamp — tuỳ theo convention của service.

Giả định nền tảng

Thuật toán giả định request phân bố đều trong previous window. Khi giả định này đúng, sai số gần như bằng 0.

Khi nào sai số tăng

Giả sử previous window có 80 request nhưng tất cả đều dồn vào giây đầu tiên (burst cực đoan). Thuật toán vẫn tính weighted 75% × 80 = 60 — trong khi thực tế tại thời điểm 12:01:15, cả 80 request đó đã nằm ngoài cửa sổ trượt (vì xảy ra ở khoảng 12:00:00–12:00:01, tức hơn 60 giây trước). Thuật toán overestimate → deny nhầm.

Ngược lại, nếu 80 request dồn vào cuối window 12:00 (12:00:58–12:01:00) thì thuật toán tính 75% × 80 = 60, nhưng thực tế gần như cả 80 đều nằm trong cửa sổ trượt. Thuật toán underestimate → allow nhầm.

Số liệu thực tế

Cloudflare công bố (blog.cloudflare.com, 2015): khi áp dụng thuật toán này trên traffic thực, tỷ lệ request bị phán quyết sai (allow nhầm hoặc deny nhầm) là 0.003%. Với hầu hết use case rate limiting cho API, mức sai số này là chấp nhận được.

Ảnh hưởng của kích thước window

Window càng dài, traffic càng ít đồng đều trong window → sai số tiềm năng tăng. Window 1 giây và window 1 ngày đều dùng được về mặt kỹ thuật, nhưng window 1 ngày với traffic lúc cao điểm sáng và thấp điểm đêm sẽ có sai số lớn hơn window 1 phút.

Tiêu chí	Fixed Window	Sliding Log	Sliding Counter
Memory / user	1 counter	N entry (1 per request)	2 counter
Accuracy	Thấp — burst 2× tại boundary	Tuyệt đối	~99.99% (0.003% sai)
Burst tại boundary	Có	Không	Gần như không
Độ phức tạp code	Đơn giản	Trung bình	Trung bình
1M user, limit 100/phút	~50 MB	~7 GB	~100 MB
Production use	Internal / low-stakes	Billing, strict + limit nhỏ	Default phổ biến nhất

Memory estimate: mỗi counter Redis (STRING) ≈ 50 bytes overhead. 1M user × 1 counter × 50 bytes ≈ 50 MB cho Fixed; 2 counter ≈ 100 MB cho Sliding Counter; sorted set với 100 member ≈ 7 KB/user → 7 GB cho Sliding Log.

Nên dùng Sliding Window Counter

• Production API rate limiting với số lượng user lớn — đây là lựa chọn mặc định.
• Cần accuracy tốt hơn Fixed Window nhưng không chấp nhận memory của Sliding Log.
• Traffic tương đối đều trong window (API thông thường, không phải batch job khuya).

Không đủ — cân nhắc Sliding Log

• Cần chính xác tuyệt đối, không chấp nhận sai số — ví dụ rate limit gắn với billing (vượt giới hạn thì tính tiền thêm).
• Limit rất nhỏ (vd 5 request/phút) — ngay cả 0.003% sai số cũng không chấp nhận được.
• Traffic có pattern burst cực đoan và lệch hẳn về một đầu window.

Xem xét Fixed Window khi

• Giới hạn chỉ mang tính tham chiếu nội bộ, burst 2× không ảnh hưởng production.
• Cần implementation đơn giản nhất, memory tối thiểu tuyệt đối.

Anti-patterns

• Non-atomic GET + GET + INCR riêng: race condition giữa đọc và ghi. Hai request đến cùng lúc có thể cùng đọc estimated = 99, cùng pass, và cùng INCR lên 101.

  # SAI — non-atomic
  current  = int(r.get(current_key) or 0)
  previous = int(r.get(previous_key) or 0)
  estimated = current + previous * weight
  if estimated < limit:
      r.incr(current_key)  # race condition xảy ra ở đây

• Quên EXPIRE window×2: nếu EXPIRE = window (thay vì window×2), key hiện tại sẽ expire trước khi nó được dùng làm previous window → thuật toán luôn đọc previous = 0 → underestimate → allow nhầm.
• Dùng cho billing hoặc strict enforcement: 0.003% sai số nhỏ nhưng không phải 0. Nếu rate limit gắn với hệ quả tài chính, dùng Sliding Log.
• Window quá dài với traffic không đều: window 1 ngày với traffic có peak sáng và valley đêm → giả định uniform phân bố không đúng → sai số lớn hơn nhiều so với con số 0.003%.

Best practices

• Dùng Lua script để đảm bảo atomic — không pipeline thủ công.
• Đặt EXPIRE = window × 2 cho current window key.
• Key format: rl:{identifier}:{window_number} — tự nhiên rotate theo thời gian.
• Monitor false allow/deny rate trong production bằng cách log khi estimated gần limit (vd 90–110%).
• Nếu cần nhiều tier limit (10/giây, 1000/giờ), chạy riêng từng Lua call với window tương ứng.

Tổng kết module window-based

• Fixed Window (bài 33): 1 counter/user, đơn giản, chấp nhận burst 2× tại boundary.
• Sliding Log (bài 34): N entry/user, chính xác tuyệt đối, memory tỷ lệ với traffic.
• Sliding Counter (bài 35): 2 counter/user, sai số ~0.003%, production default.

Bài 36 và 37 chuyển sang góc nhìn khác — Token Bucket và Leaky Bucket không đếm theo window mà kiểm soát rate (request/giây) liên tục, phù hợp với các bài toán smoothing traffic thay vì hard limit.

Quiz 4 câu

1. Lúc 12:05:45, window 60 giây. Current window (12:05) có 40 request, previous window (12:04) có 70 request. Limit = 100. Tính estimated và cho biết request tiếp theo ALLOW hay DENY?
2. Giải thích tại sao EXPIRE phải là window × 2 chứ không phải window.
3. Mô tả một kịch bản cụ thể khiến Sliding Window Counter underestimate số request thực trong cửa sổ trượt (tức allow nhầm).
4. Vì sao không nên dùng Sliding Window Counter cho rate limit gắn với billing?

Đáp án gợi ý

1. elapsed = 45s. weight = (60 - 45) / 60 = 0.25. estimated = 40 + 70 × 0.25 = 40 + 17.5 = 57.5 < 100 → ALLOW.
2. Khi window hiện tại kết thúc, nó trở thành previous window và cần sống thêm 1 window nữa để các request ở đầu window kế tiếp vẫn đọc được. EXPIRE = window: key expire đúng lúc hết làm current, mất trước khi làm previous xong. EXPIRE = window×2: sống đủ để làm cả current lẫn previous.
3. Previous window có 100 request nhưng tất cả xảy ra ở 5 giây cuối (vd 12:04:55–12:04:60). Cửa sổ trượt bao gồm đoạn [12:04:45, 12:05:45] — thực tế gần như toàn bộ 100 request nằm trong cửa sổ. Nhưng thuật toán tính weight = (60-45)/60 = 0.25, chỉ lấy 25 request → underestimate → allow nhầm.
4. Sai số 0.003% nhỏ nhưng không bằng 0. Trong billing, allow nhầm = doanh thu bị mất hoặc tranh chấp với khách hàng; deny nhầm = trải nghiệm xấu có thể dẫn đến refund request. Các bài toán tài chính yêu cầu chính xác tuyệt đối → Sliding Log.

Bài tiếp theo

Bài 36 giới thiệu Token Bucket — thuật toán kiểm soát rate theo phép ẩn dụ "bình chứa token" thay vì đếm theo window. Phù hợp với bài toán cho phép burst có kiểm soát và smoothing traffic liên tục.

Tham khảo

• Redis Docs — Lệnh INCR
• Redis Docs — Lệnh EXPIRE
• Redis Docs — Lua scripting API
• Cloudflare Blog — Sliding Window Rate Limiting (2015)
• redis-py Documentation