Building a Token Bucket with Locks

Your learning outcome for this lesson:

You will implement a lock-based token bucket using synchronized blocks or ReentrantLock.

1. The Need for Locking in Concurrent Systems

In our token bucket design, the availableTokens and lastRefillTimestamp fields represent shared, mutable state. Imagine two threads executing the tryConsume() method at nearly the same time:

1. Thread A reads availableTokens (e.g., 1.2 tokens).
2. Thread B reads availableTokens (also 1.2 tokens).
3. Thread A determines it can consume a token, calculates newTokens = 0.2, and prepares to write this value back.
4. Before Thread A can write, Thread B also determines it can consume a token, calculates newTokens = 0.2, and writes this value back.
5. Thread A finally writes its calculated value of 0.2 back.

The result is incorrect. Two requests were granted, but the token count was only decremented once. This is a classic race condition. To prevent this, we must ensure that the sequence of "read-modify-write" operations on our shared state is atomic—that is, it happens as a single, indivisible unit. Locking is the primary mechanism to achieve this.

2. Approach 1: The synchronized Keyword

The synchronized keyword is Java's built-in mechanism for ensuring that only one thread can execute a block of code at a time. It uses an intrinsic lock (also called a monitor lock) associated with every Java object. When a thread enters a synchronized block, it acquires the lock; when it exits, it releases the lock.

To understand how this works and why it's essential, let's watch a short video.

Implementing the Token Bucket with synchronized

Based on the principles from the video, we can protect our tryConsume() logic by wrapping the critical section in a synchronized block. We use this as the lock object, ensuring that all threads attempting to consume a token from the same bucket instance will synchronize with each other.

Here is a simple implementation using this approach. Notice the allowRequest() method is marked synchronized, which is equivalent to wrapping the entire method body in synchronized(this).

This implementation is simple and effective. The synchronized keyword handles all the complexities of acquiring and releasing the lock, even if an exception occurs.

3. Approach 2: ReentrantLock

While synchronized is convenient, the java.util.concurrent.locks package provides a more powerful and flexible locking mechanism: ReentrantLock. It offers the same basic mutual exclusion guarantees but with additional capabilities (which we will explore in later lessons).

Key characteristics of ReentrantLock:

• Explicit Locking: You must explicitly call lock() to acquire the lock and unlock() to release it.
• The try-finally Idiom: It is absolutely critical to place the unlock() call inside a finally block. This guarantees that the lock is released even if an exception is thrown within the try block, preventing a deadlock where other threads can never acquire the lock.

This next video explains the basics of ReentrantLock.

Implementing the Token Bucket with ReentrantLock

Now let's see how to apply ReentrantLock to our token bucket. This implementation will be slightly more verbose but also more explicit about the lock management.

The code in the article demonstrates the correct and robust pattern for using ReentrantLock. For our rate limiter's tryConsume() method, which should return immediately, we would replace the while loop and awaitNanos call with a simple if condition, but the locking structure remains the same.

4. Comparing synchronized vs. ReentrantLock

Both synchronized and ReentrantLock can solve our immediate problem. So which one should you use? Here's a quick comparison.

Key takeaways from the comparison:

• Simplicity: synchronized is less verbose and easier to use for basic locking.
• Explicitness: ReentrantLock makes lock acquisition and release explicit, which some developers find clearer.
• Features: ReentrantLock provides advanced features like timed waits, interruptible lock acquisition, and fairness policies, which are essential for more complex concurrency scenarios.

For the purpose of our rate limiter, either would be a valid choice. However, using ReentrantLock demonstrates familiarity with the more modern java.util.concurrent library, which is a valuable skill.

5. Your Implementation Task

Now it's time to put this into practice. Let's create our lock-based TokenBucket class. We will use ReentrantLock for this implementation to practice the try-finally pattern.

The class should have the fields we designed in the last lesson and a method to attempt to consume a token. For now, we will create a single bucket instance. We will later adapt this to work with our RateLimiter strategy interface that you designed previously.

Here is the class structure. Your task is to complete the tryConsume() method.

import java.util.concurrent.locks.ReentrantLock;

public class TokenBucket {

    private final long capacity;
    private final double refillRate; // tokens per second

    private double availableTokens;
    private long lastRefillTimestamp;
    private final ReentrantLock lock = new ReentrantLock();

    public TokenBucket(long capacity, double refillRate) {
        this.capacity = capacity;
        this.refillRate = refillRate;
        this.availableTokens = capacity;
        this.lastRefillTimestamp = System.nanoTime();
    }

    /**
     * Attempts to consume one token from the bucket.
     * This method is thread-safe.
     *
     * @return {@code true} if a token was consumed, {@code false} otherwise.
     */
    public boolean tryConsume() {
        lock.lock();
        try {
            // 1. Refill tokens based on elapsed time since lastRefillTimestamp.
            //    - Get the current time with System.nanoTime().
            //    - Calculate tokens to add.
            //    - Update availableTokens, ensuring it doesn't exceed capacity.
            //    - Update lastRefillTimestamp to the current time.

            // 2. Check if a token is available (availableTokens >= 1).
            //    - If yes, decrement availableTokens by 1 and return true.
            //    - If no, return false.

            // --- YOUR IMPLEMENTATION GOES HERE ---

            return false; // Placeholder
        } finally {
            lock.unlock();
        }
    }
}

Instructions:

1. Copy the code above into your IDE.
2. Implement the logic inside the try block of the tryConsume() method.
3. The logic is identical to what we reviewed in the articles: calculate elapsed time, compute new tokens, cap the total at capacity, update the timestamp, and then check if a token can be consumed.

Take your time to implement this. This is a foundational piece of our rate limiter.

Conclusion

In this lesson, you've implemented a thread-safe, lock-based token bucket, a critical step toward our final goal.

Key Takeaways:

• Protecting shared, mutable state (like availableTokens) is essential to prevent race conditions in concurrent applications.
• Java provides two primary lock-based mechanisms for this: the synchronized keyword and ReentrantLock.
• synchronized is simpler and relies on intrinsic object monitors.
• ReentrantLock is more explicit and flexible, requiring the developer to manage the lock's lifecycle, always using a try-finally block to guarantee the lock is released.

Next Steps

Locking is effective, but it can have performance implications. When a thread is waiting for a lock, it is blocked and cannot do any work. For high-throughput systems, an alternative is often preferred: lock-free programming.

In our next lesson, we will refactor our token bucket to a lock-free implementation using AtomicLong and compare-and-set (CAS) loops. We will then be able to explain the performance trade-offs between these two important concurrency models.