Why rate limiting protects services in Rest API - Performance Analysis

Time Complexity: Why rate limiting protects services

O(n)

Understanding Time Complexity

When we protect services with rate limiting, we want to see how the cost of handling requests grows as more users send requests.

We ask: How does the system's work increase when many requests come in?

Scenario Under Consideration

Analyze the time complexity of the following rate limiting check.

// Pseudocode for rate limiting check
function checkRateLimit(userId, timestamp) {
  requests = getRequestsForUser(userId)  // list of past request times
  recentRequests = filter(requests, r => r > timestamp - window)
  if (recentRequests.length > limit) {
    return false  // block request
  }
  addRequest(userId, timestamp)
  return true  // allow request
}
    

This code checks how many requests a user made recently and blocks if too many.

Identify Repeating Operations

Look for repeated work done each time a request comes in.

• Primary operation: Filtering the user's past requests to find recent ones.
• How many times: This filtering happens every time a new request arrives.

How Execution Grows With Input

As the number of requests a user makes grows, the filtering step takes longer.

Input Size (n)	Approx. Operations
10	Check 10 past requests
100	Check 100 past requests
1000	Check 1000 past requests

Pattern observation: The work grows directly with how many past requests are stored.

Final Time Complexity

Time Complexity: O(n)

This means the time to check rate limits grows linearly with the number of stored requests.

Common Mistake

[X] Wrong: "Rate limiting always takes constant time no matter how many requests."

[OK] Correct: Because filtering past requests depends on how many requests are stored, the time can grow as more requests accumulate.

Interview Connect

Understanding how rate limiting scales helps you design services that stay fast and reliable even when many users send requests.

Self-Check

"What if we stored only the count of requests instead of the full list? How would the time complexity change?"

Practice

1. What is the main purpose of rate limiting in REST APIs?

easy

A. To store user data securely

B. To speed up the response time of the server

C. To control how many requests a user can make in a set time

D. To allow unlimited access to all users

Solution

1. Step 1: Understand what rate limiting does

   Rate limiting sets a maximum number of requests a user can make in a certain time period.

2. Step 2: Identify the main goal of rate limiting

   This helps protect the service from overload and unfair use by controlling request frequency.

3. Final Answer:

   To control how many requests a user can make in a set time -> Option C

4. Quick Check:

   Rate limiting = controlling request count [OK]

Hint: Rate limiting limits request count per time [OK]

Common Mistakes:

• Thinking rate limiting speeds up server
• Confusing rate limiting with data storage
• Believing rate limiting allows unlimited access

2. Which of the following is a correct way to express a rate limit header in an HTTP response?

easy

A. X-Limit-Rate: 1000 requests

B. X-RateLimit-Limit: 1000

C. Limit-Rate: 1000

D. RateLimit: 1000 per minute

Solution

1. Step 1: Recall standard rate limit header names

   The common header to indicate rate limits is X-RateLimit-Limit.

2. Step 2: Check the format correctness

   X-RateLimit-Limit: 1000 uses the correct header name and a numeric limit value, which is standard.

3. Final Answer:

   X-RateLimit-Limit: 1000 -> Option B

4. Quick Check:

   Standard header = X-RateLimit-Limit [OK]

Hint: Look for standard header names starting with X-RateLimit [OK]

Common Mistakes:

• Using incorrect header names like RateLimit or Limit-Rate
• Adding extra words in header value
• Confusing header format with body content

3. Consider this pseudocode for a rate limiter:

requests = 0
limit = 3
for request in incoming_requests:
    if requests < limit:
        process(request)
        requests += 1
    else:
        reject(request)

What happens when 5 requests arrive quickly?

medium

A. Only 3 requests are processed; 2 are rejected

B. All 5 requests are processed

C. No requests are processed

D. Only the first request is processed; others are rejected

Solution

1. Step 1: Understand the limit and counter

   The limit is 3, and requests start at 0. Each processed request increments the counter.

2. Step 2: Trace the 5 incoming requests

   First 3 requests meet requests < limit, so processed. The 4th and 5th exceed limit, so rejected.

3. Final Answer:

   Only 3 requests are processed; 2 are rejected -> Option A

4. Quick Check:

   Limit 3 means max 3 processed [OK]

Hint: Count processed requests up to limit, reject rest [OK]

Common Mistakes:

• Assuming all requests are processed
• Ignoring the requests counter increment
• Thinking only one request is allowed

4. This code snippet tries to implement rate limiting but has a bug:

requests = 0
limit = 2
for req in requests_list:
    if requests > limit:
        reject(req)
    else:
        process(req)
        requests += 1

What is the bug?

medium

A. The condition should be requests < limit, not requests > limit

B. The requests counter is not incremented

C. The loop variable name conflicts with requests

D. The limit value is too high

Solution

1. Step 1: Analyze the if condition logic

   The code rejects requests when requests > limit, but it should allow requests while requests < limit.

2. Step 2: Understand correct rate limiting condition

   To process requests up to the limit, the condition must check if requests < limit before processing.

3. Final Answer:

   The condition should be requests < limit, not requests > limit -> Option A

4. Quick Check:

   Process if requests < limit [OK]

Hint: Check if condition matches 'less than limit' to process [OK]

Common Mistakes:

• Using greater than instead of less than in condition
• Forgetting to increment requests counter
• Confusing variable names in loop

5. A REST API uses rate limiting to allow 5 requests per minute per user. If a user sends 3 requests in the first 10 seconds and 4 more in the next 30 seconds, what should happen to the last 2 requests?

hard

A. They are processed normally because total is under 10

B. They are delayed until the next minute starts

C. They reset the counter and are processed immediately

D. They are rejected because the 5 requests per minute limit is exceeded

Solution

1. Step 1: Calculate total requests in one minute

   User sends 3 + 4 = 7 requests within one minute, exceeding the 5 request limit.

2. Step 2: Understand rate limiting enforcement

   Requests beyond the limit (the last 2) should be rejected to protect the service.

3. Final Answer:

   They are rejected because the 5 requests per minute limit is exceeded -> Option D

4. Quick Check:

   Requests > 5 per minute are rejected [OK]

Hint: Count requests per minute; reject if over limit [OK]

Common Mistakes:

• Assuming requests reset automatically before a minute
• Thinking all requests are accepted if under 10
• Believing requests are delayed instead of rejected