Hôm nay, mình sẽ giới thiệu các bạn 1 kĩ thuật rất đơn giản nhưng cực kì hay ho:

• 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ơ?

Về cơ bản, Rate Limit rất đơn giản và dễ hiểu.

Rate Limit tức là hạn chế (limit) số lượng request gửi/nhận (rate) đến hệ thống. Ví dụ gấy sợ bạn mập, chỉ cho bạn uống 2 ly trà sữa 1 tuần. Gấu bạn đã sử dụng rate limit để hạn chế số lượng trà sữa bạn tiêu thụ vào, giúp bạn đỡ mập.

Đấy, nói thì nghe đơn gỉản vậy thôi. Trên thực tế, người ta phải sử dụng 1 số thuật toán để đảm bảo chạy nhanh, chính xác mà lại ít tốn bộ nhớ.

Để dễ hiểu, mình sẽ dùng trà sữa và gấu để làm ví dụ cho các thuật toán nhé. Hãy tưởng tượng 1 ly/giọt trà sữa là 1 request tới server, gấu bạn là thuật toán Rate Limit để ngăn bạn uống quá nhiều trà sữa.

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

Tên tiếng Việt các thuật toán thì mình không rõ nên mình dịch bựa tạm, bạn nào biết tên chính thức thì comment hộ để mình update nhé.

Những thuật toán phổ biến thường dùng để rate limit bao gồm:

Thuật toán Cái Xô

Leaky bucket (Xô Lủng từa lưa): Gấu bạn không muốn bạn uống nhiều, nên đổ hết trà sữa vào 1 cái xô rồi đục lỗ cho lủng. Dù bạn có mua vài chục ly nhưng đều phải đổ vào xô, mỗi ngày chỉ chảy ra tầm 1 ly. Bạn chỉ được uống trà chảy ra từ xô.

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

 

Token Bucket (Xô Đựng Token)

Thay vì bỏ trà sữa vào xô, gấu bạn sẽ bỏ vào xô mỗi ngày 60 Token. Nếu uống trà không đường bạn sẽ mua được 4 ly, còn uống trân châu đường đen kem cheese thì chỉ được 1 ly.

Tới hết ngày, nếu hết token, gấu bạn sẽ refill thêm. Cách này đảm bảo 1 ngày bạn chỉ uống tối đa 60 Token.

Trên thực tế, có nhiều request sẽ chạy lâu hơn, tốn nhiều tài nguyên hơn (tạo report, lưu nhiều dữ liệu). Nếu dùng Xô Lủng Từa Lua, ta chỉ đảm bảo được số lượng request tới server. Với thuật toán này, thuật toán tốn tài nguyên hơn sẽ cần nhiều token hơn, ta có thể dễ dàng control lượng tải tới server.

 

Thuật toán Cửa Sổ

Thay vì dùng xô, các thuật toán này dựa theo 1 khoản thời gian (timing window) để limit số lượng request.

Fixed window (Cửa sổ cứng ngắt)

Giờ không mua xô nữa, gấu bạn quyết định là giờ 1 tuần bạn chỉ được uống tối đa 3 ly. Một tuần (tính từ 0h sáng thứ 2 tới 12h tối CN) này chính là fixed window, limit là 3 ly.

 

Thuật toán này dễ hiểu, dễ code, các hệ thống lớn khi cung cấp API cũng hay ra limit 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 limit.

Ví dụ, gấu bạn ra limit này vì muốn bạn uống 2 ngày 1 ly. Tuy nhiên bạn quá máu nên đợi 11h30 tối CN uống 3 ly, sau đó 1h sáng thứ 2 uống thêm 3 ly nữa!

Vậy là trong 2 tiếng bạn uống 6 ly, đường lên, nhầm, lên đường cmn nó luôn!

 

Do vậy, người ta thường dùng Sliding Window Log / Sliding Window nếu muốn hạn chế điều trên.

Sliding Window Log

Thay vì dùng thời gian fixed, gấu bạn quyết định thay đổi thuật toán. Giờ đây, khi bạn uống tà tữa, gấu sẽ ghi log lại. Sau đó, gấu tính thời gian 1 tuần trở về trước tính từ lúc bạn uống.

Giả sử bạn uống 1 ly trà sữa vào 12h trưa thứ 4 tuần này, gấu sẽ tra log từ 12h trưa thứ 4 tuần trước đến 12h trưa thứ tư 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

Sau đó, gấu sẽ đếm trong khoản thời gian này, nếu bạn uống ít hơn 3 ly thì mới cho bạn uống, còn không thì … gấu uống (Tin mình đi, bọn con gái rất chi li và kĩ mấy thứ này!)

Cách này đảm bảo được số lượng trà sữa bạn nốc vào người trong 1 tuần không vượt quá 3 ly. Nếu bạn nốc hết 3 ly cùng lúc, bạn sẽ phải chờ … đúng 7 ngày sau mới được hớp 1 giọt trà sữa.

Cách này rất chính xác, tuy nhiên, nó cũng đi kèm 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 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. Lưu trữ và query mòn râu luôn!

Sliding Window

Sliding Window là một thuật toán cải tiến từ Sliding Window Log. Ta đổ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 gấu. Do gấu thấy log mỗi lầ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 ly trà sữa.

Giả sử ở tuần 1 bạn uống 3 ly. Vào 12h trưa thứ 4 tuần thứ 2, bạn định uống thêm 1 ly. Sliding Window sẽ là từ 12h trưa thứ 4 tuần trước đến 12h thứ 4 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ó 4.5 ngày trong tuần 1 (Chiều thứ 4 đến tối CN), 2.5 ngày trong tuần 2 (Sáng thứ 2 đến trưa thứ 4).

Do không có log cụ thể, ta sẽ ước đoán lượng trà sữa 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 ly trà sữa, chưa uống thêm được.

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

Tạm kết

Bài học rút ra là gì?? Đó là nếu muốn uống trà sữa thoải mái thì đừng nên có gấu, hoặc rủ gấu uống chung, hoặc lén lén uống mà đừng cho gấu biết!

Đùa thôi, bài học rút ra là có những thứ tưởng chừng như đơn giản, đến khi đi sâu vào tìm hiểu cũng khá khoai và phức tạp đấy hihi.

Nếu chưa hiểu kĩ, các bạn có thể đọc lại và đọc 2 bài này nha. Họ có cả hình minh hoạ, code example và giải thích dễ hiểu hơn mình!

• https://cloud.google.com/solutions/rate-limiting-strategies-techniques#techniques-enforcing-rate-limits
• https://hechao.li/2018/06/25/Rate-Limiter-Part1

Ở phần 2 mình sẽ hướng dẫn các bạn các trang lớn dùng Rate Limiting như thế nào, làm sao để áp dụng Rate Limit vào hệ thống của bạn nha!