Thuật toán Rate Limiting là gì?

Hiện tại hầu hết những hệ thống lớn trên thế giới đều cung cấp Rate Liming cả. Nhưng mà ít ai để ý đến thuật toán đằng sau công nghệ đó như thế nào.

• Kĩ thuật này được 69.96% các hệ thống từ lớn đến nhỏ như Google, Facebook, LinkedIn, Youtube áp dụng
• Kĩ thuật này giúp chúng ta ngăn chặn DDOS, chống spam, giữ cho hệ thống hoạt động trơn tru.

Thế nhưng, chúng ta ít người biết đến “người hùng”  thầm lặng này. Kĩ thuật này có tên là Rate Limiting.

Rate Limiting là cái gì cơ?

Giả sử như hệ thống của chúng ta nhận được hàng nghìn request nhưng mà trong số đó chỉ xử lí được trăm request/s chẳng hạn, và số request còn lại thì bị lỗi (do CPU hệ thống đang quá tải không thể xử lí được).

Để giải quyết được vấn đề này thì cơ chế Rate Limiting đã ra đời. Mục đích của nó chỉ cho phép nhận 1 số lượng request nhất định trong 1 đơn vị thời gian. Nếu quá sẽ trả về response lỗi.

1 số ví dụ hay gặp trong Rate Limiting như:

• Mỗi người dùng chúng ta chỉ cho phép gửi 100 request/s. Nếu vượt quá thì sẽ trả về response lỗi.
• Mỗi người dùng chỉ cho phép nhập sai thẻ credit 3 lần trong 1 ngày
• Mỗi địa chỉ IP chỉ có thể tạo được 2 account trong 1 ngày.

Để dễ hiểu mình sẽ lấy ví dụ như khi bạn uống bia nhé 😉 Giả sử 1 chai bia là một request tới server thì tửu lượng 6 chai Tiger Nâu độ cồn 5% của bạn là thuật toán Rate Limit giúp bạn không sập quá nặng 😄.

Về cơ bản thì rate limiter sẽ cho phép gửi bao nhiêu request trong 1 khoảng thời gian nào đó. Nếu vượt quá sẽ bị block lại.

Khuyến cáo: Hình ảnh minh họa thôi nha. Mùa dịch nhìn có thèm cũng không được ra quán nhậu nha :)))

Một số thuật toán hay dùng?

Vì tên mấy thuật toán dịch ra mình thấy hơi chuối nên mình để nguyên, anh em nào biết dịch sao cho hay thì comment ở dưới nha.

Những thuật toán thường được áp dụng để rate limit bao gồm:

Bucket Algorithm

Leaky bucket: Vào một ngày bạn có bồ (giả định) và cô ấy không muốn bạn uống nhiều, nên đổ hết 8, 9 chai vào 1 cái xô rồi đục lỗ cho nó lủng. Dù bạn có mua một két để luyện thành tiên tửu nhưng đều phải đổ vào xô, mỗi ngày chỉ chảy ra tầm 1 chai. Và bạn chỉ được uống bia chảy ra từ xô.

Cách này giúp cho hệ thống không sợ bị quá tải khi có nhiều người truy cập, vì cái xô sẽ chặn bớt.

Token Bucket

Thay vì đổ bia vào xô, bồ bạn sẽ bỏ vào xô mỗi ngày 40 Token. Nếu bạn uống Tiger bạn sẽ mua được 2 chai, còn uống Corona thì chỉ được 1 chai.

Hết ngày, dù còn hay hết token, bồ bạn sẽ bỏ vào cho đủ khẩu phần 50 Token mỗi ngày. Cách này đảm bảo 1 ngày bạn chỉ mua bia tối đa 40 Token.

Trong thực tế, có nhiều request sẽ tốn nhiều tài nguyên hơn, chạy lâu hơn (tạo report, lưu nhiều dữ liệu). Nếu dùng Leaky Bucket, ta chỉ đảm bảo được số lượng request tới server. Với thuật toán này, cái gì tốn nhiều tài nguyên hơn sẽ cần nhiều token hơn, ta có thể dễ dàng kiểm soát lượng tải tới server.

Window Algorithm

Thay vì dùng xô để hạn chế lưu lượng, những thuật toán này phân chia khoảng thời gian (timing window) để hạn chế số lượng request.

Fixed window

Thấy xô dùng lâu ngày thấy nhàm chán, gấu bạn quyết định giờ 1 tuần bạn chỉ được uống tối đa 3 chai mỗi chai 20 token. Một tuần (tính từ 0h sáng thứ 2 tới 24h đêm CN) này chính là fixed window, tối đa là 3 chai.

Cách này dễ hiểu, dễ code, các hệ thống lớn khi cung cấp API cũng hay ra giới hạn như thế này. Tuy nhiên, nó có 1 điểm yếu là… có thể bị lợi dụng để burst số lượng request vượt giới hạn.

