Sliding window: vì sao sai OTP 5 lần bị khóa 1 phút?

Sai OTP vài lần là bị khóa: phía sau là một rate limiter. Từ lỗ hổng của cách đếm theo phút, tới sliding window, hệ thống nhiều server và bài thi đấu.

16 phút đọcTrung cấpEyeBlogs

Đọc bản tiếng Anh →

Hình minh hoạ phẳng trên nền hồng: bên trái là màn hình máy tính với ô đăng nhập gồm biểu tượng ổ khoá, ô tên đăng nhập và ô mật khẩu; bên phải là bàn tay cầm điện thoại hiện biểu tượng chìa khoá, phía trên có dòng chữ "Mã OTP".
Mục lục

Bạn nhập sai mã OTP lần thứ năm, và ứng dụng ngân hàng hiện dòng chữ: “Bạn đã nhập sai quá nhiều lần, vui lòng thử lại sau 1 phút”. Trang bán vé concert báo “Bạn thao tác quá nhanh”. Một lập trình viên gọi API liên tục và nhận về lỗi 429 Too Many Requests. Ba tình huống, cùng một cơ chế: rate limiting, tức giới hạn số lần một người được làm một việc trong một khoảng thời gian.

Câu hỏi nghe đơn giản: hệ thống đếm “5 lần trong 1 phút” như thế nào? Câu trả lời tốt nhất có tên là sliding window (cửa sổ trượt): thay vì đếm theo từng phút trên đồng hồ, hệ thống luôn nhìn vào đúng 60 giây vừa qua, một khung thời gian trượt theo từng khoảnh khắc. Có cái mới thì thêm vào, cái nào đã quá 60 giây thì bỏ ra, không bao giờ phải đếm lại từ đầu.

Nửa đầu bài này không cần biết lập trình: nó kể vì sao cách đếm “ngây thơ” có một lỗ hổng ở giây thứ 59, và cửa sổ trượt bịt lỗ hổng ấy ra sao. Nửa sau dành cho người muốn đi sâu: rate limiter chạy thế nào khi có hàng trăm server, và vì sao cùng ý tưởng này là một dạng bài kinh điển trong lập trình thi đấu, chỉ khó hơn binary search một chút.

Rate limiting là gì?

Hãy hình dung bảo vệ của một tòa nhà được dặn: mỗi giờ chỉ cho tối đa 100 khách vào. Người bảo vệ ấy chính là một rate limiter. Trên Internet, “khách” là các yêu cầu (request) gửi tới server: một lần đăng nhập, một lần bấm “mua vé”, một lần ứng dụng hỏi giá cổ phiếu.

Gần như mọi hệ thống lớn đều có người bảo vệ này, vì ba lý do.

Chống kẻ gian đoán mò. Mã OTP 6 chữ số có một triệu khả năng. Nếu được thử thoải mái, một chương trình máy tính sẽ thử hết trong vài phút. Nhưng nếu mỗi phút chỉ được sai 5 lần, thì thử hết một triệu khả năng mất gần 140 ngày, trong khi mã OTP chỉ sống vài phút. Mật khẩu cũng vậy: giới hạn số lần đăng nhập sai là lớp phòng thủ rẻ nhất chống lại việc dò mật khẩu.

Chống một người làm nghẽn tất cả. Một ứng dụng viết lỗi, gọi API trong một vòng lặp không có điểm dừng, có thể gửi hàng nghìn request mỗi giây. Không có giới hạn, một khách hàng như vậy có thể làm chậm hệ thống của tất cả những người còn lại. Rate limiter đảm bảo mỗi người chỉ được dùng một phần công bằng.

Giữ chi phí. Mỗi request tốn tiền: thời gian máy chủ, băng thông, đôi khi là tiền trả cho một dịch vụ khác (gửi một tin nhắn SMS chứa OTP tốn tiền thật). Giới hạn số request là giới hạn số tiền một người dùng, hoặc một kẻ phá hoại, có thể đốt của bạn.

Khi bị chặn, server trả về mã lỗi HTTP 429 Too Many Requests, được định nghĩa từ năm 2012, và có thể kèm theo một dòng Retry-After cho biết phải đợi bao lâu mới được thử lại[1]. Dòng chữ “thử lại sau 1 phút” bạn thấy trên điện thoại thường chính là con số ấy, được viết lại cho dễ đọc.

