Bài 34: Sliding Window Log — Chính Xác, Tốn Memory

• Giải thích được tại sao Fixed Window cho phép burst gấp đôi limit và Sliding Window Log loại bỏ điểm yếu đó như thế nào.
• Hiểu cơ chế hoạt động của Sliding Window Log: Sorted Set lưu timestamp từng request, cửa sổ trượt liên tục theo thời gian thực.
• Biết tại sao phải dùng Lua script để đảm bảo tính atomic khi kết hợp ZREMRANGEBYSCORE + ZCARD + ZADD.
• Viết được Lua script rate limiter hoàn chỉnh và gọi nó từ Python bằng register_script.
• Giải thích được tại sao member của ZSet phải unique và cách xử lý trường hợp timestamp trùng millisecond.
• Tính được memory footprint cụ thể và so sánh với Fixed Window để quyết định pattern phù hợp.
• Nhận diện các anti-pattern: member không unique, quên EXPIRE, không atomic, limit lớn với traffic cao.

Fixed Window chia thời gian thành các ô cứng (00:00–00:59, 01:00–01:59, …). Mỗi ô có counter riêng, reset về 0 khi sang ô mới. Với limit 100 req/phút:

• User gửi 100 request vào 00:59 → hợp lệ, counter = 100.
• Đồng hồ chuyển sang 01:00 → counter reset về 0.
• User gửi tiếp 100 request vào 01:00 → hợp lệ, counter = 100.
• Trong khoảng [00:59, 01:00] (2 giây), user đã gửi tổng cộng 200 request — gấp đôi limit.

Đây là burst boundary problem. Server nhận 200 request trong 2 giây nhưng rate limiter không chặn vì mỗi window riêng biệt đều hợp lệ. Với các hệ thống thông thường, chấp nhận sai số này là hợp lý vì đổi lại implementation đơn giản và memory thấp. Nhưng với các trường hợp cần chính xác tuyệt đối — billing API, compliance quota, kiểm soát tốc độ gửi email — sai số 2x là không chấp nhận được.

Thay vì chia thời gian thành ô cứng, Sliding Window Log ghi lại timestamp của từng request. Khi cần kiểm tra request mới, thuật toán hỏi: "trong 60 giây vừa qua tính từ ngay bây giờ, có bao nhiêu request đã được chấp nhận?"

Cửa sổ không cố định ở [00:00, 00:59]. Nó luôn là [now - 60s, now] — trượt cùng với thời gian thực. Không có boundary nào để burst qua.

Dữ liệu lưu trong Sorted Set của Redis:

• Key: rl:{user_id}
• Score: timestamp của request (milliseconds).
• Member: định danh unique của request.

Mỗi request được phép → một entry thêm vào ZSet. Các entry có score cũ hơn now - window bị xóa đi. Đếm số entry còn lại là đếm chính xác số request trong cửa sổ hiện tại.

Luồng xử lý mỗi request:

key    = "rl:{user_id}"
now    = current_timestamp_ms       # ví dụ: 1716873600000
window = 60000                      # 60 giây tính bằng ms
limit  = 100

# Bước 1: Xóa entry cũ ngoài window
ZREMRANGEBYSCORE key -inf (now - window)

# Bước 2: Đếm entry còn lại trong window
count = ZCARD key

# Bước 3: Quyết định
if count < limit:
    ZADD key now "{now}:{unique_suffix}"   # thêm entry cho request này
    EXPIRE key ceil(window / 1000)         # cleanup nếu user ngừng
    → ALLOW
else:
    → DENY

Ba bước này phải chạy atomic. Nếu không, giữa ZCARD và ZADD có thể có request khác chen vào, khiến nhiều request cùng thấy count < limit và cùng được cho qua — vượt giới hạn. Giải pháp: Lua script (xem phần 5).

