Java의 고전적인 전류 제한 알고리즘 분석 예
- 王林앞으로
- 2023-04-18 23:13:01932검색
속도 제한이란 무엇인가요?
Wikipedia의 개념은 다음과 같습니다.
컴퓨터 네트워크에서 속도 제한은 네트워크 인터페이스 컨트롤러가 보내거나 받는 요청 속도를 제어하는 데 사용됩니다. DoS 공격을 방지하는 데 사용할 수 있습니다. 웹 스크래핑을 제한하세요
간단히 말하면 컴퓨터 네트워크에서 흐름 제한은 네트워크 인터페이스가 요청을 보내거나 받는 속도를 제어하는 것입니다. 이는 DoS 공격을 방지하고 웹 크롤러를 제한할 수 있습니다.
전류 제한, 흐름 제어라고도 합니다. 이는 시스템이 높은 동시성 또는 대규모 트래픽 요청에 직면할 때 시스템에 대한 새로운 요청의 액세스를 제한하여 시스템 안정성을 보장한다는 의미입니다. 현재 제한으로 인해 일부 사용자 요청이 적시에 처리되거나 거부되어 사용자 경험에 영향을 미칩니다. 따라서 일반적으로 시스템 안정성과 사용자 경험 사이의 균형을 유지하는 것이 필요합니다. 일상 생활의 예를 들면: ★
일부 인기 관광 명소에는 일반적으로 일일 방문객 수에 제한이 있습니다. 매일 5,000장 등 정해진 수량만 판매됩니다. 노동절이나 국경절 연휴 기간에 늦게 도착하실 경우 당일 티켓이 매진되어 입장 및 플레이가 불가능할 수 있습니다. 들어가더라도 줄은 인생을 의심하게 만듭니다.”공통 전류 제한 알고리즘
고정 창 전류 제한 알고리즘
먼저 카운터를 유지하고 단위 기간을 창으로 처리하고 카운터는 이 창에서 수신된 요청 수를 기록합니다.
- 숫자가 현재 제한 임계값보다 작으면 액세스가 허용되며 카운터는 +1
- 숫자가 현재 제한 임계값보다 크면 액세스가 거부됩니다.
- 현재 시간 창이 지나면 카운터는
- 단위 시간이 1초라고 가정하면 현재 제한 임계값은 3입니다. 1초 이내에 누적된 카운터 수가 현재 제한 임계값인 3을 초과하면 카운터가 1씩 증가합니다. , 모든 후속 요청은 1초 후에 거부되고 카운터는 0으로 지워지고 다시 계산되기 시작합니다.
의사 코드는 다음과 같습니다.
/**
* 固定窗口时间算法
* @return
*/
boolean fixedWindowsTryAcquire() {
long currentTime = System.currentTimeMillis(); //获取系统当前时间
if (currentTime - lastRequestTime > windowUnit) { //检查是否在时间窗口内
counter = 0; // 计数器清0
lastRequestTime = currentTime; //开启新的时间窗口
}
if (counter < threshold) { // 小于阀值
counter++; //计数器加1
return true;
}
return false;
}그러나 이 알고리즘에는 명백한
중요한 문제가 있습니다. 문제: 제한 임계값이 단위 시간당 요청 5개라고 가정합니다. 임계값을 초과하지 않더라도 단위 시간의 처음 0.8~1초와 1~1.2초에 5개의 요청을 동시에 보내는 경우 0.8~1.2초를 계산하면 동시 요청 수는 이미 10개입니다. 이는 의 정의가 단위 시간당 임계값 5개를 초과하는 것입니다.
슬라이딩 윈도우 전류 제한 알고리즘
단위 시간이 여전히 1초라고 가정하면 슬라이딩 윈도우 알고리즘은 이를 5개의 작은 기간으로 나눕니다. 즉, 슬라이딩 윈도우(단위 시간)를 나눕니다. 5개의 작은 그리드로 구성됩니다. 각 그리드는 0.2초를 나타내며 시간 창은 오른쪽으로 한 그리드씩 이동합니다. 각 주기에는 자체 독립 카운터가 있습니다. 요청이 0.83초에 도착하면 0.8~1.0초에 해당하는 카운터가 증가합니다.
슬라이딩 창이 어떻게 중요한 문제를 해결하는지 살펴보겠습니다. 
가 고정 창 알고리즘이면 전류 제한
이 아니지만이 슬라이딩 창이면
작은 간격마다 작은 사각형을 오른쪽으로 이동합니다. 현재 단위 시간은 0.2~1.2초이며 현재 제한 시간은 5입니다. 실제로 보라색 그리드의 모든 요청이 거부되었습니다팁: 슬라이딩 창을 더 많은 그리드 기간으로 나누면 슬라이딩 창의 롤링이 더 부드러워지고 현재 제한이 적용됩니다.
슬라이딩 창 알고리즘의사 코드 구현은 다음과 같습니다.
/**
* 单位时间划分的小周期（单位时间是1分钟，10s一个小格子窗口，一共6个格子）
*/
private int SUB_CYCLE = 10;
/**
* 每分钟限流请求数
*/
private int thresholdPerMin = 100;
/**
* 计数器, k-为当前窗口的开始时间值秒，value为当前窗口的计数
*/
private final TreeMap<Long, Integer> counters = new TreeMap<>();
/**
* 滑动窗口时间算法实现
*/
boolean slidingWindowsTryAcquire() {
long currentWindowTime = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC) / SUB_CYCLE * SUB_CYCLE; //获取当前时间在哪个小周期窗口
int currentWindowNum = countCurrentWindow(currentWindowTime); //当前窗口总请求数
//超过阀值限流
if (currentWindowNum >= thresholdPerMin) {
return false;
}
//计数器+1
counters.get(currentWindowTime)++;
return true;
}
/**
* 统计当前窗口的请求数
*/
private int countCurrentWindow(long currentWindowTime) {
//计算窗口开始位置
long startTime = currentWindowTime - SUB_CYCLE* (60s/SUB_CYCLE-1);
int count = 0;
//遍历存储的计数器
Iterator<Map.Entry<Long, Integer>> iterator = counters.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<Long, Integer> entry = iterator.next();
// 删除无效过期的子窗口计数器
if (entry.getKey() < startTime) {
iterator.remove();
} else {
//累加当前窗口的所有计数器之和
count =count + entry.getValue();
}
}
return count;
}슬라이딩 창 알고리즘은 고정 창의 중요한 문제가 해결되었지만 현재 제한에 도달하면 요청이 발생합니다. Jiangzi는 일부 요청을 잃게 되며 이는 실제로 제품에 그다지 우호적이지 않습니다.
Leaky Bucket AlgorithmLeaky Bucket 알고리즘은 전류 제한에 직면할 때 더 유연하며 직접적이고 무례한 거부가 없습니다.
원리는 아주 간단합니다.물을 주입하고 물이 새는 과정
이라고 생각하시면 됩니다. 물은 새는 물통으로 어떤 속도로든 흘러 들어가고 물은 고정된 속도로 흘러나옵니다. 물이 물통의 용량을 초과하면 물이 넘치게 됩니다. 즉, 버려집니다. 버킷 용량이 변하지 않기 때문에 전체 속도가 보장됩니다.
유입되는 물방울은 시스템에 대한 접근 요청으로 간주될 수 있습니다. 이 유입 속도는 불확실합니다. 
桶的容量一般表示系统所能处理的请求数。
如果桶的容量满了，就达到限流的阀值，就会丢弃水滴（拒绝请求）
流出的水滴，是恒定过滤的，对应服务按照固定的速率处理请求。
漏桶算法伪代码实现如下：
/**
* 每秒处理数（出水率）
*/
private long rate;
/**
* 当前剩余水量
*/
private long currentWater;
/**
* 最后刷新时间
*/
private long refreshTime;
/**
* 桶容量
*/
private long capacity;
/**
* 漏桶算法
* @return
*/
boolean leakybucketLimitTryAcquire() {
long currentTime = System.currentTimeMillis(); //获取系统当前时间
long outWater = (currentTime - refreshTime) / 1000 * rate; //流出的水量 =(当前时间-上次刷新时间)* 出水率
long currentWater = Math.max(0, currentWater - outWater); // 当前水量 = 之前的桶内水量-流出的水量
refreshTime = currentTime; // 刷新时间
// 当前剩余水量还是小于桶的容量，则请求放行
if (currentWater < capacity) {
currentWater++;
return true;
}
// 当前剩余水量大于等于桶的容量，限流
return false;
}在正常流量的时候，系统按照固定的速率处理请求，是我们想要的。但是面对突发流量的时候，漏桶算法还是循规蹈矩地处理请求，这就不是我们想看到的啦。流量变突发时，我们肯定希望系统尽量快点处理请求，提升用户体验嘛。
令牌桶算法
面对突发流量的时候，我们可以使用令牌桶算法限流。
令牌桶算法原理：
有一个令牌管理员，根据限流大小，定速往令牌桶里放令牌。
如果令牌数量满了，超过令牌桶容量的限制，那就丢弃。
系统在接受到一个用户请求时，都会先去令牌桶要一个令牌。如果拿到令牌，那么就处理这个请求的业务逻辑；
如果拿不到令牌，就直接拒绝这个请求。
漏桶算法伪代码实现如下：
/**
* 每秒处理数（放入令牌数量）
*/
private long putTokenRate;
/**
* 最后刷新时间
*/
private long refreshTime;
/**
* 令牌桶容量
*/
private long capacity;
/**
* 当前桶内令牌数
*/
private long currentToken = 0L;
/**
* 漏桶算法
* @return
*/
boolean tokenBucketTryAcquire() {
long currentTime = System.currentTimeMillis(); //获取系统当前时间
long generateToken = (currentTime - refreshTime) / 1000 * putTokenRate; //生成的令牌 =(当前时间-上次刷新时间)* 放入令牌的速率
currentToken = Math.min(capacity, generateToken + currentToken); // 当前令牌数量 = 之前的桶内令牌数量+放入的令牌数量
refreshTime = currentTime; // 刷新时间
//桶里面还有令牌，请求正常处理
if (currentToken > 0) {
currentToken--; //令牌数量-1
return true;
}
return false;
}如果令牌发放的策略正确，这个系统即不会被拖垮，也能提高机器的利用率。Guava的RateLimiter限流组件，就是基于令牌桶算法实现的。
위 내용은 Java의 고전적인 전류 제한 알고리즘 분석 예의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!