Cách đếm ngây thơ và lỗ hổng ở giây thứ 59

Cách đơn giản nhất để đếm “tối đa 100 request mỗi phút” là dùng đồng hồ treo tường. Mỗi khi sang phút mới (10:00, 10:01, 10:02…), xóa bảng về 0. Mỗi request đến thì cộng 1. Bảng chưa tới 100 thì cho qua, tới 100 rồi thì chặn đến hết phút. Cách này gọi là fixed window (khung cố định).

Nó cực kỳ rẻ: mỗi người dùng chỉ cần nhớ một con số. Và trong phần lớn thời gian, nó hoạt động tốt. Nhưng hãy xem một kẻ tinh ý làm gì:

  • Từ giây thứ 55 đến giây thứ 59 của phút 10:00, hắn gửi 100 request. Bảng đếm được 100, chưa vượt giới hạn. Tất cả đều lọt.
  • Đúng giây 00 của phút 10:01, bảng bị xóa về 0. Từ giây 00 đến giây 05, hắn gửi thêm 100 request. Bảng lại đếm được 100. Tất cả lại lọt.

Kết quả: 200 request lọt qua chỉ trong 10 giây, gấp đôi giới hạn, mà không vi phạm quy tắc nào. Lỗ hổng nằm ở chỗ quy tắc nói “mỗi phút”, nhưng hệ thống lại hiểu thành “mỗi phút trên đồng hồ”. Hai chuyện đó khác nhau đúng ở những giây quanh lúc kim phút nhảy.

Hai dòng thời gian từ 0 đến 120 giây. Dòng trên: hai khung chữ nhật cho phút 1 và phút 2, một cụm 200 chấm đỏ nằm từ giây 55 đến giây 65, vắt qua ranh giới hai khung; mũi tên đánh dấu đoạn 10 giây này. Dòng dưới: một khung vàng dài 60 giây kết thúc ở giây 65, 100 chấm đầu tô vàng (được cho qua), 100 chấm sau tô xám (bị chặn).
Hình 1. Trên: đếm theo phút trên đồng hồ, mỗi phút chỉ thấy 100 request nên cho qua cả 200. Dưới: cửa sổ trượt nhìn đúng 60 giây vừa qua, thấy đủ 100 thì chặn phần còn lại.

Với một trang tin tức, 200 request thay vì 100 có thể không sao. Với mã OTP, nó nghĩa là kẻ tấn công được thử gấp đôi số lần bạn tưởng. Với một hệ thống đang quá tải, đó là một cơn sóng gấp đôi ập vào đúng lúc nó yếu nhất.

Cửa sổ trượt: luôn nhìn đúng 60 giây vừa qua

Cách sửa là đổi câu hỏi. Thay vì hỏi “phút này đã có bao nhiêu request?”, hệ thống hỏi “trong 60 giây tính tới đúng lúc này, đã có bao nhiêu request?”.

Hãy tưởng tượng một ô cửa sổ dài đúng 60 giây đặt trên dòng thời gian. Cạnh phải của nó luôn là “bây giờ”, nên nó trượt dần sang phải theo đồng hồ. Mỗi khi có request mới, request ấy rơi vào mép phải của cửa sổ. Cùng lúc đó, những request đã cũ hơn 60 giây trôi ra khỏi mép trái và không còn được tính. Muốn biết có được cho qua hay không, chỉ cần đếm những gì đang nằm trong cửa sổ.

Quay lại kẻ tinh ý ở trên. Đến giây thứ 00 của phút mới, cửa sổ vẫn còn chứa nguyên 100 request hắn vừa gửi ở giây 55 đến 59. Không có lần “xóa bảng” nào cả. Mọi request tiếp theo đều bị chặn, cho tới khi những request cũ lần lượt trôi ra khỏi mép trái, tức khoảng giây 55 của phút sau. Trong bất kỳ khoảng 60 giây nào, không bao giờ có quá 100 request lọt qua.

Điểm hay của cửa sổ trượt nằm ở chữ “trượt”: hệ thống không phải đếm lại từ đầu mỗi lần. Nó chỉ làm hai việc nhỏ ở hai mép: thêm cái mới vào, bỏ cái cũ ra. Ghi nhớ ý này, vì nó sẽ quay lại ở cuối bài dưới một hình dạng khác.

