Dynamic Sharding & Consistent Hashing — Class Notes

1. Why do we need Dynamic Sharding?

In a distributed database, data is split across multiple database servers called shards.

A common approach is hash-based sharding:

shard = hash(recordKey) % N

Where:

recordKey → ID/key of the record
hash() → hash function
N → number of database shards

Example

Suppose we have 4 shards:

hash(userId) % 4

User ID	Hash % 4	Shard
User A	0	Shard 0
User B	1	Shard 1
User C	2	Shard 2
User D	3	Shard 3

This works well as long as the number of shards doesn't change.

2. Problem with Traditional Hash-Based Sharding

The biggest problem occurs when we add or remove database servers.

Initially

Number of shards = 4

shard = hash(key) % 4

Suppose:

hash(User123) = 10

10 % 4 = 2

So User123 is stored in:

Shard 2

What happens when we add a server?

Now we have 5 shards:

shard = hash(key) % 5

For the same user:

10 % 5 = 0

The system now expects User123 in:

Shard 0

But the record is actually still in:

Shard 2

Result

A huge number of records need to be redistributed.

Before:

        Shard 0
        Shard 1
        Shard 2
        Shard 3

             ↓ Add Shard 4

        Shard 0
        Shard 1
        Shard 2
        Shard 3
        Shard 4

             ↓

Many keys get different shard assignments
             ↓
Large-scale data migration

The same problem occurs when removing a server.

3. Problems with Traditional Hashing

There are two major problems.

Problem 1 — Adding/removing nodes

Changing N changes:

hash(key) % N

Therefore, many keys get assigned to different shards.

This causes:

Large data movement
High network traffic
Disk I/O
Increased load
Potential downtime/performance degradation

Problem 2 — Different server capacities

Suppose we have:

Server A → 16 GB RAM
Server B → 64 GB RAM
Server C → 128 GB RAM

Traditional hashing treats them equally.

Server A → 33%
Server B → 33%
Server C → 33%

But this isn't necessarily ideal.

The more powerful server should potentially handle more data/traffic.

4. Consistent Hashing

Consistent hashing solves the major redistribution problem by hashing:

Database records/keys
Database nodes

into the same hash space.

Instead of:

hash(key) % N

we create a circular hash space called a hash ring.

5. Consistent Hashing Ring

Imagine the hash space as a circle:

                     25
                +----------+
             10              40
           /                    \
          /                      \
        90                        55
          \                      /
           \                    /
             75              65
                +----------+

The hash values wrap around.

For example:

0 → 1 → 2 → ... → 99 → back to 0

So:

99 → 0

The hash space is continuous.

6. Hash Both Nodes and Keys

Suppose we have:

Node 1
Node 2
Node 3

We hash their identifiers:

hash(Node 1) → 31
hash(Node 2) → 99
hash(Node 3) → 58

We also hash data keys:

hash(Key A) → 40
hash(Key B) → 57
hash(Key C) → 75
hash(Key D) → 2

Everything exists on the same ring.

7. How is a Key Assigned to a Node?

A key belongs to the next node encountered while moving clockwise around the ring.

This is the most important rule to remember.

Example

Node 1 → position 31
Node 5 → position 58
Node 2 → position 99

Consider:

Key A → position 40

Move clockwise:

40 → 58

Therefore:

Key A → Node 5

Another key:

Key B → position 75

Move clockwise:

75 → 99

Therefore:

Key B → Node 2

Another key:

Key C → position 10

Move clockwise:

10 → 31

Therefore:

Key C → Node 1

8. Why is Consistent Hashing Better?

The biggest advantage is:

Adding or removing a node affects only a small portion of the keys.

We don't need to redistribute the entire database.

9. Removing a Node

Suppose:

Node 1 → 31
Node 5 → 58
Node 2 → 99

And we remove:

Node 2 → 99

The keys belonging to Node 2 simply move to the next node clockwise.

Because the ring is circular, that might be Node 1.

