Cách đây không lâu, mình và team mình có phát triển 1 bộ RESTful API để 1 số dịch vụ bên thứ 3 gọi vào.

Mọi chuyện diễn ra suông sẻ như bao dự án đang được phát triển khác, cho đến 1 ngày, vào buổi daily meeting, cấp trên đã hỏi về việc làm thế nào để giới hạn lại số lượng truy cập vào API mỗi phút, giây, giờ để tránh tình trạng bị spam cháy máy. Và lùm xùm lùm xùm trong buổi họp đó, mình đã biết được 1 keyword mới, đó là “Rate Limiter” và mình sẽ là người implement chức năng này. Ngon, có cái mới để vọc

Rate Limiter là gì

In computer networks, rate limiting is used to control the rate of requests sent or received by a network interface controller. It can be used to prevent DoS attacks^[1] and limit web scraping.^[2]

https://en.wikipedia.org/wiki/Rate_limiting

Hiểu đơn giản là Rate Limiter là hệ thống kiểm soát số lượng request vào hệ thống của mình. Bằng cách giới hạn số lượng request trong 1 khoảng thời gian, nhằm tránh đón nhận số lượng request ồ ạt, hoặc cơ bản là bạn chỉ không muốn phía client sử dụng quá số lượng bạn cho phép họ sử dụng.

Có rất nhiều thuật toán để xử lý việc cho request vào hay không, một số có thể kể đến như:

• Token Bucket
• Leaking bucket
• Sliding window log
• Sliding window counter
• …

Sau một hồi lăn lộn trên internet thì mình thấy nếu chỉ làm ở mức cơ bản thôi thì không khó, mình quyết định chọn Token Bucket Algorithm để làm thuật toán chính để xử lý vì nó dễ implement.

Giải thích Token algorithm một cách dễ hiểu nhất là:
Giả sử bạn tham gia vào 1 buổi ăn miễn phí, để lấy 1 suất đồ ăn bạn cần phải có 1 vé, quy định của BTC là người chỉ được lấy 5 phần ăn tương ứng với 5 vé mỗi 1 giờ, sau 1 khoản thời gian sau bạn sẽ có thể lấy thêm vé và lấy đồ ăn tiếp tục (với rate là 60 phút / 5 vé = mỗi 12 phút bạn sẽ có 1 vé). Trong khoảng thời gian bạn dùng hết 5 vé, thì nếu bạn có nài nỉ van xin cũng không thể lấy được phần ăn đâu, từ từ đê.

Xác định một số thứ

Đầu tiên, mình sẽ cần xem xét mình sẽ limit lại dựa trên gì, IP, host hay client id.
A: Ở dự án của mình mình sẽ chọn client id

Thứ 2, mình sẽ implement nó ở đâu?
A: Mình sẽ implement ở backend và ngay trong con application của mình luôn.

Thứ 3, mình sẽ xác định các API nào cần limit lại (mình sẽ gọi nó là rule) và những thông tin này sẽ lưu ở đâu?
A: Mình sẽ lưu nó ở database và mình sẽ đọc và ghi vào memory ở lần khởi động app.

Thứ 4, các thông tin limit của client (mình sẽ gọi nó là limit data) mình sẽ lưu trữ ở đâu?
A: Mình sẽ lưu ở database, khi khởi động app, mình sẽ chui xuống đọc và lưu trên memory để truy nhanh hơn, đồng thời sẽ có 1 task background cập nhật xuống DB mỗi 5/10 phút.

Thứ 5, nếu client đã hết token gọi tới thì sao?
A: Khi client đã hết token và vẫn gọi request thì trả ngay mã lỗi 429 Too Many Requests.

Yêu cầu thêm từ dự án:

