Understanding Rate Limiting Token Bucket: Network Algorithm

1. Introduction and Core Concepts

Rate limiting is a fundamental control mechanism in modern distributed systems that regulates how often an action can be performed within a given time window. Among the various rate limiting strategies, the rate limiting token bucket algorithm stands out as one of the most flexible, efficient, and widely adopted approaches. It provides an elegant balance between enforcing strict rate limits and allowing short bursts of traffic, making it ideal for real-world network conditions where traffic is inherently bursty.

At its core, the token bucket is a conceptual container that holds tokens, where each token represents permission to perform a single operation, such as an API request, a network packet transmission, or a database query. Tokens are added to the bucket at a fixed, continuous rate, and each incoming request must consume one or more tokens to be processed. If the bucket is empty, the request is either denied, delayed, or queued depending on the implementation policy. This simple metaphor governs powerful traffic shaping and admission control behavior.

Why does the rate limiting token bucket matter? Without rate limiting, systems are vulnerable to accidental overload, denial-of-service attacks, runaway retry storms, and noisy-neighbor problems in multi-tenant architectures. A single misbehaving client can exhaust CPU, memory, database connections, or third-party API quotas, degrading service for everyone. Token bucket provides a predictable, fair, and mathematically sound way to enforce Service Level Agreements (SLAs), protect downstream dependencies, and ensure quality of service while still accommodating legitimate burst traffic that fixed-window counters would unnecessarily throttle.

The Two Key Parameters

Every token bucket is defined by two critical parameters that determine its behavior. The first is capacity (b), also called bucket size or burst size, which is the maximum number of tokens the bucket can hold. This parameter controls how large a burst the system will allow. A larger capacity permits bigger spikes, while a smaller capacity enforces smoother traffic.

The second parameter is the refill rate (r), typically expressed in tokens per second. This defines the long-term sustained rate that the system allows. For example, a bucket with capacity 100 and refill rate 10 tokens/second allows an average of 10 requests per second indefinitely, but can handle a burst of up to 100 requests instantaneously if the bucket is full. Understanding the interplay between these two parameters is essential for tuning rate limiting to match business and technical requirements.

2. How It Works

The rate limiting token bucket algorithm operates on a continuous refill model that is conceptually simple yet powerful. Imagine a bucket with a small hole in the top where tokens drip in at a constant rate, and an opening at the bottom where requests remove tokens. The bucket can never contain more than its capacity; any excess tokens overflow and are discarded. This overflow property is what caps the maximum burst size.

When a request arrives, the algorithm performs three steps: first, it calculates how many tokens should have been added since the last check by multiplying the elapsed time by the refill rate. Second, it adds those tokens to the bucket, capping at capacity. Third, it checks if enough tokens are available to satisfy the request. If yes, the required number of tokens is subtracted and the request is allowed. If not, the request is denied or throttled. Importantly, refill is lazy and calculated on-demand rather than via a background timer, which makes the algorithm highly efficient.

This lazy refill approach means there is no need for a separate thread or cron job to add tokens every millisecond. Instead, the timestamp of the last refill is stored, and the current token count is computed mathematically at request time. This makes the algorithm O(1) for each request and perfectly suited for high-throughput, low-latency paths such as API gateways and network packet processors.

Token Consumption Models

While most implementations consume one token per request, the model generalizes to variable token costs. For instance, a large file upload might cost 10 tokens while a simple GET request costs 1 token, allowing weighted rate limiting based on resource consumption. Some systems also support consuming zero tokens for health checks or consuming fractional tokens when using a continuous rate model. This flexibility allows the same algorithm to enforce rate limits based on requests per second, bytes per second, or even abstract cost units.

When a request is denied due to insufficient tokens, the system has several options. It can immediately return an error such as HTTP 429 Too Many Requests with a Retry-After header, it can queue the request until tokens become available (traffic shaping), or it can degrade gracefully by serving cached content. The choice depends on whether the goal is strict admission control or smooth traffic shaping, and the token bucket supports both patterns elegantly.

