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?"