(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