Bird
Raised Fist0

Design a Rate Limiter Class - Token Bucket OOP Implementation with Thread Safety

LLDhardInterview freq: medium
Choose your preparation mode4 modes available
ArchitectureTraceChallenge
🎯
Design a Rate Limiter Class - Token Bucket OOP Implementation with Thread Safety
40 min · medium
medium

Implement a Token Bucket rate limiter that controls the rate of requests per client. The limiter should allow bursts up to a maximum bucket capacity and refill tokens at a fixed rate. It must be thread-safe to handle concurrent requests from multiple threads.

Given Info
  • Each client has an independent token bucket with a fixed capacity and refill rate.
  • Tokens are refilled periodically based on elapsed time since last refill.
  • Requests consume one token; if no tokens are available, the request is rejected.
  • The system must handle concurrent requests from multiple threads safely.
  • The design should allow future extension to support different rate limiting algorithms.
📋
Guided Steps
1/5
Step 1
Define the TokenBucket class with state and behavior
Design the TokenBucket class to hold the current token count, capacity, and refill rate. Decide how to represent these fields and the methods to consume and refill tokens.
💡 Hint
Use private fields for state and provide synchronized methods to modify token count atomically.
Key Decision
Use private volatile long lastRefillTimestamp and synchronized methods consumeToken() and refillTokens() to ensure atomic state updates and visibility across threads.
Interviewer Expectation
Mid: Defines TokenBucket with synchronized consumeToken() to prevent race conditions. Senior: Explains volatile lastRefillTimestamp ensures visibility of time updates across threads, preventing stale reads.
⚠️Common Wrong Answer
Using non-volatile lastRefillTimestamp causes threads to read stale timestamps, leading to incorrect token refills and allowing more requests than capacity.
Step 2
Implement thread-safe token consumption and refill logic
How will you ensure that token consumption and refill are atomic and consistent under concurrent access?
💡 Hint
Synchronize the methods that read and update token count and last refill time to prevent interleaving issues.
Key Decision
Synchronize consumeToken() and refillTokens() methods to atomically check token availability and update token count and lastRefillTimestamp, preventing lost updates.
Interviewer Expectation
Mid: Uses synchronized keyword on methods to serialize access. Senior: Traces thread interleaving where without synchronization, two threads read tokens > 0 simultaneously, both consume, causing token count to go negative.
⚠️Common Wrong Answer
Using separate synchronized blocks for checking and updating tokens leads to race conditions where tokens can be over-consumed.
Step 3
Design an interface for RateLimiter to support extensibility
How will you design the RateLimiter abstraction to allow future algorithms beyond Token Bucket?
💡 Hint
Use a Java interface with method signatures for tryAcquire() and optionally refill().
Key Decision
Define RateLimiter interface with boolean tryAcquire() method; interface cannot hold state, so TokenBucket implements it with instance fields.
Interviewer Expectation
Mid: Defines RateLimiter interface for extensibility. Senior: Explains interface cannot hold instance state in Java, so TokenBucket must implement state and behavior.
⚠️Common Wrong Answer
Using abstract class RateLimiter with no state leads to confusion; interface is preferred for stateless contract and better multiple inheritance support.
Step 4
Manage multiple clients with independent token buckets
How will you design the system to handle multiple clients each with their own token bucket safely?
💡 Hint
Use a thread-safe concurrent map keyed by client ID to store TokenBucket instances.
Key Decision
Use ConcurrentHashMap<String, TokenBucket> to store client buckets; TokenBucket methods remain synchronized for thread safety per bucket.
Interviewer Expectation
Mid: Uses ConcurrentHashMap for thread-safe client bucket storage. Senior: Explains that without ConcurrentHashMap, concurrent client bucket creation leads to lost updates or duplicate buckets.
⚠️Common Wrong Answer
Using HashMap without synchronization causes race conditions on bucket creation and retrieval, leading to inconsistent rate limiting.
Step 5
Handle token refill timing accurately
How will you implement token refilling based on elapsed time since last refill?
💡 Hint
Calculate elapsed time using System.nanoTime() or System.currentTimeMillis() and add tokens accordingly in a synchronized method.
Key Decision
Use volatile lastRefillTimestamp updated inside synchronized refillTokens() to ensure visibility; calculate tokens to add based on elapsed time and refill rate.
Interviewer Expectation
Mid: Calculates tokens to add based on elapsed time. Senior: Explains volatile ensures visibility of lastRefillTimestamp updates across threads, preventing stale reads and incorrect refill calculations.
⚠️Common Wrong Answer
Using System.currentTimeMillis() without volatile lastRefillTimestamp causes threads to see stale timestamps, leading to token under- or over-refill.
🔌
API Design Challenge
Design a thread-safe Token Bucket Rate Limiter API that supports multiple clients with independent buckets and allows future extensibility to other rate limiting algorithms.
Hints
  • Use a RateLimiter interface with a tryAcquire() method to abstract rate limiting behavior.
  • Store client-specific TokenBucket instances in a thread-safe ConcurrentHashMap keyed by client ID.
  • Ensure atomic token consumption and refill using synchronized methods and volatile fields for visibility.
