"Mỗi user chỉ được gọi API này 100 lần một phút." "Chỉ cho gửi 5 OTP một giờ." Rate limiting — giới hạn số request trong một khoảng thời gian — có mặt ở gần như mọi hệ thống backend để chống lạm dụng, chống brute-force (nối với sê-ri bảo mật), và bảo vệ tài nguyên. Và Redis là công cụ lý tưởng cho việc này: nhanh, có bộ đếm nguyên tử (INCR), TTL, và sorted set. Nhưng có nhiều thuật toán rate limiting, mỗi cái đánh đổi khác nhau giữa đơn giản, chính xác, và bộ nhớ. Bài này (phần 9/12) đo thật ba thuật toán phổ biến nhất trong redis-lab.

Ba thuật toán

Ảnh chụp đoạn mã nền tối minh hoạ rate limiting với Redis ba cách giới hạn request ba mức mượt khác nhau, giới hạn N request mỗi khoảng để chống lạm dụng chọn thuật toán quyết định độ mượt và độ chính xác. Một fixed window đơn giản nhất INCR cộng EXPIRE c bằng INCR rl:user:1 nếu c bằng 1 lần đầu trong cửa sổ EXPIRE rl:user:1 60 c nhỏ hơn bằng limit cho qua c lớn hơn limit chặn 429 nhược burst ở ranh giới 5 req cuối cửa sổ A cộng 5 req đầu cửa sổ B bằng 10 req trong khoảng 1s. Hai sliding window mượt hơn sorted set theo timestamp ZREMRANGEBYSCORE rl now-window 0 xoá request cũ ngoài cửa sổ ZCARD rl đếm request trong cửa sổ trượt ZADD rl now now-id nếu nhỏ hơn limit thì thêm request này cửa sổ trượt theo thời gian thực không burst ở ranh giới. Ba token bucket cho phép burst có kiểm soát bucket chứa tối đa N token refill r token mỗi giây mỗi request tiêu 1 token hết token chặn cho phép dồn burst dùng cả bucket rồi chờ refill mượt cho traffic thật implement bằng Lua lưu tokens last_refill tính token mới theo thời gian trôi

Hình 1: Ba thuật toán rate limiting. Fixed window (INCR+EXPIRE, đơn giản nhưng burst ở ranh giới cửa sổ); sliding window (sorted set theo timestamp, mượt, không burst); token bucket (refill token theo thời gian, cho phép burst có kiểm soát).

  • Fixed window: INCR một key mỗi request, EXPIRE cho key hết hạn sau mỗi cửa sổ (ví dụ 60s). Nếu count ≤ limit thì cho qua, vượt thì chặn (429). Đơn giản nhất — một lệnh. Nhược điểm: burst ở ranh giới — 5 request cuối cửa sổ A + 5 request đầu cửa sổ B = 10 request trong ~1 giây, gấp đôi limit.
  • Sliding window: dùng sorted set, mỗi request là một phần tử với score = timestamp. Mỗi lần: ZREMRANGEBYSCORE xoá request cũ (ngoài cửa sổ), ZCARD đếm request trong cửa sổ trượt, nếu < limit thì ZADD thêm request này. Cửa sổ trượt theo thời gian thực → không burst ở ranh giới.
  • Token bucket: bucket chứa tối đa N token, refill r token/giây; mỗi request tiêu 1 token, hết token thì chặn. Cho phép burst có kiểm soát (dồn request dùng cả bucket rồi chờ refill) — mượt cho traffic thật.

Đo thật: fixed window và sliding window

Với limit = 5, mình gửi 7 request liên tiếp:

Ảnh chụp bảng kết quả đo thật fixed window và sliding window limit 5 output thật redis:7 INCR cộng EXPIRE sorted set cộng Lua limit bằng 5. Một fixed window INCR cộng EXPIRE limit 5 mỗi cửa sổ 7 request liên tiếp request 1 c bằng 1 cho qua request 2 c bằng 2 cho qua request 3 c bằng 3 cho qua request 4 c bằng 4 cho qua request 5 c bằng 5 cho qua request 6 c bằng 6 chặn request 7 c bằng 7 chặn 5 request đầu cho qua count nhỏ hơn bằng 5 request 6-7 bị chặn 429 đơn giản 1 lệnh INCR nhưng có burst ở ranh giới cửa sổ. Hai sliding window sorted set cộng Lua cửa sổ 10s limit 5 7 request trả cho-qua count-trong-cửa-sổ request 1 1 1 request 2 1 2 request 3 1 3 request 4 1 4 request 5 1 5 request 6 0 5 request 7 0 5 cũng chặn sau 5 nhưng đếm theo cửa sổ trượt 10 giây gần nhất ZREMRANGEBYSCORE xoá cũ ZCARD đếm không có burst gấp đôi ở ranh giới như fixed window đổi lại tốn bộ nhớ hơn lưu timestamp mỗi request và phức tạp hơn cần Lua cho nguyên tử

