Write sharding in DynamoDB - Time & Space Complexity

Time Complexity: Write sharding

O(n)

Understanding Time Complexity

When we write data to a DynamoDB table using sharding, we split the data across multiple partitions.

We want to understand how the time to write grows as we add more data and shards.

Scenario Under Consideration

Analyze the time complexity of this write sharding example.

// Pseudocode for write sharding in DynamoDB
for each item in data:
  shard_key = hash(item.id) % number_of_shards
  dynamodb.put_item(TableName, Item with shard_key)
    

This code writes each item to a shard determined by hashing its ID.

Identify Repeating Operations

Look at what repeats as data grows.

• Primary operation: Writing each item to DynamoDB with a shard key.
• How many times: Once per item in the data set.

How Execution Grows With Input

As the number of items grows, the number of writes grows the same way.

Input Size (n)	Approx. Operations
10	10 writes to shards
100	100 writes to shards
1000	1000 writes to shards

Pattern observation: The number of write operations grows directly with the number of items.

Final Time Complexity

Time Complexity: O(n)

This means the time to write grows linearly as you add more items, even when using shards.

Common Mistake

[X] Wrong: "Using more shards makes writing faster and reduces time complexity to constant."

[OK] Correct: While shards help distribute load, you still write each item once, so total time grows with data size.

Interview Connect

Understanding how sharding affects write time helps you explain scaling strategies clearly and confidently.

Self-Check

What if we batch multiple writes together per shard? How would that change the time complexity?

Practice

1. What is the main purpose of write sharding in DynamoDB?

easy

A. To backup data automatically to S3

B. To spread write load across multiple partitions by adding shard IDs

C. To encrypt data at rest for security

D. To reduce read latency by caching data locally

Solution

1. Step 1: Understand write sharding concept

   Write sharding adds shard IDs to partition keys to distribute writes evenly.

2. Step 2: Identify the main goal

   This distribution avoids hot partitions and improves write performance.

3. Final Answer:

   To spread write load across multiple partitions by adding shard IDs -> Option B

4. Quick Check:

   Write sharding = spreading writes [OK]

Hint: Write sharding spreads writes by adding shard IDs [OK]

Common Mistakes:

• Confusing write sharding with read caching
• Thinking it encrypts data
• Assuming it handles backups

2. Which of the following is the correct way to implement write sharding in a DynamoDB partition key?

easy

A. Use a fixed partition key without any shard ID

B. Use the sort key as the shard ID

C. Append a random shard ID to the partition key before writing

D. Write all data to a single partition key

Solution

1. Step 1: Recall write sharding method

   Write sharding requires adding a shard ID to the partition key to distribute writes.

2. Step 2: Identify correct implementation

   Appending a random shard ID to the partition key spreads writes across partitions.

3. Final Answer:

   Append a random shard ID to the partition key before writing -> Option C

4. Quick Check:

   Shard ID + partition key = write sharding [OK]

Hint: Add random shard ID to partition key for sharding [OK]

Common Mistakes:

• Not adding shard ID at all
• Using sort key as shard ID incorrectly
• Writing all data to one partition

3. Given the following code snippet for write sharding, what is the expected effect?

shard_id = random.randint(0, 4)
partition_key = f"user#{user_id}#{shard_id}"
dynamodb_table.put_item(Item={"PK": partition_key, "Data": data})

medium

A. Writes are distributed across 5 partitions reducing hot spots

B. All writes go to the same partition causing throttling

C. Writes fail due to invalid partition key format

D. Data is only readable by shard_id 0

Solution

1. Step 1: Analyze shard ID usage

   The shard_id is a random number from 0 to 4, appended to the partition key.

2. Step 2: Understand partition key effect

   This creates 5 different partition keys for the same user, spreading writes across 5 partitions.

3. Final Answer:

   Writes are distributed across 5 partitions reducing hot spots -> Option A

4. Quick Check:

   Random shard ID 0-4 = 5 partitions [OK]

Hint: Random shard ID 0-4 means 5 partitions [OK]

Common Mistakes:

• Assuming all writes go to one partition
• Thinking partition key format is invalid
• Believing data is restricted by shard ID

4. You implemented write sharding by appending shard IDs to partition keys, but you notice some writes still cause throttling. What is the likely cause?

medium

A. Shard ID range is too small causing uneven distribution

B. You forgot to add shard ID to the sort key

C. You used a random shard ID but did not update the partition key

D. DynamoDB does not support write sharding

Solution

1. Step 1: Check shard ID range

   If the shard ID range is too small, writes cluster on few partitions causing throttling.

2. Step 2: Verify correct key usage

   Shard ID must be part of the partition key, not sort key, and must cover enough range.

3. Final Answer:

   Shard ID range is too small causing uneven distribution -> Option A

4. Quick Check:

   Small shard range = hot partitions [OK]

Hint: Use enough shard IDs to spread writes evenly [OK]

Common Mistakes:

• Adding shard ID to sort key instead of partition key
• Not updating partition key with shard ID
• Believing DynamoDB disallows sharding

5. You want to design a write sharding strategy for a DynamoDB table with very high write traffic on user data. Which approach best balances write load and allows efficient reads?

hard

A. Write all data to a single partition key and batch writes

B. Use user ID as partition key without sharding; rely on DynamoDB auto-scaling

C. Add shard ID to sort key and keep partition key as user ID

D. Add a random shard ID (0-9) to the partition key and store user data in each shard; aggregate reads by querying all shards

Solution

1. Step 1: Evaluate write sharding options

   Adding a random shard ID (0-9) to partition key spreads writes across 10 partitions.

2. Step 2: Consider read strategy

   Reads require querying all shards and aggregating results, which is manageable for balanced load.

3. Step 3: Compare other options

   Using no sharding risks throttling; shard ID in sort key does not distribute writes; single partition causes hot spots.

4. Final Answer:

   Add a random shard ID (0-9) to the partition key and store user data in each shard; aggregate reads by querying all shards -> Option D

5. Quick Check:

   Shard ID in partition key + aggregate reads = balanced writes [OK]

Hint: Shard in partition key, aggregate reads from all shards [OK]

Common Mistakes:

• Not sharding partition key causing hot partitions
• Adding shard ID to sort key only
• Ignoring read complexity after sharding