Hình dung một rạp hát bán vé với quy định "tối đa 100 vé mỗi ngày", và cái đồng hồ đếm vé reset về 0 đúng nửa đêm. Một người tinh ranh mua 100 vé lúc 23 giờ 59, rồi mua thêm 100 vé lúc 0 giờ 01 — hai trăm vé trong vòng hai phút, mà sổ sách mỗi ngày vẫn ghi đúng 100. Không dòng nào sai, không quy định nào bị phá trên giấy tờ; lỗ hổng nằm ở chính chỗ ranh giới ngày đặt ở đâu. Đây đúng là lỗi của thuật toán giới hạn tần suất đơn giản nhất, và bài này cài bốn thuật toán bằng Lua rồi đo cả tốc độ, bộ nhớ lẫn độ chính xác để xem cái giá của việc bịt lỗ hổng đó là gì.
Giới hạn tần suất là ứng dụng phổ biến nhất của Redis sau bộ đệm.
Bốn thuật toán
| Thuật toán | Thông lượng | Bộ nhớ mỗi người dùng |
|---|---|---|
| Cửa sổ cố định | 16.432/s | 56 byte |
| Gàu token | 14.699/s | 72 byte |
| Cửa sổ trượt | 14.124/s | 56 byte |
| Nhật ký trượt | 11.539/s | 92.184 byte |
Chênh lệch tốc độ nhỏ — 1,42 lần giữa nhanh nhất và chậm nhất. Chênh lệch bộ nhớ thì không nhỏ chút nào.
Cửa sổ cố định là một INCR trên khoá gồm cả số cửa sổ:
local k = KEYS[1] .. ':' .. math.floor(now / window)
local n = redis.call('INCR', k)
if n == 1 then redis.call('PEXPIRE', k, window * 2) end
return n <= limit and 1 or 0
Đơn giản nhất, nhanh nhất, và sai nhiều nhất.
Lỗi ranh giới, đo được
Tôi bắn 200 yêu cầu ngay cuối một cửa sổ, rồi 200 nữa ngay đầu cửa sổ sau.
| Thuật toán | Cuối cửa sổ | Đầu cửa sổ sau | Tổng trong ~0,3 giây |
|---|---|---|---|
| Cửa sổ cố định | 100 | 100 | 200 |
| Nhật ký trượt | 100 | 0 | 100 |
| Cửa sổ trượt | 100 | 2 | 102 |
| Gàu token | 101 | 14 | 115 |
Giới hạn là 100 mỗi giây, và 200 yêu cầu đi qua trong 0,3 giây — đúng người mua vé lúc 23:59 và 0:01. Đây là lỗi kinh điển của cửa sổ cố định, và điều đáng nói là nó không bao giờ hiện ra trong phép thử bình thường. Bắn đều tay thì nó cho qua đúng 100/giây. Nó chỉ lộ ra khi ai đó canh đúng ranh giới — và kẻ tấn công thì canh.
Cửa sổ trượt: gần đúng và rẻ
Cửa sổ trượt giữ hai bộ đếm — cửa sổ hiện tại và cửa sổ trước — rồi nội suy:
local frac = (now % w) / w
local est = truoc * (1 - frac) + hien_tai
Nếu bạn đang ở 30% cửa sổ hiện tại, nó tính 70% số của cửa sổ trước cộng toàn bộ số hiện tại. Kết quả: 102 thay vì 100 — sai 2%, với 56 byte và tốc độ gần bằng cửa sổ cố định. Đây là lựa chọn mặc định đúng cho gần như mọi trường hợp. Nó là cách các dịch vụ lớn thực sự dùng.
Nhật ký trượt: chính xác và không dùng được
Nhật ký trượt lưu mọi yêu cầu vào một Sorted Set với điểm là dấu thời gian, rồi xoá những cái đã ra khỏi cửa sổ. Kết quả: 100 — chính xác tuyệt đối. Cái giá:
1 triệu người dùng, giới hạn 1.000/phút
cửa sổ cố định 53,4 MB
gàu token 68,7 MB
nhật ký trượt 87.913,5 MB
Gấp 1.646 lần. 88 GB cho việc mà 53 MB làm được với sai số 2%. Nó cũng chậm nhất, và mỗi lần gọi phải chạy ZREMRANGEBYSCORE — một lệnh O(log N + M) trên tập có thể rất lớn.
Dùng nó khi giới hạn nhỏ (chục yêu cầu) và số đối tượng ít, ví dụ giới hạn cho tài khoản quản trị. Đừng dùng cho lưu lượng công khai.
Gàu token: cho phép bùng nổ có kiểm soát
Gàu token giữ số token và thời điểm cập nhật, nạp lại theo thời gian trôi qua:
tok = math.min(cap, tok + (now - ts) * cap / w)
if tok >= 1 then tok = tok - 1; ok = 1 end
Kết quả 115 — vượt 15%, và đó là có chủ ý: token tích lại trong lúc rảnh, cho phép một đợt bùng nổ ngắn. Đây là thuật toán duy nhất trong bốn cái mô hình hoá được ý "cho phép dùng dồn nếu trước đó không dùng". Với API mà người dùng thỉnh thoảng gửi một lô, đó là hành vi mong muốn, không phải lỗi.
Hai tham số tách nhau: dung lượng gàu quyết định đợt bùng nổ tối đa, tốc độ nạp quyết định tần suất bền vững. Cửa sổ cố định và cửa sổ trượt không tách được hai thứ này.
Chọn cái nào
| Nhu cầu | Chọn |
|---|---|
| Mặc định, lưu lượng công khai | Cửa sổ trượt |
| Cho phép bùng nổ, ví dụ API | Gàu token |
| Đơn giản nhất, chấp nhận sai gấp đôi | Cửa sổ cố định |
| Chính xác tuyệt đối, ít đối tượng | Nhật ký trượt |
Và một lưu ý áp cho cả bốn: viết bằng Lua, đừng viết bằng nhiều lệnh từ phía ứng dụng. GET rồi INCR từ hai tiến trình khác nhau sẽ cho qua nhiều hơn giới hạn — chính là bài toán đo ở phần về khoá phân tán.
Ba chi tiết thực hành
Luôn đặt TTL. Khoá giới hạn tần suất không có hạn là khoá bất tử, và bạn có một khoá cho mỗi người dùng từng gọi API. Đặt TTL bằng hai lần cửa sổ.
Trả về thông tin cho khách. Chỉ chặn thì người gọi không biết chờ bao lâu. Trả thêm số còn lại và thời điểm được gọi lại — hầu hết script có sẵn con số đó, chỉ cần trả về.
Cẩn thận với Cluster. Khoá giới hạn cho một người dùng phải nằm cùng slot nếu script chạm nhiều khoá — cửa sổ trượt chạm hai khoá, và như đo ở phần 23, đó là CROSSSLOT trừ khi bạn dùng thẻ băm {user123}.
Mẫu số chung: chính xác tuyệt đối là một cái bẫy tài nguyên
Cái đắt nhất trong bảng — nhật ký trượt, 88 GB để đúng tuyệt đối — minh hoạ một quy luật chung: một lời giải chính xác hoàn hảo thường phải giữ trạng thái tỉ lệ với từng sự kiện (O(n)), trong khi một xấp xỉ có sai số bị chặn chỉ cần trạng thái cố định (O(1)); và ở quy mô lớn, cái sai số bị chặn ấy gần như luôn là lựa chọn kỹ thuật đúng. Cửa sổ trượt sai 2% mà tốn 1/1.646 bộ nhớ — đổi hai phần trăm lấy một bậc độ lớn ba chữ số.
Trong thế giới Java, đây đúng là lý do người ta dùng HyperLogLog để đếm số phần tử khác nhau thay vì một HashSet (đúng cái Redis PFCOUNT làm ở phần trước): HLL sai vài phần trăm nhưng dùng vài KB cố định thay cho bộ nhớ tỉ lệ số phần tử. Bloom filter của Guava cũng vậy — trả lời "có thể có / chắc chắn không" với sai dương nhỏ, đổi lấy bộ nhớ tí hon; và histogram của Micrometer gom mẫu vào các thùng cố định thay vì lưu từng mẫu để tính phân vị.
Trong Go, cùng tinh thần: HdrHistogram hay count-min sketch cho phép đo phân vị và tần suất với bộ nhớ chặn trước, thay vì giữ mọi quan sát.
Còn ở cơ sở dữ liệu, đây là khác biệt giữa SELECT count(*) quét cả bảng và đọc reltuples ước lượng của PostgreSQL trong một phần nghìn thời gian; là các phép phân vị xấp xỉ (approx_percentile), là lấy mẫu (TABLESAMPLE) — mọi nơi dữ liệu quá lớn để đếm đúng đều có một câu trả lời "đủ gần" rẻ hơn nhiều bậc.
Mẫu số chung: đòi hỏi chính xác tuyệt đối buộc bạn giữ trạng thái tỉ lệ với số sự kiện, còn chấp nhận một sai số bị chặn cho phép trạng thái cố định — nên trước khi cài lời giải "đúng đến từng đơn vị", hãy hỏi sai số nào thật sự chấp nhận được, vì thường một xấp xỉ 2% rẻ hơn ba bậc độ lớn. Câu hỏi đúng không phải "làm sao đếm cho chính xác" mà là "tôi cần chính xác đến đâu, và cái chính xác thừa ra đang khiến tôi trả giá gấp bao nhiêu lần". Với giới hạn tần suất công khai, câu trả lời gần như luôn là cửa sổ trượt.
Muốn tự xem giới hạn tần suất của bạn có đang bị vượt ở ranh giới không:
# dem so khoa gioi han hien co va kieu cua chung
redis-cli --scan --pattern 'rate*' --count 500 | head -1000 | while read k; do
echo "$(redis-cli type "$k") $(redis-cli pttl "$k") $k"
done | awk '{print $1}' | sort | uniq -c
zset nghĩa là bạn đang dùng nhật ký trượt — kiểm tổng bộ nhớ ngay, vì đó là cách tốn nhất. string với TTL âm (-1) nghĩa là khoá không có hạn: chúng sẽ tích lại vĩnh viễn, và số lượng bằng số người dùng từng gọi API của bạn.
Phần sau: cache-aside — đo tỉ lệ trúng và cái giá thật của một lần trượt.