Continuous vs. Discrete Refill

There are two common refill implementations. The discrete refill adds tokens at fixed intervals, for example, 10 tokens every second. This is simpler but can cause boundary effects and micro-bursts at refill moments. The continuous refill adds tokens proportionally to elapsed time with floating-point precision, for example, 0.01 tokens per millisecond for a 10 tokens/second rate. Continuous refill provides smoother, more accurate rate limiting and is preferred for most production systems, though it requires careful handling of floating-point rounding.

3. Implementation

Implementing a rate limiting token bucket in Python is straightforward, but production-ready code must handle time measurement, concurrency, and precision correctly. The following examples progress from a basic single-threaded implementation to thread-safe and distributed variants.

The basic implementation uses time.monotonic() rather than time.time() because monotonic time is not affected by system clock adjustments, NTP corrections, or daylight saving changes. This choice prevents subtle bugs where a clock jump could incorrectly refill or empty the bucket. We also store tokens as a float to support continuous refill, and we cap the bucket at capacity on every refill calculation.

import time

class TokenBucket:
    """
    Basic rate limiting token bucket implementation.
    capacity: maximum burst size (max tokens)
    refill_rate: tokens added per second (sustained rate)
    """
    def __init__(self, capacity, refill_rate):
        self.capacity = float(capacity)
        self.refill_rate = float(refill_rate)
        self.tokens = float(capacity)  # start full
        self.last_refill = time.monotonic()

    def _refill(self):
        now = time.monotonic()
        elapsed = now - self.last_refill
        # tokens to add proportional to elapsed time
        if elapsed > 0:
            new_tokens = elapsed * self.refill_rate
            self.tokens = min(self.capacity, self.tokens + new_tokens)
            self.last_refill = now

    def consume(self, tokens=1):
        """Try to consume tokens. Return True if allowed, False if rate limited."""
        self._refill()
        if self.tokens >= tokens:
            self.tokens -= tokens
            return True
        return False

    def get_wait_time(self, tokens=1):
        """Calculate seconds to wait until enough tokens are available."""
        self._refill()
        if self.tokens >= tokens:
            return 0.0
        needed = tokens - self.tokens
        return needed / self.refill_rate

In a multi-threaded web server, concurrent requests may race to check and update the token count, leading to over-admission where more requests are allowed than the limit. The fix is to protect the refill and consume logic with a lock. For high contention, you can use an atomic compare-and-swap or a lock-free approach, but a simple mutex is sufficient for most Python applications using threading.

import time
import threading

class ThreadSafeTokenBucket:
    """Thread-safe token bucket for concurrent environments."""
    def __init__(self, capacity, refill_rate):
        self.capacity = float(capacity)
        self.refill_rate = float(refill_rate)
        self.tokens = float(capacity)
        self.last_refill = time.monotonic()
        self.lock = threading.Lock()

    def _refill_locked(self):
        now = time.monotonic()
        elapsed = now - self.last_refill
        if elapsed > 0:
            new_tokens = elapsed * self.refill_rate
            self.tokens = min(self.capacity, self.tokens + new_tokens)
            self.last_refill = now

    def allow_request(self, tokens=1):
        with self.lock:
            self._refill_locked()
            if self.tokens >= tokens:
                self.tokens -= tokens
                return True
            return False

    def get_state(self):
        with self.lock:
            self._refill_locked()
            return {"tokens": self.tokens, "capacity": self.capacity}

# Example usage with multiple threads
bucket = ThreadSafeTokenBucket(capacity=20, refill_rate=5)

def handle_request(request_id):
    if bucket.allow_request():
        print(f"Request {request_id}: ALLOWED")
    else:
        wait = bucket.get_state()["tokens"]
        print(f"Request {request_id}: DENIED - tokens left {wait:.2f}")

