Hot partition prevention in DynamoDB - Time & Space Complexity

Time Complexity: Hot partition prevention

O(n)

Understanding Time Complexity

When using DynamoDB, some partitions can get too many requests, slowing down the whole system.

We want to understand how the work grows when we try to avoid these busy spots, called hot partitions.

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

// Example: Writing items with a random suffix to avoid hot partitions
const putItem = async (item) => {
  const partitionKey = item.id + "-" + Math.floor(Math.random() * 10);
  await dynamoDb.put({
    TableName: "Orders",
    Item: { ...item, partitionKey: partitionKey }
  }).promise();
};

for (const order of orders) {
  await putItem(order);
}
    

This code adds a random number to the partition key to spread writes evenly and prevent hot partitions.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Writing each item to DynamoDB with a randomized partition key.
• How many times: Once per item in the orders list, so as many times as the number of orders.

How Execution Grows With Input

Each new order causes one write operation, but the random suffix helps spread these writes evenly.

Input Size (n)	Approx. Operations
10	10 writes spread across partitions
100	100 writes spread across partitions
1000	1000 writes spread across partitions

Pattern observation: The number of operations grows directly with the number of items, but the load is balanced to avoid slowdowns.

Final Time Complexity

Time Complexity: O(n)

This means the time to write all items grows linearly with the number of items, but spreading keys prevents slowdowns from busy partitions.

Common Mistake

[X] Wrong: "Adding a random suffix makes the operation slower because it adds extra work."

[OK] Correct: The random suffix does not add extra loops or big work; it just changes keys to spread load, keeping the overall time linear.

Interview Connect

Understanding how to prevent hot partitions shows you can design systems that stay fast even with lots of data, a key skill for real projects.

Self-Check

"What if we used a fixed partition key without randomization? How would the time complexity and performance be affected?"

Practice

1. What is the main goal of hot partition prevention in DynamoDB?

easy

A. To spread requests evenly across partitions to avoid slowdowns

B. To increase the size of each partition for more storage

C. To reduce the number of partitions to save costs

D. To backup data more frequently for safety

Solution

1. Step 1: Understand what causes hot partitions

   Hot partitions happen when too many requests target the same partition key, causing slowdowns.

2. Step 2: Identify the goal of prevention

   Prevention aims to spread requests evenly to avoid overloading any single partition.

3. Final Answer:

   To spread requests evenly across partitions to avoid slowdowns -> Option A

4. Quick Check:

   Hot partition prevention = spreading requests evenly [OK]

Hint: Think: avoid overload by spreading requests evenly [OK]

Common Mistakes:

• Confusing prevention with increasing storage size
• Thinking it reduces partitions instead of balancing load
• Assuming it relates to backup frequency

2. Which of the following is a correct way to design a partition key to prevent hot partitions?

easy

A. Use the same timestamp as the partition key for all writes

B. Use a static string as the partition key for all items

C. Add a random suffix or hash to the partition key

D. Use a sequential number as the partition key without variation

Solution

1. Step 1: Review partition key design principles

   To prevent hot partitions, keys should distribute traffic evenly, not be identical or sequential.

2. Step 2: Identify the correct method

   Adding a random suffix or hashing the key spreads requests across partitions.

3. Final Answer:

   Add a random suffix or hash to the partition key -> Option C

4. Quick Check:

   Partition key design = add randomness or hash [OK]

Hint: Add randomness or hash to partition key to balance load [OK]

Common Mistakes:

• Using static or identical keys causing hot partitions
• Using sequential keys that cluster traffic
• Ignoring the need for key variation

3. Given this partition key design: userId#randomSuffix, what is the expected effect on hot partitions?

medium

A. It will prevent hot partitions by spreading requests across suffixes

B. It will cause errors because suffixes are not allowed

C. It will cause hot partitions because all keys start with userId

D. It will reduce storage capacity of the table

Solution

1. Step 1: Analyze the key structure

   The key combines a userId with a random suffix, creating many unique partition keys.

2. Step 2: Understand impact on partitions

   Random suffixes spread requests across partitions, preventing any single hot partition.

3. Final Answer:

   It will prevent hot partitions by spreading requests across suffixes -> Option A

4. Quick Check:

   Random suffixes spread load = prevent hot partitions [OK]

Hint: Random suffixes spread requests, avoiding hot partitions [OK]

Common Mistakes:

• Assuming prefix causes hot partitions ignoring suffix effect
• Thinking suffixes cause errors in keys
• Confusing partition key design with storage limits

4. You notice a hot partition in your DynamoDB table caused by a partition key with a timestamp. What is the best fix?

medium

A. Remove the timestamp and use a static key

B. Delete old data to reduce partition size

C. Increase the read capacity units without changing keys

D. Add a hash or random suffix to the timestamp key

Solution

1. Step 1: Identify the problem with timestamp keys

   Using timestamps as keys causes many requests to target the same partition if timestamps are similar.

2. Step 2: Choose the best fix

   Adding a hash or random suffix spreads requests across partitions, preventing hot spots.

3. Final Answer:

   Add a hash or random suffix to the timestamp key -> Option D

4. Quick Check:

   Fix hot partition = add randomness to key [OK]

Hint: Add randomness to timestamp keys to fix hot partitions [OK]

Common Mistakes:

• Using static keys increases hot partition risk
• Only increasing capacity doesn't fix key design
• Deleting data doesn't solve partition key issues

5. You have a DynamoDB table with a partition key orderId that is sequential and causes hot partitions. How can you redesign the key to prevent this while keeping orderId in the key?

hard

A. Keep orderId as partition key and add a timestamp suffix

B. Use orderId as the sort key and add a hashed prefix as the partition key

C. Use only orderId as partition key without changes

D. Remove orderId and use a static string as partition key

Solution

1. Step 1: Understand the problem with sequential keys

   Sequential orderId as partition key causes hot partitions because requests cluster on recent keys.

2. Step 2: Redesign key to spread load

   Using a hashed prefix as partition key spreads requests; orderId can be used as sort key to keep uniqueness.

3. Final Answer:

   Use orderId as the sort key and add a hashed prefix as the partition key -> Option B

4. Quick Check:

   Hash prefix + orderId sort key = balanced partitions [OK]

Hint: Hash prefix partition key, keep orderId as sort key [OK]

Common Mistakes:

• Adding timestamp suffix doesn't fix partition key clustering
• Keeping orderId as partition key causes hot partitions
• Using static partition keys causes all traffic to one partition