Hình 2: Đo thật với limit 5. (1) Fixed window: request 1-5 cho qua (count ≤ 5), request 6-7 bị chặn (429). (2) Sliding window: trả [cho-qua, count] — request 1-5 [1,1..5] cho qua, request 6-7 [0,5] bị chặn, count giữ ở 5.

Kết quả thật:

  • ① Fixed window: request 1-5 cho qua (count 1→5 ≤ 5), request 6-7 bị chặn (count 6, 7 > 5). Chỉ một lệnh INCR (cộng EXPIRE lần đầu) — cực nhẹ. Nhưng nhớ nhược điểm ranh giới: nếu 5 request này ở cuối cửa sổ và 5 request nữa đến đầu cửa sổ sau, server nhận 10 request trong một khoảng ngắn.
  • ② Sliding window: trả về [cho-qua, count]. Request 1-5 trả [1, 1..5] (cho qua), request 6-7 trả [0, 5] (chặn, count giữ ở 5). Đếm theo cửa sổ trượt 10 giây gần nhất — ZREMRANGEBYSCORE xoá các request cũ ngoài cửa sổ, ZCARD đếm. Không có burst gấp đôi như fixed window, vì cửa sổ luôn tính "10 giây vừa qua tính từ bây giờ", không phải "cửa sổ cố định reset lúc chẵn phút".

Đổi lại: sliding window tốn bộ nhớ hơn (lưu một entry timestamp cho mỗi request trong cửa sổ) và phức tạp hơn (cần Lua để xoá-đếm-thêm nguyên tử, tránh race — bài redis-04). Fixed window đơn giản và rẻ nhưng kém chính xác ở ranh giới.

Đánh đổi cần cân nhắc

Chọn thuật toán theo mức chính xác CẦN. Fixed window đủ cho hầu hết trường hợp "chống lạm dụng thô" (giới hạn gọi API chung) — burst gấp đôi ở ranh giới thường không nghiêm trọng, và nó rẻ nhất. Sliding window đáng dùng khi chính xác quanh ranh giới quan trọng (ví dụ "đúng 5 OTP/giờ, không được 10"). Token bucket hợp khi muốn cho phép burst nhưng giới hạn tốc độ trung bình (API cho dồn vài request rồi đều lại). Đừng dùng sliding window phức tạp khi fixed window đã đủ.

Rate limit phải nguyên tử — đừng GET-rồi-SET. Cạm bẫy phổ biến: đọc count, kiểm, rồi ghi count+1 trong ba lệnh riêng — hai request đồng thời cùng đọc count=4, cùng thấy "còn chỗ", cùng cho qua → vượt limit. Phải dùng thao tác nguyên tử: INCR (fixed window tự nguyên tử) hoặc một script Lua (sliding window). Đây chính là lý do sliding window cần Lua — nối thẳng bài redis-04.

Rate limit phân tán và đồng hồ. Nếu nhiều instance app cùng giới hạn một user, chúng phải dùng chung một Redis (không phải mỗi instance một bộ đếm riêng — sẽ thành limit × số instance). Và sliding window dùng timestamp — nếu dùng thời gian của client (nhiều máy lệch đồng hồ) sẽ sai; tốt hơn dùng TIME của Redis (đồng hồ một nguồn) hoặc truyền timestamp nhất quán. Chi tiết nhỏ nhưng gây lỗi khó lần.

Ba ý mang về

  1. Redis là công cụ lý tưởng cho rate limiting nhờ thao tác nguyên tử. Đo thật với limit 5: fixed window (INCR+EXPIRE) cho 5 request qua, chặn 6-7; sliding window (sorted set+Lua) cũng vậy nhưng đếm theo cửa sổ trượt.
  2. Mỗi thuật toán đánh đổi đơn giản vs chính xác vs bộ nhớ. Fixed window rẻ nhất (1 lệnh) nhưng burst ở ranh giới; sliding window mượt/chính xác hơn nhưng tốn bộ nhớ (lưu timestamp mỗi request) và cần Lua; token bucket cho phép burst có kiểm soát.
  3. Rate limit phải nguyên tử và dùng chung một Redis. Đừng GET-rồi-SET (race làm vượt limit) — dùng INCR hoặc Lua; nhiều instance phải chia sẻ một bộ đếm Redis; và sliding window nên dùng đồng hồ một nguồn để tránh lệch thời gian.

Nguồn

Phần sau ta tìm hiểu Redis có thật sự mất dữ liệu khi chết không: hai cơ chế persistence RDB và AOF, chúng ghi xuống đĩa thế nào, và đánh đổi giữa độ bền và hiệu năng.