Token bucket algorithm in Rest API - Mini Project: Build & Apply

Token Bucket Algorithm Implementation

📖 Scenario: You are building a simple rate limiter for an API using the token bucket algorithm. This algorithm controls how many requests a user can make in a given time by using tokens that refill over time.

🎯 Goal: Create a Python program that simulates a token bucket rate limiter. You will set up the initial bucket, configure the refill rate, implement the token consumption logic, and finally print whether a request is allowed or denied based on available tokens.

📋 What You'll Learn

Create a dictionary called token_bucket with keys 'capacity' and 'tokens' set to 10 and 10 respectively.

Create a variable called refill_rate and set it to 2 (tokens per second).

Write a function called consume_tokens that takes tokens_needed and reduces tokens if enough are available, returning True if allowed, False otherwise.

Print the result of calling consume_tokens(5).

💡 Why This Matters

🌍 Real World

Token bucket algorithms are used in APIs and networks to limit how many requests or data packets can be processed in a given time, preventing overload.

💼 Career

Understanding rate limiting is important for backend developers and network engineers to build reliable and fair services.

1

Set up the token bucket dictionary

Create a dictionary called token_bucket with keys 'capacity' and 'tokens' both set to 10.

Rest API

# Create the token_bucket dictionary with 'capacity' and 'tokens' set to 10
# Your code here

Hint

Use curly braces to create a dictionary with the exact keys and values.

2

Add the refill rate variable

Create a variable called refill_rate and set it to 2.

Rest API

token_bucket = {'capacity': 10, 'tokens': 10}
# Create the refill_rate variable and set it to 2
# Your code here

Hint

Just assign the number 2 to the variable named refill_rate.

3

Write the token consumption function

Write a function called consume_tokens that takes a parameter tokens_needed. Inside, check if token_bucket['tokens'] is at least tokens_needed. If yes, subtract tokens_needed from token_bucket['tokens'] and return True. Otherwise, return False.

Rest API

token_bucket = {'capacity': 10, 'tokens': 10}
refill_rate = 2
# Define the consume_tokens function below
# Your code here

Hint

Use an if-else statement to check tokens and update the dictionary.

4

Print the result of token consumption

Print the result of calling consume_tokens(5).

Rest API

token_bucket = {'capacity': 10, 'tokens': 10}
refill_rate = 2

def consume_tokens(tokens_needed):
    if token_bucket['tokens'] >= tokens_needed:
        token_bucket['tokens'] -= tokens_needed
        return True
    else:
        return False

# Print the result of consume_tokens(5) below
# Your code here

Hint

Use the print function to show the result of consume_tokens(5).

Practice

1.

What is the main purpose of the token bucket algorithm in REST APIs?

easy

A. To encrypt API responses

B. To store user data securely

C. To control the rate of incoming requests by using tokens

D. To manage database connections

Solution

1. Step 1: Understand the token bucket algorithm concept

   The token bucket algorithm limits how many requests can be processed by controlling tokens that refill over time.

2. Step 2: Identify the purpose in REST APIs

   It helps prevent too many requests at once, protecting the server from overload.

3. Final Answer:

   To control the rate of incoming requests by using tokens -> Option C

4. Quick Check:

   Token bucket controls request rate = C [OK]

Hint: Token bucket limits request rate using tokens [OK]

Common Mistakes:

• Confusing token bucket with data storage
• Thinking it encrypts data
• Assuming it manages database connections

2.

Which of the following is the correct way to represent a token bucket refill rate in pseudocode?

1. refill_rate = tokens_per_second
2. refill_rate = seconds_per_token
3. refill_rate = max_tokens * time
4. refill_rate = tokens / max_tokens

easy

A. refill_rate = seconds_per_token

B. refill_rate = tokens_per_second

C. refill_rate = max_tokens * time

D. refill_rate = tokens / max_tokens

Solution

1. Step 1: Understand refill rate meaning

   The refill rate is how many tokens are added per second to the bucket.

2. Step 2: Match with options

   refill_rate = tokens_per_second correctly shows tokens added per second, which is the refill rate.

3. Final Answer:

   refill_rate = tokens_per_second -> Option B

4. Quick Check:

   Refill rate = tokens per second [OK]

Hint: Refill rate means tokens added each second [OK]

Common Mistakes:

• Confusing refill rate with time per token
• Multiplying max tokens by time incorrectly
• Using ratios instead of rates

3.

Given a token bucket with max_tokens = 5, refill_rate = 1 token/second, and an empty bucket at time 0, what is the number of tokens available at time 3 seconds?

medium

A. 3 tokens

B. 5 tokens

C. 0 tokens

D. 1 token

Solution

1. Step 1: Calculate tokens refilled after 3 seconds

   Since refill rate is 1 token per second, after 3 seconds, 3 tokens are added.

2. Step 2: Check max tokens limit

   The bucket max is 5 tokens, so 3 tokens fit without exceeding the max.

3. Final Answer:

   3 tokens -> Option A

4. Quick Check:

   3 seconds * 1 token/sec = 3 tokens [OK]

Hint: Multiply seconds by refill rate, cap at max tokens [OK]

Common Mistakes:

• Assuming bucket fills instantly to max
• Ignoring max token limit
• Using refill rate incorrectly

4.

Consider this pseudocode snippet for token bucket check:
if tokens <= 0:
  reject_request()
else:
  tokens -= 1
  allow_request()
What is the bug in this logic?

medium

A. It should check if tokens > 0 before allowing

B. It should increase tokens instead of decreasing

C. It should reject when tokens > 0

D. It should check if tokens < 1, not <= 0

Solution

1. Step 1: Recall proper token bucket logic

   To consume 1 token, check if tokens >= 1 before decrementing (equivalent to reject if tokens < 1).

2. Step 2: Identify the bug

   The code rejects only if tokens <= 0. For fractional tokens (common in real implementations), if 0 < tokens < 1, it allows the request, decrementing to negative, which is incorrect.

3. Final Answer:

   It should check if tokens < 1, not <= 0 -> Option D

4. Quick Check:

   Reject if tokens < 1 [OK]

Hint: Allow only if tokens >= 1 [OK]

Common Mistakes:

• Using <= 0 instead of < 1 causes off-by-one errors
• Increasing tokens on request instead of decreasing
• Rejecting requests when tokens are available

5.

You want to implement a token bucket that allows bursts of up to 10 requests and refills tokens at 2 tokens per second. If a client sends 15 requests instantly after being idle for 3 seconds, how many requests will be allowed immediately?

hard

A. 6 requests

B. 5 requests

C. 15 requests

D. 10 requests

Solution

1. Step 1: Calculate tokens available after 3 seconds idle

   Refill rate is 2 tokens/second, so after 3 seconds: 2 * 3 = 6 tokens. Max tokens allowed is 10, so bucket fills to 6 tokens.

2. Step 2: Consider burst capacity

   Since the bucket max is 10, if it was full before idle, it would have 10 tokens. But starting empty, after 3 seconds it has 6 tokens.

3. Step 3: Determine allowed requests

   The client sends 15 requests instantly, but only 6 tokens are available, so only 6 requests allowed immediately.

4. Final Answer:

   6 requests -> Option A

5. Quick Check:

   3 sec * 2 tokens/sec = 6 tokens available [OK]

Hint: Tokens = min(max_tokens, refill_rate * idle_time) [OK]

Common Mistakes:

• Assuming bucket always full at max tokens
• Allowing more requests than tokens available
• Ignoring refill rate and idle time