Cấu trúc dữ liệu và Giải thuật Bài 98: Các thuật toán Rate Limiting (Token Bucket, Leaky Bucket, Sliding Window) bảo vệ API Gateway.

Khi bạn thiết kế kiến trúc Microservices cho một nền tảng E-commerce như Hasaki, toàn bộ giao thông (traffic) từ Mobile App và Web sẽ đổ dồn vào một chốt chặn duy nhất: API Gateway. Nếu không có cơ chế tự vệ, một cuộc tấn công DDoS với hàng triệu request mỗi giây, hoặc một đoạn script của đối thủ cào dữ liệu (crawling), sẽ lập tức vắt kiệt Connection Pool của Database và đánh sập toàn bộ hệ thống.

Tương tự, với hệ thống AFC của Metro Line 1, dữ liệu quẹt thẻ từ hàng trăm cổng Turnstile truyền về máy chủ trung tâm cũng cần được điều tiết để tránh gây quá tải cho các Worker xử lý giao dịch.

Để bảo vệ hệ thống, API Gateway sử dụng Rate Limiting (Giới hạn tỷ lệ). Việc từ chối một request (trả về mã lỗi 429 Too Many Requests) tốn chi phí CPU cực thấp so với việc để nó lọt vào hệ thống. Dưới đây là 3 thuật toán kinh điển nhất quyết định xem một luồng dữ liệu nên được cho qua hay bị chặn lại.

1. Token Bucket (Xô mộc bài) - Chấp nhận lưu lượng bùng nổ (Burst Traffic)

Đây là thuật toán phổ biến nhất, được sử dụng làm chuẩn bởi Amazon AWS và Stripe.

• Cơ chế: Hãy tưởng tượng một cái xô có dung tích tối đa là $B$ token. Cứ mỗi $1/R$ giây, hệ thống sẽ nhỏ đúng 1 token vào xô (Tốc độ nạp là $R$ token/giây). Nếu xô đã đầy, token mới sẽ bị vứt bỏ. Khi một Request bay tới, nó phải lấy ra 1 token từ xô để được đi tiếp. Nếu xô rỗng, Request bị từ chối.

• Điểm mạnh: Cho phép Lưu lượng bùng nổ (Burst Traffic). Nếu hệ thống đang vắng khách, xô sẽ tích đầy token. Khi có chiến dịch Flash Sale, người dùng bấm F5 liên tục, hệ thống vẫn cho phép một lượng request lớn (bằng với sức chứa của xô) đi qua ngay lập tức.

• Ứng dụng thực tế: Hoàn hảo cho các User-facing APIs tại Hasaki. Con người thường không thao tác đều đặn mà hay bấm liên tục trong một khoảnh khắc ngắn. Việc cho phép "burst" giúp trải nghiệm UI mượt mà hơn.

2. Leaky Bucket (Xô rỉ nước) - Ép buộc luồng chảy mượt mà (Traffic Shaping)

Thuật toán này là nền tảng của NGINX (module limit_req) và kiến trúc của Shopify. Nó giải quyết bài toán theo hướng ngược lại với Token Bucket.

• Cơ chế: Chiếc xô bây giờ đóng vai trò là một hàng đợi (Queue) chứa các request. Request bay tới sẽ rơi vào xô (nếu xô đầy, request bị văng ra ngoài - từ chối). Dưới đáy xô có một lỗ thủng, các request sẽ "nhỏ giọt" rỉ ra để đi vào server với một tốc độ cố định tuyệt đối (ví dụ: đúng 10 request/giây).

• Điểm mạnh: Giữ cho tải trên server phía sau luôn ở mức ổn định như một đường thẳng (Smooth Traffic). Bất chấp phía trước có bùng nổ 100 request/giây, server phía sau vẫn túc tắc nhận đúng 10 request/giây.

• Ứng dụng thực tế: Cực kỳ phù hợp cho hệ thống tiếp nhận log hoặc đồng bộ dữ liệu như trạm vé AFC Metro. Việc các cổng quẹt thẻ gửi dữ liệu dồn dập vào giờ cao điểm sẽ được "nắn dòng" (Traffic Shaping) thành một luồng chảy đều đặn, bảo vệ Database không bị spike CPU.