Ba cách làm trong thực tế

Ý tưởng thì rõ, nhưng “nhớ mọi request trong 60 giây qua” có giá. Một API phục vụ hàng triệu người dùng không thể nhớ thời điểm của từng request cho từng người. Vì vậy các hệ thống thật chọn một trong vài cách, mỗi cách đổi độ chính xác lấy bộ nhớ theo một tỷ lệ khác nhau.

Sliding window log (nhật ký cửa sổ trượt) làm đúng như mô tả ở trên: lưu thời điểm của từng request được cho qua, bỏ những cái cũ hơn 60 giây, rồi đếm số còn lại. Nó chính xác tuyệt đối. Cái giá là bộ nhớ: giới hạn 1.000 request mỗi phút nghĩa là phải nhớ tới 1.000 con số cho mỗi người dùng.

Sliding window counter (bộ đếm cửa sổ trượt) là một cách ước lượng thông minh. Nó chỉ nhớ hai con số: số request của phút trước và của phút hiện tại, giống cách đếm theo đồng hồ. Rồi nó giả định rằng request của phút trước rải đều trong phút đó. Nếu đang ở giây thứ 15 của phút này, thì cửa sổ 60 giây vừa qua gồm 15 giây của phút này và 45 giây cuối của phút trước. Phần của phút trước được ước lượng bằng 4560\frac{45}{60} số request của nó:

ước lượng=phuˊt trước×60−soˆˊ giaˆy đa˜ troˆi60+phuˊt naˋy\text{ước lượng} = \text{phút trước} \times \frac{60 - \text{số giây đã trôi}}{60} + \text{phút này}

Cloudflare, công ty đứng giữa một phần rất lớn lưu lượng web thế giới, dùng đúng cách này cho dịch vụ rate limiting của họ. Họ kiểm tra nó trên 400 triệu request từ 270.000 nguồn khác nhau, và chỉ 0,003% request bị cho qua hoặc bị chặn nhầm[2].

Token bucket (xô thẻ) là một cách nghĩ khác hẳn. Mỗi người dùng có một cái xô chứa tối đa, chẳng hạn, 100 thẻ. Mỗi request phải nộp một thẻ, hết thẻ thì bị chặn. Thẻ được bỏ thêm vào xô với tốc độ đều, ví dụ mỗi 0,6 giây một thẻ. Người lâu không dùng sẽ tích đầy xô và được phép gửi dồn một đợt, nhưng về lâu dài không thể vượt tốc độ bỏ thẻ. Stripe, công ty thanh toán trực tuyến, dùng token bucket cho API của họ[3].

Cách Chính xác Bộ nhớ mỗi người dùng Cho gửi dồn?
Đếm theo phút cố định Lọt gấp đôi ở ranh giới phút 1 con số Có, kể cả ngoài ý muốn
Sliding window log Tuyệt đối Bằng giới hạn Không
Sliding window counter Gần đúng, sai lệch nhỏ với lưu lượng thường 2 con số Không đáng kể
Token bucket Đúng với định nghĩa của nó 2 con số Có, trong sức chứa của xô

Chọn cách nào là một quyết định thiết kế. Cửa đăng nhập và OTP, nơi một lần lọt cũng là một lần kẻ gian được thử, đáng dùng cách chính xác. Một API dữ liệu phục vụ hàng triệu khách hàng thì sliding window counter hoặc token bucket gọn hơn nhiều, và sai lệch nhỏ không đáng kể so với bộ nhớ tiết kiệm được.

Khi có cả trăm server cùng đếm

Mọi thứ ở trên giả định có một người bảo vệ duy nhất. Hệ thống thật thường có hàng chục, hàng trăm server cùng phục vụ, và request của một người dùng có thể rơi vào bất kỳ server nào. Nếu mỗi server tự đếm riêng, giới hạn 100 request mỗi phút trên 10 server thực chất thành 1.000.

