pythonadvanced15 minutes

Fix Bug in Concurrent Rate Limiter Implementation

Given a broken Python implementation of a token bucket rate limiter intended to handle concurrent requests with thread safety, identify and fix the bugs causing incorrect rate limiting behavior and race conditions.

Challenge prompt

The provided Python code is intended to implement a token bucket rate limiter for an API, enforcing a max request rate over time and supporting concurrency with thread safety. However, it currently fails under concurrent load, either allowing more requests than allowed or deadlocking. Your task is to identify and fix the concurrency and logic bugs so that the rate limiter correctly enforces the limit in multithreaded environments.

Guidance

• Review thread synchronization mechanisms used in the code and ensure proper locking to avoid race conditions.
• Verify that token refill logic accounts for time and concurrency correctly and only adds tokens once per period.
• Test with concurrent threads to confirm that no more than the allowed requests pass within the specified window.

Hints

• Look for improper use or missing use of thread locks around shared state modifications.
• Check if the token refill timing is calculated correctly and whether multiple threads might simultaneously refill tokens improperly.
• Consider the atomicity of checking and decrementing token counts under concurrency.

Starter code

import threading
import time

class TokenBucket:
    def __init__(self, rate, capacity):
        self.capacity = capacity
        self.tokens = capacity
        self.rate = rate
        self.timestamp = time.time()
        self.lock = threading.Lock()

    def allow_request(self):
        now = time.time()
        elapsed = now - self.timestamp
        add_tokens = elapsed * self.rate
        if add_tokens > 0:
            self.tokens = min(self.capacity, self.tokens + add_tokens)
            self.timestamp = now

        if self.tokens >= 1:
            self.tokens -= 1
            return True
        else:
            return False

Expected output

The fixed TokenBucket should correctly limit requests so that no more than capacity tokens are used per second regardless of concurrency. For example, in a test with 10 threads attempting to call allow_request 100 times each with rate=5 and capacity=10, roughly 10-15 requests per second are permitted, reflecting the rate limiter's constraints without race conditions.

Core concepts

threadingconcurrencyrate limitinglockstoken bucket algorithm

Challenge a Friend

Send this duel to someone else and see if they can solve it.