предисловие
Недавно наша система представила компонент ограничения тока RateLimiter от Guava, основанный наАлгоритм ведра токеновРеализовано, и ведро токенов является очень классическим алгоритмом ограничения тока. Эта статья познакомит вас с несколькими классическими алгоритмами ограничения тока.
- публика:маленький мальчик собирает улиток
- гитхаб-адрес
Что такое ограничение тока?
В Википедии есть следующие понятия:
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
and limit web scraping
Простой перевод: в компьютерных сетях регулирование — это скорость, с которой запросы отправляются или принимаются сетевым интерфейсом, что предотвращает DoS-атаки и ограничивает поисковые роботы.
Ограничение тока, также известное как управление потоком. Это означает, что система сталкивается с высокой степенью параллелизма илиЗапрос с высоким трафикомв случае,Ограничить доступ к системе для новых запросов,тем самымУбедитесь, что устойчивость системы. Текущее ограничение приводит к тому, что частичная обработка запроса пользователя выполняется не вовремя или отклоняется, что влияет на взаимодействие с пользователем. Так что вообще нужно между стабильностью системы и пользовательским опытомостаток средствнемного. Возьмем пример из жизни:
Некоторые популярные туристические достопримечательности обычно имеют ограничения на количество посетителей в день. Каждый день будет продаваться только фиксированное количество билетов, например 5000. Предположим, вы опаздываете во время празднования 1 мая и Национального дня, и билеты на этот день могли быть распроданы, поэтому вы не можете войти и сыграть. Даже если вы войдете, очередь может заставить вас усомниться в своей жизни.
Общие алгоритмы ограничения тока
Алгоритм ограничения тока фиксированного окна
Поддерживая первый счетчик, единичный период как окно, счетчик окна записывает количество полученных запросов.
- Когда число меньше текущего порога ограничения, доступ и счетчик +1
- Когда количество раз превышает текущий порог ограничения, доступ запрещается.
- По истечении текущего временного окна счетчик очищается.
Предполагая, что единица времени равна 1 секунде, порог ограничения тока равен 3. В течение 1 секунды в единицу времени счетчик для каждого запроса увеличивается на 1. Если количество накоплений счетчика превышает текущий предельный порог, равный 3, все последующие запросы отклоняются. После ожидания в течение 1 с счетчик обнуляется и снова начинает считать. Как показано ниже:
Псевдокод выглядит следующим образом:
/**
* 固定窗口时间算法
* @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 запросов, а единичное временное окно равно 1 с, если мы одновременно делаем 5 запросов в первые 0,8-1 с и 1-1,2 с единицы времени. Хотя ни один из них не превышает порог, но если считать 0,8-1,2 с, количество параллелизма достигает 10, что ужеБолее 1 с в единицу времени не превышает порог 5определение.
Алгоритм ограничения тока в скользящем окне
Скользящее ограничение тока окна решает проблему фиксированных порогов окна. Он делит единичный период времени на n небольших периодов, записывает время доступа к интерфейсу в каждом небольшом периоде и удаляет истекшие небольшие периоды в соответствии со скользящим временем.
Диаграмма, объясняющая алгоритм скользящего окна, выглядит следующим образом:
Предполагая, что единица времени по-прежнему равна 1 с, алгоритм скользящего окна делит его на 5 небольших периодов, то есть скользящее окно (единица времени) делится на 5 маленьких сеток. Каждая сетка представляет 0,2 с. Каждые 0,2 с временное окно сдвигается на одну сетку вправо. Затем каждый малый цикл имеет свой собственный независимый счетчик.Если запрос поступает через 0,83 с, счетчик, соответствующий 0,8~1,0 с, увеличится на 1.
Давайте посмотрим, как скользящее окно решает проблему критичности?
Предполагая, что наш текущий предельный порог в пределах 1 с по-прежнему составляет 5 запросов,0.8~1.0sВ течение (типа 0,9с) пришло 5 запросов и попало в желтую сетку. По прошествии времени 1,0 с пришло еще 5 запросов, которые попали в фиолетовую сетку. еслиЭто алгоритм с фиксированным окном, и он не будет ограничен.,ноЕсли окно скользит, оно будет перемещаться на небольшую сетку вправо каждый раз, когда проходит небольшой период.. После точки 1,0 с он будет двигаться вправо по небольшой сетке. Текущий период времени составляет 0,2 ~ 1,2 с. Запрос в этой области превысил ограничение 5, и текущий предел был активирован. Дело в том, что запросы фиолетовой сетки были отклонены.
TIPS:Чем больше разделены периоды сетки скользящего окна, тем плавнее будет прокрутка скользящего окна и тем точнее будет текущая ограничивающая статистика.
Алгоритм скользящего окнаРеализация псевдокодаследующее:
/**
* 单位时间划分的小周期（单位时间是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 мы потеряем часть запроса, который на самом деле не очень дружелюбен к продукту.
алгоритм дырявого ведра
Алгоритм дырявого ведра более гибок в условиях ограничения тока, и здесь нет прямого грубого отказа.
Его принцип очень прост, его можно рассматривать какутечка водыпроцесс. Вода поступает в дырявое ведро с произвольной скоростью и вытекает с фиксированной скоростью. Когда вода превышает вместимость ведра, его переливают, то есть выбрасывают. Поскольку вместимость ковша постоянна, общая скорость гарантируется.
- Приток капель воды можно расценивать как запрос на доступ к системе, а скорость притока неопределенна.
- Емкость корзины обычно представляет собой количество запросов, которые может обработать система.
- Если емкость ведра заполнена, достигнут порог ограничения тока, и капля воды отбрасывается (отклонение запроса)
- Вытекающие капли воды постоянно фильтруются, а соответствующий сервис обрабатывает запросы с фиксированной скоростью.
алгоритм дырявого ведраРеализация псевдокодаследующее:
/**
* 每秒处理数（出水率）
*/
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;
}
При обычном трафике система обрабатывает запросы с фиксированной скоростью, что нам и нужно. ноЛицо бурного трафикаВ то время алгоритм Drain Bar обрабатывает запрос, это не то, что мы хотим видеть. Когда лопнет трафик, мы увереныЯ надеюсь, что система обработает запрос как можно скорее, чтобы улучшить пользовательский опыт.
Алгоритм ведра токенов
лицовзрывной трафик, мы можем использовать алгоритм ведра для токенов, чтобы ограничить ток.
Принцип алгоритма Token Bucket:
- Есть администратор токенов, который кладет токены в корзину токенов по фиксированной ставке в соответствии с текущим лимитом.
- Если количество токенов заполнено и превышает предел емкости корзины токенов, оно будет удалено.
- Когда система получает запрос пользователя, она сначала обращается к корзине токенов, чтобы запросить токен. Если вы получили токен, то обработайте бизнес-логику этого запроса;
- Если токен не может быть получен, запрос будет отклонен напрямую.
Псевдокодовая реализация алгоритма дырявого ведра выглядит следующим образом:
/**
* 每秒处理数（放入令牌数量）
*/
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;
}
Если стратегия выпуска токенов верна, система не будет тормозиться, а использование машины будет улучшено. Компонент ограничения тока RateLimiter в Guava основан наАлгоритм ведра токеновосуществленный.
Ссылка и спасибо
- Интервьюер: Давай, молодой человек! Пожалуйста, сыграйте в 5 распространенных алгоритмов ограничения тока!
- Alibaba Cloud Two Sides: что вы знаете об ограничении тока?