For distributed systems where multiple application instances share a global rate limit, an in-memory bucket is insufficient. The state must be centralized, typically in Redis or Memcached, and updated atomically using a Lua script to avoid race conditions across nodes. The script ensures that refill calculation, token check, and deduction happen as a single atomic operation.

import time
import redis

# Lua script for atomic token bucket in Redis
# KEYS[1] = bucket key, ARGV[1] = capacity, ARGV[2] = refill_rate,
# ARGV[3] = requested_tokens, ARGV[4] = now (monotonic timestamp)
REDIS_TOKEN_BUCKET_SCRIPT = """
local capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])
local requested = tonumber(ARGV[3])
local now = tonumber(ARGV[4])

local data = redis.call('HMGET', KEYS[1], 'tokens', 'last_refill')
local tokens = tonumber(data[1])
local last_refill = tonumber(data[2])

if tokens == nil then
    tokens = capacity
    last_refill = now
end

local elapsed = now - last_refill
if elapsed > 0 then
    local new_tokens = elapsed * refill_rate
    tokens = math.min(capacity, tokens + new_tokens)
    last_refill = now
end

local allowed = 0
if tokens >= requested then
    tokens = tokens - requested
    allowed = 1
end

redis.call('HMSET', KEYS[1], 'tokens', tokens, 'last_refill', last_refill)
redis.call('EXPIRE', KEYS[1], 3600)
return allowed
"""

class DistributedTokenBucket:
    def __init__(self, redis_client, key, capacity, refill_rate):
        self.redis = redis_client
        self.key = key
        self.capacity = capacity
        self.refill_rate = refill_rate
        self.script_sha = self.redis.script_load(REDIS_TOKEN_BUCKET_SCRIPT)

    def consume(self, tokens=1):
        now = time.monotonic()
        result = self.redis.evalsha(
            self.script_sha, 1, self.key,
            self.capacity, self.refill_rate, tokens, now
        )
        return bool(result == 1)

Modern asynchronous Python applications using asyncio require a non-blocking variant that does not use thread locks but instead uses asyncio primitives. This version is ideal for high-concurrency API gateways built with FastAPI or aiohttp, where thousands of concurrent coroutines share the same rate limiter without blocking the event loop.

import time
import asyncio

class AsyncTokenBucket:
    """Asyncio-compatible token bucket using continuous refill."""
    def __init__(self, capacity, refill_rate):
        self.capacity = float(capacity)
        self.refill_rate = float(refill_rate)
        self.tokens = float(capacity)
        self.last_refill = time.monotonic()
        self._lock = asyncio.Lock()

    async def _refill(self):
        now = time.monotonic()
        elapsed = now - self.last_refill
        if elapsed > 0:
            self.tokens = min(self.capacity, self.tokens + elapsed * self.refill_rate)
            self.last_refill = now

    async def acquire(self, tokens=1):
        async with self._lock:
            await self._refill()
            if self.tokens >= tokens:
                self.tokens -= tokens
                return True
            return False

    async def acquire_or_wait(self, tokens=1):
        """Wait until tokens are available, then consume."""
        while True:
            async with self._lock:
                await self._refill()
                if self.tokens >= tokens:
                    self.tokens -= tokens
                    return True
                needed = tokens - self.tokens
                wait_time = needed / self.refill_rate
            # sleep outside lock to avoid blocking others
            await asyncio.sleep(wait_time)

# Simulate bursty traffic
async def simulate():
    bucket = AsyncTokenBucket(capacity=10, refill_rate=2)
    for i in range(15):
        allowed = await bucket.acquire()
        print(f"Request {i}: {'OK' if allowed else 'RATE LIMITED'}")
        if i == 5:
            await asyncio.sleep(2)  # allow refill

4. Step-by-Step Example

