Implementing a Token Bucket Algorithm

Your learning outcome for this lesson:

You will design a TokenBucket class with capacity, available tokens, and last refill timestamp. We will focus on understanding the components and the logic that governs how tokens are generated and consumed.

1. The Token Bucket Concept

The Token Bucket algorithm is conceptually simple and intuitive. Imagine a bucket with a certain capacity. This bucket is continuously filled with tokens at a fixed rate. Each incoming request must take one token from the bucket to be processed.

• If a token is available, the request takes it and is allowed.
• If the bucket is empty, the request is denied.
• If the bucket is full, any new tokens that arrive are discarded.

The two key parameters are:

1. Capacity: The maximum number of tokens the bucket can hold. This determines the maximum burst of requests a client can make in a short period.
2. Refill Rate: The rate at which new tokens are added to the bucket (e.g., 10 tokens per second). This defines the average, sustained rate of allowed requests.

To solidify your understanding of these principles, please read the following short overview.

2. Designing the TokenBucket Class

Now, let's translate this concept into the state, or fields, of a Java class. To implement the algorithm, our class needs to track four key pieces of information:

• capacity: The maximum number of tokens. This will be a final value set during construction.
• refillRate: How many tokens are generated per unit of time. This is also a final value.
• availableTokens: The current number of tokens in the bucket. This value will change as tokens are refilled and consumed.
• lastRefillTimestamp: The precise time the bucket was last refilled. This is essential for calculating how many new tokens to add when the next request arrives.

This design uses a "lazy refill" or "on-demand" strategy. Instead of having a background process constantly adding tokens, we calculate and add the appropriate number of tokens only when a request actually arrives. This is a very common and efficient pattern as it does no work when the system is idle.

Let's examine a complete implementation that uses this lazy refill approach.

3. Deconstructing the Implementation

Let's break down the code from the article you just reviewed. It perfectly demonstrates the on-demand refill logic and the state management required.

Class Structure and State

The class defines the four fields we identified:

public class TokenBucket {
    private final int capacity;
    private final double refillRate; // tokens per second
    private double tokens; // Represents our 'availableTokens'
    private long lastRefillTimestamp;
    // ... constructor ...
}

• The tokens field is a double to allow for fractional tokens to accumulate. For example, if your rate is 0.5 tokens per second, after 1 second you should have 0.5 tokens, not 0. This prevents losing precision when refill intervals are short. A request is only granted when the total accumulated tokens are >= 1.0.

The allowRequest() Method

The synchronized keyword is used on this method. This is critical. It ensures that on a multi-threaded system, only one thread can be checking and taking a token at a time, preventing race conditions where two requests might simultaneously be granted with only one token available.

Let's look at the logic inside the method step-by-step:

1. Calculate Elapsed Time and Tokens to Add:

   long now = System.nanoTime();
   double tokensToAdd = ((now - lastRefillTimestamp) / 1e9) * refillRate;
   

   First, it captures the current time using System.nanoTime(), which is ideal for measuring elapsed time. It calculates the time passed since the last refill, converts it to seconds (by dividing by 10⁹), and multiplies by the refillRate to determine how many new tokens should be generated.

2. Refill the Bucket (Up to Capacity):

   tokens = Math.min(capacity, tokens + tokensToAdd);
   

   The newly generated tokens are added to the current token count. Math.min() ensures the total number of tokens never exceeds the capacity. This is how the "overflow" is handled.

3. Update the Timestamp:

   lastRefillTimestamp = now;
   

   The timestamp is updated to the current moment. This "resets the clock" for the next request.

4. Check and Consume a Token:

   if (tokens >= 1) {
       tokens -= 1;
       return true; // Request is allowed
   } else {
       return false; // Request is blocked
   }
   

   Finally, the code checks if at least one full token is available. If so, it decrements the token count and returns true. Otherwise, it returns false.

This entire sequence—refill, check, and consume—happens atomically within the synchronized method, guaranteeing correctness under concurrent access.

Key Takeaways

• The Token Bucket algorithm manages a budget of tokens, contrasting with the counting-based approaches of Fixed and Sliding Window algorithms.
• The core design of a TokenBucket class requires tracking capacity, refill rate, available tokens, and the last refill timestamp.
• A "lazy refill" mechanism is an efficient implementation strategy, calculating and adding new tokens only when a request arrives.
• Ensuring the entire "refill-check-consume" operation is atomic (e.g., using a synchronized block) is critical for thread safety.

Next Steps

You now have a solid design for a TokenBucket class. In the next lesson, we will implement two versions of this algorithm. First, we will build a straightforward, lock-based implementation using the synchronized approach we just analyzed. Then, drawing on your experience from the last lesson, we will refactor it into a more advanced lock-free implementation using AtomicLong and compare-and-set loops, exploring the performance trade-offs between the two concurrency models.