Khám phá Nguyên lý và Thực thi Thuật toán Giới hạn Lưu lượng Token Bucket
Trong kỷ nguyên internet hiện nay, khi số lượng người dùng và yêu cầu không ngừng tăng lên, hiệu suất và ổn định hệ thống đối mặt với những thách thức lớn. Thuật toán giới hạn lưu lượng (rate limiting) như một giải pháp quan trọng đảm bảo sự ổn định của hệ thống, được áp dụng rộng rãi trong nhiều dịch vụ và ứng dụng. Mục đích cốt lõi của giới hạn lưu lượng là kiểm soát số lượng yêu cầu trong một khoảng thời gian nhất định, duy trì khả năng sẵn sàng và ổn định của hệ thống, ngăn chặn tình trạng hệ thống chạy chậm hoặc sụp đổ do lưu lượng đột ngột tăng cao.
So sánh các thuật toán giới hạn lưu lượng phổ biến
Có bốn thuật toán giới hạn lưu lượng chính:
Thuật toán Token Bucket
- Nguyên lý: Thuật toán Token Bucket là một phương pháp giới hạn lưu lượng dựa trên token, duy trì một thùng chứa token có dung lượng cố định, thêm token vào thùng với tốc độ cố định. Khi có yêu cầu đến, tiêu thụ một token. Nếu thùng không đủ token, yêu cầu sẽ bị từ chối.
- Ưu điểm: Giới hạn lưu lượng mượt mà, có thể xử lý lưu lượng đột ngột; kiểm soát linh hoạt tốc độ lưu lượng.
Đối với lưu lượng đột ngột, cần dung lượng thùng token đủ lớn để xử lý, nếu không có thể xảy ra tình trạng từ chối một phần yêu cầu.
Thuật toán Leaky Bucket
- Nguyên lý: Thuật toán Leaky Bucket là phương pháp giới hạn lưu lượng dựa trên thùng rò rỉ, duy trì một thùng chứa có dung lượng cố định, rò rỉ nước với tốc độ cố định. Khi có yêu cầu đến, lượng nước trong thùng tăng lên. Nếu thùng đã đầy, yêu cầu sẽ bị từ chối.
- Ưu điểm: Giới hạn lưu lượng mượt mà, có thể hạn chế tốc độ xử lý yêu cầu.
- Nhược điểm: Đối với lưu lượng đột ngột, có thể xảy ra mất kết quả yêu cầu trong thời gian ngắn.
Thuật toán Fixed Window
- Nguyên lý: Thuật toán Fixed Window là phương pháp giới hạn lưu lượng đơn giản, thống kê số lượng yêu cầu trong đơn vị thời gian, khi đạt đến ngưỡng đã đặt sẽ từ chối các yêu cầu tiếp theo.
- Ưu điểm: Đơn giản, dễ triển khai, phù hợp với kịch bản lưu lượng cố định.
- Nhược điểm: Không thể xử lý lưu lượng đột ngột, có thể dẫn đến giảm hiệu suất hoặc dịch vụ không sẵn sàng.
Thuật toán Funnel
- Nguyên lý: Thuật toán Funnel là phương pháp giới hạn lưu lượng dựa trên phễu, mô phỏng quá trình của một cái phễu, yêu cầu vào phễu sẽ được kiểm soát tốc độ xử lý dựa trên dung tích và tốc độ của phễu.
- Ưu điểm: Có thể điều chỉnh linh hoạt dung tích và tốc độ phễu, thích ứng với các tình huống lưu lượng khác nhau.
- Nhược điểm: Tương đối phức tạp, khó khăn trong triển khai và tối ưu.
Thuật toán Token Bucket
Trong kiến trúc microservice, Spring Cloud Gateway đóng vai trò là cổng dịch vụ, chịu trách nhiệm quản lý lưu lượng và phân định tuyến đường. Để tăng cường khả năng giới hạn lưu lượng, Spring Cloud Gateway cung cấp lớp RequestRateLimiterGatewayFilterFactory, tích hợp Redis và sử dụng script Lua để triển khai chiến lược giới hạn Token Bucket hiệu quả.
Trong số nhiều thuật toán giới hạn lưu lượng, thuật toán Token Bucket với những ưu điểm và tính linh hoạt độc đáo đã trở thành giải pháp được ngành công nghiệp áp dụng rộng rãi. Nền tảng dịch vụ dữ liệu "DataAPI" dựa trên khả năng giới hạn sẵn có của Spring Cloud đã thực hiện các tùy chỉnh phát triển và tối ưu hóa thêm.
Ở trên đã giới thiệu ngắn gọn, thuật toán Token Bucket là một thuật toán kiểm soát lưu lượng, dùng để giới hạn số lượng yêu cầu được phép đi qua trong đơn vị thời gian, có thể giới hạn tốc độ yêu cầu một cách mượt mà, ngăn chặn lượng lớn yêu cầu đột ngột gây quá tải cho hệ thống. Dưới đây là nguyên lý cơ bản và quy trình hoạt động của thuật toán Token Bucket:
Thùng chứa Token
"Thùng chứa Token" trong thuật toán giống như một nơi lưu trữ token. Ở mỗi khoảng thời gian cố định (ví dụ mỗi giây), hệ thống sẽ thêm một số lượng nhất định token vào thùng chứa.
Xử lý yêu cầu
Khi một yêu cầu đến, hệ thống sẽ cố gắng lấy một token từ thùng chứa. Nếu thùng chứa đủ token, hệ thống cho phép xử lý yêu cầu đó và lấy đi một token. Nếu thùng chứa không đủ token, hệ thống sẽ từ chối yêu cầu hoặc đưa vào hàng đợi chờ.
Tạo Token
Số lượng token trong thùng chứa sẽ bị giới hạn, không thể tăng vô hạn. Khi thùng chứa đã đầy, sẽ không tạo thêm token mới, token thừa sẽ bị loại bỏ.
Qua quy trình hoạt động trên, thuật toán Token Bucket có thể thực hiện kiểm soát lưu lượng yêu cầu, cho phép hệ thống xử lý yêu cầu với tốc độ ổn định. Thuật toán này phù hợp với các kịch bản cần giới hạn tốc độ yêu cầu, như kiểm soát tần suất gọi API, kiểm soát lưu lượng mạng, v.v.
Tùy chỉnh giới hạn lưu lượng
Bằng cách kế thừa AbstractRateLimiter và ghi đè phương thức isAllowed để thực hiện giới hạn lưu lượng tùy chỉnh.
Bằng cách kế thừa AbstractGatewayFilterFactory và ghi đè phương thức apply để gọi phương thức giới hạn lưu lượng cụ thể.
Phân tích phương thức isAllowed
@Override
@SuppressWarnings("unchecked")
public Mono<Response> isAllowed(String routeId, String id) {
// Kiểm tra khởi tạo
if (!this.initialized.get()) {
throw new IllegalStateException("RedisRateLimiter chưa được khởi tạo");
}
// Bạn muốn cho phép người dùng thực hiện bao nhiêu yêu cầu mỗi giây?
int replenishRate = 0;
// Bạn muốn cho phép bao nhiêu yêu cầu bùng nột?
int burstCapacity = 0;
// Mỗi yêu cầu cần bao nhiêu token?
int requestedTokens = 1;
final RedisLimitDefinition limitDefinition;
if(LimitListRouteDefinitionLocator.ID_PREFIX.equals(routeId.split(ValidateRequestGlobalFilter.SPLIT)[0])){
limitDefinition = limitConfig.getLimitInfoMap().get(id);
if (ObjectUtils.isEmpty(limitDefinition) ){
throw new IllegalArgumentException("Không tìm thấy cấu hình cho uri " + id);
}
replenishRate = limitDefinition.getReplenishRate();
// Bạn muốn cho phép bao nhiêu yêu cầu bùng nột?
burstCapacity = limitDefinition.getBurstCapacity();
} else{
// Logic tùy chỉnh, chia thành giới hạn theo phút và giây
String[] routeIdArr = routeId.split(ValidateRequestGlobalFilter.SEPARATOR);
if(routeIdArr.length > 1){
replenishRate = Integer.parseInt(routeIdArr[0]);
burstCapacity = replenishRate * 60;
limitDefinition = new RedisLimitDefinition(replenishRate, replenishRate, null, null);
requestedTokens = 60;
} else{
replenishRate = Integer.parseInt(routeIdArr[0]);
burstCapacity = replenishRate;
limitDefinition = new RedisLimitDefinition(replenishRate, replenishRate, null, null);
requestedTokens = 1;
}
}
try {
List<String> keys = getKeys(id);
// Các đối số cho script LUA. time() trả về thời gian unix theo giây.
List<String> scriptArgs = Arrays.asList(replenishRate + "",
burstCapacity + "", Instant.now().getEpochSecond() + "",
requestedTokens + "");
// allowed, tokens_left = redis.eval(SCRIPT, keys, args)
// Gọi script lua và trả về kết quả
Flux<List<Long>> flux = this.reactiveStringRedisTemplate.execute(this.script, keys,
scriptArgs);
return flux.onErrorResume(throwable -> {
if (log.isDebugEnabled()) {
log.debug("Lỗi khi gọi script giới hạn tốc độ", throwable);
}
return Flux.just(Arrays.asList(1L, -1L));
}).reduce(new ArrayList<Long>(), (longs, l) -> {
longs.addAll(l);
return longs;
}).map(results -> {
boolean allowed = results.get(0) == 1L;
Long tokensLeft = results.get(1);
Response response = new Response(allowed,
getHeaders(limitDefinition, tokensLeft));
if (log.isDebugEnabled()) {
log.debug("response: " + response);
}
return response;
});
}
catch (Exception e) {
/*
* Chúng ta không muốn phụ thuộc vào Redis để cho phép lưu lượng. Đảm bảo đặt
* cảnh báo để bạn biết nếu điều này xảy ra quá nhiều. Tỷ lệ thất bại quan sát được
* của Stripe là 0.01%.
*/
log.error("Lỗi khi xác định xem người dùng có được phép từ redis", e);
}
return Mono.just(new Response(true, getHeaders(limitDefinition, -1L)));
}
Script Lua
Script Lua được tích hợp sẵn trong dịch vụ backend, vị trí như hình dưới:
Phân tích mã script:
-- Dựa trên id duy nhất tạo ra token key và timestamp key
local tokens_key = KEYS[1]
local timestamp_key = KEYS[2]
-- redis.log(redis.LOG_WARNING, "tokens_key " .. tokens_key)
-- Các tham số đầu vào tương ứng, lần lượt là
-- Tốc độ đặt token vào thùng, mỗi giây n token
local rate = tonumber(ARGV[1])
-- Dung lượng tối đa của thùng token
local capacity = tonumber(ARGV[2])
-- Dấu thời gian hiện tại, theo giây
local now = tonumber(ARGV[3])
-- Số lượng token tiêu thụ cho mỗi yêu cầu
local requested = tonumber(ARGV[4])
-- Thời gian để đổ đầy thùng token
local fill_time = capacity/rate
-- Thời gian hết hạn của redis key
local ttl = math.floor(fill_time*2)
--redis.log(redis.LOG_WARNING, "rate " .. ARGV[1])
--redis.log(redis.LOG_WARNING, "capacity " .. ARGV[2])
--redis.log(redis.LOG_WARNING, "now " .. ARGV[3])
--redis.log(redis.LOG_WARNING, "requested " .. ARGV[4])
--redis.log(redis.LOG_WARNING, "filltime " .. fill_time)
--redis.log(redis.LOG_WARNING, "ttl " .. ttl)
-- Các thao tác với last_tokens và last_refreshed ở đây vừa là gán giá trị vừa có tác dụng khởi tạo
-- Lấy số lượng token trong thùng, nếu rỗng, gán dung lượng thùng token
local last_tokens = tonumber(redis.call("get", tokens_key))
if last_tokens == nil then
last_tokens = capacity
end
--redis.log(redis.LOG_WARNING, "last_tokens " .. last_tokens)
-- Lấy dấu thời gian cập nhật cuối cùng, nếu rỗng, đặt thành 0
local last_refreshed = tonumber(redis.call("get", timestamp_key))
if last_refreshed == nil then
last_refreshed = 0
end
--redis.log(redis.LOG_WARNING, "last_refreshed " .. last_refreshed)
-- Tính toán khoảng thời gian từ lần thống kê cuối đến lần này
local delta = math.max(0, now-last_refreshed)
-- Số lượng token còn lại từ lần trước + token mới tạo, giá trị này không lớn hơn dung lượng thùng
local filled_tokens = math.min(capacity, last_tokens+(delta*rate))
-- Tổng token còn lại có đủ để đáp ứng số token tiêu thụ cho một yêu cầu
local allowed = filled_tokens >= requested
local new_tokens = filled_tokens
-- Cờ hiệu cho biết yêu cầu có được phép đi qua
local allowed_num = 0
-- Nếu đủ, trừ đi số token tiêu thụ cho một lần và cập nhật lại vào redis
if allowed then
new_tokens = filled_tokens - requested
allowed_num = 1
end
--redis.log(redis.LOG_WARNING, "delta " .. delta)
--redis.log(redis.LOG_WARNING, "filled_tokens " .. filled_tokens)
--redis.log(redis.LOG_WARNING, "allowed_num " .. allowed_num)
--redis.log(redis.LOG_WARNING, "new_tokens " .. new_tokens)
if ttl > 0 then
redis.call("setex", tokens_key, ttl, new_tokens)
redis.call("setex", timestamp_key, ttl, now)
end
-- return { allowed_num, new_tokens, capacity, filled_tokens, requested, new_tokens }
return { allowed_num, new_tokens }
Quy trình tính toán mô phỏng:
Đối với quy trình trên, do đặt giới hạn 3 yêu cầu mỗi phút, có thể thấy khi thùng token đầy chỉ có thể cho phép 3 yêu cầu đi qua. Khi thùng token rỗng, cứ sau mỗi 20 giây sẽ tạo ra đúng số lượng token đủ cho một yêu cầu, thực hiện kiểm soát lưu lượng một cách mượt mà.