Cách phổ biến là đặt bộ đếm ở một chỗ dùng chung mà mọi server cùng hỏi, thường là Redis, một cơ sở dữ liệu nằm hoàn toàn trong RAM, trả lời trong chưa tới một mili giây. Với cách đếm theo phút, mỗi người dùng là một con số trong Redis, tự hết hạn khi sang phút mới. Với sliding window log, Redis có sẵn một cấu trúc gọi là sorted set, tập hợp có thứ tự, rất hợp để lưu các thời điểm và xóa nhanh những thời điểm cũ hơn 60 giây[4]. Stripe chạy rate limiter của họ trên Redis[3], và cách ước lượng hai con số của Cloudflare được chọn một phần vì nó chỉ cần một lệnh cộng duy nhất cho mỗi request[2].

Có chỗ dùng chung rồi, vẫn còn ba câu hỏi thiết kế.

Hai server đếm cùng một lúc. Nếu server A đọc “99”, server B cũng đọc “99”, rồi cả hai cùng cho qua và cùng ghi “100”, thì thực tế đã có 101 request lọt. Lỗi này gọi là race condition. Cách sửa là để Redis làm cả việc đọc, kiểm tra và ghi trong một bước không thể chen ngang, bằng các lệnh cộng có sẵn hoặc một đoạn script nhỏ chạy ngay bên trong Redis.

Khi bộ đếm hỏng. Nếu Redis không trả lời, hệ thống nên cho qua hết (fail-open) hay chặn hết (fail-closed)? Không có đáp án chung. Với API đọc dữ liệu, cho qua hết thường hợp lý hơn: thà chịu tải cao một lúc còn hơn làm sập dịch vụ của mọi khách hàng. Với cửa nhập OTP, chặn hết an toàn hơn: thà bắt người dùng đợi một phút còn hơn mở toang cửa cho kẻ dò mã.

Đếm theo ai? Theo địa chỉ IP thì đơn giản, nhưng cả một quán cà phê, một trường học, hay hàng nghìn thuê bao di động có thể dùng chung một địa chỉ IP, và một người dùng xấu sẽ làm cả nhóm bị chặn theo. Theo tài khoản hoặc theo API key thì công bằng hơn, nhưng chỉ dùng được sau khi biết người gửi là ai. Vì vậy cửa đăng nhập thường giới hạn theo IP và theo tài khoản đang bị thử, còn các API đã xác thực thì giới hạn theo người dùng, chẳng hạn theo danh tính ghi trong token JWT mà request mang theo.

Rate limiter thường được đặt ở API gateway, cánh cổng đứng trước mọi service, để request bị chặn không bao giờ tới được phần đắt nhất của hệ thống.

Sliding window trong lập trình thi đấu

Đến đây, ta rời rate limiter để nhìn cùng một ý tưởng ở chỗ nó được dạy đầu tiên: các bài thi lập trình. Phần này dùng một chút ký hiệu, ai chỉ quan tâm phần thực tế có thể dừng ở đây mà không mất ý chính.

Bài 1: cửa sổ cố định. Cho một dãy số và một số kk. Tìm tổng lớn nhất của kk số liên tiếp. Ví dụ dãy 3 1 4 1 5 9 2 6 với k=3k = 3: các nhóm ba số liên tiếp có tổng 8, 6, 10, 15, 16, 17, nên đáp án là 17 (nhóm 9 2 6).

Cách thô là với mỗi vị trí, cộng lại kk số từ đầu. Có khoảng nn vị trí, mỗi vị trí kk phép cộng, tổng cộng O(n⋅k)O(n \cdot k) phép tính. Với nn một triệu và kk mười nghìn, đó là mười tỷ phép cộng.

Cửa sổ trượt nhận ra rằng hai nhóm liền nhau gần như trùng nhau: nhóm 4 1 5 và nhóm 1 5 9 chung nhau 1 5. Đi từ nhóm trước sang nhóm sau, chỉ cần cộng số mới vào ở mép phải và trừ số cũ ra ở mép trái: 10−4+9=1510 - 4 + 9 = 15. Mỗi bước chỉ còn hai phép tính, cả bài chỉ còn O(n)O(n). Đây chính xác là “thêm cái mới, bỏ cái cũ” của rate limiter, chỉ khác là trên dãy số thay vì trên dòng thời gian.

Bài 2: cửa sổ co giãn. Cho một chuỗi ký tự, tìm độ dài đoạn liên tiếp dài nhất không có ký tự nào lặp lại. Với chuỗi abcabcbb, đáp án là 3 (đoạn abc). Đây là bài số 3 trên LeetCode, một trong những bài phỏng vấn nổi tiếng nhất[5].

