Giới hạn tần suất là ứng dụng phổ biến nhất của Redis sau bộ đệm. 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.
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.
Đâ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}.
Thử ba mươi giây
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.