📊
Scoring Rubric
▼ Show
Must Have - 60%
  • TokenBucket class with private volatile lastRefillTimestamp field
  • Synchronized consumeToken() and refillTokens() methods for atomic updates
  • RateLimiter interface with tryAcquire() method
  • ConcurrentHashMap for client bucket storage
  • Use of volatile to ensure visibility of shared mutable state
Good to Have - 30%
  • Accurate token refill calculation based on elapsed time
  • Clear separation of interface and implementation for extensibility
  • Proper encapsulation of state and behavior in TokenBucket
  • Explanation of thread interleaving scenarios causing race conditions
  • Use of System.nanoTime() or System.currentTimeMillis() with volatile for timing
Bonus - 10%
  • Support for pluggable rate limiting algorithms beyond Token Bucket
  • Use of AtomicLong for lastRefillTimestamp as alternative to volatile + synchronized
  • Detailed concurrency scenario tracing with thread interleaving
  • Unit tests demonstrating thread safety
  • Use of Java 8+ features like default methods in interface if applicable
Anti-patterns to Avoid
Using non-volatile lastRefillTimestamp leads to stale reads and incorrect token refills, causing token over-consumption.
Separate synchronized blocks for token check and update cause lost updates and token over-consumption due to race conditions.
Using HashMap without synchronization causes race conditions on bucket creation and retrieval, leading to inconsistent rate limiting.
✅
Model Answer
▼ Reveal

