Поговорим о текущем анализе исходного кода Limiting-RateLimiter.

Java

Предыдущая статьястатьяУпомянуты несколько распространенных алгоритмов ограничения тока.В этой статье будет проанализирован класс ограничения тока гуавы.RateLimiterреализация.

RateLimiterЕсть два класса реализации:SmoothBurstyа такжеSmoothWarmingUp, которые являются вариантами реализации алгоритма ведра маркеров, разница в том, чтоSmoothBurstyСкорость добавления токенов постоянна, в то время какSmoothWarmingUpБудет период прогрева, во время которого скорость добавления токенов будет постепенно увеличиваться, пока не достигнет фиксированной скорости. Применимым сценарием является то, что для некоторых систем количество запросов в секунду, которое можно выдержать в начале запуска, невелико, и для достижения наилучшего состояния требуется некоторое время для прогрева.

Больше статей смотрите в личном блоге:GitHub.com/farmer Джон Брат…

основное использование

RateLimiterИспользование простое:

//create方法传入的是每秒生成令牌的个数
RateLimiter rateLimiter= RateLimiter.create(1);
for (int i = 0; i < 5; i++) {
    //acquire方法传入的是需要的令牌个数，当令牌不足时会进行等待，该方法返回的是等待的时间
	double waitTime=rateLimiter.acquire(1);
	System.out.println(System.currentTimeMillis()/1000+" , "+waitTime);
}

Результат выглядит следующим образом:

1548070953 , 0.0
1548070954 , 0.998356
1548070955 , 0.998136
1548070956 , 0.99982

Следует отметить, что когда токена недостаточно,acquireМетод не блокирует вызов, нобудет засчитан на голову следующего звонка. Например, при первом вызове в корзине токенов нет токена, но первый вызов не блокируется, а блокируется на 1 секунду при втором вызове. То есть,Токены, причитающиеся за каждый вызов (если в корзине недостаточно токенов), оплачиваются следующим вызовом..

RateLimiter rateLimiter= RateLimiter.create(1);
double waitTime=rateLimiter.acquire(1000);
System.out.println(System.currentTimeMillis()/1000+" , "+waitTime);
waitTime=rateLimiter.acquire(1);
System.out.println(System.currentTimeMillis()/1000+" , "+waitTime);

Результат выглядит следующим образом:

1548072250 , 0.0
1548073250 , 999.998773

Цель этой конструкции состоит в том, чтобы:

 Last, but not least: consider a RateLimiter with rate of 1 permit per second, currently completely unused, and an expensive acquire(100) request comes. It would be nonsensical to just wait for 100 seconds, and /then/ start the actual task. Why wait without doing anything? A much better approach is to /allow/ the request right away (as if it was an acquire(1) request instead), and postpone /subsequent/ requests as needed. In this version, we allow starting the task immediately, and postpone by 100 seconds future requests, thus we allow for work to get done in the meantime instead of waiting idly.

Проще говоря, если каждый запрос будет оплачен за это время, будет лишнее ожидание. Например, скорость увеличения токена 1 в секунду, а токенов в корзине в начале нет, в это время запрос требует 100 токенов, запуск задачи занимает 100 с. Таким образом, лучший подход состоит в том, чтобы сначала пропустить этот запрос, а затем отложить последующие запросы.

Кроме того, RateLimiter имеетtryAcquireметод, который немедленно возвращает true, если токена достаточно, в противном случае — false.

Анализ исходного кода

Основной анализ этой статьиSmoothBurstyреализация.

Первый взглядSmoothBurstyНесколько ключевых полей в:

// 桶中最多存放多少秒的令牌数
final double maxBurstSeconds;
//桶中的令牌个数
double storedPermits;
//桶中最多能存放多少个令牌，=maxBurstSeconds*每秒生成令牌个数
double maxPermits;
//加入令牌的平均间隔，单位为微秒，如果加入令牌速度为每秒5个，则该值为1000*1000/5
double stableIntervalMicros;
//下一个请求需要等待的时间
private long nextFreeTicketMicros = 0L;

Создание RateLimiter

Давайте сначала рассмотрим метод create для создания RateLimiter.

// permitsPerSecond为每秒生成的令牌数
public static RateLimiter create(double permitsPerSecond) {
    return create(permitsPerSecond, SleepingStopwatch.createFromSystemTimer());
}

//SleepingStopwatch主要用于计时和休眠
static RateLimiter create(double permitsPerSecond, SleepingStopwatch stopwatch) {
    //创建一个SmoothBursty
    RateLimiter rateLimiter = new SmoothBursty(stopwatch, 1.0 /* maxBurstSeconds */);
    rateLimiter.setRate(permitsPerSecond);
    return rateLimiter;
}

Метод create в основном предназначен для созданияSmoothBurstyэкземпляр и вызовите егоsetRateметод. Обратите внимание здесьmaxBurstSecondsПишите мертвым как 1.0.

@Override
final void doSetRate(double permitsPerSecond, long nowMicros) {
    resync(nowMicros);
    double stableIntervalMicros = SECONDS.toMicros(1L) / permitsPerSecond;
    this.stableIntervalMicros = stableIntervalMicros;
    doSetRate(permitsPerSecond, stableIntervalMicros);
}