Before:

             Node 2
               99
                |
        Keys belonging
        to Node 2
                |
                ↓
              Node 1
                31

After removing Node 2:

Keys of Node 2
      ↓
Node 1

Important

Keys belonging to other nodes don't need to move.

Node 5 → unchanged
Node 1 → mostly unchanged
Node 2 → removed

This dramatically reduces data migration.

10. Adding a Node

Now suppose we add:

New Node → position 31

Previously:

Node 1 → position 40

Some of Node 1's keys now fall into the new node's range.

Only those keys need to move.

Before:

       Node 1
       40

       ↓ Add New Node

New Node
   31

Node 1
   40

Only the affected range moves.

Old Node 1
     |
     | affected keys
     ↓
New Node

The rest of the cluster remains untouched.

11. Key Advantage of Consistent Hashing

Traditional hashing:

hash(key) % N

Changing N can cause:

Many keys
   ↓
Different shard
   ↓
Large data migration

Consistent hashing:

Add/remove node
       ↓
Only affected ring range
       ↓
Small data migration

Interview statement

Consistent hashing minimizes key redistribution when nodes are added or removed.

12. Handling Servers with Different Capacities

Another advantage is that consistent hashing can handle heterogeneous servers.

Suppose:

Node 0 → Weak
Node 1 → 2× more powerful
Node 2 → 3× more powerful

We don't necessarily want:

Node 0 → 33%
Node 1 → 33%
Node 2 → 33%

Instead, we can assign more positions on the ring to powerful nodes.

13. Virtual Nodes

This is achieved using virtual nodes, also called vnodes.

Instead of representing one physical server with one position:

Physical Node 0 → 1 virtual node
Physical Node 1 → 2 virtual nodes
Physical Node 2 → 3 virtual nodes

We might have:

Node 0:
    V0

Node 1:
    V1a
    V1b

Node 2:
    V2a
    V2b
    V2c

On the hash ring:

             V2a
              |
       V1a         V2b
          \       /
           \     /
            V0
           /  \
        V2c   V1b

Now Node 2 owns multiple portions of the ring.

Therefore, statistically:

Node 2 → more keys
Node 1 → medium number of keys
Node 0 → fewer keys

This allows us to use servers with different hardware capabilities.

14. Why Virtual Nodes Are Important

Virtual nodes provide two benefits:

1. Capacity weighting

Powerful server:

More virtual nodes
        ↓
Larger portion of hash ring
        ↓
More data

Weak server:

Fewer virtual nodes
        ↓
Smaller portion of hash ring
        ↓
Less data

2. Better load distribution

Multiple positions spread a physical node's responsibility across the ring.

This reduces the chance that one server receives an unusually large continuous range.

15. Uneven Load Distribution Problem

Even with consistent hashing, there is another problem.

Suppose we have only three nodes:

Node A
Node B
Node C

After hashing their identifiers:

Node A → 10
Node B → 15
Node C → 90

The ring could look like:

0 ---- A -- B -------------------------- C ---- 100

Node C may own a very large or small portion depending on the positions.

Therefore:

Node A → 5% keys
Node B → 10% keys
Node C → 85% keys

This creates a hotspot.

                Too much traffic
                      ↓
                   Node C
                      ↓
                 Bottleneck

While:

Node A → underutilized
Node B → underutilized

16. Solution — Multiple Hash Positions

One solution is to map each physical node to multiple positions on the ring.

For example, instead of:

Node 0 → 1 position
Node 1 → 1 position
Node 2 → 1 position

we can have:

Node 0 → 2 positions
Node 1 → 2 positions
Node 2 → 2 positions

Conceptually:

Hash Function 1:

Node 0 → 99
Node 1 → 16
Node 2 → 65


Hash Function 2:

Node 0 → another position
Node 1 → another position
Node 2 → another position

Now every physical node has multiple points on the ring.

17. Better Distribution

With a single position:

Node 0 ───────────── Node 1 ─── Node 2

