Distributed Rate Limiter

medium

CodingReported Apr 2026 · Single frequency

Distributed Token-Bucket Rate Limiting

Coding Software Engineer

Problem Overview

Create a distributed rate limiter that uses a token-bucket design and replenishes tokens lazily. Two classes are supplied for you:

DistributedCache: A distributed key/value system, such as Redis, exposing get() and put()
TokenBucket: A dataclass that stores the current rate-limit state for one user

You must write these two functions:

refill_token_bucket(bucket, current_time): Determine the on-demand refill amount from the time passed and apply it
allow_request(cache, user_id, tokens_requested): Decide whether a user can spend the requested tokens and deduct them when permitted

This approach is often applied to:

Large-scale API throttling for millions of accounts
Abuse protection in distributed applications
Equitable sharing of resources among services
Managing quotas for GPU inference workloads

Provided Classes

import time
from dataclasses import dataclass

class DistributedCache:
    """
    A distributed cache such as Redis that offers atomic get/put calls.
    Treat this class as prebuilt; serialization is handled internally.
    """
    def get(self, key: str) -> object | None:
        """Retrieve the value for key, or None when no such key is stored."""
        pass

    def put(self, key: str, value: object) -> None:
        """Save value under key."""
        pass


@dataclass
class TokenBucket:
    """Stores one user's token-bucket information."""
    tokens: float # Tokens currently available
    last_refill_time: float # Time of the most recent refill (Unix time)
    capacity: int # Largest token count permitted in the bucket
    refill_rate: float # Tokens replenished each second

Example Usage

cache = DistributedCache()

# The user's initial request
result = allow_request(cache, "member_47", tokens_requested=1)
print(result) # True (a new bucket begins at its capacity)

# Rapidly use the other 99 available tokens
for _ in range(99):
    allow_request(cache, "member_47", tokens_requested=1)

# With 100 tokens spent, another request is denied
result = allow_request(cache, "member_47", tokens_requested=1)
print(result) # False (no tokens remain)

# Allow tokens to be replenished...
time.sleep(1) # Sleep for one second (when refill_rate is 10/sec)

# The user can make a request again
result = allow_request(cache, "member_47", tokens_requested=1)
print(result) # True (10 tokens were replenished)

Problem Statement

Write refill_token_bucket so it works out the number of tokens earned since the previous refill time.

Why use lazy refilling? Rather than continuously running a job that refills every user's bucket, token replenishment happens only when that user sends a request. That avoids unnecessary work in systems with millions of users, most of whom may currently be inactive.

def refill_token_bucket(bucket: TokenBucket, current_time: float) -> TokenBucket:
    """
    Refill a bucket on demand using the elapsed time.

    Args:
        bucket: Existing state of the token bucket
        current_time: Current Unix time in seconds

    Returns:
        A TokenBucket containing the replenished token count and refreshed timestamp
    """
    pass

Requirements

Find the duration since last_refill_time
Increase the bucket by elapsed_time * refill_rate tokens
Never let the token total rise above capacity
Set last_refill_time to current_time
Address clock skew: when current_time < last_refill_time, tokens must not be deducted

Test Cases

# Test 1: A normal one-second refill
bucket = TokenBucket(tokens=42, last_refill_time=200.0, capacity=90, refill_rate=8.0)
updated = refill_token_bucket(bucket, current_time=201.0)
assert updated.tokens == 50 # 42 + (1 * 8)
assert updated.last_refill_time == 201.0

# Test 2: Refilling cannot exceed the bucket limit
bucket = TokenBucket(tokens=87, last_refill_time=200.0, capacity=90, refill_rate=8.0)
updated = refill_token_bucket(bucket, current_time=201.0)
assert updated.tokens == 90 # Limited to capacity rather than 95

# Test 3: Identical timestamps produce no refill
bucket = TokenBucket(tokens=42, last_refill_time=200.0, capacity=90, refill_rate=8.0)
updated = refill_token_bucket(bucket, current_time=200.0)
assert updated.tokens == 42 # The value stays unchanged

# Test 4: A long inactive period fills the bucket
bucket = TokenBucket(tokens=0, last_refill_time=200.0, capacity=90, refill_rate=8.0)
updated = refill_token_bucket(bucket, current_time=300.0) # 100 seconds later
assert updated.tokens == 90 # The bucket reaches full capacity

Problem Statement

Implement allow_request to verify that a user can afford a request and to spend those tokens as one operation.