Lưu ý về ZREMRANGEBYSCORE: tham số -inf và (now - window) dùng cú pháp range của Redis. Dấu ngoặc đơn ( nghĩa là exclusive — không xóa entry tại chính now - window. Nếu dùng now - window (inclusive), entry tại đúng boundary bị xóa và đếm thiếu. Cần inclusive phía trên nên dùng +inf hoặc bỏ qua vì ZCARD đếm toàn bộ còn lại.

Redis thực thi Lua script theo kiểu single-threaded, không bị interrupt — đảm bảo toàn bộ ZREMRANGEBYSCORE + ZCARD + ZADD chạy như một thao tác atomic.

-- KEYS[1]  = key (ví dụ: "rl:user_42")
-- ARGV[1]  = now_ms        (timestamp hiện tại, milliseconds)
-- ARGV[2]  = window_ms     (độ dài cửa sổ, milliseconds)
-- ARGV[3]  = limit         (số request tối đa trong window)
-- ARGV[4]  = unique_member (định danh duy nhất của request này)

local now    = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local limit  = tonumber(ARGV[3])

-- Xóa các entry có timestamp cũ hơn (now - window)
-- Dùng exclusive lower bound để giữ entry tại chính ranh giới
redis.call('ZREMRANGEBYSCORE', KEYS[1], 0, now - window - 1)

-- Đếm số request còn trong window
local count = redis.call('ZCARD', KEYS[1])

if count < limit then
    -- Thêm entry cho request hiện tại
    redis.call('ZADD', KEYS[1], now, ARGV[4])
    -- Đặt EXPIRE để key tự cleanup khi user ngừng gửi request
    redis.call('EXPIRE', KEYS[1], math.ceil(window / 1000))
    return 1   -- allowed
else
    return 0   -- denied
end

Một số điểm cần chú ý trong script:

• ZREMRANGEBYSCORE với 0 làm lower bound: timestamp milliseconds luôn dương, nên 0 tương đương -inf cho mục đích này.
• now - window - 1: trừ thêm 1ms để exclusive — entry tại đúng ranh giới now - window được giữ lại trong window.
• EXPIRE tính bằng giây: math.ceil(window / 1000) chuyển ms → s. Nếu window = 60000ms thì EXPIRE = 60s.
• Return 1/0: Redis Lua trả number; phía client chuyển sang boolean.

import time
import uuid
import redis

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

SLIDING_LOG_LUA = """
local now    = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
local limit  = tonumber(ARGV[3])

redis.call('ZREMRANGEBYSCORE', KEYS[1], 0, now - window - 1)
local count = redis.call('ZCARD', KEYS[1])

if count < limit then
    redis.call('ZADD', KEYS[1], now, ARGV[4])
    redis.call('EXPIRE', KEYS[1], math.ceil(window / 1000))
    return 1
else
    return 0
end
"""

# register_script compile script 1 lần, Redis cache bằng SHA1 (EVALSHA)
_limiter = r.register_script(SLIDING_LOG_LUA)


def is_allowed(user_id: str, limit: int = 100, window_ms: int = 60_000) -> bool:
    """
    Kiểm tra request có được phép hay không theo Sliding Window Log.

    Args:
        user_id:   Định danh người dùng.
        limit:     Số request tối đa trong window.
        window_ms: Độ dài cửa sổ (milliseconds). Mặc định 60 giây.

    Returns:
        True nếu request được phép, False nếu vượt giới hạn.
    """
    now = int(time.time() * 1000)                # milliseconds
    # Member phải UNIQUE — timestamp ms có thể trùng khi nhiều request đến cùng lúc.
    # Dùng uuid suffix ngắn để đảm bảo uniqueness mà không tốn thêm nhiều byte.
    member = f"{now}:{uuid.uuid4().hex[:8]}"
    key = f"rl:{user_id}"

    result = _limiter(keys=[key], args=[now, window_ms, limit, member])
    return bool(result)


# --- Demo ---
if __name__ == "__main__":
    user = "user_42"
    limit = 5
    window = 10_000  # 10 giây để dễ test

    for i in range(8):
        allowed = is_allowed(user, limit=limit, window_ms=window)
        status = "ALLOW" if allowed else "DENY"
        print(f"Request {i + 1}: {status}")
        time.sleep(0.1)  # 100ms giữa các request

Output mong đợi (5 ALLOW, 3 DENY trong cùng 10 giây):

Request 1: ALLOW
Request 2: ALLOW
Request 3: ALLOW
Request 4: ALLOW
Request 5: ALLOW
Request 6: DENY
Request 7: DENY
Request 8: DENY

Tại sao member phải unique? Sorted Set không cho phép member trùng. Nếu hai request đến đúng cùng millisecond và cùng dùng timestamp làm member, lệnh ZADD lần hai chỉ cập nhật score (không đổi vì score giống nhau) chứ không thêm entry mới. Kết quả: một request bị "mất" khỏi log, đếm sai. Suffix 8 ký tự hex từ UUID đủ để tránh collision trong thực tế.

Hãy xem lại kịch bản burst boundary của Fixed Window, áp dụng với Sliding Window Log (limit = 100, window = 60s):

• Lúc T=00:59:00 user gửi 100 request → 100 entry trong ZSet với score [59000, 59099] (ms).
• Lúc T=01:00:00 user muốn gửi thêm. Thuật toán xóa entry ngoài [now - 60000, now] = [60000, 120000].
• Các entry với score 59000–59099 đều nằm ngoài window → bị xóa.
• ZCARD = 0 → cho phép 100 request nữa.

Chờ đã — đây giống Fixed Window? Không. Khác biệt ở chỗ:

• Với Fixed Window: tại T=00:59:50 (50ms trước ranh giới), user gửi 100 request → tất cả được phép. Tại T=01:00:00 (10ms sau), gửi thêm 100 → vẫn được phép (counter mới = 0). Tổng: 200 request trong 10ms.
• Với Sliding Log: tại T=00:59:50 user gửi 100 request. Tại T=01:00:00, cửa sổ là [00:59:00, 01:00:00]. 50 entry từ 00:59:50–00:59:99 vẫn còn trong window → ZCARD = 50 → chỉ được thêm 50 nữa.

Ở bất kỳ thời điểm nào, thuật toán đếm chính xác số request trong 60 giây vừa qua — không phải 60 giây của ô cứng nào đó. Burst boundary không tồn tại vì không có ranh giới cứng để burst qua.

Đây là trade-off cốt lõi của Sliding Window Log. Fixed Window chỉ lưu 1 counter mỗi user. Sliding Log lưu 1 entry mỗi request được chấp nhận.

Với user gửi đúng limit 100 request/phút, ZSet của họ có tối đa 100 entry. Tại bất kỳ thời điểm nào trong khi user đang hoạt động tích cực, 100 entry đó đều nằm trong memory.

Các yếu tố ảnh hưởng memory:

• Limit lớn: limit = 1000 → 1000 entry/user. Memory tuyến tính theo limit.
• User count: mỗi user active có ZSet riêng. 1 triệu user active = 1 triệu ZSet.
• Member size: member dạng {timestamp}:{uuid_suffix} khoảng 20–25 bytes.
• Skiplist overhead: ZSet dùng skiplist khi có >128 entry (configurable). Mỗi node skiplist có pointer overhead đáng kể so với listpack.

Ước tính cho 1 entry trong ZSet (skiplist mode):

So sánh ở quy mô lớn:

Công thức: memory ≈ user_count × limit × 70 bytes. Fixed Window tốn khoảng 50 bytes × user_count (1 counter). Hệ số chênh lệch bằng đúng giá trị của limit — với limit=100 thì Sliding Log tốn gấp 100 lần.

Số liệu trên là ước tính. Trên thực tế cần đo bằng MEMORY USAGE rl:{user_id} trong Redis 4.0+ để biết chính xác cho workload cụ thể.

Một tối ưu đơn giản: ZSet không cần chứa quá limit entry. Nếu ZCARD đã bằng limit, bất kỳ request mới nào cũng bị deny — không cần thêm entry.

Điều này có nghĩa là memory của ZSet bị giới hạn bởi limit, không bởi traffic. User gửi 10.000 request/phút với limit=100 → ZSet vẫn chỉ có tối đa 100 entry (sau khi các entry cũ được ZREMRANGEBYSCORE xóa đi).

Script đã xử lý đúng điều này: ZADD chỉ được gọi khi count < limit. Trường hợp deny không thêm entry, nên ZSet không grow vô hạn dù traffic cao hơn limit.

Tuy nhiên, vẫn cần ZREMRANGEBYSCORE trong mọi trường hợp — kể cả khi deny — để loại bỏ entry cũ và đếm chính xác. Script hiện tại chạy ZREMRANGEBYSCORE trước rồi mới quyết định allow/deny, đúng theo thứ tự đó.

Cải tiến thêm: Nếu muốn giảm tải hơn nữa trong trường hợp deny, có thể dùng ZCARD trước ZREMRANGEBYSCORE làm "fast path" — nếu ZSet đã có >= limit entry thì deny ngay mà không cần xóa. Nhưng đây là heuristic, không chính xác tuyệt đối (vì chưa xóa entry cũ). Với hầu hết production use case không cần tối ưu đến mức đó.

Phù hợp dùng Sliding Window Log khi:

• Cần chính xác tuyệt đối: billing-related limit (vd: giới hạn số API call tính tiền), compliance quota (vd: regulation yêu cầu không quá N request/phút), kiểm soát gửi email/SMS (tránh spam).
• Limit nhỏ: 10–50 req/window → ZSet nhỏ, memory không đáng kể.
• User count không quá lớn: vài nghìn đến vài chục nghìn user active đồng thời.
• Memory budget cho phép: đã tính toán và Redis instance đủ RAM.

Không nên dùng khi:

• Limit lớn: 1000+ req/window → memory tuyến tính theo limit, nhanh chóng không kiểm soát được.
• Hàng triệu user active: memory bùng nổ (xem bảng tính ở phần 9).
• Memory critical: Redis instance có RAM hạn chế → dùng Sliding Window Counter (bài 35) — xấp xỉ sliding window với memory thấp như Fixed Window.
• Sai số 5–10% chấp nhận được: Fixed Window hoặc Sliding Window Counter đủ dùng, không cần tốn memory cho chính xác tuyệt đối.

Anti-patterns

• Member không unique — chỉ dùng timestamp:

  # SAI — timestamp ms có thể trùng khi nhiều request đến cùng lúc
  redis.call('ZADD', KEYS[1], now, tostring(now))
  # ZADD thứ hai với cùng member → chỉ update score, không thêm entry
  # → đếm sai, rate limiter bị bypass

• Quên ZREMRANGEBYSCORE — ZSet grow vô hạn:

  # SAI — chỉ đếm và thêm, không xóa entry cũ
  local count = redis.call('ZCARD', KEYS[1])
  if count < limit then
      redis.call('ZADD', KEYS[1], now, ARGV[4])
  end
  # ZSet chứa cả năm entry của user → memory rò

• Quên EXPIRE — key tồn tại mãi sau khi user ngừng: Nếu user gửi 50 request rồi dừng, ZSet vẫn giữ 50 entry trong memory vĩnh viễn. EXPIRE đặt bằng window đảm bảo key tự xóa sau 1 window không hoạt động.
• Non-atomic — ZCARD và ZADD là hai lệnh riêng biệt:

  # SAI — race condition giữa ZCARD và ZADD
  count = r.zcard(key)
  if count < limit:
      r.zadd(key, {member: now})  # thread khác có thể chen vào đây
  # Nhiều request cùng thấy count < limit → cùng ZADD → vượt limit

• Limit lớn + traffic cao — memory explode: Dùng Sliding Log với limit=1000 cho 1M user active → ~70GB Redis. Phải tính toán trước; không phải "bật lên rồi xem".

Best Practices

• Luôn dùng Lua script để gộp ZREMRANGEBYSCORE + ZCARD + ZADD thành atomic operation.
• Member = timestamp + uuid suffix (8 ký tự hex đủ) để đảm bảo uniqueness.
• Đặt EXPIRE bằng độ dài window (tính giây) để key tự cleanup.
• Tính memory footprint trước khi deploy: user_count × limit × 70 bytes.
• Chỉ dùng Sliding Log khi limit nhỏ (<100) hoặc user count kiểm soát được; ngưỡng cụ thể phụ thuộc RAM của Redis instance.
• Kiểm tra thực tế bằng MEMORY USAGE rl:{user_id} trên một ZSet có đúng limit entry để đo overhead chính xác cho production workload.

Sliding Window Log giải quyết triệt để burst boundary problem của Fixed Window bằng cách theo dõi timestamp từng request thay vì counter theo ô thời gian. Cửa sổ trượt liên tục theo thời gian thực: tại mọi thời điểm, thuật toán đếm chính xác số request trong [now - window, now]. Không có ranh giới cứng → không có điểm burst qua.

Đánh đổi là memory: mỗi request một entry, tỉ lệ tuyến tính với cả limit và user count. Pattern này phù hợp nhất khi cần chính xác tuyệt đối, limit nhỏ, và user count kiểm soát được. Khi memory là ràng buộc quan trọng, Sliding Window Counter (bài 35) cung cấp xấp xỉ sliding window tốt với memory tương đương Fixed Window.

Quiz

1. Mô tả burst boundary problem của Fixed Window và giải thích vì sao Sliding Window Log không có vấn đề đó. Cho ví dụ cụ thể với limit=100/phút.
2. Tại sao member của ZSet trong Sliding Window Log phải unique? Điều gì xảy ra nếu hai request đến đúng cùng millisecond và dùng chung timestamp làm member?
3. Tại sao phải dùng Lua script thay vì gọi ZREMRANGEBYSCORE + ZCARD + ZADD tuần tự từ application code?
4. Tính memory cần thiết cho Sliding Window Log với: 500.000 user active đồng thời, limit = 200 req/phút. So sánh với Fixed Window cùng scale.
5. Bạn đang xây rate limiter cho billing API: mỗi user được tối đa 10 request/phút, vượt quá sẽ tính phí phạt. User count là 50.000. Nên dùng Fixed Window hay Sliding Window Log? Giải thích lý do.

Đáp án gợi ý

1. Fixed Window reset counter về 0 tại ranh giới cứng (vd: mỗi phút). User gửi 100 req vào giây cuối của phút A (hợp lệ), rồi ngay đầu phút B gửi thêm 100 (counter vừa reset → hợp lệ). Trong 2 giây đó: 200 request. Sliding Log không có ranh giới — tại giây đầu phút B, cửa sổ [B-60s, B] vẫn chứa 100 req vừa gửi → chỉ được thêm 0 req nữa.
2. Sorted Set không cho phép member trùng. ZADD với member đã tồn tại chỉ cập nhật score (không thêm entry mới). Nếu hai request đến cùng ms và dùng chung timestamp làm member, lần ZADD thứ hai không tăng ZCARD → rate limiter đếm thiếu 1 request → có thể cho phép request vượt limit.
3. Giữa ZCARD và ZADD là hai thao tác riêng biệt trên network. Với nhiều instance application concurrent, hai thread có thể cùng đọc ZCARD = 99 (count < 100), cùng quyết định allow, cùng ZADD → ZSet có 101 entry. Lua script chạy single-threaded trong Redis, không bị interrupt — ZREMRANGEBYSCORE + ZCARD + ZADD là một atomic block.
4. Sliding Log: 500.000 × 200 × 70 bytes = 7.000.000.000 bytes ≈ 7GB. Fixed Window: 500.000 × 50 bytes = 25MB. Hệ số chênh: ~280 lần.
5. Nên dùng Sliding Window Log. Lý do: (1) billing API cần chính xác tuyệt đối — burst 2x với Fixed Window có thể gây tranh chấp ("tôi không gửi quá limit"). (2) Limit chỉ 10 req/phút → ZSet tối đa 10 entry/user — rất nhỏ. (3) 50.000 user × 10 entry × 70 bytes ≈ 35MB — hoàn toàn chấp nhận được.

Bài tiếp theo

Bài 35 giới thiệu Sliding Window Counter — thuật toán xấp xỉ sliding window bằng cách kết hợp hai Fixed Window liền kề, đạt memory thấp như Fixed Window trong khi loại bỏ phần lớn burst boundary problem.

Tham khảo

• Redis Docs — ZREMRANGEBYSCORE
• Redis Docs — ZCARD
• Redis Docs — ZADD
• Redis Docs — EVAL (Lua scripting)
• Redis Docs — Rate Limiting Patterns
• Redis Docs — MEMORY USAGE
• redis-py — Redis client cho Python