The ranges can be very uneven.

With multiple positions:

Node 0 ─ Node 2 ─ Node 1 ─ Node 0 ─ Node 2 ─ Node 1

Each physical node owns multiple smaller ranges.

Statistically, this produces a much more balanced distribution.

18. Consistent Hashing Architecture

A typical distributed database can look like:

                  Client
                    |
                    v
             Application Layer
                    |
                    v
          +---------------------+
          | Hashing / Router    |
          +---------------------+
                    |
              Hash(recordKey)
                    |
                    v
             Consistent Hash Ring
                    |
       +------------+------------+
       |            |            |
       v            v            v
    Node A        Node B       Node C
       |            |            |
       v            v            v
    Database      Database     Database

The router determines which node owns the key.

19. Complete Flow

Write

Client
  |
  | Write(key, value)
  v
Application
  |
  | hash(key)
  v
Consistent Hash Ring
  |
  | Find next clockwise node
  v
Database Node
  |
  v
Store record

Read

Client
  |
  | Read(key)
  v
Application
  |
  | hash(key)
  v
Consistent Hash Ring
  |
  | Find owner
  v
Database Node
  |
  v
Return record

The important point is that the application/router can determine where the key should live without querying every database server.

20. Node Addition Flow

Existing Cluster

Node A
Node B
Node C

      ↓

Add Node D

      ↓

Hash Node D

      ↓

Node D gets a position/range
on the consistent hash ring

      ↓

Only keys in that affected
range are migrated

      ↓

Cluster continues operating

21. Node Removal Flow

Node B fails/removes
       ↓
Identify Node B's ring ranges
       ↓
Transfer those ranges
to the next responsible node
       ↓
Other ranges remain unchanged

This makes scaling much easier.

22. Traditional Hashing vs Consistent Hashing

Feature	Traditional Hashing	Consistent Hashing
Formula	`hash(key) % N`	Hash key onto ring
Hash nodes?	Usually no	Yes
Hash keys?	Yes	Yes
Data structure	Fixed partitions	Circular hash ring
Add node	Large redistribution	Small redistribution
Remove node	Large redistribution	Small redistribution
Heterogeneous hardware	Difficult	Easy with virtual nodes
Load balancing	Can be uneven	Better with multiple positions/vnodes
Scalability	Limited	Excellent
Common use	Simple sharding	Distributed systems

23. Important Terminology

Hash Space

The complete range of possible hash values.

0 → 99

Hash Ring

The hash space represented as a circle:

0 → 99 → 0

Physical Node

An actual database server.

DB Server 1
DB Server 2
DB Server 3

Virtual Node

A logical position on the hash ring representing a physical node.

Physical Node A
    ↓
Virtual A1
Virtual A2
Virtual A3

Key Redistribution

Moving records from one database node to another when ownership changes.

Consistent hashing minimizes this redistribution.

24. Key Takeaways

Remember these 5 points for interviews:

1. Traditional hashing has a scaling problem

hash(key) % N

Changing N changes the mapping of many keys.

2. Consistent hashing uses a hash ring

Both:

Database keys
+
Database nodes

are mapped into the same hash space.

3. Adding/removing nodes causes minimal movement

Only the affected range of keys needs to move.

4. Virtual nodes handle different server capacities

Powerful server
      ↓
More virtual nodes
      ↓
More hash-ring ranges
      ↓
More data

5. Multiple positions improve load balancing

Instead of giving each physical node one position, give it multiple positions.

Multiple positions
        ↓
Smaller ranges
        ↓
Better statistical distribution
        ↓
Fewer hotspots

Interview-ready definition

Consistent hashing is a distributed hashing technique that maps both data keys and nodes onto the same circular hash space. When nodes are added or removed, only a small portion of the keys need to be redistributed, making it highly suitable for dynamically scalable distributed systems. Virtual nodes can be used to support servers with different capacities and improve load distribution.

Wednesday, 26 August 2026