An alternative approach to rate limiting

Figma · 2017 · 1. Khởi đầu · Độ khó: Dễ — bài gốc

Bối cảnh

Figma bị tấn công spam lần đầu: kẻ xấu dùng tính năng mời vào tài liệu để gửi email hàng loạt. Nếu không phát hiện kịp thì chi phí gửi email tăng vọt và uy tín người gửi email (sender reputation) bị ảnh hưởng.
Rate limiter tự viết (trước đó bị đùa là "viết cho vui") đã phát hiện được.
Yêu cầu: lưu dữ liệu ở ngoài (nhiều máy web dùng chung), không làm chậm request, tự dọn dữ liệu cũ, chính xác, ít bộ nhớ. Chọn Redis (thay vì Postgres) vì nhanh và có sẵn cơ chế hết hạn.

Thay đổi chính

So sánh ba thuật toán quen thuộc:

Thuật toán	Ưu	Nhược (theo Figma)
Token bucket	Ít bộ nhớ	Đọc rồi mới ghi nên không nguyên tử, có race khi phân tán; sửa bằng lock (chậm) hoặc Lua (thêm một ngôn ngữ)
Fixed window counter	Nguyên tử (`INCR`), ít bộ nhớ	Ở ranh giới hai cửa sổ có thể lọt gấp 2 lần giới hạn
Sliding window log	Chính xác	Lưu mỗi request một giá trị: ví dụ 500 req/ngày × 10.000 user ≈ 20 MB

Giải pháp: sliding window counter, lai giữa hai cách cuối:

chia cửa sổ giới hạn thành 60 counter nhỏ (giới hạn theo giờ thì mỗi counter một phút) trong một Redis hash (hash nhỏ được Redis lưu rất gọn);
mỗi request tăng counter hiện tại, đặt hạn cho hash, rồi cộng các counter;
cùng ví dụ trên chỉ còn ≈ 2,4 MB.

Sai số tối đa 59 giây. Figma chọn hơi gắt hơn: cộng thêm một phút.

Phản ứng với kẻ vượt giới hạn: lúc đầu trả 429, kẻ tấn công thấy vậy liền tạo tài khoản mới. Figma chuyển sang shadow ban: vẫn trả 200 nhưng âm thầm không gửi lời mời.

Vì sao

Bảo vệ availability của web app trước các đợt request dồn dập, và chặn lạm dụng tính năng tốn tiền (email).

Bài học cho SWE

Chọn thuật toán theo các ràng buộc cụ thể: nguyên tử trong môi trường phân tán, bộ nhớ, độ chính xác.
Thao tác ghi-rồi-đọc nguyên tử (INCR) an toàn hơn đọc-rồi-ghi khi nhiều process dùng chung trạng thái.
Tín hiệu từ chối (429) cũng là thông tin cho kẻ tấn công.
Giới hạn tốc độ là tuyến phòng thủ đầu tiên trước tải dồn dập, cùng họ với semaphore và back-pressure trong Hot partition và thundering herd.