Key Decisions
    • TokenBucket class with private volatile long lastRefillTimestamp to track last refill time with visibility guarantees.
    • Synchronized consumeToken() and refillTokens() methods to atomically update token count and timestamps, preventing race conditions.
    • RateLimiter interface defining boolean tryAcquire() to allow multiple rate limiting algorithm implementations.
    • ConcurrentHashMap<String, TokenBucket> for thread-safe storage of client-specific token buckets.
    • Use of volatile for lastRefillTimestamp to ensure visibility of time updates across threads.
    • Calculation of tokens to add based on elapsed time inside synchronized refillTokens() to maintain consistency.
    • Avoidance of separate synchronized blocks for check and update to prevent lost updates.
    • TokenBucket encapsulates state and behavior, enforcing encapsulation and single responsibility principle.
    • Extensibility via interface supports Open/Closed principle allowing new algorithms without modifying existing code.
    • Use of Java concurrency utilities (volatile, synchronized, ConcurrentHashMap) to ensure thread safety.

    Practice

    (1/5)
    1. In the Ride Booking system, the FareCalculator class has a private constructor and a static synchronized getInstance() method. Which design pattern is applied here and why is this the correct use case?
    easy
    A. Factory pattern, because it creates FareCalculator instances on demand.
    B. Prototype pattern, to clone FareCalculator instances for thread safety.
    C. Singleton pattern, to ensure only one FareCalculator instance calculates fares consistently.
    D. Builder pattern, to construct FareCalculator with complex parameters.

    Solution

    1. Step 1: Identify the pattern from constructor and method signatures

      The private constructor prevents external instantiation, and the static synchronized getInstance() method ensures a single shared instance, matching Singleton pattern characteristics.

    2. Step 2: Why Singleton fits FareCalculator

      FareCalculator needs consistent fare rules and shared state (e.g., pricing configs). Singleton avoids multiple inconsistent instances and ensures thread-safe access.

    3. Final Answer:

      Option C -> Option C

    4. Quick Check:

      Private constructor + synchronized getInstance() -> Singleton pattern [check]
    Hint: Private constructor + static getInstance() = Singleton [check]
    Common Mistakes:
    2. A Java class has a private constructor and a static synchronized getInstance() method returning the single instance. Which design pattern is applied and why is this the CORRECT use case?
    easy
    A. Factory pattern, because it controls object creation centrally.
    B. Builder pattern, because it constructs complex objects step-by-step.
    C. Prototype pattern, because it clones existing instances for reuse.
    D. Singleton pattern, because it ensures only one instance with controlled access.

    Solution

    1. Step 1: Identify the pattern by constructor and method

      The private constructor prevents external instantiation, and the static synchronized getInstance() method controls access to a single instance, matching Singleton pattern characteristics.

    2. Step 2: Eliminate other patterns

      Factory creates multiple instances, Builder constructs complex objects with multiple steps, and Prototype clones objects; none restrict to a single instance.

    3. Final Answer:

      Option D -> Option D

    4. Quick Check:

      Private constructor + synchronized static getter -> Singleton pattern [check]
    Hint: Private constructor + static synchronized getter -> Singleton [check]
    Common Mistakes:
    3. In a multi-threaded inventory update method updateStock() without synchronization, which exact sequence causes a race condition leading to incorrect stock count?
    medium
    A. Thread 1 and Thread 2 both wait on a lock, preventing race conditions
    B. Thread 1 reads stock=10, Thread 2 reads stock=10, both add 5, final stock=15
    C. Thread 1 writes stock=15, Thread 2 reads stock=15, then writes stock=20 correctly
    D. Thread 1 reads stock=10, context switch before update, Thread 2 reads stock=10, both write stock=15, losing one update

    Solution

    1. Step 1: Trace the check-then-act gap

      Thread 1 reads stock=10 but is preempted before writing update. Thread 2 reads the same stock=10 and writes stock=15. Thread 1 resumes and overwrites with stock=15, losing Thread 2's update.

    2. Step 2: Why other options fail

      Thread 1 reads stock=10, Thread 2 reads stock=10, both add 5, final stock=15 incorrectly assumes final stock=15 after both add 5 (should be 20). Thread 1 writes stock=15, Thread 2 reads stock=15, then writes stock=20 correctly shows correct sequence with no race. Thread 1 and Thread 2 both wait on a lock, preventing race conditions describes locking, which is absent here.

    3. Final Answer:

      Option D -> Option D

    4. Quick Check:

      Unsynchronized read-update-write -> lost update race condition [check]
    Hint: Unsynchronized read-update-write causes lost updates [check]
    Common Mistakes:
    4. The system needs to support ElectricCar playback devices that require ChargingSpot management. What is the minimum change to the current design to support this without modifying existing classes?
    hard
    A. Add ELECTRIC_CAR to DeviceType enum, CHARGING to SpotType enum, create ElectricCar extends Device, and update SpotCompatibility map externally.
    B. Modify existing Device class to add charging logic and add ElectricCar as a flag inside it.
    C. Create a new ElectricCar class unrelated to Device and duplicate playback logic.
    D. Add charging logic inside the PlaybackQueue class to handle ElectricCar specifics.

    Solution

    1. Step 1: Identify extensibility without modifying existing classes

      Adding new enum values and subclassing allows extension without changing existing class code.

    2. Step 2: Update compatibility externally

      Updating SpotCompatibility map outside existing classes respects OCP and avoids class explosion or god-class logic.

    3. Final Answer:

      Option A -> Option A

    4. Quick Check:

      Extend enums + subclass + external map update -> minimal change [check]
    Hint: Extend enums + subclass + external map -> minimal change [check]
    Common Mistakes:
    5. To add an ElectricPlayer who requires ChargingSpot in the Snake and Ladder game, what is the minimum change to the current design to maintain extensibility without modifying existing classes?
    hard
    A. Add ELECTRIC_PLAYER to PlayerType enum, add CHARGING to SpotType enum, create ElectricPlayer extends Player, update SpotCompatibility map.
    B. Modify Player class to include charging logic and add ChargingSpot as a new field.
    C. Create a new ElectricPlayer class and modify Board to handle ChargingSpots explicitly.
    D. Add charging behavior directly inside Player class and update all existing player types.

    Solution

    1. Step 1: Identify extensibility without modifying existing classes

      Adding new enum values and new subclass preserves existing class code unchanged.

    2. Step 2: Update compatibility map for new player and spot types

      SpotCompatibility map extension allows new rules without changing existing logic.

    3. Final Answer:

      Option A -> Option A

    4. Quick Check:

      New enums + subclass + compatibility map extension -> minimal existing code change [check]
    Hint: New enums + subclass + map update = extensible addition [check]
    Common Mistakes:
    Recommended

    Ready to prove it?

    Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

    10 questions~5 mineasy hard