To make the behavior concrete, let us walk through a detailed example with a bucket configured for capacity 10 and refill rate 2 tokens per second. We start with a full bucket at time T=0. This configuration allows a burst of 10 immediate requests and then sustains 2 requests per second on average. We will trace token count over time as requests arrive.

At T=0.0 seconds, the bucket contains 10 tokens. Five requests arrive simultaneously. Each consumes one token, leaving 5 tokens remaining. All five are allowed because tokens were available. No time has elapsed, so no refill occurs between these requests. This demonstrates the burst capability: the bucket absorbed a spike without throttling.

At T=0.5 seconds, three more requests arrive. First, we calculate refill: 0.5 seconds * 2 tokens/second = 1 token added, so the bucket goes from 5 to 6 tokens. Then we consume 3 tokens for the three requests, leaving 3 tokens. All three are allowed. At T=1.0 seconds, another 0.5 seconds has passed, adding 1 more token (3 + 1 = 4). Now six requests arrive at once, but only 4 tokens are available, so 4 are allowed and 2 are denied or delayed. The bucket is now empty (0 tokens).

Timeline Visualization

Continuing the trace, at T=2.0 seconds, one second has elapsed since the bucket was emptied, so 2 tokens have been refilled (0 + 2 = 2). Two requests arrive and both are allowed, leaving 0 tokens again. At T=5.0 seconds, three seconds have passed, so 6 tokens are added (0 + 6 = 6, capped below capacity 10). If no requests had arrived for 5 seconds, the bucket would have refilled to min(10, 0 + 10) = 10 tokens, fully recovering its burst capacity. This shows how idle periods restore burst allowance.

This walkthrough highlights two key properties. First, the long-term rate is strictly enforced: over any sufficiently long interval, the number of allowed requests cannot exceed refill_rate * interval + capacity. Second, short-term bursts are permitted but bounded by capacity, preventing both starvation of legitimate bursts and abuse by sustained high-rate clients. Tuning capacity and refill rate lets you shape this tradeoff precisely.

Notice how the token count never exceeds capacity 10, even after a long idle period. This capping is crucial; without it, a long idle period could accumulate an unbounded number of tokens and then allow an enormous burst that overwhelms downstream systems. The capacity parameter therefore acts as a safety valve for burst size.

5. Complexity Analysis

The rate limiting token bucket algorithm is prized for its constant-time performance and minimal memory footprint, which is why it can be placed directly in the hot path of high-throughput systems. Every operation, including refill calculation, token check, and deduction, is performed with a fixed number of arithmetic operations and does not depend on the number of previous requests or the size of the time window.

Time complexity for a single request is O(1) in all cases. There are no loops, no data structure traversals, and no history to scan. The refill calculation is a single multiplication and addition, and the consume check is a single comparison. This is a significant advantage over sliding window log algorithms that must iterate over or prune old entries, which can be O(n) in the number of requests in the window.

Space complexity is also O(1). The algorithm only needs to store three values: current token count (float), capacity (float), and last refill timestamp (float), plus optionally a lock. For distributed implementations, the same three values are stored per key in Redis, so memory scales as O(k) where k is the number of distinct rate limit keys (users, IPs, API keys), but per-key overhead remains constant. This makes it feasible to maintain millions of independent buckets for per-user rate limiting.

* Distributed worst case includes network round-trip latency, but computational complexity remains O(1). The Redis Lua script executes atomically and does not scale with request history.

Because both time and space are constant, the token bucket can be used for per-request rate limiting at line rate in network appliances, API gateways handling tens of thousands of requests per second, and even in kernel-level packet schedulers. The only performance consideration is lock contention in highly concurrent environments, which can be mitigated with sharding, lock-free atomics, or per-core buckets that are periodically reconciled.

6. Variations and Optimizations

While the classic token bucket is powerful, several variations adapt it to specific requirements. One common optimization is the hierarchical token bucket (HTB), widely used in Linux traffic control (tc) for quality-of-service. HTB organizes buckets in a tree where child buckets borrow tokens from parents, allowing sophisticated bandwidth sharing policies such as guaranteeing minimum rates for each class while allowing borrowing of unused capacity.