Lần này cửa sổ không có độ dài cố định. Ta giữ hai con trỏ, mép trái và mép phải. Mép phải lần lượt tiến từng ký tự một. Nếu ký tự mới đã có trong cửa sổ, mép trái nhảy tới ngay sau lần xuất hiện trước của ký tự đó, để cửa sổ lại sạch ký tự lặp. Cửa sổ dãn ra khi còn hợp lệ, co lại khi vi phạm. Mỗi mép chỉ đi tới, không bao giờ lùi, nên cả hai cùng đi tối đa nn bước: vẫn là O(n)O(n).

Chỗ “khó hơn binary search một chút” nằm ở đây. Binary search có một ý duy nhất: chia đôi. Cửa sổ co giãn đòi hỏi bạn tự trả lời hai câu: cửa sổ đang giữ bất biến gì (ở đây: không có ký tự lặp), và khi nào phải co mép trái để giữ bất biến ấy. Trả lời đúng hai câu này thì code chỉ còn vài dòng.

Góc thi đấu: nhận ra một bài sliding window

Một bài thường giải được bằng cửa sổ trượt khi đề hỏi về một đoạn liên tiếp (mảng con, chuỗi con, khoảng thời gian) và điều kiện của đoạn có tính “đơn điệu”: nếu một đoạn hợp lệ thì thu nhỏ nó vẫn hợp lệ, hoặc nếu một đoạn vi phạm thì mở rộng nó vẫn vi phạm. Tính đơn điệu ấy là thứ cho phép mép trái chỉ đi tới mà không bao giờ cần lùi.

Năm bài luyện từ dễ đến khó, đều trên LeetCode:

Bài Tên Ý chính
643 Maximum Average Subarray I Cửa sổ cố định, đúng như bài 1
3 Longest Substring Without Repeating Characters Cửa sổ co giãn, đúng như bài 2
424 Longest Repeating Character Replacement Co giãn, bất biến khó hơn: số ký tự cần thay ≤ kk
76 Minimum Window Substring Tìm cửa sổ ngắn nhất chứa đủ các ký tự cho trước
239 Sliding Window Maximum Giá trị lớn nhất của mọi cửa sổ: cần thêm hàng đợi hai đầu (deque)

Bài 239 là bước tiếp theo tự nhiên: tổng thì cộng trừ được, nhưng giá trị lớn nhất thì không “trừ” ra được khi một phần tử rời cửa sổ. Lời giải giữ một hàng đợi các ứng viên theo thứ tự giảm dần, và đó là cánh cửa sang một họ kỹ thuật khác (monotonic queue).

Tự tay mô phỏng

Đoạn Python dưới đây làm hai việc. Phần đầu là lời giải của hai bài thi đấu ở trên. Phần sau mô phỏng ba cách đếm của rate limiter, giới hạn 100 request mỗi 60 giây, trên cùng một kịch bản: một người dùng gửi lác đác khoảng 6 request mỗi phút, rồi dồn 120 request vào 5 giây cuối phút thứ nhất và 120 request vào 5 giây đầu phút thứ hai, đúng mánh khóe ở Hình 1. Nó tạo ra Hình 2. Chỉ cần cài matplotlib.

