Все интерфейсы серверных служб имеют ограничение доступа. Если внешний QPS или параллелизм превысят ограничение доступа, приложение будет парализовано. Поэтому к вызовам интерфейса обычно добавляется защита от превышения тока, чтобы предотвратить системные сбои, вызванные запросами, которые превышают ожидания.
Вообще говоря, существует два типа типов ограничения тока: ограничение текущего количества одновременных запросов и ограничение текущего количества запросов в секунду.Ограничение текущего количества одновременных запросов заключается в ограничении максимального количества одновременных запросов в одно и то же время.
С точки зрения масштаба действия, есть одномашинное ограничение тока и распределенное ограничение тока. Первое предназначено для одной машины, а второе - для кластеров. Их идеи одинаковы, но область применения различна. В этой статье анализируется всеАвтономное ограничение тока.
Далее, давайте взглянем на текущее ограничение количества одновременных запросов и текущее ограничение числа запросов в секунду.
Больше статей смотрите в личном блоге:GitHub.com/farmer Джон Брат…
Ограничение параллелизма
Количество ограничений параллелизма - это количество параллелизма одновременно, поэтому, если безопасность потоков не рассматривается, нам нужно использовать только переменную int для ее достижения.Псевдокод выглядит следующим образом:
int maxRequest=100;
int nowRequest=0;
public void request(){
if(nowRequest>=maxRequest){
return ;
}
nowRequest++;
//调用接口
try{
invokeXXX();
}finally{
nowRequest--;
}
}
Очевидно, что приведенная выше реализация будет иметь проблемы с потокобезопасностью, поэтому самый прямой способ — это блокировка:
int maxRequest=100;
int nowRequest=0;
public void request(){
if(nowRequest>=maxRequest){
return ;
}
synchronized(this){
if(nowRequest>=maxRequest){
return ;
}
nowRequest++;
}
//调用接口
try{
invokeXXX();
}finally{
synchronized(this){
nowRequest--;
}
}
}
Конечно, это также можно реализовать с помощью AtomicInteger:
int maxRequest=100;
AtomicInteger nowRequest=new AtomicInteger(0);
public void request(){
for(;;){
int currentReq=nowRequest.get();
if(currentReq>=maxRequest){
return;
}
if(nowRequest.compareAndSet(currentReq,currentReq+1)){
break;
}
}
//调用接口
try{
invokeXXX();
}finally{
nowRequest.decrementAndGet();
}
}
Студенты, знакомые с параллельными пакетами JDK, скажут, почему это так проблематично.Разве не этим занимается Semaphore? Да, на самом деле, проще всего использовать семафор для достижения:
int maxRequest=100;
Semaphore reqSemaphore = new Semaphore(maxRequest);
public void request(){
if(!reqSemaphore.tryAcquire()){
return ;
}
//调用接口
try{
invokeXXX();
}finally{
reqSemaphore.release();
}
}
Все дороги ведут в Рим, а одновременное число и ограничение по току относительно просты, вообще говоря, лучше использовать семафор.
Ограничение тока QPS
Текущее ограничение количества запросов в секунду ограничивает количество запросов за период времени (обычно 1 секунду).
встречный метод
Самый простой способ — использовать в качестве счетчика переменную count типа int: счетчик перед запросом равен +1.Если он превышает порог, а интервал с первым запросом все еще в пределах 1 с, ток будет ограничен.
Псевдокод выглядит следующим образом:
int maxQps=100;
int count;
long timeStamp=System.currentTimeMillis();
long interval=1000;
public synchronized boolean grant(){
long now=System.currentTimeMillis();
if(now<timeStamp+interval){
count++;
return count<maxQps;
}else{
timeStamp=now;
count=1;
return true;
}
}
Этот метод очень прост в реализации, но на самом деле есть критическая проблема: если 100 запросов приходят в последние 500 мс первой секунды, а 100 запросов приходят в первые 500 мс второй секунды, то максимальное значение в эту 1 секунду на самом деле QPS составляет 200. Как показано ниже:
Метод счетчика будет иметь критические проблемы, в основном из-за слишком низкой статистической точности, которую можно решить с помощью алгоритма скользящего окна.
раздвижное окно
Мы используем массив длиной 10 для представления запросов QPS в течение 1 секунды, и каждый элемент массива соответствует количеству запросов в течение соответствующих 100 мс. использовать одинsumКоличество запросов текущих единиц кода переменной. При этом просроченные значения будут отсеиваться каждые 100мс.
Псевдокод выглядит следующим образом:
int maxQps=100;
AtomicInteger[] count=new AtomicInteger[10];
long timeStamp=System.currentTimeMillis();
long interval=1000;
AtomicInteger sum;
volatile int index;
public void init(){
for(int i=0;i<count.length;i++){
count[i]=new AtomicInteger(0);
}
sum=new AtomicInteger(0);
}
public synchronized boolean grant(){
count[index].incrementAndGet();
return sum.incrementAndGet()<maxQps;
}
//每100ms执行一次
public void run(){
index=(index+1)%count.length;
int val=count[index].getAndSet(0);
sum.addAndGet(-val);
}
Чем меньше окно скользящего окна, тем выше точность и выше соответствующее потребление ресурсов.
алгоритм дырявого ведра
Идея алгоритма дырявого ведра состоит в том, что есть ведро фиксированного размера, вода (запрос) поступает в дырявое ведро с определенной скоростью, а из дырявого ведра вода сливается с определенной скоростью. Переполнение происходит, когда ведро заполнено.
существуетВикипедияКак видно из вышеизложенного, существует две реализации алгоритма дырявого ведра, одна из нихas a meter, другойas a queue.В большинстве статей в Интернете не упоминается, что существует две реализации, и существует путаница в отношении этих двух концепций.
As a meter
Первая реализация эквивалентна бакету с маркерами, но угол выражения другой.
Псевдокод выглядит следующим образом:
long timeStamp=System.currentTimeMillis();//上一次调用grant的时间
int bucketSize=100;//桶大小
int rate=10;//每ms流出多少请求
int count;//目前的水量
public synchronized boolean grant(){
long now = System.currentTimeMillis();
if(now>timeStamp){
count = Math.max(0,count-(now-timeStamp)*rate);
timeStamp = now;
}
if(count+1<=bucketSize){
count++;
return true;
}else{
return false;
}
}
Данная реализация допускает всплеск трафика на период времени.Например в начале нет воды в ведре.В это время 100 запросов приходит в течении 1мс.Эти 100 запросов не будут лимитированы,а после этого только максимум за мс может быть принято 100 запросов 10 запросов (например, в следующие 1 мс будет 100 запросов, и 90 из них будут ограничены).
Он достигает того же эффекта, что и ведро с токенами.
As a queue
Вторая реализация реализована с очередью, при поступлении запроса, если очередь не заполнена, он будет добавлен в очередь, иначе новый запрос будет отклонен. При этом запросы выводятся из очереди на выполнение с постоянной скоростью.
Псевдокод выглядит следующим образом:
Queue<Request> queue=new LinkedBlockingQueue(100);
int gap;
int rate;
public synchronized boolean grant(Request req){
if(!queue.offer(req)){return false;}
}
// 单独线程执行
void consume(){
while(true){
for(int i=0;i<rate;i++){
//执行请求
Request req=queue.poll();
if(req==null){break;}
req.doRequest();
}
Thread.sleep(gap);
}
}
Для этого алгоритма скорость запроса фиксирована, а всплеск трафика не допускается.
Например, когда корзина пуста в начале, когда 100 запросов приходят в течение 1 мс, будут приняты только первые 10, а остальные будут отклонены. Обратите внимание на приведенное вышеas a meterразница в реализации.
**Однако, когда размер ведра равен размеру воды, вытекающей из каждого билета, второй алгоритм дырявого ведра эквивалентен первому алгоритму дырявого ведра. **Это,as a queueдаas a meterСпециальная реализация . Если вы не понимаете это предложение, вы можете прочитать выше еще разas a meterПсевдокод , когдаbucketSize==rateКогда частота запросов постоянна, пакетный трафик не допускается.
Алгоритм ведра токенов
Идея алгоритма ведра токенов заключается в том, что в ведре находится не более N токенов, и токены будут добавляться в ведро с определенной скоростью.Каждый запрос должен вынимать соответствующий токен из ведра с токенами для освобождения , Токены ограничены.
Алгоритм ведра с токенами и алгоритм дырявого ведра вышеas a meterРеализации эквивалентны, они способны ограничивать среднюю скорость передачи данных, допуская при этом некоторую степень пакетной передачи. Поддельный код:
int token;
int bucketSize;
int rate;
long timeStamp=System.currentTimeMillis();
public synchronized boolean grant(){
long now=System.currentTimeMillis();
if(now>timeStamp){
token=Math.max(bucketSize,token+(timeStamp-now)*rate);
timeStamp=now;
}
if(token>0){
token--;
return true;
}else{
return false;
}
}
Сравнение двух реализаций алгоритма Leaky Bucket и алгоритма Token Bucket
as a meterАлгоритм дырявого ведра аналогичен алгоритму ведра с токенами, но угол мышления отличается.
as a queueАлгоритм дырявого ведра может принудительно ограничивать скорость передачи данных, в то время как ведро с токенами иas a meterправило дырявого ведраМожно разрешить некоторую степень пакетной передачи при ограничении средней скорости передачи данных.
Как правило, алгоритм ведра токенов чаще используется в отрасли, например, в гуаве.RateLimiterОн основан на алгоритме ведра токенов. Конечно, разные бизнес-сценарии будут иметь разные потребности, и конкретный выбор должен сочетаться со сценарием.
End
В этой статье представлены текущие ограничивающие алгоритмы, обычно используемые в серверных системах.Для каждого алгоритма существует соответствующий псевдокод, и его нетрудно понять. Однако псевдокод описывает только общую идею и не уделяет внимания некоторым деталям и вопросам эффективности, поэтому в следующей статье будет проанализирован часто используемый API ограничения тока: guava'sRateLimiterРеализация исходного кода позволяет читателям получить более четкое представление об ограничении тока.
Справочная статья
blog.Zhu Xingsheng.com/blog/count E…