Another important variant is the greedy vs. non-greedy refill. The standard greedy version refills tokens continuously and allows immediate consumption. A non-greedy or paced version may delay refill until a full token is available or may enforce a minimum interval between allowed requests, which smooths traffic even more aggressively and is useful when downstream systems cannot handle any burst at all. This is essentially a hybrid between token bucket and leaky bucket.

For handling large bursts without starving low-rate clients, the dual token bucket or two-rate three-color marker (trTCM) defined in RFC 2698 uses two buckets: one for committed information rate (CIR) and one for peak information rate (PIR). Traffic is marked as green, yellow, or red depending on which buckets have tokens, enabling differentiated service levels where green traffic is guaranteed, yellow is best-effort, and red is dropped.

Performance Optimizations

In ultra-high-throughput scenarios, even the cost of acquiring a lock per request can be significant. Optimizations include bucket sharding where requests are hashed to one of N independent buckets, each with capacity/N and refill_rate/N, reducing contention by a factor of N. Another technique is lazy expiration where buckets for inactive users are not stored indefinitely but are garbage-collected after a TTL, preventing memory bloat when tracking millions of API keys.

For distributed rate limiting, the classic Redis Lua approach can be optimized with local caching and token prefetching. Each application node maintains a small local bucket and periodically syncs with the central Redis bucket, reducing Redis round trips by 90% or more at the cost of slight over-admission. Algorithms like the approximate token bucket or leaky bucket with local buckets formalize this tradeoff between accuracy and latency.

Finally, handling clock skew and time precision is an optimization in itself. Using integer arithmetic with microsecond precision avoids floating-point drift over long periods. Some implementations store tokens as integers representing milli-tokens and use integer division for refill, ensuring deterministic behavior across different programming languages and platforms that share the same Redis state.

7. Real-World Applications

The rate limiting token bucket is ubiquitous in production infrastructure. One of its most visible uses is in API gateways and web servers such as Nginx, Kong, AWS API Gateway, and Cloudflare. These systems enforce per-IP, per-user, or per-API-key limits to prevent abuse, ensure fair usage, and protect backend services. When a client exceeds the limit, the gateway returns HTTP 429 and may include headers like X-RateLimit-Remaining and X-RateLimit-Reset to inform clients of their quota.

In networking and telecommunications, token bucket is the standard for traffic policing and shaping. Internet Service Providers use it to enforce bandwidth contracts: a customer paying for 100 Mbps gets a token bucket where tokens represent bytes and refill rate corresponds to 100 Mbps. Switches and routers implement token bucket in hardware (ASICs) to police ingress traffic and shape egress traffic, ensuring that no single flow monopolizes link capacity. The algorithm's O(1) nature makes it suitable for implementation at line rate on 100 Gbps links.

Databases and message queues also rely on token bucket to protect themselves. For example, DynamoDB and Cassandra use token bucket to throttle clients that exceed provisioned throughput, while Kafka and RabbitMQ use it to limit producer publish rates and prevent consumer lag from growing unbounded. Without such protection, a single runaway producer could fill disks or cause out-of-memory errors.

Beyond infrastructure, token bucket is used in application-level logic. Email sending services limit how many emails a user can send per hour to prevent spam, gaming servers limit actions per second to prevent cheating, and financial trading systems limit order submissions to comply with exchange rules. Even operating systems use token bucket to limit logging rates (e.g., Linux printk rate limiting) to prevent log floods from filling disks.

The algorithm's ability to allow bursts while enforcing a long-term average makes it particularly well-suited for user-facing systems where strict fixed-window limits would create a poor user experience. For example, a user who has been idle for a while should be able to quickly load a page that requires 20 API calls, even if the sustained limit is 5 requests per second. Token bucket naturally accommodates this pattern, whereas a fixed window would arbitrarily block the burst.