• Do yêu cầu dự án nên có sự khác biệt 1 tý, đó là chia theo API type, mình sẽ có 2 type là HEAVY và LIGHT. Mỗi type sẽ có 1 hoặc nhiều API.
• Các API thuộc HEAVY chỉ có thể gửi 5 request mỗi giây.
• Các API thuộc LIGHT chỉ có thể gửi 20 request mỗi giây.
• Và mỗi API sẽ có token độc lập. Tức là API A thuộc type HEAVY nếu dùng hết 5 request trên giây thì khi chạy qua dùng API B (cũng thuộc type HEAVY) vẫn bình thường vì API B vẫn còn 5 token.

Tiến hành

Đầu tiên mình define ra 1 rule cơ bản như sau:

endpoint: /api/v69/booking
method: POST
type: HEAVY
request per second: 5 


endpoint: /api/v69/booking/list
method: POST
type: LIGHT
request per second: 20

rule này mình sẽ lưu ở dưới database và load vào memory khi start app.

Đồng thời mình sẽ define ra bộ limit data, mình sẽ dùng nó để track số lượng token còn lại luôn, nó sẽ có dạng thế này:

client ponk: [
     { endpoint: /api/v69/booking, method: POST, type: HEAVY, bucket_size: 5, tokens: 5, last_request_time_millis: 1000000000 },
     { endpoint: /api/v69/booking/list, method: POST, type: LIGHT, bucket_size: 20, tokens: 20, last_request_time_millis: 1000000000 }
]

Mình sẽ sử dụng thông tin này lưu trong DB và lưu trong memory, chủ yếu sẽ truy cập qua memory cho nhanh và bớt stress database lại. (Dĩ nhiên đây không phải cấu trúc thực tế rồi)

Tiếp theo, câu hỏi là “làm sao để mình chặn cái request để kiểm tra còn đủ token không mới cho vào?”
Thì app của mình được viết với Spring Boot, nên mình có thể tạo 1 class OncePerRequestFilter để làm middleware, nó đứng ở giữa Dispatcher và Bussiness method.

OK, vậy là cơ bản đã đủ, giờ mình bắt đầu “đánh chặn” thôi.

Khi request tới, mình sẽ tìm xem request đó đang gọi tới endpoint nào, method gì, type gì? Có trong rule không?

Khi trả lời được những thông tin trên, mình sẽ chui vào lấy ra limit data, ví dụ mình sẽ lấy được:

client ponk: [
     { endpoint: /api/v69/booking, method: POST, type: HEAVY, bucket_size: 5, tokens: 5, last_request_time_millis: 1000000000 }
]

Ok, đầu tiên mình sẽ kiểm tra ông này còn token không… Ồ còn 5 token, bây giờ trừ 1 token, cập nhật lại last_request_time_millis cho ổng rồi tiến hành xử lý logic và trả về response như bình thường. Và đây là data sau request đó.

client ponk: [
     { endpoint: /api/v69/booking, method: POST, type: HEAVY, bucket_size: 5, tokens: 4, last_request_time_millis: 16969696969 }
]

Ví dụ giờ ổng gọi hết token rồi thì làm sao để phân phát token cho ổng?

Còn nhớ ảnh minh họa token bucket algorithm ở trên chứ, nó có 1 đoạn gọi là “Refill”, đó chính là giai đoạn cập nhật lại số token, và nó sẽ được thực hiện trước khi kiểm tra có đủ số lượng token không.

Đoạn refill mình sẽ có 1 hàm cơ bản thế này

public int refill (long lastRequestMillis, int maxBucketSize, int refillRate) {
     long currentMillis = System.getCurrentMillis();
     int tokenWillRefill = (currentMillis - lastRequestMillis) / 1_000L * refillRate;
     return Math.min(maxBucketSize, tokenWillRefill);
}

Hàm này nhận vào 3 tham số lần lượt là: thời gian (milli giây) lần request cuối cùng, số lượng token tối đa trong bucket (ở đây là 5 do mình chỉ tính trên giây và số lượng tối đa request mỗi giây là 5) và refill rate.