def allow_request(
    cache: DistributedCache,
    user_id: str,
    tokens_requested: int = 1,
    capacity: int = 100,
    refill_rate: float = 10.0
) -> bool:
    """
    Permit a request and deduct its tokens when sufficient tokens exist.
    Otherwise, deny it without deducting anything.

    Args:
        cache: The distributed cache to use
        user_id: The user's unique ID
        tokens_requested: Token quantity to spend (default: 1)
        capacity: Capacity assigned to buckets created for new users
        refill_rate: Per-second refill speed assigned to new users

    Returns:
        True when tokens were spent and the request is accepted; otherwise False
    """
    pass

Requirements

Derive a cache key using user_id, such as f"rate_limit:{user_id}"
When the cache has no bucket for the user, initialize one at full capacity
Replenish the bucket from elapsed time by invoking refill_token_bucket
Test whether tokens >= tokens_requested
If sufficient tokens exist, subtract them, persist the bucket, and return True
If insufficient tokens exist, persist the refilled bucket so a later call benefits, then return False

Test Cases

# Test 1: A first-time user starts with a full bucket
cache = DistributedCache()
assert allow_request(cache, "first_member") == True

# Test 2: Spend every token
cache = DistributedCache()
for _ in range(100):
    assert allow_request(cache, "account_r") == True # The first 100 are accepted

assert allow_request(cache, "account_r") == False # Request 101 is rejected

# Test 3: Each user receives an independent bucket
cache = DistributedCache()
for _ in range(100):
    allow_request(cache, "client_red")

assert allow_request(cache, "client_red") == False # client_red has spent its bucket
assert allow_request(cache, "client_blue") == True # client_blue still has available tokens

# Test 4: Spend more than one token in a single request
cache = DistributedCache()
assert allow_request(cache, "batch_user", tokens_requested=50) == True # 50 tokens remain
assert allow_request(cache, "batch_user", tokens_requested=50) == True # No tokens remain
assert allow_request(cache, "batch_user", tokens_requested=1) == False # The bucket is empty

Problem Statement

Several servers can receive requests for one user at the same time in a distributed deployment. A straightforward implementation contains a race condition:

Server A: GET member_47 -> bucket(tokens=10)
Server B: GET member_47 -> bucket(tokens=10)
Server A: tokens - 1 = 9, PUT member_47 -> bucket(tokens=9)
Server B: tokens - 1 = 9, PUT member_47 -> bucket(tokens=9)
# Both calls were accepted even though just one token was recorded as spent!

Discussion Questions

What can you do to eliminate this race condition?
- Distributed locks, such as Redis SETNX or Redlock
- Atomic primitives, such as Redis INCR/DECR or Lua scripts
- Optimistic concurrency control using version values
What compromises does each option involve?
How should lock acquisition failures and timeouts be handled?

Example: Atomic Lua-Script Operation

With Redis, the complete read, refill, check, and deduction can run atomically in a Lua script:

# Redis Lua-script approach in pseudocode
RATE_LIMIT_SCRIPT = """
local key = KEYS[1]
local tokens_requested = tonumber(ARGV[1])
local capacity = tonumber(ARGV[2])
local refill_rate = tonumber(ARGV[3])
local current_time = tonumber(ARGV[4])

local bucket = redis.call('HGETALL', key)
-- Decode the bucket, refill it, validate tokens, deduct, and persist it
-- The entire sequence executes atomically
"""

def allow_request_atomic(redis_client, user_id: str, tokens: int = 1) -> bool:
    result = redis_client.eval(
        RATE_LIMIT_SCRIPT,
        keys=[f"rate_limit:{user_id}"],
        args=[tokens, 100, 10.0, time.time()]
)
    return result == 1

Requirements for Discussion

Describe why the simple implementation suffers from a race condition
Give at least two remedies and explain the tradeoffs of each
State which approach you would deploy in production and explain your reasoning

Clarification Questions to Ask

What per-user QPS and overall system QPS are expected?
Do different users need different limits, such as premium plans?
How precise must enforcement be? Some systems tolerate a small amount of over-limit traffic.
Should buckets for inactive users expire through a TTL?
Must the API report remaining tokens or the wait time until the next refill?

BackBack to problems

Distributed Rate Limiter

medium

CodingReported Apr 2026 · Single frequency

Distributed Token-Bucket Rate Limiting

Coding Software Engineer

Problem Overview

Create a distributed rate limiter that uses a token-bucket design and replenishes tokens lazily. Two classes are supplied for you:

DistributedCache: A distributed key/value system, such as Redis, exposing get() and put()
TokenBucket: A dataclass that stores the current rate-limit state for one user

You must write these two functions:

refill_token_bucket(bucket, current_time): Determine the on-demand refill amount from the time passed and apply it
allow_request(cache, user_id, tokens_requested): Decide whether a user can spend the requested tokens and deduct them when permitted

This approach is often applied to:

Large-scale API throttling for millions of accounts
Abuse protection in distributed applications
Equitable sharing of resources among services
Managing quotas for GPU inference workloads

Provided Classes

import time
from dataclasses import dataclass

class DistributedCache:
    """
    A distributed cache such as Redis that offers atomic get/put calls.
    Treat this class as prebuilt; serialization is handled internally.
    """
    def get(self, key: str) -> object | None:
        """Retrieve the value for key, or None when no such key is stored."""
        pass

    def put(self, key: str, value: object) -> None:
        """Save value under key."""
        pass


@dataclass
class TokenBucket:
    """Stores one user's token-bucket information."""
    tokens: float # Tokens currently available
    last_refill_time: float # Time of the most recent refill (Unix time)
    capacity: int # Largest token count permitted in the bucket
    refill_rate: float # Tokens replenished each second

Example Usage

cache = DistributedCache()

# The user's initial request
result = allow_request(cache, "member_47", tokens_requested=1)
print(result) # True (a new bucket begins at its capacity)

# Rapidly use the other 99 available tokens
for _ in range(99):
    allow_request(cache, "member_47", tokens_requested=1)

# With 100 tokens spent, another request is denied
result = allow_request(cache, "member_47", tokens_requested=1)
print(result) # False (no tokens remain)

# Allow tokens to be replenished...
time.sleep(1) # Sleep for one second (when refill_rate is 10/sec)

# The user can make a request again
result = allow_request(cache, "member_47", tokens_requested=1)
print(result) # True (10 tokens were replenished)

Problem Statement

Write refill_token_bucket so it works out the number of tokens earned since the previous refill time.

def refill_token_bucket(bucket: TokenBucket, current_time: float) -> TokenBucket:
    """
    Refill a bucket on demand using the elapsed time.

    Args:
        bucket: Existing state of the token bucket
        current_time: Current Unix time in seconds

    Returns:
        A TokenBucket containing the replenished token count and refreshed timestamp
    """
    pass

Requirements

Find the duration since last_refill_time
Increase the bucket by elapsed_time * refill_rate tokens
Never let the token total rise above capacity
Set last_refill_time to current_time
Address clock skew: when current_time < last_refill_time, tokens must not be deducted

Test Cases

# Test 1: A normal one-second refill
bucket = TokenBucket(tokens=42, last_refill_time=200.0, capacity=90, refill_rate=8.0)
updated = refill_token_bucket(bucket, current_time=201.0)
assert updated.tokens == 50 # 42 + (1 * 8)
assert updated.last_refill_time == 201.0

# Test 2: Refilling cannot exceed the bucket limit
bucket = TokenBucket(tokens=87, last_refill_time=200.0, capacity=90, refill_rate=8.0)
updated = refill_token_bucket(bucket, current_time=201.0)
assert updated.tokens == 90 # Limited to capacity rather than 95

# Test 3: Identical timestamps produce no refill
bucket = TokenBucket(tokens=42, last_refill_time=200.0, capacity=90, refill_rate=8.0)
updated = refill_token_bucket(bucket, current_time=200.0)
assert updated.tokens == 42 # The value stays unchanged

# Test 4: A long inactive period fills the bucket
bucket = TokenBucket(tokens=0, last_refill_time=200.0, capacity=90, refill_rate=8.0)
updated = refill_token_bucket(bucket, current_time=300.0) # 100 seconds later
assert updated.tokens == 90 # The bucket reaches full capacity

Problem Statement

Implement allow_request to verify that a user can afford a request and to spend those tokens as one operation.

def allow_request(
    cache: DistributedCache,
    user_id: str,
    tokens_requested: int = 1,
    capacity: int = 100,
    refill_rate: float = 10.0
) -> bool:
    """
    Permit a request and deduct its tokens when sufficient tokens exist.
    Otherwise, deny it without deducting anything.

    Args:
        cache: The distributed cache to use
        user_id: The user's unique ID
        tokens_requested: Token quantity to spend (default: 1)
        capacity: Capacity assigned to buckets created for new users
        refill_rate: Per-second refill speed assigned to new users

    Returns:
        True when tokens were spent and the request is accepted; otherwise False
    """
    pass