8. Comparison with Alternatives

Token bucket is one of several rate limiting families, each with distinct tradeoffs in accuracy, memory, burst handling, and implementation complexity. Choosing the right algorithm depends on whether you prioritize precise limiting, burst tolerance, or simplicity. The most common alternatives are leaky bucket, fixed window counter, sliding window log, and sliding window counter.

The leaky bucket is often confused with token bucket but behaves differently: it queues requests and processes them at a constant rate, like water leaking from a bucket. If the queue is full, new requests are dropped. Leaky bucket smooths traffic to a perfectly constant rate and does not allow bursts, whereas token bucket allows bursts up to capacity. Leaky bucket is ideal for traffic shaping where you want to eliminate bursts entirely, such as smoothing video streaming, while token bucket is better for admission control where bursts are acceptable.

Fixed window counter is the simplest approach: count requests in a window (e.g., 60 seconds) and reset the counter when the window expires. It is easy to implement but suffers from the boundary burst problem where a client can send 100 requests at the end of one window and 100 at the start of the next, effectively doubling the rate for a short period. Sliding window log fixes this by storing timestamps of each request and counting how many fall within the sliding window, providing perfect accuracy but requiring O(n) memory and time. Sliding window counter approximates the sliding window by combining two fixed windows with weighted counts, offering a good balance of accuracy and efficiency.

In practice, many large-scale systems combine algorithms. For example, Cloudflare and Stripe use a combination of token bucket for per-second burst control and sliding window counter for per-minute and per-hour quotas. This layered approach provides both responsiveness to bursts and strict long-term quota enforcement. Understanding the comparison table helps you select the right tool or combination for your specific throughput, latency, and accuracy requirements.

9. Common Mistakes and Best Practices

Even though the token bucket algorithm is conceptually simple, production implementations frequently suffer from subtle bugs that undermine rate limiting guarantees. One of the most common mistakes is using wall-clock time (time.time()) instead of monotonic time. If the system clock is adjusted backward by NTP, tokens may appear to have negative refill, effectively freezing the bucket and blocking all requests. If adjusted forward, the bucket may instantly refill and allow a massive burst. Always use time.monotonic() or equivalent.

Another pitfall is not capping the bucket at capacity during refill. Without the min(capacity, ...) check, idle periods can accumulate an unbounded number of tokens, leading to an enormous burst that defeats the purpose of rate limiting. Similarly, using integer division instead of floating-point for refill can cause token starvation at low rates; for example, with refill_rate 0.5 tokens/second, integer arithmetic would add zero tokens for the first second, incorrectly throttling legitimate traffic.

Concurrency bugs are also prevalent. A naive implementation without locking can allow more requests than intended when multiple threads read the same token count simultaneously and all decide they have enough tokens. In distributed systems, failing to use atomic operations (Lua scripts, transactions) for the read-modify-write cycle leads to the same over-admission problem across nodes. Always protect the critical section with appropriate synchronization primitives.

Best Practices

• Choose capacity and refill rate deliberately: Set capacity to the maximum acceptable burst and refill rate to the sustained rate you can handle. A good starting point is capacity = refill_rate * 2 to allow a 2-second burst, then tune based on observed traffic patterns and downstream capacity.
• Return informative headers: On both success and failure, return headers such as X-RateLimit-Limit, X-RateLimit-Remaining, and Retry-After so clients can adapt their behavior without guessing. For denied requests, calculate Retry-After as (needed_tokens - current_tokens) / refill_rate.
• Implement layered limits: Enforce multiple buckets per client, for example, 10 requests/second and 1000 requests/hour. This prevents both short-term spikes and long-term abuse while still allowing reasonable bursts.
• Monitor and alert: Track metrics such as allowed vs. denied request counts, current token levels, and 429 response rates. A sudden spike in denied requests may indicate an attack or a misconfigured client, while a consistently full bucket may indicate an overly generous limit.
• Test edge cases: Unit test scenarios including concurrent access, clock jumps, zero and fractional token costs, bucket exhaustion, and long idle periods. Use deterministic time mocking to verify refill calculations precisely.
• Consider fairness: For multi-tenant systems, maintain separate buckets per tenant rather than a global bucket, and consider hierarchical buckets to guarantee minimum rates for high-priority tenants while sharing excess capacity.

