(WIP) Bucket4j

최근 Rate Limiter 처리를 위해 Bucket4j를 사용했습니다. 관련 내용을 정리하고 공유합니다.

1. Token Bucket 방식의 Rate Limiter

2. Token Consume

@Override
protected boolean tryConsumeImpl(long tokensToConsume) {
  long currentTimeNanos = timeMeter.currentTimeNanos();
  lock.lock();
  try {
      state.refillAllBandwidth(currentTimeNanos);
      long availableToConsume = state.getAvailableTokens();
      if (tokensToConsume > availableToConsume) {
          return false;
      }
      state.consume(tokensToConsume);
      return true;
  } finally {
      lock.unlock();
  }
}

3. Refill

Bucket4j는 여러가지 Refill 전략을 제공합니다.

public void refillAllBandwidth(long currentTimeNanos) {
    Bandwidth[] bandwidths = configuration.getBandwidths();
    for (int i = 0; i < bandwidths.length; i++) {
        refill(i, bandwidths[i], currentTimeNanos);
    }
}
private void refill(int bandwidthIndex, Bandwidth bandwidth, long currentTimeNanos) {
  long previousRefillNanos = getLastRefillTimeNanos(bandwidthIndex);
  if (currentTimeNanos <= previousRefillNanos) {
      return;
  }

  if (bandwidth.isRefillIntervally()) {
      long incompleteIntervalCorrection = (currentTimeNanos - previousRefillNanos) % bandwidth.getRefillPeriodNanos();
      currentTimeNanos -= incompleteIntervalCorrection;
  }
  if (currentTimeNanos <= previousRefillNanos) {
      return;
  } else {
      setLastRefillTimeNanos(bandwidthIndex, currentTimeNanos);
  }

  final long capacity = bandwidth.getCapacity();
  final long refillPeriodNanos = bandwidth.getRefillPeriodNanos();
  final long refillTokens = bandwidth.getRefillTokens();
  final long currentSize = getCurrentSize(bandwidthIndex);

  if (currentSize >= capacity) {
      // can come here if forceAddTokens has been used
      return;
  }

  long durationSinceLastRefillNanos = currentTimeNanos - previousRefillNanos;
  long newSize = currentSize;

  if (durationSinceLastRefillNanos > refillPeriodNanos) {
      long elapsedPeriods = durationSinceLastRefillNanos / refillPeriodNanos;
      long calculatedRefill = elapsedPeriods * refillTokens;
      newSize += calculatedRefill;
      if (newSize > capacity) {
          resetBandwidth(bandwidthIndex, capacity);
          return;
      }
      if (newSize < currentSize) {
          // arithmetic overflow happens. This mean that tokens reached Long.MAX_VALUE tokens.
          // just reset bandwidth state
          resetBandwidth(bandwidthIndex, capacity);
          return;
      }
      durationSinceLastRefillNanos %= refillPeriodNanos;
  }


  long roundingError = getRoundingError(bandwidthIndex);
  long dividedWithoutError = multiplyExactOrReturnMaxValue(refillTokens, durationSinceLastRefillNanos);
  long divided = dividedWithoutError + roundingError;
  if (divided < 0 || dividedWithoutError == Long.MAX_VALUE) {
      // arithmetic overflow happens.
      // there is no sense to stay in integer arithmetic when having deal with so big numbers
      long calculatedRefill = (long) ((double) durationSinceLastRefillNanos / (double) refillPeriodNanos * (double) refillTokens);
      newSize += calculatedRefill;
      roundingError = 0;
  } else {
      long calculatedRefill = divided / refillPeriodNanos;
      if (calculatedRefill == 0) {
          roundingError = divided;
      } else {
          newSize += calculatedRefill;
          roundingError = divided % refillPeriodNanos;
      }
  }

  if (newSize >= capacity) {
      resetBandwidth(bandwidthIndex, capacity);
      return;
  }
  if (newSize < currentSize) {
      // arithmetic overflow happens. This mean that bucket reached Long.MAX_VALUE tokens.
      // just reset bandwidth state
      resetBandwidth(bandwidthIndex, capacity);
      return;
  }
  setCurrentSize(bandwidthIndex, newSize);
  setRoundingError(bandwidthIndex, roundingError);
}

References

  • https://bucket4j.com
  • https://github.com/bucket4j/bucket4j
  • https://www.mimul.com/blog/about-rate-limit-algorithm/
  • https://en.wikipedia.org/wiki/Token_bucket
  • https://smudge.ai/blog/ratelimit-algorithms