Hash-based sharding in MongoDB - Deep Dive

Overview - Hash-based sharding

What is it?

Hash-based sharding is a way to split a large database into smaller parts called shards. It uses a hash function to decide which shard stores each piece of data. This helps spread data evenly across many servers. It makes the database faster and able to handle more users.

Why it matters

Without hash-based sharding, databases can become slow and overloaded as data grows. This method solves the problem by balancing data evenly, so no single server gets too busy. It helps websites and apps stay fast and reliable even with lots of users and data.

Where it fits

Before learning hash-based sharding, you should understand basic database concepts and what sharding means. After this, you can learn about other sharding methods like range-based sharding and how to manage distributed databases.

Mental Model

Core Idea

Hash-based sharding uses a hash function to evenly distribute data across multiple database servers to balance load and improve performance.

Think of it like...

Imagine sorting mail by putting each letter into one of many mailboxes based on a secret code on the envelope. The code (hash) decides which mailbox (shard) gets the letter, so no mailbox gets too full.

┌───────────────┐
│   Data Item   │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│  Hash Function│
└──────┬────────┘
       │
       ▼
┌──────┴───────┐   ┌──────┴───────┐   ┌──────┴───────┐
│   Shard 1    │   │   Shard 2    │   │   Shard 3    │
└──────────────┘   └──────────────┘   └──────────────┘

Build-Up - 7 Steps

1

Foundation

What is Sharding in Databases

Concept: Introduces the basic idea of splitting data across multiple servers.

Sharding means breaking a big database into smaller parts called shards. Each shard holds a portion of the data. This helps the database handle more data and users by sharing the work across servers.

Result

You understand that sharding divides data to improve database scalability and performance.

Knowing what sharding is sets the stage for understanding how different methods decide where data goes.

2

Foundation

Understanding Hash Functions

Concept: Explains what a hash function is and how it creates a fixed output from any input.

A hash function takes any input (like a username) and turns it into a number called a hash value. This number looks random but is always the same for the same input. Hash functions help quickly find or place data.

Result

You grasp that hash functions create consistent, unique numbers from data to help organize it.

Understanding hash functions is key because hash-based sharding uses them to decide data placement.

3

Intermediate

How Hash-based Sharding Works

🤔Before reading on: do you think hash-based sharding always keeps related data together or spreads it out? Commit to your answer.

Concept: Shows how the hash function assigns data to shards evenly but without grouping related data.

When data comes in, the system applies a hash function to a chosen key (like user ID). The hash value determines which shard stores the data by using a formula like modulo (hash % number_of_shards). This spreads data evenly but may separate related items.

Result

You see that hash-based sharding balances data well but does not keep related data on the same shard.

Knowing that hash-based sharding prioritizes even distribution over data locality helps explain its strengths and limits.

4

Intermediate

Choosing the Shard Key for Hashing

🤔Before reading on: do you think any field can be a good shard key for hash-based sharding? Commit to your answer.

Concept: Discusses how picking the right field to hash affects performance and balance.

The shard key is the field used to compute the hash. It should have many unique values to spread data evenly. Using a field with few unique values causes uneven shards and slow queries. For example, user ID is often a good shard key.

Result

You understand that the shard key choice impacts how well data is balanced and how fast queries run.

Recognizing the importance of shard key selection prevents common performance problems in hash-based sharding.

5

Intermediate

Handling Data Growth and Rebalancing

🤔Before reading on: do you think hash-based sharding automatically moves data when adding new shards? Commit to your answer.

Concept: Explains challenges when adding or removing shards and how data must be moved or rehashed.

When you add a new shard, the hash function changes because the number of shards changes. This means many data items must move to new shards to keep balance. This process is called rebalancing and can be complex and slow.

Result

You realize that scaling hash-based sharding requires careful data movement to maintain balance.

Understanding rebalancing challenges helps prepare for managing growing databases with hash-based sharding.

6

Advanced

MongoDB’s Hash-based Sharding Implementation

🤔Before reading on: do you think MongoDB uses the raw hash value as the shard key or modifies it? Commit to your answer.

Concept: Details how MongoDB applies hashing and manages chunks for balanced sharding.

MongoDB hashes the shard key value and uses the hash to assign data to chunks. Each chunk covers a range of hash values and is assigned to a shard. MongoDB automatically splits and migrates chunks to keep shards balanced as data grows.

Result

You see how MongoDB’s system manages hash-based sharding dynamically to maintain performance.

Knowing MongoDB’s chunk system reveals how hash-based sharding works in real production systems.

7

Expert

Trade-offs and Limitations of Hash-based Sharding

🤔Before reading on: do you think hash-based sharding is always the best choice for all workloads? Commit to your answer.

Concept: Explores when hash-based sharding may cause problems and what alternatives exist.

Hash-based sharding evenly distributes data but breaks data locality, making some queries slower if they need related data from multiple shards. It also requires rebalancing when shards change. Alternatives like range-based sharding keep related data together but risk uneven load.

Result

You understand the trade-offs and when to choose or avoid hash-based sharding.

Recognizing these limits helps experts design better database architectures tailored to workload needs.

Under the Hood

