ETag for conditional requests in Rest API - Time & Space Complexity

Time Complexity: ETag for conditional requests

O(n)

Understanding Time Complexity

When using ETags for conditional requests, we want to understand how the server's work changes as the number of requests or resources grows.

How does the server's processing time grow when checking ETags for many requests?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Pseudocode for handling a conditional GET request with ETag
function handleRequest(request) {
  resource = getResource(request.url)
  clientETag = request.headers['If-None-Match']
  serverETag = generateETag(resource)

  if (clientETag === serverETag) {
    return 304; // Not Modified
  } else {
    return 200; // OK with resource
  }
}
    

This code checks if the client's ETag matches the server's current ETag for a resource to decide if the full data needs to be sent.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Generating the ETag for the requested resource.
• How many times: Once per request, for each resource requested.

How Execution Grows With Input

Each request requires generating an ETag, which depends on the resource size.

Input Size (resource size)	Approx. Operations
Small (10 KB)	Low operations to hash or check content
Medium (100 KB)	More operations, roughly 10 times more than small
Large (1 MB)	Much more operations, about 100 times more than small

Pattern observation: The time to generate an ETag grows roughly in proportion to the size of the resource.

Final Time Complexity

Time Complexity: O(n)

This means the time to process a request grows linearly with the size of the resource being checked.

Common Mistake

[X] Wrong: "ETag checking is always instant and does not depend on resource size."

[OK] Correct: Generating or verifying an ETag often requires reading or hashing the resource, which takes more time for bigger resources.

Interview Connect

Understanding how ETag checks scale helps you explain efficient caching strategies and server load management in real projects.

Self-Check

"What if the server cached ETags instead of generating them on every request? How would the time complexity change?"

Practice

1.

What is the main purpose of an ETag in REST APIs?

easy

A. To help clients check if the resource has changed since last fetch

B. To encrypt the data sent from server to client

C. To authenticate the client making the request

D. To specify the content type of the response

Solution

1. Step 1: Understand ETag role in REST

   ETags are unique identifiers for resource versions, used to detect changes.

2. Step 2: Match purpose with options

   Only To help clients check if the resource has changed since last fetch describes checking if resource changed, which is the ETag's purpose.

3. Final Answer:

   To help clients check if the resource has changed since last fetch -> Option A

4. Quick Check:

   ETag purpose = freshness check [OK]

Hint: ETags track changes, not encrypt or authenticate [OK]

Common Mistakes:

• Confusing ETag with authentication tokens
• Thinking ETag encrypts data
• Assuming ETag sets content type

2.

Which HTTP header should a client send to make a conditional GET request using an ETag?

easy

A. If-Modified-Since

B. If-None-Match

C. ETag

D. Cache-Control

Solution

1. Step 1: Identify client header for ETag conditional requests

   The client sends If-None-Match header with the ETag value to check freshness.

2. Step 2: Compare options

   If-Modified-Since uses dates, ETag is a response header, Cache-Control controls caching rules. Only If-None-Match fits.

3. Final Answer:

   If-None-Match -> Option B

4. Quick Check:

   Client uses If-None-Match for ETag check [OK]

Hint: Client sends If-None-Match with ETag to check freshness [OK]

Common Mistakes:

• Using ETag header in request instead of response
• Confusing If-Modified-Since with ETag usage
• Sending Cache-Control instead of conditional header

3.

Given this HTTP interaction:
GET /resource HTTP/1.1
Host: example.com
If-None-Match: "abc123"
Server responds:
HTTP/1.1 304 Not Modified
What does this response mean?

medium

A. The resource has changed and new data is sent

B. The server encountered an error

C. The resource has not changed; client should use cached data

D. The request is unauthorized

Solution

1. Step 1: Understand 304 Not Modified status

   304 means resource is unchanged since client's ETag, so no new data sent.

2. Step 2: Match meaning with options

   The resource has not changed; client should use cached data correctly states client should use cached data because resource is unchanged.

3. Final Answer:

   The resource has not changed; client should use cached data -> Option C

4. Quick Check:

   304 = Not Modified, use cache [OK]

Hint: 304 means no change; use cached copy [OK]

Common Mistakes:

• Thinking 304 means new data sent
• Confusing 304 with error or unauthorized status
• Ignoring ETag and caching role

4.

Consider this server code snippet handling ETags:

etag = generate_etag(resource)
if request.headers.get('If-None-Match') == etag:
    return Response(status=304)
else:
    return Response(data=resource, headers={'ETag': etag})

What is a potential bug in this code?

medium

A. It compares ETag strings without quotes, causing mismatch

B. It returns 304 even if ETag does not match

C. It does not handle If-Modified-Since header

D. It always returns data ignoring conditional requests

Solution

1. Step 1: Analyze ETag comparison

   ETags in headers often include quotes, so direct string equality may fail if quotes differ.

2. Step 2: Identify mismatch cause

   If client sends "abc123" but server etag is abc123 without quotes, comparison fails incorrectly.

3. Final Answer:

   It compares ETag strings without quotes, causing mismatch -> Option A

4. Quick Check:

   ETag quotes matter in comparison [OK]

Hint: ETag strings must match exactly including quotes [OK]

Common Mistakes:

• Ignoring quotes around ETag values
• Assuming If-Modified-Since is required for ETag logic
• Returning 304 without checking ETag

5.

You want to optimize your REST API to reduce bandwidth by using ETags. Which approach correctly implements conditional GET requests with ETags?

1. Server generates ETag for resource.
2. Server sends ETag in response header.
3. Client stores ETag.
4. Client sends GET with If-None-Match header.
5. Server compares ETag and returns 304 if unchanged.
6. Otherwise, server sends new data with new ETag.

Which step is missing or incorrect?

hard

A. Step 6: Server should always send 200 status even if unchanged

B. Step 4: Client should send If-Modified-Since instead of If-None-Match

C. Step 3: Client should not store ETag

D. Step 5: Server must compare ETag including quotes exactly

Solution

1. Step 1: Review each step for correctness

   Steps 1-4 are correct standard flow for ETag conditional requests.

2. Step 2: Identify subtle issue in step 5

   Server must compare ETag values exactly, including quotes, or else conditional check fails.

3. Step 3: Confirm other options are incorrect

   Client should store ETag (step 3), If-None-Match is correct header (step 4), and 304 status is correct for unchanged (step 6).

4. Final Answer:

   Step 5: Server must compare ETag including quotes exactly -> Option D

5. Quick Check:

   Exact ETag match including quotes is required [OK]

Hint: ETag comparison must be exact including quotes [OK]

Common Mistakes:

• Ignoring quotes in ETag comparison
• Using wrong conditional header
• Sending 200 instead of 304 for unchanged resource