Idempotency keys for safe retries in Rest API - Time & Space Complexity

Time Complexity: Idempotency keys for safe retries

O(1)

Understanding Time Complexity

When using idempotency keys in APIs, we want to know how the system handles repeated requests efficiently.

We ask: how does the time to process requests grow when retries happen?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Pseudocode for handling idempotent requests
function handleRequest(request) {
  if (cache.has(request.idempotencyKey)) {
    return cache.get(request.idempotencyKey);  // Return cached response
  }
  let response = processRequest(request);  // Process new request
  cache.set(request.idempotencyKey, response);  // Save response
  return response;
}
    

This code checks if a request with the same idempotency key was handled before. If yes, it returns the saved response. Otherwise, it processes the request and saves the result.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Checking and retrieving from the cache (usually a hash map or dictionary).
• How many times: Once per request, whether retry or new.

How Execution Grows With Input

As the number of unique idempotency keys grows, the cache size grows, but each lookup stays fast.

Input Size (n)	Approx. Operations
10	10 cache lookups, mostly fast
100	100 cache lookups, still fast
1000	1000 cache lookups, still fast

Pattern observation: Each request requires a single quick lookup, so time grows linearly with requests but each lookup is constant time.

Final Time Complexity

Time Complexity: O(1)

This means each request, including retries, is handled in constant time due to fast cache lookups.

Common Mistake

[X] Wrong: "Each retry causes the whole request to be processed again, so time grows with retries."

[OK] Correct: The idempotency key cache prevents reprocessing by returning saved results instantly, so retries do not add processing time.

Interview Connect

Understanding how idempotency keys keep retries efficient shows you grasp safe API design and performance, a valuable skill in real projects.

Self-Check

"What if the cache lookup was implemented as a list search instead of a hash map? How would the time complexity change?"

Practice

1. What is the main purpose of using an idempotency key in REST APIs?

easy

A. To speed up the server response time

B. To prevent duplicate processing of the same request

C. To encrypt the request data

D. To authenticate the user

Solution

1. Step 1: Understand idempotency key concept

   An idempotency key is a unique identifier sent with a request to ensure the server processes it only once.

2. Step 2: Identify the main purpose

   This prevents duplicate actions like double payments or repeated orders if the client retries the request.

3. Final Answer:

   To prevent duplicate processing of the same request -> Option B

4. Quick Check:

   Idempotency key = prevent duplicates [OK]

Hint: Idempotency keys stop repeated actions safely [OK]

Common Mistakes:

• Confusing idempotency key with authentication token
• Thinking it speeds up response time
• Assuming it encrypts data

2. Which HTTP header is commonly used to send an idempotency key in a REST API request?

easy

A. Idempotency-Key

B. Cache-Control

C. Content-Type

D. Authorization

Solution

1. Step 1: Recall standard header for idempotency

   The standard practice is to send the unique idempotency key in the Idempotency-Key HTTP header.

2. Step 2: Differentiate from other headers

   Authorization is for credentials, Content-Type defines data format, and Cache-Control manages caching.

3. Final Answer:

   Idempotency-Key -> Option A

4. Quick Check:

   Idempotency key header = Idempotency-Key [OK]

Hint: Idempotency keys go in Idempotency-Key header [OK]

Common Mistakes:

• Using Authorization header for idempotency key
• Confusing Content-Type with idempotency key
• Sending key in request body instead of header

3. Consider this simplified server logic for handling POST requests with idempotency keys:

stored_keys = {}

def handle_request(idempotency_key, data):
    if idempotency_key in stored_keys:
        return stored_keys[idempotency_key]
    response = process_data(data)
    stored_keys[idempotency_key] = response
    return response

# Client sends:
print(handle_request('abc123', 'order1'))
print(handle_request('abc123', 'order1'))
print(handle_request('xyz789', 'order2'))

What will be the output?

medium

A. None, None, None

B. process_data output for order1, None, process_data output for order2

C. process_data output for order1, process_data output for order2, process_data output for order2

D. process_data output for order1, process_data output for order1, process_data output for order2

Solution

1. Step 1: Analyze first call with key 'abc123'

   Key not in stored_keys, so process_data('order1') runs, result saved and returned.

2. Step 2: Analyze second call with same key 'abc123'

   Key found, stored response returned without reprocessing.

3. Step 3: Analyze third call with new key 'xyz789'

   Key not found, process_data('order2') runs, result saved and returned.

4. Final Answer:

   process_data output for order1, process_data output for order1, process_data output for order2 -> Option D

5. Quick Check:

   Repeated key returns cached response [OK]

Hint: Repeated keys return cached response, new keys process data [OK]

Common Mistakes:

• Assuming second call reprocesses data
• Confusing keys and responses
• Thinking None is returned on repeats

4. A developer wrote this code snippet to handle idempotent POST requests:

cache = {}
def post_request(key, data):
    if key not in cache:
        process(data)
    return cache[key]

What is the bug in this code?

medium

A. It never stores the processed result in cache

B. It processes data twice for the same key

C. It raises an error if key is missing

D. It uses the wrong HTTP method

Solution

1. Step 1: Check caching logic

   The code checks if key not in cache, then calls process(data), but never saves the result in cache.

2. Step 2: Identify consequence

   Since cache[key] is never set, returning cache[key] will cause a KeyError or return None incorrectly.

3. Final Answer:

   It never stores the processed result in cache -> Option A

4. Quick Check:

   Missing cache storage causes errors [OK]

Hint: Always save processed result in cache before returning [OK]

Common Mistakes:

• Assuming process(data) stores result automatically
• Ignoring missing cache assignment
• Thinking HTTP method affects caching here

5. You are designing a payment API that uses idempotency keys to avoid duplicate charges. Which approach best ensures safe retries without charging twice if the client resends the same request due to a timeout?

hard

A. Ignore the idempotency key and process every request independently

B. Reject any request with an idempotency key that was seen before

C. Store the payment result linked to the idempotency key and return it on repeated requests

D. Process the payment again but log a warning for duplicate keys

Solution

1. Step 1: Understand safe retry requirements

   Safe retries mean the client can resend the same request without causing duplicate charges.

2. Step 2: Evaluate options

   Store the payment result linked to the idempotency key and return it on repeated requests stores the payment result linked to the key and returns it on repeats, preventing double charges. Ignore the idempotency key and process every request independently processes every request, risking duplicates. Reject any request with an idempotency key that was seen before rejects repeats, which may cause client errors. Process the payment again but log a warning for duplicate keys processes again, causing duplicates.

3. Final Answer:

   Store the payment result linked to the idempotency key and return it on repeated requests -> Option C

4. Quick Check:

   Store and reuse result for idempotency [OK]

Hint: Save and reuse payment result by key to avoid duplicates [OK]

Common Mistakes:

• Rejecting repeated keys causing client errors
• Processing duplicates causing double charges
• Logging warnings but still charging twice