Hash-based sharding works by applying a hash function to the shard key of each data item. This hash value is then used to determine the shard by calculating the remainder when divided by the number of shards (modulo operation). Internally, MongoDB manages data in chunks, each representing a range of hash values. These chunks are assigned to shards and can be split or migrated to balance load. The system tracks chunk metadata to route queries to the correct shard.

Why designed this way?

Hash-based sharding was designed to solve uneven data distribution problems seen in range-based sharding. By using a hash function, data is spread evenly regardless of the shard key's natural order. This avoids hotspots where one shard gets too much data or traffic. The trade-off is losing data locality, but the gain is predictable, balanced load across shards.

┌───────────────┐
│  Data Item    │
│ (shard key)   │
└──────┬────────┘
       │
       ▼
┌───────────────┐
│  Hash Function│
│  (e.g. MD5)   │
└──────┬────────┘
       │ hash value
       ▼
┌───────────────┐
│ Modulo Number │
│ (hash % N)    │
└──────┬────────┘
       │ shard ID
       ▼
┌───────────────┐
│   Chunk Map   │
│ (hash ranges) │
└──────┬────────┘
       │
       ▼
┌───────────────┐   ┌───────────────┐   ┌───────────────┐
│   Shard 1    │   │   Shard 2    │   │   Shard 3    │
└──────────────┘   └──────────────┘   └──────────────┘

Myth Busters - 4 Common Misconceptions

Quick: Does hash-based sharding keep related data together on the same shard? Commit to yes or no.

Common Belief: Hash-based sharding groups related data on the same shard for faster queries.

Reality: Hash-based sharding spreads data evenly but does not keep related data together, which can slow queries needing multiple shards.

Why it matters: Assuming data locality can cause poor query performance and unexpected complexity in application design.

Quick: When adding a new shard, does hash-based sharding automatically keep all data in place? Commit to yes or no.

Common Belief: Adding shards does not require moving existing data because the hash function keeps data stable.

Reality: Changing the number of shards changes the hash modulo, so many data items must be moved to new shards to maintain balance.

Why it matters: Ignoring this leads to downtime or slow rebalancing during scaling, affecting availability.

Quick: Can any field be used as a shard key in hash-based sharding? Commit to yes or no.

Common Belief: Any field can be used as a shard key and will distribute data evenly.

Reality: Fields with low uniqueness cause uneven shard distribution and hotspots, hurting performance.

Why it matters: Choosing a poor shard key leads to unbalanced shards and slow database operations.

Quick: Is hash-based sharding always better than range-based sharding? Commit to yes or no.

Common Belief: Hash-based sharding is always the best because it balances data perfectly.

Reality: Hash-based sharding sacrifices data locality and can slow queries needing related data, so range-based sharding is better for some workloads.

Why it matters: Using hash-based sharding blindly can cause inefficient queries and wasted resources.

Expert Zone

1

Hash-based sharding requires careful chunk management to avoid excessive chunk splitting and migration overhead.

2

The choice of hash function affects collision rates and distribution uniformity, impacting performance subtly.

3

MongoDB’s balancer process runs in the background to move chunks, but its timing and thresholds can affect system responsiveness.

When NOT to use

Avoid hash-based sharding when your application needs to query ranges or related data frequently, as it scatters related records. Instead, use range-based sharding or zone sharding to keep related data together for faster queries.

Production Patterns

In production, hash-based sharding is often combined with careful shard key selection and monitoring of chunk sizes. Teams use automated balancer tuning and sometimes hybrid sharding strategies to optimize performance and scalability.

Connections

Consistent Hashing

Builds-on

Understanding consistent hashing helps grasp advanced sharding that minimizes data movement when scaling shards.

Load Balancing in Networks

Same pattern

Both use hashing to evenly distribute requests or data to avoid overload on any single server.

Modular Arithmetic in Mathematics

Underlying principle

Knowing modular arithmetic clarifies how hash values map to shard numbers, making the distribution predictable.

Common Pitfalls

#1 Choosing a shard key with few unique values causing uneven data distribution.

Wrong approach:

sh.shardCollection('users', { country: 'hashed' })

Correct approach:

sh.shardCollection('users', { userId: 'hashed' })

Root cause:

Misunderstanding that the shard key must have high cardinality to distribute data evenly.

#2 Assuming data stays on the same shard after adding new shards.

Wrong approach:

Adding shards without planning for data migration, expecting no impact.

Correct approach:

Planning chunk migrations and rebalancing when adding shards to maintain balance.

Root cause:

Not realizing that changing shard count changes hash modulo, requiring data movement.

#3 Using hash-based sharding for queries needing data locality.

Wrong approach:

Designing queries that join related data scattered across shards without considering performance.

Correct approach:

Using range-based sharding or embedding related data to optimize locality.

Root cause:

Ignoring the trade-off between even distribution and data locality in hash-based sharding.

Key Takeaways

Hash-based sharding uses a hash function on a shard key to evenly spread data across multiple servers.

Choosing a high-cardinality shard key is critical to avoid unbalanced shards and performance issues.

Hash-based sharding sacrifices data locality, which can slow queries needing related data from multiple shards.

Scaling with hash-based sharding requires rebalancing data because adding shards changes the hash distribution.

Understanding the trade-offs helps choose the right sharding method for your database workload.