Batch limits and retries in DynamoDB - Time & Space Complexity

Time Complexity: Batch limits and retries

O(n)

Understanding Time Complexity

When working with DynamoDB batch operations, it is important to understand how the time to complete requests changes as the number of items grows.

We want to know how batch limits and retries affect the total time taken.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Batch write items with retry on unprocessed items
const batchWrite = async (items) => {
  const BATCH_SIZE = 25;
  let batches = [];
  for (let i = 0; i < items.length; i += BATCH_SIZE) {
    batches.push(items.slice(i, i + BATCH_SIZE).map(item => ({ PutRequest: { Item: item } })));
  }

  for (const batch of batches) {
    let unprocessed = batch;
    while (unprocessed.length > 0) {
      const response = await dynamoDB.batchWrite({ RequestItems: { "MyTable": unprocessed } }).promise();
      unprocessed = response.UnprocessedItems["MyTable"] || [];
    }
  }
};
    

This code splits items into batches of 25, sends each batch, and retries any unprocessed items until all are written.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Sending batch write requests to DynamoDB.
• How many times: Once per batch, plus additional retries for unprocessed items.
• The outer loop splits items into batches of 25, so it runs about n/25 times.
• The inner while loop retries unprocessed items until none remain, repeating as needed.

How Execution Grows With Input

As the number of items grows, the number of batches grows roughly in proportion.

Input Size (n)	Approx. Batch Requests
10	1 batch (no retries if all succeed)
100	4 batches (each up to 25 items)
1000	40 batches

Pattern observation: The number of batch requests grows linearly with input size, but retries can add extra requests depending on unprocessed items.

Final Time Complexity

Time Complexity: O(n)

This means the total time grows roughly in direct proportion to the number of items being processed.

Common Mistake

[X] Wrong: "Batch writes always complete in a single request regardless of input size."

[OK] Correct: DynamoDB limits batch writes to 25 items per request, and unprocessed items cause retries, so multiple requests are needed as input grows.

Interview Connect

Understanding how batch limits and retries affect performance shows you can handle real-world API constraints and design efficient data operations.

Self-Check

"What if the batch size limit changed from 25 to 50? How would the time complexity change?"

Practice

1. What is the main reason DynamoDB enforces batch limits when using batch write operations?

easy

A. To allow unlimited retries automatically

B. To increase the size of each item stored

C. To prevent sending too many items at once and avoid throttling

D. To reduce the number of tables in the database

Solution

1. Step 1: Understand batch write limits

   DynamoDB limits batch write operations to a maximum of 25 items per request to avoid overloading the service.

2. Step 2: Reason about the purpose of limits

   These limits help prevent throttling and ensure stable performance by controlling request size.

3. Final Answer:

   To prevent sending too many items at once and avoid throttling -> Option C

4. Quick Check:

   Batch limits = prevent throttling [OK]

Hint: Batch limits protect DynamoDB from overloads [OK]

Common Mistakes:

• Thinking batch limits increase item size
• Assuming retries are automatic without checks
• Confusing batch limits with table count

2. Which of the following is the correct maximum number of items you can send in a single BatchWriteItem request in DynamoDB?

easy

A. 25 items

B. 50 items

C. 100 items

D. 10 items

Solution

1. Step 1: Recall DynamoDB batch write limits

   DynamoDB allows a maximum of 25 items per BatchWriteItem request.

2. Step 2: Compare options with the limit

   Only 25 items matches the correct limit of 25 items.

3. Final Answer:

   25 items -> Option A

4. Quick Check:

   BatchWriteItem max = 25 items [OK]

Hint: Remember 25 items max per batch write [OK]

Common Mistakes:

• Choosing 50 or 100 items which exceed the limit
• Confusing batch write with batch get limits
• Assuming 10 items is the max without checking docs

3. Consider this Python snippet using boto3 DynamoDB client:

response = client.batch_write_item(RequestItems={
  'MyTable': [
    {'PutRequest': {'Item': {'ID': {'S': '1'}}}},
    {'PutRequest': {'Item': {'ID': {'S': '2'}}}}
  ]
})
print(response.get('UnprocessedItems'))

If the response prints {}, what does it mean?

medium

A. The batch write failed completely

B. The request exceeded batch limits

C. Only the first item was processed

D. All items were processed successfully with no retries needed

Solution

1. Step 1: Understand UnprocessedItems meaning

   The UnprocessedItems key contains items that DynamoDB did not process and need retrying.

2. Step 2: Interpret empty dictionary response

   An empty dictionary {} means no unprocessed items, so all were processed successfully.

3. Final Answer:

   All items were processed successfully with no retries needed -> Option D

4. Quick Check:

   Empty UnprocessedItems = all processed [OK]

Hint: Empty UnprocessedItems means success [OK]

Common Mistakes:

• Assuming empty means failure
• Thinking only partial items processed
• Confusing batch limits with processing status

4. You wrote code to batch write 30 items to DynamoDB but got an error. Which fix will solve the problem?

medium

A. Split the 30 items into two batches of 25 and 5 items

B. Send all 30 items in one batch and increase timeout

C. Use batch get instead of batch write

D. Reduce each item size to half

Solution

1. Step 1: Identify batch write limit violation

   DynamoDB batch write limits max 25 items per request, so 30 items exceed this limit.

2. Step 2: Apply correct fix by splitting batches

   Splitting into two batches (25 and 5) respects the limit and avoids errors.

3. Final Answer:

   Split the 30 items into two batches of 25 and 5 items -> Option A

4. Quick Check:

   Split batches to respect 25 item limit [OK]

Hint: Split batches over 25 items to fix errors [OK]

Common Mistakes:

• Trying to send all items at once ignoring limits
• Using batch get which is for reads, not writes
• Reducing item size does not fix batch count limit

5. You have a batch write operation that returns some unprocessed items due to throttling. What is the best approach to ensure all items are eventually written?

hard

A. Retry the entire batch including processed items

B. Immediately retry only the unprocessed items with exponential backoff

C. Ignore unprocessed items and assume they are saved

D. Increase the batch size to include more items

Solution

1. Step 1: Understand unprocessed items cause

   Unprocessed items occur when DynamoDB throttles requests; these items need retrying.

2. Step 2: Apply best retry strategy

   Retry only unprocessed items with exponential backoff to avoid repeated throttling and ensure eventual success.

3. Final Answer:

   Immediately retry only the unprocessed items with exponential backoff -> Option B

4. Quick Check:

   Retry unprocessed items with backoff [OK]

Hint: Retry unprocessed items with backoff, not whole batch [OK]

Common Mistakes:

• Ignoring unprocessed items causing data loss
• Retrying entire batch wastes resources
• Increasing batch size worsens throttling