Ví dụ, gấu bạn ra mức giới hạn này vì muốn bạn uống 2 ngày 1 chai. Tuy nhiên đêm đó bạn lên cơn thèm nên đợi 11h30 tối CN uống 3 chai, sau đó 1h sáng thứ 2 bơm thêm 3 chai nữa (tiên tửu)!

Vậy là trong canh Tý bạn uống 6 chai, bạn sập như chưa từng luôn!

Do vậy, để tránh bọn ranh ma người ta đã dùng Sliding Window Log / Sliding Window để hạn chế trường hợp trên.

Sliding Window Log

Thay vì dùng fixed window, gấu bạn quyết định thay đổi thuật toán. Giờ đây, khi bạn bơm alcohol, gấu sẽ ghi log lại. Sau đó, gấu bắt đầu tính từ lần đó đến đúng một tuần sau.

Ví dụ vào một buổi trưa nóng nực 11h thứ 2 bạn khui một chai bia mát lạnh để giải nhiệt cuộc sống, gấu sẽ tra log từ 11h trưa thứ 2 tuần trước đến 11h trưa thứ 2 tuần này. Đây chính là Sliding Window.

Tuần 1         - Tuần 2

2 3 4 5 6 7 CN - 2 3 4 5 6 7 CN

Nếu gấu đếm trong khoản thời gian này, bạn uống ít hơn 3 chai thì sẽ vui vẻ khui cho bạn uống, còn không … gấu vẫn sẽ vui cười và khui nhưng là cho nó uống (còn bạn thì nhìn thèm vãi chưởng).

Cách này đảm bảo lượng cồn bạn nạp vào người trong 1 tuần không vượt quá 3 chai. Nếu bạn nốc liền 3 chai cùng lúc, bạn sẽ phải nhịn … đúng 7 ngày sau mới được liếm nhẹ được miếng sinh tố lúa mạch :))

Cách này rất chính xác, tuy nhiên, nó vẫn có 1 số khuyết điểm:

• Tốn khá nhiều bộ nhớ vì phải log toàn bộ request,
• Tốn tài nguyên vì phải log ở mỗi lần request
• Chạy có thể sẽ chậm, vì mỗi lần có request, ta phải query đếm lượng request trong 1 khoản thời gian nhất định để xem có tiếp nhận request hay không
• Hãy tưởng tượng hệ thống tầm 1 triệu người dùng, mỗi ngày họ gửi 1000 request là ta phải log gần 1 tỷ event mỗi ngày. Toang rồi ông giáo ạ!

Sliding Window (Rolling Window)

Sliding Window là sự cải tiến từ Sliding Window Log. Ta sẽ đánh đổi độ chính xác lấy tốc độ và bộ nhớ (lưu ít hơn ,query ít hơn). Ta không log trên mỗi request, mà chỉ lưu lại số lượng trên mỗi khoản thời gian.

Quay lại với cô người yêu ví dụ nào. Do gấu thấy ghi lại mỗi lần bạn uống mệt qué nên bây giờ, gấu chỉ log 1 lần vào Chủ Nhật là tuần đó bạn uống bao nhiêu chai bia.

Ví dụ ở tuần 1 bạn uống 3 chai. Vào 11h trưa thứ 2 tuần thứ 2, bạn định uống thêm 1 chai. Sliding Window sẽ là từ 11h trưa tuần thứ 2 tuần trước đến 11h thứ 2 tuần này.

Tuần 1           Tuần 2

2 3 4 5 6 7 CN - 2 3 4 5 6 7 CN

Sliding window này có 6 ngày rưỡi trong tuần thứ 1 (trưa thứ 2 đến tối CN), nửa ngày trong tuần 2 (sáng thứ 2).

Do không có log cụ thể, ta sẽ ước đoán lượng bia bạn uống trong khoảng thời gian này bằng công thức sau.

Số uống tuần 1 * (Ngày trong tuần 1 / 7) + Số uống tuần 2 * (Ngày trong tuần 2 / 7)

3 * (4.5/7) + 1 * (2.5/7) = 2.285

Tức là trong khoảng 7 ngày này bạn đã uống tầm 2.285 chai bia, chưa uống thêm được.

Có thể là không chính xác lắm, vì số lượng bia bạn uống sẽ không trải dài đều theo tuần. Tuy vậy, nó không bị khai thác lỗ hổng như fixed window, lại tốn ít tài nguyên và bộ nhớ hơn, nên được sử dụng tương đối nhiều.

 

Có thể bạn quan tâm:

• Hướng dẫn giải bài toán phân bổ số lượng (thuật toán chia kẹo) trong sqlserver
• Một số thuật toán sắp xếp cơ bản. Quick Sort có phải là thuật toán sắp xếp nhanh nhất?
• Thuật toán xếp hạng bài viết đang hot, thịnh hành như Reddit và Hacker News hoạt động thế nào?

Xem thêm IT Jobs Developer hấp dẫn tại TopDev