Việc mình chia thêm 1000 là để chuyển từ milli sang giây rồi tính.

Nói về refill rate thì giải thích dễ hiểu nhất nó là 1 biến để xác định mỗi 1 giây sẽ refill lại bao nhiêu token (token/second).

Ví dụ, mỗi giây mình muốn refill 5 request mình sẽ truyền vào là 5. Lúc này bài toán sẽ là:

currentMillis = 2000
lastRequestMillis = 1000

( 2000 - 1000 ) / 1000L * 5 (refill 5 token mỗi giây)
=  5 token

Bài giây nhỏ quá, giờ thử sang phút nhé

currentMillis = 120000
lastRequestMillis = 60000

request per min = 5
refillRate = 5/60 = 0.0833333 token/second

( 120000 - 60000 ) / 1000L *  0.0833333 (refill  0.0833333 token mỗi giây)
=  ~5 token

Giá trị mà hàm refill trả về sẽ được cập nhật vào biến tokens từ limit data. Trường hợp mà hàm refill trả về 0, thì mình sẽ lập tức trả về mã lỗi 429 ngay do ông này spam quá.

Tóm lại, flow khi 1 request đến sẽ là:

• Đi vào filter
• Kiểm tra endpoint đang được request đến có trong rule không?
• Nếu có thì refill token
• Sau khi refill kiểm tra đủ token không? Nếu không thì trả mã lỗi 429
• Nếu đủ thì cập nhật số token còn lại, thời gian request mới nhất. Sau đó tiếp tục gọi tới chỗ thực hiện logic và trả về response như bình thường

Kết quả

Nói nghe dễ thế chứ lúc mình làm đập đi xây lại vài lần mới ra kết quả như trên đó

Hệ thống của mình chạy ngon, ổn, do handle thông tin chủ yếu trên memory nên khá nhanh, track trên client id thì ít tốn dung lượng hơn nữa (do scope của mình tầm 4 5 client khác nhau thôi)

Có 1 số lúc ở giờ cao điểm nhờ nó mà server để dành được nhiều resource hơn để tập trung vào các request đến từ khách hàng.

Nhưng khoan…

Dù chạy ngon, chạy ổn, tuy nhiên nó đang dính tới 1 vấn đề lớn đó là: Khả năng scale.

Mình hoàn toàn không thể đồng bộ số token còn lại của client nếu có 2 instance trở lên cùng chạy (trừ khi có load balancer đằng trước và dùng sticky session, nhưng mà chuối lắm, thề).

Cho nên tựa đề mới có từ “chưa tốt”.

Chưa kể đến việc implement trên con application cũng khiến nó tốn thêm tài nguyên để quản lý và xử lý rate limited, mặc dù performance hiện tại đang khá tốt nhưng thử tưởng tượng cỡ hơn 1000 – 2000 request cùng lúc xem.

Mình sẽ sửa lại gì nếu cho mình đi lại

Đầu tiên mình sẽ tách biệt Rate Limiter này ra làm hệ thống riêng bữa ở giữa client và API servers để có thể mở rộng thêm API server và không chiếm tài nguyên của API server như hiện tại mình đang làm.

Các thành phần trước đó mình sẽ giữ như cũ, tuy nhiên mình tách phần limit data sang Redis vì một số yếu tố như:

• Nếu sau này có mở thêm Rate Limiter thì cũng không thành vấn đề
• Redis đóng vai trò lưu trữ dưới dạng cache, mà cache thì lưu ở memory nên mình có thể lấy data ra khá nhanh, không phụ thuộc nặng nề vô disk.
• Cuối cùng là để … vọc Redis

Ý tưởng này được dựa trên System Design Interview của bác Alex Xu, nên mình follow theo hướng xử lý này, và đây là mô hình thiết kế mà mình sẽ muốn hướng theo:

Cảm ơn đọc giả đã lướt qua bài viết đầu tiên của mình