Hash-based sharding in MongoDB - Time & Space Complexity

Time Complexity: Hash-based sharding

O(1)

Understanding Time Complexity

When using hash-based sharding in MongoDB, we want to understand how the time to find or store data changes as the database grows.

We ask: How does the number of operations grow when we add more data?

Scenario Under Consideration

Analyze the time complexity of this hash-based shard key lookup.

// Assume a collection sharded by hashed _id
const shardKey = hashFunction(document._id);
const shard = findShardForKey(shardKey);
const result = db.collection.find({ _id: document._id });
    

This code finds the shard by hashing the document's _id, then queries that shard for the document.

Identify Repeating Operations

Look for repeated steps that affect performance.

• Primary operation: Hashing the shard key and locating the shard.
• How many times: Once per query or insert operation.

How Execution Grows With Input

As the number of documents grows, the hash function still runs once per operation, and the shard lookup remains quick.

Input Size (n)	Approx. Operations
10	~1 hash + 1 shard lookup
100	~1 hash + 1 shard lookup
1000	~1 hash + 1 shard lookup

Pattern observation: The number of operations stays about the same no matter how big the data is.

Final Time Complexity

Time Complexity: O(1)

This means each query or insert takes about the same time regardless of how much data there is.

Common Mistake

[X] Wrong: "Hash-based sharding slows down as data grows because it has to check many shards."

[OK] Correct: The hash function directly points to the correct shard, so only one shard is checked, keeping the operation fast.

Interview Connect

Understanding how hash-based sharding keeps queries fast helps you explain how large databases stay efficient as they grow.

Self-Check

"What if we changed from hash-based sharding to range-based sharding? How would the time complexity change?"

Practice

1.

What is the main purpose of hash-based sharding in MongoDB?

easy

A. To store data in sorted order on each shard

B. To compress data before storing it

C. To replicate data for backup purposes

D. To evenly distribute data across shards using a hash function

Solution

1. Step 1: Understand hash-based sharding concept

   Hash-based sharding uses a hash function on the shard key to distribute data evenly.

2. Step 2: Compare options with concept

   Only To evenly distribute data across shards using a hash function describes even distribution using hashing, which matches the concept.

3. Final Answer:

   To evenly distribute data across shards using a hash function -> Option D

4. Quick Check:

   Hash-based sharding = even data distribution [OK]

Hint: Hash-based sharding means even spread by hashing key [OK]

Common Mistakes:

• Confusing hash-based with range-based sharding
• Thinking it sorts data on shards
• Mixing sharding with replication

2.

Which of the following is the correct way to create a hashed shard key on the field userId in MongoDB?

sh.shardCollection("mydb.users", { ??? })

easy

A. { userId: 1 }

B. { userId: "hashed" }

C. { userId: -1 }

D. { userId: true }

Solution

1. Step 1: Recall syntax for hashed shard key

   MongoDB requires the shard key field to be set to "hashed" as a string to enable hash-based sharding.

2. Step 2: Match options with syntax

   Only { userId: "hashed" } uses the correct syntax: { userId: "hashed" }.

3. Final Answer:

   { userId: "hashed" } -> Option B

4. Quick Check:

   Hashed shard key syntax = { field: "hashed" } [OK]

Hint: Hashed keys use string "hashed" in shard key spec [OK]

Common Mistakes:

• Using 1 or -1 instead of "hashed"
• Using boolean true instead of string
• Omitting quotes around hashed

3.

Given a collection sharded by { userId: "hashed" }, which shard will store the document { userId: 42, name: "Alice" }?

Assume the hash function maps 42 to a hash value that falls into shard 2's range.

medium

A. Shard 2

B. Cannot determine without full hash map

C. Shard 3

D. Shard 1

Solution

1. Step 1: Understand hashed shard key routing

   Documents are routed to shards based on the hash of the shard key value.

2. Step 2: Use given hash mapping

   The problem states the hash of 42 falls into shard 2's range, so the document goes to shard 2.

3. Final Answer:

   Shard 2 -> Option A

4. Quick Check:

   Hash value maps to shard 2 [OK]

Hint: Hash value decides shard, not raw key [OK]

Common Mistakes:

• Assuming shard based on userId value directly
• Choosing 'Cannot determine' when info is given
• Confusing shard ranges with key values

4.

Consider this command to shard a collection:

sh.shardCollection("mydb.orders", "orderId: hashed")

After running this, you get an error: "Error: shard key must be an object". What is the likely cause?

medium

A. The shard key argument must be an object, but a string was passed

B. The shard key value should be 1 or -1, not "hashed"

C. The command syntax is correct; the error is from elsewhere

D. The database name is missing in the command

Solution

1. Step 1: Check shardCollection syntax

   The shard key must be an object specifying the field and type, e.g., { orderId: "hashed" }.

2. Step 2: Identify error cause

   The error says shard key must be an object, so likely the argument passed was not an object but a string or other type.

3. Final Answer:

   The shard key argument must be an object, but a string was passed -> Option A

4. Quick Check:

   Shard key must be an object [OK]

Hint: Shard key must be an object, not a string [OK]

Common Mistakes:

• Passing shard key as string instead of object
• Confusing shard key with database name
• Ignoring error message details

5.

You want to shard a collection by email using hash-based sharding. However, you notice some shards have much more data than others. What could be a reason for this uneven distribution?

hard

A. The shard key was set to { email: 1 } instead of hashed

B. Hash-based sharding always causes uneven data distribution

C. The email field has many duplicate values causing hash collisions

D. The collection is too small to distribute evenly

Solution

1. Step 1: Understand hash-based sharding behavior

   Hash-based sharding usually distributes data evenly unless many documents share the same shard key value.

2. Step 2: Analyze cause of uneven data

   If many documents have the same email, their hash is the same, so they go to the same shard, causing imbalance.

3. Final Answer:

   The email field has many duplicate values causing hash collisions -> Option C

4. Quick Check:

   Duplicate keys cause uneven shard data [OK]

Hint: Duplicates in shard key cause uneven shard sizes [OK]

Common Mistakes:

• Assuming hash sharding always balances perfectly
• Confusing range-based with hash-based sharding
• Ignoring data distribution of shard key values