How to Build a Simple Token Bucket RateLimiter in Java

Preface

This article is not a detailed analysis of RateLimiter, but rather an overview.

Token Bucket Algorithm

The token bucket logic is the basis of most RateLimiter implementations.

Implementation by Diagram

Following the common diagram, the implementation simply adds tokens at a fixed rate and provides a method to acquire a token.

import java.util.concurrent.*;

public class MyRateLimiter {
    // Token bucket
    BlockingQueue<Integer> TOKEN_BUCKET = new LinkedBlockingDeque<>(5);

    public static void main(String[] args) {
        MyRateLimiter myRateLimiter = new MyRateLimiter();
        myRateLimiter.addTokenFixedRate();
        for (int i = 0; i < 10; i++) {
            myRateLimiter.acquire();
            System.out.println("Execution i:" + i + ", time:" + System.currentTimeMillis());
        }
    }

    /**
     * Periodically add tokens
     */
    public void addTokenFixedRate() {
        ScheduledExecutorService scheduledExecutorService = Executors.newSingleThreadScheduledExecutor();
        scheduledExecutorService.scheduleAtFixedRate(() -> {
            boolean suc = TOKEN_BUCKET.offer(1);
            if (!suc) {
                System.out.println("Token bucket full, discarding");
            }
        }, 0, 200, TimeUnit.MILLISECONDS);
    }

    public void acquire() {
        while (TOKEN_BUCKET.poll() == null) {}
    }
}

Test results show the implementation meets basic requirements.

RateLimiter Overview Implementation

Examining Guava's RateLimiter source reveals that it does not use a collection as a bucket; instead, it records the next token generation time and the number of stored permits, updating them dynamically.

Overview Logic Diagram

The core Guava code is as follows:

@CanIgnoreReturnValue
public double acquire(int permits) {
  long microsToWait = reserve(permits);
  stopwatch.sleepMicrosUninterruptibly(microsToWait);
  return 1.0 * microsToWait / SECONDS.toMicros(1L);
}

final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {
  resync(nowMicros);
  long returnValue = nextFreeTicketMicros;
  double storedPermitsToSpend = min(requiredPermits, this.storedPermits);
  double freshPermits = requiredPermits - storedPermitsToSpend;
  long waitMicros = storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend)
      + (long) (freshPermits * stableIntervalMicros);
  this.nextFreeTicketMicros = LongMath.saturatedAdd(nextFreeTicketMicros, waitMicros);
  this.storedPermits -= storedPermitsToSpend;
  return returnValue;
}

In summary, RateLimiter does not use a collection as a bucket; its core mechanism tracks the next token generation time and the current number of stored permits, updating them dynamically.