sliding_window.py
import random
from collections import deque
import matplotlib.pyplot as plt
plt.rcParams.update({"figure.facecolor": "#16181c", "axes.facecolor": "#16181c", "text.color": "#d4d7dc",
"axes.edgecolor": "#2a2e35", "xtick.color": "#878d97", "ytick.color": "#878d97", "font.size": 12})
random.seed(2026) # Cố định seed để chạy lại ra cùng kết quả.
# ── Hai bài thi đấu ─────────────────────────────────────────────────────────
def max_sum_window(a, k):
"""Tổng lớn nhất của k phần tử liên tiếp. Mỗi bước: cộng phần tử mới, trừ phần tử vừa rơi ra."""
s = best = sum(a[:k])
for i in range(k, len(a)):
s += a[i] - a[i - k]
best = max(best, s)
return best
def longest_unique(s):
"""Độ dài chuỗi con dài nhất không lặp ký tự (LeetCode 3). Cửa sổ [lo, i] luôn không có ký tự lặp."""
last, lo, best = {}, 0, 0
for i, ch in enumerate(s):
if last.get(ch, -1) >= lo: # ch đã có trong cửa sổ: co mép trái qua lần xuất hiện trước
lo = last[ch] + 1
last[ch] = i
best = max(best, i - lo + 1)
return best
print(max_sum_window([3, 1, 4, 1, 5, 9, 2, 6], 3)) # 9 + 2 + 6 = 17
print(longest_unique("abcabcbb")) # "abc" → 3
# ── Ba cách đếm của rate limiter: tối đa LIMIT request trong mỗi WINDOW giây ──
LIMIT, WINDOW = 100, 60
class FixedWindow:
"""Đếm theo phút trên đồng hồ, sang phút mới thì về 0."""
def __init__(self):
self.window, self.count = None, 0
def allow(self, t):
w = int(t // WINDOW)
if w != self.window:
self.window, self.count = w, 0
if self.count < LIMIT:
self.count += 1
return True
return False
class SlidingLog:
"""Nhớ thời điểm của từng request được cho qua; bỏ những cái cũ hơn WINDOW giây."""
def __init__(self):
self.log = deque()
def allow(self, t):
while self.log and self.log[0] <= t - WINDOW:
self.log.popleft()
if len(self.log) < LIMIT:
self.log.append(t)
return True
return False
class SlidingCounter:
"""Chỉ giữ hai con số: số request phút trước và phút này, rồi ước lượng theo tỷ lệ thời gian."""
def __init__(self):
self.window, self.prev, self.cur = None, 0, 0
def allow(self, t):
w = int(t // WINDOW)
if w != self.window:
self.prev = self.cur if self.window == w - 1 else 0
self.window, self.cur = w, 0
elapsed = t - w * WINDOW
estimate = self.prev * (WINDOW - elapsed) / WINDOW + self.cur
if estimate < LIMIT:
self.cur += 1
return True
return False
# Một client bình thường gửi lác đác (khoảng 6 request mỗi phút), rồi dồn 120 request vào 5 giây
# cuối phút thứ nhất và 120 request vào 5 giây đầu phút thứ hai.
requests = [random.uniform(0, 180) for _ in range(18)]
requests += [55 + random.random() * 5 for _ in range(120)]
requests += [60 + random.random() * 5 for _ in range(120)]
requests.sort()
limiters = {"đếm theo phút cố định": FixedWindow(), "sliding window log": SlidingLog(),
"sliding window counter": SlidingCounter()}
allowed = {name: [t for t in requests if lim.allow(t)] for name, lim in limiters.items()}
def worst_60s(times):
"""Số request được cho qua nhiều nhất trong một khoảng 60 giây bất kỳ (chính là một cửa sổ trượt)."""
best, lo = 0, 0
for hi in range(len(times)):
while times[hi] - times[lo] >= WINDOW:
lo += 1
best = max(best, hi - lo + 1)
return best
print(f"{'cách đếm':<24} {'cho qua':>8} {'nhiều nhất trong 60 giây':>26}")
for name, times in allowed.items():
print(f"{name:<24} {len(times):>8} {worst_60s(times):>26}")
# Vẽ: số request đã cho qua trong 60 giây gần nhất, tại từng thời điểm.
grid = [i / 10 for i in range(0, 1801)]
fig, ax = plt.subplots(figsize=(9, 4.8))
colors = {"đếm theo phút cố định": "#c98f8f", "sliding window log": "#e8b05a", "sliding window counter": "#8fa9c9"}
for name, times in allowed.items():
ys = []
for g in grid:
ys.append(sum(1 for t in times if g - WINDOW < t <= g))
ax.plot(grid, ys, color=colors[name], lw=2, label=name)
ax.axhline(LIMIT, color="#d4d7dc", lw=1, ls="--")
ax.text(2, LIMIT + 4, f"giới hạn: {LIMIT} request / 60 giây", color="#a4a9b2", fontsize=10)
for m in range(1, 3):
ax.axvline(m * WINDOW, color="#2a2e35", lw=1)
ax.set_xlim(0, 180)
ax.set_xlabel("thời gian (giây) · vạch dọc: sang phút mới", color="#a4a9b2")
ax.set_ylabel("request đã cho qua trong 60 giây vừa rồi", color="#a4a9b2")
ax.grid(color="#22262c")
ax.legend(frameon=False, labelcolor="#a4a9b2", fontsize=10, loc="upper left")
ax.set_title("Dồn request quanh lúc sang phút mới", color="#d4d7dc", fontsize=12)
fig.savefig("rate-limiter.png", dpi=150, bbox_inches="tight")
17
3
cách đếm cho qua nhiều nhất trong 60 giây
đếm theo phút cố định 206 200
sliding window log 111 100
sliding window counter 122 111
Biểu đồ đường, trục ngang là thời gian từ 0 đến 180 giây, trục dọc là số request đã cho qua trong 60 giây vừa rồi, có vạch ngang đứt ở mức 100. Đường đỏ (đếm theo phút cố định) vọt lên 200 ngay sau giây 60 và giữ gần 200 tới khoảng giây 118. Đường vàng (sliding window log) dừng đúng ở 100. Đường xanh (sliding window counter) lên khoảng 110, hơi vượt vạch 100.
Hình 2. Số request đã được cho qua trong 60 giây vừa rồi, tại từng thời điểm. Đếm theo phút cố định để lọt 200; sliding window log giữ đúng 100; sliding window counter vượt nhẹ vì kịch bản cố tình phá giả định của nó.

Dòng “nhiều nhất trong 60 giây” được tính bằng chính một cửa sổ trượt: hàm worst_60s dùng đúng kỹ thuật hai con trỏ của bài 2, chỉ là trên dòng thời gian. Cách đếm theo phút để lọt 200 request trong một khoảng 60 giây, đúng gấp đôi giới hạn. Sliding window log không bao giờ vượt 100.

Sliding window counter vượt lên 111, cao hơn nhiều so với con số 0,003% của Cloudflare. Hai kết quả không mâu thuẫn. Cách ước lượng hai con số giả định rằng request của phút trước rải đều trong phút đó, và kịch bản ở đây cố tình phá giả định ấy bằng cách dồn hết vào 5 giây cuối phút. Với lưu lượng thật của hàng triệu người, request rải đều hơn nhiều, nên ước lượng gần như luôn đúng. Đó là lý do cửa nhập OTP, nơi kẻ tấn công chủ động dồn request, nên dùng cách chính xác.

Bạn có thể đổi kịch bản trong biến requests, chẳng hạn rải 240 request đều trong 2 phút, để thấy ba đường gần như trùng nhau.

Một ý tưởng, nhiều tầng

Cửa sổ trượt dạy một thói quen đáng giá: khi câu hỏi lặp lại trên dữ liệu gần như giống hệt lần trước, đừng tính lại từ đầu, chỉ cập nhật phần đã thay đổi. Trên dãy số, nó biến O(n⋅k)O(n \cdot k) thành O(n)O(n). Trên dòng thời gian, nó biến một quy tắc có lỗ hổng thành một quy tắc đúng với mọi khoảng 60 giây.

Phần system design thêm một bài học khác: thuật toán chính xác nhất chưa chắc là lựa chọn đúng. Cloudflare chọn một phép ước lượng hai con số vì ở quy mô của họ, bộ nhớ và số lệnh mỗi request quan trọng hơn sai lệch vài phần nghìn phần trăm. Một cửa nhập OTP thì ngược lại. Biết mình đang đổi cái gì lấy cái gì, đó mới là phần khó.

Lần tới khi điện thoại báo “thử lại sau 1 phút”, bạn sẽ biết phía sau là một ô cửa sổ dài 60 giây đang trượt, và mã của bạn vừa chạm vào mép của nó.

Phát video: Video: Sliding window: vì sao sai OTP 5 lần bị khóa 1 phút?
Video: Sliding window: vì sao sai OTP 5 lần bị khóa 1 phút?

Tài liệu tham khảo

  1. [1]M. Nottingham và R. Fielding. RFC 6585: Additional HTTP Status Codes (mục 4: 429 Too Many Requests). IETF, 2012.
  2. [2]How we built rate limiting capable of scaling to millions of domains. Cloudflare Blog, 2017.
  3. [3]Paul Tarjan. Scaling your API with rate limiters. Stripe Blog, 2017.
  4. [4]Redis Sorted Sets. Redis Documentation.
  5. [5]LeetCode 3: Longest Substring Without Repeating Characters. LeetCode.