void resync(long nowMicros) {
    // 如果当前时间比nextFreeTicketMicros大，说明上一个请求欠的令牌已经补充好了，本次请求不用等待
    if (nowMicros > nextFreeTicketMicros) {
      // 计算这段时间内需要补充的令牌，coolDownIntervalMicros返回的是stableIntervalMicros
      double newPermits = (nowMicros - nextFreeTicketMicros) / coolDownIntervalMicros();
     // 更新桶中的令牌，不能超过maxPermits
      storedPermits = min(maxPermits, storedPermits + newPermits);
      // 这里先设置为nowMicros
      nextFreeTicketMicros = nowMicros;
    }
}

@Override
void doSetRate(double permitsPerSecond, double stableIntervalMicros) {
    double oldMaxPermits = this.maxPermits;
    maxPermits = maxBurstSeconds * permitsPerSecond;
    if (oldMaxPermits == Double.POSITIVE_INFINITY) {
        // if we don't special-case this, we would get storedPermits == NaN, below
        storedPermits = maxPermits;
    } else {
        //第一次调用oldMaxPermits为0，所以storedPermits（桶中令牌个数）也为0
        storedPermits =
                (oldMaxPermits == 0.0)
                        ? 0.0 // initial state
                        : storedPermits * maxPermits / oldMaxPermits;
    }
}

setRateметод установленmaxPermits=maxBurstSeconds * permitsPerSecond;а такжеmaxBurstSecondsравно 1, поэтомуmaxBurstSecondsБудет сохранено только количество токенов за 1 секунду.

должен быть в курсеSmoothBurstyЭто закрытый класс, что означает, что его можно передать только черезRateLimiter.createсоздание метода иmaxBurstSecondsОн жестко закодирован в версии 1.0, что означает, что мы можем создавать только сегменты, размер которых разрешен в PerSecond*1.SmoothBurstyObject (разумеется, метод отражения не обсуждается), есть несколько вопросов в репозитории guava на github (issue1,issue2,issue3,issue4) надеюсь, можно установить извнеmaxBurstSeconds, но официального ответа не видел. А в open source проекте Vipshopvjtools, кто-то предложил этовопрос, студенты Vipshop провели тест на RateLimiter гуавырасширять.

Я не очень разбираюсь в дизайне гуавы.Если у вас есть четкий друг, вы можете сказать мне~

пока одинSmoothBurstyОбъект создается, затем мы анализируем егоacquireметод.

метод приобретения

public double acquire(int permits) {
    // 计算本次请求需要休眠多久（受上次请求影响）
    long microsToWait = reserve(permits);
    // 开始休眠
    stopwatch.sleepMicrosUninterruptibly(microsToWait);
    return 1.0 * microsToWait / SECONDS.toMicros(1L);
}
 
final long reserve(int permits) {
    checkPermits(permits);
    synchronized (mutex()) {
      return reserveAndGetWaitLength(permits, stopwatch.readMicros());
    }
}

final long reserveAndGetWaitLength(int permits, long nowMicros) {
    long momentAvailable = reserveEarliestAvailable(permits, nowMicros);
    return max(momentAvailable - nowMicros, 0);
}

final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {
    // 这里调用了上面提到的resync方法，可能会更新桶中的令牌值和nextFreeTicketMicros
    resync(nowMicros);
    // 如果上次请求花费的令牌还没有补齐，这里returnValue为上一次请求后需要等待的时间，否则为nowMicros
    long returnValue = nextFreeTicketMicros;
    double storedPermitsToSpend = min(requiredPermits, this.storedPermits);
    // 缺少的令牌数
    double freshPermits = requiredPermits - storedPermitsToSpend;
    // waitMicros为下一次请求需要等待的时间；SmoothBursty的storedPermitsToWaitTime返回0
    long waitMicros =
        storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend)
            + (long) (freshPermits * stableIntervalMicros);
    // 更新nextFreeTicketMicros
    this.nextFreeTicketMicros = LongMath.saturatedAdd(nextFreeTicketMicros, waitMicros);
    // 减少令牌
    this.storedPermits -= storedPermitsToSpend;
    return returnValue;
}

acquireбудет вызванreserveМетод получает время ожидания текущего запроса, а затем приостанавливается.reserveв конечном итоге будет вызван методreserveEarliestAvailable, в этом методе сначала вызовет вышеупомянутыйresyncМетод пополняет токены в ведре (при необходимости), затем уменьшает токены в ведре, и вычисляет количество токенов, причитающихся за этот запрос, и время ожидания (за ожидание отвечает следующий запрос).

Если последний запрос не задолжал токены или причитающиеся токены были выплачены, возвращаемое значение равноnowMicros, в противном случае возвращаемое значение представляет собой количество токенов, отсутствующих в предыдущем запросе * время, необходимое для создания токена.

End

В этой статье объясняетсяRateLimiterПодклассSmoothBursty, для другого подклассаSmoothWarmingUpПринцип можно проанализировать самостоятельно. По сравнению с ведром токенов в традиционном понимании,RateLimiterРеализация все же немного отличается, в основном тем, что стоимость одного запроса ложится на следующий запрос.

Категории