Finally, remember that rate limiting is a user experience concern as well as a technical one. Provide clear error messages, documentation of limits, and client libraries that handle 429 responses with exponential backoff and jitter. A well-implemented token bucket protects your system without frustrating legitimate users.

10. Interview Questions

Rate limiting token bucket is a frequent topic in system design and algorithm interviews. Interviewers use it to assess understanding of distributed systems, concurrency, and tradeoff analysis. Below are common questions with guidance on how to structure strong answers.

Q1: Explain how token bucket works and how you would implement it in code.

A strong answer should describe the two parameters (capacity and refill rate), the lazy refill mechanism using elapsed time, and the consume check. Then sketch the code structure: store tokens, capacity, refill_rate, and last_refill timestamp; on each request, compute new_tokens = elapsed * refill_rate, update tokens = min(capacity, tokens + new_tokens), and check if tokens >= requested. Mention using monotonic time and O(1) complexity. Optionally discuss thread safety with locks or atomic operations. Interviewers look for clarity on burst vs. sustained rate and why lazy refill is efficient.

Q2: How does token bucket differ from leaky bucket, and when would you choose one over the other?

Explain that token bucket controls admission and allows bursts up to capacity, while leaky bucket queues requests and emits them at a constant rate with no bursts. Use the analogy: token bucket is like a bouncer who lets you in if you have a token, leaky bucket is like a queue that drains at a fixed rate. Choose token bucket when you want to allow bursts but limit average rate (API rate limiting), and leaky bucket when you need perfectly smooth output (video streaming, network traffic shaping). Mention that token bucket can be used for shaping by making requests wait for tokens, blurring the distinction, but their default behaviors differ.

Q3: How would you implement distributed rate limiting with token bucket across multiple servers?

Discuss the need for centralized state, typically Redis, and the race condition if you do separate GET and SET operations. Propose using a Lua script or Redis transaction to atomically refill, check, and deduct tokens. Address performance concerns: Redis becomes a bottleneck, so suggest optimizations like local caching with periodic sync, sharding by user ID, or using a token prefetch strategy where each node reserves a batch of tokens. Also mention clock synchronization issues and using server-side time or monotonic counters. For bonus points, discuss alternative approaches like using a consensus-based token service or approximate algorithms if strict accuracy is not required.

Q4: What are the time and space complexities of token bucket, and how does it compare to sliding window log?

Answer that token bucket is O(1) time and O(1) space per key because it only stores a few scalars and does constant arithmetic per request. In contrast, sliding window log stores a timestamp for every request in the window, requiring O(n) space and O(n) time to count and prune old entries, where n is the number of requests in the window. This makes token bucket far more scalable for high-throughput scenarios with many keys. Mention that sliding window log offers perfect accuracy and no burst at window boundaries, while token bucket offers high accuracy with much lower overhead, and sliding window counter is a middle ground.

Q5: How do you handle a scenario where different requests have different costs, and how do you prevent starvation?

Explain weighted token consumption where each request consumes tokens proportional to its cost, for example, a batch API call costing 10 tokens vs. a single read costing 1. The bucket logic remains the same but checks tokens >= cost. To prevent starvation where large requests are always denied because small requests keep consuming tokens, suggest options such as separate buckets for different request classes, priority queues, or reserving a portion of capacity for large requests. Also discuss setting capacity large enough to accommodate the largest expected request cost, otherwise that request would never be allowed. This shows understanding of real-world resource-based rate limiting beyond simple request counting.