Idempotency tokens in DynamoDB - Time & Space Complexity

Time Complexity: Idempotency tokens

O(1)

Understanding Time Complexity

When using idempotency tokens in DynamoDB, we want to understand how the time to process requests changes as more requests come in.

We ask: How does the system handle repeated requests efficiently without extra cost?

Scenario Under Consideration

Analyze the time complexity of this DynamoDB operation using an idempotency token.

// PutItem with idempotency token check
const params = {
  TableName: "Orders",
  Item: {
    "OrderId": { S: "123" },
    "IdempotencyToken": { S: "token-abc" },
    "Details": { S: "Order details" }
  },
  ConditionExpression: "attribute_not_exists(IdempotencyToken)"
};
await dynamodb.putItem(params).promise();
    

This code tries to insert an order only if the idempotency token is new, preventing duplicates.

Identify Repeating Operations

Look for repeated checks or scans in the operation.

• Primary operation: Single conditional write checking if the token exists.
• How many times: Once per request, no loops or scans involved.

How Execution Grows With Input

Each request checks the token once, regardless of how many tokens exist.

Input Size (n)	Approx. Operations
10	10 checks
100	100 checks
1000	1000 checks

Pattern observation: The time per request stays about the same, growing linearly with the number of requests but not with stored tokens.

Final Time Complexity

Time Complexity: O(1)

This means each request takes about the same time, no matter how many tokens are stored.

Common Mistake

[X] Wrong: "Checking idempotency tokens slows down as more tokens are stored because it scans the whole table."

[OK] Correct: The conditional write uses a direct key check, not a scan, so it stays fast even with many tokens.

Interview Connect

Understanding how idempotency tokens keep operations fast helps you design reliable and efficient systems, a skill valued in many real-world projects.

Self-Check

What if we replaced the conditional write with a scan to find the token? How would the time complexity change?

Practice

1. What is the main purpose of using idempotency tokens in DynamoDB operations?

easy

A. To encrypt data stored in the database

B. To prevent duplicate writes when the same request is retried

C. To speed up query performance by caching results

D. To automatically backup data at regular intervals

Solution

1. Step 1: Understand idempotency token role

   Idempotency tokens are unique values sent with requests to ensure the same operation is not applied multiple times.

2. Step 2: Identify the main benefit in DynamoDB

   This prevents duplicate writes if a request is retried due to network issues or timeouts.

3. Final Answer:

   To prevent duplicate writes when the same request is retried -> Option B

4. Quick Check:

   Idempotency tokens prevent duplicates = C [OK]

Hint: Idempotency tokens stop repeated writes on retries [OK]

Common Mistakes:

• Confusing idempotency tokens with encryption keys
• Thinking they improve query speed
• Assuming they trigger backups automatically

2. Which of the following is the correct way to include an idempotency token in a DynamoDB PutItem request using AWS SDK?

easy

A. "IdempotencyToken": "unique-token-value" inside the item attributes

B. Adding IdempotencyToken as a reserved keyword in the table schema

C. Setting IdempotencyToken as a parameter outside the item attributes

D. Using a conditional expression with attribute_not_exists(IdempotencyToken)

Solution

1. Step 1: Understand how idempotency tokens work in DynamoDB

   They are used with conditional expressions to ensure the item is only created if the token does not exist.

2. Step 2: Identify correct syntax for conditional check

   The expression attribute_not_exists(IdempotencyToken) prevents overwriting if the token is already present.

3. Final Answer:

   Using a conditional expression with attribute_not_exists(IdempotencyToken) -> Option D

4. Quick Check:

   Conditional check with attribute_not_exists = B [OK]

Hint: Use conditional expression attribute_not_exists for idempotency [OK]

Common Mistakes:

• Placing token inside item without condition causes duplicates
• Trying to set token outside request parameters incorrectly
• Assuming token is a reserved schema keyword

3. Given the following DynamoDB PutItem request with idempotency token condition:

{
  "TableName": "Orders",
  "Item": {"OrderId": {"S": "123"}, "IdempotencyToken": {"S": "abc-123"}},
  "ConditionExpression": "attribute_not_exists(IdempotencyToken)"
}

What happens if this request is sent twice with the same token?

medium

A. The first request succeeds; the second fails with a conditional check error

B. Both requests succeed and create duplicate items

C. Both requests fail due to token conflict

D. The second request overwrites the first item silently

Solution

1. Step 1: Analyze the condition expression effect

   The condition attribute_not_exists(IdempotencyToken) allows the write only if the token is not present.

2. Step 2: Predict behavior on repeated requests with same token

   The first request writes the item and token. The second request fails because the token now exists, triggering a conditional check failure.

3. Final Answer:

   The first request succeeds; the second fails with a conditional check error -> Option A

4. Quick Check:

   First write OK, second fails condition = D [OK]

Hint: Same token blocks second write with condition failure [OK]

Common Mistakes:

• Assuming both writes succeed causing duplicates
• Thinking second write silently overwrites
• Believing both writes fail

4. You wrote this DynamoDB PutItem request with idempotency token:

{
  "TableName": "Payments",
  "Item": {"PaymentId": {"S": "p001"}, "IdempotencyToken": {"S": "token-xyz"}},
  "ConditionExpression": "attribute_not_exists(IdempotencyToken)"
}

But you get a ConditionalCheckFailedException on the first request. What is the likely cause?

medium

A. An item with the same IdempotencyToken already exists in the table

B. The IdempotencyToken attribute is missing from the item

C. The table does not have a primary key defined

D. The ConditionExpression syntax is invalid

Solution

1. Step 1: Understand the meaning of ConditionalCheckFailedException

   This error means the condition attribute_not_exists(IdempotencyToken) was false, so the token attribute already exists.

2. Step 2: Identify why the first request fails

   If the token already exists in an item, the condition prevents overwriting, causing the failure.

3. Final Answer:

   An item with the same IdempotencyToken already exists in the table -> Option A

4. Quick Check:

   Token exists causes condition failure = A [OK]

Hint: Condition fails if token already exists in table [OK]

Common Mistakes:

• Assuming missing token causes this error
• Thinking primary key absence triggers this error
• Believing condition syntax is wrong

5. You want to design a DynamoDB table to support idempotent order creation using tokens. Which approach best ensures no duplicate orders are created when clients retry requests?

hard

A. Use a composite primary key with OrderId and IdempotencyToken and allow overwrites

B. Use OrderId as the primary key and store IdempotencyToken as a unique attribute with a conditional write checking attribute_not_exists(IdempotencyToken)

C. Use IdempotencyToken as the primary key and reject writes if the token exists

D. Do not store tokens; rely on client-side checks to avoid duplicates

Solution

1. Step 1: Consider uniqueness enforcement for idempotency

   Using IdempotencyToken as the primary key ensures each token is unique and prevents duplicates at the database level.

2. Step 2: Evaluate other options

   Use OrderId as the primary key and store IdempotencyToken as a unique attribute with a conditional write checking attribute_not_exists(IdempotencyToken) risks duplicates if tokens are not primary keys. Use a composite primary key with OrderId and IdempotencyToken and allow overwrites allows overwrites, breaking idempotency. Do not store tokens; rely on client-side checks to avoid duplicates relies on unreliable client checks.

3. Final Answer:

   Use IdempotencyToken as the primary key and reject writes if the token exists -> Option C

4. Quick Check:

   Primary key on token ensures uniqueness = A [OK]

Hint: Make token primary key to enforce uniqueness [OK]

Common Mistakes:

• Storing token as non-key attribute without condition
• Allowing overwrites with composite keys
• Relying only on client-side checks