Requirements

Derive a cache key using user_id, such as f"rate_limit:{user_id}"
When the cache has no bucket for the user, initialize one at full capacity
Replenish the bucket from elapsed time by invoking refill_token_bucket
Test whether tokens >= tokens_requested
If sufficient tokens exist, subtract them, persist the bucket, and return True
If insufficient tokens exist, persist the refilled bucket so a later call benefits, then return False

Test Cases

# Test 1: A first-time user starts with a full bucket
cache = DistributedCache()
assert allow_request(cache, "first_member") == True

# Test 2: Spend every token
cache = DistributedCache()
for _ in range(100):
    assert allow_request(cache, "account_r") == True # The first 100 are accepted

assert allow_request(cache, "account_r") == False # Request 101 is rejected

# Test 3: Each user receives an independent bucket
cache = DistributedCache()
for _ in range(100):
    allow_request(cache, "client_red")

assert allow_request(cache, "client_red") == False # client_red has spent its bucket
assert allow_request(cache, "client_blue") == True # client_blue still has available tokens

# Test 4: Spend more than one token in a single request
cache = DistributedCache()
assert allow_request(cache, "batch_user", tokens_requested=50) == True # 50 tokens remain
assert allow_request(cache, "batch_user", tokens_requested=50) == True # No tokens remain
assert allow_request(cache, "batch_user", tokens_requested=1) == False # The bucket is empty

Problem Statement

Several servers can receive requests for one user at the same time in a distributed deployment. A straightforward implementation contains a race condition:

Server A: GET member_47 -> bucket(tokens=10)
Server B: GET member_47 -> bucket(tokens=10)
Server A: tokens - 1 = 9, PUT member_47 -> bucket(tokens=9)
Server B: tokens - 1 = 9, PUT member_47 -> bucket(tokens=9)
# Both calls were accepted even though just one token was recorded as spent!

Discussion Questions

What can you do to eliminate this race condition?
- Distributed locks, such as Redis SETNX or Redlock
- Atomic primitives, such as Redis INCR/DECR or Lua scripts
- Optimistic concurrency control using version values
What compromises does each option involve?
How should lock acquisition failures and timeouts be handled?

Example: Atomic Lua-Script Operation

With Redis, the complete read, refill, check, and deduction can run atomically in a Lua script:

# Redis Lua-script approach in pseudocode
RATE_LIMIT_SCRIPT = """
local key = KEYS[1]
local tokens_requested = tonumber(ARGV[1])
local capacity = tonumber(ARGV[2])
local refill_rate = tonumber(ARGV[3])
local current_time = tonumber(ARGV[4])

local bucket = redis.call('HGETALL', key)
-- Decode the bucket, refill it, validate tokens, deduct, and persist it
-- The entire sequence executes atomically
"""

def allow_request_atomic(redis_client, user_id: str, tokens: int = 1) -> bool:
    result = redis_client.eval(
        RATE_LIMIT_SCRIPT,
        keys=[f"rate_limit:{user_id}"],
        args=[tokens, 100, 10.0, time.time()]
)
    return result == 1

Requirements for Discussion

Describe why the simple implementation suffers from a race condition
Give at least two remedies and explain the tradeoffs of each
State which approach you would deploy in production and explain your reasoning

Clarification Questions to Ask

What per-user QPS and overall system QPS are expected?
Do different users need different limits, such as premium plans?
How precise must enforcement be? Some systems tolerate a small amount of over-limit traffic.
Should buckets for inactive users expire through a TTL?
Must the API report remaining tokens or the wait time until the next refill?

Distributed Rate Limiter

Distributed Token-Bucket Rate Limiting

Problem Overview

Provided Classes

Example Usage

Part 1: On-Demand Token Refill

Problem Statement

Requirements

Test Cases

Part 2: Request अनुमति Function

Problem Statement

Requirements

Test Cases

Part 3: Concurrency Concerns

Problem Statement

Discussion Questions

Example: Atomic Lua-Script Operation

Requirements for Discussion

Clarification Questions to Ask

Distributed Rate Limiter

Distributed Token-Bucket Rate Limiting

Problem Overview

Provided Classes

Example Usage

Part 1: On-Demand Token Refill

Problem Statement

Requirements

Test Cases

Part 2: Request अनुमति Function

Problem Statement

Requirements

Test Cases

Part 3: Concurrency Concerns

Problem Statement

Discussion Questions

Example: Atomic Lua-Script Operation

Requirements for Discussion

Clarification Questions to Ask