3. Sliding Window Log / Counter (Cửa sổ trượt) - Tuyệt đối chính xác

Hai thuật toán "Xô" ở trên xử lý rất tốt trên local memory, nhưng gặp khó khăn khi phải đồng bộ giới hạn trên một cụm Server phân tán (Distributed Gateway). Để kiểm soát chính xác (ví dụ: Mỗi User chỉ được gọi API đúng 50 lần / 1 phút, không hơn không kém), ta dùng Cửa sổ trượt kết hợp với Redis.

• Sliding Window Log: Mỗi khi IP A gửi request, hệ thống lưu Timestamp của request đó vào Redis Sorted Set. Khi nhận request mới, hệ thống xóa tất cả các Timestamp cũ hơn 1 phút trước, đếm số lượng Timestamp còn lại. Nếu $<$ 50 thì cho qua. Nhược điểm: Tốn RAM khổng lồ.

• Sliding Window Counter (Cloudflare, Redis): Tối ưu bằng cách chia thời gian thành các khung cố định (Ví dụ: Phút 01, Phút 02). Thay vì lưu từng Timestamp, ta chỉ lưu số đếm (Counter) của phút trước và phút hiện tại.

  Nếu request đến ở giây thứ 15 của phút hiện tại (tức là 25% thời gian), hệ thống ước lượng số request trong 60 giây qua bằng công thức:

  $$Request = (Counter\_Phút\_Trước \times 75\%) + Counter\_Phút\_Hiện\_Tại$$

  Thuật toán này chỉ tốn đúng 2 con số nguyên trên RAM mà vẫn đảm bảo độ mịn của giới hạn, không bị dồn cục ở ranh giới giữa 2 phút.

4. Triển khai Leaky Bucket mượt mà bằng Golang (Channels & Ticker)

Khác với các ngôn ngữ khác phải dùng Thread Sleep phức tạp, Golang sinh ra là để xử lý Leaky Bucket nhờ sức mạnh của Channels (Hàng đợi) và Tickers.

Đoạn code dưới đây minh họa một hệ thống hứng luồng dữ liệu bùng nổ, nhưng chỉ "rỉ nước" cho Worker xử lý ở một tốc độ cố định.

Go

package main

import (
	"fmt"
	"time"
)

func main() {
	// 1. Cái Xô (Bucket): Một Buffered Channel chứa tối đa 5 requests
	// Đóng vai trò là hàng đợi chứa các request chưa kịp xử lý
	burstLimit := 5
	requests := make(chan int, burstLimit)

	// Mô phỏng 10 Request bắn đến cùng một lúc (Burst Traffic)
	go func() {
		for i := 1; i <= 10; i++ {
			select {
			// Cố gắng thả request vào xô
			case requests <- i:
				fmt.Printf("[Gateway] Nhận Request %d: Đã đưa vào Xô chờ xử lý.\n", i)
			// Nếu xô đầy, từ chối ngay lập tức
			default:
				fmt.Printf("[Gateway] Nhận Request %d: BỊ TỪ CHỐI (429 Too Many Requests) - Xô đã đầy!\n", i)
			}
		}
		close(requests) // Đóng kênh khi không còn request mới
	}()

	// 2. Lỗ Rỉ Nước (Leak): Một Ticker nhịp đúng 200ms một lần
	// Đảm bảo tốc độ xử lý đầu ra luôn ổn định ở mức 5 req/s
	rateLimiter := time.Tick(200 * time.Millisecond)

	// Server đằng sau chỉ việc lấy request ra xử lý dựa trên nhịp của Ticker
	for req := range requests {
		<-rateLimiter // Đứng chờ cho đến khi Ticker 'nhỏ giọt' tiếp theo
		fmt.Printf("[Worker] Đang xử lý Request %d (Luồng chảy mượt mà)\n", req)
	}
	
	fmt.Println("Hoàn thành xử lý tất cả các request lọt vào hệ thống.")
}

Trong kiến trúc Enterprise thực thụ, các thuật toán này hiếm khi được Code cứng (Hardcode) trong Source Code của ứng dụng Backend. Thay vào đó, nó được đẩy toàn bộ ra các công cụ quản lý hạ tầng mạng chuyên dụng, tạo ra sự tách biệt rạch ròi giữa Business Logic và Network Logic.